CS-260 Data Structures - Midterm & Final Multiple Choice Quiz

In practice, recursion should be used even when a problem has a simple iterative solution.

true

false

false

Data structures are part of an ADT's implementation.

true

false

true

Modularity describes a program that is organized into ______.

loosely coupled and highly cohesive modules

tightly coupled and highly cohesive modules

loosely coupled modules which are not cohesive

tightly coupled modules which are not cohesive

loosely coupled and highly cohesive modules

One can only recursively display the data in a linear linked list, not an array.

true

false

false

When the frequent operations on a list are random access for individual element and bi-directional stepping through, which of the following data structures is the best for the job?

Array

Linear Linked List

Doubly Linked List

Circular Linked List

Array

If a sorted list is implemented using a doubly linked list, we should do binary search to improve searching performance.

true

false

false

STL vector is implemented using a doubly linked list

true

false

false

To delete a node N from a linear linked list, you will need to ______.

set the pointer next in the node that precedes N to point to the node that follows N

set the pointer next in the node that precedes N to point to N

set the pointer next in the node that follows N to point to the node that precedes N

set the pointer next in N to point to the node that follows N

set the pointer next in the node that precedes N to point to the node that follows N

Which of the following statements deletes the node to which cur points?

prev->next = cur;

cur->next = prev;

cur->next = cur->next;

prev->next = cur->next;

prev->next = cur->next;

In a recursive method that writes a string of characters in reverse order, the base case is ______.

a string with a length of 0

a string whose length is a negative number

a string with a length of 3

a string that is a palindrome

a string with a length of 0

What does the following recursive algorithm display?

writeBack(in s:string)

if (s is empty)

return

else

{

Write the first character of s

writeBack(the string beginning at the second character of s)

}

nothing

the first character of s a number of times equal to the length of s

the string s

the string s backward

the string s

If the array6, 21, 35, 3, 6, 2, 13is added to a stack, in the order given, which of the following is the top of the stack?

2

6

3

13

13

If the array6, 21, 35, 3, 6, 2, 13is added to a queue, in the order given, which of the following is the back of the queue?

2

6

3

13

13

A pointer-based implementation of a queue that uses a linear linked list should have at least ______ external pointer(s).

one

two

three

four

two

Which of the following code fragments deletes the item at the front of a queue represented by a circular array?

front = MAX_QUEUE - front;

--count;

front = front - back;

--count;

front = (front+1) % MAX_QUEUE;

--count;

front = (back+1) % MAX_QUEUE;

--count;

front = (front+1) % MAX_QUEUE;

--count;

The ADT ______ allows you to insert into, delete from, and inspect the item at any position of the ADT.

stack

queue

list

array

list

______ is a collision-resolution scheme that uses an array of linked lists as a hash table.

Linear probing

Double hashing

Quadratic probing

Separate chaining

Separate chaining

Assuming a linked list of n nodes, the C++ statements

Node *cur = head;

while (cur != null)

{ cout << curr->item << endl;

cur = cur->next;

} // end while

require ______ assignment(s).

n

n-1

n+1

1

n+1

Assuming a linked list of n nodes, the C++ statements

Node *cur = head;

while (cur != null)

{ cout << curr->item << endl;

cur = cur->next;

} // end while

require ______ comparison(s).

n

n-1

n+1

1

n+1

Assuming a linked list of n nodes, the C++ statements

Node *cur = head;

while (cur != null) {

cout << curr->item << endl;

cur = cur->next;

} // end while

perform ______ write operations.

n

n-1

n+1

1

n

Which of the following growth-rate functions grows the fastest in value?

1

n

n^2

log2 n

n^2

Which of the following growth-rate functions indicates a problem whose time requirement is independent of the size of the problem?

1

n

2n

log2 n

1

In the worst case, a binary search in an array is ______.

O(n)

O(1)

O(log2 n)

O(n2)

O(log2 n)

Low-order terms in an algorithm's growth-rate function can be ignored.

true

false

true

A(n) ______ maps the search key of a table item into a location that will contain the item.

hash function

oredered list

stack

queue

hash function

hash function should be fast and easy to compute

true

false

true

When we use array of linked list to implement a hash table, the table can "grow" as needed.

true

