06年A卷

选择题

题目没有变化，自己练一下？

一个算法必须做以下所有事情，除了：
1. Correct
2. Composed of concrete steps
3. Ambiguous
4. Terminate
选择随着 $n$ 增大而对应于最有效算法的增长率：
1. $ 20n $
2. $ 5 n $
3. $ 2^n $
4. $ 10n^2 $
如果一个数据元素需要4字节，一个指针需要4字节，则在非零元素的比例小于约多少时，链表表示法将比标准数组表示法更节省空间？
1. 75%
2. 25%
3. 15%
4. 50%
以下哪一陈述是不正确的？
1. The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.
2. A cluster is the smallest unit of allocation for a file, so all files are a multiple of the cluster size.
3. The best case for my algorithm is $ n = 1 $ because that is the fastest.
4. The number of 4-node binary trees in different shape is 14.
减少磁盘程序所需时间的最有效方法是：
1. Improve the basic operations.
2. Minimize the number of disk accesses.
3. Eliminate the recursive calls.
4. Reduce main memory use.
我们使用父指针表示法来解决一般树的哪一个问题？
1. Shortest paths
2. General tree traversal
3. Equivalence classes
4. Exact-match query
以下哪一陈述是正确的？
1. In a BST, the left child of any node is less than the right child, and in a heap, the left child of any node is less than the right child.
2. In a BST, the left child of any node could be less or greater than the right child, but in a heap, the left child of any node must be less than the right child.
3. In a BST, the left child of any node is less than the right child, but in a heap, the left child of any node could be less than or greater than the right child.
4. In both a BST and a heap, the left child of any node could be either less than or greater than the right child.
替代选择排序的功能是：
1. Select the maximal element.
2. Generate the initial merge file.
3. Merge the sorted file.
4. Replace some record.
树索引方法是为了克服哈希中的什么缺陷？
1. Inability to handle range queries.
2. Inability to handle updates.
3. Inability to handle large data sets.
4. None of all above.
假设我们有8条记录，键值从A到H，且它们最初按字母顺序排列。现在，考虑应用以下访问模式：F D F G E G F A D F G E。如果列表按“移至前面”启发式组织，则最终的列表将是：
1. F G D E A B C H
2. E G F D A B C H
3. A B F D G E C H
4. F D G E A B C H

答案：CBDCB CCBAB

程序填空题

(1) 使用 C++ 抽象类声明一个列表，编写一个函数交换列表右部分的前两个元素：

// 交换当前元素和下一个元素的顺序

void switch(List<Elem> L1) {
  Elem temp;
  if (!L1.remove(temp))  // 如果列表为空或没有下一个元素
    cout << "ERROR";  
  else {
   	L1.next();
	L1.insert(temp);
  }
}

解释：

L1.isEmpty() 用于检查列表是否为空。
L1.next() 用于获取列表中的下一个元素。
L1.insert() 用于插入元素。
如果列表为空或没有下一个元素，输出错误。

(2) 给定一个按值排序的整数数组，修改二分查找函数，返回 K 不在数组中时最大值小于 K 的元素的位置。若数组中最小值大于 K，则返回错误：

// 返回小于等于 K 的最大元素的位置

int newbinary(int array[], int n, int K) {
  int l = -1;
  int r = n;  // l 和 r 超出数组边界
  while (l + 1 != r) {  // 当 l 和 r 相遇时停止
    int i = (l + r) / 2;  // 查看子数组的中间值
    if (K < array[i])    r = i;     // 在左半部分
    if (K == array[i])   return i;  // 找到 K
    if (K > array[i])    l = i;     // 在右半部分
  }
  // 如果 K 不在数组中，返回第一个小于 K 的元素的位置
  return l;  // 如果 l = -1，则没有比 K 小的值
}

解释：

l 和 r 分别是左右边界，初始时设置为超出数组范围。
使用二分查找来查找最接近但小于 K 的元素。
当 K 不在数组中时，l 将指向比 K 小的最大值。
如果数组中最小的值大于 K，则返回 -1。

(3) 一个有 100 个内部节点的完全 2 叉树有多少个节点？

答案： 201

解释：

完全二叉树的节点数量公式是：总节点数 = 内部节点数 + 叶子节点数。
对于一棵二叉树，内部节点数与叶子节点数之间的关系是：叶子节点数 = 内部节点数 + 1。
所以，当内部节点数为 100 时，叶子节点数为 100 + 1 = 101。
因此，总节点数为：100 + 101 = 201。

复杂度分析

(1)

sum = 0;
for (i = 0; i < 3; i++)         // Outer loop runs 3 times
    for (j = 0; j < n; j++)     // Inner loop runs n times
        sum++;                   // Constant time operation

解决方案： Θ(n)

解释：

外部循环运行 3 次，这是常数操作。
内部循环运行 n 次。
所以，总的时间复杂度是 3 * n = Θ(n)，常数因子可以忽略，因此是 Θ(n)。

(2)

sum = 0;
for (i = 0; i < n; i++)         // Outer loop runs n times
    for (j = 0; A[j] != i; j++) // Inner loop runs up to j = i
        sum++;                   // Constant time operation

解决方案： Θ(n²)

解释：

外部循环运行 n 次。
内部循环的迭代次数取决于 A[j] != i 条件，在最坏情况下，内部循环最多执行 i 次。
- 对于 i = 0，内循环运行 0 次；对于 i = 1，内循环运行 1 次，依此类推。
- 所以，总的迭代次数为 0 + 1 + 2 + ... + (n-1) = n(n-1)/2，这个是一个二次增长的序列。
因此，时间复杂度是 Θ(n²)。

(3)

sum = 0;
if (EVEN(n))                    // If n is even, execute the for loop
    for (i = 0; i < n; i++)     // Loop runs n times
        sum++;                   // Constant time operation
else
    sum = sum + n;              // This is a constant time operation