Chapters 9-10

1) In a single function declaration, what is the maximum number of statements that may be recursive calls?

A. 1

B. 2

C. n (where n is the argument)

D. There is no fixed maximum

D. There is no fixed maximum

2) What is the maximum depth of recursive calls a function may make?

A. 1

B. 2

C. n (where n is the argument)

D. There is no fixed maximum

D. There is no fixed maximum

3) Consider the following function:

void super_write_vertical(int number)

// Postcondition: The digits of the number have been written,

// stacked vertically. If number is negative, then a negative

// sign appears on top.

// Library facilities used: iostream.h, math.h

{

if (number < 0)

{

cout << '-' << endl;

super_write_vertical(abs(number));

}

else if (number < 10)

cout << number << endl;

else

{

super_write_vertical(number/10);

cout << number % 10 << endl;

}

}

What values of number are directly handled by the stopping case?

A. number < 0

B. number < 10

C. number >= 0 && number < 10

D. number > 10

C. number >= 0 && number < 10

4) Consider the following function:

void super_write_vertical(int number)

// Postcondition: The digits of the number have been written,

// stacked vertically. If number is negative, then a negative

// sign appears on top.

// Library facilities used: iostream.h, math.h

{

if (number < 0)

{

cout << '-' << endl;

super_write_vertical(abs(number));

}

else if (number < 10)

cout << number << endl;

else

{

super_write_vertical(number/10);

cout << number % 10 << endl;

}

}

Which call will result in the most recursive calls?

A. super_write_vertical(-1023)

B. super_write_vertical(0)

C. super_write_vertical(100)

D. super_write_vertical(1023)

A. super_write_vertical(-1023)

5) Consider this function declaration:

void quiz(int i)

{

if (i > 1)

{

quiz(i / 2);

quiz(i / 2);

}

cout << "*";

}

How many asterisks are printed by the function call quiz(5)?

A. 3

B. 4

C. 7

D. 8

E. Some other number

C. 7

6) This question is appropriate if you studied a flood fill (which was not part of the text). Suppose that a flood fill starts at the point marked with an o in this diagram:

 XXXXXXXXXX
 XX    XXXX  This is row number 1
 XX XX XXXX  This is row number 2
 XX   o XXX  This is row number 3
 XXXXXXXXXX

Suppose that the first recursive call is always left; the second recursive call is always right; the third recursive call is always up; the fourth recursive call is always down. How will the rows be completely filled?

• A. Row 1 is filled first, then row 2, then row 3

• B. Row 1 is filled first, then row 3, then row 2

• C. Row 2 is filled first, then row 3, then row 1

• D. Row 3 is filled first, then row 1, then row 2

• E. Row 3 is filled first, then row 2, then row 1

E. Row 3 is filled first, then row 2, then row 1

7) In a real computer, what will happen if you make a recursive call without making the problem smaller?

A. The operating system detects the infinite recursion because of the "repeated state"

B. The program keeps running until you press Ctrl-C

C. The results are nondeterministic

D. The run-time stack overflows, halting the program

D. The run-time stack overflows, halting the program

8) When the compiler compiles your program, how is a recursive call treated differently than a non-recursive function call?

A. Parameters are all treated as reference arguments

B. Parameters are all treated as value arguments

C. There is no duplication of local variables

D. None of the above

D. None of the above

9) When a function call is executed, which information is not saved in the activation record?

A. Current depth of recursion.

B. Formal parameters.

C. Location where the function should return when done.

D. Local variables.

A. Current depth of recursion

10) Consider the following function:

void test_a(int n)

{

cout << n << " ";

if (n>0)

test_a(n-2);

}

What is printed by the call test_a(4)?

A. 0 2 4

B. 0 2

C. 2 4

D. 4 2

E. 4 2 0

E. 4 2 0

11) Consider the following function:

void test_b(int n)

{

if (n>0)

test_b(n-2);

cout << n << " ";

}

What is printed by the call test_b(4)?

A. 0 2 4

B. 0 2

C. 2 4

D. 4 2

E. 4 2 0

A. 0 2 4

12) Suppose you are exploring a rectangular maze containing 10 rows and 20 columns. What is the maximum number of calls to traverse_maze that can be generated if you start at the entrance and call traverse_maze?

A. 10

B. 20

C. 30

D. 200

D. 200

13) Suppose you are exploring a rectangular maze containing 10 rows and 20 columns. What is the maximum depth of recursion that can result if you start at the entrance and call traverse_maze?

A. 10

B. 20

C. 30

D. 200

D. 200

