03年数据结构试卷

选择题

问题 1

题目：一个算法必须满足以下所有条件，除了：

算法是不可以含糊不清的。

正确
由具体步骤组成
含糊不清
有终止条件

答案：

(C) 含糊不清

解释：

一个正确的算法必须能准确解决问题，得到正确的结果。
一个算法应该由具体步骤组成，每一步都必须清晰明确。
算法必须有明确的终止条件，否则可能进入无限循环或无法得出结果。
而含糊不清是算法的一个反面，它不能有效地定义和执行，因此并不符合算法的定义。

问题 2

题目：选择与最有效的算法（当 n 较大时）相对应的增长速率：

要选择最小的增长速率。

5n
20 log n
2n²
2ⁿ

答案：

(B) 20 log n

解释：

5n：线性增长，随着 n 增大，增长速度适中。
20 log n：对数增长，比线性增长慢得多，尤其在 n 较大时，比多项式增长要快。
2n²：二次增长，随着 n 增大，增长速度较快。
2ⁿ：指数增长，随着 n 增大，增长速度非常快，远远超过其他增长速率。

因此，当 n 较大时，20 log n 是最有效的增长速率，因为对数增长比线性、多项式和指数增长都要慢得多。

问题 3

题目：以下四个陈述中，哪个是不正确的？

注意空子树的数量是比节点数量要大1的。

非空完全二叉树中的叶子节点数量比内部节点数量多一个。
非空二叉树中的空子树数量等于树中的节点数量。
簇是文件分配的最小单位，因此所有文件的大小都是簇大小的倍数。
不同形状的 3 节点二叉树的数量是 5。

答案：

(B) 非空二叉树中的空子树数量等于树中的节点数量。

解释：

(A) 这是正确的。对于任何完全二叉树，内部节点数量为叶子节点数量减一，因此完全二叉树中叶子节点的数量比内部节点多一个。
(B) 这是错误的。在二叉树中，空子树的数量等于节点的数量加一，因为每个节点有两个子树（一个左子树和一个右子树），其中空子树指没有子节点的子树（叶节点的子树是空的）。
(C) 这是正确的。簇是文件系统分配的最小单位，因此所有文件的大小必须是簇大小的整数倍。
(D) 这是正确的。对于 3 个节点的二叉树，可以有 5 种不同的形状，具体可以通过手动绘制来确认。

问题 4

题目：减少磁盘程序所需时间的最有效方法是：

和上一篇试卷是一样的。

改进基本操作。
最小化磁盘访问次数。
消除递归调用。
减少主存使用。

答案：

(B) 最小化磁盘访问次数。

解释：

(A) 改进基本操作通常会提升程序的效率，但在磁盘操作中，最重要的瓶颈通常是磁盘访问本身，优化基本操作对减少磁盘访问的影响有限。
(B) 这是正确的。在磁盘操作中，磁盘访问通常是性能的瓶颈。最小化磁盘访问次数可以显著提高程序的性能，因为磁盘访问相对于内存访问来说非常缓慢。
(C) 消除递归调用可能会减少堆栈操作，但它不会直接影响磁盘访问次数，因此在磁盘操作的优化中并不是最有效的方式。
(D) 减少主存使用虽然能帮助减少内存压力，但对减少磁盘访问次数没有直接影响，因此不是最有效的优化方法。

问题 5

题目：树索引方法是为了克服哈希中的哪个缺点？

一样的。

无法处理范围查询。
无法处理更新。
无法处理大数据集。
以上都不是。

答案：

(A) 无法处理范围查询。

解释：

哈希是一种非常高效的数据结构，适用于精确查找操作，但它不能直接支持范围查询（例如查找大于某个值的所有元素）。树索引（如B树、B+树等）能够高效地处理范围查询，因为它们保持有序结构，可以支持对连续区间的数据进行有效查询。
(B) 更新操作并不是哈希的主要问题，虽然哈希表在处理某些更新时可能会遇到冲突，但它并不会限制更新操作的执行。
(C) 哈希表的处理效率对于大数据集通常是很好的，尤其是负载因子合理时，它可以处理非常大的数据集。
(D) 选项A是正确的，因此D是错误的。

