05年数据结构B卷

和A卷其实应该没什么区别

选择题

问题 1：选择随着 $ n $ 增大而对应于最有效算法的增长率：

1. $ 10n n $
1. $ 2n^2 $
1. $ n! $
1. $ 2^n $

答案： (A) $ 10n n $

解释： 算法的时间复杂度描述了随着输入规模 $ n $ 增长，算法运行时间的变化。我们需要选择增长最慢的复杂度。按照增长率从慢到快排序：

$ n n $ 是相对较慢的增长，适用于如归并排序、快速排序等高效算法。
$ n^2 $ 是多项式时间复杂度，增长较快，适用于如冒泡排序、插入排序等。
$ 2^n $ 是指数级增长，随着 $ n $ 增长非常迅速。
$ n! $ 是阶乘增长，增长最快，常见于解组合优化问题的暴力算法。

因此，$ 10n n $ 是最慢增长的，意味着它对应的算法是最有效的。

问题 2：一个算法必须做以下所有事情，除了：

1. 由具体步骤组成
1. 正确
1. 模糊
1. 终止

答案： (C) 模糊

解释： 一个算法必须满足以下条件：

由具体步骤组成：算法必须是明确的，可以被计算机执行的操作序列。
正确：算法应该在所有可能的输入下返回正确的结果。
终止：算法必须保证在有限时间内结束，即它不能进入无限循环。

但模糊（C）不是算法的必要条件。算法应该是清晰且明确的，而不是模糊的。因此，正确答案是 (C) 模糊。

问题 3：算法分析的两个主要方面是（）？

1. 正确性和简洁性
1. 时间成本和空间成本
1. 数据复杂性和程序复杂性
1. 可读性和可修改性

答案： (B) 时间成本和空间成本

解释： 算法分析通常关注以下两个关键方面：

时间成本：算法执行所需的时间，通常通过时间复杂度来衡量。
空间成本：算法执行所需的空间，通常通过空间复杂度来衡量。

这两个方面直接影响算法的效率，尤其是当输入规模 $ n $ 增大时，时间和空间的需求是评估算法优劣的核心因素。选项 (B) 是最常见的算法分析角度。

问题 4：作为软件组件的数据类型的实现是（）？

1. 抽象数据类型（ADT）
1. 真实数据类型
1. 类型
1. 数据结构

答案是A。

问题 5：下列四个陈述中，哪一个是不正确的？

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

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

解释：

1. 正确。3 节点二叉树的不同形状有 5 种，分别是：一个根节点有两个子节点，一个根节点有一个子节点，另一个子节点有一个子节点，等等。
1. 不正确。非空二叉树的空子树的数量不是节点数，而是节点数 + 1。每个节点都有两个子树（左子树和右子树），但某些子树可能为空。所以，空子树的数量实际上是树中节点数加 1。
1. 正确。聚簇是文件系统中用于分配文件的最小单位，文件的大小通常是聚簇大小的整数倍。
1. 正确。在非空满二叉树中，叶子节点的数量比内部节点多 1，因为每个内部节点都有两个子节点，而叶子节点没有子节点。

问题 6：下列哪一项陈述是正确的？

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

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

解释：

1. 不正确。在堆中，节点的左子节点和右子节点没有固定的大小关系。堆仅要求父节点和子节点之间的某种关系（最大堆或最小堆），但左子节点和右子节点之间并没有特定的大小顺序。
1. 正确。在二叉搜索树（BST）中，左子节点小于右子节点，这是 BST 的定义。而在堆中，左右子节点之间没有特定的大小顺序，取决于堆的类型（最大堆或最小堆）。
1. 不正确。在堆中，并没有规定左子节点必须小于右子节点，只是父节点和子节点之间有大小关系。左右子节点的顺序不一定。
1. 不正确。在 BST 中，左子节点小于右子节点，这是严格的规则，而堆中并没有要求左子节点和右子节点之间有特定的关系。

因此，答案是 (B) 解释了 BST 和堆的不同特性。

问题（7）：在以下键值序列中，哪一个是堆？

选项： (A) 16, 72, 31, 23, 94, 53 (B) 94, 23, 31, 72, 16, 53 (C) 16, 53, 23, 94, 31, 72 (D) 16, 23, 53, 31, 94, 72

答案： D

解释： 堆分为大顶堆和小顶堆。大顶堆要求每个节点的值都不大于其父节点的值（除了根节点），小顶堆要求每个节点的值都不小于其父节点的值（除了根节点）。这里我们以小顶堆为例来分析（当然也可以按照大顶堆规则分析，只是本题按小顶堆规则更易判断出结果）。对于选项D，将其按照完全二叉树的形式排列（如下所示）：

       16
    /      \
  23        53
 /  \      /  \
31  94   72

可以看到16 <= 23，16 <= 53，23 <= 31，23 <= 94，53 <= 72等，满足小顶堆的性质，所以选项D是堆。而选项A、B、C按照完全二叉树排列后，均不满足堆的性质。

问题（8）：当一个指针需要3字节且一个数据元素需要6字节时，在什么情况下链表实现比基于数组的列表实现占用更少的空间？

选项： (A) 数组小于三分之一满。 (B) 数组小于三分之二满。 (C) 数组小于一半满。 (D) 数组小于四分之三满。

答案： B。

之后有很多选择题都是已经完成过的，因此就不看了。