清华大学96年考研题

### 清华大学96年考研题解析 #### 一、计算下列各程序中语句＠的频度 1. **程序分析**: - **循环条件**: `while p < n do` - **更新规则**: - `p := 2 * p` (每次循环后，`p` 的值翻倍) - `k := k + 1` (计数器每次增加1) **解析**: - 当`p`首次达到或超过`n`时，循环结束。 - 假设初始时`p = 1`，那么`p`达到`n`需要的次数为`log₂n`。 - 因此，语句`＠:k:=k+1`的频度为`log₂n`。 2. **程序分析**: - 外层循环: `for j := 1 to n do` - 内层循环: `for x := i to n do` **解析**: - 对于外层循环中的每个`j`，内层循环将执行`n - i + 1`次。 - 总频度计算如下: - 第一次内层循环执行`n - 0 + 1 = n + 1`次 - 第二次内层循环执行`n - 1 + 1 = n`次 - …… - 最后一次内层循环执行`n - (n - 1) + 1 = 2`次 - 总频度为`∑(n + 1 - i)`，其中`i`从`0`到`n - 1`。 - 这是一个等差数列求和问题，其公式为`n(n + 3) / 2`。 - 因此，语句`＠:k:=k+1`的频度为`n(n + 3) / 2`。 #### 二、写出和下列递归过程等价的非递归过程 **递归过程**: ```pascal PROCEDURE test(VAR sum: integer); VAR a: integer; BEGIN read(a); IF a = 0 THEN sum := 1 ELSE BEGIN test(sum); sum := sum * a END; write(sum) END; ``` **非递归过程**: ```pascal PROCEDURE testNonRecursive(VAR sum: integer); VAR a: integer; BEGIN read(a); IF a <> 0 THEN BEGIN sum := 1; WHILE a <> 0 DO BEGIN read(a); sum := sum * a END END; write(sum) END; ``` #### 三、假设按低下标优先存储整形数组A（-3：8，3：5，-4：0，0：7）时，第一个元素的字节存储地址是100，每个整数占4个字节，问A（0，4，-2，5）的存储地址是什么？ **解析**: - 数组元素`A[i, j, k, l]`的地址计算公式为: `base + [i - low1] * stride1 + [j - low2] * stride2 + [k - low3] * stride3 + [l - low4] * stride4`，其中`stride`表示步长。 - 给定数组的维度为`(12, 3, 5, 8)`，因此`stride1 = 3 * 5 * 8 * 4`，`stride2 = 5 * 8 * 4`，`stride3 = 8 * 4`，`stride4 = 4`。 - 对于`A[0, 4, -2, 5]`，代入公式得到存储地址为: - `base = 100` - `stride1 = 3 * 5 * 8 * 4 = 480` - `stride2 = 5 * 8 * 4 = 160` - `stride3 = 8 * 4 = 32` - `stride4 = 4` - 地址`= 100 + (0 - (-3)) * 480 + (4 - 3) * 160 + ((-2) - (-4)) * 32 + (5 - 0) * 4 = 100 + 3 * 480 + 1 * 160 + 2 * 32 + 5 * 4 = 100 + 1440 + 160 + 64 + 20 = 1784` #### 四、地址为（1664）大小为（128）的存储块的伙伴地址是什么？地址为（2816）大小为（64）的存储块的伙伴地址是什么？ **解析**: - 在伙伴系统中，两个连续的存储块如果大小相同，则它们互为伙伴。 - 对于地址为`1664`大小为`128`的存储块，其二进制表示为`11010001000`。 - 下一个大小相同的伙伴块的地址为`11010001001`，即`1665`。 - 对于地址为`2816`大小为`64`的存储块，其二进制表示为`101100000000`。 - 下一个大小相同的伙伴块的地址为`101100000001`，即`2817`。 #### 五、试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过2.0。 **解析**: - 使用线性探测法解决冲突。 - 哈希函数可以采用除留余数法，例如`hash(key) = key mod 17`。 - 关键字列表为：`["CHA", "CAI", "LAN", "WEN", "LONG", "ZHAO", "WU", "LIU", "CHEN", "LI", "WANG", "CAO", "YUN", "CHANG", "YANG"]`。 - 哈希表大小设置为17，可以满足平均查找长度不超过2.0的要求。 #### 六、已知快速排序和归并排序的算法分别如下所示 **解析**: - 快速排序算法中，`qkpass`负责对子数组进行划分，而`qksort`则负责递归地对子数组进行排序。 - 归并排序算法中，`mergesort`负责递归地对子数组进行排序，而`merge`则负责合并两个有序子数组。 - 对于给定的关键字序列进行排序，具体步骤略。 #### 七、令G=（V，E）为一个有向图，编写一个给图G中每一个顶点赋以一个整型序号的算法，并满足以下条件：若从顶点I年顶点j有一条弧则应使I<j。 **解析**: - 可以采用拓扑排序来实现这一要求。 - 统计每个顶点的入度。 - 然后，从入度为0的顶点开始，依次删除与其相关的边，并更新其余顶点的入度。 - 重复这一过程直到所有顶点都被访问。 #### 八、试利用下列栈和串的基本操作完成下述填空题 **解析**: - 需要根据题目描述中的要求，利用给定的操作来完成填空。 - 例如，在`FUNC invert(pre:string; varexp:string):Boolean;`中，需要通过一系列栈操作来实现前缀表达式转换为后缀表达式的过程。 - 具体实现细节略。