数据结构期末考试题29

《数据结构期末考试题29》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、i）.密封级:装订专业：线姓名：信息技术学院2006-2007学年第二学期期末考试数据结构试卷29（适用班级：）（答题时间:120分钟，满分:100分）（考号:题号第一部分第二部分第三部分第四部分总分核分人得分得分评卷人一、判断题：（共10分，每题1分）1、满二叉树也是完全二叉树。（）2、二叉树可以用0W度W2的有序树来表示。（）3、在只有度为0和度为k的结点的k叉树中，设度为0的结点有nO个，度为k的结点有nk个，则有nO=nk+lo（）4、带权连通图中某一顶点到图中另一顶点的最短路径不一定唯一。（）5、在n个结点的无向图中，若边数少于n-1

2、,则该图必是非连通图。（）6、树的带权路径长度最小的二叉树中必定没有度为1的结点。（）7、哈希表的查找无需进行关键字的比较。（）8、折半查找方法可以用于按值有序的线性链表的查找。（）9、对一个堆按层次遍历，不一定能得到一个有序序列。（）10、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（）得分评卷人二、填空题（共20分，每空2分）1.栈和队列都是线性表。2•下三角形矩阵按行存储的下标计算公式为,三对角矩阵按行存储的计算公式为3.在简单插入排序、希尔排序、简单选择排序、快速排序、堆排序、归并排序和基数排序中，排序

3、是不稳定的有：o4.请举例输出树形结构的两种存储方法、o5.按满二叉数的概念可推广出满K叉数的概念。若対满K叉树的节点逐层编号（从1开始，同层中从左到右），则编号为i的节点的父节点编号是,编号为i的节点的第j个儿子的编号是。6.求解带权连通图最小生成树的Prim算法使用图的作为存储结构。7.在重连通图中每个顶点的度至少为o得分评卷人三、选择题（共20分，每题2分）1.若语句S的执行时间为0（1）,那么下列程序段的时间复杂度为（）。for（i=0;i

4、）D.O（n*i）2.已知一堆栈的进栈序列为：1234,则下列哪个序列为不可能的出栈序列（）oA.1234B.4321C.2143D.41233.深度为5的二叉树至多有（）个结点.A.16B.32C.31D.104.堆(HEAP)是-•种(）。A.二叉树B.线性表C.图D.算法5.若用一个大小为6的数组来实现循环队列，II当前rear和fYonl的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（）。A.1和5B.2和4C.4和2D.5和16.下列哪种排序算法的平均时间复杂度为0（nlogn）（）。

5、A.简单选择排序B.简单插入排序C.冒泡排序D.归并排序7.用冒泡排序（交换排序）算法对（123742192735564410）数据进行从小到大排序。在将最大的数“沉”到最后时，数据的顺序是（）。A.123742192735441056B.123742192735104456C.123719273542441056D.1012192735374244568.下列哪种排序算法更适合于外部排序（）。A.选择排序B.插入排序C.冒泡排序D.归并排序9.对下列二叉树进行后序遍历，其遍历结果为（）oA.gfcdcbaagB.dbcgfcaC.bdccgf

6、aD.dbaccgf10.在待排序的元素基本有序的前提下，效率最高的排序方法是（）。A.简单插入排序B.简单选择排序C.快速排序D.归并排序得分评卷人四、应用题（共30分）1.请对右图有向图（共10分）：（1）画出相应邻接链表（adjacencylist）表示法（链表中,按节点编号大小从小到大向后排）（6分）（2）指岀按深度优先遍历算法在上述表示的基础上进行遍历的两个输岀结果。（4分）2.对于下列二叉树（12分）（1）请画出其对应的中序线索（thread）二叉树。（8分每个线索一分）（2）请将下列用于中序线索二叉树遍历的程序的空白部分填上。（4

7、分每空2分）threaded_pointerinsucc（threaded_pointertree）threaded_pointertemp;temp=tree->right_child;if(!tree->right_thread)while()temp=temp->left_child;returntemp;voidtinorder(threaded_pointertree){threaded_pointertemp=tree;for(;；){temp=insucc(temp);if()break;printf("%3c",temp->da

8、ta);}}1.(8分)选取哈希函数H(k)=kmod11,用线性探测(linearprobing)冲突解决策略(H(k)+i)%ll.试在0-10的