11、在一棵二叉排序树上按（ ）遍历得到的结点序列是一个有序序列。

A.层次     B. 先序      C. 中序      D.后序

12 、在线性表的下列存储结构中，读取元素花费时间最少的是（ ）。

A. 顺序表    B. 单链表    C. 双链表    D. 循环链表

13 、算法是（ ）。

A. 计算机程序            B. 解决问题的计算方法

C. 排序算法              D. 解决问题的有限运算序列

14 、关于图的存储结构，（） 是错误的。

A ． 使用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的项，点数有关，与边数无关。

B ．邻接表只用于有向图的存储，邻接矩阵适用于有向图和无向图。

C ． 若一个有向图的邻接矩阵的对角线以下的元素为 0，則该图的拓扑序列必定存在。

D ．存储无向因的邻接矩阵是对称的，故只需存储邻接矩阵的下（或上）三角部分。

15 、无向图 G=(V,E),其中 V= {a,b,c,d,e,f} ，E={ (a,b), (a,e), (a,c). (b,e), (c,f), (f,d).(e,d) } 。对该图进行深度优先遍历,不能得到的序列是（）。

A. acfdeb                             B. aebdfc

C. aedfcb                            D. abecdf

16 、判断有向因中是否存在回路，除可以利用拓扑排序外，还可以利用（）。

A. 求关键路径的方法

B. 深度优先遍历算法

C. 求最短路径的 Dijkstra 算法

D. 广度优先遍历笋法

17 、已知一个有序表(13 ，18 ，24 ，35 ，47 ，50 ，62 ，83 ，90 ，115 ，134) ，当二分查找值为 90 的元素时，查找成功的比较次数为（）。

A. 1                         B. 2                               C. 4                           D. 6

18 、排序算法的稳定性是指（）。

A ．经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变

B ．经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变

C ．排序算法的性能与被排序元素个数关系不大

D ．排序算法的性能与被排序元素的个数关系密切

19 、以下排序算法中，稳定的是（）。

A ． 快速排序           B ． 堆排序

C ． 直接插入排序        D ． 简单选择排序

20 、用某种排序方法对线性表{25 ，84 ，21 ，47.15 ，27 ，68 ，35 ，20}进行排序时，元素序列的变化情况如下：

1) 25 ， 84 ， 21 ， 47 ， 15 ， 27 ， 68 ， 35 ， 20

2) 20 ， 15 ， 21 ， 25 ， 47 ， 27 ， 68 ， 35 ， 84

3) 15 ， 20 ， 21 ， 25 ， 35 ， 27 ， 47 ， 68 ， 84

4) 15 ， 20 ， 21 ， 25 ， 27 ， 35 ， 47 ， 68 ， 84

则所采用的排序方法是（）。

A ．选择排序           B ．插入排序

C ．2 路归并排序         D ．快速排序

二、 填空题（每空 2 分，共 10 分）

1 、现有栈 s ，经过以下栈运算后，x 的值是 _____。

InitStack(s);

Push(s,g);

Push(s,o ）;

Push(s,o ）;

Pop(s,x);

Pop(s,x);

GetTop(s,x);

2 、数据结构的四种基本类型中，________的元素是多对多关系。 

3 、假设一棵二叉树的结点数为 110 ，则它的最小高度为 _____。

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

k=0;

for（i=0；i<n <> <> <> ；i++）{ <> <> <>

k=k+i;

}

5 、在无向图G 的邻接矩阵A中，若A[i][j]等于1 ，则 A[j][i]等于 ____。

三、 程序分析题（共 30 分）

1 、循环分析题：

sort（ r, n）

{

for (i=2; i<=n;<> i++)

{ x=r(i); r(0)=x; j=i- 1;

while( x<r(j) ) <> <>

{

r(j+1)=r(j);

j=j- 1;

}

r(j+1)=x;

}

}

（1） 这是什么类型的排序算法，该排序算法稳定吗？

（2） 设置 r(0)的作用是什么？

（3） 若将 while 语句中判断条件改为 x<=r(j),该算法将会有什么变化？

（4） 若将 while 语句中判断条件改为 x<=r(j),该算法是否还能正确工作？

2 、排序分析题：

下面给出一个排序算法，其中 n 是数据类型为 Type的数组A[ ]中元素总数。

void unknown (Type a[ ], int n)

{

int d = 1, j;

while ( d <n /3 ) d = 3*d+1;

while ( d > 0 )

{

for ( int i = d; i <n; i++)

{

Type temp = a [i];

j = i;

while ( j >= d && a[j-d] > temp )

{

a [j] = a [j-d]; j -= d; }

a [j] = temp;

}

d /= 3;

}

}

(1) 阅读此算法，说明它的功能；

(2) 对于下面给出的整数数组，追踪第一趟 while ( d > 0 ) 内的每次 for 循 环结 束时数组中数据的变化。（为清楚起见，本次循环未涉及的不移动的数据可以不写出，每行仅写出一个 for 循环的变化）；

步	a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	移动次数
	77	44	99	66	33	55	88	22	44	11
1
2
...

(3) 以上各次循环的数据移动次数分别是多少。

3、队列题目

写出下列程序段的输出结果（队列中的元素类型为 char）

Void main()

{

Queue Q;InitQueue(Q);/初始化队列

Char x=“E”;y=“C”;

InQueue(Q, “H”);

InQueue(Q, “R”);

InQueue(Q, y);

OutQueue(Q, x); InQueue(Q, x);

OutQueue(Q,x); InQueue(Q,”A”);

While(!QEmpty(Q))

{

OutQueue(Q,y);

print(y);

};

print(x);

}

输出为：

四、 编程题（共 20 分）

1、结构体编程

已知长度为 n 的的线性表 A 采用顺序存储结构。

（1）写出线性表 A 的结构体

（2）设计一个时间复杂度为 o(n)，空间复杂度为 o(1)的算法，将值为 x 的元素全部移动到 A 的后半部分。

2、查找算法编程

存在一个二叉排序树，给定一个 value 值，若查找 value 值，就返回比 value 值大的所有值中最小的值，若 value 值最大就返回空。

（1）用 C 语言写出二叉排序树的结构体

（2）说出上述算法思想并用 C 语言编程。

五、 计算题（共 50 分）

1、设哈希表 H 表长 m 为 13，哈希函数为 H(k)=k MOD m，给定的关键值序列为

{9，17，23，19，67，37，83，35，55，77}。

(1)求出用线性探测法解决冲突时所构造的哈希表；

(2) 求出在等概率的情况下查找成功的平均查找长度 ASL。

2、已知图 G 中的顶点分别为 A、B、C、D、E 和 F，其邻接矩阵如下所示：

（1） 画出图 G，并求从顶点 A 出发的广度优先搜索序列；

（2） 根据普里姆算法，求图 G 从顶点 A 出发的最小生成树，要求表示出其每一步生成过程（用图的方式）。

3、假设用于通讯的电文仅由 8 个字母 A、B、C、D、E、F、G、H 组成，字母在电文中出现的频率分别为：0.10，0.22，0.06，0.02，0.03，0.32，0.19，0.07。

（1）设计一棵哈夫曼树，并给出这 8 个字母的哈夫曼编码；

（2）计算其带权路径长度 WPL。