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