SCUT2008

由于部分内容与 SCUT2007 重复，所以部分题目省略。

1. Select the correct choice.

Which is the realization of a data type as a software component: ( a )

An abstract data type (B) A real data type
A type (D)A data structure

答案解释：

选项 A：抽象数据类型（Abstract Data Type，简称 ADT）是对数据类型从逻辑层面进行定义和描述，它规定了数据的操作以及这些操作所遵循的规则等，但不涉及具体的实现细节，是一种将数据类型以软件组件形式进行抽象表示的概念，通过接口等方式对外呈现其功能，便于在软件设计中实现模块化和信息隐藏等，所以它体现了数据类型作为软件组件的一种实现方式，本题选 A。
选项 B：“真实数据类型”并不是一个标准的专业术语用于描述数据类型在软件组件方面的体现，不符合题意。
选项 C：“类型”是一个比较宽泛的概念，没有明确指出在软件组件层面如何实现和体现，太笼统了，不能准确回答问题。
选项 D：数据结构侧重于数据的组织和存储方式，比如数组、链表、树等是不同的数据结构，它主要关注数据元素之间的关系以及存储布局等，而不是从数据类型作为软件组件这个角度来说的，与题意不符。

We use the parent pointer representation for general trees to solve (b ) problem?

Shortest paths (B) General tree traversal
Equivalence classes (D) Exact-match query

答案解释：

选项 A：最短路径问题通常是通过特定的图算法来解决，比如 Dijkstra 算法、Floyd 算法等，和一般树使用父指针表示法并没有直接关联，所以该选项不符合。
选项 B：对于一般树采用父指针表示法时，利用父指针可以方便地实现树的遍历操作，例如可以通过从节点不断回溯到根节点（借助父指针）以及按一定顺序访问节点的方式来进行先序、中序、后序等遍历，所以它主要是为了解决一般树的遍历问题，本题选 B。
选项 C：等价类相关问题常涉及到并查集等数据结构和算法来处理，和一般树的父指针表示法没有直接联系，不符合题意。
选项 D：精确匹配查询更多地会在查找特定元素的场景中出现，比如在有序数据结构中进行二分查找等操作来实现精确匹配某个元素，与一般树的父指针表示法解决的问题不一致，所以该选项不对。

In the hash function, collision refers to ( b ).

Two elements have the same sequence number.
Different keys are mapped to the same address of hash table.
Two records have the same key. (D) Data elements are too much.

答案解释：

选项 A：“元素有相同的序号”这种说法不符合哈希函数中关于冲突概念的定义，序号不是哈希函数关注的关键所在，所以该选项不正确。
选项 B：哈希函数的目的是将不同的键尽可能均匀地映射到哈希表的不同地址，但当不同的键经过哈希函数计算后得到了相同的地址时，就发生了所谓的冲突（Collision），这正是哈希函数中冲突的准确含义，本题选 B。
选项 C：“两个记录有相同的键”这是关于记录中键值重复的情况，和哈希函数里由于不同键映射到相同地址的冲突概念不一样，不符合题意。
选项 D：“数据元素太多”只是说明了数据量的情况，与哈希函数中因为映射导致的冲突现象没有直接关联，所以该选项错误。

Given an array as A[m][n]. Supposed that A[0][0]is located at 644(10) and A[2][2]is stored at 676(10), and every element occupies one space. “(10)” means that the number is presented in decimals. Then the element A[3][3](10) is at position: ( a )

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

答案解释：

首先，我们知道在二维数组中存储是按行优先或者列优先的方式进行的，这里默认按行优先来计算（因为常规多数情况如此，且题中未明确说明按列优先）。

从 A[0][0] 到 A[2][2] ，一共经过的元素个数计算如下：前面完整的两行元素个数为 \(2 \times n\) 个（假设每行有 \(n\) 个元素），然后在第三行又经过了 \(2\) 个元素（到 A[2][2]），总共经过的元素个数就是 \(2n + 2\) 个。

已知 A[0][0] 的地址是 \(644\) ，A[2][2] 的地址是 \(676\) ，它们的地址差值就是经过的元素个数所对应的存储空间，即 \(676 - 644 = 32\) ，也就是 \(2n + 2 = 32\)，解方程可得：

\[ \begin{align*} 2n + 2 &= 32\\ 2n &= 30\\ n &= 15 \end{align*} \]

