2008.7数据结构期末考试试卷(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. n2

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 分钟

班级               学号              姓名               

1、

              A

         B           C

            D      E

         F       G     H

后序序列：FDBGHECA

2、                                  A: 100 B:101 C:00 D:01 E:11

3、

4、

                     AVL=(1+2*2+4*3+1*4)/8=21/8=2.62 

5、

 计算函数值

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分）