跳转至

2020-2021-1A卷

2019级

2020 - 2021 学年第一学期

课程名称: 算法设计和分析 课程性质: 专业必修

一、单项选择题(15分,每题3分)

  1. 快速排序算法的平均复杂度是( )。

A. \(O(n \log n)\)

B. \(O(n^{2})\)

C. \(\Omega(n)\)

D. 以上都是

  1. 活动选择问题的目标是选出一个最大的互相兼容的活动集合。以下策略中哪种策略能够获得全局最优的解( )。

A. 优先选择活动时长最短、且与已选择活动相兼容的活动

B. 优先选择最早开始、且与已选择活动相兼容的活动

C. 优先选择最早结束、且与已选择活动相兼容的活动

D. 优先选择与其自身相冲突的活动数量最少、且与已选择活动相兼容的活动

  1. 哈密顿回路问题在无向图中找到一条通过所有结点的简单回路，以下说法错误的是( )。

A. 哈密顿回路问题是一个NPC问题

B. 哈密顿回路问题 \({\le}_p\) 旅行商问题

C. 哈密顿回路问题的复杂度是 \(\Omega(n 2^n)\)

D. 哈密顿回路问题是否可以在多项式时间可解，目前尚无定论

  1. 基于关键字集合 \(\{1,2,..., 15\}\) 所构建的红黑树，黑高最低是( )。

A. 2

B. 3

C. 4

D. 5

  1. 假定输入数据有6个元素，则比较排序算法在最坏情况下的比较次数不能少于( )次。

A. 9

B. 10

C. 11

D. 12

二、计算题(10分,前两题每题3分,第3题4分)

计算下列递归式 \(T(n)\) 的渐进紧确界，需要写出步骤。

  1. \(T(n)=7T(n/3)+n^{3/2}\)
  2. \(T(n)=2T(n/4)+10000\)
  3. \(T(n)=T(n-1)+1/n\)

三、排序(18分,每题9分)

  1. 拟基于 \(A=<7, 8, 1, 4, 9, 5, 6, 3, 2>\)，构建大顶堆，并进行堆排序。

(1) 请分别画出初始堆结构、最终堆结构所对应的二叉树。

(2) 堆排序算法如下所示，请补齐空缺代码。

HeapSort(A)
Build-Max-Heap(A)
for i = _______ downto 2
    do exchange A[1] and A[i]
       A.heap-size = _______
       Max-Heapify(A, 1)

(3) 堆排序的时间复杂度是多少？请具体分析。

  1. 计数排序算法需要维护一个数组 \(C\)，该数组维护各个元素的频度，以及小于等于该元素的频数，并结合数组 \(C\) 遍历输入数组 \(A\) 来进行排序，从而输出数组 \(C\)。

假设数组 \(A=<2, 1, 3, 5, 4, 2, 1, 5, 5>\)，且输入元素的范围是1到5之间的自然数。

问：(1) 一次遍历 \(A\) 之后生成的数组 \(C\) 是什么？(2) 一次遍历 \(C\) 之后，\(C\) 被更新为什么？(3) 最后，还需遍历数组 \(A\) 以生成 \(B\)。当处理了前4个元素时，数组 \(B\) 的内容是什么？

四、树(20分,每题10分)

  1. 以下搜索树包含 \(\{1,2,3,4,5,6,7,8,9\}\) 等9个元素，(1) 请填充该树；(2) 这棵树是否可能是红黑树。若是，请标出红节点和黑节点；否则，请阐述理由，并画一棵红黑树。

image-20260426222726126

  1. 考虑数组 \(<7, 2, 9, 3, 8, 5, 6, 1, 4>\)。(1) 调用 Tree-insert 算法按照数组顺序生成搜索树，请画出元素8被插入后的搜索树，以及所有元素被插入后的最终搜索树；(2) 调用 Tree-delete 算法删除元素2，请画出搜索树。

五、算法设计与分析(19分,第1题10分,第2题9分)

  1. 假设队列具有 Enqueue, Dequeue, MultiEnqueue10, MultiDequeue 等四个操作，其中 Enqueue 操作将一个元素添加到队列尾部，Dequeue 操作将队列中最旧元素弹出队列，MultiEnqueue10 可以一次性将最多10个元素添加到队列中，MultiDequeue 可以一次性将多个元素弹出队列，只要元素个数不超过队列中现有元素个数。

(1) 采用核算法来进行摊还分析。

(2) 采用势能法进行摊还分析。

  1. 已知有多个字母的频度分别是: a:9, b:2, c:7, d:20, e:1, f:5, g:10, h:30。

(1) 请画出针对这些字母的赫夫曼树。

(2) 解析二进制串 101001101000101010101010 的字符串。

(3) 写出字符串 abcdefgh 的二进制编码。

六、图(18分,每题9分)

image-20260426223035473

  1. 最小生成树问题。

(1) 请根据 Prim 算法找出上图的最小生成树，计算总权重，并说明树扩展过程(只需画在一张图上，并在相关边上标注扩展次序)。

(2) HI是图中的最长边，请找出包含HI、且总权重最小的生成树，计算总权重，并说明生成过程(只需画在一张图上，并在相关边上标注扩展次序)。

(3) DG是图中第二短的边，请找出包含HI、但不包含DG的总权重最小的生成树，计算总权重，并说明生成过程(只需画在一张图上，并在相关边上标注扩展次序)。

  1. 最短路径搜索问题。

(1) 按照上图，根据 Dijkstra 算法，求A到F的最短路径。

(2) Dijkstra 算法不适合有负边(权重为负)的图。请举例阐述这个观点。

(3) 假设AE之间的权重并不等于7，而是 \(x\)。请问，在什么条件下AE处在从A到F的最短路径上。