Data Structures 03

21. Merge sort makes two recursive calls. Which statement is true after these two recursive calls finish, but before the merge step ? [Paper II June2014]
(A) The array elements form a heap.

(B) Elements in each half of the array are sorted amongst themselves.

(C) Elements in the first half of the array are less than or equal to elements in second half of the array.
(D) All of the above

22. Searching for an element in the hash table requires O(1) time for the ___ time, whereas for direct addressing it holds for the ___ time. [Paper II June 2014]
(A) worst­ case, average    (B) worst ­case, worst­ case
(C) average, worst­ case    (D) best, average

23. An algorithm is made up of 2 modules M1 and M2. If time complexity of modules M1 and M2 are h(n) and g(n) respectively, the time complexity of the algorithm is [Paper II June 2014]
(A) min (h(n), g(n))      (B) max (h(n), g(n))
(C) h(n) + g(n)            (D) h(n) * g(n)

24. What is the maximum number of parenthesis that will appear on the stack at any one time for parenthesis expression given by (( ) ( ( ) ) ( ( ) ) ) [Paper II June 2014]
(A) 2         (B) 3
(C) 4         (D) 5

25. The reverse polish notation equivalent to the infix expression ((A + B) * C + D)/(E + F + G)   [Paper III June 201 4]
(A) A B + C * D + EF + G + / 

(B) A B + C D * + E F + G + /
(C) A B + C * D + E F G + +/ 

(D) A B + C * D + E + F G + /

26. ___ comparisons are necessary in the worst case to find both the maximum and minimum of n numbers.    [Paper III December 2013 ]
(A) 2n – 2                        (B) n + floor (lg n) – 2
(C) floor (3n/2) – 2            (D) 2 * lg n – 2

27. Let A and B be two n × n matrices. The efficient algorithm to multiply the two matrices has the time complexity [Paper III December 2013 ]
(A) O(n³)                (B) O(n^2.81)
(C) O(n^2.67)            (D) O(n²)

28. Assuming there are n keys and each key is in the range [0, m – 1]. The run time of bucket sort is  [Paper III December 2013 ]

(A) O(n)                 (B) O(n * lg n)
(C) O(n * lg m)       (D) O(n + m)

29.What is the value of the postfix expression ?
a b c d + – ∗ (where a = 8, b = 4, c = 2 and d = 5) [Paper II December2013]
(A) – 3/8                (B) ­ 8/3
(C) 24                   (D) ­24

30. If the queue is implemented with a linked list, keeping track of a front pointer and a rear pointer, which of these pointers will change during an insertion into a non­empty queue ?       [Paper II December 2013]
(A) Neither of the pointers change 
(B) Only front pointer changes
(C) Only rear pointer changes
(D) Both of the pointers changes

SOLUTIONS

21. B

22. C

23. B

24. B

25. A

26. C

27. B
 
28. D

29. D

30. C

Data Structures 02

11. Which one of the following binary search tree is optimal, if probabilities of successful search and unsuccessful search are same?                 [Paper III June 2012]

12. The strategy used to reduce the number of tree branches and the number of static evaluations applied in case of a game tree is                                 [Paper III June 2012]

(A) Minmax strategy

(B) Alpha-beta pruning strategy

(C) Constraint satisfaction strategy

(D) Static max strategy

13. The postfix expression AB + CD – * can be evaluated using a

[Paper II June 2012]

(A) stack                     (B) tree

(C) queue                    (D) linked list

14. The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.

[Paper II June 2012]

(A) ABFCDE

(B) ADBFEC

(C) ABDECF

(D) None of the above

15. A binary search tree is a binary tree:    [Paper II June 2012]

(A) All items in the left subtree are less than root

(B) All items in the right subtree are greater than or equal to the root

(C) Each subtree is itself a binary search tree

(D) All of the above

16. Leaves of which of the following trees are at the same level?

[Paper II June 2012]

(A) Binary tree                      (B) B-tree

(C) AVL-tree                        (D) Expression tree

17. A / B+ tree index is to be built on the name attribute of the relation STUDENT. Assume that all students names are of length 8 bytes, disk block are of size 512 bytes and index pointers are of size 4 bytes. Given this scenario what would be the best choice of the degree (i.e. the number of pointers per node) of the B+ tree?            [Paper II June 2012]

(A) 16             (B) 42

(C) 43             (D) 44

18. The Inorder traversal of the tree will yield a sorted listing of elements of tree in

[Paper II June 2012]

(A) Binary tree

(B) Binary search tree

(C) Heaps

(D) None of the above

19. Which of the following data structure is linear type?          [Paper II June 2012]

(A) Strings

