# GATE CSE 2015 SET-1

 Question 1
If $g(x)=1-x$ and $h(x)=\frac{x}{x-1}$, then $\frac{g(h(x))}{h(g(x))}$ is:
 A $\frac{h(x)}{g(x)}$ B $\frac{-1}{x}$ C $\frac{g(x)}{h(x)}$ D $\frac{x}{(1-x)^{2}}$
Discrete Mathematics   Functions
Question 1 Explanation:
 Question 2
$\lim_{x\rightarrow \infty }x^{1/x}$ is
 A $\infty$ B 0 C 1 D Not defined
Engineering Mathematics   Calculus
Question 2 Explanation:
 Question 3
Match the following:
 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
Algorithm   Divide and Conquer
Question 3 Explanation:
 Question 4
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( $\geq$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
Algorithm   Sorting
Question 4 Explanation:
 Question 5
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
Data Structure   Binary Tree
Question 5 Explanation:
 Question 6
Match the following:
 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
Software Engg
Question 6 Explanation:
 Question 7
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
Data Structure   Binary Search Tree
Question 7 Explanation:
 Question 8
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
Compiler Design   Parsing
Question 8 Explanation:
 Question 9
Which one of the following is NOT equivalent to $p\leftrightarrow q$?
 A $(\neg p\vee q)\wedge (p\vee \neg q)$ B $(\neg p\vee q)\wedge (q \rightarrow p)$ C $(\neg p \wedge q)\vee (p \wedge \neg q)$ D $(\neg p \wedge \neg q)\vee (p \wedge q)$
Discrete Mathematics   Propositional Logic
Question 9 Explanation:
 Question 10
For a set A, the power set of A is denoted by $2^{A}$. If A={5,{6},{7}}, which of the following options are TRUE?
I. $\phi \in 2^{A}$
II. $\phi \subseteq 2^{A}$
III. {5,{6}} $\in 2^{A}$
IV. {5,{6}}$\subseteq 2^{A}$
 A I and III only B II and III only C I, II and III only D I, II and IV only
Discrete Mathematics   Set Theory
Question 10 Explanation:
There are 10 questions to complete.