那么到 A[3][3] 时，前面完整的三行元素个数为 \(3 \times n\) 个，然后在第四行又经过了 \(3\) 个元素，总共经过的元素个数就是 \(3n + 3\) 个。

将 \(n = 15\) 代入可得经过的元素个数为 \(3 \times 15 + 3 = 48\) 个。

因为每个元素占一个空间，且 A[0][0] 起始地址是 \(644\) ，所以 A[3][3] 的地址就是 \(644 + 48 = 692\)，本题选 A。

Fill the blank with correct C++ codes

The height of the shortest tree and the tallest tree with both n nodes is respectively __

答案：\(\left\lfloor\log_{2}n\right\rfloor + 1\) and \(n - 1\)

答案解释：

1. 最短树高度分析（以二叉树为例，对于平衡的多路树思路类似且更易满足此特性）

对于具有 \(n\) 个节点的树来说，要使其高度最短，往往是接近满二叉树（或者平衡的多路树）的形态。在二叉树中，满二叉树的节点数与高度有明确的关系。高度为 \(h\) 的满二叉树，其节点数 \(N\) 满足 \(N = 2^{h} - 1\)（可以通过等比数列求和公式推导得出，每层节点数是以 \(1\) 为首项， \(2\) 为公比的等比数列）。
求解高度 \(h\) 关于节点数 \(n\) 的表达式：当我们已知节点数 \(n\) ，想求对应的最短树高度（也就是尽可能平衡时的高度），对 \(N = 2^{h} - 1\) 进行变形，可得 \(h = \log_{2}(N + 1)\) 。对于有 \(n\) 个节点的情况，此时高度 \(h\) 为 \(\log_{2}(n + 1)\) ，又因为高度是整数且向下取整后再加 \(1\) 才符合树高度从 \(1\) 开始计数的常规设定（比如只有 \(1\) 个节点时，高度为 \(1\) ，而 \(\log_{2}(1 + 1) = 1\) ，但实际树高表述习惯是 \(1\) 层，所以是 \(\left\lfloor\log_{2}n\right\rfloor + 1\) ），所以最短树高度是 \(\left\lfloor\log_{2}n\right\rfloor + 1\) 。

例如，当 \(n = 7\) 时，\(\left\lfloor\log_{2}7\right\rfloor + 1 = \left\lfloor2.807\right\rfloor + 1 = 3\) ，对应的就是高度为 \(3\) 的满二叉树或者接近满二叉树这种比较平衡的形态，节点数正好是 \(7\) 个（ \(1 + 2 + 4 = 7\) ），能保证树的高度相对最短。

2. 最高树高度分析

要使树的高度最高，那就是让树尽可能地“瘦长”，也就是每层只有 \(1\) 个节点（除了叶子节点）的情况。例如，像一个链表结构的树（可以理解为特殊的树形态），第一个节点作为根节点，然后依次每个节点只有一个子节点往下延伸，这样就形成了一个高度很高但节点分布很稀疏的树。
计算这种情况下的高度与节点数关系：对于 \(n\) 个节点，因为除了叶子节点外每层只有 \(1\) 个节点，那么从根节点开始到倒数第二层一共就有 \(n - 1\) 个节点（最后一层是叶子节点），也就意味着树的高度是 \(n - 1\) 。比如有 \(3\) 个节点，高度就是 \(2\) （根节点一层，下面连着一个子节点一层），正好符合 \(n - 1\) 的关系（ \(3 - 1 = 2\) ）。

所以，具有 \(n\) 个节点的树，其最短树高度是 \(\left\lfloor\log_{2}n\right\rfloor + 1\) ，最高树高度是 \(n - 1\) 。

Please calculate the number of binary trees in different shape with 3 nodes in total, and 4 nodes? (4 scores)

答案：

当总共有 3 个节点时，不同形态的二叉树有 5 种。
当总共有 4 个节点时，不同形态的二叉树有 14 种。

答案解释：

1. 计算有 3 个节点时不同形态二叉树的数量

我们可以通过卡特兰数（Catalan number）的公式来计算具有 \(n\) 个节点的不同形态二叉树的数量，卡特兰数的计算公式为 \(C_n = \frac{C(2n, n)}{n + 1}\)（其中 \(C(2n, n)\) 表示从 \(2n\) 个元素中选取 \(n\) 个元素的组合数），也可以通过手动分析不同结构的情况来计算。

