ADVANCED DATA STRUCTURES ONLINE BITS

Code No: 07A3EC15 Set No. 1
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
II B.Tech. I Sem., II Mid-Term Examinations, Oct / Nov. – 2009
ADVANCED DATA STRUCTURES
Marks: 20.
I. Choose the correct alternative:
1. The process of accessing data stored in a tape is similar to manipulating data on a [ ]
A. stack B. queue C.list D. Heap
2. A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 10 leaves [ ]
A. cannot have more than 19 nodes B. has exactly 19nodes
C. has exactly 17 nodes D. cannot have more than 17 nodes.
3. The order of binary search algorithm is [ ]
A. n B.n2 C. nlogn D.logn
4. The height of an AVL tree is [ ]
A. logn B. o(logn) C.toglogn D.o(n)
5. What are the actions that are performed on red Black trees with the same time complexity[ ]
A. size B. find C. insert D. both b and c
6. LLb imbalance performs [ ]
A. colour change B. rotation C. both D. none
7. AVL tree is a ____________ binary tree. [ ]
A. complete B. full C. Height balanced D. skewed
8. The transformation done to remedy ________ imbalance is casual due in insect rum in as AVL tree often called single rotation [ ]
A. LL & RR B. LL & LR C. LR & RL D. RR & Rl
9. Which of the following pattern matching algorithm does not reavires pre-processing on text or pattern [ ]
A. brute force B. Robin karp C. bayer D. knuth morris pratt
10. In boyer more algorithm, in which heuristic mismatch occurs [ ]
A. looking glass heuristic B. character jump heuristic C. basic heuristic D. boyer heuristic
Cont…2

A
Code No: 07A3EC15 :2: Set No. 1
II Fill in the blanks:
11. The upward movement by means of swaps is conventionally called _________
12. The number of possible binary trees with 4 nodes is ____________
13. For an AVL tree, the balance factor is ________
14. The height of an m-way search tree of heigh ‘n’ with ‘n’ elements ranges from a low of ______ to a high of _______
15. The KMP algorithm, achieves a running time of _______ which is optimal in worst case.
16. In AVL tree the transformation for m ________ imbalance can be viewed as an RR rotation followed by an LL rotation.
17. The total time complexity of depth-first search traversal is ________
18. The average number at inversions in an array of N distinct elements is ________
19. For merging two sorted lists of sizes m and n into a sorted list of size m+n, requires ______ no.of comparsions.
20. The time complexity of indexed search method is ________
-oOo-
Code No: 07A3EC15 Set No. 2
I. Choose the correct alternative:
1. The height of an AVL tree is [ ]
A. logn B. o(logn) C.toglogn D.o(n)
2. What are the actions that are performed on red Black trees with the same time complexity[ ]
A. size B. find C. insert D. both b and c
3. LLb imbalance performs [ ]
A. colour change B. rotation C. both D. none
4. AVL tree is a ____________ binary tree. [ ]
A. complete B. full C. Height balanced D. skewed
5. The transformation done to remedy ________ imbalance is casual due in insect rum in as AVL tree often called single rotation [ ]
A. LL & RR B. LL & LR C. LR & RL D. RR & Rl
6. Which of the following pattern matching algorithm does not reavires pre-processing on text or pattern [ ]
A. brute force B. Robin karp C. bayer D. knuth morris pratt
7. In boyer more algorithm, in which heuristic mismatch occurs [ ]
A. looking glass heuristic B. character jump heuristic C. basic heuristic D. boyer heuristic
8. The process of accessing data stored in a tape is similar to manipulating data on a [ ]
A. stack B. queue C.list D. Heap
9. A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 10 leaves [ ]
A. cannot have more than 19 nodes B. has exactly 19nodes
C. has exactly 17 nodes D. cannot have more than 17 nodes.
10. The order of binary search algorithm is [ ]
A. n B.n2 C. nlogn D.logn
Cont…2

