数据结构模拟试题

1、数据结构数据结构专升本考试试卷专升本考试试卷1 1、单项选择题、单项选择题(15 (15 个小题个小题) )a ad da aa ad dc cc ca ab bd da ab ba ac cd d2 2、判断题、判断题(10 (10 个小题个小题) )1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 2 3 4 5 6 7 8 9 10 11 12 13 14 151 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 三、填空题三、填空题 1.1.在带有头结点的双链表在带有头结点的双链表L L中，指针中，指针P P所指结点是第一个元素结点

2、的条件是所指结点是第一个元素结点的条件是: : L-front=pL-front=p或或p-back=Lp-back=L 。 2.2.在具有在具有n n个单元、顺序存储的循环个单元、顺序存储的循环队列中，队满时共有队列中，队满时共有 n-1n-1 个元素。个元素。 3. 3.设设sq1.maxsizesq1.maxsize为顺序存储的栈，为顺序存储的栈，变量变量toptop指示栈顶元素的位置。能作入指示栈顶元素的位置。能作入栈操作的条件是栈操作的条件是 TopMAXSIZETopMAXSIZE 。如果。如果把栈顶元素弹出并送到把栈顶元素弹出并送到x x中，则需执行中，则需执行下列语句下列语句:

3、 : x=sqTop;Topx=sqTop;Top=Top-1=Top-1 。 4.4.二维数组二维数组A1020A1020采用列为主序采用列为主序方式存储，每个元素占用一个存储单元方式存储，每个元素占用一个存储单元, ,并且并且A00A00的存储地址是的存储地址是200,200,则则A612A612的地址是的地址是: :1212* *10+6+200=32610+6+200=326。 5. 5.树树t t的存储结构为二叉链表的存储结构为二叉链表btbt，树，树t t中一个非叶子结点在中一个非叶子结点在btbt中满足条件：中满足条件： 其左右子树不能同时为空其左右子树不能同时为空 。 6.6.

4、如果含如果含n n个顶点的图式一个环，则个顶点的图式一个环，则它有它有 n n 棵生成树。棵生成树。 7.7.对有对有1717个元素的有序表个元素的有序表1.171.17作作折半查找，在查找值等于折半查找，在查找值等于A8A8的元素时，的元素时，被比较的元素的下标依次为被比较的元素的下标依次为: : 9,4,6,7,89,4,6,7,8 。 8. 8.一个单链表一个单链表P P结点之后插入结点之后插入S S结点时，结点时，应执行应执行S-next=S-next= P-nextP-next 和和 P-next=P-next= S S 的操作。的操作。 9.9.利用线性利用线性- -交换选择排序算

5、法对有交换选择排序算法对有n n个记录的数据表进行排序，最坏的情况个记录的数据表进行排序，最坏的情况下，记录的交换次数为下，记录的交换次数为 n n2 2 。 10.10.算术式算术式(A+B)-C+D/E(A+B)-C+D/E的前序式为的前序式为: : +-+ABC/DE+-+ABC/DE , ,后序式为后序式为: : AB+C-DE/+AB+C-DE/+ 。 11.11.设行列的下三角矩阵已经设行列的下三角矩阵已经压缩到一维数组压缩到一维数组S1.nS1.n* *(n-1)/2(n-1)/2中，中，若按行序为主序存储，则若按行序为主序存储，则AijAij 对应对应的中的存储位置是的中的存储

6、位置是 i i* *(i-1)/2+j(i-1)/2+j 。 12. 12. 432112113211211 432112113211211 。四、解答下列各题四、解答下列各题、已知一棵二叉树的前序、中序列、已知一棵二叉树的前序、中序列是是ABCDEFGHIJKABCDEFGHIJK，CDBGFEAHJIKCDBGFEAHJIK，请构造，请构造出该二叉树。出该二叉树。A AB BH HC CE EI IF FG GD DJ JK K、对下面给出的数据序列，构造一、对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。棵哈夫曼树，并求出其带权路径长度。4,5,6,7,10,12,15,1

7、8,234,5,6,7,10,12,15,18,23100100424219199 94 45 51010232358582525333312121313151518186 67 7WPL=(4+5)WPL=(4+5)* *4+4+ 10 10* *3+3+ 23 23* *2+2+ 12 12* *3+3+ (6+7) (6+7)* *4+4+ (15+18) (15+18)* *3 3 = =299299 、设图、设图G=(V,E),G=(V,E), V=1,2,3,4,5,6), V=1,2,3,4,5,6), E=, E=, , , , 请写出图请写出图G G中顶点的所有拓扑序列。中顶

8、点的所有拓扑序列。1 13 32 26 65 54 41,2,3,6,5,41,2,3,6,5,41,3,6,2,5,41,3,6,2,5,41,3,2,6,5,41,3,2,6,5,4、对下面给出的数据序列，写出堆、对下面给出的数据序列，写出堆排序过程。排序过程。(45,36,18,53,72,30,48,93,15)(45,36,18,53,72,30,48,93,15)454536361818535372723030484893931515939372724848535345453030181836361515大顶堆大顶堆151572724848535345453030181836369

