一、单项选择题（本大题共10道小道小题，每小题3分，共30分）
1. 算法的时间复杂度取决于 【 】
A. 问题的规模 B. 待处理数据的初始状态
C. 软件和硬件的组合 D. 操作系统
2. 向一个栈顶指针为top的链栈中插入一个s结点，则执行 【 】
A. top->next=s; B. s->next=top->next; top->next=s;
C. s->next=top; top=s; D. s->next=top; top=top->next;
3. 广义表（（a））的表头是 【 】
A. a B. (a) C. () D. ((a))
4. 由带权为8、2、5、7的叶子结点构造一棵哈夫曼树，该树的带权路径长度为 【 】
A. 37 B. 32 C. 46 D. 43
5. 采用邻接表存储的图，其BFS算法类似于二叉树的 【 】
A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层遍历
6. 在非空m阶B_树上，除根结点之外的所有其他非终端结点 【 】
A. 至少有 棵子树 B. 至多有 棵子树
C. 至少有 棵子树 D. 至多有 棵子树
7. 对线性表进行顺序查找时，要求线性表的存储结构为 【 】
A. 散列存储 B. 顺序存储或者链式存储
C. 压缩存储 D. 索引存储
8. 在关键字“基本有序”的情况下，最佳排序算法为 【 】
A. 快速排序 B. 冒泡排序 C. 直接插入排序 D. 基数排序
9. 折半查找法和二叉排序树的时间性能 【 】
A. 与处理数据量有关 B. 相同 C. 不相同 D. 不确定
10. 串是一种特殊的线性表，其特殊性体现在 【 】
A. 可以顺序存储 B. 数据元素是一个字符
C. 可以链接存储 D. 数据元素可以是多个字符

二、填空题（本大题共10小题，每小题2分，共20分）
1. 在具有n个单元的循环队列中，队满时共有____________个元素。
2. 单链表中设置头结点的目的是____________。
3. 消除递归_____________需要使用栈。
4. 在具有n(n≥1)个结点的k叉树中，有_____________个空指针。
5. 深度为5的二叉树至多有_________个结点。
6. 一个连通图的__________是一个极小连通子图。
7. 对稀疏图进行DFS遍历时，应该采用___________作为其存储结构。
8. 在哈希表中，装填因子α越大，则_______________________。
9. 在堆排序和快速排序中，若原始记录接近有序，则应该选择____________。
10. 设关键字序列为｛3, 7, 6, 9, 7, 1, 4, 5, 20｝，对其排序的最少交换次数为_________。

三、简答题（本大题共6道小题，共56分）
1. 若中序序列为ABC，试问有多少种不同的形态的二叉树可以得到这一遍历结果？画出所有的二叉树。（9分）
2. 对于下图，请给出：
（1） 对应的邻接矩阵，并给出V1、V2、V3的出度和入度;
（2） 邻接表和逆邻接表;
（3） 强连通分量。（10分）
3. 已知关键字序列为｛9, 6, 2, 5, 4, 3, 1, 10, 7, 11, 8｝，试回答：
（1） 按表中元素的顺序，构造一棵平衡二叉排序树。
（2） 在等概率的情况下，求查找成功的ASL值。（10分）
4. 在采用线性探测再散列法解决冲突的散列表中，所有同义词在表中是否一定相邻？试说明理由。（9分）
5. 有关键字｛25, 50, 55, 20, 30, 45, 40, 15, 10, 35｝，判断其是否为堆，若不是堆，请调整为一个小根堆。要求写出调整过程。（9分）
6. 什么是内部排序？稳定性指的是什么？（9分）

四、算法阅读题（本大题共3道小题，每小题8分，共24分）
【说明】结构定义
struct ListNode {
elemtype data;
struct ListNode *next;
};

struct BtreeNode {
elemtype data;
struct BtreeNode *lchild, *rchild;
};

1. 下面算法的功能是将队列中的数据元素进行逆置。设栈和队列的元素类型均为int。请在空白处填入正确的语句。
Void unknown(queue &q)
{
__________①_________;
int d;
InitStack(s);
while(_______②_______){
Dequeue(q, d);
Push(s, d);
}
while(!StackEmpty(s)){
_______③______;
Enqueue(q, d);
}
}
2. 下面的算法是统计单链表中数据域的值为X的结点个数。请在空白处填入正确的语句。
int CountNodeX(struct ListNode *head, Elemtype x)
{
struct ListNode *p;
_______①______;
p = head;
while(______②_____){
if(_______③______) n++;
p=p->next;
}
________④_________;
}
3. 下面的算法完成了对一棵二叉树中所有的左、右子树的相互交换。请在空白入填入正确的语句。
Void TNodeExchang(struct BTreeNode *root)
{
if(________①________){
TNodeExchang(root->lchild);
_________②__________;
struct BTreeNode *p;
p = _______③_________;
root->lchild = root->rchild;
root->rchild = _______④______;
}
}

五、算法设计题（本大题共3道小题，共20分）
1. 已知Head是带头结点的单链表的头指针，试编写逆序输出表中各元素的递归算法。假设数据为整数。
Void FindLinkData(struct ListNode *head){…}（7分）
2. 试设计一个算法，求出指定结点在给定的二叉排序树中的层次。
【要求】1. 给出算法的设计思想;
2. 给出算法代码。（7分）
int pLevel(struct BTreeNode *root, struct BTreeNode *p)
{//求指定结点p在以root为根的二叉树中的层次}
3. 给出一棵二叉树的前序序列和后序序列，能否唯一地确定一棵二叉树？试证明你的论断。（6分）