A
Code No: 07A3EC15 :2: Set No. 2
II Fill in the blanks:
11. The height of an m-way search tree of heigh ‘n’ with ‘n’ elements ranges from a low of ______ to a high of _______
12. The KMP algorithm, achieves a running time of _______ which is optimal in worst case.
13. In AVL tree the transformation for m ________ imbalance can be viewed as an RR rotation followed by an LL rotation.
14. The total time complexity of depth-first search traversal is ________
15. The average number at inversions in an array of N distinct elements is ________
16. For merging two sorted lists of sizes m and n into a sorted list of size m+n, requires ______ no.of comparsions.
17. The time complexity of indexed search method is ________
18. The upward movement by means of swaps is conventionally called _________
19. The number of possible binary trees with 4 nodes is ____________
20. For an AVL tree, the balance factor is ________
-oOo-
Code No: 07A3EC15 Set No. 3
I. Choose the correct alternative:
1. LLb imbalance performs [ ]
A. colour change B. rotation C. both D. none
2. AVL tree is a ____________ binary tree. [ ]
A. complete B. full C. Height balanced D. skewed
3. The transformation done to remedy ________ imbalance is casual due in insect rum in as AVL tree often called single rotation [ ]
A. LL & RR B. LL & LR C. LR & RL D. RR & Rl
4. Which of the following pattern matching algorithm does not reavires pre-processing on text or pattern [ ]
A. brute force B. Robin karp C. bayer D. knuth morris pratt
5. In boyer more algorithm, in which heuristic mismatch occurs [ ]
A. looking glass heuristic B. character jump heuristic C. basic heuristic D. boyer heuristic
6. The process of accessing data stored in a tape is similar to manipulating data on a [ ]
A. stack B. queue C.list D. Heap
7. A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 10 leaves [ ]
A. cannot have more than 19 nodes B. has exactly 19nodes
C. has exactly 17 nodes D. cannot have more than 17 nodes.
8. The order of binary search algorithm is [ ]
A. n B.n2 C. nlogn D.logn
9. The height of an AVL tree is [ ]
A. logn B. o(logn) C.toglogn D.o(n)
10. What are the actions that are performed on red Black trees with the same time complexity[ ]
A. size B. find C. insert D. both b and c
Cont…2

A
Code No: 07A3EC15 :2: Set No. 3
II Fill in the blanks:
11. In AVL tree the transformation for m ________ imbalance can be viewed as an RR rotation followed by an LL rotation.
12. The total time complexity of depth-first search traversal is ________
13. The average number at inversions in an array of N distinct elements is ________
14. For merging two sorted lists of sizes m and n into a sorted list of size m+n, requires ______ no.of comparsions.
15. The time complexity of indexed search method is ________
16. The upward movement by means of swaps is conventionally called _________
17. The number of possible binary trees with 4 nodes is ____________
18. For an AVL tree, the balance factor is ________
19. The height of an m-way search tree of heigh ‘n’ with ‘n’ elements ranges from a low of ______ to a high of _______
20. The KMP algorithm, achieves a running time of _______ which is optimal in worst case.
-oOo-
Code No: 07A3EC15 Set No. 4
I. Choose the correct alternative:
1. The transformation done to remedy ________ imbalance is casual due in insect rum in as AVL tree often called single rotation [ ]
A. LL & RR B. LL & LR C. LR & RL D. RR & Rl
2. Which of the following pattern matching algorithm does not reavires pre-processing on text or pattern [ ]
A. brute force B. Robin karp C. bayer D. knuth morris pratt
3. In boyer more algorithm, in which heuristic mismatch occurs [ ]
A. looking glass heuristic B. character jump heuristic C. basic heuristic D. boyer heuristic
4. The process of accessing data stored in a tape is similar to manipulating data on a [ ]
A. stack B. queue C.list D. Heap
5. A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 10 leaves [ ]
A. cannot have more than 19 nodes B. has exactly 19nodes
C. has exactly 17 nodes D. cannot have more than 17 nodes.
6. The order of binary search algorithm is [ ]
A. n B.n2 C. nlogn D.logn
7. The height of an AVL tree is [ ]
A. logn B. o(logn) C.toglogn D.o(n)
8. What are the actions that are performed on red Black trees with the same time complexity[ ]
A. size B. find C. insert D. both b and c
9. LLb imbalance performs [ ]
A. colour change B. rotation C. both D. none
10. AVL tree is a ____________ binary tree. [ ]
A. complete B. full C. Height balanced D. skewed
Cont…2

A
Code No: 07A3EC15 :2: Set No. 4
II Fill in the blanks:
11. The average number at inversions in an array of N distinct elements is ________
12. For merging two sorted lists of sizes m and n into a sorted list of size m+n, requires ______ no.of comparsions.
13. The time complexity of indexed search method is ________
14. The upward movement by means of swaps is conventionally called _________
15. The number of possible binary trees with 4 nodes is ____________
16. For an AVL tree, the balance factor is ________
17. The height of an m-way search tree of heigh ‘n’ with ‘n’ elements ranges from a low of ______ to a high of _______
18. The KMP algorithm, achieves a running time of _______ which is optimal in worst case.
19. In AVL tree the transformation for m ________ imbalance can be viewed as an RR rotation followed by an LL rotation.
20. The total time complexity of depth-first search traversal is ________
-oOo-