数据结构与算法分析 复习试卷A2.doc

课程名称： 任课教师： 学号： 姓名：四川大学期末考试试题（闭卷）（20092010学年第1学期）课程号： 311036030课程名称： 数据结构与算法分析（A卷）任课教师： 孙界平，张卫华 适用专业年级： 软件工程 2008级学号： 姓名： 考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行四川大学考试工作管理办法和四川大学考场规则。有考试违纪作弊行为的，一律按照四川大学学生考试违纪作弊处罚条例进行处理。四川大学各级各类考试的监考人员，必须严格执行四川大学考试工作管理办法、四川大学考场规则和四川大学监考人员职责。有违反学校有关规定的，严格按照四川大学教学事故认定及处理办法进行处理。题 号一(40%)二(8%)三(42%)四(10%)卷面成绩得 分阅卷时间注意事项：1. 请务必将本人所在学院、姓名、学号、任课教师姓名等信息准确填写在试题纸和添卷纸上；2. 请将答案全部填写在本试题纸上；3. 考试结束，请将试题纸、添卷纸和草稿纸一并交给监考老师。eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee评阅教师得分一、单项选择题（本大题共20小题，每小题2分，共40分）提示：在每小题列出的备选项中只有一个是符合题目要求的，请将其代码写到答题纸上。错选、多选或未选均无分。1. A solution is efficient if a) it solves a problem within the require resource constraints. b) it solves a problem within human reaction time. c) it solves a problem faster than other known solutions. d) a and b. *e) a and c. f) b and c. 2. If R is a binary relation over set S, then R is transitive if a) aRa for all a in S.b) whenever aRb, then bRa, for all a, b in S.c) whenever aRb and bRa, then a = b, for all a, b in S.*d) whenever aRb and aRc, then aRc, for all a, b, c in S.3. When performing asymptotic analysis, we can ignore constants and low order terms because: *a) We are measuring the growth rate as the input size gets large.b) We are only interested in small input sizes.c) We are studying the worst case behavior.d) We only need an approximation.4. For a list of length n, the linked-list implementations prev function requires worst-case time:a) O(1).b) O(log n).*c) O(n).d) O(n2).5. Finding the element in an array-based list with a given key value requires worst case time:a) O(1).b) O(log n).*c) O(n).d) O(n2).6. All operations on a stack can be implemented in constant time except:a) Pushb) Popc) The implementors choice of push or pop (they cannot both be implemented in constant time).*d) None of the above.7. The Full Binary Tree Theorem states that:*a) The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.b) The number of leaves in a non-empty full binary tree is one less than the number of internal nodes.c) The number of leaves in a non-empty full binary tree is one half of the number of internal nodes.d) The number of internal nodes in a non-empty full binary tree is one half of the number of leaves.8. When every node of a full binary tree stores an 8-byte data field and two 4-byte child pointers, the overhead fraction is approximately:a) one quarter.b) one third.*c) one half.d) two thirds.e) three quarters.f) none of the above.9. When sorting n records, Insertion sort has worst-case cost:a) O(log n).b) O(n).c) O(n log n).*d) O(n2)e) O(n!)f) None of the above.10. Shellsort takes advantage of the best-case behavior of which sort?*a) Insertion sortb) Bubble sortc) Selection sortd) Shellsorte) Quicksortf) Radix sort11. The most effective way to reduce the time required by a disk-based program is to:a) Improve the basic operations.*b) Minimize the number of disk accesses.c) Eliminate the recursive calls.d) Reduce main memory use.12. The basic unit of I/O when accessing a disk drive is:a) A byte.*b) A sector.c) A cluster.d) A track.e) An extent.13. In external sorting, a run is:*a) A sorted sub-section for a list of records.b) One pass through a file being sorted.c) The external sorting process itself.14. Which is generally more expensive?a) A successful search.*b) An unsuccessful search.15. Which of the following is often implemented using a self-organizing list?*a) Buffer pool.b) Linked list.c) Priority queue.16. In hashing, the operation that will likely require more record accesses is:*a) insertb) delete17. Linear indexing is good for all EXCEPT:a) Range queries.b) Exact match queries.*c) Insertion/Deletion.d) In-memory applications.e) Disk-based applications.18. Tree indexing methods are meant to overcome what deficiency in in-memory data structures such as the BST?a) Inability to handle range queries.b) Inability to handle updates.*c) Inability to handle large data sets.19. Breadth-first search is best implemented using:a) A stack or recursion.*b) A queue.c) A tree.20. The single-source shortest path problem can be used to:a) Sort all of the graph vertices by value.b) Sort all of the graph vertices so that each vertex is listed prior to any others that depend on it.*c) Sort all of the graph vertices by distance from the source vertex.评阅教师得分二、判断题（本大题共8小题，每小题1分，共8分）提示：正确答T，错误答F，将其结果写到答题纸上。F 1. Queue is the data structures used to perform recursion.T 2. A binary tree is a tree in which each node have 2 child except leaf node.T 3. Depth-first search is best implemented using stack or recursion.F 4. A topological sort requires The graph contain cycles.T 5. We say two vertices are adjacent only when there is an edge connect them.F 6. Consider a node in an AVL tree, the height of left sub-tree minus height of right sub-tree can only be -1 or 1.T 7. Build a hash table of set 23,44,36,48,52,73,64,58, h(K)=K%13, then the address of element 64 is 12F 8. The C+ programmers view of a disk file is most like a graph.评阅教师得分三、问答题（本大题共6小题，每小题7分，共42分）。1. Determine (in a Big-O sense) the order of the following method as a function of the parameter n. A)i=n-1;while(i=0)&Ai!=k)j-;return (i);B)fact(n) if(n=1) return (1);else return (n*fact(n-1);A) O(n) B) O(n)2. Write down the pre-root and post-root traversal of the forest below, and draw the binary-tree of this forest.ABDEFCGHJIKNOML先根遍历：ABCDEFGHIJKLMNO后根遍历：BDEFCAHJIGKNOML二叉树：BGDCHKEIFJLMNOA3. Draw AVL of the following sequence16, 3, 7, 11, 9, 26, 18, 14, 15答案：4. Write down the DFS and BFS sequence of graph below: (Attention: while traversing, choose vertex from numeric sequence when more than one vertex can be chosen) 603451278深度优先搜索序列：0,4,7,5,8,3,6,1,2广度优先搜索序列：0,4,3,1,7,5,6,2,85. List the order in which the edges of the following graph are visited when running Prims MST algorithm. Show the final MST.(a)V1V2V3V4V5V6V760506540457050524230V1V2V3V4V5V6V750(c)V1V2V3V4V5V6V7(b)V1V2V3V4V5V6V750404550