14) What is the relationship between the maximum depth of recursion for traverse_maze and the length of an actual path found from the entrance to the tapestry?

A. The maximum depth is always less than or equal to the path length.

B. The maximum depth is always equal to the path length.

C. The maximum depth is always greater than or equal to the path length.

D. None of the above relationships are always true.

C. The maximum depth is always greater than or equal to the path length.

15) What would a suitable variant expression be for the traverse_maze function which could be used to prove termination? Assume N is the number of rows in the maze and M is the number of columns.

A. N + M

B. N + M + 1

C. N * M

D. The number of unexplored spaces in the maze.

D. The number of unexplored spaces in the maze

16) What technique is often used to prove the correctness of a recursive function?

A. Communitivity.

B. Diagonalization.

C. Mathematical induction.

D. Matrix Multiplication.

C. Mathematical induction

1) There is a tree in the box at the top of this section. How many leaves does it have?

A. 2

B. 4

C. 6

D. 8

E. 9

B. 4

2) There is a tree in the box at the top of this section. How many of the nodes have at least one sibling?

A. 5

B. 6

C. 7

D. 8

E. 9

B. 6

3) There is a tree in the box at the top of this section. What is the value stored in the parent node of the node containing 30?

A. 10

B. 11

C. 14

D. 40

E. None of the above

B. 11

4) There is a tree in the box at the top of this section. How many descendants does the root have?

A. 0

B. 2

C. 4

D. 8

D. 8

5) There is a tree in the box at the top of this section. What is the depth of the tree?

A. 2

B. 3

C. 4

D. 8

E. 9

B. 3

6) There is a tree in the box at the top of this section. How many children does the root have?

A. 2

B. 4

C. 6

D. 8

E. 9

A. 2

7) Consider the binary tree in the box at the top of this section. Which statement is correct?

A. The tree is neither complete nor full.

B. The tree is complete but not full.

C. The tree is full but not complete.

D. The tree is both full and complete.

8) What is the minimum number of nodes in a full binary tree with depth 3?

A. 3

B. 4

C. 8

D. 11

E. 15

9) What is the minimum number of nodes in a complete binary tree with depth 3?

A. 3

B. 4

C. 8

D. 11

E. 15

10) Select the one true statement.

A. Every binary tree is either complete or full.

B. Every complete binary tree is also a full binary tree.

C. Every full binary tree is also a complete binary tree.

D. No binary tree is both complete and full.

11) Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T?

A. 0

B. 3

C. 4

D. 5

12) Select the one FALSE statement about binary trees:

A. Every binary tree has at least one node.

B. Every non-empty tree has exactly one root node.

C. Every node has at most two children.

D. Every non-root node has exactly one parent.

13) Consider the binary_tree_node from Section 10.3. Which expression indicates that t represents an empty tree?

A. (t == NULL)

B. (t->data( ) == 0)

C. (t->data( ) == NULL)

D. ((t->left( ) NULL) && (t->right( ) NULL))

14) Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child's value be stored?

A. data[i+1]

B. data[i+2]

C. data[2*i + 1]

D. data[2*i + 2]

15) How many recursive calls usually occur in the implementation of the tree_clear function for a binary tree?

A. 0

B. 1

C. 2

16) Suppose that a binary taxonomy tree includes 8 animals. What is the minimum number of NONLEAF nodes in the tree?

A. 1

B. 3

C. 5

D. 7

E. 8

17) There is a tree in the box at the top of this section. What is the order of nodes visited using a pre-order traversal?

A. 1 2 3 7 10 11 14 30 40

B. 1 2 3 14 7 10 11 40 30

C. 1 3 2 7 10 40 30 11 14

D. 14 2 1 3 11 10 7 30 40

18) There is a tree in the box at the top of this section. What is the order of nodes visited using an in-order traversal?

A. 1 2 3 7 10 11 14 30 40

B. 1 2 3 14 7 10 11 40 30

C. 1 3 2 7 10 40 30 11 14

D. 14 2 1 3 11 10 7 30 40

19) There is a tree in the box at the top of this section. What is the order of nodes visited using a post-order traversal?

A. 1 2 3 7 10 11 14 30 40

B. 1 2 3 14 7 10 11 40 30

C. 1 3 2 7 10 40 30 11 14

D. 14 2 1 3 11 10 7 30 40

20) Consider this binary search tree:

       14
      /  \
     2    16
    / \    
   1   5 
      /    
     4     

Suppose we remove the root, replacing it with something from the left subtree. What will be the new root?

• A. 1

• B. 2

• C. 4

• D. 5

• E. 16