对于 \(n = 3\) 的情况，手动分析如下：

情况一：根节点有左子树和右子树，左子树有 1 个节点，右子树有 1 个节点。此时只有 1 种形态，因为左右子树各 1 个节点，它们的排列方式只有 1 种。
情况二：根节点只有左子树，左子树有 2 个节点（这 2 个节点又可以构成不同的二叉树形态）。对于 2 个节点构成二叉树有 2 种形态（可以是左节点为根，右节点为子树；或者右节点为根，左节点为子树），所以这种情况共 2 种不同形态。
情况三：根节点只有右子树，右子树有 2 个节点，同理也有 2 种不同形态（和情况二对称）。

将上述三种情况的形态数量相加：\(1 + 2 + 2 = 5\) 种，所以 3 个节点的不同形态二叉树有 5 种。

若用卡特兰数公式计算，\(C_3 = \frac{C(6, 3)}{4}\)，先计算组合数 \(C(6, 3) = \frac{6!}{3!(6 - 3)!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20\)，再计算 \(C_3 = \frac{20}{4} = 5\)，结果一致。

2. 计算有 4 个节点时不同形态二叉树的数量

同样可以用卡特兰数公式或者通过详细分析结构来计算。

用卡特兰数公式，\(n = 4\) 时，\(C_4 = \frac{C(8, 4)}{5}\)，先求组合数 \(C(8, 4) = \frac{8!}{4!(8 - 4)!} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70\)，则 \(C_4 = \frac{70}{5} = 14\)。

手动分析结构情况（过程相对复杂些）大致如下：

情况一：根节点左右子树各有 1 个或者 2 个节点。对应四种情况，在原来高度为 1 的满二叉树再依次在四个位置插入一个节点。
情况二：根节点左子树有 0 个节点，右子树有 3 个节点。3 个节点的二叉树有 5 种不同形态（前面已算出），所以这种情况有 5 种不同形态。
情况三：根节点右子树有 0 个节点，左子树有 3 个节点，同理也有 5 种不同形态（和情况二对称）。

将这些情况的形态数量相加可得 \(4 + 5 + 5 = 14\) 种不同形态的二叉树。

综上，3 个节点的不同形态二叉树有 5 种，4 个节点的不同形态二叉树有 14 种。

Trace by hand the execution of Quicksort algorithm on the array: int a[] = {44, 77, 55, 99, 66, 33, 22, 88, 79} The pivot is 66 in the first pass, the second is 55 and 88, the third is 33 and 77, the fourth is 22, and so on till the algorithm is finished.

initial:  44, 77, 55, 99, 66, 33, 22, 88, 79
pass 1:  44 22 55 33 66 99 77 88 79
pass 2:  44 22 33 55 66 79 77 88 99
pass 3:  33 22 44 55 66 77 79 88 99
pass 4:  22 33 44 55 66 77 79 88 99
final sorted array:
        22 33 44 55 66 77 79 88 99

答案展示

快速排序原理回顾

快速排序（Quicksort）是一种基于分治策略的排序算法。它的基本思想是选择一个元素作为枢轴（pivot），通过一趟排序将待排序序列分割成两部分，使得左边部分的所有元素都小于等于枢轴，右边部分的所有元素都大于等于枢轴，然后再分别对这两部分递归地应用快速排序算法，直到整个序列有序。

各轮具体执行过程

第一轮（以 66 为枢轴）：设置两个指针 i（初始指向数组最左边元素）和 j（初始指向数组最右边元素），从数组两端开始扫描，比较元素与枢轴 66 的大小关系，把小于枢轴的元素移到左边，大于枢轴的元素移到右边。
- 首先，i 从左向右移动，找到第一个大于等于 66 的元素，此时 i 指向 77；同时，j 从右向左移动，找到第一个小于等于 66 的元素，此时 j 指向 22。交换 i 和 j 所指向的元素，数组变为 {44, 22, 55, 99, 66, 33, 77, 88, 79}。
- 接着，i 继续向右移动，此时 i 指向 99；j 继续向左移动，指向 33，交换它们，数组变为 {44, 22, 55, 33, 66, 99, 77, 88, 79}。
- 然后，i 继续向右移动，指向 99；j 继续向左移动，指向 55，交换它们，数组变为 {44, 22, 55, 33, 66, 99, 77, 88, 79}（这次交换后数组状态和上一步一样，只是继续按流程操作）。
- 继续移动指针，i 指向 99，j 指向 55，此时 i 和 j 相遇（i 大于 j 了），将枢轴 66 放置到 i（此时也是 j）的位置，数组被划分为两部分：左边部分是 {44, 22, 55, 33}，右边部分是 {99, 77, 88, 79}，此时枢轴 66 已经处于最终排序后的正确位置了，得到 pass 1 的结果：44 22 55 33 66 99 77 88 79。
- 结果为{ 44 22 55 33 66 99 77 88 79}
第二轮（以 55 和 88 为枢轴，分别对两个子数组操作）：
- 对左子数组 {44, 22, 55, 33} 以 55 为枢轴进行划分：同样设置指针 i 和 j 来进行操作。 i 从左向右移动，找到第一个大于等于 55 的元素，此时 i 指向 55 本身；j 从右向左移动，找到第一个小于等于 55 的元素，此时 j 指向 33。交换 i 和 j 所指向的元素，数组变为 {44, 22, 33, 55}。接着，i 继续向右移动（此时 i 已经在 55 位置了，无需再移动），j 继续向左移动，指向 22，交换它们，数组变为 {44, 22, 33, 55}（这次交换后数组状态和上一步一样，只是继续按流程操作）。继续移动，i 指向 55，j 指向 22，此时 i 和 j 相遇，将枢轴 55 放置到该位置，这样就把左子数组划分为 {44, 22, 33} 和 {}（空数组）两部分，55 处于其正确的排序位置了。
- 对右子数组 {99, 77, 88, 79} 以 88 为枢轴进行划分：利用指针 i 和 j 进行操作。i 从左向右移动，找到第一个大于等于 88 的元素，此时 i 指向 99；j 从右向左移动，找到第一个小于等于 88 的元素，此时 j 指向 79。交换 i 和 j 所指向的元素，数组变为 {99, 77, 79, 88}。然后，i 继续向右移动（此时 i 在 99 位置了，无需移动），j 继续向左移动，指向 77，此时 i 和 j 相遇，将枢轴 88 放置到该位置，把右子数组划分为 {99, 77, 79} 和 {}（空数组）两部分，88 处于正确的排序位置了。经过上述对两个子数组的操作，数组变为 44 22 33 55 66 79 77 88 99，即 pass 2 的结果。
第三轮（以 33 和 77 为枢轴，分别对相应子数组操作）：
- 对左子数组 {44, 22, 33} 以 33 为枢轴进行划分：设置指针 i 和 j 操作。i 从左向右移动，找到第一个大于等于 33 的元素，此时 i 指向 44；j 从右向左移动，找到第一个小于等于 33 的元素，此时 j 指向 33。交换 i 和 j 所指向的元素，数组变为 {33, 22, 44}。接着，i 继续向右移动，j 继续向左移动，指向 22，此时 i 和 j 相遇，停止操作。
- 对右子数组 {79, 77, 99} 以 77 为枢轴进行划分：使用指针 i 和 j 进行操作，由于 79 大于 77，交换元素，变为{77, 79, 88, 99} 经过这一轮操作，数组变为 33 22 44 55 66 77 79 88 99，也就是 pass 3 的结果。
第四轮（以 22 为枢轴，对 {22} 这个子数组操作）：
- 交换{22}与{33}，变成{22, 33, 44, 55}，执行完毕。
- 最终结果为{22 33 44 55 66 77 79 88 99}

答案解释

整个快速排序过程就是不断地选择枢轴、划分子数组，并对划分后的子数组递归地重复这个过程，每一轮都依据枢轴将数组分成两部分，让元素逐渐移动到它们最终正确排序的位置上。按照题目给定的每轮特定枢轴以及相应操作步骤，一步步实现了对原始数组的排序，最终得到有序的数组。这种分治思想使得快速排序在平均情况下具有较好的时间复杂度，通常接近 \(O(n \log n)\)，不过在最坏情况下（比如每次选择的枢轴都是最大或最小元素时）时间复杂度会退化为 \(O(n^2)\)。

希望这样详细的解释能让你清晰理解快速排序算法在这个具体数组上的执行过程，如果还有疑问，请随时问我哦。