CS and IT GATE 2017 Set-1 Questions with Answer

Ques 40 Data Structure

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

Ques 41 DBMS

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.

Ques 42 DBMS

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

Ques 43 DBMS

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

Ques 44 Design Algorithm Analysis

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)

Ques 45 Design Algorithm Analysis

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,

Ques 46 Design Algorithm Analysis

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

Ques 47 Digital Logic Design

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

Ques 48 Discrete Mathematics

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

Ques 49 Discrete Mathematics

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

Ques 50 Discrete Mathematics

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

Ques 51 Mathematics

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 Mathematics

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

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT GATE 2017 Set-1 Questions with Answer