# GATE CSE 2017 SET-1

 Question 1
The statement $(\neg p)\Rightarrow (\neg q)$ is logically equivalent to which of the statements below?
I. $p\Rightarrow q$
II. $q \Rightarrow p$
III. $(\neg q)\vee p$
IV. $(\neg p)\vee q$
 A I only B I and IV only C II only D II and III only
Discrete Mathematics   Propositional Logic
Question 1 Explanation:
 Question 2
Consider the first-order logic sentence $F:\forall x(\exists yR(x,y))$. Assuming non-empty logical domains, which of the sentences below are implied by F?
I. $\exists y(\exists xR(x,y))$
II. $\exists y(\forall xR(x,y))$
III. $\forall y(\exists xR(x,y))$
IV. $\neg \exists x(\forall y\neg R(x,y))$
 A IV only B I and IV only C II only D II and III only
Discrete Mathematics   Propositional Logic
Question 2 Explanation:
 Question 3
Let $c_{1}....c_{n}$ be scalars, not all zero, such that $\sum_{i=1}^{n}c_{i}a_{i}=0$
where $a_{i}$ are column vectors in $R^{n}$. Consider the set of linear equations Ax = b
where A=$a_{1}....a_{n}$ and b=$\sum_{i=1}^{n}a_{i}$. The set of equations has
 A a unique solution at $x=J_{n}$ where $J_{n}$ denotes a n-dimensional vector of all 1 B no solution C infinitely many solutions D finitely many solutions
Engineering Mathematics   Linear Algebra
Question 3 Explanation:
 Question 4
Consider the following functions from positive integers to real numbers:

$10,\sqrt{n},n, log_{2}n,\frac{100}{n}$.

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
 A $log_{2}n,\frac{100}{n}, 10,\sqrt{n},n$ B $\frac{100}{n}, 10,log_{2}n, \sqrt{n}, n$ C $10, \frac{100}{n}, \sqrt{n}, log_{2}n, n$ D $\frac{100}{n}, log_{2}n, 10, \sqrt{n}, n$
Algorithm   Asymptotic Notation
Question 4 Explanation:
 Question 5
Consider the following table:

Match the algorithms to the design paradigms they are based on.
 A P-(ii), Q-(iii),R-(i) B P-(iii), Q-(i), R-(ii) C P-(ii), Q-(i), R-(iii) D P-(i), Q-(ii), R-(iii)
Algorithm   Greedy Technique
Question 5 Explanation:
 Question 6
Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are :
Note: The height of a tree with a single node is 0.
 A 4 and 15 respectively B 3 and 14 respectively C 4 and 14 respectively D 3 and 15 respectively
Data Structure   Binary Search Tree
Question 6 Explanation:
 Question 7
The n-bit fixed-point representation of an unsigned real number real X uses f bits for the fraction part. Let i=n-f. The range of decimal values for X in this representation is
 A $2^{-f} \; to \; 2^{i}$ B $2^{-f} \; to \; (2^{i}-2^{-f})$ C $0 \; to \; 2^{i}$ D $0 \; to \; (2^{i}-2^{-f})$
Digital Logic   Number System
Question 7 Explanation:
 Question 8
Consider the C code fragment given below.

typedef struct node {
int data;
node* next ;
} node;
void join (node* m, node* n) {
node* p=n ;
while (p->next ! =NULL){
p = p -> next ;
}
p-> next = m;
}
Assuming that m and n point to valid NULL- terminated linked lists, invocation of join will
 A append list m to the end of list n for all inputs. B either cause a null pointer dereference or append list m to the end of list n. C cause a null pointer dereference for all inputs. D append list n to the end of list m for all inputs.
Data Structure   Link List
Question 8 Explanation:
 Question 9
When two 8-bit numbers $A_{7}....A_{0}$ and $B_{7}....B_{0}$ in 2's complement representation (with $A_{0}$ and $B_{0}$ as the least significant bits ) are added using a ripple-carry Combinational Circuit, the sum bits obtained are $S_{7}....S_{0}$ and the carry bits are $C_{7}....C_{0}$. An overflow is said to have occurred if
 A the carry bit $C_{7}$ is 1 B all the carry bits ($C_{7}....C_{0}$) are 1 C $(A_{7}B_{7}\bar{S_{7}}+\bar{A_{7}}\bar{B_{7}}S_{7})$ is 1 D $(A_{0}B_{0}\bar{S_{0}}+\bar{A_{0}}\bar{B_{0}}S_{0})$ is 1
Digital Logic   Combinational Circuit
Question 9 Explanation:
 Question 10
Consider the following context-free grammar over the alphabet $\sum$ = {a,b,c} with S as the start symbol.

S$\rightarrow$abScT|abcT
T$\rightarrow$bT|b

Which one of the following represents the language generated by the above grammar ?
 A {$(ab)^{n}(cb)^{n}|n\geq 1$} B {$(ab)^{n}cb^{m_{1}}cb^{m_{2}}...cb^{m_{n}}|n,m_{1},m_{2},...,m_{n}\geq 1$} C $(ab)^{n}(cb^{m})^{n}|n,m\geq 1$ D $(ab)^{n}(cb^{n})^{m}|n,m\geq 1$
Theory of Computation   Context Free Grammar
Question 10 Explanation:
There are 10 questions to complete.