false

true

If we use an array of linked list to implement a hash table, we have direct access to individual "chain."

true

false

true

If we use an array of linked list to implement hash table, "add" could be implemented in a way that no traversing is needed.

true

false

true

if we use an array of linked list to implement hash table, the "retrieve" function might require traversing through a "chain."

true

false

true

The ADT ______ is value-oriented.

list

stack

queue

binary search tree

binary search tree

The ADT stack manages an association between data items and the ______ of the data items.

names

values

sizes

positions

positions

The ______ of a tree is the number of nodes on the longest path from the root to a leaf.

height

length

depth

balance

height

A ______ of height h is full down to level h - 1, with level h filled in from left to right.

full binary tree

complete binary tree

balanced binary tree

general tree

complete binary tree

Which of the following is NOT a property of a complete binary tree of height h?

all nodes at level h - 2 and above have two children each

when a node at level h - 1 has children, all nodes to its left at the same level have two children each

when a node at level h - 1 has one child, it is a left child

all leaves are at level h

all leaves are at level h

The minimum height of a binary tree of n nodes is ______.

n

n / 2

(n / 2) - 2

élog2(n + 1)ù

élog2(n + 1)ù

Locating a particular item in a binary search tree of n nodes requires at most ______ comparisons.

n

n / 2

(n / 2) - 2

élog2(n + 1)ù

n

A full binary tree whose height is 4 has ______ nodes.

7

8

15

31

15

A 2-3 tree of height h always has at least ______ nodes.

h^2

h^2 - 2

2^h

2^h - 1

2^h - 1

A 2-3 tree implementation of a table is ______ for all table operations.

O(n)

O(log2 n)

O(n * log2 n)

O(n2)

O(log2 n)

Which of the following is NOT true about a red-black tree?

it is balanced

its insertion operation requires one pass from root to leaf

its deletion operation requires one pass from root to leaf

it requires more storage than a 2-3-4 tree

it requires more storage than a 2-3-4 tree

A(n) ______ is a balanced binary search tree.

2-3 tree

2-3-4 tree

red-black tree

n-ary tree

red-black tree

The balance of a binary search tree is sensitive to the order in which items are inserted into the tree.

true

false

true

The balance of a 2-3 tree is sensitive to the order in which items are inserted into the tree.

true

false

false

A 2-3 tree is never taller than a minimum-height binary search tree.

true

false

true

A red-black representation of a 2-3-4 tree is unique.

true

false

false

An AVL tree is a balanced binary search tree.

true

false

true

The ______ of a weighted graph have numeric labels.

vertices

edges

paths

cycles

edges

A graph-traversal algorithm stops when it ______.

first encounters the designated destination vertex

has visited all the vertices that it can reach

has visited all the vertices

has visited all the vertices and has returned to the origin vertex

has visited all the vertices that it can reach

An iterative DFS traversal algorithm uses a(n) ______.

list

array

queue

stack

stack

The first item to be removed from a priority queue is the item ______.

at the front of the priority queue

at the end the priority queue

with the highest value

with the highest priority value

with the highest priority value

In an array-based implementation of the priority queue, the pqDelete operation returns the item in ______.

items[size]

items[0]

items[size-1]

items[size+1]

items[size-1]

In a linear implementation of the priority queue based on a linked list, the item with the highest priority value is located ______.

at the beginning of the linked list

at the end of the linked list

in the middle of the linked list

at a random location in the linked list

at the beginning of the linked list

In a heap, the search keys of the children of a particular node have no relationship to each other.

true

false

true

The quicksort is ______ in the worst case.

O(n^2)

O(n^3)

O(n * log2 n)

O(log2 n)

O(n^2)

The efficiency of the selection sort depends on the initial arrangement of the data.

true

false

false

For large arrays, the insertion sort is prohibitively inefficient.

true

false

true

In a recursive mergesort, the actual sorting occurs during the recursive calls. The merge step simply puts two array segments together again.

true

false

false

To sort numeric data, the radix sort treats each number as a character string.

true

false

true

Given the fact that a selection sort of n items requires n^2/2 + 5 * n/2 - 3 major operations, the selection sort is

O(1)

O(n^2)

O(n)

O(n^2/2)

O(n^2)