SCUT2003

Select the correct choice.

(3) 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.
The number of empty subtrees in a non-empty binary tree is equal to the number of nodes in the tree.
A cluster is the smallest unit of allocation for a file, so all files are a multiple of the cluster size.
The number of 3-node binary trees in different shape is 5.

选项 A

在非空满二叉树中，设内部节点数为 \(n\)，根据满二叉树的性质，其节点总数 \(N = 2n + 1\)（满二叉树节点总数和内部节点数的关系）。而叶子节点数等于 \(n + 1\)（可以通过对满二叉树的结构分析或者利用公式推导得出），所以叶子节点数确实比内部节点数多 1，该选项说法正确。

选项 B

对于非空二叉树，每一个节点（除了根节点外）都对应着一个空的子树（因为每个节点要么有两个子节点，要么有一个子节点，要么没有子节点，没有子节点的地方就是空的子树），再加上根节点也可以看作对应着两个空的子树（从概念上理解，它的两个“潜在”子树位置初始为空），所以空的子树数量是节点数量加 1，而不是等于节点数量，该选项说法错误。

选项 C

在文件系统中，簇（cluster）是磁盘分配的最小单位，文件在磁盘上存储时是以簇为基本单位进行分配的，所以文件所占用的磁盘空间一定是簇大小的整数倍，该选项说法正确。

选项 D

不同形态的 3 个节点的二叉树，其形态数量可以通过列举或者利用卡特兰数（Catalan number）相关公式来计算。对于 3 个节点的二叉树，其形态数量确实为 5 种，可以手动画出这 5 种不同形态的二叉树来验证，该选项说法正确。

答案：B

答案解释：因为非空二叉树中空子树的数量是节点数量加 1，并非等于节点数量，而选项 A、C、D 的描述均符合对应概念和性质的正确表述，所以选择 B 选项作为说法不正确的那一项。

Fill the blank with correct C++ codes: (10 scores)

Using the C++ abstract class declaration for a list, write a function to interchange the first two elements in the right partition of a list:

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

在这个问题中，我们需要使用 C++ 抽象类声明来实现一个函数，该函数交换列表中右部分的前两个元素。首先，我们要补充代码中的空白部分。下面是每个空白的解释和填写：

第一个空白应该检查列表是否为空或列表的元素不足两个。如果列表为空或元素不足，则输出错误消息。
第二个空白是获取列表中第一个元素的引用，可以通过列表的迭代器或相应的成员函数来访问。
第三个空白是交换这两个元素。

基于以上分析，代码的填写应该如下：

// Interchange the order of current and next elements
void switch(List<Elem> L1) {
    Elem temp;

    // Check if the list has fewer than 2 elements
    if (L1.size() < 2) {
        cout << "ERROR";
        return;  // Return early if there's an error
    }

    // Get references to the first two elements in the list
    Elem& first = L1.get(0);  // Assuming `get(index)` retrieves the element at `index`
    Elem& second = L1.get(1); // Get the second element

    // Swap the two elements
    temp = first;
    first = second;
    second = temp;
}

中文解释：

检查列表是否为空或元素不足：首先检查列表中元素的数量是否少于 2，如果是，就输出错误信息，并提前返回。
获取列表中的前两个元素：通过 L1.get(0) 获取第一个元素的引用，通过 L1.get(1) 获取第二个元素的引用。
交换元素：通过一个临时变量 temp 来交换这两个元素。

需要注意的是，代码中假设 L1.get(index) 是列表类的成员函数，可以通过该函数获取指定位置的元素。

Trace by hand the situation of the array `(int a[] = {72,6,57,88,60,42,83,73,48, 85})`using Quicksort algorithm. The pivot is 60 in the first pass, the second is 6 and 73, the third is 57 and 88 and so on till the algorithm is finished.

第一轮：{48, 6, 57, 42, 60, 88, 83, 73, 72, 85}
第二轮：{6, 42, 57, 48, 60, 72, 73, 85, 88, 83}
第三轮：{6, 42, 48, 57, 60, 72, 73, 85, 83, 88}
- 第三轮：以 85 为pivot，得到{6, 42, 48, 57, 60, 72, 73, 83, 85, 88}，完成。