数据结构期末考试卷.docVIP

杭州师范大学信息科学与工程学院2008-2009学年第一学期期末考试 《数据结构》试卷（A） 题号 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ 总分 得分 Note: Please write your answers on the answer sheet. 注意：请将答案填写在答题纸上。 得分 I. Please select the answer for the following problems.(30 points) (1) Given a connected graph(连通图) with n vertices, the minimum number of edges in the graph must be ( ). A. n B. n ( n – 1) / 2 C. n + 1 D. n – 1 (2) Given the preorder traversal(先序遍历) sequence ABDCEFHG and the inorder traversal (中序遍历)sequence BDAFHEGC, the corresponding postorder traversal(后序遍历)sequence is ( ). A. DBAHFGCE B. BDHFGECA C. DBHFGECA D. DBCFHEGA (3) Given a list of integers {1,2,3,4,5,9,8,6,7}. To sort them in increasing order, ( ) is the fastest, and ( ) takes the most extra spaces. A. insertion sort B. quick sort C. merge sort D. selection sort (4) Place m items in a hash table with an array size of s, the loading factor is ( ). A. s + m B. m / s C. m * s D. m – s (5) Breadth-first search(广度优先有哪些信誉好的足球投注网站) with the adjacency list representation of a graph is similar to the ( ) traversal of a binary tree. A. preorder B. inorder C. postorder D. level-order (6) In a ( ), keys along each of the paths from a node to the root are ordered. A. heap B. binary search tree C. complete tree D. none of the above (7) In the following integer sequences, ( ) is NOT a heap(堆). A. {100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66} B. {100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10} C. {10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100} D. {100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 20} (8) If the input to a stack is 1,2,3,4,…,n, and the first output is n, the i-th output is ( ). A. n – i + 1 B. n – i C. i D. undecided (9) The maximum number of nodes in a binary tree of depth k (k≥1) is ( ). A. 2k + 1 – 1 B. 2k - 1 C. 2k-1 – 1 D. 2k +1 (10) Which of the following