问题 6

题目：当指针需要4字节，而数据元素需要12字节时，链表实现比基于数组的列表实现节省空间的条件是：

非常普通的一个分析。

数组小于 1/3 满。
数组小于 2/3 满。
数组小于一半满。
数组小于 3/4 满。

答案：

(D) 数组小于 3/4 满。

解释：

链表实现：在链表中，每个元素都包含一个数据部分和一个指针部分，因此总空间为 数据元素大小 + 指针大小，在这个例子中为 12 + 4 = 16 字节。
数组实现：为12个字节。
稍微使用一下除法即可解决。

问题 7

题目：以下哪个是正确的陈述：

熟悉两种结构的特点。

在二叉搜索树（BST）中，任何节点的左子节点都小于右子节点，在堆中，任何节点的左子节点都小于右子节点。
在二叉搜索树（BST）中，任何节点的左子节点都小于右子节点，但在堆中，任何节点的左子节点可能小于或大于右子节点。
在二叉搜索树（BST）中，任何节点的左子节点可能小于或大于右子节点，但在堆中，任何节点的左子节点必须小于右子节点。
在二叉搜索树（BST）和堆中，任何节点的左子节点可能小于或大于右子节点。

答案：

(B) 在二叉搜索树（BST）中，任何节点的左子节点都小于右子节点，但在堆中，任何节点的左子节点可能小于或大于右子节点。

解释：

二叉搜索树（BST）：对于BST的任何节点，左子树的所有节点都小于该节点，右子树的所有节点都大于该节点，因此BST中的左子节点一定小于右子节点。
堆（Heap）：堆有两种形式：最大堆（Max-Heap）和最小堆（Min-Heap）。对于最大堆，父节点的值大于或等于任何子节点的值，而对于最小堆，父节点的值小于或等于任何子节点的值。因此，堆中并不一定保证左子节点小于右子节点，它依赖于堆的性质，但不要求左右子节点有特定大小关系。

因此，选项B是正确的。

问题 8

题目：哪一个是数据类型作为软件组件的实现？

抽象数据类型就是。

抽象数据类型（ADT）
实际数据类型（Real Data Type）
类型（Type）
数据结构（Data Structure）

答案：

(A) 抽象数据类型（ADT）

抽象数据类型（ADT）：抽象数据类型（ADT）是描述数据和对数据操作的集合，它只关心数据的操作和行为，而不关心数据的具体实现。ADT 提供了操作的接口，但不提供实现细节，因此它是“数据类型”的一种抽象表达，可以理解为软件组件的实现方式。

问题 9

题目：假设我们有八个记录，键值从 A 到 H，并且它们最初按照字母顺序排列。现在，考虑以下访问模式的结果：F D F G E G F A D F G E，如果列表使用“移至前端（move-to-front）”启发式算法进行组织，则最终的列表将是：

如果访问到，就直接移动到最前端。

F G D E A B C H
E G F D A B C H
A B F D G E C H
F D G E A B C H

答案：

(D) F D G E A B C H

解释：

移至前端启发式（Move-to-Front Heuristic）：每当访问一个元素时，将该元素移动到列表的前端。
初始列表是：A B C D E F G H
- 访问 F：F 被移动到前端，列表变为：F A B C D E G H
- 访问 D：D 被移动到前端，列表变为：D F A B C E G H
- 访问 F：F 被移动到前端，列表变为：F D A B C E G H
- 访问 G：G 被移动到前端，列表变为：G F D A B C E H
- 访问 E：E 被移动到前端，列表变为：E G F D A B C H
- 访问 G：G 被移动到前端，列表变为：G E F D A B C H
- 访问 F：F 被移动到前端，列表变为：F G E D A B C H
- 访问 A：A 被移动到前端，列表变为：A F G E D B C H
- 访问 D：D 被移动到前端，列表变为：D A F G E B C H
- 访问 F：F 被移动到前端，列表变为：F D A G E B C H
- 访问 G：G 被移动到前端，列表变为：G F D A E B C H
- 访问 E：E 被移动到前端，列表变为：E G F D A B C H

