09年数据结构A卷

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

选择题

Which algorithm is used to generate runs in classic external sorting?
(A) Quick-sort
(B) Bubble sort
(C) Insertion sort
(D) Replacement selection

Answer:

(D) Replacement selection

Explanation:

In external sorting, we need to handle data that is too large to fit into memory and must be stored on disk. The goal is to break the data into smaller runs that can be efficiently merged. To do this, the replacement selection algorithm is commonly used.

Here’s how the algorithms work:

Quick-sort: While Quick-sort is a popular in-memory sorting algorithm, it is not specifically used in generating runs for external sorting.
Bubble sort: This is a simple comparison-based sorting algorithm but not efficient enough to generate runs for external sorting, especially when dealing with large datasets.
Insertion sort: Similar to Bubble sort, Insertion sort is too slow for generating runs in external sorting, especially when the input is large.
Replacement selection: This is the correct algorithm. Replacement selection is used to create sorted runs from the input data by iteratively selecting the smallest or largest element and replacing it with the next item in the stream. This process ensures that the runs are as long as possible and are sorted, making them suitable for efficient merging during external sorting.

构造

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