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
ly 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 )
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 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.
Secto 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
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 one more
than the number of internal nodes”
Select one:
True
False
The correct answer`FD�U `FD�U �}�
�U ��
�U �FD�U �FD�U @ �FD�U s 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 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
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 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
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 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
ly 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
new0
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 f 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
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
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
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
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
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
The correct answer is: Queue
Question 95
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 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 poi0ause 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 lees 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. {x | x is all
positive integers}
d. {1,2,3,4,5,6}
The correct answer is:
{1,2,3,4,5,6}
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
Question 105
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 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 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 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
ly 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 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)
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 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,0e 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
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;
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
44
For the following code fragment, select the option that represents the most
appropriate asymptotic analysis:
// Recursive Fibonacci generator
static
l`FD�U `FD�U �}�
�U ��
�U �FD�U �FD�U @ �FD�U -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 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: Inserting a new element into
the head of the list.
Question 49
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
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;Θ (
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
structure:
Select one:
a. Queue
b. Stack
c. List
d.
Array
The correct 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 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; eet
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
d. a Merge
Operation
The correct answer is: Union / Find
Question
85
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 i`FD�U `FD�U �}�
�U ��
�U �FD�U �FD�U @ �FD�U ted
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. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4
The correct answer is: Choice 3
Question
87
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 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 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
lstion 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
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
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 solveHan risks-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])
le 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:
// 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
Top of
Form
A list is
Select one:
a. An ADT for storing and retrieving data
b. A
tree data structure
c. Finite or`FD�U `FD�U �}�
�U ��
�U �FD�U �FD�U @ �FD�U 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 correct answer
is 'False'.
Question 3
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 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 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
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
ly 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 ged
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
The correct answer is: It flushes or writes the block out to the
disk
Question 2
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
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: (only 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
s 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 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
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 `FD�U `FD�U �}�
�U ��
�U �FD�U �FD�U @ �FD�U match search
c. A Dictionary search
d. bit map vector search
The correct answer is: A Dictionary
search
Question 4
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 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:
Select one:
a. Secondary
Key
b. Primary index
c. Primary key
d. Index key
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
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 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
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. Composited 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
The correct answer is: Buffer cache access methods
Question
42
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
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:
S`FD�U `FD�U �}�
�U ��
�U �FD�U �FD�U @ �FD�U 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 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
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 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 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 rees 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: is: Choice 2
Question
75
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 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)
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:
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 85
ly 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-`FD�U `FD�U �}�
�U ��
�U �FD�U �FD�U @ �FD�U
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 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
Question 94
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
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 allocersal 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 c0urn 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
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
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:
Selection sort
Question 19
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 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 (`FD�U `FD�U �}�
�U ��
�U �FD�U �FD�U @ �FD�U ith 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
Question
23
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 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 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
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 a 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 (Θ 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.
The correct answer is: Holds the list nodes that are no longer in
use.
Question 56
Which of the following is NOT true for Linked Lists
structures (please select 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
ly 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: Preorder traversal
Question 65
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
66
`FD�U `FD�U �}�
�U ��
�U �FD�U �FD�U @ �FD�U g 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
Get Free Quote!
300 Experts Online