《数据结构》试题 （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指向原链表的最后一个结点。  五、填空题 下面给出的算法是建立AOV网络并对其进行拓扑排序的算法，其中有多个语句缺失。 void Graph::TopologicalSort ( ) { Edge * p, q; int i, j, k; for ( i = 0; i < n; i++ ) { NodeTable[i].adj = NULL; ( ;   } cin >> j >> k; //输入有向边<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) 请给出对于下面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个空归并段，命名为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树中删去根结点后的结果。 【解答】 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<class Type> void List<Type> :: Inverse ( ) { if ( first == NULL ) return; ListNode<Type> *p = first→link;, *pr = NULL; while ( p != NULL ) { first→link = pr; //逆转first指针 pr = first; first = p; p = p→link; //指针前移 } } 【解答2】 template<class Type> void List<Type> :: Inverse ( ) { ListNode<Type> *p, *head = new ListNode<Type> ( ); 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进栈 栈空