数据结构1
1、 单项选择题（每小题2分，共20分）
在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。
1.栈和队列都是（ C ）。
A.顺序存储的线性结构
B.链式存储的线性结构
C.限制存储点的线性结构
D.限制存储点的非线性结构
2.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p 之间插入s结点，则执行（ C ）。
A.s->next=p->next; p->next=s;
B.p->next=s->next; s-
>next=p;
C.q->next=s;s->next=p;
D.p->next=s; s->next=q;
3.稀疏矩阵一般的压缩存储方法有两种，即（ C ）。
A．二维数组和三维数组 B三元组和散列
C．三元组和十字链表 D散列和十字链表
4.对于下面的二叉树，按后序遍历所得的结点序列为（ D ）。
A． 1234567
B． 1245367
C． 4251637
D． 452673l
5.深度为5的二叉树至多有（ C ）个结点。
A. 16 B .32 C. 31 D.10
6.Huffman树的WPL 是指（ C ）。
A．除根以外所有结点的权值之和 B．所有结点权值之和
C．各叶子结点的带权路径长度之和 D．根结点的值
7.下列排序方法中，（ D ）的比较次数与记录的初始排列状态无关？A．直接插入排序 B．起泡排序 C．快速排序 D．直接选择排序8.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是( B)
A. 9 B．11 C．12 D．不确定
9.设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是( C )。
A.1,2,3,4,5
B.1,4,3,2,5
C.4，1,3,2,5
D.1,3,2,5,4
10.对下图，不能得到的拓扑序列是(D)
A.l,2,3,4,5,6,7,8
B.1,5,2,6,3,7,4,8
C.1,2,5,6,3,4,7,8
D.1,2,3,4,8,7,6,5
2、 填空题（每空1分，共20分）
11.数据元素之间的 关系 称为结构，通常有如下四种基本结构：集合结构、
线性 结构、 树形 结构和 图形 结构。
12.具有n个结点的无向图中，有 n(n-1)/2 条边的无向图称为完全图；对于具有n个结点有向图，有 n(n-1) 条弧的有向图称为有向完全图。
13.循环队列用数组A[0..m-1]存放其元素值。已知其头尾指针分别是front和rear，则当前队列中的元素个数是 (rear-front+m)%m ，判断队空的条件是 front==rear 。
14.在二叉树的第i层上至多有2i-1 结点。
15.设有一个二维数组A[0..6,0..8]，A[0][0]存放位置为500，每个元素占2个字节，以行序为主序列，则A[4][5]在位置 582 。
16.图的遍历的两种搜索方法分别是深度优先搜索 和 广度优先搜索 。
17.广义表(a,(a,b),d,e,((i,j),k))的长度是 5 ，表头是 a ，表尾是((a,b),d,e,((i,j),k))。
18.查找算法中的两种最基本的操作是比较和 移动 。
19.具有n条记录的顺序表中，在查找概率相等的情况下顺序查找平均查找长度为 (n+1)/2 。
20．算法质量的度量标准有两个：时间复杂度和空间复杂度。
三、设计题（共40分）
21.假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为
DCEGBFHKJIA请画出该二叉树，并给出先序序列。（6分）
二叉树为 (4’) 先序序列为：ABCDGEIHFJK (2’)
22.已知某系统在通讯联络中只可能出现5种字符{a,b,c,d,e}，其概
率分别为0.10，0.22，0.27，0.15，0.26，试画出赫夫曼树并设计赫夫曼编码。（8分）
w={10,22,27,15,26} 赫夫曼树为（4’）
赫夫曼编码为：a: 010 b: 00 c: 11 d: 011 e:
10（4’）
23.已知如下所示长度为6的表（36，48，22，58，46，18），按表中
元素的顺序插入一棵初始为空的二叉排序树，并求在等概率的情况下查找成功的平均查找长度。（8分）
……每棵树1分，共6分
ASL=(1*1+2*2+3*3)/6=7/3……2分
24.已知一组关键字（68，32，56，6，38，49，43，9，55，37，35，12）请按哈希函数H（key）=keyMOD13和线性探测处理冲突构造哈希表(表长为13)。（8分）
H（68）=68MOD13=3
H（32）=32MOD13=6
H（56）=56MOD13=4
H（6） = 6MOD13=6 冲突+1
H（38）=38MOD13=12
H（49）=49MOD13=10
H（43）=43MOD13=4 冲突+1
H（9） = 9MOD13=9
H（55）=55MOD13=3 冲突+5
H（37）=37MOD13=11
H（35）=35MOD13=9 冲突+4
H（12）=12MOD13=12 冲突+2
0 1 2 3 4 5 6 7 8 9 10 11 12
3512685643326559493738 25.已知一个待排序的关键字序列为{56，36，22，86，72，10，28，48}，请写出快速排序每一趟排序的结果。（10分）
第1趟排序结果：48,36,22,28,10,56,72,86
第2趟排序结果：10,36,22,28,48,56,72,86
第3趟排序结果：10,36,22,28,48,56,72,86
第4趟排序结果：10,22,28,36,48,56,72,86
第5趟排序结果：10,22,28,36,48,56,72,86
……每趟排序结果2分，共10分
四、算法设计题（每空2 分，共20分）
26.补充下列折半查找算法：
int search_bin(SSTable ST，KeyType key)
{ low=1;high=ST.length;
while( low<=high )
{ mid=(low+high)/2 ;
if(key=ST.elem[mid].key) return mid ;
else if (keyelse low=mid+1 ;
}//while
return 0;
}//Search_Bin
27.先序遍历二叉树的非递归算法
void PreOrder_Nonrecursive(Bitree T)
{ InitStack(S);
Push(S, T ); //根指针进栈
while(!StackEmpty(S))
{ while(Gettop(S, p )&&p)
{ visit(p->data); push(S, p->lchild ); } //向左走到尽头
pop(S,p);
if(!StackEmpty(S))
