University : Kerala University
Course : BCA Degree Examinations
Subject of Question Paper : Oops and Data Structures
Semester : III
Year of Question Paper : Jan. 2015
Kerala University
BCA Degree Third Semester Examination January 2015
Oops and Data Structures
Section A (Objective Type Questions) 20 questions of 1 mark each
1. A complete binary tree of level 4 has how many nodes?
(a) 14
(b) 15
(c) 16
(d) 20
2. The maximum number of nodes on level i of a binary tree is
(a) i+1
(b) 2i+1
(c) 2i.1
(d) 3i.1
3. Which of the following sorting algorithm has the lowest worst-case complexity?
(a) Merge sort
(b) Quick sort
(c)Bubble sort
(d) Selection sort
4. Which one of the following is the difference between a binary tree and a BST?
(a) A binary tree is a BST
(b) The number of nodes at level i of a BST is more than the number nodes in binary tree.
(c) The left child of BST is less than or equal to root but this is not in case of binary tree.
(d) None of the above.
5. Which of the following is not a traversal technique?
(a) In-order traversal
(b) Out-order traversal
(c) Pre-order traversal
(d) None of the above
6. What is the running time of in-order traversal in case of BST?
(a) O (n log n) (b) O (n^2) (c) O (n) (d) None of the above
7. In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is
(a) nk
(b) n (k-1)
(c) n (k-1)+1
(d) None of the above
8. Post-order traversal of a given BST produces the following sequence of keys: 10,9,23,22,27,25,15,50,95,60,40,29.
Which of the following sequences of keys can be the result of an in-order traversal of BST?
(a) 9,10,15,22,23,25,27,29,40,50,60,29
(b) 9,10,15,22,40,50,60,95,23,25,27,29
(c) 29,15,9,10,25,22,23,27,40,60,50,95
(d) 95,50,60,40,27,23,22,25,10,9,15,29
9. Which of the following is a valid sequence of elements in array representing a max-heap?
(a) 1,3,5,6,8,9
(b) 9,6,3,1,8,5
(c) 9,3,6,8,5,1
(d) 9,5,6,8,3,1
10. The height of the binary tree is the maximum number of edges in any root to the leaf path. The maximum number of nodes in a binary tree of height h is
(a) 2h
(b) 2h-1-1
(c) 2h+1-1
(d) 2h+1
11. The maximum number of binary trees that can be formed with three unlabeled nodes is
(a) 1
(b) 5
(c) 4
(d) 3
12. The in-order and post-order traversal of a binary tree are "d b e a f c g" and "a b d e c f g" respectively. The post-order traversal of the binary tree is
(a) d e b f g c a
(b) e d b g f c a
(c) e d b f g c a
(d) d e f g b c a
13. Which of the following is not a comparison based sorting algorithm
(a) Bubble sort
(b) Quick sort
(c) Heap Sort
(d) Radix sort
14. Which of the following is a non-comparison based sorting algorithm
(a) Radix sort
(b) Counting sort
(c) Bucket sort
(d) All of these
15. What is the best case time complexity of Bubble sort?
(a) O (n log n)
(b) O (n^2)
(c) O(n)
(d) None of these
16. What is the worst case running time of Insertion sort?
(a) O (n log n)
(b) O(n^2)
(c) O (log n)
(d) O (1)
17. Find out the floor of 4.99.
(a) 4
(b) 5
(c) 4.5
(d) 5.5
18. Determine the ceil of 5.99999.
(a) 6
(b) 5
(c) 4
(d) None of these
19. Which of the following property a B-Tree of order m doesn't satisfy?
(a) The number of keys in each non-leaf node is one less than the number of its children.
(b) All leaves are on the same level.
(c) All non-leaf nodes except the root have at least m/2 children.
(d) A leaf node contains no more than m-1 keys.
20. Which of the following is the property of AVL tree?
(a) Each node satisfies BST property.
(b) Each node satisfies height-balanced 1 tree property.
(c) The difference between the heights of the left sub tree and the right sub tree of the node doesn't exceed one.
(d) All of these
Section B
(Fill in the blanks) 5 questions of 1 mark each
1. The average case running time of Quick sort is
2. The running time of extracting maximum element from a max-heap is
3. The running time of MAX-HEAPIFY procedure is
4. The running time of BUILDING-MAX-HEAP procedure takes
5. The asymptotic representation of the function f(n) = 10n^3+3n^2+20n+1 is
Section C
(True/False) 5 questions of 1 mark each
1. The best case running time of Insertion sort is O (n).
2. The worst case running time of Merge sort is O(n^2).
3. An AVL tree is a binary search tree.
4. A binary tree is called a complete binary tree if at every level of the tree contains 2i number of nodes.
5. If i is the index of a non-root node in the array representation of Heap, then the parent of that node is at index (i-1)/2.
Section D
(Descriptive Type Question) 2 questions of 10 marks each
1. Write the steps for Insertion sort algorithm to sort the elements in decreasing order & apply it on the array A = <1, 2, 3, 4, 5>
2. Write the property of BST. Write the algorithm for In-order and Pre-order BST traversal.
3. Perform Heap Sort on the array A= < 4, 9, 20, 12, 14, 23, 15>and find its lower bound.
Course : BCA Degree Examinations
Subject of Question Paper : Oops and Data Structures
Semester : III
Year of Question Paper : Jan. 2015
Kerala University
BCA Degree Third Semester Examination January 2015
Oops and Data Structures
Section A (Objective Type Questions) 20 questions of 1 mark each
1. A complete binary tree of level 4 has how many nodes?
(a) 14
(b) 15
(c) 16
(d) 20
2. The maximum number of nodes on level i of a binary tree is
(a) i+1
(b) 2i+1
(c) 2i.1
(d) 3i.1
3. Which of the following sorting algorithm has the lowest worst-case complexity?
(a) Merge sort
(b) Quick sort
(c)Bubble sort
(d) Selection sort
4. Which one of the following is the difference between a binary tree and a BST?
(a) A binary tree is a BST
(b) The number of nodes at level i of a BST is more than the number nodes in binary tree.
(c) The left child of BST is less than or equal to root but this is not in case of binary tree.
(d) None of the above.
5. Which of the following is not a traversal technique?
(a) In-order traversal
(b) Out-order traversal
(c) Pre-order traversal
(d) None of the above
6. What is the running time of in-order traversal in case of BST?
(a) O (n log n) (b) O (n^2) (c) O (n) (d) None of the above
7. In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is
(a) nk
(b) n (k-1)
(c) n (k-1)+1
(d) None of the above
8. Post-order traversal of a given BST produces the following sequence of keys: 10,9,23,22,27,25,15,50,95,60,40,29.
Which of the following sequences of keys can be the result of an in-order traversal of BST?
(a) 9,10,15,22,23,25,27,29,40,50,60,29
(b) 9,10,15,22,40,50,60,95,23,25,27,29
(c) 29,15,9,10,25,22,23,27,40,60,50,95
(d) 95,50,60,40,27,23,22,25,10,9,15,29
9. Which of the following is a valid sequence of elements in array representing a max-heap?
(a) 1,3,5,6,8,9
(b) 9,6,3,1,8,5
(c) 9,3,6,8,5,1
(d) 9,5,6,8,3,1
10. The height of the binary tree is the maximum number of edges in any root to the leaf path. The maximum number of nodes in a binary tree of height h is
(a) 2h
(b) 2h-1-1
(c) 2h+1-1
(d) 2h+1
11. The maximum number of binary trees that can be formed with three unlabeled nodes is
(a) 1
(b) 5
(c) 4
(d) 3
12. The in-order and post-order traversal of a binary tree are "d b e a f c g" and "a b d e c f g" respectively. The post-order traversal of the binary tree is
(a) d e b f g c a
(b) e d b g f c a
(c) e d b f g c a
(d) d e f g b c a
13. Which of the following is not a comparison based sorting algorithm
(a) Bubble sort
(b) Quick sort
(c) Heap Sort
(d) Radix sort
14. Which of the following is a non-comparison based sorting algorithm
(a) Radix sort
(b) Counting sort
(c) Bucket sort
(d) All of these
15. What is the best case time complexity of Bubble sort?
(a) O (n log n)
(b) O (n^2)
(c) O(n)
(d) None of these
16. What is the worst case running time of Insertion sort?
(a) O (n log n)
(b) O(n^2)
(c) O (log n)
(d) O (1)
17. Find out the floor of 4.99.
(a) 4
(b) 5
(c) 4.5
(d) 5.5
18. Determine the ceil of 5.99999.
(a) 6
(b) 5
(c) 4
(d) None of these
19. Which of the following property a B-Tree of order m doesn't satisfy?
(a) The number of keys in each non-leaf node is one less than the number of its children.
(b) All leaves are on the same level.
(c) All non-leaf nodes except the root have at least m/2 children.
(d) A leaf node contains no more than m-1 keys.
20. Which of the following is the property of AVL tree?
(a) Each node satisfies BST property.
(b) Each node satisfies height-balanced 1 tree property.
(c) The difference between the heights of the left sub tree and the right sub tree of the node doesn't exceed one.
(d) All of these
Section B
(Fill in the blanks) 5 questions of 1 mark each
1. The average case running time of Quick sort is
2. The running time of extracting maximum element from a max-heap is
3. The running time of MAX-HEAPIFY procedure is
4. The running time of BUILDING-MAX-HEAP procedure takes
5. The asymptotic representation of the function f(n) = 10n^3+3n^2+20n+1 is
Section C
(True/False) 5 questions of 1 mark each
1. The best case running time of Insertion sort is O (n).
2. The worst case running time of Merge sort is O(n^2).
3. An AVL tree is a binary search tree.
4. A binary tree is called a complete binary tree if at every level of the tree contains 2i number of nodes.
5. If i is the index of a non-root node in the array representation of Heap, then the parent of that node is at index (i-1)/2.
Section D
(Descriptive Type Question) 2 questions of 10 marks each
1. Write the steps for Insertion sort algorithm to sort the elements in decreasing order & apply it on the array A = <1, 2, 3, 4, 5>
2. Write the property of BST. Write the algorithm for In-order and Pre-order BST traversal.
3. Perform Heap Sort on the array A= < 4, 9, 20, 12, 14, 23, 15>and find its lower bound.
0 comments:
Pen down your valuable important comments below