SCUT2005

Select the correct choice.

Which statement is not true among the following four : ( )

The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.
A cluster is the smallest unit of allocation for a file, so all files are a multiple of the cluster size.
The best case for my algorithm is n=1 because that is the fastest.
The number of 4-node binary trees in different shape is 14.

答案：

不正确的选项是 (C)。

解释：

(A)：正确在一个非空的满二叉树中，叶子节点的数量 (LL) 比内部节点的数量 (II) 多 1，公式为 L=I+1L = I + 1。这是满二叉树的一个基本性质。
(B)：正确在文件系统中，簇（Cluster） 是文件分配的最小单位。因此，所有文件的大小通常是簇大小的整数倍。
(C)：不正确 算法的最优情况（best case） 不一定是当 n=1n = 1 时。最优情况依赖于算法的性质和输入数据。例如，在排序算法中，最优情况可能是输入数据已经是有序的（而非 n=1n = 1）。
(D)：正确具有 n=4n = 4 个节点且形状不同的二叉树数量由卡塔兰数（Catalan Number）计算，结果为 C4=14C_4 = 14。

Which of the following cases is fit for a list L to be implemented by link structure?( )

It needs to modify the element values frequently.
It needs to insert or delete elements in the list frequently.
There are lots of elements in the list
The structure of the element in the list is complex.

答案：(B)

答案解释：

1. 如果需要频繁修改元素值，基于数组的实现可能更高效，因为数组可以直接访问元素进行修改。
1. 链表非常适合频繁地插入和删除元素。在链表中插入或删除一个元素只需要调整少量指针，而在数组中可能需要移动大量元素，所以当需要频繁地在列表中插入或删除元素时，适合用链表结构实现列表，答案是(B)。
1. 列表中元素数量多并不一定意味着就适合用链表，还需要考虑操作类型等其他因素。
1. 列表中元素结构的复杂程度并不直接决定是否要用链表来实现。

In the following sequences of key value, which is a heap? ( )

16, 72, 31, 23, 94, 53 (B) 94, 23, 31, 72, 16, 53
16, 53, 23, 94, 31, 72 (D) 16, 23, 53,31, 94, 72

答案：(D)

答案解释：堆是一种满足堆性质的完全二叉树。对于大顶堆，每个节点都大于等于它的子节点；对于小顶堆，每个节点都小于等于它的子节点。

1. \(16, 72, 31, 23, 94, 53\)不是堆。例如\(16<72\)，但\(72\)在这个序列中的位置不符合大顶堆的要求。
1. \(94, 23, 31, 72, 16, 53\)不是堆。因为\(23<94\)，且\(23\)的位置不符合大顶堆规则。
1. \(16, 53, 23, 94, 31, 72\)不是堆。例如\(16<53\)，\(53\)位置不符合大顶堆特性。
1. \(16, 23, 53,31, 94, 72\)是小顶堆。每个父节点都小于等于它的子节点。

The two main aspects of algorithm analysis is ( )?

Correctness and shortness (B) Time cost and space cost
Data complexity and program complexity (D) Readability and revisability

答案：(B)

答案解释：算法分析主要关注两个重要的方面，其一是时间成本，也就是算法运行所花费的时间，通过时间复杂度等指标来衡量，例如分析算法在不同规模数据下运行时间随数据量增长的变化趋势，像简单的遍历算法时间复杂度可能是线性的，而一些高效排序算法平均时间复杂度能达到对数线性级别等；其二是空间成本，即算法执行过程中所占用的存储空间大小，用空间复杂度来描述，比如有些算法在处理数据时需要额外开辟大量辅助空间，而有的则可以在较小的固定空间内完成操作。所以算法分析的两个主要方面是时间成本和空间成本，答案选 (B)。 (A) 选项中，正确性确实是算法很重要的特性，但短 ness（这里可能指简短程度）并非算法分析重点关注的核心方面，主要还是聚焦在资源消耗情况上。 (C) 选项里的数据复杂度不是常规算法分析着重考量的标准说法，程序复杂度表述也比较宽泛，不符合算法分析的两个关键维度。 (D) 选项的可读性和可修订性更多是关乎代码编写质量、维护便利性等方面，和对算法本身运行效率、资源占用等分析的主要方面不相关。