最终的列表为：E G F D A B C H，所以选项 (B) 是正确的。

问题 10

题目：给定一个数组 A 存放的位置是：

如果可以画图来解决，就会更好办了。

答案：

(B) 695

解释：

假设数组 A 的大小是 m x n，并且数组是按行优先存储的（即按行存储）。我们可以使用行优先存储公式来确定元素的位置。

已知：

A[0][0]位于 644
A[2][2]位于 676

每个元素占一个存储单元。由于 A[2][2]位于位置 676，而 A[0][0]位于位置 644，因此从A[0][0]到 A[2][2]之间的存储单位数是： $ 676 - 644 = 32 $ 这意味着每行有 15 个元素。

现在，计算A[3][3]的位置。A[3][3]相对于A[0][0] 的偏移量是： $ 3 + 3 = 48 $ 因此，A[3][3] 的位置是： $ 644 + 48 = 692 $

所以，A[3][3]位于 692，因此选项 (A) 是正确的。

程序填空题

问题 1

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

先看看能不能移除，如果可以就移除，回到首部，插入即可。

// Interchange the order of current and next elements
void switch(List<Elem> L1) {
  Elem temp;
  if ______________________  cout<<"ERROR";
  ____________;
  ____________;
}

答案：

// Interchange the order of current and next elements
void switch(List<Elem> L1) {
  Elem temp;
  if (L1.isEmpty() || L1.size() < 2)  // Check if the list is empty or has less than 2 elements
    cout << "ERROR";  // If so, print error message
  else {
    L1.moveToFirst();  // Move to the first element in the right partition
    temp = L1.current();  // Store the value of the current element
    L1.next();  // Move to the next element
    L1.insert(temp);  // Insert the current element at the next position
    L1.remove();  // Remove the original first element
  }
}

解释：

检查错误条件：我们需要确保列表不为空且至少有两个元素可供交换。如果列表为空或元素不足两个，应该输出错误信息。
移动到第一个元素：假设右部分从列表的第一个元素开始，调用 moveToFirst() 将指针移动到列表的第一个元素。
交换元素：
- 通过 current() 获取当前元素的值，并使用临时变量 temp 存储它。
- 然后调用 next() 移动指针到下一个元素。
- 使用 insert() 将 temp 的值插入到当前指针的位置（即原来的第二个位置）。
- 最后，调用 remove() 删除原来指向第一个元素的节点，完成交换。

这样就能成功交换列表中右部分的前两个元素。

问题 2

题目：给定一个存储按值排序的整数的数组，修改二分查找例程，以便当 K 不在数组中时，返回第一个小于 K 的整数的位置。如果数组中的最小值大于 K，则返回 ERROR。

二分需要灵活掌握。

// Return position of greatest element <= K
int newbinary(int array[], int n, int K) {
  int l = -1;
  int r = n;             // l and r beyond array bounds
  while (l + 1 != r) {     // Stop when l and r meet
    __________________________;     // Look at middle of subarray
    if (K < array[i])    _________;       // In left half
    if (K == array[i])   _________;    // Found it
    if (K > array[i])    _________;       // In right half
  }
  // Search value not in array
  __________;              // l at first value less than K 
                         // l=-1, no value less than K
}

答案：

// Return position of greatest element <= K
int newbinary(int array[], int n, int K) {
  int l = -1;
  int r = n;             // l and r beyond array bounds
  while (l + 1 != r) {     // Stop when l and r meet
    int i = (l + r) / 2;  // Look at middle of subarray
    if (K < array[i])    r = i;  // In left half
    if (K == array[i])   return i;    // Found it
    if (K > array[i])    l = i;  // In right half
  }
  // Search value not in array
  if (l == -1) return ERROR; // l=-1, no value less than K
  return l;              // l at first value less than K 
}

解释：

