数据结构严蔚敏清华大学出版社习题及答案

1、第1章 绪论 31、填空题 32、应用题 3第2章 线性表 41、填空题 42、选择题 53、判断题 54 、程序设计题 5第3 章 栈和队列 81、填空题 82、选择题 83 、判断题 9第4 章 串 91、选择题 92 、判断题 9第5 章 数组和广义表 91、填空题 92、选择题 93、判断题 10第6 章 树和二叉树 101、填空题 102、选择题 113、判断题 114、应用题 115、读程序写结果 18第7 章 图 191、填空题 192、选择题 193、判断题 204、应用题 205 、程序设计题 25第8 章 动态存储管理 251、填空题 252、选择题 253、判断题 254

2、、应用题 255 、程序设计题 25第9章 查找 261、选择题 262、判断题 273、应用题 274 、程序设计题 28第 10 章内部排序 291、填空题 292、选择题 303、判断题 304、应用题 30第 11 章外部排序 31第 12 章文件 31第 1 章 绪论 1 、填空题1. 常见的数据结构有 _线性_结构， _树形_结构， _图形_结构等三种。2. 常见的存储结构有 _顺序存储 结构， _链式存储 结构等两种。3. 数据的基本单位是 _数据元素 _，它在计算机中是作为一个整体来处理的。4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，_线性结构和 _非线性

3、结构 _。2、应用题1、给出以下算法的时间复杂度 .void fun(int n)int i=1,k=100;while(i<n)k=k+1;i=i+2;时间复杂度为 O (n )。2、给出以下算法的时间复杂度 .void fun2(int n)int i=1,k=100;while(i<n)i=i*10;k=k+1;时间复杂度为 O( log n ) 。第2 章 线性表1、填空题1. 线性表按照存储结构不同主要有两种实现方式，一种是_顺序 _表，另一种是 _链_表2. 顺序表采用 _随机 _访问机制 对数据元素进行访问。3. 若在单链表结点p的后面插入一个新的结点s,则其操作序列

4、为： s->next=p->next ； p->n ext=s；4. 在单向链表中，若要删除某个结点p, 般要找到_p的前趋_结点，才能实现该操作。2、选择题1. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是_A(A) n(B)2n -1(C)2n(D)n-12. 在单链表中，如果在结点p之后插入一个新结点s，其操作为_ A _。(A) s->next=p->next; p->next=s;(B) p->next=s; s->next=p->next;(C) s->next=p; p->next=s->n

5、ext;(D) p->next=s; s->next=p;3. 若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为 ( C )。(1 总勺)A. 0(0)B . 0(1)C.O(n)D . O(n 2)4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为( b )。(1 m 旬+1)A. n-i B. n-i+1C. iD. n-i-13、判断题1. 线性表中每一个元素都有一个前驱和一个后继。(x )4、程序设计题1、单链表的结点结构定义如下：struct LinkNodeLinkNode *next;int

6、 data;请根据述函数的功能写程序。void Insert（LinkNode *h,LinkNode *s）/h 指向链表的头结点（即使链表中没有元素，头结点也存在。 ） /链表中元素已经递增有序/函数功能为将结点 s 插入到链表 h 中。插入后链表仍然保持递增的顺序 LinkNode *p,*q;/q 指向 p 的前驱q=h; p=h->next; while（p） if（p->data>s->data）/ 寻找到插入点位置，插入 s q->next=s; s->next=p;return;elseq=p; （1 分 ） p=p->next; （1

7、 分 ） /当表中没有比 s 大的结点时，插入到表尾 s->next=q->next; （2 分 ） q->next=s; （2 分 ）2、设顺序表 L 是一个递增有序表，试写一算法，将 x 插入 L 中，并使 L 仍是一个有序表。顺序表的 结构定义如下：#define ListSize 100/ 假定表空间大小为 100struct SqList int elemListSize;/ 数组 elem 用于存放表中的数据int length;/ 当前的表长度;/以上为顺序表的结构/函数头定义如下void InsertIncreaseList( SqList &L ,i

