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 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 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 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 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 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 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 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 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 10
Consider the following context-free grammar over the alphabet \sum = {a,b,c} with S as the start symbol.

S\rightarrowabScT|abcT
T\rightarrowbT|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
There are 10 questions to complete.

Leave a Comment