考试中心填写：

**大学课程考试试卷

课程名称：数据结构与算法分析；试卷编号：；考试时间：120分钟

题号	一	二	三	四	五	六	七	八	九	十	总分
应得分											100
实得分
评卷人											评分：

一、判断题（对的打√，错的打×，10分，每题2分）

1、算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是空间复杂性和时间复杂性。..........………….……..( )

2、每种数据结构都具备三个基本运算：插入、删除和查找。..........………….……..( )

3、设输入序列是12345，通过一个栈可以得到输出序列12345。.......………….……..( )

4、空串即为空格串。......………….……..( )

5、一个广义表的表头总是一个广义表。....………….……..( )

二、选择题（从每题给出的答案中选择一个正确答案，15分，每题3分）

1、当一棵二叉树的前序序列和中序序列分别是 HGEDBFCA 和 EGBDHFAC 时，其后序序列必是（）。

(A)BDEAGFHC (B)EBDGACFH (C)HGFEDCBA (D) HFGDEABC

2、堆是一种特殊的数据结构，( )是一个堆。

(A)19,75,34,26,97,56 (B)97,26,34,75,19,56

3、外排序是指( )。

(A) 用机器指令直接对硬盘中需排序数据排序

(B) 把需排序数据，用其他大容量机器排序\

(D) 对外存中大于内存允许空间的需排序的数据，通过多次内外存间的交换实现排序。

4、已知一个线性表(38，25，74，63，52，48)，采用的散列函数为H(Key)=Key mod 7，将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为( )。

(A) 1.5 (B) 1.7 (C) 2.0 (D) 2.3

5、关键路径是指AOE(Activity On Edge)网中（）。

(A) 最长的回路 (B) 最短的回路

(D) 从源点到汇点(结束顶点)的最短路径

三、填空题（20分，每题2分）

1、在线性结构中，开始结点有个前驱结点，其余各个结点有个前驱结点；终端结点有个后继结点，其余每个结点有个后继结点。

2、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。

3、下面程序段的时间复杂度是。

i=0; s=0;

while(s<n){

i++; s+=i

}

4、在图形结构中，每个结点的前驱结点和后继结点数为。

5、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2,p3,…,pn,若p1=n，则pi= 。

6、循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中元素的个数是。

7、向栈中推入元素的操作是。

8、在一个含有e条边的图中，设所有顶点的度数之和为d，则d和e的关系是：。。

9、对一棵二叉排序树进行中序遍历，得到的结点序列是一个。

10、深度为5的二叉树至多有个结点。

四、简答题（每题5分，共10分）

1. 简述数据结构的逻辑结构和存储结构的区别和联系。它们如何影响算法的设计与实现？

2. 如何只想得到一个序列中第k个最小元素之前的部分排序序列，那么最好应采用何种排序方法？为什么？

五、应用题（给出下面各题的结果，每题5分，共25分）

1. 证明：在二叉树的第i层上至多有2i-1个结点(i>=1)。（5分）

2. 将下面的森林（图5-1）转换成一棵二叉树，并写出森林的两种遍历序列。（10分）

图5-1 森林

3. 已知一组记录为（73,6,57,88,60,42,83,72,48,85），分别写出下列各种排序方法进行升序排序时的变化过程：（10分）

a) 采用堆排序方法进行排序，写出前三趟的排序结果。（写出的每一趟结果要求未排序的记录构成一个堆）；

b) 采用shell 排序进行排序，增量序列分别为4，2，1，每一趟的结果。

六、算法设计题（每题10分，共20分）

1. 编写一个递归函数计算二叉树的高度。

2. 已知一个向量中的元素按元素值非递减有序排列，编写一个程序删除向量中多余的值相同的元素。