9、393输出输出93727253534848363645453030181815159393调整调整151553534848363645453030181872729393输出输出7272535345454848363615153030181872729393调整调整请自己继续完成请自己继续完成、利用、利用DijkstraDijkstra算法求出下图中从算法求出下图中从顶点到其余顶点的最短路径。顶点到其余顶点的最短路径。33082541252010 第第1趟趟 第第2趟趟 第第3趟趟 第第4趟趟V2 3 v1,v2V3 28 15 v1,v3 v1,v2,v3 v1,v2,v4,v3V4 11

10、v1,v4 v1,v2,v4 V5 30 30 23 23 v1,v5 v1,v5 v1,v2,v4,v5 v1,v2,v4,v5Vj V2 V4 V3 V5 S v1,v2 v1,v2,v4 v1,v2,v4, v3 v1,v2,v4,v5, S:S:当前已确定了最短距离的顶点集合当前已确定了最短距离的顶点集合。模拟试卷一模拟试卷一1 1、单项选择题、单项选择题(9 (9 个小题个小题) )3 34 41 11 12 24 41 14 44 42 2、判断题、判断题(4 (4 个小题个小题) )1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 1 2 3

11、 4 三、填空题三、填空题 1.1.在带有头结点的单链表在带有头结点的单链表L L中，第一中，第一个元素结点的指针是个元素结点的指针是 L-nextL-next 。 2.2.在双循环链表中，在指针在双循环链表中，在指针P P所指结所指结点前插入指针点前插入指针S S所指的结点，需执行下列所指的结点，需执行下列语句：语句： S-front=P; S-back=P-back;S-front=P; S-back=P-back; P-back=S; P-back=S; S-back-frontS-back-front=S=S。 3. 3.设设sq1.maxsizesq1.maxsize为一个顺序存为一

12、个顺序存储的栈，变量储的栈，变量toptop指示栈顶元素的位置。指示栈顶元素的位置。栈为空的条件是栈为空的条件是 top=0top=0 ，栈为满的条，栈为满的条件是件是 top=maxsizetop=maxsize 。 4.4.具有具有100100个结点的完全二叉树的个结点的完全二叉树的深度为深度为 7 7 。 5.5.有向图有向图G G用邻接矩阵用邻接矩阵A1.n,1.nA1.n,1.n存储，其第存储，其第i i行的所有元素之和等于顶行的所有元素之和等于顶点点i i的的 出度出度 。 6. 6. 对下面的二叉树，按中序遍历所得对下面的二叉树，按中序遍历所得到的结点序列为到的结点序列为 DBH

13、EACFDBHEACF 。 A AB BC CD DH HF FE E 7 7、分别采用堆、快速、插入和归并、分别采用堆、快速、插入和归并排序算法对初始状态为递增序列的表按排序算法对初始状态为递增序列的表按递增排序，递增排序， 最省时间的算法是最省时间的算法是 插入插入 算法，算法， 最费时间的算法是最费时间的算法是 快速快速 算法。算法。 8. 8.对下图所示的网，执行对下图所示的网，执行primprim算法可得到算法可得到最小生成树，试在下表的空白处填上适当的最小生成树，试在下表的空白处填上适当的内容，以说明该算法的执行过程。内容，以说明该算法的执行过程。1 13 34 42 21 15

14、55 52 24 42,4,3,2,4,3,11(U,V)(U,V)代价代价 1 12,4,32,4,3(2,1)(2,1)1(U,V)(U,V)代价代价1,31,32,42,4(2,3)(2,3)4(4,1)(4,1)5 5(U,V)(U,V)代价代价1,3,1,3,4422(2,4)(2,4)3(2,3)(2,3)4(2,1)(2,1)(U,V)(U,V)代价代价V VU U4 43 31 1顶点顶点四、应用题四、应用题 1 1、已知一棵二叉树的后序序列、中序序列、已知一棵二叉树的后序序列、中序序列如下，请构造该二叉树。如下，请构造该二叉树。 后序序列：后序序列：ABCDEFGABCDEF

15、G 中序序列：中序序列：ACBGEDFACBGEDFG GC CF FA AE EB BD D 2 2、有一组关键字序列、有一组关键字序列 (38,19,65,13,97,49,41,95,1,73)(38,19,65,13,97,49,41,95,1,73)采用冒泡排序方法按从小到大的次序进采用冒泡排序方法按从小到大的次序进行排序，写出每趟排序的结果。行排序，写出每趟排序的结果。38 19 19 13 13 13 13 13 1338 19 19 13 13 13 13 13 13 1 119 38 13 19 19 19 19 1919 38 13 19 19 19 19 19 1 1 1

