数据结构2013-141

数据结构与算法（B 卷）2013~2014~1

一、单项选择题（本大题共15 小题，每小题2 分，共30 分）

1. Given the input order of a stack is 6, 5, 4, 3, 2, 1, ( )is not the valid output order?

A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6

2. If the MaxSize of a Circular Queue is n and there is always a space not used, front points to the previous of the

front element in the queue, and rear points to the rear element in the queue. ( ) means that the Queue is Empty.

A. (rear+1) MOD n == front B. rear == front

C. rear+1 == front D. (rear-l) MOD n == front

A．Shell sort B. Heap sort C. Selection sort D. merge sort

6. In the following sequence, ( ) is a heap?

A. 75, 65, 30, 15, 25, 45, 20, 10 B. 75, 65, 45, 10, 30, 25, 20, 15

C. 75, 45, 65, 30, 15, 25, 20, 10 D. 75, 45, 65, 10, 25, 30, 20, 15

7. The data Structures can be divided into ( ) according to their Physical form

A．Array-based structures and Linked structures B．Dynamic structures, Static structures

C．Liner structures, Non-liner structures D．Simple structures, Complex structures

8. In the following data-structures, ( ) is liner structure.

A．DAG B. BST C. linked based Stack D. Heap

9. If the height of a Complete Binary Tree is n, then the number of node is at most ( ).

A. Open hashing B. Separate chaining C. Closed hashing D. Probe function

12. A 2-3 tree is a specific variant of a ( ).

A. Splay tree B. B-tree C. BST D. Trie

13. Pick the growth rate that corresponds to the most efficient algorithm when n = 4. ( )

A. 5n B. 20 log n C. 2n

n

14. All operations on a stack can be implemented in constant time except ( ).

A. Push

B. Pop

C. The implementor's choice of push or pop (they cannot both be implemented in constant time).