GATE Computer Science Solved Paper 2017 Session I - Part 1

1.       The statement (¬p) (¬q) is logically equivalent to which of the statements below?
I. p⇒q
II. q⇒p
III. (¬q) p
IV. (¬p) q
(A) I only
(B) I and IV only
(C) II only
(D) II and III only
Answer: D
2.       Consider the first-order logic sentence F: x(yR(x,y)). Assuming non-empty logical domains, which of the sentences below are implied by F?
I. y(xR(x,y))
II. y(xR(x,y))
III. ∀y(xR(x,y))
IV. ¬∃x(∀y¬R(x,y))
(A) IV only
(B) I and IV only
(C) II only
(D) II and III only
Answer: B
3.       Let c1,...,cn be scalars, not all zero, such that
where ai are column vectors in Rn.
Consider the set of linear equations
where A=[a1,...,an] and
The set of equations has
(A) a unique solution at x=Jn where Jn denotes a n-dimensional vector of all 1
(B) no solution
(C) infinitely many solutions
(D) finitely many solutions
Answer: C
4.       Consider tile following functions from positive integers to real numbers:
10, √n, n, log2n, 100/n
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
(A) log2n, 100/n, 10, √n, n
(B) 100/n, 10, log2n, √n, n
(C) 10, 100/n, √n, log2n, n
(D) 100/n, log2n, 10, √n, n,
Answer: B
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)
Answer: C

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
Answer: B
7.       The n-bit fixed-point representation of an unsigned real number 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 2i
(B) 2-f to (2i – 2-f)
(C) 0 to 2i
(D) 0 to (2i – 2-f)
Answer: D
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.
Answer: B
9.       When two 8-bit numbers A7...A0 and B7...B0 in 2’s complement representation (with A0 and B0 as the least significant bits) are added using a ripple-carry adder, the sum bits obtained are S7...S0 and the carry bits are C7...C0. An overflow is said to have occurred if
Answer: C
10.    Consider the following context-free grammar over the alphabet ∑ = (a, b, c) with S as the start symbol:
S→abScT | abcT
T→bT | b
Which one of the following represents the language generated by the above grammar?
(A) {(ab)n(cb)n | n≥1)
(B) {(ab)ncbm1cbm2 ... ,cbmn | n, m1, m2, ..., mn ≥ 1)
(C) ((ab)n (cbm)n | m, n ≥ 1 }
(D) {(ab)n(cbn)m | m, n ≥ 1 }
Answer: B

Pages   2   3   4   5 

Post a Comment