一、单项选择题(本题总分20分，每题2分)在每小题列出的四个选项中只有
一个选项是符合题目要求的，请将正确选项前的字母。
1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) 。
A.顺序表
B.链表
C.索引表
D.散列表
采用排除法，顺序表存储位置表示数据元素的顺序关系，跟关键字无法；链表的地址是动态分配的；索引表是按数据元素的关键字排序所得，它的数据元素是没有规律的
2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( A ) 。
A.n-i+1
B.n-i
C.i
D.i-1
代入计算法，我们知道在i=n+1时不需要移动元素
3.若一棵二叉树的先序遍历序列为a,b,c，则由abc三个结点构成的二叉树个数为( B ) 。
A.4
B.5
C.6
D.7
4.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为130，则元素A[3][4][5]的存储地址为(B ) 。
A.370 B .368 C .366 D.372
Loc(3,4,5)=loc(0,0,0)+(3*5*6+4*6+5)*2=130+119*2=368;
5.高度为h的二叉树（仅含根结点的二叉树高度为1）的结点最少是多少( D )。
A. h+1
B. 2h
C. 2h－1
D. h
二叉树性质2
6. 将两个各有n个元素的有序表归并成一个有序表，其最多的比较次数是( C )。
A. n
B. n+1
C. 2n-1
D. n-1
7. 已知一算术表达式的中缀形式为A＋B *C-D/E，后缀形式为ABC *+DE/-，其前缀形式为( A )。
A. -+A*BC/DE
B. –A+B*CD/E
C. -+*ABC/DE
D. –A+B*C/DE
根据中缀和后缀表达式可画出表达树如下：
-
+/
*
A
B C
D E
故前缀表达式为：-+A*BC/DE
8．下面图示的顺序存储结构表示的二叉树是（A ）。
本题有两种可能性，第一种位置0是本身是数据，第二种6表示元素个数。
第一种双亲i左孩子2*i+1 右孩子2*i+2 B.中F应该是D右孩子; D.错的
第二种双亲i 左孩子2*i 右孩子2*i+1 A.正确 C.错
9．给定一个有n个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动（ C ）个元素。
A．(n+1)/2 B．n/2 C．(n-1)/2 D．1
10．法的时间复杂度表达式为T(n)=an2+bnlgn+cn+d，其中n为问题的规模，a、b、c和d为常数，用O表示其渐进时间复杂度为（ D ）。
A．O(1) B．O(n) C．O(nlogn) D．O(n2)
二、填空题（本题总分26分，每空2分）
1．在带头结点的单链表中，除头结点外，任一结点的位置由（前驱结点的next 域）指示。
2．若n阶下三角矩阵A,以行优先顺序存储其非0元素,所需要的存储空间元的数量为（n*(n+1)/2）。
3．如果树中某结点A有三个兄弟,且P是A的父亲,P的度是（4 ）。
4．若k>=1，深度为k的完全二叉树所包含的结点数最多为（2k-1 ）。
5．“X = (A + B ) × ( C - D / E )”的后缀式表示为（XAB+CDE/-1*= ），后缀算式9 2 3 +- 10 2 / - 的值为（-1）。
6．若用链表存储一棵二叉树，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有（2*n ）个指针域，其中有（n-1）个指针域是存放了地址，有（n+1）个指针是空指针。
7．设有一个10×10的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[6][4]存放于B中的位置为（B[25] ）。
8．对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号，则第i（i>1）个结点的双亲结点编号为（i/2 ），如果第i个结点有右孩子，则右孩子结点的编号为（2*i+1 ）。
9．设哈夫曼树中共有n个结点，则该哈夫曼树中有（0 ）个度数为1的结点。
三、应用题（共4题，每题11分，共44分）
1． 假设有9个权值{5，9，6，7，3，14，15，18，23}，构造huffman 树（画出构造过程）并求带权路径
长度WPL 。 解：
WPL=(3+5)*5+(6+7+9)*4+(14+15)*3+(18+23)*2=297 2．将图一`8(d)的二叉树转换为相应的森林。
3
． 假设以数组seqn ［m ］存放循环队列的元素，设变量rear 和quelen 分别指示循环队列中队尾元素的位置和元素的个数。
(1) 写出队满的条件表达式； (2) 写出队空的条件表达式；
(3) 设m=40，rear=13，quelen=18，求队头元素的位置。 解：
(1) 队满： quelen==m (2) 队空： quelen==0
(3) 队首位置：(m+rear-quelen+1)%m=(40+13-18+1)%40=36
4． 已知一棵二叉树的前序序列为ABCDEFGH ，中序序列为CBEDFAGH ，请画出该二叉树。
四、算法设计题（共2题，任选一题每题10分，共10分）
1. 设有两顺序有序表A 和B,A 表是升序,表长m,B 表是降序,表长n,设计一算法根据A 和B 两表数据合并成新表C(升序),要求算法时间复杂度为O(m+n) 。
