浙江大学2006–2007学年秋季学期 数据结构基础 课程期末考试试卷.doc

浙江大学2006–2007学年秋季学期 《数据结构基础》课程期末考试试卷 开课学院： 软件学院 ， 考试形式：闭卷， 允许带_ 无 入场 考试时间：_2006_年_11_月_11_日, 所需时间： 120 分钟 考生姓名： ___学号： 专业： ____教师： 题序 一 二 三 四 总 分 得分 评卷人 NOTE: Please write your answers on the answer sheet. 注意：请将答案填写在答题纸上。 Please select the answer for the following problems. (20 points) Suppose that n numbers are pushed onto a stack in the order 1, 2, …, n–1, n. If n is the first number that is popped out of the stack, then the i-th number popped must be (2 points) a. i b. n–i+1 c. n–i d. any one is possible The property(s) that a list does NOT have is(are) (2 points) a. no need to pre-estimate the total space b. no need to move items for insertion and deletion c. quick random access d. the space taken is proportional to the length of the list In the following integer sequences, is(are) NOT a heap. (2 points) 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) If depth-first search can visit every vertex with any starting vertex, then that graph must be a . (2 points) a. tree b. graph contains cycles c. complete graph d. connected graph Given an integer sequence {15，9，7，8，20，-1，4，}after the first run of Shellsort, the sequence becomes {15，-l，4，8，20，9，7}, the increment must be (2 points) a. 1 b. 2 c. 3 d. 4 Place m items in a hash table with an array size of s, the loading factor is . (2 points) a. s + m b. m / s c. m * s d. m - s Breath-first search with the adjacency list representation of a graph is similar to the traversal of a binary tree (2 points) a. preorder b. inorder c. postorder d. leverl-order Among the following sorting algorithms, has the average run time O(NlogN) with small extra space. (2 points) a. Quick sort b. Heap sort c. Merge sort d. Radix sort In a