06年B卷

Multiple Choice Questions

Pick the growth rate that corresponds to the most efficient algorithm as n gets large:
1. 8nlog n
2. 5n²
3. n!
4. 2ⁿ
An algorithm must be or do all of the following EXCEPT:
1. Composed of concrete steps
2. Correct
3. Infinite
4. No Ambiguous
Which statement is not true among the following:
1. The number of 3-node binary trees in different shape is 5.
2. The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.
3. A cluster is the smallest unit of allocation for a file, so all files are a multiple of the cluster size.
4. The best case for my algorithm is n=1 because that is the fastest.
In the hash function, collision refers to:
1. Two elements have the same sequence number.
2. Different keys are mapped to the same address of hash table.
3. Two records have the same key.
4. Data elements are too much.
The most effective way to reduce the time required by a disk-based program is to:
1. Improve the basic operations.
2. Minimize the number of disk accesses.
3. Eliminate the recursive calls.
4. Reduce main memory use.
Which of the following cases is fit for a list L to be implemented by link structure?
1. It needs to modify the element values frequently.
2. It needs to insert or delete elements in the list frequently.
3. There are lots of elements in the list.
When a pointer requires 3 bytes and a data element requires 6 bytes, the linked list implementation requires less space than the array-based list implementation when the array would be:
1. less than 1/3 full.
2. less than 2/3 full.
3. less than half full.
4. less than 3/4 full.
Which of the following is a true statement:
1. In a BST, the left child of any node is less than the right child, and in a heap, the left child of any node is less than the right child.
2. In a BST, the left child of any node could be less or greater than the right child, but in a heap, the left child of any node must be less than the right child.
3. In a BST, the left child of any node is less than the right child, but in a heap, the left child of any node could be less than or greater than the right child.
4. In both a BST and a heap, the left child of any node could be either less than or greater than the right child.
The time cost of Quicksort in the worst case is:
1. O(n)
2. O(log₂ n)
3. O(n log₂ n)
4. O(n²)
In the following sequences of key value, which is a heap?
1. 16, 72, 31, 23, 94, 53
2. 94, 23, 31, 72, 16, 53
3. 16, 53, 23, 94, 31, 72
4. 16, 23, 53, 31, 94, 72
In the following sorting algorithms, which is the best one to find the first 10 biggest elements in the 1000 unsorted elements?
1. Insert sort.
2. Heap sort.
3. Quicksort.
4. Shell sort.
The function of replacement selection sort is:
1. Select the maximal element.
2. Generate the initial merge file.
3. Merge the sorted file.
4. Replace some record.
Tree indexing methods are meant to overcome what deficiency in hashing?
1. Inability to handle range queries.
2. Inability to handle updates.
3. Inability to handle large data sets.
4. None of all above.
Assume that we have eight records, with key values A to H, and that they are initially placed in alphabetical order. Now, consider the result of applying the following access pattern: F D F G E G F A D F G E. If the list is organized by the move-to-front heuristic, then the final list will be:
1. F G D E A B C H
2. E G F D A B C H
3. A B F D G E C H
4. F D G E A B C H
In the multiway merge for external sorting, for example, 0.5MB working memory, 4KB/block, yield 128 blocks for working memory. Average run size is 1MB, so how many bytes can be sorted in one pass on average:
1. 256MB
2. 128MB
3. 4MB
4. 64MB

答案：ACDBB BBCDD BBABB

问题：从一般树转化为二叉树

将一个 一般树 （任意节点可以有多个子节点）转换为 二叉树 （每个节点最多有两个子节点）。这种转换在数据结构中非常常见，特别是为了简化操作或提高算法效率时。

解决方法：左孩子-右兄弟表示法（Left-Child Right-Sibling Representation）

步骤：

保留第一个子节点作为左孩子
对于一般树中的每个节点，只保留它的第一个子节点，并将该子节点作为二叉树中的左孩子。
将兄弟节点连接为右兄弟
对于一般树中的每个节点的其余子节点，将这些子节点以链表的形式依次连接，作为二叉树中的右兄弟。
递归转换子树
对一般树中的每个节点的子树递归执行上述两个步骤。

构造树

A certain binary tree has the preorder enumeration as ABEDCFGHIJ and the inorder enumeration as EDBCAFIHGJ. Try to draw the binary tree and give the postorder enumeration. (The process of your solution is required!!!) (8 scores)

图论

(a) 图的表示

邻接矩阵表示（Adjacency Matrix）

矩阵定义如下，其中每个元素表示对应顶点之间的边的权重，若无边则为 ∞（或未填值）：

	1	2	3	4	5	6
1	-	10	∞	20	∞	2
2	10	-	3	5	∞	∞
3	∞	3	-	∞	15	∞
4	20	5	∞	-	11	10
5	∞	∞	15	11	-	3
6	2	∞	∞	10	3	-

邻接表表示（Adjacency List）

1 -> 2(10) -> 4(20) -> 6(2)
2 -> 1(10) -> 3(3) -> 4(5)
3 -> 2(3) -> 5(15)
4 -> 1(20) -> 2(5) -> 5(11) -> 6(10)
5 -> 3(15) -> 4(11) -> 6(3)
6 -> 1(2) -> 4(10) -> 5(3)