第1章 绪论
1．数据结构包括 数据的逻辑结构 、 数据的存储结 和 数据的运算 三方面的内容。
2．程序包括两个内容： 和 。
3. 数据结构的形式定义为：数据结构是一个二元组： Data_Structure=(D,R) 。 4. 数据的逻辑结构在计算机存储器内的表示，称为数据的 。
5. 数据的逻辑结构可以分类为 线性结构 结构和 非线性结构 结构两大类。 6. 在图状结构中，每个结点的前驱结点数和后继结点数可以 。 7. 在树形结构中，数据元素之间存在 一对多 的关系。
8. 数据的物理结构，指数据元素在 中的标识（映象），也即 存储结构 。 9. 数据的逻辑结构包括 集合 、 线性结构和 非线性结构 3种类型，树型结构和有向图结构合称为 非线性结构 。
10. 顺序存储结构是把逻辑上相邻的结点存储在物理上 相邻 的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。
11. 链式存储结构是把逻辑上相邻的结点存储在物理上 任意 的存储单元里，节点之间的逻辑关系由附加的指针域来体现。
12. 数据的存储结构可用4种基本的存储方法表示，它们分别是 顺序存储方法 、 链式存储方法 、
索引存储方法 和 散列存储方法 。
13. 线性结构反映结点间的逻辑关系是 的，非线性结构反映结点间的逻辑关系是 。
14. 数据结构在物理上可分为 存储结构和 存储结构。
15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的 方式，还给出了处理数据的 。
16. 数据元素可由若干个 组成。
17. 算法分析的两个主要方面是 时间复杂度和 空间 复杂度。
18. 一个算法的时间复杂度是用该算法 的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的 的大小来度量的。
19. 算法具有如下特点： 有穷性 、确定性、 可行性 、输入、输出。
20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的 的定义，并在 内计算出结果。 21. 下面程序段的时间复杂度为 。
1
i=1； while(i<=n) i= i﹡3；
第2章 线性表
1. 一线性表表示如下：（a1，a2，…，ai-1，ai，ai+1，…，an），其中每个ai代表一个 数据元素 。a1称为 结点，an称为 结点，i称为ai在线性表中的 。对任意一对相邻结点ai，ai+1，（1≤i≤n），ai称为ai+1的直接 ，ai+1称为ai的直接 。 2. 对一个长度为n的线性表，要删除第i个元素，则在顺序表示的情况下，计算复杂性为 ，在链式表示的情况下，计算复杂性为 。
3. 在一个长度为n的顺序表中，向第i个元素（1≤i≤n）之前插入一个新元素时，需向后移动 个元素。
4. 顺序表中逻辑上相邻的元素在物理位置上 相连。
5. 在n个结点的顺序表中插入一个结点需平均移动 个结点，具体的移动次数取决于 。
6. 在顺序表中访问任意一个结点的时间复杂度均为 ，因此，顺序表也称为 的数据结构。
7. 顺序表相对于链表的优点有 存储密度高和 随机访问方便 。 8. 在长度为n的顺序表中插入一个元素的时间复杂度为 。
9. 在带有头结点的单链表L中，若要删除第一个结点，则须执行下列三条语句： ；L->next=U->next；free（U）。
10. 链表相对于顺序表的优点有 和 操作方便。
11. 在单链表中除首结点外，任意结点的存储位置都由 结点中的指针指示。
12. 在n个结点的单链表中要删除已知结点*p，需找到 ，其时间复杂度为 。 13．单链表中设置头结点的作用是 。
14．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的 结点。 15. 在双链表中，每个结点有两个指针域，一个指向 ，另一个指向 。 16. 带头结点的单链表L为空的判定条件是 ，不带头结点的单链表L为空的判定条件是 。
17. 在单链表中，指针p所指结点为最后一个结点的条件是 。
18. 循环链表的最大优点是 。 19. 设rear是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的存储位置是 。
2
20. 带头结点的双向循环表L为空表的条件是 。
21. 在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道 才能遍历整个链表。
22. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 。
第3章 栈和队列
1. 栈又称为 表，队列又称为 表。
2. 向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把待插入元素 到这个位置上。
3. 从一个栈删除元素时，需要前移一位 。
4. 在一个顺序栈中，若栈顶指针等于 ，则为空栈； 若栈顶指针等于 ，则为满栈。
5. 在一个链式栈中，若栈顶指针等于NULL，则为 ；在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为 或该队列 。
6. 向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给 ，然后把新结点的存储位置赋给 。
7．在求表达式值的算符优先算法中使用的主要数据结构是 。
8．设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为 。
9. 设有一个空栈，现输入序列为1，2，3，4，5。经过push，push，pop，push，pop，push，pop，push后，输出序列是 。
10. 在按算符优先法求解表达式3－1＋5*2时，最先执行的运算是 ，最后执行的运算是 。 11. 在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求 。 12. 仅允许在同一端进行插入和删除的线性表称为 。
13. 在顺序栈s中，栈为空的条件是 ，栈为满的条件是 s.top－s.base＞=s.stacksize 。 14. 设有算术表达式x＋a*（y－b）－c/d，该表达式的前缀表示为 。 后缀表示为 。
15. 用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S、X操作串为 。
16. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行 和 操作。 17. 从一个栈顶指针为top的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 操作。
18. 设有一个空栈，栈顶指针为1000H（十六进制。现有输入序列为1，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是 ，而栈顶指针是 H。设栈为顺序栈，每个元素占4个字节。
19. 在作入栈运算时应先判别栈是否 ；在作出栈运算时应先判别栈是否 。
3
10. 用一个大小为1000的数组来实现循环队列，当前rear和front的值分别为0和994，若要达到队满的条件，还需要继续入队的元素个数是 。
20. 队列的插入操作在 进行，删除操作在 进行。
21. 在一个循环队列Q中，判断队空的条件为 ，判断队满的条件为 。
22. 向一个循环队列中插入元素时，需要首先移动 ，然后再向所指位置 新插入的元素。
23. 当用长度为n的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为 。
24. 循环队列的引入，目的是为了克服 。
第4章 串
1. 两个串相等的充分必要条件是 。
2. 空格串是 ，其长度等于 。 3. 模式串′abaabade′的next函数值为 补充：
1. 串的两种最基本的存储方式是 。 2. 空串是 ，其长度等于 。 3. 组成串的数据元素只能是 。
4. 串是一种特殊的线性表，其特殊性表现在 。
第5章 数组
1. 将下三角矩阵A[1..8，1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则元素A[7，5]的地址为 。
2. 二维数组A[0…9，0…19]采用列序为主方式存储，每个元素占一个存储单元，并且元素A[0，0]的存储地址是200，则元素A[6，12]的地址是 。
3. 二维数组A[10…20，5…10]采用行序为主方式存储，每个元素占4个存储单元，并且元素A[10，5]的存储地址是1000，则元素A[18，9]的地址是 。 补充：
1. 一维数组的逻辑结构是 ，存储结构是 。
2. 对于二维数组或多维数组，分为按 和按 两种不同的存储方式存储。 3. 对矩阵压缩存储是为了 。
4. 二维数组是一种非线性结构，其中的每一个数组元素最多有 个直接前驱（或直接后继）。
第6章 树
4. 结点最少的树为 ，结点最少的二叉树为 。
4
5. 根据二叉树的定义，具有三个结点的二叉树有 种不同的形态，它们分别是 。 6. 具有n个结点的完全二叉树的深度为 。
8. 以数据集{4，5，6，7，10，12，18}为结点权值所构造的哈夫曼树为 ，其带权路径长度为 。
9. 哈夫曼树是带权路径长度 的树，通常权值较大的结点离根 。 10. 在 遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
第7章 图
1．n个顶点的连通图至少有 n(n-1)/2 条边。
2．在无权图G的邻接矩阵A中，若（vi，vj）或〈vi，vj〉属于图G的边集，则对应元素A[i][j]等于 ，否则等于 。
3. 在无向图G的邻接矩阵A中，若A[i][j]等于1，A[j] [i]等于 。
4. 已知图G的邻接表如下图所示，其从顶点v1出发的深度优先搜索序列为 ，其从顶点v1出发的广度优先搜索序列为 。
V1
v2
v3
v4 ^
v5
v6 ^
V2 v3 V6 ^ V5 V5 ^ V4 ^ V4 V6 V3 ^ 5. 设x，y是图G中的两顶点，则（x，y）与（y，x）被认为 ，但〈x，y〉与〈y，x〉是 的两条弧。
6. 已知一个图的邻接矩阵表示，删除所有从i个结点出发的边的方法是 。
7. 在有向图的邻接矩阵上，由第i行可得到第 个结点的出度，而由第j列可得到第 个结点的入度。
8. 在无向图中，如果从顶点v到顶点v′有路径，则称v和v′ 是 。
第8章 查找
1. 顺序查找法的平均查找长度为 O(n) ；哈希表查找法采用链接法处理冲突时的平均查找
5
长度为 。
2. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。 3. 二分查找的存储结构仅限于 。
4. 长度为255的表，采用分块查找法，每块的最佳长度是 17 。
5. N个记录的有序顺序表中进行折半查找，最大的比较次数是 。
6. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为 ；若采用二分法查找，则时间复杂度为 ；若采用分块查找（假定总块数和每块长度均接近n），则时间复杂度为 。 7. 在散列存储中，装填因子a的值越大，则 ；a的值越小，则 。 8. 对于二叉排序树的查找，若根结点元素的键值大于被查元素的键值，则应该在二叉树的 上继续查找。
9. 高度为8的平衡二叉树至少有 个结点。 10. 在散列函数H（key）=key % p中，p应取 。
第9章 排序
1. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第8个记录45插入到有序表时，为寻找插入位置需比较 5 次。
2. 对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为 100 的关键字开始。
3. 对n个记录的表r[1…n]进行简单选择排序，所需要进行的关键字间的比较次数为 n(n-1)/2 。 4. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有 选择排序，快速排序，堆排序 。
5. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是 ，需要内存容量最多的是 归并排序 。
6. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用 堆排序 ，若原始记录无序，则最好选用 快速排序 。
7. 在插入排序和选择排序中，若初始数据基本正序，则选用 插入排序 ；若初始数据基本反序，则选用 选择排序 。
8. 对n个元素的序列进行冒泡排序时，最少的比较次数是 n(n-1)/2 。 9. 排序不需要进行记录关键字间的比较。
6
因篇幅问题不能全部显示，请点此查看更多更全内容