Top of Form

An important advantage of the sequential tree implementation is that (select the
best answer):

Select one:

a. It is an extremely shallow tree

b. The data
structure can be transmitted between computers

c. It saves space because no pointers are
stored

d. It uses dynamic nodes

The correct answer is: It saves space because
no pointers are stored

Question 2

A solution is said to be efficient if
it:

Select one:

a. Solves the problem within the required resource constraints

b. Executes faster than other solutions

c. Is completed in the fewest number of
steps

d. Can be explained in the context of Big-Oh notation

The correct answer
is: Solves the problem within the required resource constraints

Question
3

Asymptotic Algorithm Analysis is primarily concerned with:

Select one:

a. The size of the constant in the algorithm running time equation

b. The speed of the
computing running the algorithm

c. The speed of the compiler

d. The growth rate
demonstrated in the algorithm running time equation

The correct answer is: The
growth rate demonstrated in the algorithm running time equation

Question
4

For the following code fragment, select the option which represents the most
appropriate asymptotic analysis:

/** @return Position of largest value in "A“
*/

static int largest(int[] A) {

int currlarge = 0; // Position of largest

for
(int i=1; i<A.length; i++)

if (A[currlarge] < A[i])

currlarge = i; // Remember
pos

return currlarge; // Return largest pos

}

Choice 1. Θ ( n
)

Choice 2. O( 2n )

Choice 3. Θ( n log n )

Choice 4. Ω( n2 )

(NOTE:
code fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
1

Question 5

The process of determining if two objects are in the same set
and then merging those sets is called:

Select one:

a. a Union Operation

b.
Union / Find

c. a Weighted Union

d. a Merge Operation

The correct answer
is: Union / Find

Question 6

A sequential tree can be represented using a bit
vector?

Select one:

True

False

The correct answer is
'True'.

Question 7

Enqueue and Dequeue are notations associated with which
data structure:

Select one:

a. Queue

b. Stack

c. List

d.
Array

The correct answer is: Queue

Question 8

True/False: The
stack data structure is implemented as a LIFO structure (last in first out)

Select
one:

True

False

The correct answer is 'True'.

Question
9

Correctly identify the following heap structure by selecting the best answer:

Select one:

a. partially ordered heap

b. max-heap structure

c. priority
heap

d. min-heap structure

The correct answer is: max-heap
structure

Question 10

True/False: Big Theta (Θ) indicates that the
Upper and Lower bounds of an algorithm are the same.

Select one:

True

False

The correct answer is 'True'.

Question 11

A finite set of
one or more nodes such that there is one designated node call the root is a: (select the best
answer)

Select one:

a. Parent root

b. a B+ tree data structure

c.
Index

d. Tree

The correct answer is: Tree

Question 12

If
A={1, 2, 3, 4} and B={4, 5, 6}, find A∪ B .

Select one:

a. {1,2,3,4,4,5,6}

b. {4}

c. {x | x is all positive integers}

d. {1,2,3,4,5,6}

The correct
answer is: {1,2,3,4,5,6}

Question 13

Select the answer that best defines
Huffman Coding:

Select one:

a. A set of coding rules that is typically used for
compression

b. A fixed length coding scheme for character representation

c. A tree
structure that trades off space and time requirements to provide a more efficient priority
queue

d. An approach of assigning codes to characters such that the frequency length of
the code depends upon the relative frequency of the corresponding character in use

The correct answer is: An approach of assigning codes to characters such that the
frequency length of the code depends upon the relative frequency of the corresponding character
in use

Question 14

A leaf is any node that:

Select one:

a. Has
one child

b. Is an internal node with no ancestors

c. Is any node with two empty
children

d. Is the ancestor of the root node

The correct answer is: Is any node with two empty children

Question 15

A linked list implementation relies upon static memory allocation where static refers to the requirement to pre-allocate all of the memory that will be used for the list.

Select one:

True

False

The correct answer is 'False'.

Question 16

For the following code fragment, select the option that represents the most appropriate asymptotic analysis:

for (int i = 1; i <= n; i *= 2) {

for (int j = 0; j < n; j++) {

count++;

}

}

Option 1. O( 1 )

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

Explanation: Here the outer loop is done log n times and the inner loop is done n times, so T(n) = n log n. (Note that the default base for logarithms in Computer Science is 2.)

The correct answer is: Option 3

Question 17

In linked lists there are no NULL links in:

Select one:

a. Single linked list

b. Linear doubly linked list

c. Circular linked list

d. None of these

The correct answer is: Circular linked list

Question 18

True/False: Big Theta (Θ) indicates that the Upper and Lower bounds of an algorithm are the same.

Select one:

True

False

The correct answer is 'True'.

Question 19

A list is said to be empty when all of its elements have a zero (0) value

Select one:

True

False

The correct answer is 'False'.

Question 20

A full binary tree has a restricted shape which starts at the root and fills the tree by levels from left to right.

Select one:

True

False

The correct answer is 'False'.

Question 21

Which of the following is NOT one of the design patterns outlined in our text.

Select one:

a. Flyweight

b. Visitor

c. Composite

d. Synergy

The correct answer is: Synergy

Question 22

The upper bound for the growth of the Algorithms running time is represented by (please select the best answer):

1. Big Oh (O)

2. Big Omega (Ω)

3. Big Theta (Θ)

4. Exponential growth

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice 1

Question 23

The most time consuming of the following operations on an array based list implementation is:

Select one:

a. Inserting a new element at position n-1 in the list where n is the number of elements in the list.

b. Inserting a new element into the head of the list.

c. Removing an element at position n-1 within the list

d. Removing an element from the tail of the list.

The correct answer is: Inserting a new element into the head of the list.

Question 24

Which of the following is not a characteristic of an algorithm?

Select one:

a. It must be correct

b. It must be composed of concrete steps

c. It can have no ambiguity

d. It must be composed of an infinite number of steps.

The correct answer is: It must be composed of an infinite number of steps.

Question 25

For the following code fragment, select the most appropriate asymptotic analysis:

// Towers of Hanoi

static void solveHanoi(int disks, char fromPole, char toPole, char withPole) {

if (disks >= 1) {

solveHanoi(disks-1, fromPole, withPole, toPole);

moveDisk(fromPole, toPole);

solveHanoi(disks-1, withPole, toPole, fromPole);

}

}

static void moveDisk(char fromPole, char toPole) {

moves++;

}

Option 1. O( n )

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The correct answer is: Option 2

Bottom of Form

For the following code fragment, select the option that represents the most appropriate
asymptotic analysis:

for (int i = 0; i < a.length; i++) {

System.out.println(a[i]);

}

Option 1. O( n )

Option 2. O( 2n )

Option 3.
O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The correct answer is: Option 1

Question
2

The weighted union rule joins a tree with fewer nodes to a tree with more nodes by
making the smaller tree’s root point to the root of the larger tree.

Select
one:

True

False

The correct answer is 'True'.

Question
3

The depth of node H in the following tree is:

Select one:

a.
3

b. 2

c. 4

d. 1

The correct answer is: 3

Question
4

The most significant difference between the B+-Tree and the BST is that the B+-Tree
stores records only at the leaf nodes.

Select one:

True

False

The
correct answer is 'True'.

Question 5

True/False: Big Theta (Θ)
indicates that the Upper and Lower bounds of an algorithm are the same.

Select one:

True

False

The correct answer is 'True'.

Question 6

The
quicksort is typically slower than the heapsort by a constant factor.

Select one:

True

False

The correct answer is 'False'.

Question 7

For
the following code fragment, select the choice which represents the most appropriate asymptotic
analysis:

static int function ( n ) {

sum = 0;

for (i=1; i<=n; i++)

sum += n;

return sum;

}

Choice 1. Ω( n2 )

Choice 2. Ω( log n2 )

Choice
3. Θ( n log n )

Choice 4. O ( n )

(NOTE: code fragment is not intended to be
functioning code)

Select one:

a. Cho =!Question 8

A
compound computed search that combines a binary search to get close to the required record and
then uses sequential search to find the item is referred to as a/an:

Select one:

a.
Zipf search

b. An Exact match search

c. A Dictionary search

d. bit map vector
search

The correct answer is: A Dictionary search

Question 9

The
process for visiting all of the nodes of a binary tree in some order is called a
traversal.

Select one:

True

False

The correct answer is
'True'.

Question 10

For the following code fragment, select the choice which
represents the most appropriate asymptotic analysis:

function ( n ) {

sum2 = 0;

for (k=1; k<=n; k*=2)

for (j=1; j<=k; j++)

sum2++;

}

Choice 1. O( 2n
)

Choice 2. Θ ( n )

Choice 3. Θ( n log n )

Choice 4. Ω( n2
)

(NOTE: code fragment is not intended to be functioning code)

Select
one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The
correct answer is: Choice 2

Question 11

A linked list creates order through
the use of pointers that link one element to another.

Select one:

True

False

The correct answer is 'True'.

Question 12

Inserting or
removing an item at position n-1 within a linked list has the same cost in terms ( n ) time as
the same operation in an array based implementation of a list.

Select one:

True

False

The correct answer is 'False'.

Question 13

Select the
answer that best defines Huffman Coding:

Select one:

a. A set of coding rules that is
typically used for compression

b. A fixed length coding scheme for character
representation

c. A tree structure that trades off space and time requirements to provide
a more efficient priority queue

d. An approach of assigning codes to characters such that
the frequency length of the code depends upon the relative frequency of the corresponding
character in use

The correct answer is: An approach of assigning codes to characters
such that the frequency length of the code depends upon the relative frequency of the
corresponding character in use

Question 14

A tree data structure whose shape
obeys the following definition,

o A node contains one or two keys

o Every internal
node has either 2 children if it contains 1 key or 3 children if it contains two keys

o All
leaves are at the same level in the tree

Is called a/an:

Select one:

a.
B*-Tree

b. BST

c. B+-Tree

d. 2-3 tree

The correct answer is: 2-3
tree

Question 15

Data is stored within the disk drive on the: (select the
best answer)

Select one:

a. Spindle

b. Platter

c. Cylinder

d.
Sector

The correct answer is: Platter

Question 16

For the
following code fragment, select the most appropriate asymptotic analysis:

// Towers of
Hanoi

static void solveHanoi(int disks, char fromPole, char toPole, char withPole) {

if (disks Hanoi(disks-1, withPole, toPole, fromPole);

}

}

static void
moveDisk(char fromPole, char toPole) {

moves++;

}

Option 1. O( n )

Option
2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option
1

b. Option 2

c. Option 3

d. Option 4

The correct answer is: Option
2

Question 17

The full binary tree theorem states “the number of
leaves in an empty full binary tree is@8 is 'False'.

Question 18

A full
binary tree has a restricted shape which starts at the root and fills the tree by levels from
left to right.

Select one:

True

False

The correct answer is
'False'.

Question 19

A list that organizes the order �8�U
�8�U$�
�U�:�
�U��8�U@�8�U@@�8�Unswer):

Select one:

a. Quadratic
Binary search order

b. A Zipf Distribution

c. A Self-organizing list

d. A
range query

The correct answer is: A Self-organizing list

Question
20

An exchange sort is one where: (select the best answer)

Select one:

a.
Records in an unsorted list are moved to a sorted list

b. Adjacent records in the list and
compared and exchanged

c. An inversion is executed

d. The sorting algorithm is said
to be stable

The correct answer is: Adjacent records in the list and compared and
exchanged

Question 21

An algorithm that breaks a file to be sorted in
smaller files called runs which are sorted and eventually put back together resulting in a
sorted file is called:

Select one:

a. Quicksort algorithm

b. Replacement sort
algorithm

c. An indexed key sort algorithm

d. Mergesort algorithm

The
correct answer is: Mergesort algorithm

Question 22

The lower bound for the
growth of the Algorithms running time is represented by (please the best answer):

1. Big Oh
(O)

2. Big Omega (Ω)

3. Big Theta (Θ)

4. Exponential growth

Select
one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The
correct answer is: Choice 2

Question 23

For the following code fragment,
select the choice which represents the most appropriate asymptotic analysis:

function ( n )
{

sum1 = 0;

for (i=1; i<=n; i++)

for (j=1; j<=n; j++)

sum1++;

}

Choice 1. Θ ( n2 )

Choice 2. O( 2n )

Choice 3. Θ( n
log n )

Choice 4. Ω( log n2 )

