数据结构复习题答案

1、1 / 15 、选择题 1. 栈和队列的共同特点是 ( ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接斱式存储的队列，在进行插入运算时 A. 仅修改头指针 B. C. 仅修改尾指针 D. 3. 以下数据结构中哪一个是非线性结构？ A. 队列 B. 栈 4. 设有一个二维数组 A m n ，假设 每个元素占一个空间，问 A 688 C. A00 A33 (10) 存放在( B 678 C 5. 树最适合用来表示 ( ) ( ). 头、尾指针都要修改 头、尾指针可能都要修改 ) 线性表 D. 二叉树 存放位置在 644(10) ，

2、A22 存放位置在 676(10) ， )位置，脚注 (10) 表示用 10 进制表示。 692 D 696 A. 有序数据元素 B. C. 元素之间具有分支层次关系的数据 6. 二叉树的第 k 层的结点数最多为 ( ). k A 2k-1 B.2K+1 C.2K-1 7. 若有 18 个元素的有序表存放在一维数组 A19 中，第一个元素放 A1 中，现进行二分查找， 则查找 A : 3的比较序列的下标依次为 () A. 1 ，2，3 B. 9 ， C. 9 ，5，3 D. 9 ， 8. 对 n 个记彔的文件进行快速排序，所需要的辅助存储空间大致为 B. O (n) 55，25，64，46，

3、1 的元素有( 2 C A. O ( 1) 9. 对于线性表( 7，34， 散列函数，则散列地址为 A 1 B 10. 设有 6 个结点的无向图，该图至少应有 A.5 B.6 C.7 D.8 D. C. O 20，10) )个， 3 ( ) 11. 一个链队列中， f， r 分别为队首、队尾指针， A) f-next=c ；f=s C) s-next=r ；r=s 12. 下列说法正确的是( )。 A)二叉树中每个结点的度都为 C) 一棵二叉树的度可小于 2 无序数据元素 间无联系的数据 元素之 k-1 D. 2 k-1 5，2， 4，2， ( D. O 进行散列存储时，若选用 1og2n)

4、n2) H(K) =K %9 作为 D 4 条边才能确保是一个连通图。 则插入 r-next=s s-next=f s 所指结点的操作为 二叉树的度为 r=s ； f=s ； 二叉树中至少有一个结点的度 13. 一棵非空二叉树先序遍历不后序遍历序列正好相反，则该二叉树( )。 A)所有的结点均无左孩子 )所有的结点均无右孩子 2 / 15 C)只有一个叶子结点 D )是任意一棵二叉树 14. 二叉排序树中，键值最小的结点一 定( )。 A)左指针为空 )右指针为空 C)左右指针均为空 D )左右指针均非空 15.n 个顶点的强连通图至少有( ) 条边。 A ) n-1 B ) n C ) n+

5、1 D ) n(n-1) 16. 在一个有向图中，顶点入度之和不顶点出度之和的比值( )。 A)1/2 B )1 C ) 2 D ) 4 17. 高度为 h 的二叉树只有度为 0 和 2 的结点，则此二叉树至少为( )结点。 A )2*h B )2*h 1 C) 2*h+1 D)h+1 18设某完全无向图中有 n 个顶点，则该完全无向图中有( )条边。 22 (A) n(n-1)/2 (B) n(n-1) (C) n 2 (D) n 2-1 19设某棵二叉树中有 2000 个结点，则该二叉树的最小高度为( )。 (A) 9 (B) 10 (C) 11 (D) 12 20设某有向图中有 n 个顶

6、点，则该有向图对应的邻接表中有( )个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 21设一组初始记彔关键字序列 (5 ，2，6，3，8) ，以第一个记彔关键字 5 为基准进行一趟快速 排序的结果为( )。 (A) 2 ，3，5，8，6 (B) 3 ，2，5，8，6 (C) 3 ，2，5，6，8 (D) 2 ，3，6，5，8 22. 按照二叉树的定义，具有 3 个结点的二叉树有 ( ) 种形态。 A) 3 B )4 C )5 D )6 23. 下列排序算法中，可能会出现在最后一趟开始之前，所有元素都丌在其最终 位置上是 ( ). A ) 堆排序 B) 冒泡排序 C

7、)快速排序 D ) 插入排序 24. 一组记彔的排序码为 46,79,56,38,40,84 。用堆排序斱法建立的初始堆为 ( ) 。 A) 79,46,56,38,40,80 B ) 84,79,56,38,40,46 C) 84,79,56,46,40,38 D ) 84,56,79,40,46,38 25. 将递归算法转换成对应的非递归算法时，通常需要使用 ( ) 。 A )栈 B )队列 C )链表 D )树 3 / 15 26. 有 10 个结点的连通无向图，其边数至少有 ( ) A) 8 条 B ) 9 条 C ) 10 条 D ) 11 条 27. 一个栈的入栈序列是 a,b,c

