Comparative Programming Languages Quiz

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 )
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 8


A compound computed search that combines a binary search to get close to the required record and then uses sequential search to find the item is referred to as a/an:
Select one:
a. Zipf search
b. An Exact match search
c. A Dictionary search
d. bit map vector search


The correct answer is: A Dictionary search

Question 9


The process for visiting all of the nodes of a binary tree in some order is called a traversal.
Select one:
True
False


The correct answer is 'True'.

Question 10


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
function ( n ) {
sum2 = 0;
for (k=1; k<=n; k*=2)
for (j=1; j<=k; j++)
sum2++;
}
Choice 1. O( 2n )
Choice 2. Θ ( n )
Choice 3. Θ( n log n )
Choice 4. Ω( n2 )
(NOTE: code fragment is not intended to be functioning code)

Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 2

Question 11


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


The correct answer is 'True'.

Question 12


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


The correct answer is 'False'.

Question 13


Select the answer that best defines Huffman Coding:
Select one:
a. A set of coding rules that is typically used for compression
b. A fixed length coding scheme for character representation
c. A tree structure that trades off space and time requirements to provide a more efficient priority queue
d. An approach of assigning codes to characters such that the frequency length of the code depends upon the relative frequency of the corresponding character in use


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

Question 14


A tree data structure whose shape obeys the following definition,
o A node contains one or two keys
o Every internal node has either 2 children if it contains 1 key or 3 children if it contains two keys
o All leaves are at the same level in the tree
Is called a/an:
Select one:
a. B*-Tree
b. BST
c. B+-Tree
d. 2-3 tree


The correct answer is: 2-3 tree

Question 15


Data is stored within the disk drive on the: (select the best answer)
Select one:
a. Spindle
b. Platter
c. Cylinder
d. Sector


The correct answer is: Platter

Question 16