(B) Lists

(C) Queues

(D) All of the above

20. To represent hierarchical relationship between elements, which data structure is suitable? 
[Paper II June 2012]

(A) Dequeue             (B) Priority

(C) Tree                    (D) All of the above

SOLUTIONS

11. D

This tree is optimal because the distance to the leaf nodes is minimum.

12. B

Minimax is a decision rule used in decision theory, game theory for minimizing the possible loss for a worst case (maximum loss) scenario. Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty.

Alpha-beta pruning is a procedure to reduce the amount of computation and searching during minimax. It seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. 

13. A

14.

15. D

16. B
A B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. A B-tree is kept balanced by requiring that all leaf nodes be at the same depth.
An AVL tree is a self-balancing binary search tree in which the heights of the two child subtrees of any node differ by at most one.
An expression tree is a specific application of a binary tree to evaluate certain expressions. 

17.

18. B

19. D

20. C

Data Structures 01

1. Which of the following permutations can be obtained in the output using a stack of size 3 elements assuming that input, sequence is 1, 2, 3, 4, 5?                [Paper III December 2012]

(A) 3, 2, 1, 5, 4

(B) 5, 4, 3, 2, 1

(C) 3, 4, 5, 2, 1

(D) 3, 4, 5, 1, 2

2. Suppose there are log_n sorted lists of n log_n elements each. The time complexity of producing a sorted list of all these elements is (use heap data structure)             [Paper III December 2012]

(A) O (n log log_n)

(B) θ (n log_n)

(C) Ω (n log_n)

(D) Ω (n^3/2)

3. Which of the following data structure is Non-linear type?         [Paper II Dec 2011]

 (A) Strings          (B) Lists

 (C) Stacks          (D) None of the above

4. The total number of comparisons in a bubble sort is:                [Paper II Dec 2011]

 (A) 0(log n)                (B) 0(n log n)

 (C) 0(n)                     (D) None of the above

5. Which of the following is a bad example of recursion?          [Paper II Dec 2011]

 (A) Factorial                        (B) Fibonacci numbers

 (C) Tower of Hanoi             (D) Tree traversal

6. The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.

(A) ABFCDE              (B) ADBFEC

(C) ABDECF              (D) ABDCEF

7. B + tree are preferred to binary tree in database because

(A) Disk capacities are greater than memory capacities

(B) Disk access much slower than memory access

(C) Disk data transfer rates are much less than memory data transfer rate

(D) Disk are more reliable than memory

8. The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to

(A) 2⁰ + 2¹ + ….. 2^h

(B) 2⁰ + 2¹ + ….. 2^{h – 1}

(C) 2⁰ + 2¹ + ….. 2^{h + 1}

(D) 2¹ + ….. 2^{h + 1}

9. Number of binary trees formed with 5 nodes are             [Paper III June 2012]

(A) 32              (B) 36

(C) 120            (D) 42

10. The following postfix expression is evaluated using a stack 823^/23* + 51* –

The top two elements of the stack after first * is evaluated   [Paper III June 2012]

(A) 6, 1            (B) 5, 7

(C) 3, 2            (D) 1, 5

SOLUTIONS

1. A, C (UGC Agrees only C!)

Above sequences can be obtained by the following sequence of operations

A: Push 1, Push 2, Push 3, Pop 3, Pop 2, Pop 1, Push 4, Push 5, Pop 5, Pop 4

C: Push 1, Push 2, Push 3, Pop 3, Push 4, Pop 4, Push 5, Pop 5, Pop 2, Pop 1

2. A

3. D

4. D

Bubble sort has worst-case and average complexity both О(n²)

5.

6.

7.

8. A

In a binary tree of height h the total number of nodes is at most 2⁰ + 2¹ + ….. 2^h   =   2^{h + 1} – 1

A binary tree is a complete binary tree, when it has maximum number of nodes.

9. D
Let C(n) be the number of distinct binary trees with n nodes, Then:

C(n) =

so for n=5, C(n) = 10! / (6!)5! = 42

10. A
The evaluation is as follows:
Step       Symbol               Action                                                Stack
1.                8           Push 8 on to stack                                        8,
2.                2           Push 2 on to stack                                        8, 2
3.                3           Push 3 on to stack                                        8, 2, 3
4.                ^           Pop 2, 3. Find 2^3, Push result on to stack   8, 8
5.                /            Pop 8, 8. Find 8/8, Push result on to stack    1
6.                2           Push 2 on to stack                                        1, 2
7.                3           Push 3 on to stack                                        1, 2, 3
8.                *           Pop 2, 3. Find 2*3, Push result on to stack   1, 6