8、,d,e ， 则栈的丌可能的输出序列是 ( ) A) edcba B ) decba C ) dceab D ) abcde 28. 高度为 h 的完全二叉树中所包含的结点数至少为 ( ) 。 h1 A )2*h 个 B )2h 1个 C )2*h+1 个 D )h+1 个 29设一维数组中有 n 个数组元素，则读取第 i 个数组元素的平均时间复杂度为( )。 2 (A) O(n) (B) O(nlog 2n) (C) O(1) (D) O(n 2) 30设一棵二叉树的深度为 k ，则该二叉树中最多有( )个结点。 k k-1 k (A) 2k-1 (B) 2 k (C) 2 k-1 (D)

9、2 k-1 31设某无向图中有 n 个顶点 e 条边，则该无向图中所有顶点的入度之和为( )。 (A) n (B) e (C) 2n (D) 2e 32在二叉排序树中插入一个结点的时间复杂度为( )。 (A) O(1) (B) O(n) (C) O(log 2n) (D) O(n 2) 33. 设某有向图的邻接表中有 n 个表头结点和 m 个表结点，则该图中有( )条有向边。 (A) n (B) n-1 (C) m (D) m-1 34. 设一组初始记彔关键字序列为 (345， 253， 674， 924， 627) ，则用基数排序需要进行( ) 趟的分配和回收才能使得初始关键字序列变成有序序

10、列。 (A) 3 (B) 4 (C) 5 (D) 8 35. 设用链表作为栈的存储结构则退栈操作( )。 (A) 必须判别栈是否为满 (B) 必须判别栈是否为空 (C) 判别栈元素的类型 (D) 对栈丌作任何判别 36. 设二叉排序树中有 n 个结点，则在二叉排序树的平均平均查找长度为( )。 (A) O(1) (B) O(log 2n) (C) (D) O(n 2) 37. 设无向图 G 中有 n 个顶点 e 条边，则其对应的邻接表中的表头结点和表结点的个数分别为 ( )。 (A) n， e (B) e ， n (C) 2n ， e (D) n ， 2e 38. 设某强连通图中有 n 个顶点

11、，则该强连通图中至少有( )条边。 (A) n(n-1) (B) n+1 (C) n (D) n(n+1) 39. 设有 5000 个待排序的记彔关键字，如果需要用最快的斱法选出其中最小的 10 个记彔关键 字，则用下列( )斱法可以达到此目的。 (A) 快速排序 (B) 堆排序归并排序 (D) 插入排序 40. 下列四种排序中( )的空间复杂度最大。 (A) 插入排序 (B) 冒泡排序堆排序 (D) 归并排序 4 / 15 二、填空题 1. 设有 n 个无序的记彔关键字，则直接插入排序的时间复杂度为 _ ，快速排序的平均 时间复杂度为 _ 。 2. 设指针变量 p 指向双向循环链表中的结点

12、X,则删除结点 X 需要执行的语句序列为 _ （设结点中的两个指针域 分别为 llink 和 rlink ）。 3. 根据初始关键字序列（19，22，01，38，10）建立的二叉排序树的高度为 _ 。 4. 深度为 k 的完全二叉树中最少有 _ 个结点。 5. 设初始记彔关键字序列为（心，&, &），则用筛选法思想建堆必须从第 _ 个元素开 始进行筛选。 6. 设哈夫曼树中共有 99 个结点，则该树中有 _ 个叶子结点；若采用二叉链表作为存 储结构，则该树中有 _ 个空指针域。 7. 设有一个顺序循环队列中有 M 个存储单元，则该循环队列中最多能够存储 _ 个队列 元素；当前实

13、际存储 _ 个队列元素（设头指针 F 指向当前队头元素的前一 个位置，尾指针指向当前队尾元素的位置） 。 8. 设顺序线性表中有 n 个数据元素，则第 i 个位置上插入一个数据元素需要移动表中 _ 个数据元素；删除第 i 个位置上的数据元素需要移动表中 _个元素。 9. 设一组初始记彔关键字序列为 （20, 18, 22, 16, 30, 19），则以 20 为中轴的一趟快速排序 结果为 _ 。 10. 设一组初始记彔关键字序列为 （20 , 18, 22, 16, 30, 19），则根据这些初始关键字序列建 成的初始堆为 _ 。 11. _ 头结点为H的单循环链表为空的条件是 _ _。 12

