CS and IT GATE 2019 Questions with Answer

Ques 27 Data Structure

Consider the following statements:

I. The smallest element in a max-heap is always at a leaf node.
II. The second largest element in a max-heap is always a child of the root node.
III. A max-heap can be constructed from a binary search tree in Θ(n) time.
IV. A binary search tree can be constructed from a max-heap in Θ(n) time.

Which of the above statements is/are TRUE?

I, II and III

I, III and IV

I, II and IV

II, III and IV

Ques 28 Data Structure

Let G be any connection, weighted, undirected graph:

I. G has a unique minimum spanning tree if no two edges of G have the same weight.
II. G has a unique minimum spanning tree if, for every cut G, there is a unique minimum weight edge crossing the cut.

Which of the above two statements is/are TRUE?

I only

II only

Both I and II

Neither I nor II

Ques 29 Data Structure

Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?

B+ Tree is a height-balanced tree.

Non-leaf nodes have pointers to data records.

Key values in each node are kept in sorted order.

Ques 30 Data Structure

Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

(n-1)!

^(n-1)!/₂

Ques 31 DBMS

Consider the following two statements about database transaction schedules:

I. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable.
II. Timestamp-ordering concurrency control protocol with Thomas’ Write Rule can generate view serializable schedules that are not conflict serializable.

Which of the above statements is/are TRUE?

I only

II only

Both I and II

Neither I nor II

Ques 32 DBMS

Let the set of functional dependencies F = {QR → S, R → P, S → Q} hold on a relation schema X = (PQRS). X is not in BCNF. Suppose X is decomposed into two schemas and Z where Y = (PR) and Z = (QRS).
Consider the two statements given below:

I. Both Y and Z are in BCNF
II. Decomposition of X into Y and Z is dependency preserving and a lossless.

Which of the above statements is/are correct?

Both I and II

Neither I nor II

I only

II only

Ques 33 Design Algorithm Analysis

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum ∑^j_k=iA[k]. Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)

a is the correct answer.

Ques 34 Design Algorithm Analysis

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _________.

a is the correct answer.

Ques 35 Design Algorithm Analysis

There are n unsorted arrays: A₁, A₂, ....,A_n. Assume that n is odd. Each of A₁, A₂, ...., A_n contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A₁ ,A₂, ....,A_n is ________ .

Ο(n)

Ο(n²)

Ο(n log n)

Ω(n²log n)

Ques 36 Digital Logic Design

In 16-bit 2’s complement representation, the decimal number −28 is:

1111 1111 0001 1100

0000 0000 1110 0100

1111 1111 1110 0100

1000 0000 1110 0100

Ques 37 Digital Logic Design

What is the minimum number of 2-input NOR gates required to implement 4-variable function expressed in sum-of-minterms from as f = Σ(0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available. Answer ________

3 is the correct answer.

Ques 38 Digital Logic Design

Two numbers are chosen independently and uniformly at random from the set {1, 2, ..., 13}. The probability (rounded off to 3 decimal places) that their 4-bit (unsigned) binary representations have the same most significant bit is ___________.

a is the correct answer.

Ques 39 Discrete Mathematics

Let G be an arbitrary group. Consider the following relations on G:

R₁: ∀a, b ∈ G, aR₁b if and only if ∃g ∈ G such that a = g^-1bg
R₂: ∀a, b ∈ G, aR₂b if and only if a = b^-1

Which of the above is/are equivalence relation/relations?

R1 and R2

R1 only

R2 only

Neither R1 nor R2

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT GATE 2019 Questions with Answer