数据结构试题及答案4.doc

《数据结构》自考复习思考试题 一、 单选题：判断下列各小题叙述的正误。对，在题号前的括号内填入“√ ”；错，在题号前填入“ ×”。（每小题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; elseif(unknown(t—leftChild)=unknown(t—rightChild)) return 1+unknown(t—leftChild)); elsereturn 1+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．设散列表的长度ｍ＝１３；散列函数为Ｈ（Ｋ）＝Ｋ mod m，给定的关键码序列为19，14，23，01，68，20，84，27，55，11，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度和搜索不成功的平均搜索长度。 0 1 2 3 4 5 6 7 8 9 10 11 12 搜索成功时的平均搜索长度为：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网络并对其进行拓扑排序的算法，其中有多个语句缺失。 Void Graph : : TopologicalSort(){ Edge * p , q ; int I , j , k ; For (I=0; In; I++){ NodeTable[I].adj=NULL; 1、 ； } cin j k ; while ( j k){ p=new Edge ( k ) ; p—link=NodeTable[ j ].adj ; 2、 ； Count [ k ] ++ ; Cin j k ; } int top=-1 ; for ( I=0, In ; I++) if (count[ I ]=0 ) { count[ I ]=top ; 3、 } for ( I=0 ; I n ; I++ ) if (top = -1 ) { cout “Network has a cycle” endl ; return ; } else { j= top; 4、 ； cout