一．单项选择题（本大题共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. 至少有2/m棵子树 B. 至多有2/m棵子树

C. 至少有2/m棵子树 D. 至多有2/m棵子树

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分）