advanced data structures and algorithms online bits

Code No: 07A3EC20 Set No. 1
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
II B.Tech. I Sem., II Mid-Term Examinations, Oct / Nov. – 2009
ADVANCED DATA STRUCTURES AND ALGORITHMS
I. Choose the correct alternative:
1. A max heap (min heap) is a max (min) tree that is also a ______ binary tree. [ ]
a) Full b) Complete c) Extendible d) Skewed
2. Permissible balance factors are [ ]
a) –1, 0, 2 b) 0, 1, 2 c) –2, -1, 0 d) –1, 0, 1
3. Given 2 sorted list of size ‘m’ and ‘n’ respectively. The number of comparisons needed
in the worst case by the merge sort algorithm will be [ ]
a) mn b) max (m,n) c) min (m, n) d) m + n – 1
4. The _______ suggests that one can devise an algorithm that works in stages, considering one input at a time. [ ]
a) divide and conquer method b) greedy method c) backtracking approach d) heuristic search
5. The number of spanning trees in an n vertex graph can be greater than ______ [ ]
a) 2n-1 –1 b) 2n –2 c) 2n-1 –2 d) 2n-1
6. The height of the binary search tree is _____ on the average. [ ]
a) O(log n) b) O(n) c) O(n log n) d) O(n2)
7. Which of the following traversal technique lists the nodes o a binary search tree in ascending order?
[ ]
a) Post-order b) In-order c) Pre-order d) None
8. Which of the following sorting algorithm has the worst time complexity of n log n? [ ]
a) merge sort b) quick sort c) insertion sort d) selection sort
9. The height of an AVL tree with n elements/nodes is [ ]
a) O(log n) b) O(n) c) O(n log n) d) O(n2)
10. The number of passes required using k-way merging is [ ]
a) log k (N/M) b) log k (N/K) c) log k (K/M) d) log k (N)
Cont….2

A
Code No: 07A3EC20 :2: Set No. 1
II Fill in the blanks:
11. The computing time of OBST is______
12. The time complexity of Strassen’s matrix multiplication is _______
13. A graph G is ________ if and only if it contains no articulation points.
14. If P and Q are two root-to-external-node paths is a red-black tree, then ____
15. Experimental studies indicate that for random sequences of dictionary operations, ______ are actually faster than AVL trees and red-black trees are.
16. Time complexity to delete an element from max heap is _______
17. _______ sorting algorithms are designed to handle very large inputs.
18. A ____ of order m is an m-way search tree.
19. The formula for S1i in 0 / 1 knapsack problem is ______ .
20. _______ is an algorithm design method that can be used when the solution to a problem can be viewed as the result of a sequence of decisions.
-oOo-
Code No: 07A3EC20 Set No. 2
I. Choose the correct alternative:
1. The _______ suggests that one can devise an algorithm that works in stages, considering one input at a time. [ ]
a) divide and conquer method b) greedy method c) backtracking approach d) heuristic search
2. The number of spanning trees in an n vertex graph can be greater than ______ [ ]
a) 2n-1 –1 b) 2n –2 c) 2n-1 –2 d) 2n-1
3. The height of the binary search tree is _____ on the average. [ ]
a) O(log n) b) O(n) c) O(n log n) d) O(n2)
4. Which of the following traversal technique lists the nodes o a binary search tree in ascending order?
[ ]
a) Post-order b) In-order c) Pre-order d) None
5. Which of the following sorting algorithm has the worst time complexity of n log n? [ ]
a) merge sort b) quick sort c) insertion sort d) selection sort
6. The height of an AVL tree with n elements/nodes is [ ]
a) O(log n) b) O(n) c) O(n log n) d) O(n2)
7. The number of passes required using k-way merging is [ ]
a) log k (N/M) b) log k (N/K) c) log k (K/M) d) log k (N)
8. A max heap (min heap) is a max (min) tree that is also a ______ binary tree. [ ]
a) Full b) Complete c) Extendible d) Skewed
9. Permissible balance factors are [ ]
a) –1, 0, 2 b) 0, 1, 2 c) –2, -1, 0 d) –1, 0, 1
10. Given 2 sorted list of size ‘m’ and ‘n’ respectively. The number of comparisons needed
in the worst case by the merge sort algorithm will be [ ]
a) mn b) max (m,n) c) min (m, n) d) m + n – 1
Cont….2

