一、选择题（在每个小题四个备选答案中选出一个正确答案，按照序号填在下面的表
格中）（本大题共10小题，每小题2分，答对得分，答错不得分，总计20分）
1、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为：
A. SA+144 B .SA+180 C. SA+222 D. SA+225
2、循环队列用数组A[0,m－1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是：
A. (rear-front+m)%m B .read-front+1 C. read-front-1 D. read-front
3、不带头结点的单链表head为空的判定条件是：
A. head->next= =NULL B . head= =NULL C. head->next= =head D. head!=NULL
4、一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（）：
A 45321
B 54321
C 12345
D 45312
5、设有两个串p和q，则q与p相等的条件是：
A. 长度相等 B 对应位置字符相等 C A并且B D. A或者B
6、稀疏矩阵一般的压缩方法有两种，即：
A. 三元组表和十字链表 B .三元组表和散列表
C. 二维数组和三维数组
D. 散列表和十字链表
7、通常需要使用下列哪种数据结构来实现将递归算法转换成对应的非递归算法：
A. 队列 B . 栈 C. 图 D. 树
8、从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较多少个结点？
A. n B .n/2 C. (n-1)/2 D. (n+1)/2
9、采用邻接表存储的图的深度优先遍历算法类似于二叉树的：
A. 中序遍历 B .先序遍历 C. 后序遍历 D. 按层遍历
10、设有5000个无序的元素，希望用最快速度挑选出其中前3个最大的元素，在以下的排序方法中，采用哪种方法最好？
A 快速排序
B 插入排序C希尔排序D堆排序
二、填空（本大题共9小题，10个空，每空2分，答对得分，答错不得分，总计20分）
1、在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有（）个。
2、以折半查找方法查找一个线性表时，此线性表必须是顺序存储的（）表。
3、对于一个具有n个顶点和e条边的连通图，其生成树中的边数是（）条。
4、向一棵高度为H的B树中插入关键码的过程中，若最终引起树根结点的分裂，则新树的高度为（）。
5、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺
序查找来确定结点所在的块时，每块应分（ ）个结点最佳。
6、在一棵9阶B 树中，若在某结点中插入一个关键字而引起该结点的分裂，则此结点中原有的关键字的个数是（ ）个。
7、中缀表达式F+ (A/B+C)×D －E 的后缀表达式是（ ）
8、已知广义表L=(a, (b ，d)，(f, ( c)))，设取表头和表尾的运算分别为H(L)，T(L)，则取得原子c 的运算是（ ）。
9、设某双链表的结点形式为
，若要删除已知指针R 所指结点（中间结点）则需执行下述主要语句段：
( )；
( )；
三、简答题（每题5分，共30分，答案写在后面的答题纸上
1、计算模式串“BBABBBAB ”的NEXT 数组。
（5分）
2、已知一棵二叉树的中根序列为ABCDEFGHI ，先根序列为FBADCEIGH ，请：
（1）画出该二叉树；（3分）
（2）画出该二叉树对应的森林。
（2分）
3、已知图G 的邻接表表示如下所示，请：
（1）写出该图以H 为出发点深度优先遍历的结果；（3分）
（2）画出它的深度优先生成树。
（2分）
4、给出一组关键字T=（12，2，
16，30，8，28，4，10，20，6，18）。
写出用下列算法从小到大排序时第一趟结束时的序列：
1
2
3 4 5 6
7
8
（1）快速排序(选第一个记录为枢轴(分隔))（3分）
（2）希尔排序（第一趟排序的增量为5）（2分）
5、对于给出的一组权W={3，3，9，4，15，11，5，20}：
（1）构造哈夫曼树；(3分)
（2）求它的带权路径长度为。
（2分）
6、已知关键字序列（12，1，4，3，7，8，10，2），画出逐个插入这些关键字生成平衡二叉树的详细过程。
（5分）
四、解答题（共10分，答案写在后面的答题纸上）
1、给定关键码序列（26，25，20，33，21，24，45，204，42，38，29，31），要用散列法进行存储，规定负载因子a=0.6。
（1）请给出除余法的散列函数。
（3分）
（2）用开放地址法中的线性探测法解决冲突，请画出插入所有的关键码后得到的散列表（5分）
（3）计算等概率下查找成功的平均查找长度ASL。
（2分）
五、算法设计题(共10分，答案写在后面的答题纸上，要求写出结构类型定义和必要的函数说明)
已知有两个具有相同结点个数的带头结点的单链表A和B，A={a1，a2，……，an}，B={b1，b2，……，bn}，编写一个函数将其合并成一个带头结点的单链表C，使得C={bn，an，bn-1，an-1，……..，b2，a2，b1，a1 }。