一、选择题（每题2分，共20分）
1、二分查找，要求被查找的表是（ ）
A 顺序表 B 分块有序表 C 链表 D 无限制
2、一完二叉树有30个接点，则该树有（ ） 层。(根为0层)
A 3 B 4 C 5 D 6
3、下列排序算法中，第一趟排序后，其最大的或最小的数一定在最终的位置上的是（ ）
A 归并排序 B 直接插入排序 C 快速排序 D 冒泡排序
4、设八栈序列为A,B,C,D,则栈可能产生的出栈序列是（ ）
A、 A C D B B、 C A D B
C、 D C A B D、 D A B C
5、如有一颗二叉树按先序遍历所得结果为（ ）
A A、C G B E F D A
B D B、A B C G D E F
C E F C、C G B A E D F
G D、G C B E F D A
6、下面哪个结构属于线形结构 （ ）
A 二叉排序树 B 线索树 C 队列 D 图
7、栈和队列都是 （ ）
A 没有限制的线形表 B 没有限制的非线形表
CD
8、在线性表操作中，常对某元素插入或删除。则采用什么存贮结构最节省运算时间（ ）
A、单链表 B、散列表 C、二叉链表 D、顺序表
9、设H为带头结点单向循环链表的头指针，P为移动指针，指针域为link，则表尾的判断条件是（ ）
A、H->link = H B、P = H C、P->link = nil D、P->link = H
10、先序遍历能得到A，B，C序列的不同二叉树，最多有几种（ ）
A、4 B、5 C、6 D、7
二、填空题（每题2分，共20分）
1、在单链表中，欲删除某一指定结点时，必须找到该结点的 结点。
2、 和 是操作点受限的线性表。
3、二分查找的条件是 。
4、深度为K的二叉树中结点总数最多为 。
5、在有n（n>0）个结点的二叉链表中，空链域的个数为 个。
6、在对有15个数据的有序表中作二分查找时，有 个结点查找长度为3。
7、在单链表中，若要在指针P所指结点后插入指针S所指结点，则需执行下列语句： 。
8、举出插入排序的两种排序法： 。
9、快速排序的时间复杂度是 。
三、解答下列各题（每题10分，共30分）
1、简述基数排序的思想方法。
2、如图所示森林，请将其转化为二叉树，并写出其前，中，后序遍历序列。
A
B C
D E F G
H I J K
L M N
3、利用哈夫曼树进行编码。
请写出下列字符集的最佳前缀码：
字符集： a b c d
频率（万次）：2 3 4 8
编 码：
（给出详细编码过程）
四、算法设计题（每题10分，共30分）
1、有一数组，随机存贮一串关键字代码，请用快速排序法将关键字由小到大排列写出其算法描述。
2、设有一二叉树，用链式存贮，结点结构如下
lc data Kc
请写出后序遍历该二叉树的算法描述。（方法不限）