(NOTE: code fragment is not intended to be functioning
code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d.
Choice 4

The correct answer is: Choice 1

Question 24

For the
following code fragment, select the choice which represents the most appropriate asymptotic
analysis:

static int function ( n ) {

for (k=0; k<n; k++)

A[k] = k;

return A[k];

}

Choice 1. O ( n2 )

Choice 2. O( 2n )

Choice 3. Ω( n2
)

Choice 4. Θ ( n )

(NOTE: code fragment is not intended to be functioning
code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d.
Choice 4

The correct answer is: Choice 4

Question 25

A technique
that allows a programmer to use more main memory than exists in the computer is called: (select
the best answer)

Select one:

a. Buffer cache

b. Random access memory

c.
Secondary storage

d. Virtual memory

The correct answer is: Virtual
memory

Question 26

For the following code fragment, select the option that
represents the most appropriate asymptotic analysis:

public static int binarySearch(int[]
a, int key) {

int left = 0;

int right = a.length-1;

while (left <= right)
{

int mid = left + (right-left)/2;

if (key < a[mid]) right = mid-1;

else if
(key > a[mid]) left = mid+1;

else return mid;

}

//not found

return
-1;

}

Option 1. Ω( 1 ), O( log n )

Option 2. Ω( n ), O( 2n )

Option 3.
Θ( n log n )

Option 4. Θ( log n )

Select one:

a. Option 1

b.
Option 2

c. Option 3

d. Option 4

The correct answer is: Option
1

Question 27

For the following code fragment, select the choice which
represents the most appropriate asymptotic analysis:

static int function ( n ) {

for
(k=0; k<n; k++)

A[k] = k;

return A[k];

}

Choice 1. Θ ( n log n
)

Choice 2. O( 2n )

Choice 3. O( n )

Choice 4. Ω( n2 )

(NOTE: code fragment
is not intended to be functioning code)

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 28

A list is

Select one:

a. An ADT for storing and
retrieving data

b. A tree data structure

c. Finite ordered sequence of data
items

d. A collection of operations to implement an ADT

The correct answer is:
Finite ordered sequence of data items

Question 29

Internal Fragmentation
refers to: (select the best answer)

Select one:

a. Space that is left empty because
records do not fit evenly into a sector

b. Space allocated to a file that is not
physically adjacent on the disk drive

c. Space that is left empty because records do not
fit evenly into a sector or Space allocated to a file that is not physically adjacent

d.
None of the options

The correct answer is: Space that is left empty because records
do not fit evenly into a sector or Space allocated to a file that is not physically
adjacent

Question 30

The best asymptotic analysis for the selection sort is
represented by (select the best option):

Option 1. O( n log n )

Option 2. Ω( n2
)

Option 3. O( n2 )

Option 4. Θ( n2 )

Select one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The correct answer is: Option
4

Question 31

Each record of a database normally has a unique identifier
called the:

Select one:

a. Secondary Key

b. Primary index

c. Primary
key

d. Index key

The correct answer is: Primary key

Question
32

True/False: The queue data structure is implemented as FIFO structure (first in
first out)

:

Select one:

True

False

The correct answer is
'True'.

Question 33

The benefit of a quicksort is that it provides excellent
performance in both the average and worst case:

Select one:

True

False

The correct answer is 'False'.

Question 34

Setting the
dirty bit causes what action to be performed on a block: (select the best answer)

Select
one:

a. It is deleted because it is no longer consistent

b. It flushes or writes the
block out to the disk

c. Refreshes the data by re-reading the block

d. It cleans the
cache by flushing all data from the cache

The correct answer is: It flushes or writes
the block out to the disk

Question 35

According to the properties of
logarithms, log(nm) =

Note: Due to issues with HTML formatting, an exponent is represented
by preceding it with the ^ symbol. As such x^2 is equivalent to x2.

Select one:

a.
log n – log m

b. n log n

c. log n + log m

d. log(n^m)

The
correct answer is: log n + log m

Question 36

A sorting algorithm that
assigns records to bins and then relies on some other sorting technique to sort the records
within each bin called:

Select one:

a. Radix Sort

b. Quicksort

c. Hash
sort

d. Bucket sort

The correct answer is: Bucket sort

Question
37

The upper bound for the growth of the Algorithms running time is represented by
(please select the best answer):

1. Big Oh (O)

2. Big Omega (Ω)

3. Big Theta
(Θ)

4. Exponential growth

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice 1

Question
38

In linked lists there are no NULL links in:

Select one:

a. Single
linked list

b. Linear doubly linked list

c. Circular linked list

d. None of
these

The correct answer is: Circular linked list

Question 39

For
the following code fragment, select the option that represents the most appropriate asymptotic
analysis:

for (int i = 1; i <= n; i *= 2) {

for (int j = 0; j < n; j++)
{

count++;

}

}

Option 1. O( 1 )

Option 2. O( 2n )

Option 3. O( n
log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c.
Option 3

d. Option 4

Explanation: Here the outer loop is done log n times and
the inner loop is done n times, so T(n) = n log n. (Note that the default base for logarithms in
Computer Science is 2.)

The correct answer is: Option 3

Question 40

For
the following code fragment, select the choice which represents the most appropriate asymptotic
analysis:

static int function ( n ) {

sum = 0;

for (j=1; j<=n; j++)

for (i=1; i<=j; i++)

sum++;

return sum;

}

Choice 1. Θ ( n
)

Choice 2. O( 2n )

Choice 3. Θ( n2 )

Choice 4. Ω( n2 )

(NOTE: code
fragment is not intended to be functioning code)

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 41

The upper bound for the growth of the Algorithms running time
is represented by:

Select one:

a. Big Oh (O)

b. Big Omega (Ω)

c. Big
Theta (Θ)

d. Exponential growth

The correct answer is: Big Oh
(O)

Question 42

Which of the following is NOT one of the design patterns
outlined in our text.

Select one:

a. Flyweight

b. Visitor

c.
Composite

d. Synergy

The correct answer is: Synergy

Question
43

For the following code fragment, select the choice which represents the most
appropriate asymptotic analysis:

function ( n ) {

sum1 = 0;

for (k=1; k<=n;
k*=2)

for (j=1; j<=n; j++)

sum1++;

}

Choice 1. Θ ( n
)

Choice 2. O( 2n )

Choice 3. Θ( n log n )

Choice 4. Ω( n2 )

(NOTE:
code fragment is not intended to be functioning code)

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 44

When big-Oh and coincide, we indicate this by using (select
the best answer):

1. Big Oh (O)

2. Big Omega (Ω)

3. Big Theta (Θ)

4.
Exponential growth

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice 3

Question 45

A
traversal that visits the left subtree, then the node, and then the right subtree is
called:

Select one:

a. Preorder Traversal

b. Postorder Traversal

c. Inorder Traversal

d. Outoforder Traversal

The correct answer is: Inorder
Traversal

Question 46

A sequential tree can be represented using a bit
vector?

Select one:

True

False

The correct answer is
'True'.

Question 47

A list is said to be empty when all of its elements have
a zero (0) value

Select one:

True

False

The correct answer is
'False'.

Question 48

A sort algorithm that uses two nested loops with the
inner loop moving through the array from bottom to top is called the:

Select one:

a.
Insertion sort

b. Bubble sort

c. Inversion sort

d. Selection
sort

The correct answer is: Bubble sort

Question 49

Which of the
following is not a characteristic of an algorithm?

Select one:

a. It must be
correct

b. It must be composed of concrete steps

c. It can ha =Per is: It must be
composed of an infinite number of steps.

Question 50

Which of the following
is not a mathematical proof technique?

Select one:

a. Proof by mathematical
induction

b. Proof by contradiction

c. Direct proof

d. Proof by
consensus

The correct answer is: Proof by consensus

Question
51

True/False: Big Theta (Θ) indicates that the Upper and Lower bounds of an
algorithm are the same.

Select one:

True

False

The correct answer is
'True'.

Question 52

A collection of one or more trees is called:

Select
one:

a. Trees

b. Multiple Spanning Trees

c. a Forest

d.
Traversals

The correct answer is: a Forest

Question 53

The most
time consuming of the following operations on an array based list implementation is:

Select
one:

a. Inserting a new element at position n-1 in the list where n is the number of
elements in the list.

b. Inserting a new element into the head of the list.

c.
Removing an element at position n-1 within the list

d. Removing an element from the tail
of the list.

The correct answer is: Inserting a new element into the head of the
list.

Question 54

In a queue, placing new items in the queue is referred to
as a push and taking an item out of the queue is called a pop.

Select one:

True

False

The correct answer is 'False'.

Question 55

A method that is
designed to create extremely shallow trees is called:

Select one:

a. Dynamic node
implementation

b. Union/Find

c. The list of children method

d. Path
compression

The correct answer is: Path compression

Question
56

Correctly identify the following heap structure by selecting the best
answer:

Select one:

a. partially ordered heap

b. max-heap
structure

c. priority heap

d. min-heap structure

The correct answer is:
max-heap structure

Question 57

True/False: There is always one most
efficient algorithm to solve a particular problem.

Select one:

True

False

The correct answer is 'False'.

Question 58

For the
following code fragment, select the option that represents the most appropriate asymptotic
analysis:

if (a.length > 0) {

return a[a.length - 1];

} else {

throw
new NoSuchElementException();

}

Option 1. O( 1 )

Option 2. O( 2n )

Option 3.
O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

Explanation: Here n = a.length, and T(n) = 1.

The
correct answer is: Option 1

Question 59

An ADT is:

Select one:

a.
A type together with a collection of operations to manipulate the type

b. An
implementation of a flyweight design pattern

c. The realization of a data type as a
software component

d. An implementation in java of a class for a data type

The
correct answer is: The realization of a data type as a software search algorithms:

Select
one:

a. Buffer cache access methods

b. Sequential and list methods

c. Direct
access by key value (hashing)

d. Tree indexing methods

The correct answer is:
Buffer cache access methods

Question 61

A preorder traversal visits every
node starting at the leaf nodes and working up the tree.

Select one:

True

False

The correct answer is 'False'.

Question 62

A tree whose
internal nodes all have exactly K children is called @8

According to textbook by Shaffer, a
heap data structure has two properties which are:

Select one:

a. every node stores a
value less than or equal to that of its children and it is a complete binary tree

b. it is
a min-heap and is partially ordered

c. it is a complete binary tree and the values stored
in it are partially ordered

d. it is a priority queue and is in Θ( n
)

The correct answer is: it is a complete binary tree and the values stored in it are
partially ordered

Question 64

A traversal that visits each node before
visiting its children is called �8�U �8�U$�
�U�:�
�U��8�U@�8�U@@�8�Ur /> d. Outoforder Traversal

The
correct answer is: Preorder traversal

Question 65

A traversal of a general
tree that traverses the roots subtrees from left to right, then visits the root is called a
preorder traversal.

Select one:

True

False

The correct answer is
'False'.

Question 66

Which of the following is NOT one of the buffer pool
heuristics defined in the text : (select the best answer)

Select one:

a. FIFO

b. LIFO

c. LRU

d. LFU

The correct answer is: LIFO

Question
67

A solution is said to be efficient if it:

Select one:

a. Solves the
problem within the required resource constraints

b. Executes faster than other
solutions

c. Is completed in the fewest number of steps

d. Can be explained in the
context of Big-Oh notation

The correct answer is: Solves the problem within the
required resource constraints

Question 68

The list of children approach uses
both pointers and an array structure to represent the tree.

Select one:

True

False

The correct answer is 'True'.

Question 69

A characteristic
of RAM (random access memory) is that it is persistent and is not lost when the power to a
computer is turned off.

Select one:

True

False

The correct answer is
'False'.

Question 70

For the following code fragment, select option that
represents the most appropriate asymptotic analysis:

for (i=0; i<n; i++) {

//

// Search in array a for smallest element starting at i to n-1

//

minIndex
= findSmallestElement(a, i, n-1)

a[i] = a[minIndex];

}

findSmallestElement( int
a[], int i, int n ) {

int largest = a[i];

while(i<n) {

if(a[i]
>a[largest])

largest = i;

i++;

}

return(largest);

}

Option
1. O( n )

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option
4

index-of-smallest element in a[i..j] takes j-i+1 operations

• n + (n-1) +
(n-2) + (n-3) + ... + 3 + 2 + 1

• this is n2

The correct answer is: Option
4

Question 71

Push and Pop are notations associated with which data
structure:

Select one:

a. Queue

b. Stack

c. List

d.
Array

The correct answer is: Stack

Question 72

For the following
code fragment, select the choice which represents the most appropriate asymptotic
analysis:

function ( n ) {

sum2 = 0;

for (i=1; i<=n; i++)

for (j=1;
j<=i; j++)

sum2++;

}

}

Choice 1. Ω ( 1 )

Choice 2. O( 2n
)

Choice 3. Θ( n2 )

Choice 4. Ω( n2 )

(NOTE: code fragment is not intended
to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c.
Choice 3

d. Choice 4

The correct answer is: Choice 3

Question
73

The process of storing records in the order that they were added to a file is
called:

Select one:

a. Entry-sequenced file

b. Binary Sequenced file

c.
LIFO file format

d. Tombstone approach

The correct answer is: Entry-sequenced
file

Question 74

Secondary storage is characterized by the
following:

Select one:

a. It is persistent

b. It is faster than primary
storage

c. It is volatile

d. It is more expensive than primary
storage

The correct answer is: It is persistent

Question 75

Which
of the following items is NOT true for Array-Based Lists (please select the best
choice):

Choice 1. Insertion and deletion operations are ( n )

Choice 2. Direct
access of an item in the array is ( 1 )

Choice 3. Space used grows dynamically as the
array is populated

Choice 4. Array contains wasted space if array positions are not
full

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice
4

The correct answer is: Choice 3

Question 76

A linear index is
an index file organized as a sequence of key/pointer pairs where the keys are in a sorter
order.

Select one:

True

False

The correct answer is
'True'.

Question 77

In a stack which option would access the 3rd element
from the top of the stack S

Option 1. S.push(-1);

Option 2. S.dequeue(-3);

Option
3. S.pop();

S.pop();

S.pop();

Option 4. S.pop(n-3);

Select one:

a.
Option 1

b. Option 2

c. Option 3

d. Option 4

The correct answer is:
Option 3

Question 78

For the following code fragment, select the option that
represents the most appropriate asymptotic analysis:

// Recursive Fibonacci
generator

static long fibr(int n) {

if ((n == 1) || (n == 2)) return 1; // Base
case

return fibr(n-1) + fibr(n-2); // Recursive call

}

Option 1. O( n
)

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The
correct answer is: Option 2

Question 79

A binary tree traversal that lists
every node in the tree exactly once is called:

Select one:

a. a Traversal

b. A
visitor design pattern

c. An enumeration

d. Natural ordering sequence

The
correct answer is: An enumeration

Question 80

The process of storing blocks
of data in main memory after reading from disk is referred to as:

Select one:

a.
Buffering

b. Hashing

c. Pooling

d. Indexing

The correct answer is:
Buffering

Question 81

For the following code fragment, select the choice
which represents the most appropriate asymptotic analysis:

static int function ( n )
{

sum = 0;

for (i=1; i<=n; i++)

sum += n;

return
sum;

}

Choice 1. Ω( n2 )

Choice 2. Θ ( n2 )

Choice 3. O( log n
)

Choice 4. O( n )

(NOTE: code fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice
4

The correct answer is: Choice 4

Question 82

For the following
code fragment, select the choice which represents the most appropriate asymptotic
analysis:

/** @return The position of an element in sorted array A with value k. If k is
not in A,return A.length. */

static int binary(int[] A, int k) {

int l = -1; // Set l
and r

int r = A.length; // beyond array bounds

while (l+1 != r) { // Stop when l, r
meet

int i = (l+r)/2; // Check middle

if (k < A[i]) r = i; // In left half

if (k == A[i]) return i; // Found it

if (k > A[i]) l = i; // In right half

}

return A.length; // Search value not in A

}

Choice 1. Θ ( n
)

Choice 2. O( 2n )

Choice 3. O( log n )

Choice 4. Ω( n2 )

(NOTE: code
fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 83

A linked list implementation relies upon static memory
allocation where static refers to the requirement to pre-allocate all of the memory that will be
used for the list.

Select one:

True

False

The correct answer is
'False'.

Question 84

A traversal that visits each node after visiting its
children is called:

Select one:

a. Preorder Traversal

b. Postorder
Traversal

c. Inorder Traversal

d. Outoforder Traversal

The correct answer
is: Postorder Traversal

Question 85

A sort where the list is divided into
halves, the halves sorted and these two halves are merged is called:

Select one:

a.
Mergesort

b. Binary sort

c. Quicksort

d. Heapsort

The correct
answer is: Mergesort

Question 86

A coding scheme that replaces repeated
occurrences of strings with a pointer to the location in the file of the first occurrence of the
string is called Ziv-Lempel coding.

Select one:

True

False

The
correct answer is 'True'.

Question 87

A sort that features a limit of n-1 of
record swaps is called:

Select one:

a. Insertion sort

b. Bubble sort

c.
Inversion sort

d. Selection sort

The correct answer is: Selection
sort

Question 88

A finite set of one or more nodes such that there is one
designated node call the root is a: (select the best answer)

Select one:

a. Parent
root

b. a B+ tree data structure

c. Index

d. Tree

The correct
answer is: Tree

Question 89

The freelist …

Select one:

a.
Provides access to memory within the operating system that has not yet been allocated

b.
Provides access to memory objects which have no Big O ( n ) time.

c. Facilitates and
encourages the use of the new operator.

d. Holds the list nodes that are no longer in
use.

The correct answer is: Holds the list nodes that are no longer in
use.

Question 90

For the following code fragment, select the option which
represents the most appropriate asymptotic analysis:

static int function ( n ) {

sum
= 0;

for (i=1; i<=n; i++)

sum += n;

return sum;

}

Option 1. Ω( n2
)

Option 2. Θ ( n )

Option 3. O( log n )

Option 4. O( 2n )

(NOTE: code
fragment is not intended to be functioning code)

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
2

Question 91

True/False: The stack data structure is implemented as a LIFO
structure (last in first out)

Select one:

True

False

The correct
answer is 'True'.

Question 92

A leaf is any node that:

Select
one:

a. Has one child

b. Is an internal node with no ancestors

c. Is any node
with two empty children

d. Is the ancestor of the root node

The correct answer
is: Is any node with two empty children

Question 93

Which of the following
is NOT true for Linked Lists structures (please select the best choice):

Choice 1.
Insertion and deletion are ( 1 ).

Choice 2. Direct access of an item in the list structure
is ( n ).

Choice 3. Space grows with number of elements.

Choice 4. There is no
overhead associated with elements in the list structure

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
4

Question 94

Enqueue and Dequeue are notations associated with which data
structure:

Select one:

a. Queue

b. Stack

c. List

d. Array

public E getValue
( ) {

assert (curr >= 0) && (curr < listSize) :

"No current
element";

return listArray[curr];

}

Choice 1. Θ ( n )

Choice 2. O( 2n
)

Choice 3. Θ( n log n )

Choice 4. O( 1 )

(NOTE: code fragment is not
intended to be functioning code)

Select one:

a. Choice 1

b.
Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
4

Question 96

For the following code fragment, select the option which
represents the most appropriate asymptotic analysis:

/** @return Position of largest value
in "A“ */

static int largest(int[] A) {

int currlarge = 0; // Position of
largest

for (int i=1; i<A.length; i++)

if (A[currlarge] < A[i])

currlarge = i; // Remember pos

return currlarge; // Return largest pos

}

Choice 1. Θ ( n )

Choice 2. O( 2n )

Choice 3. Θ( n log n
)

Choice 4. Ω( n2 )

(NOTE: code fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice
4

The correct answer is: Choice 1

Question 97

The process of
determining if two objects are in the same set and then merging those sets is
called:

Select one:

a. a Union Operation

b. Union / Find

c. a Weighted
Union

d. a Merge Operation

The correct answer is: Union /
Find

Question 98

The implementation of a data type as a data structure is
the physical form of an ADT.

Select one:

True

False

The correct
answer is 'True'.

Question 99

An important advantage of the sequential tree
implementation is that (select the best answer):

Select one:

a. It is an extremely
shallow tree

b. The data structure can be transmitted between computers

c. It saves
space because no pointers are stored

d. It uses dynamic nodes

The correct
answer is: It saves space because no pointers are stored

Question 100

The
processing time or cost of a sort is defined by the number of comparisons and exchanges that
must be made during processing. What is the average cost of the heapsort?:

Option 1. O( n
log n )

Option 2. Ω( n2 )

Option 3. O( n2 )

Option 4. Θ( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The
correct answer is: Option 1

Question 101

A significant benefit to using an
index to hold and sort keys to a file is:

Select one:

a. Smaller keys require less
I/O

b. The entire sort can always be completed in memory

c. The head of the disk
drive does not need to move

d. There is no seek time added to the latency of I/O
operations

The correct answer is: Smaller keys require less I/O

Question
102

If A={1, 2, 3, 4} and B={4, 5, 6}, find A∪ B .

Select one:

a.
{1,2,3,4,4,5,6}

b. {4}

c.p

Question 103

The process of associating a
key with the location of a corresponding data record is called folding.

Select one:

True

False

The correct answer is 'False'.

Question
104

Asymptotic Algorithm Analysis is primarily concerned with:

Select one:

a. The size of the constant in the algorithm running time equation

b. The speed of the
computing running the algorithm

c. The speed of the compiler

d. The growth rate
demonstrated in the algorithm running time equation

The correct answer is: The
growth@8 in a quicksort algorithm?

Select one:

a. It identifies the maxkey
value

b. It specifies the point where the array will be subdivided into partitions and
each partition then sorted

c. It defines the sequence for merging in the sort

d. It
indicates the index of the current record being compared

The correct answer is: It
specifies the point where the array will be subdivided into partitions and each partition then
sorted

Question 106

Recursion is when an algorithm uses a series of loop
structures to repeat an operation until the answer has been computed.

Select one:

True

False

The correct answer is 'False'.

A sort that features a limit of
n-1 of record swaps is called:

Select one:

a. Insertion sort

b. Bubble
sort

c. Inversion sort

d. Selection sort

The correct answer is: Selection
sort

Question 2

A �8�U �8�U$�
�U�:�
�U��8�U@�8�U@@�8�U/> False

The correct answer is
'False'.

Question 3

A characteristic of RAM (random access memory) is that
it is persistent and is not lost when the power to a computer is turned off.

Select
one:

True

False

The correct answer is 'False'.

Question
4

Correctly identify the following heap structure by selecting the best answer:

Select one:

a. partially ordered heap

b. max-heap structure

c. priority
heap

d. min-heap structure

The correct answer is: max-heap
structure

Question 5

True/False: The queue data structure is implemented as
FIFO structure (first in first out)

:

Select one:

True

False

The correct answer is 'True'.

Question 6

The process for
visiting all of the nodes of a binary tree in some order is called a traversal.

Select
one:

True

False

The correct answer is 'True'.

Question
7

A traversal that visits each node before visiting its children is
called:

Select one:

a. Preorder traversal

b. Postorder traversal

c.
Inorder Traversal

d. Outoforder Traversal

The correct answer is: Preorder
traversal

Question 8

A sort where the list is divided into halves, the
halves sorted and these two halves are merged is called:

Select one:

a.
Mergesort

b. Binary sort

c. Quicksort

d. Heapsort

The correct
answer is: Mergesort

Question 9

A linked list implementation relies upon
static memory allocation where static refers to the requirement to pre-allocate all of the
memory that will be used for the list.

Select one:

True

False

The
correct answer is 'False'.

Question 10

For the following code fragment,
select the choice which represents the most appropriate asymptotic analysis:

public E
getValue ( ) {

assert (curr >= 0) && (curr < listSize) :

"No current
element";

return listArray[curr];

}

Choice 1. Θ ( n )

Choice 2. O( 2n
)

Choice 3. Θ( n log n )

Choice 4. O( 1 )

(NOTE: code fragment is not
intended to be functioning code)

Select one:

a. Choice 1

b.
Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
4

Question 11

The list of children approach uses both pointers and an array
structure to represent the tree.

Select one:

True

False

The correct
answer is 'True'.

Question 12

The upper bound for the growth of the
Algorithms running time is represented by:

Select one:

a. Big Oh (O)

b. Big
Omega (Ω)

c. Big Theta (Θ)

d. Exponential growth

The correct answer
is: Big Oh (O)

Question 13

A preorder traversal visits every node starting
at the leaf nodes and working up the tree.

Select one:

True

False

The correct answer is 'False'.

Question 14

Select the
answer that best defines Huffman Coding:

Select one:

a. A set of coding rules that is
typically used for compression

b. A fixed length coding scheme for character
representation

c. A tree structure that trades off space and time requirements to provide
a more efficient priority queue

d. An approach of assigning codes to characters such that
the frequency length of the code depends upon the relative frequency of the corresponding
character in use

The correct answer is: An approach of assigning codes to characters
such that the frequency length of the code depends upon the relative frequency of the
corresponding character in use

Question 15

An exchange sort is one where:
(select the best answer)

Select one:

a. Records in an unsorted list are moved to a
sorted list

b. Adjacent records in the list and compared and exchanged

c. An
inversion is executed

d. The sorting algorithm is said to be stable

The correct
answer is: Adjacent records in the list and compared and exchanged

Question
16

The processing time or cost of a sort is defined by the number of comparisons and
exchanges that must be made during processing. What is the average cost of the
heapsort?:

Option 1. O( n log n )

Option 2. Ω( n2 )

Option 3. O( n2 )

Option
4. Θ( n2 )

Select one:

a. Option 1

b. Option 2

c. Option 3

d.
Option 4

The correct answer is: Option 1

Question 17

A linked
list creates order through the use of pointers that link one element to another.

Select
one:

True

False

The correct answer is 'True'.

Question
18

A technique that allows a programmer to use more main memory than exists in the
computer is called: (select the best answer)

Select one:

a. Buffer cache

b.
Random access memory

c. Secondary storage

d. Virtual memory

The correct
answer is: Virtual memory

Question 19

A list that organizes the order of
records within the list based upon patterns of actual record access is called a/an (select the
best answer):

Select one:

a. Quadratic Binary search order

b. A Zipf
Distribution

c. A Self-organizing list

d. A range query

The correct
answer is: A Self-organizing list

Question 20

For the following code
fragment, select the choice which represents the most appropriate asymptotic
analysis:

static int function ( n ) {

sum = 0;

for (j=1; j<=n; j++)

for (i=1; i<=j; i++)

sum++;

return sum;

}

Choice 1. Θ ( n
)

Choice 2. O( 2n )

Choice 3. Θ( n2 )

Choice 4. Ω( n2 )

(NOTE: code
fragment is not intended to be functioning code)

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 21

A tree data structure whose shape obeys the following
definition,

o A node contains one or two keys

o Every internal node has either 2
children if it contains 1 key or 3 children if it contains two keys

o All leaves are at the
same level in the tree

Is called a/an:

Select one:

a. B*-Tree

b.
BST

c. B+-Tree

d. 2-3 tree

The correct answer is: 2-3
tree

Question 22

A collection of one or more trees is called:

Select
one:

a. Trees

b. Multiple Spanning Trees

c. a Forest

d.
Traversals

The correct answer is: a Forest

Question 23

The most
significant difference between the B+-Tree and the BST is that the B+-Tree stores records only
at the leaf nodes.

Select one:

True

False

The correct answer is
'True'.

Question 24

A list is

Select one:

a. An ADT for storing
and retrieving data

b. A tree data structure

c. Finite ordered sequence of data
items

d. A collection of operations to implement an ADT

The correct answer is:
Finite ordered sequence of data items

Question 25

Which of the following is
NOT one of the buffer pool heuristics defined in the text : (select the best answer)

Select
one:

a. FIFO

b. LIFO

c. LRU

d. LFU

The correct answer is:
LIFO

Question 26

Which of the following is not one of the general approaches
to search algorithms:

Select one:

a. Buffer cache access methods

b. Sequential
and list methods

c. Direct access by key value (hashing)

d. Tree indexing
methods

The correct answer is: Buffer cache access methods

Question
27

Which of the following is not a mathematical proof technique?

Select
one:

a. Proof by mathematical induction

b. Proof by contradiction

c. Direct
proof

d. Proof by consensus

The correct answer is: Proof by
consensus

Question 28

A tree whose internal nodes all have exactly K
children is called a K-ary tree.

Select one:

True

False

The correct
answer is 'True'.

Question 29

The freelist …

Select one:

a. Provides access to memory within the operating system that has not yet been allocated

b. Provides access to memory objects which have no Big O ( n ) time.

c. Facilitates and
encourages the use of the new operator.

d. Holds the list nodes that are no longer in
use.

The correct answer is: Holds the list nodes that are no longer in
use.

Question 30

A full binary tree has a restricted shape which starts at
the root and fills the tree by levels from left to right.

Select one:

True

False

The correct answer is 'False'.

Question 31

For the
following code fragment, select the option that represents the most appropriate asymptotic
analysis:

for (int i = 1; i <= n; i *= 2) {

for (int j = 0; j < n; j++)
{

count++;

}

}

Option 1. O( 1 )

Option 2. O( 2n )

Option 3. O( n
log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c.
Option 3

d. Option 4

Explanation: Here the outer loop is done log n times and
the inner loop is done n times, so T(n) = n log n. (Note that the default base for logarithms in
Computer Science is 2.)

The correct answer is: Option 3

Question 32

A
leaf is any node that:

Select one:

a. Has one child

b. Is an internal node with
no ancestors

c. Is any node with two empty children

d. Is the ancestor of the root
node

The correct answer is: Is any node with two empty children

Question
33

For the following code fragment, select the most appropriate asymptotic
analysis:

// Towers of Hanoi

static void solveHanoi(int disks, char fromPole, char
toPole, char withPole) {

if (disks >= 1) {

solveHanoi(disks-1, fromPole,
withPole, toPole);

moveDisk(fromPole, toPole);

solveHanoi(disks-1, withPole, toPole,
fromPole);

}

}

static void moveDisk(char fromPole, char toPole) {

moves++;

}

Option 1. O( n )

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c. Option
3

d. Option 4

The correct answer is: Option 2

Question
34

For the following code fragment, select the choice which represents the most
appropriate asymptotic analysis:

function ( n ) {

sum1 = 0;

for (k=1; k<=n;
k*=2 =

Choice 3. Θ( n log n )

Choice 4. Ω( n2 )

(NOTE: code fragment is not
intended to be functioning code)

Select one:

a. Choice 1

b. Choice
2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 35

Asymptotic Algorithm Analysis is primarily concerned
with:

Select one:

a. The size of the constant in the algorithm running time
equation

b. The speed of the computing running the algorithm

c. The speed of the
compiler

d. The growth rate demonstrated in the algorithm running time
equation

The correct answer is: The growth rate demonstrated in the algorithm running
time equation

Question 36

For the following code fragment, select the choice
which represents the most appropriate asymptotic analysis:

static int function ( n )
{

sum = 0;

for (i=1; i<=n; i++)

sum += n;

return
sum;

}

Choice 1. Ω( n2 )

Choice 2. Ω( log n2 )

Choice 3. Θ( n log n
)

Choice 4. O ( n )

(NOTE: code fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d.
Choice 4

The correct answer is: Choice 4

Question 37

The benefit
of a quicksort is that it provides excellent performance in both the average and worst
case:

Select one:

True

False

The correct answer is
'False'.

Question 38

If A={1, 2, 3, 4} and B={4, 5, 6}, find A∪ B
.

Select one:

a. {1,2,3,4,4,5,6}

b. {4}

c. {x | x is all positive
integers}

d. {1,2,3,4,5,6}

The correct answer is:
{1,2,3,4,5,6}

Question 39

The weighted union rule joins a tree with fewer
nodes to a tree with more nodes by making the smaller tree’s root point to the root of the
larger tree.

Select one:

True

False

The correct answer is
'True'.

Question 40

A compound computed search that combines a binary search
to get close to the required record and then uses sequential search to find the item is referred
to as a/an:

Select one:

a. Zipf search

b. An Exact match search

c. A
Dictionary search

d. bit map vector search

The correct answer is: A Dictionary
search

Question 41

The process of storing records in the order that they
were added to a file is called:

Select one:

a. Entry-sequenced file

b. Binary
Sequenced file

c. LIFO file format

d. Tombstone approach

The correct
answer is: Entry-sequenced file

Question 42

Each record of a database
normally has a unique identifier called the:

Select one:

a. Secondary Key

b.
Primary index

c. Primary key

d. Index key

The correct answer is: Primary
key

Question 43

For the following code fragment, select the choice which
represents the most appropriate asymptotic analysis:

static int function ( n ) {

for
(k=0; k<n; k++)

A[k] = k;

returnpΩ( n2 )

(NOTE: code fragment is not
intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 44

For the following code fragment, select the option that
represents the most appropriate asymptotic analysis:

// Recursive Fibonacci
generator

static long fibr(int n) {

if ((n == 1) || (n == 2)) return 1; // Base
case

return fibr(n-1) + fibr(n-2); // Recursive call

}

Option 1. O( n
)

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2
)

Selec@82

Question 45

A traversal that visits each node after visiting
its children is called:

Select one:

a. Preorder Traversal

b. Postorder
Traversal

c. Inorder Traversal

d. Outoforder Traversal

The correct answer
is: Postorder Traversal

Question 46

True/False: Big Theta (Θ)
indicates that the Upper and Lower bounds of an algorithm are the same.

Select one:

True

False

The correct answer is 'True'.

Question 47

A sort
algorithm that uses two nested loops with the inner loop moving through the array from bottom to
top is called the:

Select one:

a. Insertion sort

b. Bubble sort

c.
Inversion sort

d. Selection sort

The correct answer is: Bubble
sort

Question 48

The most time consuming of the following operations on an
array based list implementation is:

Select one:

a. Inserting a new element at
position n-1 in the list where n is the number of elements in the list.

b. Inserting a new
element into the head of the list.

c. Removing an element at position n-1 within the
list

d. Removing an element from the tail of the list.

The correct answer is:
Insert �8�U �8�U$�
�U�:�
�U��8�U@�8�U@@�8�Ues repeated occurrences of strings with a
pointer to the location in the file of the first occurrence of the string is called Ziv-Lempel
coding.

Select one:

True

False

The correct answer is
'True'.

Question 50

Internal Fragmentation refers to: (select the best
answer)

Select one:

a. Space that is left empty because records do not fit evenly
into a sector

b. Space allocated to a file that is not physically adjacent on the disk
drive

c. Space that is left empty because records do not fit evenly into a sector or Space
allocated to a file that is not physically adjacent

d. None of the options

The
correct answer is: Space that is left empty because records do not fit evenly into a sector or
Space allocated to a file that is not physically adjacent

Question
51

True/False: There is always one most efficient algorithm to solve a particular
problem.

Select one:

True

False

The correct answer is
'False'.

Question 52

A sorting algorithm that assigns records to bins and
then relies on some other sorting technique to sort the records within each bin
called:

Select one:

a. Radix Sort

b. Quicksort

c. Hash sort

d.
Bucket sort

The correct answer is: Bucket sort

Question 53

In a
queue, placing new items in the queue is referred to as a push and taking an item out of the
queue is called a pop.

Select one:

True

False

The correct answer is
'False'.

Question 54

A binary tree traversal that lists every node in the
tree exactly once is called:

Select one:

a. a Traversal

b. A visitor design
pattern

c. An enumeration

d. Natural ordering sequence

The correct answer
is: An enumeration

Question 55

A finite set of one or more nodes such that
there is one designated node call the root is a: (select the best answer)

Select one:

a. Parent root

b. a B+ tree data structure

c. Index

d. Tree

The
correct answer is: Tree

Question 56

An important advantage of the sequential
tree implementation is that (select the best answer):

Select one:

a. It is an
extremely shallow tree

b. The data structure can be transmitted between computers

c.
It saves space because no pointers are stored

d. It uses dynamic nodes

The
correct answer is: It saves space because no pointers are stored

Question
57

Which of the following items is NOT true for Array-Based Lists (please select the
best choice):

Choice 1. Insertion and deletion operations are ( n )

Choice 2. Direct
access of an item in the array is ( 1 )

Choice 3. Space used grows dynamically as the
array is populated

Choice 4. Array contains wasted space if array positions are not
full

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice
4

The correct answer is: Choice 3

Question 58

A linear index is
an index file organized as a sequence of key/pointer pairs where the keys are in a sorter
order.

Select one:

True

False

The correct answer is
'True'.

Question 59

For the following code fragment, select the option which
represents the most appropriate asymptotic analysis:

static int function ( n ) {

sum
= 0;

for (i=1; i<=n; i++)

sum += n;

return sum;

}

Option 1. Ω( n2
)

Option 2. Θ ( n )

Option 3. O( log n )

Option 4. O( 2n )

(NOTE: code
fragment is not intended to be functioning code)

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
2

Question 60

The lower bound for the growth of the Algorithms running time
is represented by (please the best answer):

1. Big Oh (O)

2. Big Omega (Ω)

3. Big
Theta (Θ)

4. Exponential growth

Select one:

a. Choice 1

b. Choice
2

c. Choice 3

d. Choice 4

The correct answer is: Choice
2

Question 61

A solution is said to be efficient if it:

Select
one:

a. Solves the problem within the required resource constraints

b. Executes
faster than other solutions

c. Is completed in the fewest number of steps

d. Can be
explained in the context of Big-Oh notation

The correct answer is: Solves the problem
within the required resource constraints

Question 62

In a stack which option
would access the 3rd element from the top of the stack S

Option 1. S.push(-1);

Option
2. S.dequeue(-3);

Option 3. S.pop();

S.pop();

S.pop();

Option 4.
S.pop(n-3);

Select one:

a. Option 1

b. Option 2

c. Option 3

d.
Option 4

The correct answer is: Option 3

Question 63

According to
textbook by Shaffer, a heap data structure has two properties which are:

Select one:

a. every node stores a value less than or equal to that of its children and it is a complete
binary tree

b. it is a min-heap and is partially ordered

c. it is a complete binary
tree and the values stored in it are partially ordered

d. it is a priority queue and is in
Θ( n )

The correct answer is: it is a complete binary tree and the values
stored in it are partially ordered

Question 64

The quicksort is typically
slower than the heapsort by a constant factor.

Select one:

True

False

The correct answer is 'False'.

Question 65

Which of the
following is NOT true for Linked Lists structures (please select the best choice):

Choice
1. Insertion and deletion are ( 1 ).

Choice 2. Direct access of an item in the list
structure is ( n ).

Choice 3. Space grows with number of elements.

Choice 4. There is
no overhead associated with elements in the list structure

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
4

Question 66

For the following code fragment, select the option that
represents the most appropriate asymptotic analysis:

for (int i = 0; i < a.length; i++)
{

System.out.println(a[i]);

}

Option 1. O( n )

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b.
Option 2

c. Option 3

d. Option 4

The correct answer is: Option
1

Question 67

Secondary storage is characterized by the
following:

Select one:

a. It is persistent

b. It is faster than primary
storage

c. It is volatile

d. It is more expensive than primary
storage

The correct answer is: It is persistent

Question 68

For
the following code fragment, select the option which represents the most appropriate asymptotic
analysis:

/** @return Position of largest value in "A“ */

static int
largest(int[] A) {

int currlarge = 0; // Position of largest

for (int i=1;
i<A.length; i++)

if (A[currlarge] < A[i])

currlarge = i; // Remember pos

return currlarge; // Return largest pos

}

Choice 1. Θ ( n )

Choice
2. O( 2n )

Choice 3. Θ( n log n )

Choice 4. Ω( n2 )

(NOTE: code fragment is
not intended to be functioning code)

Select one:

a. Choice 1

b. Choice
2

c. Choice 3

d. Choice 4

The correct answer is: Choice
1

Question 69

The upper bound for the growth of the Algorithms running time
is represented by (please select the best answer):

1. Big Oh (O)

2. Big Omega
(Ω)

3. Big Theta (Θ)

4. Exponential growth

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
1

Question 70

Data is stored within the disk drive on the: (select the best
answer)

Select one:

a. Spindle

b. Platter

c. Cylinder

d.
Sector

The correct answer is: Platter

Question 71

A sequential
tree can be represented using a bit vector?

Select one:

True

False

The correct answer is 'True'.

Question 72

For the following
code fragment, select the choice which represents the most appropriate asymptotic
analysis:

function ( n ) {

sum2 = 0;

for (k=1; k<=n; k*=2)

for (j=1;
j<=k; j++)

sum2++;

}

Choice 1. O( 2n )

Choice 2. Θ ( n
)

Choice 3. Θ( n log n )

Choice 4. Ω( n2 )

(NOTE: code fragment is not
intended to be functioning code)

Select one:

a. Choice 1

b. Choice
2

c. Choice 3

d. Choice 4

The correct answer is: Choice
2

Question 73

For the following code fragment, select the option that
represents the most appropriate asymptotic analysis:

if (a.length > 0) {

return
a[a.length - 1];

} else {

throw new NoSuchElementException();

}

Option 1.
O( 1 )

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option
4

Explanation: Here n = a.length, and T(n) = 1.

The correct answer is: Option
1

Question 74

Recursion is when an algorithm uses a series of loop
structures to repeat an operation until the answer has been computed.

Select one:

True

False

The correct answer is 'False'.

Question 75

The
process of associating a key with the location of a corresponding data record is called
folding.

Select one:

True

False

The correct answer is
'False'.

Question 76

An ADT is:

Select one:

a. A type together
with a collection of operations to manipulate the type

b. An implementation of a flyweight
design pattern

c. The realization of a data type as a software component

d. An
implementation in java of a class for a data type

The correct answer is: The
realization of a data type as a software component

Question 77

Enqueue and
Dequeue are notations associated with which data structur =Answer is: Queue

Question
78

For the following code fragment, select the choice which represents the most
appropriate asymptotic analysis:

function ( n ) {

sum1 = 0;

for (i=1; i<=n;
i++)

for (j=1; j<=n; j++)

sum1++;

}

Choice 1. Θ ( n2
)

Choice 2. O( 2n )

Choice 3. Θ( n log n )

Choice 4. Ω( log n2
)

(NOTE: code fragment is not intended to be functioning code)

Select
one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The
correct answer is: Choice 1

Question 79

Which of the following is not a
characteristic of an algorithm?

Select one:

a. It must be correct

b. It must be
composed of concrete steps

c. It can have no ambiguity

d. It must be composed of an
infinite number of steps.

The correct answer is: It must be composed of an infinite
number of steps.

Question 80

Setting the dirty bit causes what action to be
performed on a block: (select the best answer)

Select one:

a. It is deleted because
it is no longer consistent

b. It flushes or writes the block out to the disk

c.
Refreshes the data by re-reading the block

d. It cleans the cache by flushing all data
from the cache

The correct answer is: It flushes or writes the block out to the
disk

Question 81

A traversal that visits the left subtree, then the node,
and then the right subtree is called:

Select one:

a. Preorder Traversal

b. Postorder Traversal

c. Inorder Traversal

d. Outoforder Traversal

The
correct answer is: Inorder Traversal

Question 82

For the following code
fragment, select the choice which represents the most appropriate asymptotic analysis:

/**
@return The position of an element in sorted array A with value k. If k is not in A,return
A.length. */

static int binary(int[] A, int k) {

int l = -1; // Set l and r

int
r = A.length; // beyond array bounds

while (l+1 != r) { // Stop when l, r meet

int i
= (l+r)/2; // Check middle

if (k < A[i]) r = i; // In left half

if (k == A[i])
return i; // Found it

if (k > A[i]) l = i; // In right half

}

return
A.length; // Search value not in A

}

Choice 1. Θ ( n )

Choice 2. O( 2n
)

Choice 3. O( log n )

Choice 4. Ω( n2 )

(NOTE: code fragment is not intended to
be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice
3

d. Choice 4

The correct answer is: Choice 3

Question
83

In linked lists there are no NULL links in:

Select one:

a. Single
linked list

b. Linear doubly linked list

c. Circular linked list

d. None of
these

The correct answer is: Circular linked list

Question 84

The
process of determining if two objects are in the same set and then merging those sets is
called:

Select one:

a. a Union Operation

b. Union / Find

c. a Weighted
Union

a. It identifies
the maxkey value

b. It specifies the point where the array will be subdivided into
partitions and each partition then sorted

c. It defines the sequence for merging in the
sort

d. It indicates the index of the current record being compared

The correct
answer is: It specifies the point where the array will be subdivided into partitions and each
partition then sorted

Question 86

When big-Oh and coincide, we indicate
this by using (select the best answer):

1. Big Oh (O)

2. Big Omega (Ω)

3. Big
Theta (Θ)

4. Exponential growth

Select one:

A
traversal of a general tree that traverses the roots subtrees from left to right, then visits
the root is called a preorder traversal.

Select one:

True

False

The
correct answer is 'False'.

Question 88

Which of the following is NOT one of
the design patterns outlined in our text.

Select one:

a. Flyweight

b.
Visitor

c. Composite

d. Synergy

The correct answer is:
Synergy

Question 89

Push and Pop are notations associated with which data
structure:

Select one:

a. Queue

b. Stack

c. List

d.
Array

The correct answer is: Stack

Question 90

True/False: The
stack data structure is implemented as a LIFO structure (last in first out)

Select
one:

True

False

The correct answer is 'True'.

Question
91

An algorithm that breaks a file to be sorted in smaller files called runs which
are sorted and eventually put back together resulting in a sorted file is called:

Select
one:

a. Quicksort algorithm

b. Replacement sort algorithm

c. An indexed key
sort algorithm

d. Mergesort algorithm

The correct answer is: Mergesort
algorithm

Question 92

The process of storing blocks of data in main memory
after reading from disk is referred to as:

Select one:

a. Buffering

b.
Hashing

c. Pooling

d. Indexing

The correct answer is:
Buffering

Question 93

For the following cod �8�U
�8�U$�
�U�:�
�U��8�U@�8�U@@�8�Un; i++) {

//

// Search in array
a for smallest element starting at i to n-1

//

minIndex = findSmallestElement(a, i,
n-1)

a[i] = a[minIndex];

}

findSmallestElement( int a[], int i, int n ) {

int largest = a[i];

while(i<n) {

if(a[i] >a[largest])

largest = i;

i++;

}

return(largest);

}

Option 1. O( n )

Option 2. O( 2n
)

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b.
Option 2

c. Option 3

d. Option 4

index-of-smallest element in a[i..j]
takes j-i+1 operations

• n + (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1

• this
is n2

The correct answer is: Option 4

Question 94

The depth of node H
in the following tree is:

Select one:

a. 3

b. 2

c. 4

d.
1

The correct answer is: 3

Question 95

The implementation of a
data type as a data structure is the physical form of an ADT.

Select one:

True

False

The correct answer is 'True'.

Question 96

A method that is
designed to create extremely shallow trees is called:

Select one:

a. Dynamic node
implementation

b. Union/Find

c. The list of children method

d. Path
compression

The correct answer is: Path compression

Question
97

True/False: Big Theta (Θ) indicates that the Upper and Lower bounds of an
algorithm are the same.

Select one:

True

False

The correct answer is
'True'.

Question 98

According to the properties of logarithms, log(nm)
=

Note: Due to issues with HTML formatting, an exponent is represented by preceding it with
the ^ symbol. As such x^2 is equivalent to x2.

Select one:

a. log n – log
m

b. n log n

c. log n + log m

d. log(n^m)

The correct answer is:
log n + log m

Question 99

For the following code fragment, select the choice
which represents the most appropriate asymptotic analysis:

static int function ( n )
{

for (k=0; k<n; k++)

A[k] = k;

return A[k];

}

Choice 1. O ( n2
)

Choice 2. O( 2n )

Choice 3. Ω( n2 )

Choice 4. Θ ( n )

(NOTE: code
fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
4

Question 100

The full binary tree theorem states “the number of
leaves in an empty full binary tree is one more than the number of internal
nodes”

Select one:

True

False

The correct answer is
'False'.

Question 101

A significant benefit to using an index to hold and
sort keys to a file is:

Select one:

a. Smaller keys require less I/O

b. The
entire sort can always be completed in memory

c. The head of the disk drive does not need
to move

d. There is no seek time added to the latency of I/O operations

The
correct answer is: Smaller keys require less I/O

Question 102

For the
following code fragment, select the choice which represents the most appropriate asymptotic
analysis:

function ( n ) {

sum2 = 0;

for (i=1; i<=n; i++)

for (j=1;
j<=i; j++)

sum2++;

}

}

Choice 1. Ω ( 1 )

Choice 2. O( 2n
)

Choice 3. Θ( n2 )

Choice 4. Ω( n2 )

(NOTE: code fragment is not intended
to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c.
Choice 3

d. Choice 4

The correct answer is: Choice 3

Question
103

The best asymptotic analysis for the selection sort is represented by (select the
best option):

Option 1. O( n log n )

Option 2. Ω( n2 )

Option 3. O( n2
)

Option 4. Θ( n2 )

Select one:

a. Option 1

b. Option 2

c.
Option 3

d. Option 4

The correct answer is: Option 4

Question
104

For the following code fragment, select the option that represents the most
appropriate asymptotic analysis:

public static int binarySearch(int[] a, int key) {

int left = 0;

int right = a.length-1;

while (left <= right) {

int mid =
left + (right-left)/2;

if (key < a[mid]) right = mid-1;

else if (key > a[mid])
left = mid+1;

else return mid;

}

//not found

return
-1;

}

Option 1. Ω( 1 ), O( log n )

Option 2. Ω( n ), O( 2n )

Option 3.
Θ( n log n )

Option 4. Θ( log n )

Select one:

a. Option 1

b.
Option 2

c. Option 3

d. Option 4

The correct answer is: Option
1

Question 105

For the following code fragment, select the choice which
represents the most appropriate asymptotic analysis:

static int function ( n ) {

sum
= 0;

for (i=1; i<=n; i++)

sum += n;

return sum;

}

Choice 1. Ω( n2
)

Choice 2. Θ ( n2 )

Choice 3. O( log n )

Choice 4. O( n )

(NOTE: code
fragment is not intended to be functioning code)

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
4

Question 106

Inserting or removing an item at position n-1 within a linked
list has the same cost in terms ( n ) time as the same operation in an array based
implementation of a list.

Select one:

True

False

The correct answer
is 'False'.

A solution is said to be efficient if it:

Select one:

a. Solves the
problem within the required resource constraints

b. Executes faster than other
solutions

c. Is completed in the fewest number of steps

d. Can be explained in the
context of Big-Oh notation

The correct answer is: Solves the problem within the
required resource constraints

Question 2

An ADT is:

Select one:

a. A type together with a collection of operations to manipulate the type

b. An
implementation of a flyweight design pattern

c. The realization of a data type as a
software component

d. An implementation in java of a class for a data type

The
correct answer is: The realization of a data type as a software component

Question
3

The implementation of a data type as a data structure is the physical form of an
ADT.

Select one:

True

False

The correct answer is
'True'.

Question 4

Which of the following is NOT one of the design patterns
outlined in our text.

Select one:

a. Flyweight

b. Visitor

c.
Composite

d. Synergy

The correct answer is: Synergy

Question
5

If A={1, 2, 3, 4} and B={4, 5, 6}, find A∪ B .

Select one:

a.
{1,2,3,4,4,5,6}

b. {4}

c. {x | x is all positive integers}

d.
{1,2,3,4,5,6}

The correct answer is: {1,2,3,4,5,6}

Question
6

According to the properties of logarithms, log(nm) =

Note: Due to issues with
HTML formatting, an exponent is represented by preceding it with the ^ symbol. As such x^2 is
equivalent to x2.

Select one:

a. log n – log m

b. n log n

c. log n
+ log m

d. log(n^m)

The correct answer is: log n + log m

Question
7

Recursion is when an algorithm uses a series of loop structures to repeat an
operation until the answer has been computed.

Select one:

True

False

The correct answer is 'False'.

Question 8

Which of the following
is not a mathematical proof technique?

Select one:

a. Proof by mathematical
induction

b. Proof by contradiction

c. Direct proof

d. Proof by consensus

The correct answer is: Proof by consensus

Question 9

Which of
the following is not a characteristic of an algorithm?

Select one:

a. It must be
correct

b. It must be composed of concrete steps

c. It can have no ambiguity

d. It must be composed of an infinite number of steps.

The correct answer is: It
must be composed of an infinite number of steps

The upper bound for the growth of the
Algorithms running time is represented by:

Select one:

a. Big Oh (O)

b. Big
Omega (Ω)

c. Big Theta (Θ)

d. Exponential growth

The correct answer
is: Big Oh (O)

Question 2

Asymptotic Algorithm Analysis is primarily
concerned with:

Select one:

a. The size of the constant in the algorithm running time
equation

b. The speed of the computing running the algorithm

c. The speed of the
compiler

d. The growth rate demonstrated in the algorithm running time equation

The correct answer is: The growth rate demonstrated in the algorithm running time
equation

Question 3

True/False: Big Theta (Θ) indicates that the Upper
and Lower bounds of an algorithm are the same.

Select one:

True

False

The correct answer is 'True'.

Question 4

For the following
code fragment, select the option that represents the most appropriate asymptotic
analysis:

for (int i = 0; i < a.length; i++) {

System.out.println(a[i]);

}

Option 1. O( n )

Option 2. O( 2n )

Option 3.
O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The correct answer is: Option 1

Question
5

For the following code fragment, select the option that represents the most
appropriate asymptotic analysis:

for (int i = 1; i <= n; i *= 2) {

for (int j =
0; j < n; j++) {

count++;

}

}

Option 1. O( 1 )

Option 2. O( 2n
)

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b.
Option 2

c. Option 3

d. Option 4 =!PT(n) = n log n. (Note that the default base for
logarithms in Computer Science is 2.)

The correct answer is: Option 3

Question
6

For the following code fragment, select the option that represents the most
appropriate asymptotic analysis:

if (a.length > 0) {

return a[a.length -
1];

} else {

throw new NoSuchElementException();

}

Option 1. O( 1
)

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option
4

Explanation: Here n = a.length, and T(n) = 1.

The correct answer is: Option
1

Question 7

For the following code fragment, select the most appropriate
asymptotic analysis:

// Towers of Hanoi

static void solveHanoi(int disks, char
fromPole, char toPole, char withPole) {

if (disks >= 1) {

solveHanoi(disks-1,
fromPole, withPole, toPole);

moveDisk(fromPole, toPole);

solveHanoi(disks-1,
withPole, toPole, fromPole);

}

}

static void moveDisk(char fromPole, char
toPole) {

moves++;

}

Option 1. O( n )

Option 2. O( 2n )

Option 3. O( n
log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c.
Option 3

d. Option 4

The correct answer is: Option 2

Question
8

For the following code fragment, select the option that represents the most
appropriate asymptotic analysis:

public static int binarySearch(int[] a, int key) {

int left = 0;

int right = a.length-1;

while (left <= right) {

int mid =
left + (right-left)/2;

if (key < a[mid]) right = mid-1;

else if (key > a[mid])
left = mid+1;

else return mid;

}

//not found

return
-1;

}

Option 1. Ω( 1 ), O( log n )

Option 2. Ω( n ), O( 2n )

Option 3.
Θ( n log n )

Option 4. Θ( log n )

Select one:

a. Option 1

b.
Option 2

c. Option 3

d. Option 4

The correct answer is: Option
1

Question 9

For the following code fragment, select option that represents
the most appropriate asymptotic analysis:

for (i=0; i<n; i++) {

//

// Search
in array a for smallest element starting at i to n-1

//

minIndex =
findSmallestElement(a, i, n-1)

a[i] = a[minIndex];

}

findSmallestElement( int
a[], int i, int n ) {

int largest = a[i];

while(i<n) {

if(a[i]
>a[largest])

largest = i;

i++;

}

return(largest);

}

Option
1. O( n )

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

index-of-smallest element in a[i..j] takes j-i+1 operations

• n + (n-1) +
(n-2) + (n-3) + ... + 3 + 2 + 1

• this is n2

The correct answer is: Option
4

Question 10

For the following code fragment, select the option that
represents the most appropriate asymptotic analysis:1; // Base case

return fibr(n-1) +
fibr(n-2); // Recursive call

}

Option 1. O( n )

Option 2. O( 2n )

Option 3.
O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The correct answer is: Option 2

Top of Form

A
list is

Select one:

a. An ADT for storing and retrieving data

b. A tree data
structure

c. Finite ordered sequence of data items

d. A collection of operations to
implement an ADT

The correct answer is: Finite ordered sequence of data
items

Question 2

A list is said to be empty when all of its elements have a
zero (0) value

Select one:

True

False

The corr@8sed list
implementation is:

Select one:

a. Inserting a new element at position n-1 in the list
where n is the number of elements in the list.

b. Inserting a new element into the head of
the list.

c. Removing an element at position n-1 within the list

d. Removing an
element from the tail of the list.

The correct answer is: Inserting a new element
into the head of the list.

Question 4

A linked list implementation relies
upon static memory allocation where static refers to the requirement to pre-allocate all of the
memory that will be used for the list.

Select one:

True

False

The
correct answer is 'False'.

Question 5

A linked list creates order through
the use of pointers that link one element to another.

Select one:

True

False

The correct answer is 'True'.

Question 6

Inserting or
removing an item at position n-1 within a linked list has the same cost in terms ( n ) time as
the same operation in an array based implementation of a list.

Select one:

True

False

The correct answer is 'False'.

Question 7

The freelist
…

Select one:

a. Provides access to memory within the operating system that
has not yet been allocated

b. Provides access to memory objects which have no Big O ( n )
time.

c. Facilitates and encourages the use of the new operator.

d. Holds the list
nodes that are no longer in use.

The correct answer is: Holds the list nodes that
are no longer in use.

Question 8

In a queue, placing new items in the queue
is referred to as a push and taking an item out of the queue is called a pop.

Select
one:

True

False

The correct answer is 'False'.

Question
9

In linked lists there are no NULL links �8�U �8�U$�
�U�:�
�U��8�U@�8�U@@�8�Ulinked list

d. None of
these

The correct answer is: Circular linked list

Question 10

In
a stack which option would access the 3rd element from the top of the stack S

Option 1.
S.push(-1);

Option 2. S.dequeue(-3);

Option 3. S.pop();

S.pop();

S.pop();

Option 4. S.pop(n-3);

Select one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The correct answer is: Option 3

Bottom of
Form

A leaf is any node that:

Select one:

a. Has one child

b. Is an
internal node with no ancestors

c. Is any node with two empty children

d. Is the
ancestor of the root node

The correct answer is: Is any node with two empty
children

Question 2

The full binary tree theorem states “the number of
leaves in an empty full binary tree is one more than the number of internal
nodes”

Select one:

True

False

The correct answer is
'False'.

Question 3

The process for visiting all of the nodes of a binary
tree in some order is called a traversal.

Select one:

True

False

The correct answer is 'True'.

Question 4

A full binary tree
has a restricted shape which starts at the root and fills the tree by levels from left to
right.

Select one:

True

False

The correct answer is
'False'.

Question 5

A binary tree traversal that lists every node in the
tree exactly once is called:

Select one:

a. a Traversal

b. A visitor design
pattern

c. An enumeration

d. Natural ordering sequence

The correct
answer is: An enumeration

Question 6

A preorder traversal visits every node
starting at the leaf nodes and working up the tree.

Select one:

True

False

The correct answer is 'False'.

Question 7

Correctly identify the
following heap structure by selecting the best answer:

Select one:

a.
partially ordered heap

b. max-heap structure

c. priority heap

d. min-heap
structure

The correct answer is: max-heap structure

Question
8

Select the answer that best defines Huffman Coding:

Select one:

a. A set
of coding rules that is typically used for compression

b. A fixed length coding scheme for
character representation

c. A tree structure that trades off space and time requirements
to provide a more efficient priority queue

d. An approach of assigning codes to characters
such that the frequency length of the code depends upon the relative frequency of the
corresponding character in use

The correct answer is: An approach of assigning codes
to characters such that the frequency length of the code depends upon the relative frequency of
the corresponding character in use

Question 9

The depth of node H in the
following tree is:

Select one:

a. 3

b. 2

c. 4

d.
1

The correct answer is: 3

Question 10

According to textbook by
Shaffer, a heap data structure has two properties which are:

Select one:

a. every
node stores a value less than or equal to that of its children and it is a complete binary
tree

b. it is a min-heap and is partially ordered

c. it is a complete binary tree
and the values stored in it are partially ordered

d. it is a priority queue and is in
Θ( n )

The correct answer is: it is a complete binary tree and the values
stored in it are partially ordered

Top of Form

A finite set of one or more nodes such
that there is one designated node call the root is a: (select the best answer)

Select
one:

a. Parent root

b. a B+ tree data structure

c. Index

d. Tree

The correct answer is: Tree

Question 2

A collection of one or
more trees is called:

Select one:

a. Trees

b. Multiple Spanning Trees

c.
a Forest

d. Traversals

The correct answer is: a Forest

Question
3

The process of determining if two objects are in the same set and then merging
those sets is called:

Select one:

a. a Union Operation

b. Union / Find

c. a Weighted Union

d. a Merge Operation

The correct answer is: Union /
Find

Question 4

A traversal of a general tree that traverses the roots
subtrees from left to right, then visits the root is called a preorder traversal.

Select
one:

True

False

The correct answer is 'False'.

Question
5

A method that is designed to create extremely shallow trees is called:

Select
one:

a. Dynamic node implementation

b. Union/Find

c. The list of children
method

d. Path compression

The correct answer is: Path
compression

Question 6

A tree whose internal nodes all have exactly K
children is called a K-ary tree.

Select one:

True

False

The correct
answer is 'True'.

Question 7

An important advantage of the sequential tree
implementation is that (select the best answer):

Select one:

a. It is an extremely
shallow tree

b. The data structure can be transmitted between computers

c. It saves
space because no pointers are stored

d. It uses dynamic nodes

The correct
answer is: It saves space because no pointers are stored

Question 8

A
sequential tree can be represented using a bit vector?

Select one:

True

False

The correct answer is 'True'.

Question 9

The list of
children approach uses both pointers and an array structure to represent the tree.

Select
one:

True

False

The correct answer is 'True'.

Question
10

The weighted union rule joins a tree with fewer nodes to a tree with more nodes by
making the smaller tree’s root point to the root of the larger tree.

Select
one:

True

False

The correct answer is 'True'.

Bottom of
Form

Top of Form

The best asymptotic analysis for the selection sort is represented by
(select the best option):

Option 1. O( n log n )

Option 2. Ω( n2 )

Option 3. O(
n2 )

Option 4. Θ( n2 )

Select one:

a. Option 1

b. Option 2

c.
Option 3

d. Option 4

The correct answer is: Option 4

Question
2

A sort algorithm that uses two nested loops with the inner loop moving through the
array from bottom to top is called the:

Select one:

a. Insertion sort

b. Bubble
sort

c. Inversion sort

d. Selection sort

The correct answer is: Bubble
sort

Question 3

A sort that features a limit of n-1 of record swaps is
called:

Select one:

a. Insertion sort

b. Bubble sort

c. Inversion
sort

d. Selection sort

The correct answer is: Selection sort

Question
4

An exchange sort is one where: (select the best answer)

Select one:

a.
Records in an unsorted list are moved to a sorted list

b. Adjacent records in the list and
compared and exchanged

c. An inversion is executed

d. The sorting algorithm is said
to be stable

The correct answer is: Adjacent records in the list and compared and
exchanged

Question 5

A sort where the list is divided into halves, the
halves sorted and these two halves are merged is called:

Select one:

a. Mergesort

b. Binary sort

c. Quicksort

d. Heapsort

The correct answer is:
Mergesort

Question 6

The benefit of a quicksort is that it provides
excellent performance in both the average and worst case:

Select one:

True

False

The correct answer is 'False'.

Question 7

What is the role
of the pivot in a quicksort algorithm?

Select one:

a. It identifies the maxkey
value

b. It specifies the point where the array will be subdivided into partitions and
each partition then sorted

c. It defines the sequence for merging in the sort

d. It
indicates the index of the current record being compared

The correct answer is: It
specifies the point where the array will be subdivided into partitions and each partition then
sorted

Question 8

A sorting algorithm that assigns records to bins and then
relies on some other sorting technique to sort the records within each bin called:

Select
one:

a. Radix Sort

b. Quicksort

c. Hash sort

d. Bucket sort

The correct answer is: Bucket sort

Question 9

The processing
time or cost of a sort is defined by the number of comparisons and exchanges that must be made
during processing. What is the average cost of the heapsort?:

Option 1. O( n log n
)

Option 2. Ω( n2 )

Option 3. O( n2 )

Option 4. Θ( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The
correct answer is: Option 1

Question 10

The quicksort is typically slower
than the heapsort by a constant factor.

Select one:

True

False

The
correct answer is 'False'.

Bottom of Form

Setting the dirty bit causes what action to
be performed on a block: (select the best answer)

Select one:

a. It is deleted
because it is no longer consistent

b. It flushes or writes the block out to the
disk

c. Refreshes the data by re-reading the block

d. It cleans the cache by
flushing all data from the cache

=each of the following is NOT one of the buffer
pool heuristics defined in the text : (select the best answer)

Select one:

a.
FIFO

b. LIFO

c. LRU

d. LFU

The correct answer is:
LIFO

Question 3

A technique that allows a programmer to use more main memory
than exists in the computer is called: (select the best answer)

Select one:

a. Buffer
cache

b. Random access memory

c. Secondary storage

d. Virtual memory

The correct answer is: Virtual memory

Question 4

Internal
Fragmentation refers to: (select the best answer)

Select one:

a. Space that is left
empty because records do not fit evenly into a sector

b. Space allocated to a file that is
not physically adjacent on the disk drive

c. Space that is left empty because records do
not fit evenly into a sector or Space allocated to a file that is not physically adjacent

d. None of the options

The correct answer is: Space that is left empty because
records do not fit evenly into a sector or Space allocated to a file that is not physically
adjacent

Question 5

Data is stored within the disk drive on the: (select the
best answer)

Select one:

a. Spindle

b. Platter

c. Cylinder

d.
Sector

The correct answer is: Platter

Question 6

The process of
storing blocks of data in main memory after reading from disk is referred to as:

Select
one:

a. Buffering

b. Hashing

c. Pooling

d. Indexing

The
correct answer is: Buffering

Question 7

A characteristic of RAM (random
access memory) is that it is persistent and is not lost when the power to a computer is turned
off.

Select one:

True

False

The correct answer is
'False'.

Question 8

Secondary storage is characterized by the
following:

Select one:

a. It is persistent

b. It is faster than primary
storage

c. It is volatile

d. It is more expensive than primary
storage

The correct answer is: It is persistent

Question 9

An
algorithm that breaks a file to be sorted in smaller files called runs which are sorted and
eventually put back together resulting in a sorted file is called:

Select one:

a.
Quicksort algorithm

b. Replacement sort algorithm

c. An indexed key sort algorithm

d. Mergesort algorithm

The correct answer is: Mergesort
algorithm

Question 10

A significant benefit to using an index to hold and
sort keys to a file is:

Select one:

a. Smaller keys require less I/O

b. The
entire sort can always be completed in memory

c. The head of the disk drive does not need
to move

d. There is no seek time added to the latency of I/O operations

The
correct answer is: Smaller keys require less I/O

Top of Form

Which of the following is
not one of the general approaches to search algorithms:

Select one:

a. Buffer cache
accespct indexing methods

The correct answer is: Buffer cache access
methods

Question 2

A list that organizes the order of records within the
list based upon patterns of actual record access is called a/an (select the best
answer):

Select one:

a. Quadratic Binary search order

b. A Zipf
Distribution

c. A Self-organizing list

d. A range query

The correct
answer is: A Self-organizing list

Question 3

A compound computed search that
combines a binary search to get close to the required record and then uses sequential search to
find the item is referred to as a/an:

Select one:

a. Zipf search

b. An Exact
match search

c. A Dictionary search

d. bit map vector search

The correct
answer is: A Dictionary search
<@8ion in the file of the first occurrence of the string is called Ziv-Lempel coding.

Select one:

True

False

The correct answer is 'True'.

Question
5

The process of storing records in the order that they were added to a file is
called:

Select one:

a. Entry-sequenced file

b. Binary Sequenced file

c.
LIFO file format

d. Tombstone approach

The correct answer is: Entry-sequenced
file

Question 6

The process of associating a key with the location of a
corresponding data record is called folding.

Select one:

True

False

The correct answer is 'False'.

Question 7

Each record of a
database normally has a unique identifier called the:

Select one:

a. Secondary
Key

b. Primary index

c. Primary key

d. Index key

The correct
answer is: Primary key

Question 8

A linear index is an index file organized
as a sequence of key/pointer pairs where the keys are in a sorter order.

Select one:

True

False

The correct answer is 'True'.

Question 9

A tree
data structure whose shape obeys the following definition,

o A node contains one or two
keys

o Every internal node has either 2 children if it contains 1 key or 3 children if it
contains two keys

o All leaves are at the same level in the tree

Is called
a/an:

Select one:

a. B*-Tree

b. BST

c. B+-Tree

d. 2-3 tree

The correct answer is: 2-3 tree

Question 10

The most significant
difference between the B+-Tree and the BST is that the B+-Tree stores records only at the leaf
nodes.

Select one:

True

False

The correct answer is
'True'.

Bottom of Form

A traversal that visits the left subtree, then the node, and
then the right subtree is called:

Select one:

a. Preorder Traversal

b.
Postorder Traversal

c. Inorder Traversal

d. Outoforder Traversal

The
correct answer is: Inorder Traversal

Question 2

Each record of a database
normally has a unique identifier called the:

Se �8�U �8�U$�
�U�:�
�U��8�U@�8�U@@�8�U />The correct answer is: Primary
key

Question 3

An ADT is:

Select one:

a. A type together with a
collection of operations to manipulate the type

b. An implementation of a flyweight design
pattern

c. The realization of a data type as a software component

d. An
implementation in java of a class for a data type

The correct answer is: The
realization of a data type as a software component

Question 4

A linked list
creates order through the use of pointers that link one element to another.

Select
one:

True

False

The correct answer is 'True'.

Question
5

The most significant difference between the B+-Tree and the BST is that the B+-Tree
stores records only at the leaf nodes.

Select one:

True

False

The
correct answer is 'True'.

Question 6

A sequential tree can be represented
using a bit vector?

Select one:

True

False

The correct answer is
'True'.

Question 7

In linked lists there are no NULL links in:

Select
one:

a. Single linked list

b. Linear doubly linked list

c. Circular linked
list

d. None of these

The correct answer is: Circular linked
list

Question 8

Recursion is when an algorithm uses a series of loop
structures to repeat an operation until the answer has been computed.

Select one:

True

False

The correct answer is 'False'.

Question 9

A
linked list implementation relies upon static memory allocation where static refers to the
requirement to pre-allocate all of the memory that will be used for the list.

Select
one:

True

False

The correct answer is 'False'.

Question
10

The process of storing records in the order that they were added to a file is
called:

Select one:

a. Entry-sequenced file

b. Binary Sequenced file

c.
LIFO file format

d. Tombstone approach

The correct answer is: Entry-sequenced
file

Question 11

For the following code fragment, select the choice which
represents the most appropriate asymptotic analysis:

static int function ( n ) {

for
(k=0; k<n; k++)

A[k] = k;

return A[k];

}

Choice 1. O ( n2 )

Choice
2. O( 2n )

Choice 3. Ω( n2 )

Choice 4. Θ ( n )

(NOTE: code fragment is not
intended to be functioning code)

Select one:

a. Choice 1

b. Choice
2

c. Choice 3

d. Choice 4

The correct answer is: Choice
4

Question 12

For the following code fragment, select the option that
represents the most appropriate asymptotic analysis:

for (int i = 0; i < a.length; i++)
{

System.out.println(a[i]);

}

Option 1. O( n )

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b.
Option 2

c. Option 3

d. Option 4

The correct answer is: Option
1

Question 13

Inserting or removing an item at position n-1 within a linked
list has the same cost in terms ( n ) time as the same operation in an array based
implementation of a list.

Select one:

True

False

The correct answer
is 'False'.

Question 14

Which of the following is NOT one of the buffer pool
heuristics defined in the text : (select the best answer)

Select one:

a. FIFO

b. LIFO

c. LRU

d. LFU

The correct answer is: LIFO

Question
15

For the following code fragment, select the option that represents the most
appropriate asymptotic analysis:

for (int i = 1; i <= n; i *= 2) {

for (int j =
0; j < n; j++) {

count++;

}

}

Option 1. O( 1 )

Option 2. O( 2n
)

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b.
Option 2

c. Option 3

d. Option 4

Explanation: Here the outer loop is done
log n times and the inner loop is done n times, so T(n) = n log n. (Note that the default base
for logarithms in Computer Science is 2.)

The correct answer is: Option 3

Question
16

The full binary tree theorem states “the number of leaves in an empty full
binary tree is one more than the number of internal nodes”

Select one:

True

False

The correct answer is 'False'.

Question 17

The
processing time or cost of a sort is defined by the number of comparisons and exchanges that
must be made during processing. What is the average cost of the heapsort?:

Option 1. O( n
log n )

Option 2. Ω( n2 )

Option 3. O( n2 )

Option 4. Θ( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The
correct answer is: Option 1

Question 18

When big-Oh and coincide, we
indicate this by using (select the best answer):

1. Big Oh (O)

2. Big Omega
(Ω)

3. Big Theta (Θ)

4. Exponential growth

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 19

A list is said to be empty when all of its elements have a
zero (0) value

Select one:

True

False

The correct answer is
'False'.

Question 20

True/False: Big Theta (Θ) indicates that the
Upper and Lower bounds of an algorithm are the same.

Select one:

True

False

The correct answer is 'True'.

Question 21

A traversal of a
general tree that traverses the roots subtrees from left to right, then visits the root is
called a preorder traversal.

Select one:

True

False

The correct
answer is 'False'.

Question 22

Enqueue and Dequeue are notations associated
with which data structure:

Select one:

a. Queue

b. Stack

c. List

d.
Array

The correct answer is: Queue

Question 23

A significant
benefit to using an index to hold and sort keys to a file is:

Select one:

a. Smaller
keys require less I/O

b. The entire sort can always be completed in memory

c. The
head of the disk drive does not need to move

d. There is no seek time added to the latency
of I/O operations

The correct answer is: Smaller keys require less
I/O

Question 24

A tree whose internal nodes all have exactly K children is
called a K-ary tree.

Select one:

True

False

The correct answer is
'True'.

Question 25

Which of the following is not a characteristic of an
algorithm?

Select one:

a. It must be correct

b. It must be composed of concrete
steps

c. It can have no ambiguity

d. It must be composed of an infinite number of
steps.

The correct answer is: It must be composed of an infinite number of
steps.

Question 26

For the following code fragment, select the most
appropriate asymptotic analysis:

// Towers of Hanoi

static void solveHanoi(int disks,
char fromPole, char toPole, char withPole) {

if (disks >= 1) {

solveHanoi(disks-1, fromPole, withPole, toPole);

moveDisk(fromPole, toPole);

solveHanoi(disks-1, withPole, toPole, fromPole);

}

}

static void moveDisk(char
fromPole, char toPole) {

moves++;

}

Option 1. O( n )

Option 2. O( 2n
)

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The correct answer is: Option
2

Question 27

For the following code fragment, select the option which
represents the most appropriate asymptotic analysis:

static int function ( n ) {

sum
= 0;

for (i=1; i<=n; i++)

sum += n;

return sum;

}

Option 1. Ω( n2
)

Option 2. Θ ( n )

Option 3. O( log n )

Option 4. O( 2n )

(NOTE: code
fragment is not intended to be functioning code)

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
2

Question 28

True/False: There is always one most efficient algorithm to
solve a particular problem.

Select one:

True

False

The correct
answer is 'False'.

Question 29

A technique that allows a programmer to use
more main memory than exists in the computer is called: (select the best answer)

Select
one:

a. Buffer cache

b. Random access memory

c. Secondary storage

d.
Virtual memory

The correct answer is: Virtual memory

Question
30

A sort that features a limit of n-1 of record swaps is called:

Select
one:

a. Insertion sort

b. Bubble sort

c. Inversion sort

d. Selection
sort

The correct answer is: Selection sort

Question 31

A
traversal that visits each node before visiting its children is called:

Select one:

a. Preorder traversal

b. Postorder traversal

c. Inorder Traversal

d.
Outoforder Traversal

The correct answer is: Preorder traversal

Question
32

A list tha =!P�U =an (select the best answer):

Select one:

a.
Quadratic Binary search order

b. A Zipf Distribution

c. A Self-organizing list

d. A range query

The correct answer is: A Self-organizing list

Question
33

True/False: The stack data structure is implemented as a LIFO structure (last in
first out)

Select one:

True

False

The correct answer is
'True'.

Question 34

The process of determining if two objects are in the
same set and then merging those sets is called:

Select one:

a. a Union
Operation

b. Union / Find

c. a Weighted Union

d. a Merge
Operation

The correct answer is: Union / Find

Question 35

A sort
algorithm that uses two nested loops with the inner loop moving through the array from bottom to
top is called the:

Select one:

a. Insertion sort

b. Bubble sort

c.
Inversion sort

d. Selection sort

The correct answer is: Bubble
sort

Question 36

Which of the following is NOT one of the design patterns
outlined in our text.

Select one:

a. Flyweight

b. Visitor

c.
Composite

d. Synergy

The correct answer is: Synergy

Question
37

Push and Pop are notations associated with which data structure:

Select
one:

a. Queue

b. Stack

c. List

d. Array

The correct answer
is: Stack

Question 38

The process of associating a key with the location of
a corresponding data record is called folding.

Select one:

True

False

The correct answer is 'False'.

Question 39

For the
following code fragment, select the option that represents the most appropriate asymptotic
analysis:

// Recursive Fibonacci generator

static long fibr(int n) {

if ((n ==
1) || (n == 2)) return 1; // Base case

return fibr(n-1) + fibr(n-2); // Recursive
call

}

Option 1. O( n )

Option 2. O( 2n )

Option 3. O( n log n
)

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c. Option
3

d. Option 4

The correct answer is: Option 2

Question
40

For the following code fragment, select the choice which represents the most
appropriate asymptotic analysis:

static int function ( n ) {

for (k=0; k<n;
k++)

A[k] = k;

return A[k];

}

Choice 1. Θ ( n log n )

Choice 2.
O( 2n )

Choice 3. O( n )

Choice 4. Ω( n2 )

(NOTE: code fragment is not intended
to be functioning code)

Select one:

a. Choice 1

b. Choice
2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 41

Which of the following is not one of the general approaches to
search algorithms:

Select one:

a. Buffer cache access methods

b. Sequential and
list methods

c. Direct access by key value (hashing)

d. Tree indexing
methods

ins a tree with fewer nodes to a tree with more nodes by making the smaller
tree’s root point to the root of the larger tree.

Select one:

True

False

The correct answer is 'True'.

Question 43

The list of
children approach uses both pointers and an array structure to represent the tree.

Select
one:

True

False

The correct answer is 'True'.

Question
44

The depth of node H in the following tree is:

Select one:

a.
3

b. 2

c. 4

d. 1

The correct answer is: 3

Question
45

Data is stored within the disk drive on the: (select the best answer)

Select
one:

a. Spindle

b. Platter

c. Cylinder

d. Sector

The correct
answer is: Platter

Question 46

The most time consuming @8at position n-1 in
the list where n is the number of elements in the list.

b. Inserting a new element into
the head of the list.

c. Removing an element at position n-1 within the list

d.
Removing an element from the tail of the list.

The correct answer is: Inserting a new
element into the head of the list.

Question 47

If A={1, 2, 3, 4} and B={4,
5, 6}, find A∪ B .

Select one:

a. {1,2,3,4,4,5,6}

b. {4}

c. {x | x is
all positive integers}

d. {1,2,3,4,5,6}

The correct answer is:
{1,2,3,4,5,6}

Question 48

For the following code fragment, select the option
which represents the most appropriate asymptotic analysis:

/** @return Position of largest
value in "A“ */

static int largest(int[] A) {

int currlarge = 0; // Position of
largest

for (int i=1; i<A.length; i++)

if (A[currlarge] < A[i])

currlarge = i; // Remember pos

return currlarge; // Return largest pos

}

Choice 1. Θ ( n )

Choice 2. O( 2n )

Choice 3. Θ( n log n
)

Choice 4. Ω( n2 )

(NOTE: code fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice
4

The correct answer is: Choice 1

Question 49

For the following
code fragment, select the choice which represents the most appropriate asymptotic
analysis:

function ( n ) {

sum1 = 0;

for (k=1; k<=n; k*=2)

for (j=1;
j<=n; j++)

sum1++;

}

Choice 1. Θ ( n )

Choice 2. O( 2n
)

Choice 3. Θ( n log n )

Choice 4. Ω( n2 )

(NOTE: code fragment is not
intended to be functioning code)

Select one:

a. Choice 1

b. Choice
2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 50

The implementation of a data type as a data structure is the
physical form of an ADT.

Select one:

True

False

The correct answer
is 'True'.

Question 51

An exchange sort is one where: (select the best
answer)

Select one:

a. Records in an unsorted list are moved to a sorted list

b. Adjacent records in the list and compared and exchanged

c. An inversion is
executed

d. The sorting algorithm is said to be stable

The correct answer is:
Adjacent records in the list and compared and exchanged

Question 52

For the
�8�U �8�U$�
�U�:�
�U��8�U@�8�U@@�8�Ur />static int function ( n ) {

sum =
0;

for (j=1; j<=n; j++)

for (i=1; i<=j; i++)

sum++;

return
sum;

}

Choice 1. Θ ( n )

Choice 2. O( 2n )

Choice 3. Θ( n2
)

Choice 4. Ω( n2 )

(NOTE: code fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice
4

The correct answer is: Choice 3

Question 53

An important
advantage of the sequential tree implementation is that (select the best answer):

Select
one:

a. It is an extremely shallow tree

b. The data structure can be transmitted
between computers

c. It saves space because no pointers are stored

d. It uses
dynamic nodes

The correct answer is: It saves space because no pointers are
stored

Question 54

For the following code fragment, select the choice which
represents the most appropriate asymptotic analysis:

function ( n ) {

sum1 = 0;

for (i=1; i<=n; i++)

for (j=1; j<=n; j++)

sum1++;

}

Choice 1.
Θ ( n2 )

Choice 2. O( 2n )

Choice 3. Θ( n log n )

Choice 4. Ω( log n2
)

(NOTE: code fragment is not intended to be functioning code)

Select
one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The
correct answer is: Choice 1

Question 55

A sort where the list is divided
into halves, the halves sorted and these two halves are merged is called:

Select one:

a. Mergesort

b. Binary sort

c. Quicksort

d. Heapsort

The correct
answer is: Mergesort

Question 56

A traversal that visits each node after
visiting its children is called:

Select one:

a. Preorder Traversal

b. Postorder
Traversal

c. Inorder Traversal

d. Outoforder Traversal

The correct answer
is: Postorder Traversal

Question 57

The process for visiting all of the
nodes of a binary tree in some order is called a traversal.

Select one:

True

False

The correct answer is 'True'.

Question 58

A collection of
one or more trees is called:

Select one:

a. Trees

b. Multiple Spanning
Trees

c. a Forest

d. Traversals

The correct answer is: a
Forest

Question 59

The upper bound for the growth of the Algorithms running
time is represented by (please select the best answer):

1. Big Oh (O)

2. Big Omega
(Ω)

3. Big Theta (Θ)

4. Exponential growth

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
1

Question 60

Which of the following is not a mathematical proof
technique?

Select one:

a. Proof by mathematical induction

b. Proof by
contradiction

c. Direct proof

d. Proof by consensus

The correct answer
is: Proof by consensus

Question 61

For the following code fragment, select
the option that represents the most appropriate asymptotic analysis:

public static int
binarySearch(int[] a, int key) {

int left = 0;

int right = a.length-1;

while
(left <= right) {

int mid = left + (right-left)/2;

if (key < a[mid]) right =
mid-1;

else if (key > a[mid]) left = mid+1;

else return mid;

}

//not
found

return -1;

}

Option 1. Ω( 1 ), O( log n )

Option 2. Ω( n ), O( 2n
)

Option 3. Θ( n log n )

Option 4. Θ( log n )

Select one:

a.
Option 1

b. Option 2

c. Option 3

d. Option 4

The correct answer is:
Option 1

Question 62

For the following code fragment, select the choice
which represents the most appropriate asymptotic analysis:

static int function ( n )
{

sum = 0;

for (i=1; i<=n; i++)

sum += n;

return
sum;

}

Choice 1. Ω( n2 )

Choice 2. Ω( log n2 )

Choice 3. Θ( n log n
)

Choice 4. O ( n )

(NOTE: code fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d.
Choice 4

The correct answer is: Choice 4

Question 63

Which of the
following is NOT true for Linked Lists structures (please select the best choice):

Choice
1. Insertion and deletion are ( 1 ).

Choice 2. Direct access of an item in the list
structure is ( n ).

Choice 3. Space grows with number of elements.

Choice 4. There is
no overhead associated with elements in the list structure

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
4

Question 64

For the following code fragment, select the choice which
represents the most appropriate asymptotic analysis:

function ( n ) {

sum2 = 0;

for (i=1; i<=n; i++)

for (j=1; j<=i; j++)

sum2++;

}

}

Choice
1. Ω ( 1 )

Choice 2. O( 2n )

Choice 3. Θ( n2 )

Choice 4. Ω( n2
)

(NOTE: code fragment is not intended to be functioning code)

Select
one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The
correct answer is: Choice 3

Question 65

Which of the following items is NOT
true for Array-Based Lists (please select the best choice):

Choice 1. Insertion and
deletion operations are ( n )

Choice 2. Direct access of an item in the array is ( 1
)

Choice 3. Space used grows dynamically as the array is populated

Choice 4. Array
contains wasted space if array positions are not full

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 66

A method that is designed to create extremely shallow trees is
called:

Select one:

a. Dynamic node implementation

b. Union/Find

c. The
list of children method

d. Path compression

The correct answer is: Path
compression

Question 67

The process of storing blocks of data in main memory
after reading from disk is referred to as:

Select one:

a. Buffering

b.
Hashing

c. Pooling

d. Indexing

The correct answer is:
Buffering

Question 68

A solution is said to be efficient if it:

Select
one:

a. Solves the problem within the required resource constraints

b. Executes
faster than other solutions

c. Is completed in the fewest number of steps

d. Can be
explained in the context of Big-Oh notation

The correct answer is: Solves the problem
within the required resource constraints

Question 69

A sorting algorithm
that assigns records to bins and then relies on some other sorting technique to sort the records
within each bin called:

Select one:

a. Radix Sort

b. Quicksort

c. Hash
sort

d. Bucket sort

The correct answer is: Bucket sort

Question
70

In a stack which option would access the 3rd element from the top of the stack
S

Option 1. S.push(-1);

Option 2. S.dequeue(-3);

Option 3. S.pop();

S.pop();

S.pop();

Option 4. S.pop(n-3);

Select one:

a. Option 1

b.
Option 2

c. Option 3

d. Option 4

The correct answer is: Option
3

Question 71

A leaf is any node that:

Select one:

a. Has one
child

b. Is an internal node with no ancestors

c. Is any node with two empty
children

d. Is the ancestor of the root node

The correct answer is: Is any node
with two empty children

Question 72

According to textbook by Shaffer, a heap
data structure has two properties which are:

Select one:

a. every node stores a value
less than or equal to that of its children and it is a complete binary tree

b. it is a
min-heap and is partially ordered

c. it is a complete binary tree and the values stored in
it are partially ordered

d. it is a priority queue and is in Θ( n )

The
correct answer is: it is a complete binary tree and the values stored in it are partially
ordered

Question 73

The upper bound for the growth of the Algorithms running
time is represented by:

Select one:

a. Big Oh (O)

b. Big Omega (Ω)

c. Big
Theta (Θ)

d. Exponential growth

The correct answer is: Big Oh
(O)

Question 74

The lower bound for the growth of the Algorithms running
time is represented by (please the best answer):

1. Big Oh (O)

2. Big Omega
(Ω)

3. Big Theta (Θ)

4. Exponential growth

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
2

Question 75

The benefit of a quicks = True

False

The
correct answer is 'False'.

Question 76

The best asymptotic analysis for the
selection sort is represented by (select the best option):

Option 1. O( n log n
)

Option 2. Ω( n2 )

Option 3. O( n2 )

Option 4. Θ( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The
correct answer is: Option 4

Question 77

A finite set of one or more nodes
such that there is one designated node call the root is a: (select the best answer)

Select
one:

a. Parent root

b. a B+ tree data structure

c. Index

d.
Tree

The correct answer is: Tree

Question 78

True/False: The
queue data structure is implemented as FIFO structure (first in first out)

:

Select
one:

True

False

The correct answer is 'True'.

Question
79

For the following code fragment, select the choice which represents the most
appropriate asymptotic analysis:

function ( n ) {

sum2 = 0;

for (k=1; k<=n;
k*=2)

for (j=1; j<=k; j++)

sum2++;

}

Choice 1. O( 2n )

Choice 2.
Θ ( n )

Choice 3. Θ( n log n )

Choice 4. Ω( n2 )

(NOTE: code fragment
is not intended to be functioning code)

Select one:

a. Choice 1

b.
Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
2

Question 80

A coding scheme that replaces repeated occurrences of strings
with a pointer to the location in the file of the first occurrence of the string is called
Ziv-Lempel coding.

Select one:

True

False

The correct answer is
'True'.

Question 81

In a queue, placing new items in the queue is referred
to as a push and taking an item out of the queue is called a pop.

Select one:

True

False

The correct answer is 'False'.

Question 82

For
the following code fragment, select the option that represents the most appropriate asymptotic
analysis:

if (a.length > 0) {

return a[a.length - 1];

} else {

throw
new NoSuchElementException();

}

Option 1. O( 1 )

Option 2. O( 2n )

Option 3.
O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

Explanation: Here n = a.length, and T(n) = 1.

The
correct answer is: Option 1

Question 83

Setting the dirty bit causes what
action to be performed on a block: (select the best answer)

Select one:

a. It is
deleted because it is no longer consistent

b. It flushes or writes the block out to the
disk

c. Refreshes the data by re-reading the block

d. It cleans the cache by
flushing all data from the cache

The correct answer is: It flushes or writes the
block out to the disk

Question 84

Asymptotic Algorithm Analysis is primarily
concerned with:p of the computing running the algorithm

c. The speed of the compiler

d. The growth rate demonstrated in the algorithm running time equation

The correct
answer is: The growth rate demonstrated in the algorithm running time equation

Question
85

Correctly identify the following heap structure by selecting the best
answer:

Select one:

a. partially ordered heap

b. max-heap
structure

c. priority heap

d. min-heap structure

The correct answer is:
max-heap structure

Question 86

For the following code fragment, select
option that represents the most appropriate asymptotic analysis:

for (i=0; i<n; i++)
{

//

// Search in array a for smallest element starting at i to n-1

//

minIndex = findSmallestElement(a, i, n-1)

a[i] = a[minIndex];

}

findSmallestElement( int a[], int i, int n ) {

}

Option 1. O( n
)

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option
4

index-of-smallest element in a[i..j] takes j-i+1 operations

• n + (n-1) +
(n-2) + (n-3) + ... + 3 + 2 + 1

• this is n2

The correct answer is: Option
4

Question 87

An algorithm that breaks a file to be sorted in smaller files
called runs which are sorted and eventually put back together resulting in a sorted file is
called:

Select one:

a. Quicksort algorithm

b. Replacement sort algorithm

c. An indexed key sort algorithm

d. Mergesort algorithm

The correct answer is:
Mergesort algorithm

Question 88

A list is

Select one:

a. An ADT
for storing and retrieving data

b. A tree data structure

c. Finite ordered sequence
of data items

d. A collection of operations to implement an ADT

The correct
answer is: Finite ordered sequence of data items

Question 89

Select the
answer that best defines Huffman Coding:

Select one:

a. A set of coding rules that is
typically used for compression

b. A fixed length coding scheme for character
representation

c. A tree structure that trades off space and time requirements to provide
a more efficient priority queue

d. An approach of assigning codes to characters such that
the frequency length of the code depends upon the relative frequency of the corresponding
character in use

The correct answer is: An approach of assigning codes to characters
such that the frequency length of the code depends upon the relative frequency of the
corresponding character in use

Question 90

True/False: Big Theta (Θ)
indicates that the Upper and Lower bounds of an algorithm are the same.

Select one:

True

False

The correct answer is 'True'.

Question 91

The
quicksort is typically slower than the heapsort by a constant factor.

Select one:

True

False

The correct answer is 'False'.

Question
92

Secondary storage is characterized by the following:

Select one:

a. It
is persistent

b. It is faster than primary storage

c. It is volatile

d. It is
more expensive than primary storage

The correct answer is: It is
persistent

Question 93

A compound computed search that combines a binary
search to get close to the required record and then uses sequential search to find the item is
referred to as a/an:

Select one:

a. Zipf search

b. An Exact match search

c. A Dictionary search

d. bit map vector search

The correct answer is: A
Dictionary search

< �8�U �8�U$� �U�:�
�U��8�U@�8�U@@�8�Uppropriate asymptotic analysis:

static int function ( n ) {

sum = 0;

for (i=1; i<=n; i++)

sum += n;

return sum;

}

Choice 1. Ω( n2 )

Choice 2. Θ ( n2 )

Choice 3. O( log n
)

Choice 4. O( n )

(NOTE: code fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice
4

The correct answer is: Choice 4

Question 95

According to the
properties of logarithms, log(nm) =

Note: Due to issues with HTML formatting, an exponent
is represented by preceding it with the ^ symbol. As such x^2 is equivalent to x2.

Select
one:

a. log n – log m

b. n log n

c. log n + log m

d.
log(n^m)

The correct answer is: log n + log m

Question 96

A
characteristic of RAM (random access memory) is that it is persistent and is not lost when the
power to a computer is turned off.

Select one:

True

False

The
correct answer is 'False'.

Question 97

A full binary tree has a restricted
shape which starts at the root and fills the tree by levels from left to right.

Select
one:

True

False

The correct answer is 'False'.

Question
98

What is the role of the pivot in a quicksort algorithm?

Select one:

a.
It identifies the maxkey value

b. It specifies the point where the array will be
subdivided into partitions and each partition then sorted

c. It defines the sequence for
merging in the sort

d. It indicates the index of the current record being
compared

The correct answer is: It specifies the point where the array will be
subdivided into partitions and each partition then sorted

Question 99

For
the following code fragment, select the choice which represents the most appropriate asymptotic
analysis:

/** @return The position of an element in sorted array A with value k. If k is
not in A,return A.length. */

static int binary(int[] A, int k) {

int l = -1; // Set l
and r

int r = A.length; // beyond array bounds

while (l+1 != r) { // Stop when l, r
meet

int i = (l+r)/2; // Check middle

if (k < A[i]) r = i; // In left half

if (k == A[i]) return i; // Found it

if (k > A[i]) l = i; // In right half

}

return A.length; // Search value not in A

}

Choice 1. Θ ( n
)

Choice 2. O( 2n )

Choice 3. O( log n )

Choice 4. Ω( n2 )

(NOTE: code
fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 100

A linear index is an index file organized as a sequence of
key/pointer pairs where the keys are in a sorter order.

Select one:

True

False

The correct answer is 'True'.

Question 101

The freelist
…

Select one:

a. Provides access to memory within the operating system that
has not yet been allocated

b. Provides access to memory objects which have no Big O ( n )
time.

c. Facilitates and encourages the use of the new operator.

d. Holds the list
nodes that are no longer in use.

The correct answer is: Holds the list nodes that are
no longer in use.

Question 102

A tree data structure whose shape obeys the
following definition,

o A node contains one or two keys

o Every internal node has
either 2 children if it contains 1 key or 3 children if it contains two keys

o All leaves
are at the same level in the tree

Is called a/an:

Select one:

a. B*-Tree

b. BST

c. B+-Tree

d. 2-3 tree

The correct answer is: 2-3
tree

Question 103

A preorder traversal visits every node starting at the
leaf nodes and working up the tree.

Select one:

True

False

The
correct answer is 'False'.

Question 104

For the following code fragment,
select the choice which represents the most appropriate asymptotic analysis:

public E
getValue ( ) {

assert (curr >= 0) && (curr < listSize) :

"No current
element";

return listArray[curr];

}

Choice 1. Θ ( n )

Choice 2. O( 2n
)

Choice 3. Θ( n log n )

Choice 4. O( 1 )

(NOTE: code fragment is not
intended to be functioning code)

Select one:

a. Choice 1

b.
Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
4

Question 105

Internal Fragmentation refers to: (select the best
answer)

Select one:

a. Space that is left empty because records do not fit evenly
into a sector

b. Space allocated to a file that is not physically adjacent on the disk
drive

c. Space that is left empty because records do not fit evenly into a sector or Space
allocated to a file that is not physically adjacent

d. None of the options

The
correct answer is: Space that is left empty because records do not fit evenly into a sector or
Space allocated to a file that is not physically adjacent

Question 106

A
binary tree traversal that lists every node in the tree exactly once is called:

Select
one:

a. a Traversal

b. A visitor design pattern

c. An enumeration

d.
Natural ordering sequence

The correct answer is: An enumeration

The process of
associating a key with the location of a corresponding data record is called
folding.

Select one:

True

False

The correct answer is
'False'.

Question 2

A characteristic of RAM (random access memory) is that
it is persistent and is not lost when the power to a computer is turned off.

Select
one:

True

False

The correct answer is 'False'.

Question
3

An algorithm that breaks a file to be sorted in smaller files called runs which are
sorted and eventually put back together resulting in a sorted file is called:

Select
one:

a. Quicksort algorithm

b. Replacement sort algorithm

c. An indexed key
sort algorithm

d. Mergesort algorithm

The correct answer is: Mergesort
algorithm

Question 4

The weighted union rule joins a tree with fewer nodes
to a tree with more nodes by making the smaller tree’s root point to the root of the
larger tree.

Select one:

True

False

The correct answer is
'True'.

Question 5

For the following code fragment, select the option that
represents the most appropriate asymptotic analysis:

for (int i = 1; i <= n; i *= 2) {

for (int j = 0; j < n; j++) {

count++;

}

}

Option 1. O( 1
)

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option
4

Explanation: Here the outer loop is done log n times and the inner loop is done n
times, so T(n) = n log n. (Note that the default base for logarithms in Computer Science is
2.)

The correct answer is: Option 3

Question 6

The best asymptotic
analysis for the selection sort is represented by (select the best option):

Option 1. O( n
log n )

Option 2. Ω( n2 )

Option 3. O( n2 )

Option 4. Θ( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The
correct answer is: Option 4

Question 7

A leaf is any node that:

Select
one:

a. Has one child

b. Is an internal node with no ancestors

c. Is any node
with two empty children

d. Is the ancestor of the root node

The correct answer
is: Is any node with two empty children

Question 8

A preorder traversal
visits every node starting at the leaf nodes and working up the tree.

Select one:

True

False

The correct answer is 'False'.

Question 9

For
the following code fragment, select the option which represents the most appropriate asymptotic
analysis:

/** @return Position of largest value in "A“ */

static int
largest(int[] A) {

int currlarge = 0; // Position of largest

for (int i=1;
i<A.length; i++)

if (A[currlarge] < A[i])

currlarge = i; // Remember pos

return currlarge; // Return largest pos

}

Choice 1. Θ ( n )

Choice
2. O( 2n )

Choice 3. Θ( n log n )

Choice 4. Ω( n2 )

(NOTE: code fragment is
not intended to be functioning code)

S =Pt answer is: Choice 1

Question
10

A technique that allows a programmer to use more main memory than exists in the
computer is called: (select the best answer)

Select one:

a. Buffer cache

b.
Random access memory

c. Secondary storage

d. Virtual memory

The correct
answer is: Virtual memory

Question 11

A method that is designed to create
extremely shallow trees is called:

Select one:

a. Dynamic node implementation

b. Union/Find

c. The list of children method

d. Path compression

The
correct answer is: Path compression

Question 12

For the following code
fragment, select the choice which represents the most appropriate asymptotic
analysis:

static int function ( n ) {

sum = 0;

for (j=1; j<=n; j++)

for (i=1; i<=j; i++)

sum++;

return sum;

}

Choice 1. Θ ( n
)

Choice 2. O( 2n )

Choice 3. Θ( n2 )

Choice 4. Ω( n2 )

(NOTE: code
fragment is not intended to be functioning code)

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 13

Asymptotic Algorithm Analysis is primarily concerned
with:

Select one:

a. The size of the constant in the algorithm running time
equation

b. The speed of the computing running the algorithm

c. The speed of the
compiler

d. The growth rate demonstrated in the algorithm running time
equation

The correct answer is: The growth rate demonstrated in the algorithm running
time equation

Question 14

According to the properties of logarithms, log(nm)
=

Note: Due to issues with HTML formatting, an exponent is represented by preceding it with
the ^ symbol. As such x^2 is equivalent to x2.

Select one:

a. log n – log
m

b. n log n

c. log n + log m

d. log(n^m)

The correct answer is:
log n + log m

Question 15

The process for visiting all of the nodes of a
binary tree in some order is called a traversal.

Select one:

True

False

The correct answer is 'True'.

Question 16

A list is said to
be empty when all of its elements have a zero (0) value

Select one:

True

False

The correct answer is 'False'.

Question 17

A list that
organizes the order of records within the list based upon patterns of actual record access is
called a/an (select the best answer):

Select one:

a. Quadratic Binary search
order

b. A Zipf Distribution

c. A Self-organizing list

d. A range
query

The correct answer is: A Self-organizing list

Question 18

A
sort that features a limit of n-1 of record swaps is called:

Select one:

a. Insertion
sort

b. Bubble sort

c. Inversion sort

d. Selection sort

The correct
answer is: Sepng from disk is referred to as:

Select one:

a. Buffering

b.
Hashing

c. Pooling

d. Indexing

The correct answer is:
Buffering

Question 20

The upper bound for the growth of the Algorithms
running time is represented by:

Select one:

a. Big Oh (O)

b. Big Omega
(Ω)

c. Big Theta (Θ)

d. Exponential growth

The correct answer is:
Big Oh (O)

Question 21

A coding scheme that replaces repeated occurrences of
strings with a pointer to the location in the file of the first occurrence of the string is
called Ziv-Lempel coding.

Select one:

True

False

The correct answer
is 'True'.

Question 22

In linked lists there are no NULL links
in:

Select one:

a. Single linked list

b. Linear doubly linked list

c.
Circular linked list

d. None of these

The correct answer is: Circular linked
list

Q@8case:

Select one:

True

False

The correct answer is
'False'.

Question 24

Internal Fragmentation refers to: (select the best
answer)

Select one:

a. Space that is left empty because records do not fit evenly
into a sector

b. Space allocated to a file that is not physically adjacent on the disk
drive

c. Space that is left empty because records do not fit evenly into a sector or Space
allocated to a file that is not physically adjacent

d. None of the options

The
correct answer is: Space that is left empty because records do not fit evenly into a sector or
Space allocated to a file that is not physically adjacent

Question 25

A
binary tree traversal that lists every node in the tree exactly once is called:

Select
one:

a. a Traversal

b. A visitor design pattern

c. An enumeration

d.
Natural ordering sequence

The correct answer is: An enumeration

Question
26

Which of the following is not one of the general approaches to search
algorithms:

Select one:

a. Buffer cache access methods

b. Sequential and list
methods

c. Direct access by key value (hashing)

d. Tree indexing
methods

The correct answer is: Buffer cache access methods

Question
27

In a queue, placing new items in the queue is referred to as a push and taking an
item out of the queue is called a pop.

Select one:

True

False

The
correct answer is 'False'.

Question 28

Which of the following is not a
mathematical proof technique?

Select one:

a. Proof by mathematical induction

b.
Proof by contradiction

c. Direct proof

d. Proof by consensus

The correct
answer is: Proof by consensus

Question 29

True/False: There is always one
most efficient algorithm to solve a particular problem.

Select one:

True

False

The correct answer is 'False'.

Question 30

The process of
determining if two objects are in the same set and then merging those sets is
called:

Select one:

a. a Union Operation

b. Union / Find

c. a Weighted
Union

d. a Merge Operation

The correct answer is: Union /
Find

Question 31

Data is stored within the disk drive on the: (select the
best answer)

Select one:

a. Spindle

b. Platter

c. Cylinder

d.
Sector

The correct answer is: Platter

Question 32

The depth of
node H in the following tree is:

Select one:

a. 3

b. 2

c. 4

d. 1

The correct answer is: 3

Question 33

An ADT is:

Select
one:

a. A type together with a collection of operations to manipulate the type

b. An
implementation of a flyweight design pattern

c. The realization of a data type as a
software component

d. An implementation in java of a class for a data type

The
correct answer is: The realization of a data type as a software component

Question
34

A full binary tree ha �8�U �8�U$�
�U�:�
�U��8�U@�8�U@@�8�Uct one:

True

False

The correct answer is 'False'.

Question 35

For the
following code fragment, select the choice which represents the most appropriate asymptotic
analysis:

function ( n ) {

sum1 = 0;

for (k=1; k<=n; k*=2)

for (j=1;
j<=n; j++)

sum1++;

}

Choice 1. Θ ( n )

Choice 2. O( 2n
)

Choice 3. Θ( n log n )

Choice 4. Ω( n2 )

(NOTE: code fragment is not
intended to be functioning code)

Select one:

a. Choice 1

b. Choice
2

c. Choice 3

d. Choice 4

The correct answer is: Choice
3

Question 36

A linked list creates order through the use of pointers that
link one element to another.

Select one:

True

False

The correct
answer is 'True'.

Question 37

The implementation of a data type as a data
structure is the physical form of an ADT.

Select one:

True

False

The
correct answer is 'True'.

Question 38

Secondary storage is characterized by
the following:

Select one:

a. It is persistent

b. It is faster than primary
storage

c. It is volatile

d. It is more expensive than primary
storage

The correct answer is: It is persistent

Question 39

The
process of storing records in the order that they were added to a file is called:

Select
one:

a. Entry-sequenced file

b. Binary Sequenced file

c. LIFO file
format

d. Tombstone approach

The correct answer is: Entry-sequenced
file

Question 40

For the following code fragment, select option that
represents the most appropriate asymptotic analysis:

for (i=0; i<n; i++) {

//

// Search in array a for smallest element starting at i to n-1

//

minIndex
= findSmallestElement(a, i, n-1)

a[i] = a[minIndex];

}

findSmallestElement( int
a[], int i, int n ) {

int largest = a[i];

while(i<n) {

if(a[i]
>a[largest])

largest = i;

i++;

}

return(largest);

}

Option
1. O( n )

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option
4

index-of-smallest element in a[i..j] takes j-i+1 operations

• n + (n-1) +
(n-2) + (n-3) + ... + 3 + 2 + 1

• this is n2

The correct answer is: Option
4

Question 41

When big-Oh and coincide, we indicate this by using (select
the best answer):

1. Big Oh (O)

2. Big Omega (Ω)

3. Big Theta (Θ)

4.
Exponential growth

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice 3

Question 42

Which of
the following is not a characteristic of an algorithm?

Select one:

a. It must be
correct

b. It must be composed of concrete steps

c. It can have no ambiguity

d. It must be composed of an infinite number of steps.

The correct answer is: It must
be composed of an infinite number of steps.

Question 43

Each record of a
database normally has a unique identifier called the:

Select one:

a. Secondary
Key

b. Primary index

c. Primary key

d. Index key

The correct answer
is: Primary key

Question 44

Which of the following is NOT one of the buffer
pool heuristics defined in the text : (select the best answer)

Select one:

a.
FIFO

b. LIFO

c. LRU

d. LFU

The correct answer is:
LIFO

Question 45

A collection of one or more trees is called:

Select
one:

a. Trees

b. Multiple Spanning Trees

c. a Forest

d.
Traversals

The correct answer is: a Forest

Question 46

Enqueue
and Dequeue are notations associated with which data structure:

Select one:

a.
Queue

b. Stack

c. List

d. Array

The correct answer is:
Queue

Question 47

A traversal that visits each node after visiting its
children is called:

Select one:

a. Preorder Traversal

b. Postorder
Traversal

c. Inorder Traversal

d. Outoforder Traversal

The correct answer
is: Postorder Traversal

Question 48

For the following code fragment, select
the choice which represents the most appropriate asymptotic analysis:

function ( n )
{

sum2 = 0;

for (k=1; k<=n; k*=2)

for (j=1; j<=k; j++)

sum2++;

}

Choice 1. O( 2n )

Choice 2. Θ ( n )

Choice 3. Θ( n log
n )

Choice 4. Ω( n2 )

(NOTE: code fragment is not intended to be functioning
code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d.
Choice 4

The correct answer is: Choice 2

Question 49

For the
following code fragment, select the option that represents the most appropriate asymptotic
analysis:

public static int binarySearch(int[] a, int key) {

int left = 0;

int
right = a.length-1;

while (left <= right) {

int mid = left +
(right-left)/2;

if (key < a[mid]) right = mid-1;

else if (key > a[mid]) left =
mid+1;

else return mid;

}

//not found

return -1;

}

Option 1.
Ω( 1 ), O( log n )

Option 2. Ω( n ), O( 2n )

Option 3. Θ( n log n )

Option
4. Θ( log n )

Select one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The correct answer is: Option 1

Question 50

The
processing time or cost of a sort is defined by the number of comparisons and exchanges that
must be made during processing. What is the average cost of the heapsort?:

Option 1. O( n
log n )

Option 2. Ω( n2 )

Option 3. O( n2 )

Option 4. Θ( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The
correct answer is: Option 1

Question 51

For the following code fragment,
select the choice which represents the most appropriate asymptotic analysis:

public E
getValue ( ) {

assert (curr >= 0) && (curr < listSize) :

"No current
element";

return listArray[curr];

}

Choice 1. Θ ( n )

Choice 2. O( 2n
)

Choice 3. Θ( n log n )

Choice 4. O( 1 )

(NOTE: code fragment is not
intended to be functioning code)

Select one:

a. Choice 1

b.
Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
4

Question 52

For the following code fragment, select the option that
represents the most appropriate asymptotic analysis:

// Recursive Fibonacci
generator

static long fibr(int n) {

if ((n == 1) || (n == 2)) return 1; // Base
case

return fibr(n-1) + fibr(n-2); // Recursive call

}

Option 1. O( n
)

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option 4

The
correct answer is: Option 2

Question 53

True/False: Big Theta (Θ)
indicates that the Upper and Lower bounds of an algorithm are the same.

Select one:

True

False

The correct answer is 'True'.

Question 54

For
the following code fragment, select the choice which represents the most appropriate asymptotic
analysis:

static int function ( n ) {

for (k=0; k<n; k++)

A[k] = k;

return A[k];

}

Choice 1. O ( n2 )

Choice 2. O( 2n )

Choice 3. Ω( n2
)

Choice 4. Θ ( n )

(NOTE: code fragment is not intended to be functioning
code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d.
Choice 4

The correct answer is: Choice 4

Question 55

The freelist
…

Select one:

a. Provides access to memory within the operating system that
has not yet been allocated

b. Provides access to memory objects which have no Big O ( n )
time.

c. Facilitates and encourages the use of the new operator.

d. Holds the list
nodes that are no longer in use =!

Which of the following is NOT true for Linked
Lists structures (please select the best choice):

Choice 1. Insertion and deletion are ( 1
).

Choice 2. Direct access of an item in the list structure is ( n ).

Choice 3. Space
grows with number of elements.

Choice 4. There is no overhead associated with elements in
the list structure

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice 4

Question 57

A sort
algorithm that uses two nested loops with the inner loop moving through the array from bottom to
top is called the:

Select one:

a. Insertion sort

b. Bubble sort

c.
Inversion sort

d. Selection sort

The correct answer is: Bubble
sort

Question 58

For the following code fragment, select the option which
represents the most appropriate asymptotic analysis:

static int function ( n ) {

sum
= 0;

for (i=1; i<=n; i++)

sum += n;

return sum;

}

Option 1. Ω( n2
)

Option 2. Θ ( n )

Option 3. O( log n )

Option 4. O( 2n )

(NOTE: code
fragment is not intended to be functioning code)

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
2

Question 59

A list is

Select one:

a. An ADT for storing and
retrieving data

b. A tree data structure

c. Finite ordered sequence of data
items

d. A collection of operations to implement an ADT

The correct answer is:
Finite ordered sequence of data items

Question 60

Push and Pop are notations
associated with which data structure:

Select one:

a. Queue

b. Stack

c.
List

d. Array

The correct answer is: Stack

Question 61

A
tree whose internal nodes all have exactly K children is called a K-ary tree.

Select
one:

True

False

The correct answer is 'True'.

Question
62

A compound computed search that combines a binary search to get close to the
required record and then uses sequential search to find the item is referred to as
a/an:

Select one:

a. Zipf search

b. An Exact match search

c. A Dictionary
search

d. bit map vector search

The correct answer is: A Dictionary
search

Question 63

Correctly identify the following heap structure by
selecting the best answer:

Select one:

a. partially ordered heap

b.
max-heap structure

c. priority heap

d. min-heap structure

The correct
answer is: max-heap structure

Question 64

A traversal that visits each node
before visiting its children is called:

Select one:

a. Preorder traversal

b.
Postorder traversal

c. Inorder Traversal

d. Outoforder Traversal

The
correct answer is: Preorderp

o A node contains one or two keys

o Every internal node
has either 2 children if it contains 1 key or 3 children if it contains two keys

o All
leaves are at the same level in the tree

Is called a/an:

Select one:

a.
B*-Tree

b. BST

c. B+-Tree

d. 2-3 tree

The correct answer is: 2-3
tree

Question 66

Select the answer that best defines Huffman
Coding:

Select one:

a. A set of coding rules that is typically used for
compression

b. A fixed length coding scheme for character representation

c. A tree
structure that trades off space and time requirements to provide a more efficient priority
queue

d. An approach of assigning codes to characters such that the frequency length of
the code depends upon the relative frequency of the corresponding character in
use

The correct answer is: An approach of assigning codes to characters such that the
frequency length of the code depends upon the relative frequency of the corresponding character
in use

Question 67

A significant benefit to using an index to hold and sort
keys to a file is:

Select one:

a. Smaller keys require less I/O

b. The entire
sort can always be completed in memory

c. The head of the disk drive does not need to
move

d. There is no seek time added to the latency of I/O operations

The
correct answer is: Smaller keys require less I/O

Question 68

For the
following code fragment, select the choice which represents the most appropriate asymptotic
analysis:

static int function ( n ) {

sum = 0;

for (i=1; i<=n; i++)

sum += n;

return sum;

}

Choice 1. Ω( n2 )

Choice 2. Θ ( n2
)

Choice 3. O( log n )

Choice 4. O( n )

(NOTE: code fragment is not intended to
be functioning code)

Select one:

a. Choice 1

b. Choice 2

c.
Choice 3

d. Choice 4

The correct answer is: Choice 4

Question
69

The most time consuming of the following operations on an array based list
implementation is:

Select one:

a. Inserting a new element at position n-1 in the list
where n is the number of elements in the list.

b. Inserting a new element into the head of
the list.

c. Removing an element at position n-1 within the list

d. Removing an
element from the tail of the list.

The correct answer is: Inserting a new element
into the head of the list.

Question 70

For the following code fragment,
select the choice which represents the most appropriate asymptotic analysis:

static int
function ( n ) {

sum = 0;

for (i=1; i<=n; i++)

sum += n;

return
sum;

}

Choice 1. Ω( n2 )

Choice 2. Ω( log n2 )

Choice 3. Θ( n log n
)

Choice 4. O ( n )

(NOTE: code fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d.
Choice 4

The correct answer is: Choice 4

Question 71

For the
following code fragment, select the choice which represents the most appropriate asymptotic
analysis:

function ( n ) {

sum1 = 0;

for (i=1; i<=n; i++)

for (j=1;
j<=n; j++)

sum1++;

}

Choice 1. Θ ( n2 )

Choice 2. O( 2n
)

Choice 3. Θ( n log n )

Choice 4. Ω( log n2 )

(NOTE: code fragment is not
intended to be functioning code)

Select one:

a. Choice 1

b. Choice
2

c. Choice 3

d. Choice 4

The correct answer is: Choice
1

Question 72

A linked list implementation relies upon static memory
allocation where static refers to the requirement to pre-allocate all of the memory that will be
used for the list.

Select one:

True

False

The correct answer is
'False'.

Question 73

A sorting algorithm that assigns records to bins and
then relies on some other sorting technique to sort the records within each bin
called:

Select one:

a. Radix Sort

b. Quicksort

c. Hash sort

d.
Bucket sort

The correct answer is: Bucket sort

Question
74

True/False: The stack data structure is implemented as a LIFO structure (last in
first out)

Select one:

True

False

The correct answer is
'True'.

Question 75

True/False: The queue data structure is implemented as
FIFO structure (first in first out)

:

Select one:

True

False

The correct answer is 'True'.

Question 76

Recursion is when
an algorithm uses a series of loop structures to repeat an operation until the answer has been
computed.

Select one:

True

False

The correct answer is
'False'.

Question 77

Which of the following is NOT one of the design
patterns outlined in our text.

Select one:

a. Flyweight

b. Visitor

c.
Composite

d. Synergy

The correct answer is: Synergy

Question
78

In a stack which option would access the 3rd element from the top of the stack
S

Option 1. S.push(-1);

Option 2. S.dequeue(-3);

Option 3. S.pop();

S.pop();

S.pop();

Option 4. S.pop(n-3);

Select one:

a. Option 1

b.
Option 2

c. Option 3

d. Option 4

The correct answer is: Option
3

Question 79

For the following code fragment, select the choice which
represents the most appropriate asymptotic analysis:

/** @return The position of an element
in sorted array A with value k. If k is not in A,return A.length. */

static int
binary(int[] A, int k) {

int l = -1; // Set l and r

int r = A.length; // beyond
array bounds

while (l+1 != r) { // Stop when l, r meet

int i = (l+r)/2; // Check
middle

if (k < A[i]) r = i; // In left half

if (k == A[i]) return i; // Found
it

if (k > A[i]) l = i; // In right half

}

return A.length; // Search value
not in A

}

Choice 1. Θ ( n )

Choice 2. O( 2n )

Choice 3. O( log n
)

Choice 4. Ω( n2 )

(NOTE: code fragment is not intended to be functioning code)

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice
4

The correct answer is: Choice 3

Question 80

A traversal that
visits the left subtree, then the node, and then the right subtree is called:

Select
one:

a. Preorder Traversal

b. Postorder Traversal

c. Inorder Traversal

d. Outoforder Traversal

The correct answer is: Inorder Traversal

Question
81

Inserting or removing an item at position n-1 within a linked list has the same
cost in terms ( n ) time as the same operation in an array based implementation of a
list.

Select one:

True

False

The correct answer is
'False'.

Question 82

For the following code fragment, select the option that
represents the most appropriate asymptotic analysis:

if (a.length > 0) {

return
a[a.length - 1];

} else {

throw new NoSuchElementException();

}

Option 1.
O( 1 )

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select
one:

a. Option 1

b. Option 2

c. Option 3

d. Option
4

Explanation: Here n = a.length, and T(n) = 1.

The correct answer is: Option
1

Question 83

The most significant difference between the B+-Tree and the
BST is that the B+-Tree stores records only at the leaf nodes.

Select one:

True

False

The correct answer is 'True'.

Question 84

According to
textbook by Shaffer, a heap data structure has two properties which are:

Select one:

a. every node stores a value less than or equal to that of its children and it is a complete
binary tree

b. it is a min-heap and is partially ordered

c. it is a complete binary
tree and the values stored in it are partially ordered

d. it is a priority queue and is in
Θ( n )

The correct answer is: it is a complete binary tree and the values
stored in it are partially ordered

Question 85

For the following code
fragment, select the choice which represents the most appropriate asymptotic
analysis:

static int function ( n ) {

for (k=0; k<n; k++)

A[k] = k;

return A[k];

}

Choice 1. Θ ( n log n )

Choice 2. O( 2n )

Choice 3. O(
n )

Choice 4. Ω( n2 )

(NOTE: code fragment is not intended to be functioning
code)

Select one:

a. Choice 1

b. Choice 2

c. Choice
3

d. Choice 4

The correct answer is: Choice 3

Question 86

A
linear index is an index file organized as a sequence of key/pointer pairs where the keys are in
a sorter order.

Select one:

True

False

The correct answer is
'True'.

Question 87

An exchange sort is one where: (select the best
answer)

Select one:

a. Records in an unsorted list are moved to a sorted list

b. Adjacent records in the list and compared and exchanged

c. An inversion is
executed

d. The sorting algorithm is said to be stable

The correct answer is:
Adjacent records in the list and compared and exchanged

Question 88

What is
the role of the pivot in a quicksort algorithm?

Select one:

a. It identifies the
maxkey value

b. It specifies the point where the array will be subdivided into partitions
and each partition then sorted

c. It defines the sequence for merging in the sort

d.
It indicates the index of the current record being compared

The correct answer is: It
specifies the point where the array will be subdivided into partitions and each partition then
sorted

Question 89

If A={1, 2, 3, 4} and B={4, 5, 6}, find A∪ B
.

Select one:

a. {1,2,3,4,4,5,6}

b. {4}

c. {x | x is all positive
integers}

d. {1,2,3,4,5,6}

The correct answer is:
{1,2,3,4,5,6}

Question 90

Setting the dirty bit causes what action to be
performed on a block: (select the best answer)

Select one:

a. It is deleted because
it is no longer consistent

b. It flushes or writes the block out to the disk

c.
Refreshes the data by re-reading the block

d. It cleans the cache by flushing all data
from the cache

The correct answer is: It flushes or writes the block out to the
disk

Question 91

Which of the following items is NOT true for Array-Based
Lists (please select the best choice):

Choice 1. Insertion and deletion operations are (
n )

Choice 2. Direct access of an item in the array is ( 1 )

Choice 3. Space used
grows dynamically as the array is populated

Choice 4. Array contains wasted space if array
positions are not full

Select one:

a. Choice 1

b. Choice 2

c. Choice
3

d. Choice 4

The correct answer is: Choice 3

Question
92

The lower bound for the growth of the Algorithms running time is represented by
(please the best answer):

1. Big Oh (O)

2. Big Omega (Ω)

3. Big Theta
(Θ)

4. Exponential growth

Select one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice 2

Question
93

A sequential tree can be represented using a bit vector?

Select one:

True

False

The correct answer is 'True'.

Question 94

The
list of children approach uses both pointers and an array structure to represent the
tree.

Select one:

True

False

The correct answer is
'True'.

Question 95

The upper bound for the growth of the Algorithms running
time is represented by (please select the best answer):

1. Big Oh (O)

2. Big Omega
(Ω)

3. Big Theta (Θ)

4. Exponential growth

Select one:

a. Choice
1

b. Choice 2

c. Choice 3

d. Choice 4

The correct answer is: Choice
1

Question 96

A traversal of a general tree that traverses the roots
subtrees from left to right, then visits the root is called a preorder traversal.

Select
one:

True

False

The correct answer is 'False'.

Question
97

For the following code fragment, select the most appropriate asymptotic
analysis:

// Towers of Hanoi

static void solveHanoi(int disks, char fromPole, char
toPole, char withPole) {

if (disks >= 1) {

solveHanoi(disks-1, fromPole,
withPole, toPole);

moveDisk(fromPole, toPole);

solveHanoi(disks-1, withPole, toPole,
fromPole);

}

}

static void moveDisk(char fromPole, char toPole) {

moves++;

}

Option 1. O( n )

Option 2. O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option 1

b. Option 2

c. Option
3

d. Option 4

The correct answer is: Option 2

Question
98

The full binary tree theorem states “the number of leaves in an empty full
binary tree is one more than the number of internal nodes”

Select one:

True

False

The correct answer is 'False'.

Question 99

The
quicksort is typically slower than the heapsort by a constant factor.

Select one:

True

False

The correct answer is 'False'.

Question 100

A
sort where the list is divided into halves, the halves sorted and these two halves are merged is
called:

Select one:

a. Mergesort

b. Binary sort

c. Quicksort

d.
Heapsort

The correct answer is: Mergesort

Question 101

An
important advantage of the sequential tree implementation is that (select the best
answer):

Select one:

a. It is an extremely shallow tree

b. The data structure
can be transmitted between computers

c. It saves space because no pointers are
stored

d. It uses dynamic nodes

The correct answer is: It saves space because
no pointers are stored

Question 102

True/False: Big Theta (Θ)
indicates that the Upper and Lower bounds of an algorithm are the same.

Select one:

True

False

The correct answer is 'True'.

Question 103

A
solution is said to be efficient if it:

Select one:

a. Solves the problem within the
required resource constraints

b. Executes faster than other solutions

c. Is
completed in the fewest number of steps

d. Can be explained in the context of Big-Oh
notation

The correct answer is: Solves the problem within the required resource
constraints

Question 104

A finite set of one or more nodes such that there
is one designated node call the root is a: (select the best answer)

Select one:

a.
Parent root

b. a B+ tree data structure

c. Index

d. Tree

The
correct answer is: Tree

Question 105

For the following code fragment, select
the option that represents the most appropriate asymptotic analysis:

for (int i = 0; i <
a.length; i++) {

System.out.println(a[i]);

}

Option 1. O( n )

Option 2.
O( 2n )

Option 3. O( n log n )

Option 4. O( n2 )

Select one:

a. Option
1

b. Option 2

c. Option 3

d. Option 4

The correct answer is: Option
1

Question 106

For the following code fragment, select the choice which
represents the most appropriate asymptotic analysis:

function ( n ) {

sum2 = 0;

for (i=1; i<=n; i++)

for (j=1; j<=i; j++)

sum2++;

}

}

Choice
1. Ω ( 1 )

Choice 2. O( 2n )

Choice 3. Θ( n2 )

Choice 4. Ω( n2
)

(NOTE: code fragment is not intended to be functioning code)

Select
one:

a. Choice 1

b. Choice 2

c. Choice 3

d. Choice 4

The
correct answer is: Choice 3

**CS 3304: ANALYSIS OF ALGORITHMS**

Using Prim’s Algorithm, determine the minimum spanning tree of the following graph. When you have identified the MST, add together the path weights and submit as your answer.

Please enter a numerical answer only; do not enter any letters or words.

Answer:

The correct answer is: 12

Question 2

Question text

Using Prim’s Algorithm, determine the minimum spanning tree of the following graph.

Which edge, written in the format of: (startnode, endnode), is NOT included in the minimum spanning tree?

Please enter your answer in the following format: (#,#)

Answer:

The correct answer is: (1, 8)

Question 3

Question text

Using Prim’s Algorithm, determine the minimum spanning tree of the following graph.

What is the weight of the minimum spanning tree (the sum of the weights of the edges included in the minimum spanning tree)?

Please enter a numerical answer only; do not enter any letters or words.

Answer:

The correct answer is: 22

Information

Information text

For the following questions, please read this problem statement:

A computer manufacturer must determine what product mix to produce. A server requires 4
CPU’s and 8 Memory modules. A desktop computer requires 1 CPU and 4 Memory modules. Each
server is sold for $1850 and each desktop is sold for $925. The manufacturer must produce a
quantity of both units to keep both lines in production so the quantity of servers and desktops
produced must both be greater than 0.

The manufacturer can only get a supply of 1250
CPU’s and 3800 memory modules due to shortages in the supply chain. Using the Simplex
algorithm, determine the number of servers and desktops that should be built to maximize the
profits of the manufacturer and determine how much revenue will be generated.

Please enter a numerical answer only; do not enter any letters or words. If the answer is a dollar amount, please enter in the following format: $#,###

Question 4

Question text

How many servers should be built?

Answer:

The correct answer is: 150

Question 5

Question text

How many Desktop computers should be built?

Answer:

The correct answer is: 650

Question 6

Question text

How much Revenue (money in dollars received by selling the desktops and servers) will be generated?

Answer:

The correct answer is: $878,750.00

** **

True/False: Dynamic Programming reduces asymptotic complexity by eliminating redundant computations.

Select one:

True

False

The correct answer is 'True'.

Question 2

Question text

True/False: Recursive routines cannot be used in Dynamic Programming algorithms?

Select one:

True

False

The correct answer is 'True'.

Question 3

Question text

Which of the following is NOT one of the main principles of dynamic programming algorithms?

Select one:

- Optimal substructure: optimal solutions to problems are built from optimal solutions to subproblems.
- "Shop around": to determine the best option, try them all and select the best one. Do not employ heuristics.
- Memorization: answers to subproblems are remembered to avoid repeated computation of the same thing.
- Recursion: implemented as a recursive routine to reduce overhead and improve computational efficiency.

The correct answer is: Recursion: implemented as a recursive routine to reduce overhead and improve computational efficiency.

Question 4

Question text

True/False: In a dynamic programming algorithm, we can use a table to store results of sub-problems and then refer to this table to ensure that we don't recomputed those sub-problems.

Select one:

True

False

The correct answer is 'True'.

Question 5

Question text

True/False: Dynamic programming is a variation of the linear programming model in that it breaks the problem down into smaller problems that are solved using the simplex method?

Select one:

True

False

The correct answer is 'False'.

Question 6

Question text

True/False: Dynamic programming is less complex asymptotically but is substantially more complex from a programming perspective?

Select one:

True

False

The correct answer is 'False'.

** **

If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a time, in what order will they be removed?

Select one:

- ABCD
- ABDC
- DCAB
- DCBA
- ACDB

The correct answer is: DCBA

Question 2

Question text

What is the big-o complexity of the red line?

Select one:

- O(n)
- O(log n)
- O(n²)
- O(1)

The correct answer is: O(1)

Question 3

Question text

What is the big-o complexity of the purple line?

Select one:

- O(n)
- O(log n)
- O(n²)
- O(2
^{n})

The correct answer is: O(n²)

Question 4

Question text

True/False: Dijkstra's algorithm finds the shortest paths in a graph from all vertices to a given vertex.

Select one:

True

False

The correct answer is 'False'.

Question 5

Question text

Which method of traversal does not use stack to hold nodes that are waiting to be processed?

Select one:

- Depth First
- Breadth first
- Back-tracking
- Bounding

The correct answer is: Breadth first

Question 6

Question text

What is the big-o complexity of the green line?

Select one:

- O(n)
- O(log n)
- O(n log n)
- O(2
^{n})

The correct answer is: O(n log n)

Question 7

Question text

______ is the time complexity of an algorithm that operates in exponential time. This means that process times doubles with the addition of each data element.

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(2^{n})

Question 8

Question text

Breadth first search __________.

Select one:

- Scans each incident node along with its children.
- Scans all incident edges before moving to other node.
- Is same as backtracking.
- Scans all the nodes in random order.
- Scans all the nodes in pre-order manner.

The correct answer is: Scans all incident edges before moving to other node.

Question 9

Question text

What is the Big-Oh complexity of the selection sort?

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(n^{2})

Question 10

Question text

What will be the Big-Oh complexity to search a balanced binary tree?

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(log n)

Question 11

Question text

What will be the Big-Oh complexity of a linear search?

Select one:

- O(n)
- O(1)
- O(n²)
- O(2
^{n})

The correct answer is: O(n)

Question 12

Question text

_____ is the time complexity of an algorithm that operates in linear time. The process time changes in the same ratio as the data size.

Select one:

- O(n)
- O(1)
- O(n²)
- O(2
^{n})

^{n}

The correct answer is: O(n)

Question 13

Question text

True/False: O(1) is the time complexity of an algorithm that operates in constant time. The process time required stays constant regardless of the data size.

Select one:

True

False

The correct answer is 'True'.

Question 14

Question text

What is the big-o complexity of the blue line?

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(2^{n})

Question 15

Question text

Suppose you have a directed graph representing all the flights that an airline flies and the flying times for each connection. What algorithm might be used to find the best sequence of connections from one city to another to minimize the overall time of the flight?

Select one:

- Breadth first search.
- Depth first search.
- A cycle-finding algorithm.
- A shortest-path algorithm.

The correct answer is: A shortest-path algorithm.

Question 16

Question text

What will be the Big-Oh complexity to traverse a linked list?

Select one:

- O(n)
- O(1)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(n)

** **

Which of the following is NOT one of the steps used in a Divide-and-conquer algorithm to solve a problem?

Select one:

- Breaking the problem into subproblems that are themselves smaller instances of the same type of problem
- Recursively solving the subproblems
- Appropriately combining the answers of the solved subproblems
- Exhaustively searching every potential path of the problem to identify all solution candidates

The correct answer is: Exhaustively searching every potential path of the problem to identify all solution candidates

Question 2

Question text

True/False: Amortized analysis allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations.

Select one:

True

False

The correct answer is 'True'.

** **

True/False: Is ?

Select one:

True

False

The correct answer is 'False'.

Question 2

Incorrect

Question text

Select one:

- Θ()
- Ω()
- Ο()
- Ο()

The correct answer is: Θ()

Question 3

Incorrect

Question text

What is the Asymptotic complexity of a binary search given the code below and the following recursion equation:

// initially called with low = 0, high = N - 1

BinarySearch_Right(A[0..N-1], value, low,
high) {

// invariants: value >= A[i] for all i < low

value < A[i] for all i
> high

if (high < low)

return low

mid = (low + high) / 2

if
(A[mid] > value)

return BinarySearch_Right(A, value, low, mid-1)

else

return BinarySearch_Right(A, value, mid+1, high)

}

Select one:

The correct answer is:

Question 4

Question text

Given the following algorithm, what is the number of fundamental instructions that this routine will execute if the value of n is 4?

var M = A[ 0 ];

for ( var i = 0; i < n; ++i ) {

if ( A[ i ] >= M ) {

M = A[ i ];

}

}

Select one:

- 4+2n
- 10
- 2n+2

The correct answer is: 4+2n

Question 5

Question text

True/False: A Boolean variable can take on only 1 value.

Select one:

True

False

The correct answer is 'False'.

Question 6

Question text

Which of the following is NOT a property of logarithms?

Select one:

- log(nm) = log n + log m
- log(n/m) = log n - log m

The correct answer is:

Question 7

Question text

True/False: An algorithm is a well-defined sequence of steps used to solve a well-defined problem in finite time.

Select one:

True

False

The correct answer is 'True'.

Question 8

Question text

True/False: The running time of an algorithm is the number of instructions it executes when run on a particular instance.

Select one:

True

False

The correct answer is 'True'.

Question 9

Question text

True/False: An algorithm is a well-defined sequence of steps used to solve a well-defined problem in an infinite number of steps.

Select one:

True

False

The correct answer is 'False'.

Question 10

Question text

True/False: The backtracking algorithm treats the solution space as a graph and follows a path to conclusion to find a solution to a problem. The algorithm may 'backtrack' by reversing up to previous branches in a tree and try all branches to find the solution.

Select one:

True

False

The correct answer is 'True'.

Question 11

Question text

The Backtracking algorithm implements the following search?

Select one:

- Depth First Search
- Sequential search
- Breadth First Search
- Binary Search

The correct answer is: Depth First Search

Given the following algorithm, what is the number of fundamental instructions that this routine will execute if the value of n is 4?

var M = A[ 0 ];

for ( var i = 0; i < n; ++i ) {

if ( A[ i ] >= M ) {

M = A[ i ];

}

}

Select one:

- 4+2n
- 10
- 2n+2

The correct answer is: 4+2n

Question 2

Question text

Suppose you have a directed graph representing all the flights that an airline flies and the flying times for each connection. What algorithm might be used to find the best sequence of connections from one city to another to minimize the overall time of the flight?

Select one:

- Breadth first search.
- Depth first search.
- A cycle-finding algorithm.
- A shortest-path algorithm.

The correct answer is: A shortest-path algorithm.

Question 3

Question text

What is the big-o complexity of the red line?

Select one:

- O(n)
- O(log n)
- O(n²)
- O(1)

The correct answer is: O(1)

Question 4

Question text

What is the big-o complexity of the purple line?

Select one:

- O(n)
- O(log n)
- O(n²)
- O(2
^{n})

The correct answer is: O(n²)

Question 5

Question text

True/False: According to our reading assignments, circuit satisfiability is a good example of a problem that we don't know how to solve in polynomial time.

Select one:

True

False

The correct answer is 'True'.

Question 6

Question text

Breadth first search __________.

Select one:

- Scans each incident node along with its children.
- Scans all incident edges before moving to other node.
- Is same as backtracking.
- Scans all the nodes in random order.
- Scans all the nodes in pre-order manner.

The correct answer is: Scans all incident edges before moving to other node.

Question 7

Question text

What will be the Big-Oh complexity to traverse a linked list?

Select one:

- O(n)
- O(1)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(n)

Question 8

Question text

In the following graph what do the circles represent?

Select one:

- Edges
- Vertices
- Nodes
- Cycles

The correct answer is: Vertices

Question 9

Question text

True/False: A graph with edges that point in such a way that one could follow such directed edges and visit the same vertex again, as is illustrated in the following diagram is a graph that is said to have or be:

Select one:

- Directed
- Cyclic or cycles
- Free tree
- Acyclic

The correct answer is: Cyclic or cycles

Question 10

Question text

True/False: A Boolean variable can take on only 1 value.

Select one:

True

False

The correct answer is 'False'.

Question 11

Question text

Using Prim’s Algorithm, determine the minimum spanning tree of the following graph.

Which edge, written in the format of: (startnode, endnode), is NOT included in the minimum spanning tree?

Please enter your answer in the following format: (#,#)

Answer:

The correct answer is: (1, 8)

Question 12

Question text

Which method of traversal does not use stack to hold nodes that are waiting to be processed?

Select one:

- Depth First
- Breadth first
- Back-tracking
- Bounding

The correct answer is: Breadth first

Question 13

Question text

How many Desktop computers should be built?

Answer:

The correct answer is: 650

Question 14

Question text

True/False: Dynamic Programming reduces asymptotic complexity by eliminating redundant computations.

Select one:

True

False

The correct answer is 'True'.

Question 15

Question text

True/False: In a dynamic programming algorithm, we can use a table to store results of sub-problems and then refer to this table to ensure that we don't recomputed those sub-problems.

Select one:

True

False

The correct answer is 'True'.

Question 16

Question text

Consider: A farmer can plant up to 8 acres of land with wheat and barley. He can earn $5,000 for every acre he plants with wheat and $3,000 for every acre he plants with barley. His use of a necessary pesticide is limited by federal regulations to 10 gallons for his entire 8 acres. Wheat requires 2 gallons of pesticide for every acre planted and barley requires just 1 gallon per acre. Problem: What is the maximum profit he can make? Assumptions: let x = the number of acres of wheat and let y = the number of acres of barley. Which of the following is a valid constraint for this problem?

Select one:

- y <= 8 - 2x
- x <= 0
- x <= 8-x
- y <= 10 - 2x

The correct answer is: y <= 10 - 2x

Question 17

Question text

True/False: In a linear programming problem there can be no more than 3 constraints:

Select one:

True

False

The correct answer is 'False'.

Question 18

Question text

True/False: Let T be a minimum spanning tree of G. Then, for any pair of vertices s and t, the shortest path from s to T is G is the path from s to t in T.

Select one:

True

False

The correct answer is 'False'.

Question 19

Question text

______ is the time complexity of an algorithm that operates in exponential time. This means that process times doubles with the addition of each data element.

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(2^{n})

Question 20

Question text

True/False: O(1) is the time complexity of an algorithm that operates in constant time. The process time required stays constant regardless of the data size.

Select one:

True

False

The correct answer is 'True'.

Question 21

Question text

True/False: Linear programming is used primarily to solve problems of optimization?

Select one:

True

False

The correct answer is 'True'.

Question 22

Question text

Which of the following is NOT one of the main principles of dynamic programming algorithms?

Select one:

- Optimal substructure: optimal solutions to problems are built from optimal solutions to subproblems.
- "Shop around": to determine the best option, try them all and select the best one. Do not employ heuristics.
- Memorization: answers to subproblems are remembered to avoid repeated computation of the same thing.
- Recursion: implemented as a recursive routine to reduce overhead and improve computational efficiency.

The correct answer is: Recursion: implemented as a recursive routine to reduce overhead and improve computational efficiency.

Question 23

Question text

A process that is designed to visit every vertex in a graph is known as a:

Select one:

- Graph traversal
- Graph search
- Binary search
- Enumeration

The correct answer is: Graph traversal

Question 24

Question text

Which of the following is NOT one of the steps used in a Divide-and-conquer algorithm to solve a problem?

Select one:

- Breaking the problem into subproblems that are themselves smaller instances of the same type of problem
- Recursively solving the subproblems
- Appropriately combining the answers of the solved subproblems
- Exhaustively searching every potential path of the problem to identify all solution candidates

The correct answer is: Exhaustively searching every potential path of the problem to identify all solution candidates

Question 25

Question text

True/False: The backtracking algorithm treats the solution space as a graph and follows a path to conclusion to find a solution to a problem. The algorithm may 'backtrack' by reversing up to previous branches in a tree and try all branches to find the solution.

Select one:

True

False

The correct answer is 'True'.

Question 26

Question text

Consider the following figure:

Select one:

- Pivot column
- The Vertex
- Objective Value
- Optimal point

The correct answer is: Pivot column

Question 27

Question text

True/False: In linear programming a constraint must be represented as a inequality.

Select one:

True

False

The correct answer is 'False'.

Question 28

Question text

Linear programming problems can be solved using which of the following:

Select one:

- Simplex method
- Quick method
- Stochastic method
- None of these answers

The correct answer is: Simplex method

Question 29

Question text

True/False: The running time of an algorithm is the number of instructions it executes when run on a particular instance.

Select one:

True

False

The correct answer is 'True'.

Question 30

Question text

What term best describes this graph?

Select one:

- Directed Graph
- Undirected Graph
- Tree
- Directed Acyclic Graph

The correct answer is: Undirected Graph

Question 31

Question text

What is the Asymptotic complexity of a binary search given the code below and the following recursion equation:

// initially called with low = 0, high = N - 1

BinarySearch_Right(A[0..N-1], value, low,
high) {

// invariants: value >= A[i] for all i < low

value < A[i] for all i
> high

if (high < low)

return low

mid = (low + high) / 2

if
(A[mid] > value)

return BinarySearch_Right(A, value, low, mid-1)

else

return BinarySearch_Right(A, value, mid+1, high)

}

Select one:

The correct answer is:

Question 32

Question text

True/False: A reduction is solving problem A using problem B where an algorithm for B exists (for example redefining an optimization problem as a search problem).

Select one:

True

False

The correct answer is 'True'.

True/False: In linear programming, either the constraints or the optimization criteria must be linear functions.

Select one:

True

False

The correct answer is 'False'.

Question 2

Question text

True/False: An algorithm is a well-defined sequence of steps used to solve a well-defined problem in an infinite number of steps.

Select one:

True

False

The correct answer is 'False'.

Question 3

Question text

True/False: Is ?

Select one:

True

False

The correct answer is 'False'.

Question 4

Question text

What will be the Big-Oh complexity to search a balanced binary tree?

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(log n)

Question 5

Question text

Consider the following figure:

Select one:

- The optimal solution
- An infeasible solution
- An Alternate vertex
- None of these answers

The correct answer is: The optimal solution

Question 6

Question text

True/False: Recursive routines cannot be used in Dynamic Programming algorithms?

Select one:

True

False

The correct answer is 'True'.

Question 7

Question text

True/False: Linear programming is an excellent approach for optimization problems where the objective function graphs as a curvilinear line.

Select one:

True

False

The correct answer is 'False'.

Question 8

Question text

_____ is the time complexity of an algorithm that operates in linear time. The process time changes in the same ratio as the data size.

Select one:

- O(n)
- O(1)
- O(n²)
- O(2
^{n})

^{n}

The correct answer is: O(n)

Question 9

Question text

What term best describes this graph?

Select one:

- Directed Graph
- Undirected Graph
- Tree
- Directed Acyclic Graph

The correct answer is: Undirected Graph

Question 10

Question text

True/False: NP is the set of decision problems that can be solved in polynomial time.

Select one:

True

False

The correct answer is 'False'.

Question 11

Question text

According to the Cook-Levin Theorem, Circuit satisfiability is:

Select one:

- NP-Complete
- NP-Hard
- NP-Easy
- P

The correct answer is: NP-Complete

Question 12

Question text

The Backtracking algorithm implements the following search?

Select one:

- Depth First Search
- Sequential search
- Breadth First Search
- Binary Search

The correct answer is: Depth First Search

Question 13

Question text

Using Prim’s Algorithm, determine the minimum spanning tree of the following graph.

What is the weight of the minimum spanning tree (the sum of the weights of the edges included in the minimum spanning tree)?

Please enter a numerical answer only; do not enter any letters or words.

Answer:

The correct answer is: 22

Question 14

Question text

Select one:

- Θ()
- Ω()
- Ο()
- Ο()

The correct answer is: Θ()

Question 15

Question text

What is the Big-Oh complexity of the selection sort?

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(n^{2})

Question 16

Question text

True/False: A graph is a set of vertices and a set of edges such that each edge is a connection between a pair of vertices.

Select one:

True

False

The correct answer is 'True'.

Question 17

Question text

Which of the following is NOT a property of logarithms?

Select one:

- log(nm) = log n + log m
- log(n/m) = log n - log m

The correct answer is:

Question 18

Question text

How many servers should be built?

Answer:

The correct answer is: 150

Question 19

Question text

In a linear programming problem, a statement such as max x1 + 6x2 represents:

Select one:

- A constraint function
- The Objective function
- The maximization function
- The feasible function

The correct answer is: The Objective function

Question 20

Question text

True/False: A graph with numbers or letters on the vertices is called a labeled graph.

Select one:

True

False

The correct answer is 'True'.

Question 21

Question text

True/False: Amortized analysis allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations.

Select one:

True

False

The correct answer is 'True'.

Question 22

Question text

If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a time, in what order will they be removed?

Select one:

- ABCD
- ABDC
- DCAB
- DCBA
- ACDB

The correct answer is: DCBA

Question 23

Question text

True/False: A graph with edges that have no directional indication as in the following diagram is called a uni-directed graph.

Select one:

True

False

The correct answer is 'False'.

Question 24

Question text

Consider the following figure. What does the region that is shaded represent?

Select one:

- The Feasible region
- The Infeasible solutions
- The optimal solution
- The Constraint Space

The correct answer is: The Feasible region

Question 25

Question text

True/False: Dynamic programming is a variation of the linear programming model in that it breaks the problem down into smaller problems that are solved using the simplex method?

Select one:

True

False

The correct answer is 'False'.

Question 26

Question text

What is the big-o complexity of the blue line?

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(2^{n})

Question 27

Question text

What is the big-o complexity of the green line?

Select one:

- O(n)
- O(log n)
- O(n log n)
- O(2
^{n})

The correct answer is: O(n log n)

Question 28

Question text

In a linear programming problem assuming the Simplex Method the following is known as:

Select one:

- The Constraints
- The Solution definition
- The Problem definition
- The Tableau

The correct answer is: The Tableau

Question 29

Question text

What term best describes this graph?

Select one:

- Directed Graph
- Undirected Graph
- Tree
- Directed Acyclic Graph

The correct answer is: Directed Acyclic Graph

Question 30

Question text

True/False: Dynamic programming is less complex asymptotically but is substantially more complex from a programming perspective?

Select one:

True

False

The correct answer is 'False'.

Question 31

Question text

What will be the Big-Oh complexity of a linear search?

Select one:

- O(n)
- O(1)
- O(n²)
- O(2
^{n})

The correct answer is: O(n)

Question 32

Question text

True/False: Dijkstra's algorithm finds the shortest paths in a graph from all vertices to a given vertex.

Select one:

True

False

The correct answer is 'False'.

Which of the following is NOT a property of logarithms?

Select one:

- log(nm) = log n + log m
- log(n/m) = log n - log m

The correct answer is:

Question 2

Question text

True/False: O(1) is the time complexity of an algorithm that operates in constant time. The process time required stays constant regardless of the data size.

Select one:

True

False

The correct answer is 'True'.

Question 3

Question text

True/False: The Simplex method is important for computer programming, as the need for processing power is significantly lower when using it as opposed to other methods.

Select one:

True

False

The correct answer is 'True'.

Question 4

Question text

_____ is the time complexity of an algorithm that operates in linear time. The process time changes in the same ratio as the data size.

Select one:

- O(n)
- O(1)
- O(n²)
- O(2
^{n})

^{n}

The correct answer is: O(n)

Question 5

Question text

Which of the following is NOT one of the main principles of dynamic programming algorithms?

Select one:

- Optimal substructure: optimal solutions to problems are built from optimal solutions to subproblems.
- "Shop around": to determine the best option, try them all and select the best one. Do not employ heuristics.
- Memorization: answers to subproblems are remembered to avoid repeated computation of the same thing.
- Recursion: implemented as a recursive routine to reduce overhead and improve computational efficiency.

The correct answer is: Recursion: implemented as a recursive routine to reduce overhead and improve computational efficiency.

Question 6

Question text

True/False: Dijkstra's algorithm finds the shortest paths in a graph from all vertices to a given vertex.

Select one:

True

False

The correct answer is 'False'.

Question 7

Question text

True/False: The backtracking algorithm treats the solution space as a graph and follows a path to conclusion to find a solution to a problem. The algorithm may 'backtrack' by reversing up to previous branches in a tree and try all branches to find the solution.

Select one:

True

False

The correct answer is 'True'.

Question 8

Question text

What is the Asymptotic complexity of a binary search given the code below and the following recursion equation:

// initially called with low = 0, high = N - 1

BinarySearch_Right(A[0..N-1], value, low,
high) {

// invariants: value >= A[i] for all i < low

value < A[i] for all i
> high

if (high < low)

return low

mid = (low + high) / 2

if
(A[mid] > value)

return BinarySearch_Right(A, value, low, mid-1)

else

return BinarySearch_Right(A, value, mid+1, high)

}

Select one:

The correct answer is:

Question 9

Question text

True/False: Is ?

Select one:

True

False

The correct answer is 'False'.

Question 10

Question text

Consider the following figure. What does the region that is shaded represent?

Select one:

- The Feasible region
- The Infeasible solutions
- The optimal solution
- The Constraint Space

The correct answer is: The Feasible region

Question 11

Question text

Which method of traversal does not use stack to hold nodes that are waiting to be processed?

Select one:

- Depth First
- Breadth first
- Back-tracking
- Bounding

The correct answer is: Breadth first

Question 12

Question text

True/False: Dynamic programming is a variation of the linear programming model in that it breaks the problem down into smaller problems that are solved using the simplex method?

Select one:

True

False

The correct answer is 'False'.

Question 13

Question text

What will be the Big-Oh complexity of a linear search?

Select one:

- O(n)
- O(1)
- O(n²)
- O(2
^{n})

The correct answer is: O(n)

Question 14

Question text

How much Revenue (money in dollars received by selling the desktops and servers) will be generated?

Answer:

The correct answer is: $878,750.00

Question 15

Question text

What will be the Big-Oh complexity to traverse a linked list?

Select one:

- O(n)
- O(1)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(n)

Question 16

Question text

True/False: Linear programming is an excellent approach for optimization problems where the objective function graphs as a curvilinear line.

Select one:

True

False

The correct answer is 'False'.

Question 17

Question text

True/False: Amortized analysis allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations.

Select one:

True

False

The correct answer is 'True'.

Question 18

Question text

Breadth first search __________.

Select one:

- Scans each incident node along with its children.
- Scans all incident edges before moving to other node.
- Is same as backtracking.
- Scans all the nodes in random order.
- Scans all the nodes in pre-order manner.

The correct answer is: Scans all incident edges before moving to other node.

Question 19

Question text

Consider the following figure:

Select one:

- Pivot column
- The Vertex
- Objective Value
- Optimal point

The correct answer is: Pivot column

Question 20

Question text

Using Prim’s Algorithm, determine the minimum spanning tree of the following graph.

What is the weight of the minimum spanning tree (the sum of the weights of the edges included in the minimum spanning tree)?

Please enter a numerical answer only; do not enter any letters or words.

Answer:

The correct answer is: 22

Question 21

Question text

Using Prim’s Algorithm, determine the minimum spanning tree of the following graph. When you have identified the MST, add together the path weights and submit as your answer.

Please enter a numerical answer only; do not enter any letters or words.

Answer:

The correct answer is: 12

Question 22

Question text

In the following graph what do the circles represent?

Select one:

- Edges
- Vertices
- Nodes
- Cycles

The correct answer is: Vertices

Question 23

Question text

True/False: Dynamic programming is less complex asymptotically but is substantially more complex from a programming perspective?

Select one:

True

False

The correct answer is 'False'.

Question 24

Question text

True/False: Let T be a minimum spanning tree of G. Then, for any pair of vertices s and t, the shortest path from s to T is G is the path from s to t in T.

Select one:

True

False

The correct answer is 'False'.

Question 25

Question text

True/False: Linear programming is used primarily to solve problems of optimization?

Select one:

True

False

The correct answer is 'True'.

Question 26

Question text

What is the big-o complexity of the green line?

Select one:

- O(n)
- O(log n)
- O(n log n)
- O(2
^{n})

The correct answer is: O(n log n)

Question 27

Question text

True/False: A graph is a set of vertices and a set of edges such that each edge is a connection between a pair of vertices.

Select one:

True

False

The correct answer is 'True'.

Question 28

Question text

True/False: A graph with edges that point in such a way that one could follow such directed edges and visit the same vertex again, as is illustrated in the following diagram is a graph that is said to have or be:

Select one:

- Directed
- Cyclic or cycles
- Free tree
- Acyclic

The correct answer is: Cyclic or cycles

Question 29

Question text

True/False: A graph with numbers or letters on the vertices is called a labeled graph.

Select one:

True

False

The correct answer is 'True'.

Question 30

Question text

According to the Cook-Levin Theorem, Circuit satisfiability is:

Select one:

- NP-Complete
- NP-Hard
- NP-Easy
- P

The correct answer is: NP-Complete

Question 31

Question text

True/False: NP is the set of decision problems that can be solved in polynomial time.

Select one:

True

False

The correct answer is 'False'.

Question 32

Question text

True/False: An algorithm is a well-defined sequence of steps used to solve a well-defined problem in finite time.

Select one:

True

False

The correct answer is 'True'.

True/False: In a dynamic programming algorithm, we can use a table to store results of sub-problems and then refer to this table to ensure that we don't recomputed those sub-problems.

Select one:

True

False

The correct answer is 'True'.

Question 2

Question text

How many Desktop computers should be built?

Answer:

The correct answer is: 650

Question 3

Question text

True/False: A reduction is solving problem A using problem B where an algorithm for B exists (for example redefining an optimization problem as a search problem).

Select one:

True

False

The correct answer is 'True'.

Question 4

Question text

What will be the Big-Oh complexity to search a balanced binary tree?

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(log n)

Question 5

Question text

What term best describes this graph?

Select one:

- Directed Graph
- Undirected Graph
- Tree
- Directed Acyclic Graph

The correct answer is: Directed Acyclic Graph

Question 6

Question text

True/False: The running time of an algorithm is the number of instructions it executes when run on a particular instance.

Select one:

True

False

The correct answer is 'True'.

Question 7

Question text

What is the Big-Oh complexity of the selection sort?

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(n^{2})

Question 8

Question text

True/False: A graph with edges that have no directional indication as in the following diagram is called a uni-directed graph.

Select one:

True

False

The correct answer is 'False'.

Question 9

Question text

True/False: Recursive routines cannot be used in Dynamic Programming algorithms?

Select one:

True

False

The correct answer is 'True'.

Question 10

Question text

Suppose you have a directed graph representing all the flights that an airline flies and the flying times for each connection. What algorithm might be used to find the best sequence of connections from one city to another to minimize the overall time of the flight?

Select one:

- Breadth first search.
- Depth first search.
- A cycle-finding algorithm.
- A shortest-path algorithm.

The correct answer is: A shortest-path algorithm.

Question 11

Question text

Select one:

- Θ()
- Ω()
- Ο()
- Ο()

The correct answer is: Θ()

Question 12

Question text

A process that is designed to visit every vertex in a graph is known as a:

Select one:

- Graph traversal
- Graph search
- Binary search
- Enumeration

The correct answer is: Graph traversal

Question 13

Question text

True/False: A graph is a set of vertices and a set of edges such that each edge is a connection between a pair of vertices.

Select one:

True

False

The correct answer is 'True'.

Question 14

Question text

What is the big-o complexity of the blue line?

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(2^{n})

Question 15

Question text

True/False: Dynamic Programming reduces asymptotic complexity by eliminating redundant computations.

Select one:

True

False

The correct answer is 'True'.

Question 16

Question text

In a linear programming problem, a statement such as max x1 + 6x2 represents:

Select one:

- A constraint function
- The Objective function
- The maximization function
- The feasible function

The correct answer is: The Objective function

Question 17

Question text

Linear programming problems can be solved using which of the following:

Select one:

- Simplex method
- Quick method
- Stochastic method
- None of these answers

The correct answer is: Simplex method

Question 18

Question text

Consider the following figure:

Select one:

- The optimal solution
- An infeasible solution
- An Alternate vertex
- None of these answers

The correct answer is: The optimal solution

Question 19

Question text

What is the big-o complexity of the red line?

Select one:

- O(n)
- O(log n)
- O(n²)
- O(1)

The correct answer is: O(1)

Question 20

Question text

True/False: An algorithm is a well-defined sequence of steps used to solve a well-defined problem in finite time.

Select one:

True

False

The correct answer is 'True'.

Question 21

Question text

In a linear programming problem assuming the Simplex Method the following is known as:

Select one:

- The Constraints
- The Solution definition
- The Problem definition
- The Tableau

The correct answer is: The Tableau

Question 22

Question text

What is the big-o complexity of the purple line?

Select one:

- O(n)
- O(log n)
- O(n²)
- O(2
^{n})

The correct answer is: O(n²)

Question 23

Question text

True/False: In linear programming a constraint must be represented as a inequality.

Select one:

True

False

The correct answer is 'False'.

Question 24

Question text

True/False: A graph with numbers or letters on the vertices is called a labeled graph.

Select one:

True

False

The correct answer is 'True'.

Question 25

Question text

Which of the following is NOT one of the steps used in a Divide-and-conquer algorithm to solve a problem?

Select one:

- Breaking the problem into subproblems that are themselves smaller instances of the same type of problem
- Recursively solving the subproblems
- Appropriately combining the answers of the solved subproblems
- Exhaustively searching every potential path of the problem to identify all solution candidates

The correct answer is: Exhaustively searching every potential path of the problem to identify all solution candidates

Question 26

Question text

______ is the time complexity of an algorithm that operates in exponential time. This means that process times doubles with the addition of each data element.

Select one:

- O(n)
- O(log n)
- O(n
^{2}) - O(2
^{n})

The correct answer is: O(2^{n})

Question 27

Question text

If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a time, in what order will they be removed?

Select one:

- ABCD
- ABDC
- DCAB
- DCBA
- ACDB

The correct answer is: DCBA

Question 28

Question text

The Backtracking algorithm implements the following search?

Select one:

- Depth First Search
- Sequential search
- Breadth First Search
- Binary Search

The correct answer is: Depth First Search

Question 29

Question text

How much Revenue (money in dollars received by selling the desktops and servers) will be generated?

Answer:

The correct answer is: $878,750.00

Question 30

Question text

Given the following algorithm, what is the number of fundamental instructions that this routine will execute if the value of n is 4?

var M = A[ 0 ];

for ( var i = 0; i < n; ++i ) {

if ( A[ i ] >= M ) {

M = A[ i ];

}

}

Select one:

- 4+2n
- 10
- 2n+2

The correct answer is: 4+2n

Question 31

Question text

True/False: According to our reading assignments, circuit satisfiability is a good example of a problem that we don't know how to solve in polynomial time.

Select one:

True

False

The correct answer is 'True'.

Question 32

Question text

Using Prim’s Algorithm, determine the minimum spanning tree of the following graph. When you have identified the MST, add together the path weights and submit as your answer.

Please enter a numerical answer only; do not enter any letters or words.

Answer:

The correct answer is: 12