下载文档原格式
数据结构填空题题库一、填空题1题目：在数据结构中，_______是一种线性结构，它按照_______的方式存储数据。
答案：数组，连续解析：数组是一种线性结构，它在内存中按照连续的方式存储数据。
二、填空题2题目：在二叉树中，每个节点最多有_______个子节点。
答案：2解析：二叉树中，每个节点最多有两个子节点，分别称为左子节点和右子节点。
三、填空题3题目：栈是一种_______结构，它遵循_______的原则。
答案：线性，后进先出解析：栈是一种线性结构，它遵循后进先出（LIFO）的原则，即最后进入栈的元素最先被访问。
四、填空题4题目：在图的表示中，邻接矩阵使用一个_______来表示图中的边。
答案：矩阵解析：邻接矩阵使用一个矩阵来表示图中的边，矩阵的行和列分别表示图中的顶点，矩阵中的元素表示两个顶点之间是否存在边。
五、填空题5题目：在哈希表中，通过_______函数将关键字映射到哈希表的_______。
答案：哈希，索引解析：哈希表通过哈希函数将关键字映射到哈希表的索引，从而实现高效的查找和插入操作。
六、填空题6题目：在堆排序中，堆是一种_______树，它分为_______堆和_______堆。
答案：完全，最大，最小解析：堆是一种完全二叉树，它分为最大堆和最小堆。
最大堆中，每个节点的值都大于或等于其子节点的值；最小堆中，每个节点的值都小于或等于其子节点的值。
七、填空题7题目：在链表中，每个节点包含两部分，分别是_______和_______。
答案：数据，指针解析：链表中的每个节点包含两部分，一部分是存储数据的区域，另一部分是指向下一个节点的指针。
八、填空题8题目：在树的遍历中，前序遍历的顺序是_______，中序遍历的顺序是_______，后序遍历的顺序是_______。
答案：根-左-右，左-根-右，左-右-根解析：前序遍历先访问根节点，然后按照左子树-右子树的顺序进行遍历；中序遍历先访问左子树，然后访问根节点，最后访问右子树；后序遍历先访问左子树，然后访问右子树，最后访问根节点。
《数据结构》填空作业题答案第 1 章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。
2．程序包括两个内容：数据结构和算法。
3.数据结构的形式定义为：数据结构是一个二元组：Data Structure =（ D， S）。
4.数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。
5.数据的逻辑结构可以分类为线性结构和非线性结构两大类。
6.在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。
7.在树形结构中，数据元素之间存在一对多的关系。
8.数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。
9.数据的逻辑结构包括线性结构、树形结构和图形结构 3 种类型，树型结构和有向图结构合称为非线性结构。
10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。
11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。
12.数据的存储结构可用 4 种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。
13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。
14.数据结构在物理上可分为顺序存储结构和链式存储结构。
15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。
16.数据元素可由若干个数据项组成。
17.算法分析的两个主要方面是时间复杂度和空间复杂度。
18.一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。
19.算法具有如下特点：有穷性、确定性、可行性、输入、输出。
20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。
第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。
1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。
1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。
A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。
1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。
1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。
A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。
A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。
A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。
head第3章 栈和队列 自测卷答案 姓名 班级一、填空题（每空1分，共15分）1. 【李春葆】向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。
2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。
不允许插入和删除运算的一端称为 栈底 。
3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。
(注：不一定，这是一种约定，在殷教材中是队首指针指向队列的首元素位置)5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。
6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。
7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。
(注：不一定，这是一种约定，在殷教材中是先 取出元素 ，后移动队首指针 )8. 〖00年统考题〗带表头结点的空循环双向链表的长度等于 0 。
解：二、判断正误（判断下列概念的正确性，并作出简要的说明。
）（每小题1分，共10分） （ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。
（ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。
错，不一定吧调用子程序或函数常用，CPU 中也用队列。
（ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（√）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。
（×）5. 栈和链表是两种不同的数据结构。
错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。
参考答案第一章、绪论一、选择题1 B；2 A； 3 B；4 C ；5 C； 6 B；7 C；8 C；9 D；10 B。
二、填空题1、存储；2、无，1，无，1；3、前驱，1，后继，任意多个；4、一对一，一对多，多对多；5、时间复杂度，空间复杂度；6、集合，线性结构，树形结构，图形结构；7、顺序结构，链式结构，索引结构，散列结构；8、顺序。
三、问答题与算法题1、3 ；2、T1 ( n ) = 5n 2 -O ( n ) ; T2 ( n ) = 3 n 2 + O ( n ) ; T3 ( n ) = 8 n 2 + O(log n) ;T4 ( n ) = 1.5 n 2 + O ( n ) 。
T4 ( n ) 较优，T3 ( n )较劣。
3、见课本。
第二章线性表一、选择题1C；2A；3D；4B；5D；6B；7C；8B；9A；10C；11D；12D；13C；14C.二、填空题1、O ( 1 ), O ( n )；2、单链表，双链表；3、地址，指针；4、4，2；5、便于访问尾结点和头结点；6、前驱；7、L->next== L且L->prior== L；8、顺序。
三、问答题与算法题1、头指针：结点或头结点的指针变量。
其作用是存放第一个结点或头结点的地址，从头指针出发可以找到链表中所有结点的信息。
头结点：是附加在链表的第一个结点之前的一个特殊结点，其数据域一般不存放信息。
其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。
首结点：是链表的第一个结点。
2、(1)基于空间的考虑。
当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
(2)基于时间的考虑。
若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。
第九章 查找 一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。
因为这是在假设n ＝2m -1的情况下推导出来的公式。
应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。
如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。
(而任一元素查找次数 ≤n-1)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法 10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。
数据结构题库及答案详解一、选择题1. 在数据结构中，线性结构的特点是什么？A. 结构中存在唯一的开始结点和终端结点B. 结构中所有结点的前驱和后继都存在C. 结构中所有结点都只有一个直接前驱和一个直接后继D. 结构中存在多个开始结点和终端结点答案：C2. 栈是一种特殊的线性表，其特点是：A. 先进先出B. 先进后出C. 可以同时在两端进行插入和删除操作D. 只能在一端进行插入和删除操作答案：D3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根结点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根结点，最后遍历右子树C. 先遍历右子树，然后访问根结点，最后遍历左子树D. 先遍历左右子树，最后访问根结点答案：A二、填空题4. 在图的遍历中，______算法可以避免重复访问同一顶点。
5. 哈希表的冲突可以通过______方法来解决。
答案：4. 深度优先搜索（DFS）5. 链地址法或开放地址法三、简答题6. 简述排序算法中的快速排序算法的基本原理。
答案：快速排序算法是一种分治算法，它通过选择一个元素作为“基准”，然后将数组分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素。
然后对这两个子数组递归地应用快速排序算法。
7. 解释什么是递归，并给出一个递归函数的例子。
答案：递归是一种在函数中调用自身的编程技术。
递归函数必须有一个明确的终止条件，以避免无限递归。
例如，计算阶乘的递归函数如下：```int factorial(int n) {if (n == 0) return 1; // 终止条件return n * factorial(n - 1); // 递归调用}```四、编程题8. 编写一个函数，实现单链表的反转。
答案：```c// 假设ListNode是链表节点的定义ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;ListNode* curr = head;ListNode* next = NULL;while (curr != NULL) {next = curr->next; // 保存下一个节点curr->next = prev; // 反转指针prev = curr; // 移动prevcurr = next; // 移动curr}return prev; // 新的头节点}```9. 给定一个整数数组，请实现一个函数来找到数组中的最长连续子序列的长度。
《数据结构》填空作业题答案第1章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。
2．程序包括两个内容：数据结构和算法。
3. 数据结构的形式定义为：数据结构是一个二元组：Data Structure =（D，S）。
4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。
5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。
6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。
7. 在树形结构中，数据元素之间存在一对多的关系。
8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。
9. 数据的逻辑结构包括线性结构、树形结构和图形结构3种类型，树型结构和有向图结构合称为非线性结构。
10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。
11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。
12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。
13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。
14. 数据结构在物理上可分为顺序存储结构和链式存储结构。
15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。
16. 数据元素可由若干个数据项组成。
17. 算法分析的两个主要方面是时间复杂度和空间复杂度。
18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。
19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。
20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。
数据结构练习题第一部分绪论一、单选题1. 一个数组元素a[i]与________的表示等价。
A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。
A、参数类型B、参数个数C、函数类型3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值4. 下面程序段的时间复杂度为____________。
for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)5. 执行下面程序段时，执行S语句的次数为____________。
for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/26. 下面算法的时间复杂度为____________。
int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1. 数据的逻辑结构被分为__________、_________、__________和__________四种。
2. 数据的存储结构被分为__________、_________、__________和__________四种。
3. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。
4. 一种抽象数据类型包括__________和__________两个部分。
5. 当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。
数据结构考试题及答案一、选择题1. 下列哪种数据结构是一种线性结构？A. 树B. 栈C. 图D. 队列答案：B. 栈2. 以下哪种不是二叉树的遍历方式？A. 先序遍历B. 层序遍历C. 后序遍历D. 中序遍历答案：B. 层序遍历3. 在队列中，哪种操作不是O(1)时间复杂度的？A. 入队B. 出队C. 判空D. 获取队首元素答案：D. 获取队首元素二、填空题4. 二叉查找树的中序遍历结果为_______。
答案：升序排列的序列5. 栈的特点是_______进，_______出。
答案：后进，先出6. 图中两点间存在边则称它们为_______。
答案：邻接点三、简答题7. 请简要介绍一下栈和队列的应用场景及区别。
答：栈和队列都是常用的数据结构，栈适合用于实现括号匹配、表达式求值等场景，而队列常用于实现广度优先搜索、缓存队列等。
栈是一种后进先出的数据结构，而队列是一种先进先出的数据结构。
8. 什么是哈希表？它的优缺点分别是什么？答：哈希表是一种通过哈希函数将关键字映射到数组位置的数据结构。
其优点是能够快速查找、插入、删除元素，时间复杂度接近O(1)；缺点是可能发生哈希冲突，导致性能下降。
四、综合题9. 给定以下无向图的邻接矩阵表示，请写出图的深度优先搜索（DFS）遍历路径。
```0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0```答：起始节点为0，路径：0 - 1 - 3 - 210. 写出以下树的层序遍历结果。
```1/ \2 3/ \ / \4 5 6 7```答：1 - 2 - 3 - 4 - 5 - 6 - 7以上就是数据结构考试题及答案，希望对您有所帮助。
如果有不清楚的地方，欢迎随时向老师询问。
祝您考试顺利！。
《数据结构》填空作业题答案第1章绪论（已校对无误）1 •数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。
2 •程序包括两个内容：数据结构和算法。
3. 数据结构的形式定义为：数据结构是一个二元组：Data Structure = （D, S）。
4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。
5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。
6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。
7. 在树形结构中，数据元素之间存在一对多的关系。
8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。
9. 数据的逻辑结构包括线性结构、树形结构和图形结构3种类型，树型结构和有向图结构合称为非线性结构。
10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。
11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。
12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。
13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是—对多或多对多。
14. 数据结构在物理上可分为顺序存储结构和链式存储结构。
15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。
16. 数据元素可由若干个数据项组成。
17. 算法分析的两个主要方面是时间复杂度和空间复杂度。
18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。
19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。
20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。
21. 下面程序段的时间复杂度为3L。
i=1 ；while(i<=n)i= i * 3；第2章线性表(已校对无误)1. 一线性表表示如下：(a i, a2,…，a i-i, a , a+1,…，a n),其中每个a i代表一个数据元素(或结点)。
a i称为起始结点,a n称为终端结点,i称为a在线性表中的位置(或序号) 。
对任意一对相邻结点a i, a i+i, (1 <i<n), a称为a i+i的直接前驱，a+i称为a的直接后继。
2. 对一个长度为n的线性表，要删除第i个元素，则在顺序表示的情况下，计算复杂性为0(n),在链式表示的情况下，计算复杂性为0(i)。
3. 在一个长度为n的顺序表中，向第i个元素(K i< n)之前插入一个新元素时，需向后移动n —i + i 个元素。
4. 顺序表中逻辑上相邻的元素在物理位置上一定相连。
5. 在n个结点的顺序表中插入一个结点需平均移动n/2个结点，具体的移动次数取决于__表长n和插入位置i 。
6. 在顺序表中访问任意一个结点的时间复杂度均为0(i),因此，顺序表也称为随机访问的数据结构。
7. 顺序表相对于链表的优点有随机访问和空间利用率高。
8. 在长度为n的顺序表中插入一个元素的时间复杂度为0(n)。
9. 在带有头结点的单链表L中，若要删除第一个结点，则须执行下列三条语句：U = L->next ; L->next=U->next ；free (U )。
10. 链表相对于顺序表的优点有插入和删除操作方便。
11. 在单链表中除首结点外，任意结点的存储位置都由直接前驱结点中的指针指示。
12. 在n个结点的单链表中要删除已知结点*p,需找到它的直接前驱结点的地址，其时间复. 杂度为O(n)。
13. 单链表中设置头结点的作用是简化操作，减少边界条件的判断。
14. 在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的前驱结点。
15. 在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后续结点。
16. 带头结点的单链表L为空的判定条件是L->next==NULL，不带头结点的单链表L为空的判定条件是L==NULL。
17. 在单链表中，指针p所指结点为最后一个结点的条件是p-> next==NULL18. 循环链表的最大优点是从表中任意结点出发都可访问到表中每一个元素（或从表中任意结点出发都可遍历整个链表）。
19. 设rear是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的存储位置是rear->next- >n ext 。
20. 带头结点的双向循环表L为空表的条件是L-> prior== L-> next。
21. 在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道头指针才能遍历整个链表。
22. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 1 。
第3章栈和队列（已校对无误）1. 栈又称为后进先出表，队列又称为先进先出表。
2. 向一个顺序栈插入一个元素时，首先使栈顶指针后移一个位置,然后把待插入元素写入（或插入）到这个位置上。
3. 从一个栈删除元素时，需要前移一位栈顶指针。
4. 在一个顺序栈中，若栈顶指针等于—1 ，则为空栈；若栈顶指针等于maxSize— 1 ，则为满栈。
5. 在一个链式栈中，若栈顶指针等于NULL，则为空栈：在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为空或该队列只含有一个结点。
6. 向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给栈顶指针。
7•在求表达式值的算符优先算法中使用的主要数据结构是栈。
8. 设有一个顺序栈S，元素s1，s2，s3，s4，s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3，s4，s6, s5, s1,则顺序栈的容量至少为 3 。
9. 设有一个空栈，现输入序列为1, 2, 3, 4, 5。
经过push, push, pop, push, pop, push, pop, push后，输出序列是2 3 4。
10. 在按算符优先法求解表达式3-1 + 5*2时，最先执行的运算是丄，最后执行的运算是亠。
11. 在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求栈存在。
12. 仅允许在同一端进行插入和删除的线性表称为栈。
13. 在顺序栈s中，栈为空的条件是s.top==s.base，栈为满的条件是s.top—s.base> =s.stacksize。
14. 设有算术表达式x+ a* （y—b）—c/d,该表达式的前缀表示为一—+ x*a —yb/cd。
后缀表示为xayb —* + cd/—。
15. 用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S、X操作串为SXSSXSXX 。
16. 向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行p->link = top和top = p 操作。
17. 从一个栈顶指针为top的非空链式栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行top = top->li nk 操作。
18. 设有一个空栈，栈顶指针为1000H （十六进制。
现有输入序列为1, 2, 3, 4, 5,经过PUSH, PUSH, POP, PUSH, POP, PUSH, PUSH之后，输出序列是2, 3 ，而栈顶指针是100C H。
设栈为顺序栈，每个元素占4个字节。
19. 在作入栈运算时应先判别栈是否满；在作出栈运算时应先判别栈是否空。
10.用一个大小为1000的数组来实现循环队列，当前rear和front的值分别为0和994,若要达到队满的条件，还需要继续入队的元素个数是993 。
20. 队列的插入操作在队尾进行，删除操作在队头进行。
21. 在一个循环队列Q中，判断队空的条件为Q.front==Q.rear ，判断队满的条件为（Q.rear+ 1）% maxSize==Q.fr ont 。
22. 向一个循环队列中插入元素时，需要首先移动队尾指针，然后再向所指位置写入（或插入）新插入的元素。
23. 当用长度为n的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为top==0 。
24. 循环队列的引入，目的是为了克服假溢出时大量移动数据元素。
第4章串（已校对无误）1. 两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。
2. 空格串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。
3. 模式串’abaabade的next函数值为01122341补充：1. 串的两种最基本的存储方式是顺序存储方式和链接存储方式。
2. 空串是零个字符的串，其长度等于零。
3. 组成串的数据元素只能是字符。
4. 串是一种特殊的线性表，其特殊性表现在其数据元素都是字符—。
第5章数组（已校对无误）1. 将下三角矩阵A[1 .. 8, 1.. 8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则元素A[7, 5]的地址为1100 。
2. 二维数组A[0…9, 0…19]采用列序为主方式存储，每个元素占一个存储单元，并且元素A[0 , 0]的存储地址是200,则元素A[6 , 12]的地址是332 。
3. 二维数组A[10…20, 5-10]采用行序为主方式存储，每个元素占4个存储单元，并且元素A[10, 5]的存储地址是1000,则元素A[18，9]的地址是1208补充：1. 一维数组的逻辑结构是线性结构，存储结构是顺序存储结构。
2. 对于二维数组或多维数组，分为按以行为主序和按以列为主序两种不同的存储方式存储。
3. 对矩阵压缩存储是为了节省存储空间。
4. 二维数组是一种非线性结构，其中的每一个数组元素最多有二个直接前驱（或直接后继）。
第6章树（已校对无误）4. 结点最少的树为只有一个结点的树，结点最少的二叉树为空的二叉树。
5. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，它们分别是________ 。
6. 具有n个结点的完全二叉树的深度为____ 。
8. 以数据集｛4，5, 6, 7, 10, 12，18｝为结点权值所构造的哈夫曼树为需用图示，其带权路径长度为165 。
9. 哈夫曼树是带权路径长度最短的树，通常权值较大的结点离根较近。
10. 在先序遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
第7章图（已校对无误）1. n个顶点的连通图至少有n—1条边。
2•在无权图G的邻接矩阵A中，若（vi, vj）或〈vi, vj〉属于图G的边集，则对应元素A[i][j]等于L,否则等于0 。