16、31365 13 38 38 38 38 3865 13 38 38 38 38 38 1 1 191913 65 49 41 41 4113 65 49 41 41 41 1 1 383897 49 41 49 4997 49 41 49 49 1 1 414149 41 65 1 1 49 41 65 1 1 494941 95 1 65 41 95 1 65 656595 1 73 95 1 73 73731 73 1 73 9595 73 73 97973 3、设图、设图G=(V,E),G=(V,E), V=1,2,3,4,5,6), V=1,2,3,4,5,6), E=, E=, ,

17、 , , 请写出图请写出图G G中顶点的所有拓扑序列。中顶点的所有拓扑序列。1 12 23 36 65 54 41 1：1 2 3 6 5 41 2 3 6 5 42 2：1 3 6 2 5 41 3 6 2 5 43 3：1 3 2 6 5 41 3 2 6 5 44 4、对下面两棵二叉树，分别画出它们、对下面两棵二叉树，分别画出它们的顺序存储结构。的顺序存储结构。 A AB BC CD DF FI IG GE EJ JK KA AB BC CD DF FE EJ JI I顺序存储结构。顺序存储结构。 A AB BC CD DF FI IG GE EJ JK KK KJ JI IH HG G

18、F FE ED DC CB BA A1 2 3 4 5 6 7 8 9 10 111 2 3 4 5 6 7 8 9 10 11顺序存储结构。顺序存储结构。 A AB BC CD DF FE EJ JI IJ JI IF FE ED DC CB BA A1 2 3 4 5 6 7 8 9 10 111 2 3 4 5 6 7 8 9 10 11、图、图G G的邻接表如下，画出图的邻接表如下，画出图G G的所有的所有连通分量。连通分量。IHGFEDCBA5476727193 26 31 12 23 34 45 56 67 78 89 99 34A AE EB BD DG GC CI IF F模拟

19、试卷二模拟试卷二1 1、单项选择题、单项选择题(5 (5 个小题个小题) )2 2、判断题、判断题(9 (9 个小题个小题) )cabdd1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 三、填空题三、填空题 1.1.在单链表中，删除指针在单链表中，删除指针P P所指结点的所指结点的后继结点的语句是后继结点的语句是 P-next=P-next-P-next=P-next-nextnext 。 2.2.已知完全二叉树的第八层有已知完全二叉树的第八层有8 8个结点，个结点，则其叶子结点数是则其叶子结点数是 6868 。 3.3.将下三角

20、矩阵将下三角矩阵1.8,1.81.8,1.8的下三的下三角部分逐行地存储到起始地址为角部分逐行地存储到起始地址为10001000的的内存单元中，已知每个元素占用内存单元中，已知每个元素占用4 4个单元，个单元，则则A7,5A7,5的地址是的地址是 11041104 。 4. 4.有有n n个顶点的强连通有向图个顶点的强连通有向图G G至少至少有有 n n 条弧。条弧。 5.5.求最短路径的求最短路径的DijkstraDijkstra算法的时间算法的时间复杂度为复杂度为 O(nO(n2 2) ) 。 6.6.在有序表在有序表1.201.20中，采用折半查中，采用折半查找算法查找元素等于找算法查找

