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

华南农业大学期末考试试卷（A卷）2007年7月 考试科目：数据结构考试类型：（闭卷）考试时间：120 分钟班级 学号 姓名 考试须知：1 答案必须写在“答题卡”上，写在试卷上不得分。2 考试结束时，只回收答题卡，不回收试卷。3. 必须在答题卡上正确填写班级、学号、姓名等内容，否则没有考试成绩。一、选择题（每小题2分，共20分）1.链表不具有的特点是（A ）A可以随机访问任意一个元素B插入删除时不需要移动元素C不必事先估计存储空间 D所需空间与线性表长度成正比2.在有n个叶子结点的哈夫曼树中，结点总数为（D）An B.2n C.2n1 D.2n13.就平均时间而言，下列排序（B）最好。A直接插入 B。快速排序 C.堆排序 D.归并排序4.由3个节点组成的二叉树深度可能为（B）A.1 B.2 C.4 D.55.设线性表的每一个元素占8个存储单元，第一个单元的存储地址为100，则第6个元素占用的最后一个存储单元的地址为（C ）A.139 B.140 C.147 D.1486. 假设8行10列二维数组a1.8，1.10分别以行序为主序和以列序为主序存储时，其首地址相同，则行序为主序的a3，5和以列序为主序（ d ）的地址相同。A.a5,3 B. a8,3 C. a1,4 D. 都不对7. 设一个栈的输入序列是DACB，则下列序列中，是栈的合法输出序列的是（A）。A.DCBA B. ACDB C. ABCD D. CBDA8.直接插入排序的最好情况下，时间复杂度为（ A ）。AO(n) B. O(logn) C. O(nlogn) D. O(n的平方)9. 若循环队列用数组A0,n-1存放元素，其头尾指针分别为front 和rear，则当前队列的长度是（ ）。A. (rear-front+n)%n B. rear-front+1 C. rear-front-1 D. (rear-front)%n10. 对一组数据（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.判断下列关键字序列是否为堆（大根堆或小根堆），若不是，则将其调整为堆：（1）（100, 86, 48, 73, 35, 39, 42, 57, 66, 21）；（2）（12, 70, 33, 65, 24, 56, 48, 92, 86, 33）；（3）（103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 6, 20）；（4）（5, 56, 20, 23, 40, 38, 29, 61, 35, 76, 28, 100）。5. 已知一组记录的关键字为（45, 23, 30, 38, 9, 77, 12, 96, 23, 76, 5），要求：（1）用直接插入排序方法进行排序，写出每一趟排序后的结果；（2）用冒泡法排序，写出第一趟冒泡过程和各趟冒泡排序后的结果；（3）用希尔排序方法进行排序，画出增量d分别为4, 2, 1时，每趟排序后的结果；6.一组记录关键码为（26，5，37，1，62，11，59，15），使用快速排序，写出以第一个记录为基准的一次划分过程。7. 使用哈希函数H(key)=key mod 7，把一个整数值转换成哈希表下标，现将19,24, 10,17,15,38,18,40依次插入到长度为10的哈希表中，使用线性探测法解决冲突。请构造哈希表并计算查找成功时的平均查找长度ASL。四、算法设计题（计算机专业做，两题选一题，10分）1.请分别以顺序表和带头结点的单链表作为存储结构，编写算法实现线性表的逆置。要求：（1）用原表空间将A=(a1, a2, , am-1, am)逆置为A=(am, am-1, , a2, a1)；（2）另辟空间将A=(a1, a2, ,