Welcome to Data Structure Quiz, Randomly Selected !!

Question 1. A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.
Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

1, 3, 5, 6, 8, 9

9, 6, 3, 1, 8, 5

9, 3, 6, 8, 5, 1

9, 5, 6, 8, 3, 1

Question 2. Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1
Which of the following is true ?

T(n) = O(n^2)

T(n) = Theta(n^2)

T(n) = Omega(n^2)

T(n) = O(nLogn)

Question 3. The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

O(n)

O(nlogn)

O(log*n)

O(n^2)

Question 4. What 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.

Question 5. Which one of the following in place sorting algorithms needs the minimum number of swaps?

Quick sort

Insertion sort

Selection sort

Heap sort

Question 6. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
i. 9679, 1989, 4199 hash to the same value
ii. 1471, 6171 has to the same value
iii. All elements hash to the same value
iv. Each element hashes to a different value

i only

ii only

i and ii only

iii or iv

Question 7. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that '_' denotes an empty location in the table.

8, _, _, _, _, _, 10

1, 8, 10, _, _, _, 3

1, _, _, _, _, _,3

1, 10, 8, _, _, _, 3

Question 8. Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?

s + m

s - m

m * s

m / s

Question 9. A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i + 1]. To be able to store any binary tree on n vertices the minimum size of X should be.

log2n

n

2n + 1

2^n - 1

Question 10. The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is
Graph

MNOPQR

NQMPOR

QMNPRO

QMNPOR