《数据结构》试题(A卷) 单选题[判断下列各个叙述的正误。对,在题号前的括号内填入"y";错,在题号前的括号内填入"x"] (每小题3分,共24分) ()(1)有n个结点的不同的二叉树有n!棵。 ()(2)直接选择排序是一种不稳定的排序方法 ()(3)在2048个互不相同的关键码中选择最小的5个关键码,用堆排序比用锦标赛排序更快 ()(4)当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。 )(5)一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶B树 )(6)在用散列表存储关键码集合时,可以用双散列法寻找下一个空桶。在设计再散列函数时, 要求计算出的值与表的大小m互质。 ()(7)在只有度为0和度为k的结点的k叉树中,设度为0的结点有m个,度为k的结点有mk个, 则有m=nk+1。 )(8)折半搜索只适用于有序表,包括有序的顺序表和有序的链表 、阅读理解題[说明下列递归过程的功能](10分) int unknown( Bin Tre Node *t)i ∥指针t是二叉树的根指针。 if(t==NULL )return -l else if unknown(1-lefiChild)>=unknown( I-rightChild)) return 1+unknown(1-lefi child); else return 1 +unknown( t-rightChild ) 简答题(每小题12分,共36分) 1、设已有12个不等长的初始归并段,各归并段的长度(包含记录数)分别为 RUN1(25),RUN2(13),RUN3(04),RUN4(55),RUNS(30),RUN6(47),RUN7(19) RUN8(80),RUN9(76,RUN10(92,RUNl1(55),RUN2(89) 若采用的是4路平衡归并排序,试画出其最佳归并树,并计算每趟归并时的读记录数。(括号内即为该归 并段包含的记录数) 2、设散列表的长度m=13:散列函数为H(K)= Kmod m,给定的关键码序列为19,14,23,01,68,20,84, 27,55,1],试画出用线性探査法解决冲突时所构造的散列表。并求出在等概率的情况下,这种方法的搜索 成功时的平均搜索长度和搜索不成功时的平均搜索长度 3、画出在一个初始为空的AVL树中依次插入3,1,4,6,9,8,5,7时每一步插入后AVL树的形态。若做了 某种旋转,说明旋转的类型。然后,给出在这棵插入后得到的AVL树中删去根结点后的结果 四、综合算法题 (10分) 设有一个表头指针为h的单链表。试设计一个算法,通过遍历一趟链表,将链表中所有结点的链接方 向逆转,如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点
1 《数据结构》试题 （A 卷） 一、单选题 [判断下列各个叙述的正误。对，在题号前的括号内填入""；错，在题号前的括号内填入"" ] （每小题 3 分，共 24 分） ( ) (1) 有 n 个结点的不同的二叉树有 n！棵。 ( ) (2) 直接选择排序是一种不稳定的排序方法。 ( ) (3) 在 2048 个互不相同的关键码中选择最小的 5 个关键码，用堆排序比用锦标赛排序更快。 ( ) (4) 当 3 阶 B_树中有 255 个关键码时，其最大高度（包括失败结点层）不超过 8。 ( ) (5) 一棵 3 阶 B_树是平衡的 3 路搜索树，反之，一棵平衡的 3 路搜索树是 3 阶 B_树。 ( ) (6) 在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。在设计再散列函数时， 要求计算出的值与表的大小 m 互质。 ( ) (7) 在只有度为 0 和度为 k 的结点的 k 叉树中，设度为 0 的结点有 n0 个，度为 k 的结点有 nk个， 则有 n0 = nk + 1。 ( ) (8) 折半搜索只适用于有序表，包括有序的顺序表和有序的链表。 二、阅读理解题 [说明下列递归过程的功能] (10 分) int unknown ( BinTreNode * t ) { //指针 t 是二叉树的根指针。 if ( t == NULL ) return -1; else if ( unknown ( t→leftChild ) >= unknown ( t→rightChild ) ) return 1 + unknown ( t→leftChild ); else return 1 + unknown ( t→rightChild ); } 三、简答题 (每小题 12 分，共 36 分) 1、设已有 12 个不等长的初始归并段，各归并段的长度（包含记录数）分别为 RUN1 (25), RUN2 (13), RUN3 (04), RUN4 (55), RUN5 (30), RUN6 (47), RUN7 (19), RUN8 (80), RUN9 (76), RUN10 (92), RUN11 (55), RUN12 (89) 若采用的是 4 路平衡归并排序，试画出其最佳归并树，并计算每趟归并时的读记录数。（括号内即为该归 并段包含的记录数） 2、设散列表的长度 m = 13；散列函数为 H (K)＝K mod m，给定的关键码序列为 19, 14, 23, 01, 68, 20, 84, 27, 55, 11，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索 成功时的平均搜索长度和搜索不成功时的平均搜索长度。 3、画出在一个初始为空的 AVL 树中依次插入 3, 1, 4, 6, 9, 8, 5, 7 时每一步插入后 AVL 树的形态。若做了 某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的 AVL 树中删去根结点后的结果。 四、综合算法题 （10 分） 设有一个表头指针为 h 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方 向逆转，如下图所示。要求逆转结果链表的表头指针 h 指向原链表的最后一个结点
_d_ 五、填空题 下面给出的算法是建立AOV网络并对其进行拓扑排序的算法,其中有多个语句缺失。 void Graph: TopologicalSort()& Edge*p, g: int i,j, k; for(i=0;i>k; 输入有向边,k while(&&k)i p=new Edge(k); ∥建立边结点,dest域赋为k link= Node Tablel.adj: ∥链入顶点j的边链表的前端 count(k++; 顶点k入度加 in >>j>> k; for (i=0; i<n: i++) ∥建立入度为零顶点的链栈 ==0){ for (i=0 f cout <<"Network has a cycle"<< endl; return; cout < Node Tablel]. data < endl; U).adj; while(q)i 1k]==0){ (1)请将缺失的语句补上: (10分)
2 五、填空题 下面给出的算法是建立 AOV 网络并对其进行拓扑排序的算法，其中有多个语句缺失。 void Graph::TopologicalSort ( ) { Edge * p, q; int i, j, k; for ( i = 0; i > j >> k; //输入有向边 while ( j && k ) { p = new Edge (k); //建立边结点, dest 域赋为 k p→link = NodeTable[j].adj; //链入顶点 j 的边链表的前端 ; count[k]++; //顶点 k 入度加一 cin >> j >> k; } int top = -1; for ( i = 0; i < n; i++ ) //建立入度为零顶点的链栈 if ( count[i] == 0 ) { count[i] = top; ; } for ( i = 0; i < n; i++ ) if ( top == -1 ) { cout << "Network has a cycle" << endl; return; } else { j = top; ; cout << NodeTable[j].data << endl; q = NodeTable[j].adj; while ( q ) { k = q→dest; if ( -- count[k] == 0 ) { count[k] = top; top = k; } ; } } } (1) 请将缺失的语句补上： （10 分）
(2)请给出对于下面AOⅤ网络,使用上述算法进行拓扑排序的结果,以及在 count数组中建立的链式栈的 变化。(1op是栈顶指针) (10分) (B) E ABCDEF 初始
3 (2) 请给出对于下面 AOV 网络，使用上述算法进行拓扑排序的结果，以及在 count 数组中建立的链式栈的 变化。（top 是栈顶指针） （10 分） top→ A B C D E F 初始
试题解答 、单选题 【解答】(1)×(2)√(3)×(4)√(5)×(6)√(⑦7×(8) 、阅读理解题[说明下列递归过程的功能] 【解答】计算二叉树的高度 简答题 1、【解答】构造最佳归并树 因为(12-1)%(4-1)=2,所以需要补充4-2-1=1个空归并段,命名为RUNO(O)。依此构造4 叉霍夫曼树: R0(00)R3(04)R2(13)R7(19) Rl(25)R5(30)R0237(36)R6(47)R4(55)Rll(55)R9(76)R8(80) Rl2(89)R10(92)RO123567(138) R48911(266) R0-12(585) 此即最佳归并树。第一趟读记录数为36,第二趟读记录数为138+266=404,第三趟读记录数为89+ 92+138+266=585。 2、【解答】 设散列表的长度m=13:散列函数为H(K)= K mod m,给定的关键码序列为19,14,23,01,68,20, 7,55,11,则有 H(19)=6,成功:H(14)=1,成功:H(23)=10,成功 H(01)=1,冲突,=2,成功;H(68)=3,成功:H(20)=7,成功 H(84)=6,冲突,=7,冲突,=8,成功; H(27)=1,冲突,=2,冲突,=3,冲突,=4,成功 H(55)=3,冲突,=4,冲突,=5,成功:h(11)=11,成功。 10 68275 (1)(2)(1)(4)(3)(1)(1)(3) 在等概率的情况下,搜索成功时的平均搜索长度 (1+2+1+4+3+1+1+3+1+1)/10=18/10, 搜索不成功时的平均搜索长度 A slunsucc=(1+9+8+7+6+5+4+3+2+1+3+2+1)/13=52/13=4 3、画出在一个初始为空的AVL树中依次插入3,1,4,6,9,8,5,7时每一步插入后AVL树的形态。若做了 某种旋转,说明旋转的类型。然后,给出在这棵插入后得到的AVL树中删去根结点后的结果。 【解答】
4 试题解答 一、单选题 【解答】 (1) (2) (3) (4) (5) (6) (7) (8) 二、阅读理解题 [说明下列递归过程的功能] 【解答】 计算二叉树的高度。 三、简答题 1、【解答】构造最佳归并树 因为 (12 - 1) % ( 4 - 1 ) = 2，所以需要补充 4 - 2 - 1 = 1 个空归并段，命名为 RUN0 (0)。依此构造 4 叉霍夫曼树： R0 (00) R3 (04) R2 (13) R7 (19) R1 (25) R5 (30) R0237 (36) R6 (47) R4 (55) R11 (55) R9 (76) R8 (80) R12 (89) R10 (92) R0123567 (138) R48911(266) R0-12 (585) 此即最佳归并树。第一趟读记录数为 36，第二趟读记录数为 138 + 266 = 404，第三趟读记录数为 89 + 92 +138 + 266 = 585。 2、【解答】 设散列表的长度 m = 13；散列函数为 H (K)＝K mod m，给定的关键码序列为 19, 14, 23, 01, 68, 20, 84, 27, 55, 11，则有 H(19) = 6，成功； H(14) = 1，成功； H(23) = 10，成功； H(01) = 1，冲突，= 2，成功； H(68) = 3，成功； H(20) = 7，成功； H(84) = 6，冲突，= 7，冲突，= 8，成功； H(27) = 1，冲突，= 2，冲突，= 3，冲突，= 4，成功； H(55) = 3，冲突，= 4，冲突，= 5，成功； h(11) = 11，成功。 0 1 2 3 4 5 6 7 8 9 10 11 12 14 01 68 27 55 19 20 84 23 11 (1) (2) (1) (4) (3) (1) (1) (3) (1) (1) 在等概率的情况下，搜索成功时的平均搜索长度 ASLsucc = ( 1 + 2 + 1 + 4 + 3 + 1 + 1 + 3 + 1 + 1 ) / 10 = 18 / 10， 搜索不成功时的平均搜索长度 ASLunsucc = ( 1 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 3 + 2 + 1 ) / 13 = 52 / 13 = 4。 3、画出在一个初始为空的 AVL 树中依次插入 3, 1, 4, 6, 9, 8, 5, 7 时每一步插入后 AVL 树的形态。若做了 某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的 AVL 树中删去根结点后的结果。 【解答】
左单旋1 6 左单旋 8 6 右单旋 在这个AVL树中删除根结点时有两种方案: 【方案1】在根的左子树中沿右链走到底,用5递补 根结点中原来的6,再删除5所在的结点 【方案2】在根的右子树中沿左链走到底,用7递补 根结点中原来的6,再删除7所在的结点 四、综合算法题 设有一个表头指针为h的单链表。试设计一个算法,通过遍历一趟链表,将链表中所有结点的链接方 向逆转,如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点
5 3 3 3 3 3 3 1 1 4 1 4 1 4 左单旋 1 6 6 6 4 9 9 3 6 6 1 6 3 9 3 9 左单旋 4 9 1 4 8 1 4 8 8 5 6 6 3 9 3 8 右单旋 1 4 8 1 4 7 9 5 7 5 在这个 AVL 树中删除根结点时有两种方案： 【方案 1】在根的左子树中沿右链走到底，用 5 递补 5 根结点中原来的 6，再删除 5 所在的结点。 3 8 1 4 7 9 【方案 2】在根的右子树中沿左链走到底，用 7 递补 7 根结点中原来的 6，再删除 7 所在的结点。 3 8 1 4 9 5 四、综合算法题 设有一个表头指针为 h 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方 向逆转，如下图所示。要求逆转结果链表的表头指针 h 指向原链表的最后一个结点
【解答1】 template void List: Inverse (i f(first== NULL )return; ListNode *p=first-link;, *pr=NULL while(p l= NULl)( fist→lnk ∥)转frt指针 pr=rs;frst=p;p=p→lmnk;∥指针前移 【解答2】 templatevoid List: Inverse (i ListNode *p, *head=new ListNode(; while(first I=NULL)t p=first fist→lnk; ∥摘下frst链头结点 P→link=head→link;head→link=p;/插入head链前端 first =head-link; delete head ∥重置frst 五、填空题 【解答】 (1)请将缺失的语句补上 counta=0 Node Tablel] adj=p top= counttopl q=q→lnk 2)对于下面AOⅤ网络,使用上述算法进行拓扑排序的结果,以及在coun数组中建立的链式栈的变 化。(1op是栈顶指针) 排序结果是 ABCDEF,链式栈coum的变化如下 B (E BL1p→ E 初始输出A输出 输出C输出D输出E输出 B进栈C进栈D进栈E进栈F进栈栈空
6 【解答 1】 template void List :: Inverse ( ) { if ( first == NULL ) return; ListNode *p = first→link;, *pr = NULL; while ( p != NULL ) { first→link = pr; //逆转 first 指针 pr = first; first = p; p = p→link; //指针前移 } } 【解答 2】 template void List :: Inverse ( ) { ListNode *p, *head = new ListNode ( ); while ( first != NULL ) { p = first; first = first→link; //摘下 first 链头结点 p→link = head→link; head→link = p;//插入 head 链前端 } first = head→link; delete head; //重置 first } 五、填空题 【解答】 (1) 请将缺失的语句补上 count[i] = 0 NodeTable[j].adj = p top = i top = count[top] q = q→link (2) 对于下面 AOV 网络，使用上述算法进行拓扑排序的结果，以及在 count 数组中建立的链式栈的变 化。（top 是栈顶指针） 排序结果是 A B C D E F，链式栈 count 的变化如下： tp→ tp→A -1 B 1 tp→ -1 C 2 1 tp→ -1 D 2 2 1 tp→ -1 E 2 2 1 1 tp→ -1 F 2 1 1 1 1 tp→ -1 初始 输出 A 输出 B 输出 C 输出 D 输出 E 输出 F B 进栈 C 进栈 D 进栈 E 进栈 F 进栈 栈空