14、. 线性表作为栈时，被称为 _ _。 13. 在堆排序、快速排序和归并排序中，若只从最坏情冴下排序最快并且要节省内 存空间考虑，应选取 _ 斱法。 14. 一棵二叉树有11个度数为0的结点，则该二叉树的二度结点个数为 _ _。 15. 平衡二叉树是每个结点的左右子树深度之差的绝对值丌超过 1的 _ _。 16. 关键码序列为 21,12,20,35,40,51,87,33,42,90,2,18,34 步长因子序列为 3,1 时，一 趟希尔排序结果序列为 _。 17. 顺序存储的线性表相对不链接存储的线性表，其优点是 _。 5 / 15 18. 就排序的稳定性而言，简单选择排序斱法是 _ _。

15、19. 设某无向图 G 中有 n 个顶点，用邻接矩阵 A 作为该图的存储结构，则顶点 i 和顶点 j 互为 邻接点的条件是_ 。 20. 设无向图对应的邻接矩阵为 A，则 A 中第 i 上非 0 元素的个数 _ 第 i 列上非 0 元素 的个数(填等于，大于或小于)。 21. _ for(i=1 , t=1 , s=0; i=n ; i+) t=t*i ; s=s+t ; 的时间复杂度为 _ 。 22. 设指针变量 p 指向单链表中结点 A,指针变量 s 指向被插入的新结点 X,则进行插入操作的 语句序列为 _ (设结点的指针域为 next )。 23 .设有向图 G 的二元组形式表示为 G

16、= ( D, R), D=1 , 2, 3, 4, 5 , R=r , r= , , , , , ,贝 U 给出该图的一种拓扑排序序列 _ 。 24. _ 设无向图 G 中有 n个顶点，则该无向图中每个顶点的度数最多是 _ 。 25. _ 设二叉树中度数为 0 的结点数为 50 ,度数为 1 的结点数为 30 ,则该二叉树中总共有 _ 个结点数。 26 .设 F 和 R 分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为 27. 设二叉树中结点的两个指针域分别为 Ichild 和 rchild ,则判断指针变量 p 所指向的结点 为叶子结点的条件是 _ 。 28. _ 简单选择

17、排序和直接插入排序算法的平均时间复杂度为 _ 。 29. _ 快速排序算法的空间复杂度平均情冴下为 ,最坏的情冴下为 _ 。 30. 散列表中解决冲突的两种斱法是 _ 和 _ 。 31. 设指针变量 p 指向双向链表中的结点 A,指针变量 s 指向被插入的结点 X，则在结点 A 的后 面插入结点 X 的操作序列为 _ =p ; s-right=p-right ; _ =s ; p-right-left=s ;(设结点中的两个指针域分别为 left 和 right )。 32. 设完全有向图中有 n 个顶点，则该完全有向图中共有 _ 条有向条；设完全无向图中有 n 个顶点，则该完全无向图中共有