21、元素等于A12A12的元素，所的元素，所比较的元素的下标依次为比较的元素的下标依次为 10,15,1210,15,12 。 7. 7.交换交换- -线性选择排序算法所执行的线性选择排序算法所执行的元素交换次数最多为元素交换次数最多为 n-1n-1 。 8.8.下列排序算法中，稳定的算法是：下列排序算法中，稳定的算法是： 中心插入中心插入 排序排序( (选择、堆、快速、中选择、堆、快速、中心插入）。心插入）。四、应用题四、应用题、已知一棵二叉树的、已知一棵二叉树的 前序序列是：前序序列是：ABCDEFGHIJABCDEFGHIJ， 中序序列是：中序序列是：CBEDAGHFJICBEDAGHFJI

22、，请构造出该二叉树。请构造出该二叉树。A AB BF FC CD DG GI IE EH HJ J、对下面给出的数据序列，构造一、对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。棵哈夫曼树，并求出其带权路径长度。 4,5,6,7,10,12,15,18,234,5,6,7,10,12,15,18,23 数据结构数据结构专升本考试试题专升本考试试题 第四大题的第二小题第四大题的第二小题、图、图G G的邻接表的邻接表如下，完成下列如下，完成下列各题各题 (1)(1)画出从顶画出从顶点点5 5出发进行广度出发进行广度遍历所生成的生遍历所生成的生成树。成树。 (2)(2)判断其中判断其中

23、是否存在有向回是否存在有向回路，若不存在，路，若不存在，求出其拓扑排序求出其拓扑排序121110987654321325467989108111291011125 510109 98 811111212(1)(1)从顶点从顶点5 5出发广度遍历所生成的生成树。出发广度遍历所生成的生成树。(2)(2)其拓扑排序：其拓扑排序： 1,2,4,5,8,9,10,3,7,6,11,121,2,4,5,8,9,10,3,7,6,11,12、对下列数据表，写出采用快速排、对下列数据表，写出采用快速排序的每一趟的结果。序的每一趟的结果。(60,20,31,1,5,44,55,61,200,30,80,150,

24、4,29)(60,20,31,1,5,44,55,61,200,30,80,150,4,29) 29 61 29 61 4 200 4 200 30 60 30 60(30 20 31 1 5 44 55 29 4)(30 20 31 1 5 44 55 29 4)6060(80 150 200 61)(80 150 200 61) 4 31 4 31 29 44 29 44(29 20 4 1 5)(29 20 4 1 5)3030(55 44 31)(55 44 31)(5 20 4 1)(5 20 4 1)2929() () (4 1)(4 1)5 5(20)(20) 1 4 5 20

25、29 30 1 4 5 20 29 30 (29 20 4 1 5)(29 20 4 1 5)3030(55 44 31)(55 44 31)(5 20 4 1)(5 20 4 1)2929() () (4 1)(4 1)5 5(20)(20) 1 4 5 20 29 30 1 4 5 20 29 30 (31 44)55 (31 44)55 31 44 55 31 44 55 6060(80 150 200 61) (80 150 200 61) (61) 80 (200 150) (61) 80 (200 150) 150 200 150 2001 4 5 20 29 30 31 44 5

26、5 60 61 80 150 200 1 4 5 20 29 30 31 44 55 60 61 80 150 200 另一种方法：另一种方法： (60,20,31,1,5,44,55,61,200,30,80,150,4,29)(60,20,31,1,5,44,55,61,200,30,80,150,4,29) 29 60 29 60 60 61 60 61 4 60 4 60 60 200 60 200 30 60 30 60 (29 20 31 1 5 44 55 4 30) (29 20 31 1 5 44 55 4 30)6060(80 150 200 61)(80 150 200

27、61) 4 29 4 29 29 31 29 31 5 29 5 29 (4 20 5 1) (4 20 5 1)2929(44 55 31 30)(44 55 31 30) 1 4 1 4 4 20 4 20 (1 4)5(20) (1 4)5(20) 2929(44 55 31 30)(44 55 31 30) 30 44 30 44 31 55 31 55 (30 31) (30 31)4444(55)(55) 30(31)44 30(31)44 30 31 30 55 30 31 30 55 6060(80 150 200 61)(80 150 200 61) 61 80 61 80

28、80 150 80 150 (61) (61)8080(150 200)(150 200) 150150(200)(200) 1 4 5 20 29 30 31 44 55 61 80 150 200 1 4 5 20 29 30 31 44 55 61 80 150 200 模拟试卷三模拟试卷三1 1、单项选择题、单项选择题(9 (9 个小题个小题) )d db bd dc ca ac cc cd db b2 2、判断题、判断题(7 (7 个小题个小题) )1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 1 2 3 4 5 6 7 三、填空

29、题三、填空题 1.1.在双循环链表在双循环链表L L中，指针中，指针P P所指结点所指结点为尾结点的条件是为尾结点的条件是 P-front=LP-front=L 。 2.2.在单链表中，删除指针在单链表中，删除指针P P所指结点所指结点的后继结点的语句是的后继结点的语句是: : P-next=P-next-nextP-next=P-next-next 。 3.3.队列的特性是队列的特性是 先进先出先进先出 。 4.4.有有n n个叶子结点的哈夫曼树，总结个叶子结点的哈夫曼树，总结点数是点数是 2 2* *n-1n-1 。 5. 5.有有n n个顶点的无向图其边数最多为个顶点的无向图其边数最多为

30、 n n* *(n-1)/2(n-1)/2 。 6.6.对矩阵采用压缩存储是为了对矩阵采用压缩存储是为了 节省节省存储空间存储空间 。 四、应用题四、应用题、分别画出满足下列条件的所有二、分别画出满足下列条件的所有二叉树。叉树。 前序序列和中序序列均为前序序列和中序序列均为ABCDEABCDE。 前序序列为前序序列为ABCDEABCDE，并且与其相对于，并且与其相对于应的树高度为应的树高度为5 5。1)1)A AB BC CD DE E2)2)A AB BC CD DE E2 2、对下列数据表，写出采用、对下列数据表，写出采用shellshell排排序的每一趟的结果。序的每一趟的结果。100,

31、12,20,31,1,5,44,66,61,200,30,80,150,4,8100,12,20,31,1,5,44,66,61,200,30,80,150,4,8d1=7:d1=7:100 12 20 31 1 5 44 66 61 200 30 80 150 4 8100 12 20 31 1 5 44 66 61 200 30 80 150 4 866661001008 81001008 866661 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 8,8,12,20,31,1,5,44,12,2