A
Code No: 07A3EC20 :2: Set No. 2
II Fill in the blanks:
11. If P and Q are two root-to-external-node paths is a red-black tree, then ____
12. Experimental studies indicate that for random sequences of dictionary operations, ______ are actually faster than AVL trees and red-black trees are.
13. Time complexity to delete an element from max heap is _______
14. _______ sorting algorithms are designed to handle very large inputs.
15. A ____ of order m is an m-way search tree.
16. The formula for S1i in 0 / 1 knapsack problem is ______ .
17. _______ is an algorithm design method that can be used when the solution to a problem can be viewed as the result of a sequence of decisions.
18. The computing time of OBST is______
19. The time complexity of Strassen’s matrix multiplication is _______
20. A graph G is ________ if and only if it contains no articulation points.
-oOo-
Code No: 07A3EC20 Set No. 3
I. Choose the correct alternative:
1. The height of the binary search tree is _____ on the average. [ ]
a) O(log n) b) O(n) c) O(n log n) d) O(n2)
2. Which of the following traversal technique lists the nodes o a binary search tree in ascending order?
[ ]
a) Post-order b) In-order c) Pre-order d) None
3. Which of the following sorting algorithm has the worst time complexity of n log n? [ ]
a) merge sort b) quick sort c) insertion sort d) selection sort
4. The height of an AVL tree with n elements/nodes is [ ]
a) O(log n) b) O(n) c) O(n log n) d) O(n2)
5. The number of passes required using k-way merging is [ ]
a) log k (N/M) b) log k (N/K) c) log k (K/M) d) log k (N)
6. A max heap (min heap) is a max (min) tree that is also a ______ binary tree. [ ]
a) Full b) Complete c) Extendible d) Skewed
7. Permissible balance factors are [ ]
a) –1, 0, 2 b) 0, 1, 2 c) –2, -1, 0 d) –1, 0, 1
8. Given 2 sorted list of size ‘m’ and ‘n’ respectively. The number of comparisons needed
in the worst case by the merge sort algorithm will be [ ]
a) mn b) max (m,n) c) min (m, n) d) m + n – 1
9. The _______ suggests that one can devise an algorithm that works in stages, considering one input at a time. [ ]
a) divide and conquer method b) greedy method c) backtracking approach d) heuristic search
10. The number of spanning trees in an n vertex graph can be greater than ______ [ ]
a) 2n-1 –1 b) 2n –2 c) 2n-1 –2 d) 2n-1
Cont….2

A
Code No: 07A3EC20 :2: Set No. 3
II Fill in the blanks:
11. Time complexity to delete an element from max heap is _______
12. _______ sorting algorithms are designed to handle very large inputs.
13. A ____ of order m is an m-way search tree.
14. The formula for S1i in 0 / 1 knapsack problem is ______ .
15. _______ is an algorithm design method that can be used when the solution to a problem can be viewed as the result of a sequence of decisions.
16. The computing time of OBST is______
17. The time complexity of Strassen’s matrix multiplication is _______
18. A graph G is ________ if and only if it contains no articulation points.
19. If P and Q are two root-to-external-node paths is a red-black tree, then ____
20. Experimental studies indicate that for random sequences of dictionary operations, ______ are actually faster than AVL trees and red-black trees are.
-oOo-
Code No: 07A3EC20 Set No. 4
I. Choose the correct alternative:
1. Which of the following sorting algorithm has the worst time complexity of n log n? [ ]
a) merge sort b) quick sort c) insertion sort d) selection sort
2. The height of an AVL tree with n elements/nodes is [ ]
a) O(log n) b) O(n) c) O(n log n) d) O(n2)
3. The number of passes required using k-way merging is [ ]
a) log k (N/M) b) log k (N/K) c) log k (K/M) d) log k (N)
4. A max heap (min heap) is a max (min) tree that is also a ______ binary tree. [ ]
a) Full b) Complete c) Extendible d) Skewed
5. Permissible balance factors are [ ]
a) –1, 0, 2 b) 0, 1, 2 c) –2, -1, 0 d) –1, 0, 1
6. Given 2 sorted list of size ‘m’ and ‘n’ respectively. The number of comparisons needed
in the worst case by the merge sort algorithm will be [ ]
a) mn b) max (m,n) c) min (m, n) d) m + n – 1
7. The _______ suggests that one can devise an algorithm that works in stages, considering one input at a time. [ ]
a) divide and conquer method b) greedy method c) backtracking approach d) heuristic search
8. The number of spanning trees in an n vertex graph can be greater than ______ [ ]
a) 2n-1 –1 b) 2n –2 c) 2n-1 –2 d) 2n-1
9. The height of the binary search tree is _____ on the average. [ ]
a) O(log n) b) O(n) c) O(n log n) d) O(n2)
10. Which of the following traversal technique lists the nodes o a binary search tree in ascending order?
[ ]
a) Post-order b) In-order c) Pre-order d) None
Cont….2

A
Code No: 07A3EC20 :2: Set No. 4
II Fill in the blanks:
11. A ____ of order m is an m-way search tree.
12. The formula for S1i in 0 / 1 knapsack problem is ______ .
13. _______ is an algorithm design method that can be used when the solution to a problem can be viewed as the result of a sequence of decisions.
14. The computing time of OBST is______
15. The time complexity of Strassen’s matrix multiplication is _______
16. A graph G is ________ if and only if it contains no articulation points.
17. If P and Q are two root-to-external-node paths is a red-black tree, then ____
18. Experimental studies indicate that for random sequences of dictionary operations, ______ are actually faster than AVL trees and red-black trees are.
19. Time complexity to delete an element from max heap is _______
20. _______ sorting algorithms are designed to handle very large inputs.
-oOo-