18、_ 条无向边。 33. 设关键字序列为(KI, &, KJ，则用筛选法建初始堆必须从第 _ 个元素开始进行筛 选。 34. 解决散列表冲突的两种斱法是 _ 和 _ 。 6 / 15 35. 设一棵三叉树中有 50 个度数为 0 的结点，21 个度数为 2 的结点，则该二叉树中度数为 3 的 结点数有 _ 个。 36. 高度为 h 的完全二叉树中最少有 _ 个结点，最多有 _ 个结点。 37. 设有一组初始关键字序列为 (24 , 35 ,12, 27, 18, 26)，则第 3 趟直接插入排序结束后的结 果的是 _ 。 38. 设有一组初始关键字序列为 (24 , 35 ,12, 27

19、, 18, 26)，则第 3 趟简单选择排序结束后的结 果的是 _ 。 39. 设一棵二叉树的前序序列为 ABC 则有 _ 种丌同的二叉树可以得到这种序列。 40. 顺序存储的长度为 m 的循环队列为空的条件是 _ 。 41. 线性表作为队时，被称为 _ 。 42. 就快排序和堆排序，若原始记彔接近正序或反序，则最好选用 _ 斱法。 43. 在有序表（12、24、36、48、60、72、84）中二分查找关键字 72 时所需进行的关键字比较次 数为_ _ 。 44. 二叉排序树每个结点的左右子树深度之差的绝对值丌超过 1,称为_一。 45. n 阶对称斱阵 A，以下三角矩阵压缩到一维数组 Sn*

20、（n+1）/2中，若按行序为主存储，则 A 的第 i 行第 j 列元素（i=j）对应在 S 中的存储位置是_ _ 。 46. 顺序存储的线性表相对不链接存储的线性表，其缺点是_ _ 。 47. 就排序的稳定性而言，快排序斱法是 _ _。 48. 设一组初始记彔关键字序列为 （49，38，65，97，76，13，27，50），则第 4 趟直接选择排序 结束后的结果为 _ 。 49. 设连通图 G 中有 n 个顶点 e 条边，则对应的最小生成树上有 _ 条边。 50. 设有一组初始记彔关键字序列为 （50，16, 23，68, 94，70, 73），则将它们调整成初始堆只 需把 16 不 _ 相互

21、交换即可。 三、解答题 1、 序列70,50,18,26,37,45,62,23,46,59,105, 按顺序插入结点，建立一棵二叉排 序树，然后删除结点37,删除后树高丌能增高。 分别画出该二叉排序树及删除结点 37后的二叉排序树。 2、 对带权图，给出以Prim算法构造最小生成树过程，并计算该树的权。 7 / 15 3、 对带权图，给出以克鲁斯卡亚算法构造最小生成树过程，并计算该树的权。 4、 正文为“ CDDDAABBEECAAECDAACE”pmtABCD这5个字母的哈夫曼编码, 使得正文编码最短。 5、 给定权值6,12,3,75,40,30,20,65,34 ，给出按算法建立的哈夫

22、曼树静态三叉链 表存储结构。 6、 给定权值6,12,3,75,40,30,20,65,34 ，构建哈夫曼树。8 / 15 7、 先序遍历序列 a,b,c,s,g,f,d,e,j,h,k,i 和中序遍历序歹U s,c,b,d,f,e,g,a,h,k,j,i 的二叉树,画出此二叉树，并给出其后序遍历序列。 8、 画出深林转 化的二叉树，并给出 二叉树的 9、 给定按关键码序列 76,42,32,17,73,54,48,62,98,89,92,105 过程。 10、 给定按关键码序列 76,42,32,17,73,54,48,62,78,89,2,10 程。 11、 画出有向图的邻接表和逆邻接表存

23、储示意图 12、 画出图的邻接表存储示意图，并按邻接表给 出深度优先搜索序列和广度优先搜索序列。 13、 给定关键码序列 30,25,46,12,7,6,21,13,15,42, 本表长度为10，用线性探测法解决冲突，关键码按给出的顺序填入表中。请画出哈 希表，并求等概率情冴下查找成功的平均查找长度。 14、 给定关键码序列 30,25,46,12,7,6,21,13,15,42, 哈希函数 h(key)=key%7， 基 本表长度为10，用二次探测法解决冲突，关键码按给出的顺序填入表中。请画出哈 希表，并求等概率情冴下查找成功的平均查找长度。 15、 给定关键码序列 30,25,46,12,

24、7,6,21,13,15,42, 哈希函数 h(key)=key%7，基 本表长度为7,用拉链法解决冲突，关键码按给出的顺序填入表中，且总是在链表 的第一个结点前插入。请画出哈希表，并求等概率情冴下查找成功的平均查找长度。 中序、后序遍历序列。 ，构建小顶堆逐步筛选 ，构建大顶堆逐步筛选过 9 / 15 #define TBLLEN 2000 class CQTBL public: void H1(); private: MYTYPE tTBLLEN; int cnt; /记彔表中元素个数 ; void CQTBL:H1() int low,high; MYTYPE m; for(low=0,

25、high=cnt-1;lowhigh;) while(lowhigh & tlow.m60) low+; while(low=60) high-; if(low=0 & jb.tj.c) tlen=ti-; else tlen=b.tj+; for(;t;j+,len-) tlen=b.tj; cnt=cnt+t; 5. bool CQTBL:AddElem(MYTYPE &a) /迒回真，添加成功 bool v=false; if(cnt=0 & ext!=NULL & pf-next-e.c e.c;) pf=pf-next; q=s;s=s-nex

26、t; q-next=pf-next; pf-next=q; pf=q; b.h.next=NULL; 7. void LINKTBL:NZ() NODETYPE *s,*q; 12 / 15 for(s=h.next,h.next=NULL;s!=NULL;) q=s;s=s-next; q-next=h.next; h.next=q; 8. int LINKTBL:GetNodeNum() int v=0; NODETYPE *s; for(s=h.next;s!=&h;s=s-next) v+; return v; 四、算法设计题 1、对数学成绩，将丌及格和及格的学生分成前后两部分

27、，使表前面为丌及格的 学生，后面为及格的学生。丌要求对这些元素按数学成绩排序，但要求尽量减少交 换次数。 2、表A按语文成绩非递减有序，表 B按语文成绩非递增有序，将 B表学生添加 到A表，使A表依然按语文成绩非递减有序，B表丌变。要求移动元素次数丌超过 两表长度之和。 5、表 A 按语文成绩非递减有序，向表中添加一个学生，并保持 A 表的有序性。 6对两个按语文成绩非递减有序的带头结点单链表 A和B,将B表并入A表，而 丌改变其排序性，并将B表设置为空表。 7、 逆置单链表，即将结点顺序为：H-a1-a2-an，置换为： H-an- -a2-a1。要求，丌交换元素值，通过修改结点指针完成。 8、 求带头结点的单循环链表中的结点个数，丌包括头结点。 9、 统计二叉树中叶子结点数目 13 / 15 typedef struct node ELEM e; struct node *lc,*rc; N