QUESTION 1

If each key is mapped to a different index in the hash table, this is called ________ hashing.

		quadratic
		normal
		perfect
		linear

QUESTION 2

In a preorder tree traversal, each node is processed ____ its children.

		after
		instead of
		before
		relative to the ordinal values of

QUESTION 3

A tree node that has zero children is called a ________ node.

		terminal
		leaf
		swollen
		root

QUESTION 4

What is the base case in the following recursive function?

void xMethod(int n) { if (n > 0) {

cout << (n % 10) << endl; xMethod(n / 10); } }

		n > 0
		There is no base case.
		n <= 0
		n != 0

QUESTION 5

Resolving collisions by sequentially finding the next available location is called ________.

		double hashing
		bucketed hashing
		quadratic probing
		linear probing

QUESTION 6

Fill in the code to complete the following function for computing a Fibonacci number.

long fib(long index)

{

if (index == 0) // Base case

return 0;

else if (index == 1) // Base case

return 1;

else // Reduction and recursive calls

return __________________;

}

		fib(index - 1)
		fib(index + 2) + fib(index + 1)
		fib(index - 1) + fib(index - 2)
		fib(index - 2)

QUESTION 7

A binary tree gets its name from the fact that it ________.

		is made of nodes that have, at most, two children
		involves math and a number system that most people do not understand
		has leaves that resemble little ones and zeros
		is represented in memory using a binary number format

QUESTION 8

The ________ traversal algorithm processes the nodes of a binary tree in alphabetical or numeric order.

		unordered
		preorder
		postorder
		inorder

QUESTION 9

In a postorder tree traversal, each node is processed ____ its children.

		instead of
		relative to the ordinal values of
		after
		before

QUESTION 10

Which of the following statements is FALSE?

		Every recursive function must return a value.
		Every recursive function must have a base case or stopping condition.
		Infinite recursion can occur if the problem is not reduced in a way that brings it to a base case.
		Every recursive call reduces the original problem, bringing it closer to a base case.

QUESTION 11

When is the right subtree of a binary tree processed before the left?

		When using a preorder traversal algorithm.
		Never. The left always goes before the right in the standard traversal algorithms.
		When using a postorder traversal algorithm.
		When using an inorder traversal algorithm.

QUESTION 12

In hashing, a collision occurs when:

		many elements share the same key
		two or more keys map to the same hash value
		the requested data is not found
		we try to insert new data when the hash table is already full

QUESTION 13

If you have an array of 4,000 sorted data items, about how many comparisons will it take for a binary search to discover that a certain value is not present?

		12
		It depends on where the value would fall in the array.
		4000
		64

QUESTION 14

Fill in the code to complete the following method for computing a factorial.

long factorial(int n){

if (n == 0) // Base case

return 1;

else

return _____________; // Recursive call }

		factorial(n) * factorial(n - 1)
		n * (n - 1)
		n
		n * factorial(n - 1)

QUESTION 15

Which of the following statements is true about this recursive function?

long f(int n)

{

return n * f(n - 1);

}

		Invoking f(1) returns 1.
		The function runs infinitely and causes a crash.
		This function works perfectly for all n > 0.
		Invoking f(0) returns 0.

QUESTION 16

A hashing function ________.

		maps a key to an index in the hash table
		resolves conflicts between data with identical hash codes
		is usually implemented recursively
		stores an element in a hash table

QUESTION 17

Rather than finding a new location for colliding data, a(n) ________ scheme stores the data in linked lists.

		double hashing
		open addressing
		linear probing
		bucketing/separate chaining

QUESTION 18

In the following recursive function, what is the base case?

int xFunc(int n)

{

if (n == 1) return 1;

else return n + xFunc(n - 1);

}

		n is greater than 1.
		n is 1.
		There is no base case.
		n is less than 1.

QUESTION 19

Suppose a list is {2, 9, 5, 4, 8, 1}. After the first pass of bubble sort, the list becomes:

		2, 5, 4, 8, 1, 9
		2, 9, 5, 4, 8, 1
		2, 9, 5, 4, 1, 8
		2, 1, 5, 4, 8, 9
		2, 5, 9, 4, 8, 1

QUESTION 20

A binary tree whose left and right subtrees are similar in height is said to be ________.

		abstract
		fictitious
		balanced
		inefficient