CS and IT Gate 2017 Set-1 Questions with Answer

Ques 40 Gate 2017 Set-1

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.

4 and 15 respectively

3 and 14 respectively

4 and 14 respectively

3 and 15 respectively

(Binary Search Tree) is the correct answer.

Ques 41 Gate 2017 Set-1

In a database system, unique time stamps are assigned to each transaction using Lamport’s logical clock. Let TS(T1) and TS(T2) be the time stamps of transactions T1 and T2 respectively. Besides, T1 holds a lock on the resource R, and T2 has requested a conflicting lock on the same resource R. The following algorithm is used to prevent deadlocks in the database assuming that a killed transaction is restarted with the same timestamp.

if TS(T2) <TS(T1) then
T1 is killed
else
T2 waits.

.
.
Assume any transactions that is not killed terminates eventually. Which of the following is TRUE about the database system that uses the above algorithm to prevent deadlocks?

The database system is both deadlock-free and starvation- free.

The database system is deadlock- free, but not starvation-free.

The database system is starvation-free but not deadlock- free.

The database system is neither deadlock- free nor starvation-free.

(a) is the correct answer.

Ques 42 Gate 2017 Set-1

Consider a database that has the relation schemas EMP (EmpId, EmpName, DepId), and DEPT(DeptName, DeptId). Note that the DepId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.

I. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∀ v ∈ DEPT (t[DeptId] ≠ DeptId]))}
II. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] ≠ DeptId]))}
III. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] = DeptId]))}

I and II only

I and III only

II and III only

I, II, and III

(Relational Algebra) is the correct answer.

Ques 43 Gate 2017 Set-1

The following functional dependencies hold true for the relational schema R{V, W, X, Y, Z}:

V→W
VW→X
Y→VX
Y→Z

Which of the following is irreducible equivalent for this set of functional dependencies?

V→W
V→X
Y→V
Y→Z

V→W
W→X
Y→V
Y→Z

V→W
V→X
Y→V
Y→X
Y→Z

V→W
W→X
Y→V
Y→X
Y→Z

(Functional Dependency) is the correct answer.

Ques 44 Gate 2017 Set-1

Consider the following table

Algorithms	Design Paradigms
(P) Kruskal	(i) Divide and Conquer
(Q) Quicksort	(ii) Greedy
(R) Floyed Warshall	(iii) Dynamic Programming

Match the algorithm to design paradigms they are based on:

P-(ii), Q-(iii), R-(i)

P-(iii), Q-(i), R-(ii)

P-(ii), Q-(i), R-(iii)

P-(i), Q-(ii), R-(iii)

(Algorithms) is the correct answer.

Ques 45 Gate 2017 Set-1

Consider the following functions from positives integers to real numbers

10, √n, n, log₂n, 100/n.

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

log₂n, 100/n,10, √n, n,

100/n,10,log₂n, √n, n,

10,100/n, √n,log₂n,n

100/n,log₂n, 10,√n, n,

(Complexity) is the correct answer.

Ques 46 Gate 2017 Set-1

Consider the following intermediate program in three address code

p = a - b
q = p * c
p = u * v
q = p+q

Which one of the following corresponds to a static single assignment from the above code?

p₁ = a - b
q₁ =p₁ * c
p₁= u * v
q₁ =p₁ + q₁

p₃= a - b
q₄= p₃* c
p₄= u * v
q₅ =p₄+ q₄

p₁ = a - b
q₁=p₂ * c
p₃= u * v
q₂= p₄ + q₃

p₁ = a - b
q₁= p * c
p₂= u * v
q₂= p + q

(Addressing Mode) is the correct answer.

Ques 47 Gate 2017 Set-1

When two 8-bit numbers A₇ ... A₀ and B₇ ... B₀ in 2^^s complement representation (with A₀ and B₀ as the least significant bits) are added using ripple-carry adder. the sum bits obtained are S₇ ... S₀ and the carry bits are C₇ ... C₀. An overflow is said to have occurred if

the carry bit C₇ is 1

all the carry bits (C₇, ... , C₀ ) are 1

(A₇ . B₇ . S₇' + A₇' . B₇' . S₇) is 1

(A₀ . B₀ . S₀' + A₀' . B₀' . S₀) is 1

(Complements) is the correct answer.

Ques 48 Gate 2017 Set-1

Let p, q, and r be the propositions and the expression (p -> q) -> r be a contradiction. Then, the expression (r -> p)-> q is

a tautology

a contradiction

always TRUE when p is FALSE

always TRUE when q is TRUE

(d) is the correct answer.

Ques 49 Gate 2017 Set-1

Consider the first-order logic sentence

F: ∀ x (∃ y R(x,y)).

Assuming non-empty logical domains, which of the sentences below are implied by F?

I. ∃y (∃x R(x,y))
II. ∃y (∀x R(x,y))
III. ∀y (∃x R(x,y))
IV. ∼∃x (∀y R(x,y))

II only

IV only

I and IV only

II and III only

(Pridicate Calculus) is the correct answer.

Ques 50 Gate 2017 Set-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

I only

II only

I and IV only

II and III only

(d) is the correct answer.

Ques 51 Gate 2017 Set-1

The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ______.

(271) is the correct answer.

Ques 52 Gate 2017 Set-1

Let u and v be two vectors in R² whose Euclidean norms satisfy ||u|| = 2||v||. What is the value α such that w = u + αv bisects the angle between u and v ?

1/2

-1/2

(a) is the correct answer.

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT Gate 2017 Set-1 Questions with Answer

Question Options

Sign in to ExamPrev