（2007-2008学年第1学期）

课程号：         课程名称： 数据结构与算法分析（B卷）    任课教师：         

适用专业年级： 06级软件工程          学号：     姓名：     

考试须知

四川大学学生参加由学校组织或由学校承办的各级，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。

（1）The primary purpose of most computer programs is

   a) to perform a mathematical calculation.

   b) to store and retrieve information.

   c) to sort a collection of records.

   d) all of the above.

（2）Assume that P contains n elements.  The number of sets in the powerset of  P is

a) n                        b) n^2

c) 2^n                    d) 2^n - 1

e) 2^n + 1

（3）Pick the growth rate that corresponds to the most efficientalgorithm as n gets large:

a) 5n                        b) 20 log n

c) 2n^2                    d) 2^n

（4）A sequence has the following properties:

a) May have duplicates, element have a position.

b) May have duplicates, elements do not have a position.

c) May not have duplicates, elements have a position.

d) May not have duplicates, elements do not have a position.

（5）The correct traversal to use on a BST to visit the nodes in sorted order is:

a) Preorder traversal.            b) Inorder traversal.

c) Postorder traversal.

（6）When sorting n records, Insertion sort has best-case cost:

a) O(log n).                b) O(n).

c) O(n log n).                d) O(n^2)

e) O(n!)                    f) None of the above.

（7）For a list of length n, the linked-list implementation's prev

   function requires worst-case time:

a) O(1).

b) O(log n).

c) O(n).

d) O(n^2).

（8）The easiest way to represent a general tree is to:

a) convert to a list.            b) convert to a binary tree.

c) convert to a graph.

（9）Depth-first search is best implemented using:

a) A stack or recursion.        b) A queue.

c) A tree.

（10）For set P, the notation |P| indicates

a) The number of elements in P.    b) The inverse of P.

c) The powerset of P.            d) None of the above.

2．（10 scores）

Write a series of C++ statements that uses the List ADT as follows to create a list capable of holding twenty elements and which actually stores the list with following configuration:

<6, 28 | 18, 8, 19>

solution:

list L1(20);

L1.append(6);

L1.append(28);

L1.append(18);

L1.append(8);

L1.append(9);

L1.next();

L1.next();

// List abstract class

template class List {

public:

  // Reinitialize the list.  The client is responsible for

  // reclaiming the storage used by the list elements.

  virtual void clear() = 0;

  // Insert an element at the front of the right partition.

  // Return true if successful, false if the list is full.

  virtual bool insert(const Elem&) = 0;

  // Append an element at the end of the right partition.

  // Return true if successful, false if the list is full.

  virtual bool append(const Elem&) = 0;

  // Remove the first element of right partition. Return

  // true if successful, false if right partition is empty.

  // The element removed is returned in the parameter.

  virtual bool remove(Elem&) = 0;

  // Place fence at list start, making left partition empty

  virtual void setStart() = 0;

  // Place fence at list end, making right partition empty

  virtual void setEnd() = 0;

  // Move fence one step left; no change if already at start

  virtual void prev() = 0;

  // Move fence one step right; no change if already at end

  virtual void next() = 0;

  // Return length of left partition

  virtual int leftLength() const = 0;

  // Return length of right partition

  virtual int rightLength() const = 0;

  // If pos or more elements are in the list, set the size

  // of left partition to pos and return true.  Otherwise,

  // do nothing and return false.

  virtual bool setPos(int pos) = 0;

  // Return in first parameter the first element  of the

  // right partition.  Return true if successful, false

  // if the right partition is empty.

  virtual bool getValue(Elem&) const = 0;

  // Print the contents of the list

  virtual void print() const = 0;

};

3．（10 scores）

Build the Huffman coding tree and determine the codes for the following set of letters and weights:

a     b    c    d    e.

1    3    5    7    11

solution:

Huffman coding tree as follows:

Here are the final codes.

a 11111

b 1110

c 110

d 10

e 0

4．（15 scores）

What are the minimum and maximum number of elememts in a heap of  height h ?

solution:

The minimum number of elements is contained in the heap with a single nodeat depth h - 1, for a total of 2h-1 nodes.

The maximum number of elements is contained in the heap that has completely filled up level h - 1, for a total of 2h - 1 nodes.

5．（15 scores）

The Bubble Sort implentation has the following inner for loop:

for (int j = n – 1; j > i; j--)

Consider the effect of replacing this with the following staement:

for (int j = n – 1; j > 0; j--)

Would the new implementation work correctly? Would the change affect the asymptotic complexity of the algorithm? How would the change affect the running time of the algorithm?

solution:

The revised algorithm will work correctly, and its asymptotic complexity willremainΘ(n2). However, it will do about twice as many comparisons, since it will compare adjacent elements within the portion of the list already known to be sorted. These additional comparisons are unproductive.

6．（15 scores）

// Binary tree node abstract class

template class BinNode {

public:

  // Return the node's element

  virtual Elem& val() = 0;

  // Set the node's element

  virtual void setVal(const Elem&) = 0;

  // Return the node's left child

  virtual BinNode* left() const = 0;

  // Set the node's left child

  virtual void setLeft(BinNode*) = 0;

  // Return the node's right child

  virtual BinNode* right() const = 0;

  // Set the node's right child

  virtual void setRight(BinNode*) = 0;

  // Return true iff the node is a leaf

  virtual bool isLeaf() = 0;

};

Write a recursive function that returns a count of the number of leaf nodes in a binary true..

solution:

template

int count(BinNode* subroot)

{

if (subroot == NULL) return 0; // Empty subtree

if (subroot->isLeaf()) return 1; // A leaf

return 1 + count(subroot->left()) +

count(subroot->right());

}

7．（15 scores）

List the order in which the edges of the following graph are visited when running Kruskal’s MST algorithm. Show the final MST.

solution:

(1, 6) (6, 5) (2, 3) (2, 4) (4, 6).

Alternatively, (1, 6) (6, 5) (2, 3) (2, 4) (1, 2).

etc下载本文