8、nt x ) int i;if ( L.length>=ListSize)cout<< ”OVERFLOW ”; /判断是否溢出for ( i=L.length ; i>0 && L.elem i-1 > x ; i-)L.elem i =L.elem i-1 ; / 比较并移动元素L.elem i =x; / 插入 xL.length+;/ 表长增 1/3、单链表中结点的结构如下所示：typedef struct node int data;struct node *next;node;请设计满足下述功能的函数。要求： 建立带头结点的单链表 H

9、，要求函数从屏幕上读入 m 个整数，每读入一个，便生成相应的结点，并且把它插入到链表 H 的尾部。函数形式为 void CreateLinkList(node *H) 。参考程序：void CreateList(node *H)/H 指向头指针int m,temp;cout<<" 输入数据的个数： "cin>>m;/int i=1;node *tail;H->next=NULL;tail=H;while(i<=m)cout«"please input your number:"«endl; cin&

10、gt;>temp;node *t=new node ;t->data=temp;t->next=tail->next;tail->next=t;tail=t;i+;第3章栈和队列1、填空题1. 栈和队列在本质上都是 线性表。2. 栈的操作特点是 _后进先岀_。队列的操作特点是先进先岀2、选择题1. 消除递归不一定需要使用栈，此说法A。A.正确B.错误2. 对于栈，输入序列为(1, 2, 3, 4),不可能得到的输岀序列有 _D(A) ( 1 , 2, 3, 4) (B) (4, 3, 2, 1)(C) (1 , 3, 4, 2) (D) (3, 1 , 2 , 4

11、)3. 用单循环链表表示队列,正确的说法是_B_。(A) 可设一个头指针使入队、出队都方便；(B) 可设一个尾指针使入队、出队都方便；(C) 必须设头尾指针才能使入队、出队都方便；(D) 无论如何，只可能使入队方便。3、判断题1. 栈的特点是先进先岀。(x )2. 可以在队列的任意位置插入元素。(X)3. 递归程序化非递归程序必须用到栈。(X )4. 如果进栈的序列为(1 ,2,3,4),则(4,2 ,3,1)不可能是出栈序列。()5. 在用顺序表表示的循环队列中，可用标志位来区分队空或队满的条件。(V)第4章串1、选择题1. 设有两个串p和q，求q在p中首次出现的位置的运算称作(B )A.连

