CSCI 2380 TF/MC

In a recursive function, the base case stops the recursion.

True

With recursion, the base case must eventually be reduced to a general case.

False

The following is an example of a recursive function, where nextNum is a function such that nextNum(x) = x + 1.

int recFunc(int x) {

return nextNum(nextNum(x));

}

False

Every call to a recursive function requires the system to allocate memory for the local variables and formal parameters.

True

Infinite recursions execute forever on a computer.

False

A definition in which something is defined in terms of a smaller version of itself is called a(n) ____ definition.

a. step-wise b. recursive c. member-wise d. iterative

b

7. The ____ case is the case for which the solution to an equation is obtained directly.

a. general b. base c. direct d. tail

b

int foo(int n) //line 1

{ //line 2

if (n == 0) //line 3

return 0; //line 4

else //line 5

return n + foo(n - 1); } //line 6

Consider the accompanying definition of a recursive function. Which of the statements represents the base case?

a. Statements in Lines 1-6.

b. Statements in Lines 3 and 4.

c. Statements in Lines 5 and 6.

d. Statements in Lines 3, 4, and 5.

b

Consider the accompanying definition of a recursive function. Which of the statements represent the general case?

a. Statements in Lines 1-6 b. Statements in Lines 3 and 4

c. Statements in Lines 4, 5, and 6 d. Statements in Lines 5 and 6

int recFunc(int num)

{

if (num >= 10)

return 10;

else return num * recFunc(num + 1);

}

d

Consider the accompanying definition of a recursive function. What is the output of the following statement?

cout << recFunc(8) << endl;

a. 4 b. 8 c. 72 d. 720

d

Consider the accompanying definition of a recursive function. What is the output of the following statement?

cout << recFunc(10) << endl;

a. 10 b. 11 c. 100 d. 110

a

Consider the following definition of the recursive function print.

void print(int num)

{

if (num > 0)

{

cout << num << " "; print(num - 1);

}

}

What is the output of the following statement? print(4);

a. 0 1 2 3 4 b. 1 2 3 4

c. 4 3 2 1 d. 4 3 2 1 0

c

A recursive function in which the last statement executed is the recursive call is called a(n) ____ recursive function.

a. direct b. tail c. indefinite d. indirect

b

If every recursive call results in another recursive call, then the recursive function (algorithm) is said to have ____ recursion.

a. unlimited b. indefinite c. infinite d. tail

int mystery(int list[], int first, int last)

{

if (first == last)

return list[first];

else

return list[first] + mystery(list, first + 1, last);

}

b

Consider the accompanying definition of the recursive function mystery. Given the declaration:

int alpha[5] = {1, 4, 5, 8, 9};

what is the output of the following statement?

cout << mystery(alpha, 0, 4) << endl;

a. 1 b. 18 c. 27 d. 35

c

Consider the accompanying definition of the recursive function mystery. Given the declaration:

int beta[10] = {2, 5, 8, 9, 13, 15, 18, 20, 23, 25};

What is the output of the following statement?

cout << mystery(beta, 4, 7) << endl;

a. 27 b. 33 c. 55 d. 66

d

Consider the following definition of the recursive function mystery.

int mystery(int first, int last)

{

if (first > last)

return 0;

else if (first == last)

return first;

else return first + mystery(first + 1, last - 1);

}

What is the output of the following statement?

cout << mystery(6, 10) << endl;

a. 13 b. 21 c. 40 d. 42

b

Consider the following definition of the recursive function mystery.

int mystery(int num)

