# GATE Computer Science and IT Solved Paper 2015 Session 1 - Part 2

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
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
12.       Limx→∞ x1/x is
(A) ∞                   (B) 0
(C) 1                   (D) Not defined
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
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
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
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
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
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
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)