12、接B 模式匹配C 求子串D 求串长2、判断题1. 空串和空格串是同一个概念，二者没有区别。(x )第5章数组和广义表1、填空题1. 二维数组在内存中存储可以有两种存储方式，一种是 行优先存储,一种是列优先存储。2. 设广义表 L =(),(),()。则 head(L)是 () ;tail(L)是 (),();L的长度是 3; L的深度是 3。3. 设广义表 L = ( (a), ( b), ( c) )_则 head(L)是 _ ( a) _;tail(L)是(b), (c) )_o2、选择题1.在C语言中，如果有数组定义int A89;假定每个整型数据占2字节，则数组元素A44的地址是( A

13、 )。A. A+80 B. A+76 C.A+82 D. 以上都不对2. 广义表 A=( a,b,(c,d),(e,(f,g) ),则下面式子的值为 ( D)；Head(Tail(Head(Tail(Tail(A)A( g )B.(d) C.c D.d3、判断题1. 在C语言中，多维数组的存储采取的是行优先的方式。(V)2. 广义表在本质上也是线性表。(X )3. 可以用三元组存储法来压缩存储稀疏矩阵。 ( V)4. 已 知 广 义 表 A=(a,b,c),(d,e,f), 从 A 中 取 出 原 子 e 的 运 算 是 ( V )第6 章 树和二叉树1 、填空题1.一棵 62个叶结点的完全二

14、叉树 ,最多有_62*2=124 个结点。2. 若规定仅有根的二叉树的高度为1，那么高为 h 的完全二叉树最多有点，最少有_"(h-1)个结点。3. 设 只 包 含 有 根 结 点 的 二 叉 树 的 高 度 为 0 ， 则 高 度 为 k 的 二2人代+1)-1 ，最小结点数为k+1。head(tail(head(tail(A)2Ah-1个结叉树的最大结点数为- 叉树的最大结点数为-4. 设 仅 包 含 根 结 点 的 二 叉 树 的 高 度 为 1 ， 则 高 度 为 k 的 二2Ak-1，最小结点数为k2、选择题1具有N个结点的完全二叉树的深度是 _B(A)? log2N ?(

15、B) ? log2N ?+1(C) ? log2(N) ?(D) ? log2N ?-12.设二叉树的树根为第一层，则第i层上至多有_C_ 结点(A)1(B)2(C)2 i-1(D)2i-13、判断题1. 二叉树的左右子树次序是严格的，不能够任意改变。（V）2.若根为第一层，则深度为 k的满二叉树的结点为 2Ak-1 。3. 二叉树的三叉链表存储结构可以方便的访问到双亲结点。（V）4、应用题1.在一段文字中，共出现 a、b、c、d、e、f六种字符，每种字符出现的频率分别为 请回答下列问题：（1）什么是哈夫曼树？ （3分）（2） 根据题目所给频率值，画出相应的哈夫曼树。（11分）（3） 给岀各个

16、字符对应的哈夫曼编码。（6分）（4） 该段文字经过哈夫曼编码后，长度是多少。（4分）参考答案如下：（1） 答案为：带权路径长度最小的二叉树称为哈夫曼树。（3分）（2） 根据题目所给频率值，画岀相应的哈夫曼树。（11分，每个结点1分）7,9,12,22,23,2716ab(3) 给岀各个字符对应的哈夫曼编码。(6分)a:1110b:1111c:110d:00e:01f:10(4) 该段文字经过哈夫曼编码后，长度是多少。(4分)(7+9)*4+12*3+(22+23+27)*2=244或者 100+45+55+28+16=2442.设一棵二叉树的先序遍历序列为abcde，中序遍历序列为 badce

17、，请画出对应的二叉树，并写出对应后序遍历序列。(15分)参考答案如下:(1)画出二叉树(10分)错一个结点扣2分（2）后序遍历序列为：bdeca（5 分）3.通信报文中出现的字符 A、B、C、D、E ,在报文中出现的频率分别为0.23、0.2、0.32、0.12、0.13，分别给岀相应字符的哈夫曼编码（要求画岀哈夫曼树，并且把权值小的结点放在左边）。（共14分）参考答案如下：为处理方便，关键字都乘以100，为23 , 20 , 32 , 12 , 13构造哈夫曼树为：（9分，每个结点1分）4.100014357010132232520CAB011312DE所以编码为：A : 01 B : 00

18、 C : 11 D : 100 E : 101（5分，每个编码1分）某二叉树结点的中序序列为H，B，C，D，E，F，G，后序序列为 B，D，C，H，F，G，E，请据此画岀该二叉树，再给该树加上中序线索。（共15分）对应的二叉树为：（7分，每个结点1分）EGHCDB分）18(105. 请证明对于任何一棵二叉树，如果其终端结点数为nO，度为2的结点数为n2，则n0=n2+1证明：令树中结点总数为 N，度为1的结点个数为ni 则树中结点数满足下列公式：no+ni+n2=N从度的角度来考虑，满足下列公式：2n2+ni+仁N从而得证：n0=n2+l6. 请按照孩子-兄弟表示法，将图1所示树转化为二叉树。

19、（共14分）20解:ACBDEFGABCDEFG（每个结点2分）7.设二叉树如图2所示。分别写岀它的先序遍历、中序遍历、后序遍历序列。（共15分）8.（1 ）写出如图所示二叉树的中序遍历结果。（8分）（2）画出二叉树的中序后继线索。（10分）（1 ）中序遍历结果：ADBCHFEG共8分，每个字符1分（2）二叉树的中序后继线索如图共10分，每个后继线索 2分9.已知某二叉树的前序遍历序列为：ABC D E FG 和中序遍历序列为：C B E DAFG。请画出该二叉树。答案如下：10.已知通信联络中只可能出现 A、B、C、D、E、F、G、H共8种字符，其出现次数分别为 5 ,28，7, 9，14，

20、23，3，11 次。（1 ）请画岀赫夫曼树（权值小的结点在左边）。（15分）（2）计算该树的带权路径长度。（3分）答案：（1 ）赫夫曼树构造如下。树中结点位置正确者，每个1分，共15分。25(2 )该树的带权路径长度为(5+3+7+8 ) *4+ (11+14 ) *3+ (23+29 ) *2=2713分5、读程序写结果已知二叉树的结点结构如下:struct Nodeint data;Node *lchild,*rchild;某棵二叉树的形态如右图：根据要求解答下题：1、(共5分)int fun1(Node *root)if(root=0) return 0; int l,r;I=fun1(

21、root->lchild); r=fun1(root->rchild); if(l>=r) return l+1;else return r+1;(1 )当root是指向结点A的指针时，函数funl的返回值是多少? 函数funl的返回值是3。(2)函数funl的功能是什么？ (3分)函数funl的功能是求二叉树的高度。2、洪6分)int fun2(Node *root)if(root=0) return 0;int I=fun2(root->lchild );int r=fun2(root->rchild );return 1+叶1;(1 )当root是指向结点A

22、的指针时，函数fun1的返回值是多少? 函数fun1的返回值是5。(2)函数fun1的功能是什么？ (4分)函数fun1的功能是求二叉树中所有结点的个数（2分）（2分）1、填空题1. 有n个顶点的有向连通图最多有 条边，最少有 条边2. 具有n个顶点的完全无向图有 条边，完全有向图有 条边2、选择题1.方法可以判断出一个有向图中是否有环(回路)(A)深度优先遍历(B)拓扑排序(C)求最短路径(D)求关键路径2. 关键路径是指。(A) 从开始事件到终止事件路径长度最短的路径(B) 从开始事件到终止事件路径长度最长的路径(C) 从开始事件到终止事件活动最少的路径(D) 从开始事件到终止事件活动最多

23、的路径5. 方法可以判断出一个有向图中是否有环(回路)。(A)深度优先遍历(B)拓扑排序(C)求最短路径(D)求关键路径3、判断题1. 具有n个顶点的有向图最多有 n*(n-1)条边。()2. 在AOV-网中，不应该出现有向环，因为存在环就意味着活动可以以自己为先决条件4、应用题1、已知某图的存储结构如下，试写岀该图从顶点A开始的深度优先遍历序列。(11 分)011111000000000001000000000001000KABABCDEFGHI JC26000000001000000000001000000000001010000000000010000000000010000000000

24、0100000000000100000DEFGHIJK答案为：ABGCHDIEJFK （对一个1分）2请给出图1的所有最小生成树。（10分）共两棵。第一棵为：（5分）错一条边扣1分36第二棵为：（5分）错一条边扣1分3请给岀图2的所有拓扑排序序列。（16）dbehacg答案如下：仅有两个第一个：abcdefgh（错一个字符扣1分）第二个：abcdegfh（错一个字符扣1分）4、对于有向无环图（如图 2）,写出它的所有不同的拓扑有序序列。（共16分）序列为：1、3、2、4、5、6、7、86. 已知某图采取如图2所示的邻接矩阵表示法，请回答下列问题。（共12 分）01234560110001001

25、10100011010000011000001000123456123456图2（1）请画出该图。（6分）（2） 对其从顶点 A开始进行深度优先遍历，写岀遍历序列。（6分）（1） 请画出该图。（6分）错一个结点扣1分。CBDEF（6分，错一个字符扣1分）（2）对其从顶点 A开始进行深度优先遍历，写岀遍历序列序列为：ABDECF7、（本题总计7分）构造该图的最小生成树图的最小生成树如下2beg1da314c每条边1分，共7分5、程序设计题第8章动态存储管理1、填空题2、选择题3、判断题4、应用题5、程序设计题第9 章 查找1、选择题1. 若在线性表中采用二分查找法查找元素，该线性表应该( C)。A.元素按值有序B.采用顺序存储结构C 元素按值有序，且采用顺序存储结构D 元素按值有