数据结构与算法 英文版哈理工12-13.docVIP

Choice Questions（choose the right answer for each one, 10 points） Assume a sequence list as 1,2,3,4 passes a stack, an impossible output is _______. 4,1,2,3 B. 3,2,4,1 C. 3,1,2,4 D. 4,3,1,2 In a simple linked list with n nodes, the number of pointer fields with NULL totles ______. n B. 2 C. n/2 D. 1 In the binary search tree, for any root of subtree, the keys of all nodes in its left subtree is _______ the keys of all nodes in its right subtree. A.less than B. equal to C. greater than D. less than or equal to The output from scanning a minimum heap with level traversal algorithm______. A.must be an ascending sequence B. must be descending sequence C.must have a minimum item at the head position D.must have a minimum item at the rear position 5. Suppose that a linear list contains n = 31 nodes, the binary search is applied to the list, the maximum times in searching is ______. A.4 B.5 C.31 D.15 6. A queue is a version of _________. A. linked list B. LIFO list C. sequential list D. FIFO list 7. In a tree, _______are vertices with the same parent. A.children B.sibling C.adjacent D.leaf 8. To find the shortest path between a pair of vertices, _____can be used. A.Kruskal B.Disjkstra C.Hashing D.Critical Path 9. Among sorting algorithms, whitch kind of algorithm is divide-and-conquer sorting.______. A. shell sort B.heap sort C.quick sort D.insertionsort 10. In a undirected graph with n vertices, the maximum edges is ______. A.n(n+1)/2 B.n(n-1)/2 C.n(n-1) D.n*n Fill in the blanks.(22points) A Binary Tree will have _______nodes on its level i at most. If the depth of full binary tree is k, then the number of nodes in the tree at least_______. In a ______ data structure, all insertions and deletions of entries are made at one end. It is particularly useful in applications involving________. Give three different topological orders of the following directed graph…. Hash storage with two problems of _____________________