数据结构A卷

课程名称 《算法与数据结构》 任课教师签名 蔡琼等 出题教师签名 联盟出题 审题教师签名 吕品等 考试方式 （ 闭 ）卷 适用专业 计算机各专业 考试时间 （ 120 ）分钟

题号 一 二 三 四 五 六 七 总分 得分 评卷人 一、填空题(每空2分, 共30分)

1. _____是数据的基本单位, 在计算机程序中通常作为一个整体进行考虑和处理。

2. 数据的逻辑结构可分为集合、线性结构、_____结构和_____结构。 3. 数据元素之间的关系在计算机中有两种不同的表示方法: 顺序映象和非顺序映象, 由此得到两种不同的存储结构: 顺序存储结构和_____。 4. 算法的五个重要特性包括: 有穷性、_____、_____、输入和输出。 5. 下面的算法计算实数x (x > 0)的非负整数n (n  0)次幂, 其时间复杂度是_____。

double Power(double x, int n) { double y = 1; if (n > 0) { y = Power(x, n / 2); y *= y; if (n % 2 == 1) y *= x;

}

return y;

}

6. 只在表的一端进行插入和删除的线性表称为_____。在表的一端进行插入、另一端进行删除的线性表称为_____。 7. 在C语言中定义下面的二维实型数组:

double a[5][10];

每个元素占用8字节内存空间, 若数组起始地址为0x1000, 则元素a[3][5] 的地址为0x_____。

8. 已知完全二叉树有1024个结点, 则该二叉树的深度为_____。 9. 包含5个顶点的有向图, 至多有_____条弧。

10. 深度为10的完全二叉树至少有_____个结点, 至多有_____个结点。 11. 包含20个顶点的连通图, 其最小生成树拥有_____条边。 二、单项选择题 (每小题2分，共20分)

1. 若元素1, 2, 3依次进栈, 则出栈的次序不可能是_____。

A) 3, 2, 1

B) 1, 3, 2

C) 3, 1, 2

D) 2, 1, 3

2. 在无附加头结点的链栈中, 若栈顶指针为top, 将指针s所指示的结点入栈, 所执行的操作为_____。

A) s->next = top; top = top->next; B) top = s; s->next = top;

C) s->next = top->next; top->next = s; D) s->next = top; top = s;

3. 在无附加头结点的链栈中, 若栈顶指针为top, 则判断栈空的条件是_____。

A) top==NULL B) top!=NULL

C) top->next == top

D) top->next==NULL

4. 循环队列存于数组a[M]中, 假定队首和队尾指针分别是front和rear, D 则判断队空的条件是_____。

A) front == 0

B) rear == 0

C) front == M - 1 D) front == rear

5. _____是关于排序算法的错误说法。

A) 直接插入法和冒泡法是稳定的 B) 快速法在任何情况下都是最快的

C) 二路归并算法需要的辅助空间是O(n) D) 堆排序的时间复杂度是O(n lb n)

6. 主关键字是指能唯一标识一条记录的_____。

A) 一个数据项 B) 一组数据项 C) A或B D) 以上都不是 7. 按照二叉树的定义, 具有3个结点的二叉树有_____种形态。 A) 3 B) 4 C) 5 D) 6 8. 求串s2在串s1中首次出现的位置的运算是_____。 A) 连接 B)求串长 C) 求子串 D) 模式匹配 9. 以下数据结构中，_____是线性结构 A) 串 B) 广义表 C) 稀疏矩阵 D)二叉树 10. 下面算法的时间复杂度, _____效率最高

A) O(n)

B) O(lb n)

C) O(n lb n)

D) O(n2)

三、分析题（每小题5分，共30分）

1. 若二叉树先根遍历的序列为: EFGADCB, 中根遍历的序列为GDAFBCE, 请画出二叉树形态。

2. 已知电文为“ABBCDADDDCACAAAD”, 根据字母的出现频率构造哈夫曼树, 并写出每个字符的哈夫曼编码。

字母 频率 哈夫曼编码

A B C

3. 请写出用Dijkstra算法求从顶点1出发到其余顶点的最短路径的计算

过程。

B 1 C 1 4 2 4 A 6 G 1 D 2 5 3 1 F 1 E

4. 已知散列表表长为15, 地址计算公式为

H(k) = k mod 13

冲突处理方式为线性探测再散列, 将关键字5、15、18、2、3、31、16、4依次插入到散列表中, 请写出散列表的状态。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5. 根据下面左边图所示的无向图, 请用Prim算法从顶点1出发求最小生成树的步骤。

2 6 5 E F 2 1 2 3 1 3 3 5 6 1 8 A B C D 1 6 1 2 4 3 7 G H

6. 根据上面右图所示的有向无环图进行拓扑排序, 请写出至少5种排序结果。

四、综合应用题（每小题10分，共20分） 1. 单值化处理

顺序表结构类型定义如下:

struct ALIST {

float *data; // 动态数组起始地址

int size, length; // 动态数组大小、顺序表长度 };

请编写算法, 对于顺序表中所有值相同的元素, 只保留其中第一个元素, 删除其余的元素。

假如线性表为(2.5, 3.8, 1.2, 2.5, 4.7, 3.8, 3.8, 9.1, 1.2), 则经过单值化处理后将变为(2.5, 3.8, 1.2, 4.7, 9.1)。

void Unique(ALIST *list);

要求: 用文字描述算法思想, 并估算时间复杂度, 然后用C/C++语言编码。

2. 二叉树采用链式存储结构, 结点的存储结构如下图所示:

lch data rch 结点的结构类型定义如下: struct NODE {

float data;

struct NODE *lch, *rch; };

// 数据域 // 指针域

请编写算法求二叉树的深度。 int Depth(NODE *root);

函数的参数是根指针, 函数值是二叉树的深度。如: printf(\"%f\\n\

要求: 用文字描述算法思想, 并估算时间复杂度, 然后用C/C++语言编码。