数据结构期末考试试卷A.pdfVIP

华南农业大学期末考试试卷（A 卷） 2007 年 7 月 考试科目：数据结构 考试类型：（闭卷） 考试时间： 120 分钟 班级 学号 姓名 考试须知： 1．答案必须写在“答题卡”上，写在试卷上不得分。 2．考试结束时，只回收答题卡，不回收试卷。 3. 必须在答题卡上正确填写班级、学号、姓名等内容，否则没有考试成绩。 一、选择题（每小题 2 分，共 20 分） 1.链表不具有的特点是（A ） A．可以随机访问任意一个元素 B．插入删除时不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性表长度成正比 2.在有 n 个叶子结点的哈夫曼树中，结点总数为（D） A．n n n＋1 D.2n－1 3.就平均时间而言，下列排序（B）最好。 A．直接插入 B。快速排序 4.由 3 个节点组成的二叉树深度可能为（B） A.1 B.2 C.4 5.设线性表的每一个元素占 8 个存储单元，第一个单元的存储地址为 100，则第 6 个元素占用的最后一个 存储单元的地址为（C ） A.139 B.140 C.147 6. 假设 8 行 10 列二维数组 a[1..8，1..10]分别以行序为主序和以列序为主序存储时，其首地址相同，则 行序为主序的 a[3，5]和以列序为主序（ d ）的地址相同。 A.a[5,3] B. a[8,3] C. a[1,4] D. 都不对 7. 设一个栈的输入序列是 DACB，则下列序列中，是栈的合法输出序列的是（A）。 B. ACDB C. ABCD D. CBDA 8.直接插入排序的最好情况下，时间复杂度为（ A ）。 A．O(n) B. O(logn) C. O(nlogn) D. O(n 的平方) 9. 若循环队列用数组 A[0,n-1]存放元素，其头尾指针分别为 front 和 rear，则当前队列的长度是 （ ）。 A. (rear-front+n)%n B. rear-front+1 C. rear-front-1 D. (rear-front)%n 10. 对一组数据 （85，49，27，16，19）排序，数据的排列次序在排序的过程中的变化为： （1）85 49 27 16 19 （2）16 49 27 85 19 （3）16 19 27 85 49 （4） 16 19 27 49 85 则采用的排序是 ( b )。 A. 选择排序 B. 冒泡排序 C. 快速排序 D. 插入排序 二、是非判断题（每小题 1 分，共 10 分） 1.对于任意一个图，从它的某个点进行一次先深或先广有哪些信誉好的足球投注网站可以访问到该图的每一个顶点。错 2.一个带权的无向连通图的最小生成树的权值之和是惟一的。对 3.索引文件可以随机访问，也可以顺序访问。错 4.带头节点的单循环链表中，任意节点的后继结点的指针域均不空。对 ‘ 5.中根遍历二元查找树所得序列是有序序列。对 6.栈和队列均为操作有限的线性表。对 7.对于无向图的生成树，从同一顶点出发所得的生成树相同。错 8.线性表的顺序存储表示优于链式存储方式。错 9. 带权连通无向图可能有多棵生成树，但最小生成树一定只有一棵。错 10. 给定一棵树，可以找到唯一的一棵二叉树与之对应。 对 三、应用题（非计算机专业每题 10 分，计算机专业第一题 6 分，2-7 题每题 9 分） 1.已知二叉树的中序遍历和后序遍历结果分别为 BDCEAFHG 和 DECBHGFA，试画出这棵二叉树，并写出该二 叉树前序遍历结果。 2.假设某系统用于通信的电文仅由字符集 C={a, b, c, d, e, f, g, h}中的8 个字母组成，这 8 个字母在电文中出 W 现的频率分别为 ={7, 19, 2, 6, 32, 3, 21, 10}。要求： （1）画出由这些结点所构成的哈夫曼树； （2）计算此树的带权路径长度WPL ； （3）给出这8 个字母的哈夫曼编码。 3.对图所示的带权连通图 G16，从 V3 出发，利用 Prim 算法构造最小生成树 （给出步骤），并求最小代价 （权 值）。 4