32、0,31,1,5,44,6666,61,200,30,80,150,4,61,200,30,80,150,4,100100303031314 44444整理后：整理后：d=3d=38,12,20,30,1,5,4,66,61,200,31,80,150,44,1008,12,20,30,1,5,4,66,61,200,31,80,150,44,1001 115015012122002004 44 48 85 52020若有交换且可以回溯则必须进行若有交换且可以回溯则必须进行比较，直到不必交换或不可回溯比较，直到不必交换或不可回溯为止，然后再接着从刚才的位置为止，然后再接着从刚才的位置继续比较。

33、继续比较。整理后：整理后：4,1,5,8,12,20,30,31,61,150,44,80,200,66,1004,1,5,8,12,20,30,31,61,150,44,80,200,66,100最后一趟最后一趟 d=1d=11,4,5,8,12,20,30,31,44,61,66,80,100,150,2001,4,5,8,12,20,30,31,44,61,66,80,100,150,200模拟试卷四模拟试卷四1 1、单项选择题、单项选择题(6 (6 个小题个小题) )a ab bc ca ac ca a2 2、判断题、判断题(6 (6 个小题个小题) )1 2 3 4 5 6 1 2

34、3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 三、填空题三、填空题 1.1.带头结点的双循环链表带头结点的双循环链表L L为空表的为空表的条件是条件是 L-front=LL-front=L 。 2.2.在双链表中，在指针在双链表中，在指针P P所指结点前所指结点前面插入一个结点面插入一个结点S S的语句序列是：的语句序列是：S-S-front=P;S-back=P-back;Pfront=P;S-back=P-back;P-back=S;-back=S; S-back-front=SS-back-front=S 。 3.3.已知完全二叉树的第已知完全二叉树的第7 7层有层有1

35、010个结点，个结点，则整个二叉树的结点最多是则整个二叉树的结点最多是 235235 。 4. 4.有有n n个顶点并且高度为个顶点并且高度为n n的二叉树的二叉树的数目是的数目是 2 2n-1n-1 。 5. 5. 循环队列采用数组循环队列采用数组data1.ndata1.n来存储元素的值，并用来存储元素的值，并用frontfront和和rearrear分分别作为其指针，为区分队列的满和空，别作为其指针，为区分队列的满和空，约定：队中能够存放的元素个数最大约定：队中能够存放的元素个数最大n-n-1 1，也即至少一个元素空间不用，则在，也即至少一个元素空间不用，则在任意时刻，至少知道一个空元素

36、的下标任意时刻，至少知道一个空元素的下标是是 frontfront , ,可用语句可用语句 rear=(rear+1rear=(rear+1)%n)%n 求出新元素在数组求出新元素在数组datadata中的下标。中的下标。 6. 6.高度为高度为8 8的平衡二叉树的结点至少的平衡二叉树的结点至少是是 5454 。 7.7.在有在有n n个结点的有向图中，每个顶个结点的有向图中，每个顶点的度最大可达点的度最大可达 2(n-1)2(n-1) 。 8.8.数组数组1.10,1.101.10,1.10的每个元素的每个元素占用占用5 5个单元，将其按列优先次序存储个单元，将其按列优先次序存储在起始地址在

37、起始地址10001000的连续内存单元中，则的连续内存单元中，则A5,6A5,6的地址为的地址为 1270 1270 。四、应用题四、应用题、已知一棵二叉树的、已知一棵二叉树的 中序序列是：中序序列是：DCEFBHGAKJLIMDCEFBHGAKJLIM 后序序列是：后序序列是：DFECHGBKLJMIADFECHGBKLJMIA请构造出该二叉树。请构造出该二叉树。A AB BI IC CJ JG GM MD DE EK KL LE EK K、以下面的数据作为叶子结点构造、以下面的数据作为叶子结点构造一棵哈夫曼树，并求出其带权路径长度。一棵哈夫曼树，并求出其带权路径长度。 5,6,7,8,9,

38、10,15,18,225,6,7,8,9,10,15,18,22WPL=304 WPL=304 5 56 67 78 8111115159 9101019192626151534341818222240406060100100 3 3、对下列数据表，写出采用快速排、对下列数据表，写出采用快速排序的每一趟的结果。并标明每一趟排序序的每一趟的结果。并标明每一趟排序过程的数据移动情况。第二种方法：过程的数据移动情况。第二种方法：5050,12,20,31,1,5,44,166,61,100,30,80,150,4,8,12,20,31,1,5,44,166,61,100,30,80,150,4,88

