第1頁共6頁

資料結構

期末考

系級： 座號： 姓名：

一、 是非題(24%)

( )1. A cycle is a simple path in which the first and last vertices are the same.

( )2. If a n-vertex, undirected graph with exactly n(n-1)/2 edges, then it is a complete graph.

( )3. The degree of a vertex is the number of edges incident to that vertex.

( )4. Any tree consisting solely of edges in G and including all vertices in G is called a spanning tree.

( )5. A connected component of an undirected graph is a maximal connected subgraph.

( )6. A biconnected graph is a connected graph that has only one articulation points.

( )7. The time complexity of the greedy algorithm to find the single source/ all destinations shortest paths in a nonnegative-edge-cost graph with n vertices is O(n4).

( )8. A relation · is irreflexive on a set S if for no element x in S it is the case that x·x.

( )9. Any decision tree that sorts n distinct elements has a height of at least log2(n!)+1.

( )10. Any algorithm that sorts only by comparisons must have a worst-case computing time of O(n log n).

( )11. The seek time is the time to transmit the block of data to/from disk.

( )12. A collision occurs when two non-identical identifiers are hashed into the same bucket.

二、 填充題(18%)

  1. Let n be the number of identifiers in the table, T be the total number of possible identifiers, b be the number of buckets, and s be the number of records in each bucket, then the loading factor of a hash table is .
  2. Given a binary search tree, if the number of external nodes of the binary tree is n, then the related formula of E and I is .
  3. The number of distinct binary trees with n nodes is:

  1. Use the dynamic programming methodology to find the single source /all destinations shortest paths in a general-weight graph with n vertices. Let be the length of a shortest path from the source vertex v to vertex u under the constraint that the shortest path contains at most l edges. Then, , , where is a length function which indicates the distance between adjacent vertices m to n. Therefore, we can make the following observations:

(a) If the shortest path from vertices v to u with at most k, k >1, edges has no more than k-1 edges, then .

(b) If the shortest path from vertices v to u with at most k, k >1, edges has exactly k edges, then it is comprised of a shortest path from source v to some vertex j followed by the edge <j, u>. The path from v to j has k-1 edges, and its length is .

These observations result in the following recurrence for dist:

This recurrence may be used to compute from , for k = 2, ..., n-1.

三、 (5%) Given a max heap, whose elements are all integer, as follows:

If we delete two elements from the heap, please draw the max heap after these deletions.

ANS:

系級： 座號： 姓名：

四、 (5%) Given a forest as follows:

The result of pre-order traversal of the forest is:

五、 (5%) Suppose we have the postorder sequence EFDCBIHKJGA and the inorder sequence EBFCDAIHGKJ of the same binary tree. Can you draw the tree? If not, explain.

ANS:

六、 (8%) For the graph G shown as follows, please obtain its adjacency multilists representation.

ANS:

七、 (5%) Given a graph G as follows:

Please show its minimum-cost spanning tree.

ANS:

八、 (5%) Given a directed graph G as follows, please show its reflexive transitive closure matrix.

系級： 座號： 姓名：

九、 (10%) Input a sequence of records, and its corresponding key sequence is 26, 5, 37, 1, 61, 11, 59, 15, 48, 19. Using quick sort method to sort these keys, please show each intermediated result. What are the time complexities of the worst-case and the average-case?

ANS:

十、 (10%) Given an AOE (activity-on-edge) graph as follows, please show

(1) the earliest time of events 1 and 7

(2) the earliest time of activities a1 and a7

(3) the critical activities

十一、 (5%) Given a 12-element min-max heap as follows, please show the min-max heap after inserting two new elements with keys 5 and 80, respectively. ( the node with key 5 is inserted first)

ANS:

十二、 (5%) Here shows a possible binary search trees for the identifier set (a1, a2, a3) = (do, if, while), with probabilities, p1 = 0.5, p2 = 0.1, p3 = 0.05, q0 = 0.15, q1 = 0.1, q2 = 0.05, and q3 = 0.05, show the cost of this tree.

ANS:

1