1
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the sequence obtained would be
A
8, 7, 6, 5, 4, 3, 2, 1
B
1, 2, 3, 4, 8, 7, 6, 5
C
2, 1, 4, 3, 6, 7, 8, 5
D
2, 1, 4, 3, 7, 8, 6, 5
2
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
A
10, 8, 7, 5, 3, 2, 1
B
10, 8, 7, 2, 3, 1, 5
C
10, 8, 7, 1, 2, 3, 5
D
10, 8, 7, 3, 2, 1, 5
3
GATE CSE 2004
MCQ (Single Correct Answer)
+2
-0.6
Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?
i) preorder and postorder
ii) inorder and postorder
iii) preorder and inorder
iv) level order and postorder
A
(i) only
B
(ii), (iii)
C
(iii) only
D
(iv) only
4
GATE CSE 2004
MCQ (Single Correct Answer)
+2
-0.6
A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{ no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x } then the worst-case time complexity of the program is
A
$$\Theta (n)$$
B
$$\Theta (n \log n)$$
C
$$\Theta(n^2)$$
D
$$\Theta (n^2\log n)$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP