一、选择题（共20题，每题3分，共60分）

1.在数据结构中，与所使用的计算机无关的是数据的（ ）。

A. 存储结构

B. 逻辑结构

C. 物理结构

D. 运算实现

2.单链表中，在指针p所指结点之后插入一个结点s的操作是（ ）。

A. p->next = s; s->next = p->next;

B. s->next = p->next; p->next = s;

C. p->next = s; p->next = s->next;

D. p->next = s->next; p->next = s;

3.一个栈的入栈序列为1,2,3,...,n，其出栈序列为p1,p2,...,pn。若p1=n，则pi为（ ）。

A. i

B. n-i

C. n-i+1

D. 不确定

4.循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别为front和rear，则当前队列中的元素个数是（ ）。

A. (rear - front + m) % m

B. rear - front + 1

C. rear - front - 1

D. rear - front

5.在一棵完全二叉树中，若某结点无左孩子，则该结点（ ）。

A. 一定是叶子结点

B. 一定无右孩子

C. 可能有右孩子

D. 是度为1的结点

6.下列排序算法中，最坏情况下时间复杂度最低的是（ ）。

A. 快速排序

B. 冒泡排序

C. 堆排序

D. 直接插入排序

7.哈希表中，冲突是指（ ）。

A. 两个元素具有相同的序号

B. 两个元素的关键字不同但哈希地址相同

C. 两个元素的关键字相同

D. 两个元素的哈希地址不同

8.在图的最小生成树中，下列说法正确的是（ ）。

A. 最小生成树是唯一的

B. 最小生成树中所有边的权值之和最小

C. 最小生成树中边的数量等于顶点数

D. 最小生成树中不含回路

9.对一棵二叉排序树进行（ ）遍历，可以得到一个递增的关键字序列。

A. 先序

B. 中序

C. 后序

D. 层序

10.下列排序方法中，稳定的是（ ）。

A. 快速排序

B. 堆排序

C. 希尔排序

D. 冒泡排序

11. 关于广义表 A = (a, (b, c), (d, (e, f)))，下列说法正确的是（ ）。

A. 表头是 a

B. 表尾是 ((b, c), (d, (e, f)))

C. 深度为 3

D. 长度为 2

12. 串 S = "data structure"，其子串的个数是（ ）（包括空串）。

A. 14×15/2

B. 14×15/2 + 1

C. 13×14/2 + 1

D. 13×14/2

13. 已知二维数组 A[10][20] 采用行优先存储，每个元素占 2 个存储单元，A[0][0] 的地址为 100，则 A[6][12] 的地址为（ ）。

A. 100 + (6×20+12)×2

B. 100 + (6×20+12)

C. 100 + (12×10+6)×2

D. 100 + (12×10+6)

14. 下列关于二叉树的说法，错误的是（ ）。

A. 满二叉树一定是完全二叉树

B. 完全二叉树中，若某结点无左孩子，则它必无右孩子

C. 二叉树的遍历序列不能唯一确定一棵二叉树

D. 一棵二叉树的后序遍历序列与中序遍历序列相同，则该二叉树所有结点均无左子树

15. 一个有向图具有 n 个顶点，若所有顶点的出度之和为 S，则所有顶点的入度之和为（ ）。

A. S

B. S−1

C. S+1

D. 无法确定

16. 下列排序算法中，在初始序列已基本有序时，效率最高的是（ ）。

A. 快速排序

B. 堆排序

C. 直接插入排序

D. 归并排序

17. 在 C 语言中，若有定义 int a[5] = {1,2,3,4,5}, *p = a+2; 则 *(p+1) 的值是（ ）。

A. 3

B. 4

C. 5

D. 不确定

18. 对于一个用单链表实现的不带头结点的队列，在进行入队操作时，需要修改（ ）。

A. 仅队尾指针

B. 仅队头指针

C. 队头和队尾指针

D. 根据队列空或非空决定修改哪个指针

19. 已知函数 f(int n) 递归定义如下：

c

int f(int n) {

    if (n <= 1) return 1;

    return f(n-1) + f(n-2);}

则 f(5) 的执行过程中，f(2) 被调用的次数为（ ）。

A. 2

B. 3

C. 4

D. 5

20. 下列选项中，能够正确实现两个整型变量 x 和 y 值交换的代码段是（ ）。

A. x=y; y=x;

B. x=x+y; y=x-y; x=x-y;

C. x=x^y; y=x^y; x=x^y;

D. B 和 C 都正确

二、填空题（共10空，每空3分，共30分）

1.数据的逻辑结构可分为集合、线性结构、树形结构和______四种。

2.在顺序表中插入或删除一个元素，平均需要移动______个元素。

3.一个栈的输入序列为12345，若输出序列的第一个元素是3，则输出序列的最后一个元素可能是______。

4.在长度为n的线性表中进行顺序查找，平均查找长度为______。

5.一棵有n个结点的满二叉树，其叶子结点个数为______。

6.图的深度优先遍历算法使用的数据结构是______。

7.在哈希表中，装载因子α的值越大，冲突的可能性______。

8.快速排序在______情况下时间复杂度最差。

9.若一棵二叉树有10个叶子结点，则该二叉树中度为2的结点个数为______。

10.在堆排序中，对n个元素进行初始建堆的时间复杂度为______。

三、解答题（共4题，每题15分，共60分）

1. 树与二叉树（15分）

已知某二叉树的先序遍历序列为：ABDGCEHIF，中序遍历序列为：DGBAHEICF。

（1）请构造出该二叉树。

（2）写出该二叉树的后序遍历序列。

（3）画出该二叉树对应的森林。

2. 图的应用（15分）

已知一个无向带权图的顶点为V={A,B,C,D,E,F}，边及权值为：

A-B(6), A-C(1), A-D(5), B-C(5), B-E(3), C-D(5), C-E(6), C-F(4), D-F(2), E-F(6)。

（1）画出该图。

（2）使用普里姆（Prim）算法从顶点A开始构造最小生成树，写出依次加入的边和权值。

（3）使用克鲁斯卡尔（Kruskal）算法构造最小生成树，写出依次加入的边和权值。

3. 查找与哈希表（15分）

给定关键字序列{19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79}，哈希函数为H(key)=key mod 13，采用线性探测再散列方法处理冲突，哈希表长度为16。

（1）构造哈希表。

（2）计算等概率下查找成功的平均查找长度。

（3）若改用链地址法处理冲突，再求平均查找长度。

4. 排序过程（15分）

给定序列{49, 38, 65, 97, 76, 13, 27, 49}，

（1）写出直接插入排序的每趟结果。

（2）写出快速排序（以第一个元素为枢轴）的每趟划分结果。

（3）写出堆排序的初始建堆过程及每趟排序后的序列。

四、算法设计与程序设计题（共50分）

题1（15分）

编写一个函数 void ReversePrint(LinkList L)，其功能是：逆序输出单链表中的所有元素，要求不能修改链表结构，且空间复杂度为O(1)。

（说明：链表结点结构为 struct Node{ int data; Node* next; };）

题2（15分）

已知一个二叉树采用二叉链表存储，请编写递归算法 int CountLeaf(BiTree T) 统计二叉树中叶子结点的个数。

题3（20分）

已知一个无向图采用邻接表存储，请编写一个函数 int IsConnected(ALGraph G) 判断该图是否为连通图。若是，返回1；否则返回0。

要求：

使用深度优先遍历实现

写出关键数据结构定义

给出完整算法代码