Q. 11 – Q. 35 carry one mark each.
11. If
g(x)=1−x and h(x)=x/x-1, then g(h(x))/h(g(x)) is:
(A) h(x)/g(x) (B)
-1/x
(C) g(x)/h(x) (D)
x/(1-x)2
Answer: A
Explanation:
g(h(x)) = g(x/(x-1)) = 1 - x/(x-1) = -1/(x-1)
h(g(x)) = h(1-x) = (1-x)/((1-x)-1) = -(1-x)/x
g(h(x)) / h(g(x)) = [-1/(x-1)] / [-(1-x)/x]
= -x/(x-1)2
h(x) / g(x) = [x/(x-1)] / (1-x) = [x/(x-1)] /
-(x-1)
=
-x/(x-1)2
So answer is option (A).
12. Limx→∞ x1/x is
(A) ∞ (B)
0
(C) 1 (D)
Not defined
Answer: C
Explanation:
x1/x =
e1/x log x
limx→∞ x1/x = limx→∞ e1/x
log x
=
e ^ limx→∞1/x
log x
=
e^0 [numerator = finite, denominator = infinite and finite/infinite = 1/∞ = 0]
=
1
13. Match
the following:
(P) Prim’s algorithm for minimum spanning
tree (i) Backtracking
(Q) Floyd-Warshall algorithm for all pairs
shortest paths (ii) Greedy method
(R) Mergesort (iii)
Dynamic programming
(S) Hamiltonian circuit (iv)
Divide and conquer
(A) P-iii, Q-ii, R-iv, S-i
(B) P-i, Q-ii, R-iv, S-iii
(C) P-ii, Q-iii, R-iv, S-i
(D) P-ii, Q-i, R-iii, S-iv
Answer: C
14. Which
one of the following is the recurrence equation for the worst case time complexity
of the Quicksort algorithm for sorting (≥2) numbers? In the recurrence
equations given in the options below, c
is
a constant.
(A) T(n) = 2T(n/2) + cn
(B) T(n) = T(n-1) + T(1) + cn
(C) T(n) = 2T(n-1) + cn
(D) T(n) = T(n/2) + cn
Answer: B
Explanation:
When the pivot is the smallest or largest
element at partitioning on a block of size n the result yields
(i) one empty sub-block.
(ii) one element (pivot) in the correct place.
(iii) one sub block of size n-1.
Hence recurrence relation T(n) = T(n-1)+T(1)+Cn
15. The
height of a tree is the length of the longest root-to-leaf path in it. The
maximum and minimum number of nodes in a binary tree of height 5 are
(A) 63 and 6, respectively (B) 64 and 5, respectively
(C) 32 and 6, respectively (D) 31 and 5, respectively
Answer: A
Explanation:
Maximum number of nodes is possible in a
binary tree, if maximum number of nodes are present in each level. Thus,
maximum number of nodes in a binary tree of height h is 2h+1 – 1.
A binary tree has minimum number of nodes, if
each level has minimum number of nodes. Minimum nodes possible at every level
is only one when every parent has one child. Such kind of trees are called skew
binary trees. A skew binary tree of height h has h+1 nodes.
16. Match
the following:
(P) Condition coverage (i) Black-box testing
(Q) Equivalence class partitioning (ii) System testing
(R) Volume testing (iii) White-box testing
(S) Alpha testing (iv) Performance testing
(A) P-ii, Q-iii, R-i, S-iv (B) P-iii, Q-iv, R-ii, S- i
(C) P-iii, Q-i, R-iv, S-ii (D) P-iii, Q-i, R-ii, S-iv
Answer: C
17. Which
of the following is/are correct inorder traversal sequence(s) of binary search
tree(s)?
I. 3, 5, 7, 8, 15, 19, 25
II. 5, 8, 9, 12, 10, 15, 25
III. 2, 7, 10, 8, 14, 16, 20
IV. 4, 6, 7, 9 18, 20, 25
(A) I and IV only (B) II and III only
(C) II and IV only (D) II only
Answer: A
18. Which
one of the following is TRUE at any valid state in shift-reduce parsing?
(A) Viable prefixes appear only at the bottom
of the stack and not inside
(B) Viable prefixes appear only at the top of
the stack and not inside
(C) The stack contains only a set of viable
prefixes
(D) The stack never contains viable prefixes
Answer: C
19. Which
one of the following is NOT equivalent to p ↔ q?
(A) (┐p ˅ q) ˄ (p ˅ ┐q) (B) (┐p ˅ q) ˄ (q → p)
(C) (┐p ˄ q) ˅ (p ˄ ┐q) (D) (┐p ˄ ┐q) ˅ (p ˄ q)
Answer: C
20. For
a set A the power set of A
is denoted by 2A. If A={5,{6},{7}},
which of the following options are TRUE?
I. ∅∈2A
II. ∅⊆2A
III. {5,{6}}∈2A
IV. {5,{6}}⊆2A
(A) I and III only (B) II and III only
(C) I, II and III only (D) I, II and IV only
Answer: C
0 Comments