{ if (num <= 0)

return 0;

else if (num % 2 == 0)

return num + mystery(num – 1); ………

Consider the accompanying definition of a recursive function. What is the output of the following statement?

cout << mystery(5) << endl;

a. 50 b. 65 c. 120 d. 180

a

int puzzle(int start, int end) {

if (start > end) return start - end;

else if (start == end) return start + end;

else return end * puzzle(start + 1, end - 1); }

Consider the accompanying definition of a recursive function. What is the output of the following statement?

cout << puzzle(5, 10) << endl;

a. 720 b. 5040 c. 5760 d. 10800

a

Consider the accompanying definition of a recursive function. What is the output of the following statement?

cout << puzzle(3, 7) << endl;

a. 10 b. 21 c. 42 d. 420

d

Linked lists allow you to overcome the size limitations of an array data type.

True

Memory for the components of an array does not need to be contiguous.

False

You can use the pointer head of a linked list to traverse the list.

False

We deallocate the memory for a linked list by calling the operator clear.

False

The length of a linked list is the number of nodes in the list.

True

A linked list is a random access data structure.

False

A doubly linked list can be traversed in either direction.

True

A linked list is a collection of components, called ____.

a. elements b. nodes c. members d. pointers

b

In a linked list, the address of the first node in the list is stored in a separate location, called the ____ or first.

a. head b. pointer c. front d. top

a

In a linked list, the order of the nodes is determined by the address, called the ____, stored in each node.

a. head b. tail c. link d. first

c

Every node (except of the last node) in a singly linked list contains ____.

a. the next node b. no address information

c. the address of the next node

d. the address of the previous node

c

The link field of the last node of a linked list is ____.

a. nullptr b. 1 c. n-1 d. n

a

Because each node of a linked list has two components, we need to declare each node as a(n) ____.

a. reference and string b. int and object

c. index and element d. class or struct

d

Suppose that the pointer head points to the first node in the list, and the link of the last node is nullptr. The first node of the linked list contains the address of the ____ node.

a. head b. first c. second d. tail

c

What is the purpose of the following code?

current = head;

while (current != nullptr)

{ //Process current

current = current->link;

}

a. Insertion of a node

b. Selection of a node

c. Traversal of a linked list

d. Creation of a new list

c

struct nodeType {

int info;

nodeType *link; };

nodeType head, *p, *q, *newNode;

newNode = new nodeType;

Consider the accompanying code. What is the effect of the following statement?

newNode->info = 50;

a. Stores 50 in the info field of the newNode

b. Creates a new node

c. Places the node at location 50

d. Cannot be determined from this code

a

The ____ deallocates the memory occupied by the nodes of a list when the class object goes out of scope.

a. constructor

b. destructor

c. head pointer

d. tail pointer

b

template <class Type>

____ doublyLinkedList<Type>::isEmptyList() const

{

return (first == nullptr);

}

Consider the accompanying statements. The operation returns true if the list is empty; otherwise, it returns false. The missing code is ____.

a. protected b. int c. void d. bool

d

template <class Type>

int doublyLinkedList::length() const { ____ }

The statement that provides the length of the linked list is ____.

a. cout <<< count; b. destroy();

c. return count; d. return next;

c

void doublyLinkedList<Type>::destroy()

{ nodeType *temp; ..pointer to delete the node

…

last = nullptr; count = 0;

Which of the following is the missing statement?

a. delete first;

b. delete temp;

c. destroy temp;

d. clear temp;

b

The sequential search algorithm does not require that the list be sorted.

True

In a binary search, first, the search item is compared with the last element of the list.

False

The binary search algorithm can be written iteratively or recursively.

True

During the sorting phase of insertion sort, the array containing the list is divided into two sublists, sorted and unsorted.

True

The sequential search algorithm uses a(n) ____ variable to track whether the item is found.

a. int b. bool c. char d. double

b

A sequential search of an n-element list takes ____ key comparisons on average to determine whether the search item is not in the list.

a. 0

b. n/2

c. n

d. n2

c

A sequential search of an n-element list takes ____ key comparisons on average to determine whether the search item is in the list.

a. 0

b. n/2

c. n

d. n2

b

In the average case, sequential search typically searches ____.

a. one quarter of the list

b. one third of the list

c. one half of the list

d. the entire list

c

Consider the following list: int list[] = {4, 8, 19, 25, 34, 39, 45, 48, 66, 75, 89, 95} When performing a binary search, the target is first compared with ____.

a. 4 b. 25 c. 39 d. 95

c

Consider the following list: int list[] = {4, 8, 19, 25, 34, 39, 45, 48, 66, 75, 89, 95} When performing a binary search for 75, after the first comparison, the search is restricted to ____.

a. list[0]...list[6]

b. list[0]...list[7]

c. list[5]...list[11]

d. list[6]...list[11]

d

The formula to find the index of the middle element of a list is ____.

a. (mid + last)/2

b. (first + last) - 2

c. (first + last) / 2

d. (first + mid ) * 2

c

With the binary search algorithm, ____ key comparison(s) is/are made in the successful case—the last time through the loop.

a. one b. two

c. n-2 d. n

a

For the Insertion sort algorithm, select the theoretical, worst-case running time.

a. Θ(log(n))

b. Θ(n)

c. Θ(n log(n))

d. Θ(n2)

d

For the quickort algoritthm select the theoretical worst-case running time

a. Θ(log(n))

b. Θ(n)

c. Θ(n log(n))

d. Θ(n2)

d

For a list of length n, insertion sort makes ____ key comparisons, in the worst case.

a. n(n - 1)/4

b. n(n - 1)/2

c. n2

d. n3

b

For the Mergesort algorithm, select the theoretical, worst-case running time.

a. Θ(log(n))

b. Θ(n)

c. Θ(n log(n))

d. Θ(n2)

c

Which of the following correctly states the quick sort algorithm?
…

c. if (the list size is greater than 1)

{

a. Partition the list into two sublists, say lowerSublist and upperSublist.

b. Quick sort lowerSublist.

c. Quick sort upperSublist.

d. Combine the sorted lowerSublist and sorted upperSublist.

}

…

c

For the Linear search algorithm, select the theoretical, worst-case running time.

a. Θ(log(n))

b. Θ(n)

c. Θ(n log(n))

d. Θ(n2)

b

____ sort requires knowing where the middle element of the list is.

a. Merge. b. Bubble

c. Insertion. d. Selection

a

For the Binary search algorithm, select the theoretical, worst-case running

time.

a. Θ(log(n)) b. Θ(n)

c. Θ(n log(n)) d. Θ(n2)

a

The level of the root node of a binary tree is 1.

False

All binary tree traversals start at the left-most child node.

False

The item search, insertion, and deletion operations all require the binary tree to be traversed.

True

Duplicates are allowed in a binary search tree.

False

After deleting the desired item from a binary search tree, the resulting tree must be a binary search tree.

True

A binary tree has a special node called the ____ node.

a. super

b. root

c. superparent

d. rootleaf

b

Consider that A is a binary tree, C and D are the subtrees of A. Which of the following statements is always true?

a. C and D are binary trees.

b. C and D are search binary trees.

c. C and D are empty trees.

d. A is empty.

a

Each link in a binary tree node points to a(n) ____ of that node.

a. parent. b. child

c. value. d. sibling

b

Every node in a binary tree has at most ____ children.

a. one. b. two

c. three. d. four

b

Every node in a binary tree has ____ pointers.

a. one. b. two

c. three. d. four

b

A pointer to the root node of the binary tree is stored outside the binary

tree in a pointer variable, usually called the ____.

a. node. b. parent

c. root. d. nodeType

c

A node in a binary tree is called a(n) ____ if it has no left and right children.

a. edge

b. branch

c. leaf

d. path

c

In a binary tree, the level of the children of the root node is ____.

a. 0

b. 1

c. 2

d. 3

2

The ____ of a node in a binary tree is the number of branches on the path from the root to the node.

a. height

b. level

c. width

d. size

b

The three traversal algorithms discussed for binary trees are ____, ____, and ____.

a. order, preorder, postorder

b. in, preorder, order

c. order, preorder, post

d. inorder, preorder, postorder

d

The sequence of operations in a postorder traversal is ____.

a. traverse left; traverse right

b. traverse left; traverse right; visit

c. visit; traverse left; traverse right

d. traverse left; visit; traverse right

b

A binary tree is empty if root is ____.

a. '0'

b. 1

c. "zero"

d. nullptr

d

Assume the key of the left child below the root node of a binary search tree is 30. The value in the root node could be ____.

a. 0

b. 10

c. 30

d. 40

d

The key of the right child below the root node of a search binary tree is

40. The value in the root node could be ____.

a. 30

b. 40

c. 50

d. 60

a

In a binary search tree, the data in each node is ____ the data in the left child.

a. larger than

b. smaller than

c. equal to

d. larger or equal to

a