Welcome to Data Structure Quiz, Randomly Selected !!

Question 1. Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
f(int Y[10], int x) { 
	int i, j, k; 
	i = 0; j = 9; 
	do { 
		k = (i +  j) /2; 
		if( Y[k] < x) i = k; else j = k; 
	} while(Y[k] != x && i < j); 
	if(Y[k] == x) printf ("x is in the array") ; 
	else printf ("x is not in the array") ; 
}

On which of the following contents of Y and x does the program fail?

Y is [1 2 3 4 5 6 7 8 9 10] and x < 10

Y is [1 3 5 7 9 11 13 15 17 19] and x < 1

Y is [2 2 2 2 2 2 2 2 2 2] and x > 2

Y is [2 4 6 8 10 12 14 16 18 20] and 2 > ?x < 20 and x is even

Question 2. Which one of the following is a key factor for preferring B-trees to binary search trees for indexing database relations?

Database relations have a large number of records

Database relations are sorted on the primary key

B-trees require less memory than binary search trees

Data transfer form disks is in blocks.

Question 3. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

log 2 n

n/2

log 2 n - 1

n

Question 4. Consider a B+ - tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?

1

2

3

4

Question 5. The maximum number of binary trees that can be formed with three unlabeled nodes is:

1

5

4

3

Question 6. Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

(1 2 (4 5 6 7))

(1 (2 3 4) 5 6) 7)

(1 (2 3 4)(5 6 7))

(1 (2 3 NULL) (4 5))

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

Quick sort

Insertion sort

Selection sort

Heap sort

Question 8. Suppose you are given an array s[1...n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence do, where 1 < k <= n:
  reverse (s, 1, k);
  reverse (s, k + 1, n);
  reverse (s, 1, n);

Rotates s left by k positions

Leaves s unchanged

Reverses all elements of s

none of the above

Question 9. 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 10. The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

n/2

(n-1)/3

(n-1)/2

(2n +1)/3