初始化：
- l = -1 和 r = n 表示数组的初始范围，l 和 r 超出了数组的索引边界。
二分查找：
- 在每次迭代中，通过 (l + r) / 2 计算中间索引 i，查看该位置的值 array[i]。
- 如果 K < array[i]：则 K 可能在左半部分，因此更新右边界 r = i。
- 如果 K == array[i]：找到了 K，直接返回该位置 i。
- 如果 K > array[i]：则 K 可能在右半部分，因此更新左边界 l = i。
最终检查：
- 当 l + 1 == r 时，意味着二分查找结束。
- 如果此时 l == -1，说明 K 比数组中的最小值还小，返回 ERROR。
- 否则，l 将指向第一个小于 K 的位置。

复杂度：

时间复杂度为 O(log n)，符合二分查找的标准复杂度。

问题 3

题目：在具有 n 个节点的树中，最短树的高度是 ____________，而最高树的高度是 ____________（假设一棵单节点树的高度为 1）。

注意，这是一道有坑的题目，因为他并没有说究竟是几叉树。

答案：

最矮高度：

对于 n = 0，树不存在，因此高度为 0。
对于 n = 1，只有一个节点，树的高度为 1。
对于n大于或等于2时，为2；

最高高度： n

建堆问题

题目：运行 buildheap 操作后，给定数组 [4, 2, 5, 8, 3, 6, 10, 14]，展示最终的最小堆（min-heap）。

O(n)的建堆是很简单的，只需要不断的从非叶子结点往下沉即可。

答案：

以下是构建最小堆的每一步堆化过程，给定初始数组 [4, 2, 5, 8, 3, 6, 10, 14]：

初始数组：

1	[4, 2, 5, 8, 3, 6, 10, 14]

构建最小堆的过程从数组的最后一个非叶子节点开始堆化。

第一步：堆化索引 3（节点 8）

       4
     /    \
    2      5
   / \    / \
  8   3  6  10
 /
14

这里节点 8 没有子节点需要堆化，堆不变。

第二步：堆化索引 2（节点 5）

       4
     /    \
    2      5
   / \    / \
  8   3  6  10
 /
14

节点 5 的左子节点 6 和右子节点 10 都比 5 大，所以不需要交换，堆不变。

第三步：堆化索引 1（节点 2）

       4
     /    \
    2      5
   / \    / \
  8   3  6  10
 /
14

节点 2 已经满足最小堆性质，无需堆化，堆不变。

第四步：堆化索引 0（节点 4）

       2
     /    \
    3      4
   / \    / \
  8   6  5  10
 /
14

节点 4 和节点 2 交换，结果变成上面的堆。接着堆化左右子树。

继续堆化：

       2
     /    \
    3      4
   / \    / \
  8   6  5  10
 /
14

最终最小堆：

       2
     /    \
    3      4
   / \    / \
  8   6  5  10
 /
14

最终最小堆是 [2, 3, 4, 8, 6, 5, 10, 14]。

构建树

构建树主要是先看前序，知道谁开头，之后去看中序遍历，知道谁在头的左边，知道谁在头的右边，之后就十分的容易了。

问题： 给定一个二叉树的先序遍历和中序遍历序列，要求绘制出该二叉树。

先序遍历序列：ABECDFGHIJ

中序遍历序列：EBCDAFHIGJ

解答过程：

我们可以通过先序遍历和中序遍历的关系来构造二叉树。具体步骤如下：

1. 理解遍历方式

先序遍历（Preorder）：根节点 -> 左子树 -> 右子树
中序遍历（Inorder）：左子树 -> 根节点 -> 右子树

2. 构造二叉树的步骤

步骤一：从先序遍历的第一个元素开始，这个元素就是根节点。

从先序遍历 ABECDFGHIJ 中可以看出，根节点是 A（因为它是第一个出现的元素）。

步骤二：在中序遍历中找到根节点 A，它将中序遍历分成了左子树和右子树。

在中序遍历 EBCDAFHIGJ 中，A 左边的部分 EBCD 是左子树，右边的部分 FHIGJ 是右子树。

步骤三：递归地对左子树和右子树进行相同的操作。

