### 清华大学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;`中，需要通过一系列栈操作来实现前缀表达式转换为后缀表达式的过程。
- 具体实现细节略。
