SCUT2009

Trace by hand the execution of Quicksort algorithm on the array: int a[] = {49 38 65 97 76 13 27 49*}. The pivot is 49 in the first pass, the following pivots are selected by the same method (at the first position of the input array).

initial:	49, 38, 65, 97, 76, 13, 27, 49*
pass1:		27, 38, 13, 49, 76, 65, 49*, 97
pass2:		13, 27, 38, 49, 49*, 65, 76, 97

Trace by hand the execution of Quicksort algorithm on the array: int a[] = {27，34，78，13，20，44，09，34*} The pivot is 27 in the first pass, the following pivots are selected by the same method (at the first position of the input array).

initial:	27, 34, 78, 13, 20, 44, 9, 34*
pass1:		9, 20, 13, 27, 34, 44, 34*, 78
pass2:		9, 20, 13, 27, 34*, 34, 78, 44
pass3:		9, 13, 20, 27, 34*, 34, 44, 78

Select the correct choice.

  1. Which statement is not correct among the following four: ( A )

  1. A general tree can be transferred to a binary tree with the root having both left child and right child.

  2. The number of empty sub-trees in a non-empty binary tree is one more than the number of nodes in the tree.

  3. A cluster is the smallest unit of allocation for a file, so all files occupy a multiple of the cluster size.

  4. The Heap-sort is an unstable sorting algorithm.

答案：(A)

答案解释：

  • 选项 A： 一般树转换为二叉树采用的是 “孩子兄弟表示法”，转换后的二叉树其根节点只有左子树（原树的第一个孩子节点转换而来）和右子树（原树的第一个孩子节点的兄弟节点依次转换连接而成），并不是说根节点随意就有左、右两个子树，它有着特定的转换规则和对应关系，所以该选项说法不正确。
  • 选项 B： 对于非空二叉树，空子树的数量确实是比节点数量多 1。可以通过数学归纳法等方式来证明，比如只有 1 个节点的二叉树，它有 2 个空指针域也就是对应 2 个空子树，节点数为 1，满足空子树数比节点数多 1；随着节点数增加，每增加一个节点会占用一个原来的空指针域，但同时又会新产生 2 个空指针域，依然保持空子树数量比节点数量多 1 的关系，所以该选项说法正确。
  • 选项 C： 在文件系统中，簇是文件分配的最小单位，文件在磁盘上存储时所占空间必然是簇大小的整数倍，这是文件存储分配的基本原理，所以该选项说法正确。
  • 选项 D： 堆排序是一种不稳定的排序算法。不稳定指的是在排序前后相等元素的相对顺序可能会发生改变，在堆排序的过程中，例如在调整堆结构时，有可能会出现相等元素位置互换的情况，导致相等元素的相对顺序变化，所以该选项说法正确。
  1. We use the parent pointer representation for general trees to solve (C) problem?

  1. Shortest paths (B) General tree traversal

  2. Merging two tree together (D) Exact-match query

答案解释：

  • 选项 A： 解决最短路径问题通常会用到专门的图算法，比如迪杰斯特拉（Dijkstra）算法、弗洛伊德（Floyd）算法等，利用图的边权重以及节点之间的连接关系来计算最短路径，和一般树的父指针表示法没有直接关联，所以该选项不符合。
  • 选项 B： 虽然父指针表示法可以一定程度上辅助进行树的遍历，比如可以通过父指针回溯到上层节点等，但一般有更常规且方便的方式来实现树的遍历（如先序、中序、后序递归或非递归遍历等），而且这也不是使用父指针表示法的主要目的，所以该选项不太准确。
  • 选项 C： 在合并两棵树的时候，利用父指针表示法可以方便地将一棵树的某个节点及其子树结构接入到另一棵树的相应位置，通过调整父指针指向等操作，能够较好地实现两棵树的合并，所以使用父指针表示法可以解决两棵树合并的问题，该选项符合题意。
  • 选项 D： 精确匹配查询更多是在查找特定元素的场景下，比如在有序的数据结构中通过二分查找等方式来精确查找某个元素，和一般树的父指针表示法主要解决的问题不一致，所以该选项不符合。

综上，答案依次为 (4) 中的 (A) 以及 (5) 中的 (C)。