SCUT2009数据结构试卷

选择题

(1) 一个算法必须具备或做到以下所有条件，除了： (C)

(A) 正确
(B) 有限
(C) 模棱两可
(D) 具体步骤

解答：一个算法的定义是必须是正确的、有明确步骤、且在有限时间内完成。但算法绝不能是模棱两可的，因此选择 (C) 模棱两可。

(2) 选择与 \(n\) 变大时最为低效的算法增长率： (C)

(A) \(2n^3\)
(B) \(2^n\)
(C) \(n!\)
(D) \(20n^2 \log n\)

解答：比较这些函数的增长速度，随着 \(n\) 的增大，阶乘 \(n!\) 增长得最快，因此是最为低效的算法。选择 (C)。

(3) 如果一个数据元素需要 8 字节，一个指针需要 6 字节，那么当非空元素的比例小于约为多少时，链表表示将比标准数组表示更节省空间？ (B)

(A) 1/4
(B) 4/7
(C) 4/5
(D) 3/4

解答：设非空元素的比例为 \(x\)，链表的空间复杂度为每个元素 8 字节加 6 字节指针，共 \(14x\) 字节；数组的空间复杂度为 8 字节。通过解不等式 \(14x < 8\)，可得 \(x < 4/7\)。因此选择 (B) 4/7。

(4) 以下四个选项中哪一个陈述是不正确的： (B)

(A) 快速排序是一种不稳定的排序算法。
(B) 在非空二叉树中，空子树的数量比节点数多一个。
(C) 我的算法的最坏情况是当 \(n\) 越来越大时，因为那是最慢的。
(D) 集群是文件分配的最小单位，因此所有文件都占据集群大小的倍数。

解答：(B) 选项不正确。在非空二叉树中，空子树的数量实际上等于节点数加一，而不是节点数多一个。因此选择 (B)。

(5) 以下哪一项陈述是正确的： (C)

(A) 一般树可以转换为二叉树，且根节点同时具有左孩子和右孩子。
(B) 在二叉搜索树（BST）中，节点可以通过先序遍历来进行排序。
(C) 在二叉搜索树（BST）中，任意节点的左孩子小于右孩子，但在堆中，任意节点的左孩子可以小于或大于右孩子。
(D) 堆必须是满二叉树。

解答：(C) 是正确的。在二叉搜索树中，左孩子总是小于右孩子，但在堆中，左右孩子的值相对不做任何规定。因此选择 (C)。

(6) 磁盘程序设计的黄金法则是： (B)

(A) 改进基本操作。
(B) 最小化磁盘访问次数。
(C) 消除递归调用。
(D) 减少主内存的使用。

解答：在磁盘程序设计中，磁盘访问通常是最耗时的操作，因此减少磁盘访问的次数是提高性能的关键。选择 (B)。

(7) 给定数组 \(A[m][n]\)。假设 \(A[0][0]\) 存储在地址 644（十进制），\(A[2][2]\) 存储在地址 676（十进制），且每个元素占据一个空间单位。那么元素 \(A[4][4]\) 的位置是： (D)

(A) 692
(B) 695
(C) 650
(D) 708

解答：根据题意，\(A[2][2]\) 和 \(A[0][0]\) 之间的差距为 \(676 - 644 = 32\) 个空间单位，即从 \(`A[0][0]`\) 开始，2 行 2 列的偏移量是 32。因此，按照相同的计算，\(A[4][4]\) 的位置是 \(644 + 64 = 708\)。选择 (D)。