步骤四：继续递归这个过程，直到树构造完成。

3. 构造出的二叉树结构

通过递归的构造过程，最终得到的二叉树如下所示：

    A
   / \
  B   F
 / \    \
E   C     G
     \    / \
      D  H   J
          \   
           I

2-3树问题：

普通的插入，不过由于数据有点大，过程会有一些繁琐。

给定一系列记录，其键值为整数。记录按以下顺序到达：C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J。展示插入这些记录后得到的2-3树。

答案与解释：

在2-3树中，每个节点可以包含1个或2个键，并且有2或3个子节点。我们依次将记录插入2-3树，并遵循以下规则：

如果当前节点有空位，直接插入新的键。
如果节点已满，进行分裂，将中间键提升到父节点。

我们根据给定的顺序插入记录并展示最终结果：

插入过程：

这整个过程十分的繁琐，一定要多练，稍有不慎，就有可能出错。

哈希问题：

使用闭合哈希（带双重哈希解决冲突）将以下键值插入到一个包含11个槽位（槽位编号为0到10）的哈希表中。使用的哈希函数为H1和H2，定义如下。你需要在插入所有八个键值后，展示哈希表的状态。并确保说明如何使用H1和H2进行哈希操作。

注意计算不要出错，有一个技巧是先算出所有的H1,H2，之后会更方便计算，也方便后来检查。

哈希函数：
H1(k) = 3k mod 11
H2(k) = (7k mod 10) + 1

键值：22, 41, 53, 46, 30, 13, 1, 67

答案：

计算哈希值：

使用哈希函数H1和H2来插入这些键值。
- 键值 22：
  H1(22) = 3 × 22 mod 11 = 66 mod 11 = 0
  插入槽位 0。
- 键值 41：
  H1(41) = 3 × 41 mod 11 = 123 mod 11 = 2
  插入槽位 2。
- 键值 53：
  H1(53) = 3 × 53 mod 11 = 159 mod 11 = 5
  插入槽位 5。
- 键值 46：
  H1(46) = 3 × 46 mod 11 = 138 mod 11 = 6
  插入槽位 6。
- 键值 30：
  H1(30) = 3 × 30 mod 11 = 90 mod 11 = 2
  槽位 2 已被占用，使用双重哈希H2：
  H2(30) = (7 × 30 mod 10) + 1 = (210 mod 10) + 1 = 0 + 1 = 1
  尝试插入槽位 (2 + 1) mod 11 = 3，插入槽位 3。
- 键值 13：
  H1(13) = 3 × 13 mod 11 = 39 mod 11 = 6
  槽位 6 已被占用，使用双重哈希H2：
  H2(13) = (7 × 13 mod 10) + 1 = (91 mod 10) + 1 = 1 + 1 = 2
  尝试插入槽位 (6 + 2) mod 11 = 8，插入槽位 8。
- 键值 1：
  H1(1) = 3 × 1 mod 11 = 3 mod 11 = 3
  槽位 3 已被占用，使用双重哈希H2：
  H2(1) = (7 × 1 mod 10) + 1 = (7 mod 10) + 1 = 7 + 1 = 8
  尝试插入槽位 (3 + 8) mod 11 = 0
  
  被占用，不断计算，占据10。
- 键值 67：
  H1(67) = 3 × 67 mod 11 = 201 mod 11 = 3
  槽位 3 已被占用，使用双重哈希H2：
  H2(67) = (7 × 67 mod 10) + 1 = (469 mod 10) + 1 = 9 + 1 = 10
  尝试插入槽位 (3 + 10) mod 11 = 2，槽位 2 已被占用，再次使用H2：
  H2(67) = 10，再次尝试插入槽位 (2 + 10) mod 11 = 1，占据1。

最终哈希表：

插入键值后的哈希表：
槽位 0: 22
槽位 1: 67
槽位 2: 41
槽位 3: 30
槓位 4: 空
槓位 5: 53
槓位 6: 46
槓位 7: 空
槓位 8: 13
槓位 9: 空
槓位 10: 1