Data Structures and Algorithms Quiz # 3

Here is a code for an integer variable n

   while (n > 0)
   {
     n = n/10; // Use integer division
   }
What is the worst case scenario analysis for the above loop?

O(1)

O(log n)

O(n)

O(n2)
Suppose we have a circular array implementation of a queue, with ten items in the queue stored at data[2] through data[11]. The CAPACITY is 42. Where does the push member function place the new entry in the array?

data[1]

data[2]

data[11]

data[12]
Which of the following sorting algorithms yield approximately the same worst-case and average-case running time behavior in O(n*log(n))?

Bubble sort and selection sort

Heap sort and merge sort

Quick sort and radix sort

Tree sort and Median-of-3 quicksort
The operation for adding an entry to a stack is traditionally called ________.

add

append

insert

push
For a complete binary tree with depth d, the total number of nodes is:

2d+1

2d

2d+1-1

2d2
Which of the following is false?

A binary search begins with the middle element in the array

A binary search continues halving the array either until a match is found or until there are no more elements to search

If the search argument is greater than the value located in the middle of the binary, the binary search continues in the lower half of the array
Which of the following applications may use a stack?

A parentheses balancing program

Keeping track of local variables at run time

Syntax analyzer for a compiler

All of the above
What is the value of the post-fix expression 6 3 2 4 + - *?

Something between -15 and -100

Something between -5 and -15

Something between 5 and 15

Something between 15 and 100
The minimum number of interchanges needed to convert the array 89,19,14,40,17,12,10,2,5,7,11,6,9,70 into a heap with the maximum element at the root is:

0

1

2

3
Suppose T is a complete binary tree with 14 nodes. What would be the minimum possible depth of T?

3

4

5
In which data structure do the insertion and deletion take place at the same end?

Linked list

Tree

Stack

Linked list of stack
What is the formulae to find maximum number of nodes n in a perfect binary tree?

2h + 1 - 1

2h + 1

2h

2h + 1 + 1
A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?

511

512

1024

There is no maximum limit
In which dynamically created linked list can the first node be recovered after moving to the second node?

Simple linked list

Circular linked list

Doubly linked list

Both b and c
What is the best definition of a collision in a hash table?

Two entries are identical except for their keys

Two entries with different data have exactly the same key

Two entries with different keys have exactly the same hash value

Two entries with exactly the same key have different hash values
What is the pre-order traversal equivalent of the following algebraic expression? [a+(b-c)]*[(d-e)/(f+g-h)]