39、,12,20,31,1,5,44,4,30,8,12,20,31,1,5,44,4,30,5050,100,80,150,61,166,100,80,150,61,1664,5,1,4,5,1,8 8,31,20,44,12,30,31,20,44,12,30,50501,1,4 4,5,5,8 8 30,20,12,30,20,12,3131,44,44 12,20, 12,20,30,30, 61,80,61,80,100100,150,166,150,1661,4,5,8,12,20,30,31,44,50,61,66,100,150,1661,4,5,8,12,20,30,31,44,

40、50,61,66,100,150,166 4 4、求出下图的所有拓扑序列。、求出下图的所有拓扑序列。 6 1 2 3 4 5 6; 1 2 4 3 5 6;1 2 3 4 5 6; 1 2 4 3 5 6; 2 1 3 4 5 6; 2 1 4 3 5 6 2 1 3 4 5 6; 2 1 4 3 5 6。 模拟试卷五模拟试卷五1 1、单项选择题、单项选择题(7 (7 个小题个小题) )c cc cc cb bb bd d1 2 3 4 5 6 7 1 2 3 4 5 6 7 a a二、填空题二、填空题 1.1.双循环链表双循环链表L L中某结点为尾结点的中某结点为尾结点的条件是条件是 P-f

41、ront=LP-front=L 。 2.2.已知二叉树中叶子结点数为已知二叉树中叶子结点数为5050，仅，仅有一个孩子的结点数为有一个孩子的结点数为3030，则整个二叉，则整个二叉树的结点数是树的结点数是 129129 。三、解答下列各题三、解答下列各题、一棵二叉树的前序、中序和后序、一棵二叉树的前序、中序和后序分别如下，其中有一部分未显示出来，分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树。试求出空格处的内容，并画出该二叉树。 前序：前序：A AB BD DF FK KICEHICEHJ JG G， 中序：中序：D DB BKFIAKFIAH HEJCEJCG G， 后

42、序：后序：D DKIKIF FBHJBHJE EG GC CA A。A AB BC CD DF FK KI IE EG GH HJ J该二叉树该二叉树、对下面的递归算法，要求：、对下面的递归算法，要求： (1)(1)写出调用写出调用p(4)p(4)的执行过程。的执行过程。void p(intvoid p(int w) w) if (w0) if (w0) printf(“%d”,w printf(“%d”,w);); p(w-1); p(w-1); p(w-1); p(w-1); P(4):4 3 2 1 1 2 1 1 3 2 1 1 2 1 1P(4):4 3 2 1 1 2 1 1 3

