发布时间 : 星期六 文章数据结构与算法复习题及参考答案更新完毕开始阅读
2016《数据结构域算法》复习题
A.(18,22,30,46,51,68,75,83) C.(46,30,22,18,51,75,68,83)
B.(30,18,22,46,51,75,83,68) D.(30,22,18,46,51,75,68,83)
二、填空题
1．数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。 2．下面程序段的时间复杂度是 O(log3n) 。
i ＝ 1；
while（i<=n） i = i * 3；
3．在顺序表中插入或删除一个元素，需要平均移动 表中一半 元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。
4．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用 顺序 存储结构。
5．在n个结点的单链表中要删除已知结点*p，需找到它的 前驱结点 的地址，其时间复杂度为O（n）。 6．已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列。
删除P结点的直接后继结点的语句序列是 (11)(4)(14) 。 删除P结点的语句序列是 (10)(12)(7)(4)(14) 。
(1) P = P->next ; (2) P->next = P; (3) P->next = P->next->next (4) P->next = P->next->next; (5) while(P!=NULL) P = P->next ; (6) while(Q->next != NULL) {P = Q; Q=Q->next;} (7) while(P->next != Q) P = P->next;
(8) while(P->next->next != Q) P = P->next; (9) while(P->next->next != NULL) P = P->next;
(10) Q = P; (11) Q = P->next; (12) P = L ; (13) L = L->next; (14) free(Q); 7．栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。
8．设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈，得到的出栈序列是b、d、c、f、e、a，则栈S的容量至少是 3 。
9．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为 SXSSXSXX 。 10．数据的逻辑结构可以分为 线性 和 非线性 两大类。 11．数据的运算用 算法 表示。
12．逻辑上相邻的结点在存储器中也相邻，这是 顺序 存储结构的特点。 13．在长度为n的顺序表上实现定位操作，其算法的时间复杂度为 O(n) 。 14．为了实现随机访问，线性结构应该采用 顺序 存储。 15．在长度为n的顺序表中插入一个元素，最多要移动 n 个元素。 16．栈的存储结构主要有 顺序 和 链式 两种。
17．在编写程序的时候，如果栈的最大长度难以预先估计，则最好使用 链式 栈。
18．在树形结构中，如果某结点 没有前驱（双亲） ，则称该结点为根结点；如果某结点 没有后继（孩子） ，
5
2016《数据结构域算法》复习题
则称该结点为叶子。
19．在树形结构中，每个结点最多只有一个前驱（双亲）。 20． 由3个结点所构成的二叉树有 5 种形态。
21．二叉树的前序遍历按如下三个步骤进行： ①访问根结点 ； ②前序遍历左子树 ； ③前序遍历右子树 。【注意：②③中一定要加“前序”两字！】
22．二叉树的中序遍历按如下三个步骤进行：①中序遍历左子树 ； ②访问根结点 ；③中序遍历左子树 。【注意：①③中一定要加“中序”两字！】
23．在n个顶点的无向图中，至少有 0 条边，至多有 n(n-1)/2 条边。 24．在n个顶点的有向图中，至少有 0 条边，至多有 n(n-1) 条边。 25．如果排序不改变关键字相同的记录之间的相对次序，则称该排序方法是稳定的。 26．如果排序改变了关键字相同的记录之间的相对次序，则称该排序方法是不稳定的。
27．当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是 直接插入排序 。
28．在一个图中，所有顶点的度数之和是所有边数的 2 倍。 29．无向图中边的数目等于邻接矩阵中非零元素个数的 0.5 倍。
30．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
31．在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第二次被比较的元素
是 4 。
32．在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第三次被比较的元素
是 6 。
三、简答题
1．对链表设置头结点的作用是什么？（至少说出两条好处） 答：其好处有：（1）对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一个结点的指针域，因为任何元素结点都有前驱结点（若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点和删除该结点时操作复杂些）。
（2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
2.写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。 void main( ){
Queue Q; Init Queue (Q); Char x=’e’; y=’c’;
EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’);
while(!QueueEmpty(Q)){ DeQueue (Q,y); printf(y); }; Printf(x); }
解：char
6
2016《数据结构域算法》复习题
3. 简述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q){
Stack S; int d; InitStack(S);
while(!QueueEmpty(Q)){
DeQueue (Q,d); Push(S,d); };
while(!StackEmpty(S)){
Pop(S,d); EnQueue (Q,d); } }
解：
利用栈S作为缓存空间，将队列Q中的元素进行逆置（即相对于原顺序进行倒排）。
4. 描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？
答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。
头结点 ? head data link 头指针 首元结点
简而言之，
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）
首元素结点是指链表中存储线性表中第一个数据元素a1的结点。
5. 对以下单链表执行下列语句，简述代码的功能，并画出单链表结果示意图。 L 2 5 7 3 8 ^ T = L; while(T->next != NULL) {
T->data = 2 * T->data; T = T->next; } 解：
代码功能：除最后一个结点之外，每个结点的数值部分改变为原值的2倍。 单链表结果示意图如下： L 4 14 8 ^ 10 6 6. 请画出下图的邻接矩阵和邻接表 【本题较简单，不提供答案】
7
2016《数据结构域算法》复习题
7．假设二叉树采用顺序存储结构，如图所示。 （1） 画出二叉树表示；
（2） 写出先序遍历、中序遍历和后序遍历的结果； （3） 写出结点值c 的双亲结点，其左、右孩子；
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f d g c j h i b
8. 树和二叉树之间有什么样的区别与联系？ 解： 联系：（1）二叉树是树的一种，是一种特殊的树；（2）对树适用的操作或规律都可应用到二叉树上。 区别：（1）二叉树是一种特殊的树，特殊在，第一是有序树，第二结点的度数不超过2；（2）普通二叉树有3个性质，完全二叉树有5个性质，普通树是没有这些性质的。
9. 一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。 证明：
设总结点数为n，度数为2的结点数为n2，依题意，该二叉树没有度数为1的结点。 那么n= n0+ n2
假定分枝数为B，每个结点通过一个分枝跟其双亲相连，除根结点外；这意味着除根结点外，每个结点对应一个分枝，即B=n-1 ,根据二叉树的性质3，n2=n0+1 , 于是B==n-1= n0+ n2-1= n0+ n0-1-1=2(n0-1)
10. 一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：
（1）各层的结点的数目是多少？
（2）编号为n的结点的双亲结点（若存在）的编号是多少？
（3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？
（4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 请给出计算和推导过程。
11. 如果用一个循环数组q[0..m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。
（1）编写实现队列的三个基本运算：判空、入队、出队 （2）队列中能容纳元素的最多个数是多少？ 【此题超出教学范围，不作解答。】
12. 已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，画出此二叉树。并给出其后序遍历的结果。
A
解：根据已知的前序和中序遍历结果，建立二叉树如图所示。 此二叉树的后序遍历结果为：CBEFDA D B 13．假设以二叉链表表示二叉树，其类型定义如下：
8
C
E F