abc-+de-fg+h-/*

*+a-bc/-de-+f-gh

a+*b-/c-d-e+fgh

*+a-bc-/d+e-fgh
A sparse matrix can be a lower-triangular matrix when____.

all the non-zero elements lie only on the leading diagonal

all the non-zero elements lie above the leading diagonal

all the non-zero elements lie below the leading diagonal

None of the above
A graph in which all nodes are of an equal degree is known as:

Multigraph

Non - regular graph

Regular graph

Complete graph
What is the maximum number of statements that may be recursive calls in a single function declaration?

1

2

n (n is the argument)

There is no fixed maximum
Which additional requirement is placed on an array so that binary search may be used to locate an entry?

The array elements must form a heap

The array must have at least 2 entries

The array must be sorted

The array's size must be a power of two
What is the worst-case scenario for heapsort to sort an array of n elements?

O(log n)

O(n)

O(n log n)

O(n2)
The recurrence relation T(n)=mT(n/2)+an2 is satisfied by___

T(n)=O(nm)

T(n)=O(m*log(m))

T(n)=O(n*log(m))

T(n)=O(m*log(n))
Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child's value be stored (the array's first index is 0)?

data[i+1]

data[i+2]

data[2*i + 1]

data[2*i + 2]
In a complete binary tree, the parent of any node k can be determined by ________.

2k

2k+1

K/2

2K-1
Consider a linked list of n elements which is pointed by an external pointer. What is the time taken to delete the element which is a successor of the pointed element by a given pointer?

O(1)

O(log2n)

O(n)

O(n*log2n)
Suppose X is a B-tree leaf containing 41 entries and has at least one sibling. Which of the statements would be true in this case?

Any sibling of X is also a leaf

Any sibling of X contains at least 41 entries

The parent of X has exactly 42 entries

X has at least 41 siblings
In a complete binary tree of n nodes, how far are the most distant two nodes? Assume each in the path counts 1. Assume log(n) is log base 2.

about log(n)

about 2*log(n)

about 3*log(n)

about 4*log(n)
In a graph G, F is a spanning forest of G if

(i)F is a subgraph of G containing all the nodes of G
(ii)F is an order forest containing trees T1,T2,...Tn
(iii)Ti contains all the nodes that are reachable in G from the root Ti and are contained in Tj for some j

Which of the above conditions is/are true?

(i),(ii)

(ii),(iii)

(i),(iii)

(i),(ii) and (iii)

Which information is not saved in the activation record when a function call is executed?

Current depth of recursion

Formal parameters

Location where the function should return when done

Local variables

The linked list implementation of sparse matrices is superior to the generalized dope vector method because it is __________.

conceptually easier and completely dynamic

efficient if the sparse matrix is a band matrix

efficient in accessing an entry

all of these

Quiz:	Data Structures and Algorithms Quiz # 3
Total Questions:	30 MCQs
Time:	30 Minutes

Data Structures and Algorithms Quiz # 3

Here is a code for an integer variable n while (n > 0) { n = n/10; // Use integer division }What is the worst case scenario analysis for the above loop?

Suppose we have a circular array implementation of a queue, with ten items in the queue stored at data[2] through data[11]. The CAPACITY is 42. Where does the push member function place the new entry in the array?

Which of the following sorting algorithms yield approximately the same worst-case and average-case running time behavior in O(n*log(n))?

The operation for adding an entry to a stack is traditionally called ________.

For a complete binary tree with depth d, the total number of nodes is:

Which of the following is false?

Which of the following applications may use a stack?

What is the value of the post-fix expression 6 3 2 4 + - *?

The minimum number of interchanges needed to convert the array 89,19,14,40,17,12,10,2,5,7,11,6,9,70 into a heap with the maximum element at the root is:

Suppose T is a complete binary tree with 14 nodes. What would be the minimum possible depth of T?

In which data structure do the insertion and deletion take place at the same end?

What is the formulae to find maximum number of nodes n in a perfect binary tree?

A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?

In which dynamically created linked list can the first node be recovered after moving to the second node?

What is the best definition of a collision in a hash table?

What is the pre-order traversal equivalent of the following algebraic expression? [a+(b-c)]*[(d-e)/(f+g-h)]

A sparse matrix can be a lower-triangular matrix when____.

A graph in which all nodes are of an equal degree is known as:

What is the maximum number of statements that may be recursive calls in a single function declaration?

Which additional requirement is placed on an array so that binary search may be used to locate an entry?

What is the worst-case scenario for heapsort to sort an array of n elements?

The recurrence relation T(n)=mT(n/2)+an2 is satisfied by___

Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child's value be stored (the array's first index is 0)?

In a complete binary tree, the parent of any node k can be determined by ________.

Consider a linked list of n elements which is pointed by an external pointer. What is the time taken to delete the element which is a successor of the pointed element by a given pointer?

Suppose X is a B-tree leaf containing 41 entries and has at least one sibling. Which of the statements would be true in this case?

In a complete binary tree of n nodes, how far are the most distant two nodes? Assume each in the path counts 1. Assume log(n) is log base 2.

Which information is not saved in the activation record when a function call is executed?

The linked list implementation of sparse matrices is superior to the generalized dope vector method because it is __________.

Here is a code for an integer variable n

while (n > 0)
{
n = n/10; // Use integer division
}
What is the worst case scenario analysis for the above loop?