For the following code fragment, select the most appropriate asymptotic analysis:
// Towers of Hanoi
static void solveHanoi(int disks, char fromPole, char toPole, char withPole) {
if (disks >= 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 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 is 'False'.

Question 18


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


The correct answer is 'False'.

Question 19


A list that organizes the order 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
Select one:
True
False


The correct answer is 'False'.

Question 48


A sort algorithm that uses two nested loops with the inner loop moving through the array from bottom to top is called the:
Select one:
a. Insertion sort
b. Bubble sort
c. Inversion sort
d. Selection sort


The correct answer is: Bubble sort

Question 49


Which of the following is not a characteristic of an algorithm?
Select one:
a. It must be correct
b. It must be composed of concrete steps
c. It can 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 new NoSuchElementException();
}
Option 1. O( 1 )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


Explanation: Here n = a.length, and T(n) = 1.
The correct answer is: Option 1

Question 59


An ADT is:
Select one:
a. A type together with a collection of operations to manipulate the type
b. An implementation of a flyweight design pattern
c. The realization of a data type as a software component
d. An implementation in java of a class for a data type


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

Question 60


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 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 a K-ary tree.
Select one:
True
False


The correct answer is 'True'.

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


The correct answer is 'True'.

Question 92


A leaf is any node that:
Select one:
a. Has one child
b. Is an internal node with no ancestors
c. Is any node with two empty children
d. Is the ancestor of the root node


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

Question 93


Which of the following is NOT true for Linked Lists structures (please select the best choice):
Choice 1. Insertion and deletion are ( 1 ).
Choice 2. Direct access of an item in the list structure is ( n ).
Choice 3. Space grows with number of elements.
Choice 4. There is no overhead associated with elements in the list structure
Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 4

Question 94


Enqueue and Dequeue are notations associated with which data structure:
Select one:
a. Queue
b. Stack
c. List
d. Array


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 pointers are stored
d. It uses dynamic nodes


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

Question 100


The processing time or cost of a sort is defined by the number of comparisons and exchanges that must be made during processing. What is the average cost of the heapsort?:
Option 1. O( n log n )
Option 2. Ω( n2 )
Option 3. O( n2 )
Option 4. Θ( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 1

Question 101


A significant benefit to using an index to hold and sort keys to a file is:
Select one:
a. Smaller keys require less I/O
b. The entire sort can always be completed in memory
c. The head of the disk drive does not need to move
d. There is no seek time added to the latency of I/O operations


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

Question 102


If A={1, 2, 3, 4} and B={4, 5, 6}, find A∪ B .
Select one:
a. {1,2,3,4,4,5,6}
b. {4}
c. {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


The correct answer is: 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 3
d. Option 4


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

Question 32


A leaf is any node that:
Select one:
a. Has one child
b. Is an internal node with no ancestors
c. Is any node with two empty children
d. Is the ancestor of the root node


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

Question 33


For the following code fragment, select the most appropriate asymptotic analysis:
// Towers of Hanoi
static void solveHanoi(int disks, char fromPole, char toPole, char withPole) {
if (disks >= 1) {
solveHanoi(disks-1, fromPole, withPole, toPole);
moveDisk(fromPole, toPole);
solveHanoi(disks-1, withPole, toPole, fromPole);
}
}
static void moveDisk(char fromPole, char toPole) {
moves++;
}
Option 1. O( n )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 2

Question 34


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
function ( n ) {
sum1 = 0;
for (k=1; k<=n; k*=2)
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,4,4,5,6}
b. {4}
c. {x | x is all positive integers}
d. {1,2,3,4,5,6}


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

Question 39


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


The correct answer is 'True'.

Question 40


A compound computed search that combines a binary search to get close to the required record and then uses sequential search to find the item is referred to as a/an:
Select one:
a. Zipf search
b. An Exact match search
c. A Dictionary search
d. bit map vector search


The correct answer is: A Dictionary search

Question 41


The process of storing records in the order that they were added to a file is called:
Select one:
a. Entry-sequenced file
b. Binary Sequenced file
c. LIFO file format
d. Tombstone approach


The correct answer is: Entry-sequenced file

Question 42


Each record of a database normally has a unique identifier called the:
Select one:
a. Secondary Key
b. Primary index
c. Primary key
d. Index key


The correct answer is: Primary key

Question 43


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
static int function ( n ) {
for (k=0; k<n; k++)
A[k] = k;
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 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 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; k<=n; k*=2)
for (j=1; j<=k; j++)
sum2++;
}
Choice 1. O( 2n )
Choice 2. Θ ( n )
Choice 3. Θ( n log n )
Choice 4. Ω( n2 )
(NOTE: code fragment is not intended to be functioning code)

Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 2

Question 73


For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
if (a.length > 0) {
return a[a.length - 1];
} else {
throw new NoSuchElementException();
}
Option 1. O( 1 )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


Explanation: Here n = a.length, and T(n) = 1.
The correct answer is: Option 1

Question 74


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


The correct answer is 'False'.

Question 75


The process of associating a key with the location of a corresponding data record is called folding.
Select one:
True
False


The correct answer is 'False'.

Question 76


An ADT is:
Select one:
a. A type together with a collection of operations to manipulate the type
b. An implementation of a flyweight design pattern
c. The realization of a data type as a software component
d. An implementation in java of a class for a data type


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

Question 77


Enqueue and Dequeue are notations associated with which data 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 writes the block out to the disk
c. Refreshes the data by re-reading the block
d. It cleans the cache by flushing all data from the cache


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

Question 81


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

Select one:
a. Preorder Traversal
b. Postorder Traversal
c. Inorder Traversal
d. Outoforder Traversal


The correct answer is: Inorder Traversal

Question 82


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
/** @return The position of an element in sorted array A with value k. If k is not in A,return A.length. */
static int binary(int[] A, int k) {
int l = -1; // Set l and r
int r = A.length; // beyond array bounds
while (l+1 != r) { // Stop when l, r meet
int i = (l+r)/2; // Check middle
if (k < A[i]) r = i; // In left half
if (k == A[i]) return i; // Found it
if (k > A[i]) l = i; // In right half
}
return A.length; // Search value not in A
}
Choice 1. Θ ( n )
Choice 2. O( 2n )
Choice 3. O( log n )
Choice 4. Ω( n2 )
(NOTE: code fragment is not intended to be functioning code)

Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 3

Question 83


In linked lists there are no NULL links in:
Select one:
a. Single linked list
b. Linear doubly linked list
c. Circular linked list
d. None of these


The correct answer is: Circular linked list

Question 84


The process of determining if two objects are in the same set and then merging those sets is called:
Select one:
a. a Union Operation
b. Union / Find
c. a Weighted Union
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 is: It specifies the point where the array will be subdivided into partitions and each partition then sorted

Question 86


When big-Oh and  coincide, we indicate this by using (select the best answer):
1. Big Oh (O)
2. Big Omega (Ω)
3. Big Theta (Θ)
4. Exponential growth
Select one:
a. 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 proof
d. Proof by consensus


The correct answer is: Proof by consensus

Question 9

Which of the following is not a characteristic of an algorithm?
Select one:
a. It must be correct
b. It must be composed of concrete steps
c. It can have no ambiguity
d. It must be composed of an infinite number of steps.


The correct answer is: It must be composed of an infinite number of steps
The upper bound for the growth of the Algorithms running time is represented by:
Select one:
a. Big Oh (O)
b. Big Omega (Ω)
c. Big Theta (Θ)
d. Exponential growth


The correct answer is: Big Oh (O)

Question 2

Asymptotic Algorithm Analysis is primarily concerned with:
Select one:
a. The size of the constant in the algorithm running time equation
b. The speed of the computing running the algorithm
c. The speed of the compiler
d. The growth rate demonstrated in the algorithm running time equation


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

Question 3

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


The correct answer is 'True'.

Question 4

For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
Option 1. O( n )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 1

Question 5

For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
for (int i = 1; i <= n; i *= 2) {
for (int j = 0; j < n; j++) {
count++;
}
}
Option 1. O( 1 )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


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 solveHanoi(int disks, char fromPole, char toPole, char withPole) {
if (disks >= 1) {
solveHanoi(disks-1, fromPole, withPole, toPole);
moveDisk(fromPole, toPole);
solveHanoi(disks-1, withPole, toPole, fromPole);
}
}
static void moveDisk(char fromPole, char toPole) {
moves++;
}
Option 1. O( n )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 2

Question 8

For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
public static int binarySearch(int[] a, int key) {
int left = 0;
int right = a.length-1;
while (left <= right) {
int mid = left + (right-left)/2;
if (key < a[mid]) right = mid-1;
else if (key > a[mid]) left = mid+1;
else return mid;
}
//not found
return -1;
}
Option 1. Ω( 1 ), O( log n )
Option 2. Ω( n ), O( 2n )
Option 3. Θ( n log n )
Option 4. Θ( log n )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 1

Question 9

For the following code fragment, select option that represents the most appropriate asymptotic analysis:
for (i=0; i<n; i++) {
//
// Search in array a for smallest element starting at i to n-1
//
minIndex = findSmallestElement(a, i, n-1)
a[i] = a[minIndex];
}
findSmallestElement( int a[], int i, int n ) {
int largest = a[i];
while(i<n) {
if(a[i] >a[largest])
largest = i;
i++;
}
return(largest);
}
Option 1. O( n )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


index-of-smallest element in a[i..j] takes j-i+1 operations
• n + (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
• this is n2
The correct answer is: Option 4

Question 10

For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
// 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 ordered sequence of data items
d. A collection of operations to implement an ADT


The correct answer is: Finite ordered sequence of data items

Question 2

A list is said to be empty when all of its elements have a zero (0) value
Select one:
True
False


The 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 to be stable


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

Question 5

A sort where the list is divided into halves, the halves sorted and these two halves are merged is called:
Select one:
a. Mergesort
b. Binary sort
c. Quicksort
d. Heapsort


The correct answer is: Mergesort

Question 6

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


The correct answer is 'False'.

Question 7

What is the role of the pivot in a quicksort algorithm?
Select one:
a. It identifies the maxkey value
b. It specifies the point where the array will be subdivided into partitions and each partition then sorted
c. It defines the sequence for merging in the sort
d. It indicates the index of the current record being compared


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

Question 8

A sorting algorithm that assigns records to bins and then relies on some other sorting technique to sort the records within each bin called:
Select one:
a. Radix Sort
b. Quicksort
c. Hash sort
d. Bucket sort


The correct answer is: Bucket sort

Question 9

The processing time or cost of a sort is defined by the number of comparisons and exchanges that must be made during processing. What is the average cost of the heapsort?:
Option 1. O( n log n )
Option 2. Ω( n2 )
Option 3. O( n2 )
Option 4. Θ( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 1

Question 10

The quicksort is typically slower than the heapsort by a constant factor.
Select one:
True
False


The correct answer is 'False'.
Bottom of Form
Setting the dirty bit causes what action to be performed on a block: (select the best answer)
Select one:
a. It is deleted because it is no longer consistent
b. It flushes or writes the block out to the disk
c. Refreshes the data by re-reading the block
d. It cleans the cache by flushing all data from the cache


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: (select the best answer)
Select one:
a. Space that is left empty because records do not fit evenly into a sector
b. Space allocated to a file that is not physically adjacent on the disk drive
c. Space that is left empty because records do not fit evenly into a sector or Space allocated to a file that is not physically adjacent
d. None of the options


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

Question 5

Data is stored within the disk drive on the: (select the best answer)
Select one:
a. Spindle
b. Platter
c. Cylinder
d. Sector


The correct answer is: Platter

Question 6


The process of storing blocks of data in main memory after reading from disk is referred to as:
Select one:
a. Buffering
b. Hashing
c. Pooling
d. Indexing


The correct answer is: Buffering

Question 7

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


The correct answer is 'False'.

Question 8

Secondary storage is characterized by the following:
Select one:
a. It is persistent
b. It is faster than primary storage
c. It is volatile
d. It is more expensive than primary storage


The correct answer is: It is persistent

Question 9


An algorithm that breaks a file to be sorted in smaller files called runs which are sorted and eventually put back together resulting in a sorted file is called:
Select one:
a. Quicksort algorithm
b. Replacement sort algorithm
c. An indexed key sort algorithm
d. Mergesort algorithm


The correct answer is: Mergesort algorithm

Question 10


A significant benefit to using an index to hold and sort keys to a file is:
Select one:
a. Smaller keys require less I/O
b. The entire sort can always be completed in memory
c. The head of the disk drive does not need to move
d. There is no seek time added to the latency of I/O operations


The correct answer is: Smaller keys require less I/O
Top of Form
Which of the following is not one of the general approaches to search algorithms:
Select one:
a. Buffer cache 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 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 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


The correct answer is 'True'.

Question 25


Which of the following is not a characteristic of an algorithm?
Select one:
a. It must be correct
b. It must be composed of concrete steps
c. It can have no ambiguity
d. It must be composed of an infinite number of steps.


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

Question 26


For the following code fragment, select the most appropriate asymptotic analysis:
// Towers of Hanoi
static void solveHanoi(int disks, char fromPole, char toPole, char withPole) {
if (disks >= 1) {
solveHanoi(disks-1, fromPole, withPole, toPole);
moveDisk(fromPole, toPole);
solveHanoi(disks-1, withPole, toPole, fromPole);
}
}
static void moveDisk(char fromPole, char toPole) {
moves++;
}
Option 1. O( n )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 2

Question 27


For the following code fragment, select the option which represents the most appropriate asymptotic analysis:
static int function ( n ) {
sum = 0;
for (i=1; i<=n; i++)
sum += n;
return sum;
}
Option 1. Ω( n2 )
Option 2. Θ ( n )
Option 3. O( log n )
Option 4. O( 2n )
(NOTE: code fragment is not intended to be functioning code)


Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 2

Question 28


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


The correct answer is 'False'.

Question 29


A technique that allows a programmer to use more main memory than exists in the computer is called: (select the best answer)
Select one:
a. Buffer cache
b. Random access memory
c. Secondary storage
d. Virtual memory


The correct answer is: Virtual memory

Question 30


A sort that features a limit of n-1 of record swaps is called:
Select one:
a. Insertion sort
b. Bubble sort
c. Inversion sort
d. Selection sort


The correct answer is: Selection sort

Question 31


A traversal that visits each node before visiting its children is called:
Select one:
a. Preorder traversal
b. Postorder traversal
c. Inorder Traversal
d. Outoforder Traversal


The correct answer is: Preorder traversal

Question 32


A list 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 33


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


The correct answer is 'True'.

Question 34


The process of determining if two objects are in the same set and then merging those sets is called:
Select one:
a. a Union Operation
b. Union / Find
c. a Weighted Union
d. a Merge Operation


The correct answer is: Union / Find

Question 35


A sort algorithm that uses two nested loops with the inner loop moving through the array from bottom to top is called the:
Select one:
a. Insertion sort
b. Bubble sort
c. Inversion sort
d. Selection sort


The correct answer is: Bubble sort

Question 36


Which of the following is NOT one of the design patterns outlined in our text.
Select one:
a. Flyweight
b. Visitor
c. Composite
d. Synergy


The correct answer is: Synergy

Question 37


Push and Pop are notations associated with which data structure:
Select one:
a. Queue
b. Stack
c. List
d. Array


The correct answer is: Stack

Question 38


The process of associating a key with the location of a corresponding data record is called folding.
Select one:
True
False


The correct answer is 'False'.

Question 39


For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
// Recursive Fibonacci generator
static long fibr(int n) {
if ((n == 1) || (n == 2)) return 1; // Base case
return fibr(n-1) + fibr(n-2); // Recursive call
}
Option 1. O( n )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 2

Question 40


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
static int function ( n ) {
for (k=0; k<n; k++)
A[k] = k;
return A[k];
}
Choice 1. Θ ( n log n )
Choice 2. O( 2n )
Choice 3. O( n )
Choice 4. Ω( n2 )
(NOTE: code fragment is not intended to be functioning code)



Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 3

Question 41


Which of the following is not one of the general approaches to search algorithms:
Select one:
a. Buffer cache access methods
b. Sequential and list methods
c. Direct access by key value (hashing)
d. Tree indexing methods


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:

Select one:
a. 3
b. 2
c. 4
d. 1


The correct answer is: 3

Question 45


Data is stored within the disk drive on the: (select the best answer)
Select one:
a. Spindle
b. Platter
c. Cylinder
d. Sector


The correct answer is: Platter

Question 46


The most time consuming 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: Choice 3

Question 66


A method that is designed to create extremely shallow trees is called:
Select one:
a. Dynamic node implementation
b. Union/Find
c. The list of children method
d. Path compression


The correct answer is: Path compression

Question 67


The process of storing blocks of data in main memory after reading from disk is referred to as:
Select one:
a. Buffering
b. Hashing
c. Pooling
d. Indexing


The correct answer is: Buffering

Question 68


A solution is said to be efficient if it:
Select one:
a. Solves the problem within the required resource constraints
b. Executes faster than other solutions
c. Is completed in the fewest number of steps
d. Can be explained in the context of Big-Oh notation


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

Question 69


A sorting algorithm that assigns records to bins and then relies on some other sorting technique to sort the records within each bin called:
Select one:
a. Radix Sort
b. Quicksort
c. Hash sort
d. Bucket sort


The correct answer is: Bucket sort

Question 70


In a stack which option would access the 3rd element from the top of the stack S
Option 1. S.push(-1);
Option 2. S.dequeue(-3);
Option 3. S.pop();
S.pop();
S.pop();
Option 4. S.pop(n-3);
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 3

Question 71


A leaf is any node that:
Select one:
a. Has one child
b. Is an internal node with no ancestors
c. Is any node with two empty children
d. Is the ancestor of the root node


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

Question 72


According to textbook by Shaffer, a heap data structure has two properties which are:
Select one:
a. every node stores a value less than or equal to that of its children and it is a complete binary tree
b. it is a min-heap and is partially ordered
c. it is a complete binary tree and the values stored in it are partially ordered
d. it is a priority queue and is in Θ( n )


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

Question 73


The upper bound for the growth of the Algorithms running time is represented by:
Select one:
a. Big Oh (O)
b. Big Omega (Ω)
c. Big Theta (Θ)
d. Exponential growth


The correct answer is: Big Oh (O)

Question 74


The lower bound for the growth of the Algorithms running time is represented by (please the best answer):
1. Big Oh (O)
2. Big Omega (Ω)
3. Big Theta (Θ)
4. Exponential growth
Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 2

Question 75


The benefit of a 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)
:
Select one:
True
False


The correct answer is 'True'.

Question 79


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
function ( n ) {
sum2 = 0;
for (k=1; k<=n; k*=2)
for (j=1; j<=k; j++)
sum2++;
}
Choice 1. O( 2n )
Choice 2. Θ ( n )
Choice 3. Θ( n log n )
Choice 4. Ω( n2 )
(NOTE: code fragment is not intended to be functioning code)

Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 2

Question 80


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


The correct answer is 'True'.

Question 81


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


The correct answer is 'False'.

Question 82


For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
if (a.length > 0) {
return a[a.length - 1];
} else {
throw new NoSuchElementException();
}
Option 1. O( 1 )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


Explanation: Here n = a.length, and T(n) = 1.
The correct answer is: Option 1

Question 83


Setting the dirty bit causes what action to be performed on a block: (select the best answer)
Select one:
a. It is deleted because it is no longer consistent
b. It flushes or writes the block out to the disk
c. Refreshes the data by re-reading the block
d. It cleans the cache by flushing all data from the cache


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

Question 84


Asymptotic Algorithm Analysis is primarily concerned with:
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-heap structure


The correct answer is: max-heap structure

Question 86


For the following code fragment, select option that represents the most appropriate asymptotic analysis:
for (i=0; i<n; i++) {
//
// Search in array a for smallest element starting at i to n-1
//
minIndex = findSmallestElement(a, i, n-1)
a[i] = a[minIndex];
}
findSmallestElement( int a[], int i, int n ) {
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 allocated to a file that is not physically adjacent

Question 106


A binary tree traversal that lists every node in the tree exactly once is called:
Select one:
a. a Traversal
b. A visitor design pattern
c. An enumeration
d. Natural ordering sequence


The correct answer is: An enumeration
The process of associating a key with the location of a corresponding data record is called folding.
Select one:
True
False


The correct answer is 'False'.

Question 2


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


The correct answer is 'False'.

Question 3


An algorithm that breaks a file to be sorted in smaller files called runs which are sorted and eventually put back together resulting in a sorted file is called:
Select one:
a. Quicksort algorithm
b. Replacement sort algorithm
c. An indexed key sort algorithm
d. Mergesort algorithm


The correct answer is: Mergesort algorithm

Question 4


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


The correct answer is 'True'.

Question 5


For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
for (int i = 1; i <= n; i *= 2) {
for (int j = 0; j < n; j++) {
count++;
}
}
Option 1. O( 1 )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


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

Question 6


The best asymptotic analysis for the selection sort is represented by (select the best option):
Option 1. O( n log n )
Option 2. Ω( n2 )
Option 3. O( n2 )
Option 4. Θ( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 4

Question 7


A leaf is any node that:
Select one:
a. Has one child
b. Is an internal node with no ancestors
c. Is any node with two empty children
d. Is the ancestor of the root node


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

Question 8


A preorder traversal visits every node starting at the leaf nodes and working up the tree.
Select one:
True
False


The correct answer is 'False'.

Question 9


For the following code fragment, select the option which represents the most appropriate asymptotic analysis:
/** @return Position of largest value in "A“ */
static int largest(int[] A) {
int currlarge = 0; // Position of largest
for (int i=1; i<A.length; i++)
if (A[currlarge] < A[i])
currlarge = i; // Remember pos
return currlarge; // Return largest pos
}

Choice 1. Θ ( n )
Choice 2. O( 2n )
Choice 3. Θ( n log n )
Choice 4. Ω( n2 )
(NOTE: code fragment is not intended to be functioning code)

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
b. Union/Find
c. The list of children method
d. Path compression


The correct answer is: Path compression

Question 12


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
static int function ( n ) {
sum = 0;
for (j=1; j<=n; j++)
for (i=1; i<=j; i++)
sum++;
return sum;
}
Choice 1. Θ ( n )
Choice 2. O( 2n )
Choice 3. Θ( n2 )
Choice 4. Ω( n2 )
(NOTE: code fragment is not intended to be functioning code)


Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 3

Question 13


Asymptotic Algorithm Analysis is primarily concerned with:
Select one:
a. The size of the constant in the algorithm running time equation
b. The speed of the computing running the algorithm
c. The speed of the compiler
d. The growth rate demonstrated in the algorithm running time equation


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

Question 14


According to the properties of logarithms, log(nm) =
Note: Due to issues with HTML formatting, an exponent is represented by preceding it with the ^ symbol. As such x^2 is equivalent to x2.
Select one:
a. log n – log m
b. n log n
c. log n + log m
d. log(n^m)


The correct answer is: log n + log m

Question 15


The process for visiting all of the nodes of a binary tree in some order is called a traversal.
Select one:
True
False


The correct answer is 'True'.

Question 16


A list is said to be empty when all of its elements have a zero (0) value
Select one:
True
False


The correct answer is 'False'.

Question 17


A list that organizes the order of records within the list based upon patterns of actual record access is called a/an (select the best answer):
Select one:
a. Quadratic Binary search order
b. A Zipf Distribution
c. A Self-organizing list
d. A range query


The correct answer is: A Self-organizing list

Question 18


A sort that features a limit of n-1 of record swaps is called:
Select one:
a. Insertion sort
b. Bubble sort
c. Inversion sort
d. Selection sort


The correct answer is: 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 (O)

Question 21


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


The correct answer is 'True'.

Question 22


In linked lists there are no NULL links in:
Select one:
a. Single linked list
b. Linear doubly linked list
c. Circular linked list
d. None of these


The correct answer is: Circular linked list

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 is: Postorder Traversal

Question 48


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
function ( n ) {
sum2 = 0;
for (k=1; k<=n; k*=2)
for (j=1; j<=k; j++)
sum2++;
}
Choice 1. O( 2n )
Choice 2. Θ ( n )
Choice 3. Θ( n log n )
Choice 4. Ω( n2 )
(NOTE: code fragment is not intended to be functioning code)

Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 2

Question 49


For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
public static int binarySearch(int[] a, int key) {
int left = 0;
int right = a.length-1;
while (left <= right) {
int mid = left + (right-left)/2;
if (key < a[mid]) right = mid-1;
else if (key > a[mid]) left = mid+1;
else return mid;
}
//not found
return -1;
}
Option 1. Ω( 1 ), O( log n )
Option 2. Ω( n ), O( 2n )
Option 3. Θ( n log n )
Option 4. Θ( log n )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 1

Question 50


The processing time or cost of a sort is defined by the number of comparisons and exchanges that must be made during processing. What is the average cost of the heapsort?:
Option 1. O( n log n )
Option 2. Ω( n2 )
Option 3. O( n2 )
Option 4. Θ( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 1

Question 51


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
public E getValue ( ) {
assert (curr >= 0) && (curr < listSize) :
"No current element";
return listArray[curr];
}
Choice 1. Θ ( n )
Choice 2. O( 2n )
Choice 3. Θ( n log n )
Choice 4. O( 1 )
(NOTE: code fragment is not intended to be functioning code)


Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 4

Question 52


For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
// Recursive Fibonacci generator
static long fibr(int n) {
if ((n == 1) || (n == 2)) return 1; // Base case
return fibr(n-1) + fibr(n-2); // Recursive call
}
Option 1. O( n )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 2

Question 53


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


The correct answer is 'True'.

Question 54


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
static int function ( n ) {
for (k=0; k<n; k++)
A[k] = k;
return A[k];
}
Choice 1. O ( n2 )
Choice 2. O( 2n )
Choice 3. Ω( n2 )
Choice 4. Θ ( n )
(NOTE: code fragment is not intended to be functioning code)

Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 4

Question 55


The freelist …
Select one:
a. Provides access to memory within the operating system that has not yet been allocated
b. Provides access to memory objects which have no Big O ( n ) time.
c. Facilitates and encourages the use of the new operator.
d. Holds the list nodes that are no longer in use.


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 the best choice):
Choice 1. Insertion and deletion are ( 1 ).
Choice 2. Direct access of an item in the list structure is ( n ).
Choice 3. Space grows with number of elements.
Choice 4. There is no overhead associated with elements in the list structure
Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 4

Question 57


A sort algorithm that uses two nested loops with the inner loop moving through the array from bottom to top is called the:
Select one:
a. Insertion sort
b. Bubble sort
c. Inversion sort
d. Selection sort


The correct answer is: Bubble sort

Question 58


For the following code fragment, select the option which represents the most appropriate asymptotic analysis:
static int function ( n ) {
sum = 0;
for (i=1; i<=n; i++)
sum += n;
return sum;
}
Option 1. Ω( n2 )
Option 2. Θ ( n )
Option 3. O( log n )
Option 4. O( 2n )
(NOTE: code fragment is not intended to be functioning code)


Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 2

Question 59


A list is
Select one:
a. An ADT for storing and retrieving data
b. A tree data structure
c. Finite ordered sequence of data items
d. A collection of operations to implement an ADT


The correct answer is: Finite ordered sequence of data items

Question 60


Push and Pop are notations associated with which data structure:
Select one:
a. Queue
b. Stack
c. List
d. Array


The correct answer is: Stack

Question 61


A tree whose internal nodes all have exactly K children is called a K-ary tree.
Select one:
True
False


The correct answer is 'True'.

Question 62


A compound computed search that combines a binary search to get close to the required record and then uses sequential search to find the item is referred to as a/an:
Select one:
a. Zipf search
b. An Exact match search
c. A Dictionary search
d. bit map vector search


The correct answer is: A Dictionary search

Question 63

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


Select the answer that best defines Huffman Coding:
Select one:
a. A set of coding rules that is typically used for compression
b. A fixed length coding scheme for character representation
c. A tree structure that trades off space and time requirements to provide a more efficient priority queue
d. An approach of assigning codes to characters such that the frequency length of the code depends upon the relative frequency of the corresponding character in use


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

Question 67


A significant benefit to using an index to hold and sort keys to a file is:
Select one:
a. Smaller keys require less I/O
b. The entire sort can always be completed in memory
c. The head of the disk drive does not need to move
d. There is no seek time added to the latency of I/O operations


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

Question 68


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
static int function ( n ) {
sum = 0;
for (i=1; i<=n; i++)
sum += n;
return sum;
}
Choice 1. Ω( n2 )
Choice 2. Θ ( n2 )
Choice 3. O( log n )
Choice 4. O( n )
(NOTE: code fragment is not intended to be functioning code)


Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 4

Question 69


The most time consuming of the following operations on an array based list implementation is:
Select one:
a. Inserting a new element at position n-1 in the list where n is the number of elements in the list.
b. Inserting a new element into the head of the list.
c. Removing an element at position n-1 within the list
d. Removing an element from the tail of the list.


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

Question 70


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
static int function ( n ) {
sum = 0;
for (i=1; i<=n; i++)
sum += n;
return sum;
}
Choice 1. Ω( n2 )
Choice 2. Ω( log n2 )
Choice 3. Θ( n log n )
Choice 4. O ( n )
(NOTE: code fragment is not intended to be functioning code)



Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 4

Question 71


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
function ( n ) {
sum1 = 0;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
sum1++;
}
Choice 1. Θ ( n2 )
Choice 2. O( 2n )
Choice 3. Θ( n log n )
Choice 4. Ω( log n2 )
(NOTE: code fragment is not intended to be functioning code)

Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 1

Question 72


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


The correct answer is 'False'.

Question 73


A sorting algorithm that assigns records to bins and then relies on some other sorting technique to sort the records within each bin called:
Select one:
a. Radix Sort
b. Quicksort
c. Hash sort
d. Bucket sort


The correct answer is: Bucket sort

Question 74


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


The correct answer is 'True'.

Question 75


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


The correct answer is 'True'.

Question 76


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


The correct answer is 'False'.

Question 77


Which of the following is NOT one of the design patterns outlined in our text.
Select one:
a. Flyweight
b. Visitor
c. Composite
d. Synergy


The correct answer is: Synergy

Question 78


In a stack which option would access the 3rd element from the top of the stack S
Option 1. S.push(-1);
Option 2. S.dequeue(-3);
Option 3. S.pop();
S.pop();
S.pop();
Option 4. S.pop(n-3);
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 3

Question 79


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
/** @return The position of an element in sorted array A with value k. If k is not in A,return A.length. */
static int binary(int[] A, int k) {
int l = -1; // Set l and r
int r = A.length; // beyond array bounds
while (l+1 != r) { // Stop when l, r meet
int i = (l+r)/2; // Check middle
if (k < A[i]) r = i; // In left half
if (k == A[i]) return i; // Found it
if (k > A[i]) l = i; // In right half
}
return A.length; // Search value not in A
}
Choice 1. Θ ( n )
Choice 2. O( 2n )
Choice 3. O( log n )
Choice 4. Ω( n2 )
(NOTE: code fragment is not intended to be functioning code)

Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 3

Question 80


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

Select one:
a. Preorder Traversal
b. Postorder Traversal
c. Inorder Traversal
d. Outoforder Traversal


The correct answer is: Inorder Traversal

Question 81


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


The correct answer is 'False'.

Question 82


For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
if (a.length > 0) {
return a[a.length - 1];
} else {
throw new NoSuchElementException();
}
Option 1. O( 1 )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


Explanation: Here n = a.length, and T(n) = 1.
The correct answer is: Option 1

Question 83


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


The correct answer is 'True'.

Question 84


According to textbook by Shaffer, a heap data structure has two properties which are:
Select one:
a. every node stores a value less than or equal to that of its children and it is a complete binary tree
b. it is a min-heap and is partially ordered
c. it is a complete binary tree and the values stored in it are partially ordered
d. it is a priority queue and is in Θ( n )


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

Question 85


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
static int function ( n ) {
for (k=0; k<n; k++)
A[k] = k;
return A[k];
}
Choice 1. Θ ( n log n )
Choice 2. O( 2n )
Choice 3. O( n )
Choice 4. Ω( n2 )
(NOTE: code fragment is not intended to be functioning code)



Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 3

Question 86


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


The correct answer is 'True'.

Question 87


An exchange sort is one where: (select the best answer)
Select one:
a. Records in an unsorted list are moved to a sorted list
b. Adjacent records in the list and compared and exchanged
c. An inversion is executed
d. The sorting algorithm is said to be stable


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

Question 88


What is the role of the pivot in a quicksort algorithm?
Select one:
a. It identifies the maxkey value
b. It specifies the point where the array will be subdivided into partitions and each partition then sorted
c. It defines the sequence for merging in the sort
d. It indicates the index of the current record being compared


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

Question 89


If A={1, 2, 3, 4} and B={4, 5, 6}, find A∪ B .
Select one:
a. {1,2,3,4,4,5,6}
b. {4}
c. {x | x is all positive integers}
d. {1,2,3,4,5,6}


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

Question 90


Setting the dirty bit causes what action to be performed on a block: (select the best answer)
Select one:
a. It is deleted because it is no longer consistent
b. It flushes or writes the block out to the disk
c. Refreshes the data by re-reading the block
d. It cleans the cache by flushing all data from the cache


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

Question 91


Which of the following items is NOT true for Array-Based Lists (please select the best choice):
Choice 1. Insertion and deletion operations are ( n )
Choice 2. Direct access of an item in the array is ( 1 )
Choice 3. Space used grows dynamically as the array is populated
Choice 4. Array contains wasted space if array positions are not full
Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 3

Question 92


The lower bound for the growth of the Algorithms running time is represented by (please the best answer):
1. Big Oh (O)
2. Big Omega (Ω)
3. Big Theta (Θ)
4. Exponential growth
Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 2

Question 93


A sequential tree can be represented using a bit vector?
Select one:
True
False


The correct answer is 'True'.

Question 94


The list of children approach uses both pointers and an array structure to represent the tree.
Select one:
True
False


The correct answer is 'True'.

Question 95


The upper bound for the growth of the Algorithms running time is represented by (please select the best answer):
1. Big Oh (O)
2. Big Omega (Ω)
3. Big Theta (Θ)
4. Exponential growth
Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 1

Question 96


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


The correct answer is 'False'.

Question 97


For the following code fragment, select the most appropriate asymptotic analysis:
// Towers of Hanoi
static void solveHanoi(int disks, char fromPole, char toPole, char withPole) {
if (disks >= 1) {
solveHanoi(disks-1, fromPole, withPole, toPole);
moveDisk(fromPole, toPole);
solveHanoi(disks-1, withPole, toPole, fromPole);
}
}
static void moveDisk(char fromPole, char toPole) {
moves++;
}
Option 1. O( n )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 2

Question 98


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


The correct answer is 'False'.

Question 99


The quicksort is typically slower than the heapsort by a constant factor.
Select one:
True
False


The correct answer is 'False'.

Question 100


A sort where the list is divided into halves, the halves sorted and these two halves are merged is called:
Select one:
a. Mergesort
b. Binary sort
c. Quicksort
d. Heapsort


The correct answer is: Mergesort

Question 101


An important advantage of the sequential tree implementation is that (select the best answer):
Select one:
a. It is an extremely shallow tree
b. The data structure can be transmitted between computers
c. It saves space because no pointers are stored
d. It uses dynamic nodes


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

Question 102


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


The correct answer is 'True'.

Question 103


A solution is said to be efficient if it:
Select one:
a. Solves the problem within the required resource constraints
b. Executes faster than other solutions
c. Is completed in the fewest number of steps
d. Can be explained in the context of Big-Oh notation


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

Question 104


A finite set of one or more nodes such that there is one designated node call the root is a: (select the best answer)
Select one:
a. Parent root
b. a B+ tree data structure
c. Index
d. Tree


The correct answer is: Tree

Question 105


For the following code fragment, select the option that represents the most appropriate asymptotic analysis:
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
Option 1. O( n )
Option 2. O( 2n )
Option 3. O( n log n )
Option 4. O( n2 )
Select one:
a. Option 1
b. Option 2
c. Option 3
d. Option 4


The correct answer is: Option 1

Question 106


For the following code fragment, select the choice which represents the most appropriate asymptotic analysis:
function ( n ) {
sum2 = 0;
for (i=1; i<=n; i++)
for (j=1; j<=i; j++)
sum2++;
}
}
Choice 1. Ω ( 1 )
Choice 2. O( 2n )
Choice 3. Θ( n2 )
Choice 4. Ω( n2 )
(NOTE: code fragment is not intended to be functioning code)

Select one:
a. Choice 1
b. Choice 2
c. Choice 3
d. Choice 4


The correct answer is: Choice 3

 

CallTutors Guarantees

  • Work Within Deadline
  • Lowest Price Guranteed
  • Plagiarism Free Guranteed
  • 24 * 7 Availability
  • Native Experienced Experts
  • Free Revisions

Avg Client Rating: 4.8/5

Total Reviews: 9,835

Assignment07/20/2019

got an Hd grade in my paper. I was totally depressed but after taking help from you i feel free from all of my burden, Thank you

Naomi
Essay help07/20/2019

Good writing All the topics I wanted in this assignment were covered Thank you very much.

O Brian
Statistics07/19/2019

very impressive quick service the solution, very nice support team thanx for the instant help

John Williams
Biology assignment07/19/2019

Well presented assignment, managed to get a good score, just a few minor gaps from the marker's feedback

Emilia Adam
Psychology07/18/2019

Great job, received great grade on paper will be using again, Highly recommended from my side.

Abby Jones

Read More...