重庆理工大学2014年《算法分析与设计》期末考试试题

"2014年重庆理工大学《算法分析与设计》三套期末考试试卷.pdf" 这份试卷主要涵盖了算法分析与设计的基础知识，包括算法效率比较、递归算法分析、递推方程求解、最优化问题、分治策略以及字符串处理等核心概念。以下是各部分详细知识点： **问题一** 1. **算法效率比较**：比较了不同函数的增长率，涉及大O表示法。正确排序是：log(n) < n + 3 < 2n + n^99 - 2 < n^300 < n! < 4nlog(n)。增长率从小到大，依次是常数、线性、多项式、指数和阶乘。 2. **递归算法分析**：给出了一个递归算法S(n)，用于计算前n个立方的和。递归关系为S(n) = S(n-1) + n^3，基本操作是n次立方加法。求解递归公式，可得S(n) = n*(n+1)*(2n+1)/6。 3. **递推方程求解**：提供了两个递推方程，T(n) = T(n-1) + n 和 T(n) = 2T(n-1) + 1，分别通过迭代或主定理求解。 **问题二** 1. **最接近点对问题**：这是一个经典的计算几何问题，可以使用蛮力法解决，即遍历所有点对并计算距离，找出最小距离。伪代码：对于每对点i和j (i < j)，计算距离d，并更新最小距离min_dist。 2. **连分式计算**：递归算法用于计算n阶连分式，递归公式为F(n) = F(n-1) / (1 + F(n-1))，基础情况为F(1) = 1。 **问题三** 1. **快速排序与选择第k小元素**：两者的共同点是都基于分治策略，不同在于快速排序是对整个数组进行排序，而选择第k小元素仅需找出特定位置的元素。时间复杂度上，快速排序平均为O(n log n)，最坏为O(n^2)，选择第k小元素为O(n)。 2. **分区算法**：提供了两种分区策略，lomuto分区和Hoare分区。这里以lomuto为例，伪代码如下： ``` LomutoPartition(arr, low, high): pivot = arr[high] i = low - 1 for j = low to high-1: if arr[j] <= pivot: i++ swap(arr[i], arr[j]) swap(arr[i+1], arr[high]) ``` 3. **快速排序算法**：经典的快速排序伪代码如下： ``` QuickSort(arr, low, high): if low < high: pivot_index = Partition(arr, low, high) QuickSort(arr, low, pivot_index - 1) QuickSort(arr, pivot_index + 1, high) ``` **问题四** 1. **俄式乘法列表**：俄式乘法是一种高效的乘法算法，18 * 32的乘积可通过列式乘法得到，步骤如下： ``` 18 ×32 ---- 72 (18×2) 560 (18×30，向左移一位) ---- 576 ``` 2. **二进制格雷码**：生成3位二进制串的过程，从000开始，每次改变一个比特，得到下一码字。例如，000 -> 001 -> 011 -> 010 -> 110 -> 111 -> 101 -> 100。 **问题五** 编辑距离定义了一个衡量两个字符串转换成彼此所需的最少插入、删除和替换操作数。具体算法通常采用动态规划实现，状态转移方程为dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + (s1[i-1] != s2[j-1]))，其中s1和s2是两个字符串，dp[i][j]表示s1的前i个字符转换到s2的前j个字符的最小操作数。