华南农业大学期末考试试卷及参考答案2011学年第一学期考试科目：数据结构考试类型：（闭卷）考试时间：120分钟班级学号姓名考试须知：1．答案必须写在“答题卡”上，写在试卷上不得分。2．考试结束时，只回收答题卡，不回收试卷。3.必须在答题卡上正确填写班级、学号、姓名等内容，否则没有考试成绩一、选择题（每小题2分，共20分）1、有n个顶点的有向图最多有()条边。A．nB．n(n—1)Cn(n+1)D.n22、任何一个无向连通图（）最小生成树。A．只有一棵B．有一棵或多棵C．一定有多棵D．可能不存在3、如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有顶点，则该图一定是（）。A.完全图B.连通图C.有回路D.一棵树4、有一个有序表位{1,3,9,12,32,41,45,62,75,77,82,95,99}，当采用二分查找法查找关键字为82的元素时，（）次比较后查找成功。A．1B．2C．4D．85、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为：（1）8447251521（2）1547258421（3）1521258447（4）1521254784，则采用的排序是()。A.选择排序B.冒泡排序C.快速排序D.插入排序6、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的()的两趟排序后的结果。A．选择排序B．冒泡排序C．插入排序D．堆排序7、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知插入结点后A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作()型调整以使其平衡。A．LLB．LRC．RLD．RR8、快速排序算法的时间复杂性为O(nlog2n),但在（）情况下，该算法效率近似为O(n2)。A.初始序列有序或基本有序B.初始序列无序C.经排序后的子序列有序或基本有序D.经排序后的子序列无序9、在以下排序算法中，关键字比较的次数与记录的初始排列次序无关的是（）。A.希尔排序B.冒泡排序C.插入排序D.直接选择排序10、就平均性能而言，目前最好的内排序方法是()排序法。A.冒泡排序B.希尔排序C.堆排序D.快速排序二、是非判断题（每小题1分，共5分）1、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。2、拓扑排序算法把一个无向图中的顶点排成一个有序序列。3、排序的时间开销主要取决与算法执行中的比较次数。4、带权连通无向图不仅可能有多棵生成树，其最小生成树也可能有多棵。5、归并排序辅助存储为O（1）。三、应用题（第3、3+题任选一题，每小题5分，共45分）1、已知无向带权连通图G(V,E)的邻接表如下所示，请画出该图，并使用Prim或Kruskal算法求出该图的最小生成树。其中边结点的3个域为：顶点号边上的权值指针1V1212316418^V2211232522^V331162244^V4411834510^V55222410^2、对长度为8的有序表，给出折半查找的判定树，给出等概率情况下的平均查找长度。3、使用哈希函数H(key)=keymod7，把一个整数值转换成哈希表下标，现将{19,24,10,17,15,38,18,40}依次插入到长度为10的哈希表中，使用线性探测法解决冲突。请构造哈希表并计算查找成功时的平均查找长度ASL。3+、设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=keymod7，表长为10，用开放定址法的二次探测再散列方法Hi=(H(key)+di)mod10(di=12,-12,22,-22,32,…,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。4、关键字序列为{19,14,23,1,68,20,84,27,55,11,10,79}，哈希函数为H(key)=keymod13，采用链地址法处理冲突，给定哈希表的长度为13（0-12），要求画出关键字序列在哈希表中的存储状态，并计算在等概率情况下，查找成功的平均查找长度。5、一组记录关键码为（49，38，65，97，76，13，27，49），使用快速排序，写出以第一个记录为基准的一次划分过程。6、设记录的关键字集合K={23，9，39，5，68，12，62，48，33}，给定的增量序列D={4，2，1}，请写出对K按“SHELL方法”排序各趟排序结束时的结果。7、判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆，只需写出重新调整后的序列，不需用二叉树的形式画出过程）。（1）100，