07年A卷

选择题

An algorithm must be or do all of the following EXCEPT:
(D) Ambiguous
- (A) Correct
- (B) Finite
- (C) Terminate
- (D) Ambiguous
Pick the growth rate that corresponds to the most efficient algorithm as n gets large:
(C) 10n log n
- (A) n!
- (B) 2n
- (C) 10n log n
- (D) 2n²
If a data element requires 6 bytes and a pointer requires 4 bytes, then a linked list representation will be more space efficient than a standard array representation when the fraction of non-null elements is less than about:
(B) 3/5
- (A) 2/3
- (B) 3/5
- (C) 3/4
- (D) 1/2
Which statement is not correct among the following four:
(A) The worst case for my algorithm is n becoming larger and larger because that is the slowest.
- (A) The worst case for my algorithm is n becoming larger and larger because that is the slowest.
- (B) A cluster is the smallest unit of allocation for a file, so all files occupy a multiple of the cluster size.
- (C) The selection sort is an unstable sorting algorithm.
- (D) The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.
Which of the following is a true statement:
(C) In a BST, the left child of any node is less than the right child, but in a heap, the left child of any node could be less than or greater than the right child.
- (A) In a BST, the left child of any node is less than the right child, and in a heap, the left child of any node is less than the right child.
- (B) In a BST, the left child of any node could be less or greater than the right child, but in a heap, the left child of any node must be less than the right child.
- (C) In a BST, the left child of any node is less than the right child, but in a heap, the left child of any node could be less than or greater than the right child.
- (D) In both a BST and a heap, the left child of any node could be either less than or greater than the right child.
The most effective way to reduce the time required by a disk-based program is to:
(B) Minimize the number of disk accesses.
- (A) Improve the basic operations.
- (B) Minimize the number of disk accesses.
- (C) Eliminate the recursive calls.
- (D) Reduce main memory use.
The max-heap constructed by a sequence of key (46, 79, 56, 38, 40, 84) is:
- (A) 79, 46, 56, 38, 40, 84
- (B) 84, 79, 56, 46, 40, 38
- (C) 84, 79, 46, 38, 40, 56
- (D) 84, 56, 79, 40, 46, 38
- 本题四个答案都是错误的，正确答案为：84 79 56 38 40 46。
If there is 0.5MB working memory, 4KB blocks, yield 128 blocks for working memory. By the multi-way merge in external sorting, the average run size and the sorted size in one pass of multi-way merge on average are separately:
(A) 1MB, 128MB
- (A) 1MB, 128MB
- (B) 1MB, 64MB
- (C) 2MB, 64MB
- (D) 0.5MB, 128MB
Tree indexing methods are meant to overcome what deficiency in hashing?
(D) All of above
- (A) Inability to handle range queries.
- (B) Inability to maximum queries.
- (C) Inability to handle queries in key order.
- (D) All of above.
Assume that we have eight records, with key values A to H, and that they are initially placed in alphabetical order. Now, consider the result of applying the following access pattern: E D F G B G F A F E G B, if the list is organized by the move-to-front heuristic, then the final list will be:
(B) B G E F A D C H

(A) B G E F D A C H
(B) B G E F A D C H
(C) A B F D G E C H
(D) F D G E A B C H

程序填空题

Problem 1 (10 scores): Modify the binary search routine

Task: You need to modify the binary search routine so that it returns the position of the greatest integer in the array that is less than a given integer K when K itself does not appear in the array. If the smallest value in the array is greater than K, return an error. Here's how the code can be filled in:

// Return position of greatest element <= K
int newbinary(int array[], int n, int K) {
  int l = -1;
  int r = n;             // l and r beyond array bounds
  while (l + 1 != r) {    // Stop when l and r meet
    int i = (l + r) / 2;  // Look at middle of subarray
    if (K < array[i])     r = i;       // In left half
    if (K == array[i])    return i;    // Found it
    if (K > array[i])     l = i;       // In right half
  }
  // Search value not in array
  return l;               // l at first value less than K 
                         // l = -1, no value less than K
}

Explanation:

Binary Search Process:
- We start with two pointers: l (left) and r (right). l is initially set to -1 (indicating no valid element before the first element), and r is set to n (the size of the array).
- The algorithm repeatedly divides the array in half by finding the middle element i = (l + r) / 2.
Adjusting Pointers:
- If K < array[i], we move to the left half by setting r = i.
- If K == array[i], we've found the element and return its index.
- If K > array[i], we move to the right half by setting l = i.
Return Value:
- After the loop ends, if K is not found, l will be at the position of the greatest element less than K.
- If no such element exists (i.e., l == -1), then no valid position is found, and the search is unsuccessful.

Problem 2 (3 scores): Full 5-ary tree with 100 internal vertices

Question: A full 5-ary tree with 100 internal vertices has how many vertices in total?

Solution:

A 5-ary tree is a tree where each internal node has exactly 5 children.
For a full 5-ary tree:
- Internal vertices (I) are the nodes that have children.
- Leaf vertices (L) are the nodes that do not have children.

The relationship between the number of internal nodes and leaf nodes in a full d-ary tree (where each internal node has d children) is:

$ L = (d - 1) I + 1 $

For a 5-ary tree, we have d = 5 and I = 100. Using the formula:

$ L = (5 - 1) + 1 = 4 + 1 = 401 $

The total number of vertices $ V $ is the sum of the internal nodes and the leaf nodes:

$ V = I + L = 100 + 401 = 501 $

Answer: A full 5-ary tree with 100 internal vertices has 501 vertices.

Constructing a 2-3 Tree

Question: You are given a series of records whose keys are integers. The records arrive in the following order: C, S, D, T, A, M, P, I, B, W, N, G, U, R. Show the 2-3 tree that results from inserting these records. (The process of your solution is required.)

Solution Explanation

A 2-3 tree is a balanced search tree where each node can have 2 or 3 children and 1 or 2 keys. Here's how we insert the records into the 2-3 tree step by step:

Algorithms and Graph Traversal

1) Use Dijkstra’s Algorithm to find the shortest paths from C to all other vertices. (4 scores)

Let's first define the graph based on the given information:

Vertices: A, B, C, D, E, F, G
Edges with weights:
- C to A: 4 (C,A)
- C to F: 5 (C,F)
- C to D: 6 (C,D)
- C to B: 12 (C,B)
- C to G: 11 (C,G)
- C to E: 13 (C,E)