2008.7数据结构期末考试试卷(A卷)
名著简介-银杏酒店管理学院
华南农业大学期末考试试卷（ A卷）
2007学年第2学期
考试科目：数据结构
考试类型：（闭卷） 考试时间： 120 分钟
班级
学号 姓名
考试须知：
1．
答案必须写在“答题卡”上，写在试卷上不得分。
2． 考试结束时，只回收答题卡，不回收试卷。
3. 必须在答题卡上正确填写班级、学号、姓名等内容，否则没有考试成绩。
4.
计算机专业包括计算机科学与技术、软件工程，网络工程。
一、选择题（每小题2分，共20分）
1、链表不具备的特点是？（ ）
A．可随机访问任一节点。
B．插入删除不需要移动元素。
C．不必事先估计存储空间。
D．所需空间与其长度成正比。
2、一个栈的输入序列为a，b，c，d，e，则下列序列中不可能是栈的输出序列的是
（
）。
A. edcba B. decba C. dceab
D. abcde
3、串的长度是指（ ）。
A．串中所含不同字母的个数
B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
4、有n个顶点的有向图最多有( )条边。
A．n B．n(n—1)
C n(n+1) D. n
2
5、就平均性能而言，目前最好的内排序方法是(
)。
A. 冒泡排序 B. 希尔排序 C. 堆排序 D. 快速排序
6、一个队列的入队序列是1，2，3，4，则队列的输出序列是（ ）。
A.
4，3，2，1 B. 1，2，3，4 C.1，4，3，2 D.
3，2，1，4
7、 若循环队列用数组A[0,m-1]存放元素，其头尾指针分别为front
和rear，则当前
队列的长度是（ ）。
A. (rear-
front+m)%m B. rear-front+1
C.
rear-front-1 D. (rear-front)%m
8、以下哪个数据结构是非线性数据结构（）。
A. 树 B. 字符串
C. 队列 D. 栈
9、一维数组和线性表的区别是( )。
A.
前者长度固定，后者长度可变 B. 后者长度固定，前者长度可变
C.
两者长度均固定 D. 两者长度都可变
10、线性表（
a1,a2,„,an）以链式存储时，访问第i位置元素的时间复杂度为（ ）。
A．O（i） B．O（1） C．O（n）
D．O（i-1）
二、是非判断题（每小题1分，共10分）
1、
排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
2、
线性表的每一个结点都有一个前驱和一个后继。
3、 任意一棵树均可转换成二叉树，再进行存储。
4、 在无向图中，边的条数是结点度数之和。
5、
顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
6、
队列和栈都是运算受限的线性表，只允许在表的两端进行运算。
7、
顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。
8、
排序的时间开销主要取决于算法执行中的比较次数。
9、
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。
10、归并排序辅助存储为O（1）。
三、应用题（每题10分，共70分）
1、设一棵二叉树的先序、中序遍历序列分别为：
先序遍历序列： A B D F C E
G H 中序遍历序列： B F D A G E H C
（1）画出这棵二叉树。
（2）写出这颗二叉树的后序遍历序列。
2、用给出的一组字符A，B，C，D，E的权值是
{3，4，5，6，8}，建立一棵哈夫
曼树，并给出每个字符的哈夫曼编码。
3、输入一个
正整数序列{40，28，6，72，100，3，54，1，80，91，38}，建立一颗
二叉排序
树。
4、对长度为8的有序表，给出折半查找的判定树，给出等概率情况下的平均查找长
度。
5、已知关键字序列为：{75,33,52,41,12,88,66,27},哈希表长为10，哈
希函数
H(key)=key % 7，解决冲突用线性探测法，构造哈希表并给出找每个关键字的比较
次数及哈希表等概率条件下AVL（平均查找长度）值。
6、一组记录关键码为（49，38
，65，97，76，13，27，49），使用快速排序，写出
以第一个记录为基准的一次划分过程。
7、判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整
为堆）。
（1）100，85，98，77，80，60，82，40，20，10，66
（2）100，98，85，82，80，77，66，60，40，20，10
（3）100，85，40，77，80，60，66，98，82，10，20
（4）10，20，40，60，66，77，80， 82，85，98，100
华南农业大学期末考试答题卡（A卷）
2007学年第2学期 考试科目： 数据结构
考试类型：（闭卷） 考试时间：
120 分钟
班级 学号 姓名
题号
得分
评阅人
一
二
三
四
总分
一、单项选择题（每小题2分，共20分）
1
6
A
B
2
7
C
A
3
8
B
A
4
9
B
A
5
10
D
C
二、是非判断题（对的打“√”，错的打“×”，每小题1分，
共10分）
1
6
×
×
2
7
×
×
3
8
√
×
4
9
×
√
5
10
×
×
三、应用题（非计算机专业每题10分，计算机专业第一题6
分，2-7题每题9分）
1、
A
B
C
D E
F G H
后序序列：FDBGHECA
11
2
6
2、
A: 100 B:101 C:00 D:01
15
E:11
3、
C D
3 4
5 6
7
8
E
A B
40
28
72
6 38 54 100
3 80
1
4、
91
0
1
2 4
3
5
6
7
AVL=(1+2*2+4*3+1*4)8=218=2.62
5、
计算函数值
key
75 33
5
52
3
41
6
12
5
88
4
66
3
27
6 Key%7 5
(1)哈希表（4分，每对1个0.5分）
index
0 1
2
3
52
4
88
5
75
6
33
7
41
8
12
9
66 key 27
(2)比较次数（3分）
key
Cmp
75
1
33
2
52
1
41
2
12
4
88
1
66
7
27
5
AVL=(1+2+1+2+4+1+7+5)8=238
6、
（1）27，38，65，97，76，13， 49
（2）27，38，
97，76，13，65，49
（3）27，38，13，97，76， 65，49
（4）27，38，13， 76，97，65，49
（5）27，38，13，49，76，97，65，49
7、(1)是大堆； (2)是大堆；（4）是小堆；
(3)不是堆，调成大堆
100，98，66，85，80，60，40，77，82，10，20
四、算法设计题（计算机专业做，10分）