一、单选题：判断下列各小题叙述的正误。对，在题号前的括号内填入“√”；错，在题号前填入“×”。（每小题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分）
intunknown(BinTreNode*t){
//指针T是二叉树的根指针。
if(t==NULL)return-1;
elseif(unknown(t—leftChild)>=unknown(t—rightChild))
return1+unknown(t—leftChild));
elsereturn1+unkuown(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．设散列表的长度ｍ＝１３；散列函数为Ｈ（Ｋ）＝Ｋmodm，给定的关键码序列为19，14，23，01，68，20，84，27，55，11，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度和搜索不成功的平均搜索长度。
0123456789101112
搜索成功时的平均搜索长度为：ASLsucc=
搜索不成功时的平均搜索长度为：ASLunsucc=
3．画出在一个初始为空的AVL树中依次插入3，1，4，6，9，8，5，7时每一步插入后AVL树的形态。若做了某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的AVL树中删去根结点后的结果。
四、（10分）
以知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入生成的一棵二叉搜索树。
五、综合算法题（10）
设有一个表头为first的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。
六、程序填空题
下面给出的算法是建立AOV网络并对其进行拓扑排序的算法，其中有多个语句缺失。
VoidGraph::TopologicalSort(){
Edge*p,q;intI,j,k;
For(I=0;I NodeTable[I].adj=NULL; 1、； cin>>j>>k; while(j&&k){ p=newEdge(k); p—link=NodeTable[j].adj; 2、； Count[k]++; Cin>>j>>k; inttop=-1; for(I=0,I if(count[I]=0){ count[I]=top; 3、 for(I=0;I if(top=-1) {cout<<“Networkhasacycle”< else{ j=top;4、； cout< q=NodeTable[j].adj; while(q){ k=q—dest; if(----count[k]==0 count[k]=top; top=k; 5、； 1、 2、 4、 5、 （2）请给出对于下面AOV网络，使用上述算法进行拓扑排序的结果，以及在count数据库中建立的链式栈的变化。（top是栈顶指针）（5分） B C A D E F 初始 卷代号：1010 中央广播电视大学1999—2000学年度第二学期 “开放教育（本科）期末考试计算机科学与技术专业数据结构 试题答案及评分标准 （供参考） 一、单选题 解答（1）×（2）√（3）×（4）√（5）×（6）√（7）×（8）× 二、阅读理解题 解答：计算二叉树的高度（深度）。 三、简答题 1、解答：构造最佳归并树 因为（12-1）/（4-1）=2，所以需要补充4-2-1=1个空归并段，命名为RUN（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)R12(92)R0123567(138)R48911(266) R0-12(585) 此即最佳归并树。第一趟读记录数为36，第二趟读记录数为138+266=404，第三趟读记录书数为89+92+138+266=585。 2、解答 设散列表的长度m=13；散列函数为H（K）=Kmodm，给定的关键码序列为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）=16，冲突，=2，冲突，=3，冲突，=4，成功； H（55）=3，冲突，=4，冲突，=5，成功；H（11）=11，成功； 14 01 68 27 5 19 20 84 23 11 （1）（2）（1）（4）（3）（1）（1）（3）（1）（1） 在等概率的情况下，搜索成功时的平均搜索长度： ASLSUCC=18/10=1.8 搜索不成功时的平均搜索长度： ASLSUCC=52/13=4 3、画出在一个初始为空的AVL树中依次插入3，1，4，6，9，8，5，7时每一步插入后AVL树的形态。若做了某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的AVL树中删去根结点的结果。 解答： 333333 6649 9 366 16左单旋3939 49148148 66 3938 148右单旋1479 575 这个AVL树中删除根结点时有两种方案： 方案1：在根的左子树中沿右链走到底，用5递补根结点中原来的6，再删除5所在的结点。 38 1479 方案2：在根的左子树中沿左链走到底，用7递补根结点中原来的6，再删除7所在的结点。 7 149 四、（10） 得到的二叉树如下： 46 2578 123762 2970 五、综合算法题 设有一个表头指针为first的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。 解答1 template if(first==NULL)return; ListNode While(p!=NULL){ First→link=pr; Pr=first;first=p;p=p→link; first->link=pr; 解答2 ListNode While(first!=NULL){ P=first;first=first→link; p→link=head→link;head→link=p; first=head→link;deletehead; 解答 1count[I]=0 2NodeTable[j].adj=p 3top=I (2)对于下面AOV网络，使用上述算法进行拓扑排序的结果，以及在count数组中建立的链式栈的变化。（top是栈顶指针）（5分）