09年数据结构A卷

这一张试卷只记录一些没有怎么留意过的知识点，之前已经出现过的知识点就不记录在内了。

Problem 4:

Which statement is not correct among the following four?
(A) A general tree can be transferred to a binary tree with the root having both left child and right child.
(B) The number of empty sub-trees in a non-empty binary tree is one more than the number of nodes in the tree.
(C) A cluster is the smallest unit of allocation for a file, so all files occupy a multiple of the cluster size.
(D) The Heap-sort is an unstable sorting algorithm.

Answer:

The correct answer is (A).

Explanation:

(A) False. A general tree can be converted into a binary tree, but the process typically involves modifying the structure of the tree so that each node has at most two children: the first child becomes the left child, and the rest of the children are linked as right children in sequence. The idea is not that the root has both a left and right child directly, but rather that each child of a node is connected to the right pointer of the node, which transforms the general tree into a binary tree. This statement is misleading and not accurate in the context of binary tree conversion.
(B) True. This statement is correct. In a non-empty binary tree, there is one more empty subtree than the number of nodes. The number of empty subtrees is calculated as the total number of leaves plus one (because each internal node contributes to one more subtree).
(C) True. This is also correct. In file systems, a cluster is the smallest unit of allocation for data storage. Files are stored in multiples of cluster size, even if the file size is smaller than the cluster size.
(D) True. Heap sort is an unstable sorting algorithm because it does not guarantee the preservation of the order of equal elements. For example, if two equal elements are initially in different relative orders, their relative order may be changed during the sorting process.

Problem 5:

We use the parent pointer representation for general trees to solve which problem?
(A) Shortest paths
(B) General tree traversal
(C) Merging two trees together
(D) Exact-match query

答案是C。