43、2 1 1 2 1 13 3、已知二叉树的存储结构为二叉链表，、已知二叉树的存储结构为二叉链表，阅读下面算法。对如下所示的二叉树。阅读下面算法。对如下所示的二叉树。 (1)(1)画出执行上述算法后所建立的结。画出执行上述算法后所建立的结。 (2)(2)说明该算法的功能。说明该算法的功能。ACBDFEGHVoid inorder(bintreeVoid inorder(bintree T) T)if(Tif(T) ) inorder(T-lchild inorder(T-lchild) )； if(!T-lchild)&(!T-rchildif(!T-lchild)&(!T-rc

44、hild) s=(listnode s=(listnode * *)malloc(sizeof(listnode)malloc(sizeof(listnode);); s-data=T-data; s-data=T-data; s-next=leafhead s-next=leafhead; ; leafhead leafhead=s; =s; inorder(T-rchild inorder(T-rchild) )；/ /* *头插入头插入/ /(2)(2)功能：功能： 将中序遍历二叉树的叶子结点按将中序遍历二叉树的叶子结点按头插入方式建立一个单链表。头插入方式建立一个单链表。leafhea

45、dleafheadF F H H G G D D (1)(1)所建立的结构：所建立的结构：模拟试卷六模拟试卷六1 1、单项选择题、单项选择题(4 (4 个小题个小题) )d dc ca ad d2 2、判断题、判断题(7 (7 个小题个小题) )1 2 3 4 1 2 3 4 1 2 3 4 5 6 7 1 2 3 4 5 6 7 三、填空题三、填空题 1.1.在双循环链表中，删除指针在双循环链表中，删除指针P P所指结所指结点的语句序列是点的语句序列是 P-front-back=P-back P-front-back=P-back 和和 P-back-front=P-front P-back

46、-front=P-front 。 2.2.已知完全二叉树的第已知完全二叉树的第7 7层有层有8 8个结点，个结点，则其叶子结点数是则其叶子结点数是 3636 。 3.3.在有在有n n个叶子结点的哈夫曼树中，结个叶子结点的哈夫曼树中，结点总数是点总数是 2n-12n-1 。 4.4.有有n n个顶点的有向图最多有个顶点的有向图最多有 n(n-1)n(n-1) 条弧。条弧。 5. 5.高度为高度为7 7的平衡二叉树至少有的平衡二叉树至少有 33 33 个结点。个结点。 6.6.在有序表在有序表A1.18A1.18中，采用二分查中，采用二分查找算法查找元素值等于找算法查找元素值等于A7A7的元素，

47、所的元素，所比较过的元素下标依次为比较过的元素下标依次为 9,4,6,79,4,6,7 。 7.7.冒泡排序算法在最好的情况下的元冒泡排序算法在最好的情况下的元素交换次数为素交换次数为 0 0 。 四、解答下列各题四、解答下列各题、已知一棵树的、已知一棵树的 前序序列是：前序序列是：ABCDEFGHIJKLMNABCDEFGHIJKLMN 后序序列是：后序序列是：CDEBHIGKMLNJFACDEBHIGKMLNJFA请构造出该树。请构造出该树。 该树为：该树为：A AB BF FC CE ED DK KG GJ JH HI IL LN NM M. .对下面的数据，写出采用快速排序对下面的数据

48、，写出采用快速排序算法排序的每一趟结果。算法排序的每一趟结果。 70,12,20,31,1,5,44,66,61,200,30,80,150,4,2870,12,20,31,1,5,44,66,61,200,30,80,150,4,283.3.求求V1V1到其他顶点的最短路径。到其他顶点的最短路径。1 12 23 34 47 75 56 68 89 9101014148 812125 53 37 76 65 54 46 63 35 52 26 65 54 43 32 28 8V1 1 2 3 4 5 6 7V1 1 2 3 4 5 6 7V2V2V3V3V4V4V5V5V6V6V7V7V8V8

49、 14 8 12 11 12 13 14 1213 14 20 13 14 20 14 16 22 16 16 16 V3 V3,V2 V3,V2,V4 V3,V2,V4,V5 V3,V2,V4,V5,V6 22V3,V2,V4,V5,V6,V7V3,V2,V4,V5,V6,V7,V8 22 23 18再选再选V10V10加入，最后为加入，最后为V9V9. .V3,V2,V4,V5,V6,V7,V8,V10,V9V3,V2,V4,V5,V6,V7,V8,V10,V9 =8; =8; = 11; 11; =12;=12; = 13;13;= =14; = =14; =16; =16; = = =

50、 16; 16; = = = 18;18; = = = 22;22;V9V9V10V104 4、对下面的递归算法，要求：、对下面的递归算法，要求： (1)(1)写出调用写出调用p(4)p(4)的执行过程。的执行过程。 (2)(2)将其转换为等价的非递归算法。将其转换为等价的非递归算法。void p(intvoid p(int w) w) if (w0) if (w0) p(w-1); p(w-1); printf(“%d”,w printf(“%d”,w);); p(w-1); p(w-1); P(4)P(4)输出结果：输出结果：2 1 3 1 2 1 4 1 2 1 3 1 2 12 1 3

51、 1 2 1 4 1 2 1 3 1 2 15 5、已知一个无向图的顶点集为：、已知一个无向图的顶点集为： a,b,c,d,ea,b,c,d,e,其邻接矩阵如下所示其邻接矩阵如下所示 a 0 1 0 0 1a 0 1 0 0 1 b 1 0 0 1 0 b 1 0 0 1 0 c 0 0 0 1 1 c 0 0 0 1 1 d 0 1 1 0 1 d 0 1 1 0 1 e 1 0 1 1 0 e 1 0 1 1 0 (1) (1)画出该图的图形。画出该图的图形。 (2)(2)根据邻接矩阵从顶点根据邻接矩阵从顶点a a出发进行出发进行深度优先遍历和广度优先遍历，写出相深度优先遍历和广度优先遍历

52、，写出相应的遍历序列。应的遍历序列。深度优先遍历深度优先遍历:a b d c e:a b d c e广度优先遍历广度优先遍历:a b e d c:a b e d ca ad db be ec c模拟试卷七模拟试卷七1 1、单项选择题、单项选择题(4 (4 个小题个小题) )c cb bc cd d2 2、判断题、判断题(6 (6 个小题个小题) )1 2 3 41 2 3 41 2 3 4 5 6 1 2 3 4 5 6 三、填空题三、填空题 1.1.带头结点的双循环链表带头结点的双循环链表L L中，最后中，最后一个结点的指针是一个结点的指针是 L-front=LL-front=L 。 2.2

53、.在仅有尾指针在仅有尾指针p p的单循环链表中，的单循环链表中，在表尾插入一个结点在表尾插入一个结点S S的语句序列是的语句序列是 R-next=S;R=SR-next=S;R=S 。 3.3.已知栈的输入序列为已知栈的输入序列为1,2,3,1,2,3,n,n,输出序列为输出序列为a a1 1,a,a2 2,a,a3 3, ,a,an n, ,符合符合a a2 2=n=n的的输出序列共有输出序列共有 n-1n-1 种。种。 4. 4.已知循环队列用数组已知循环队列用数组data1.ndata1.n存存储元素，用储元素，用f,rf,r分别作为头尾指针，则分别作为头尾指针，则当前的元素个数是当前的

54、元素个数是: : (rear-front+n)%n(rear-front+n)%n 。 5.5.在二叉链表中，判断某指针在二叉链表中，判断某指针p p所指所指结点位叶子结点的条件是结点位叶子结点的条件是: : P-lchild=NULL&P-rchildP-lchild=NULL&P-rchild=NULL=NULL 。 6.6.已知二叉树中叶子结点数为已知二叉树中叶子结点数为2020，仅，仅有一个孩子的结点数为有一个孩子的结点数为3030，则整个二叉，则整个二叉树的结点数是树的结点数是 6969 。 7. 7.有有n n个顶点的连通图中，其边数最个顶点的连通图中，其边数最少为

55、少为 n-1n-1 。 8.8.已知数组已知数组A1.10,1.10A1.10,1.10为对称矩为对称矩阵，其中每个元素占用阵，其中每个元素占用5 5个单元，现将个单元，现将其下三角按行优先次序存储在起始地址其下三角按行优先次序存储在起始地址10001000的连续内存单元中，则的连续内存单元中，则A6,5A6,5对应对应的地址为的地址为 11001100 。9.9.线性线性- -选择排序算法在最好的情况下选择排序算法在最好的情况下所交换元素的次数为所交换元素的次数为 0 0 。 10. 10.已知一个图的广度优先生成树如已知一个图的广度优先生成树如图所示，则与此相应的广度优先遍历序图所示，则与

56、此相应的广度优先遍历序列为列为 a b e f c d ga b e f c d g 。a ad db bf fg ge ec c四、解答下列各题四、解答下列各题、已知一棵树的双亲表示法如、已知一棵树的双亲表示法如下，其中各兄弟结点是依次出现的，下，其中各兄弟结点是依次出现的，画出该树及其对应的二叉树。画出该树及其对应的二叉树。8 87 76 66 65 54 44 43 33 32 22 21 11 11 10 0O ON NM ML LK KJ JI IH HG GF FE ED DC CB BA Adatadataparentparent1 2 3 4 5 6 7 8 9 10 11 1

57、2 13 14 151 2 3 4 5 6 7 8 9 10 11 12 13 14 15A AB BC CD DE EF FG GH HI IJ JK KL LM MN NO O该树该树A AB BC CD DE EF FG GH HI IJ JK KL LM MN NO O对应的二叉树对应的二叉树、一棵二叉排序树，各结点的值从、一棵二叉排序树，各结点的值从小到大依次为小到大依次为1 18,8,请标出各结点的值。请标出各结点的值。6 61 18 85 57 73 32 24 4 3 3、对下列数据表，写出采用冒泡排、对下列数据表，写出采用冒泡排序的每一趟的结果。序的每一趟的结果。(25,10

58、,20,31,5,44,16,61,100,3)(25,10,20,31,5,44,16,61,100,3) 4 4、求出下图的最小生成树。、求出下图的最小生成树。 68 87 76574535865384 4 4、求出下图的最小生成树。、求出下图的最小生成树。 65435634模拟试卷八模拟试卷八1 1、单项选择题、单项选择题(3 (3 个小题个小题) )2 2、判断题、判断题(5 (5 个小题个小题) )1 2 3 1 2 3 1 2 3 4 5 1 2 3 4 5 三、填空题三、填空题 1.1.在单链表中，在指针在单链表中，在指针P P所指结点的后所指结点的后插入一个结点插入一个结点S

59、S的语句是的语句是: : S-next=P-next;PS-next=P-next;P-next=S-next=S 。 2.2.已知栈的输入序列为已知栈的输入序列为1,2,3,1,2,3,n,n,其其输出序列的第二个元素为输出序列的第二个元素为n n的输出序列的的输出序列的个数是：个数是： n-1n-1 。 3.3.以以4,5,6,7,84,5,6,7,8作为叶子结点的权值作为叶子结点的权值构造哈夫曼树，则其带权路径长度是构造哈夫曼树，则其带权路径长度是: : 6969 。 4. 4.在顺序存储的二叉树中，编号为在顺序存储的二叉树中，编号为i i和和j j的两个结点处在同一层的条件是的两个结点

60、处在同一层的条件是 loglog2 2i=logi=log2 2j j 。 5.5.已知二叉树有已知二叉树有5050个叶子结点，则整个叶子结点，则整个二叉树的总结点数至少是个二叉树的总结点数至少是 9999 。 6.6.已知数组已知数组A1.10,1.9A1.10,1.9中每个元中每个元素占用素占用4 4个单元，现将其按行优先次序个单元，现将其按行优先次序存储在起始地址存储在起始地址10001000的连续内存单元中，的连续内存单元中，则则A5,9A5,9对应的地址为对应的地址为 11061106 。 7. 7.有有n n个球队参加足球联赛按主客场个球队参加足球联赛按主客场制进行比赛，共需进行制进行比赛，共需进行 n(n-1