CS/IT Gate Subject

Aptitude and Reasoning
Engineering Mathematics
C Programming
Data Structure
Design Algorithm Analysis
Operating System
Computer Network
Digital Logic Design
Compiler Design
Database Management System
Theory of Computation

Data Structure GATE CS and IT previous year questions with Answer

Ques 11 Gate 2020

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree ?

10, 11, 12, 15, 16, 18, 19, 20

11, 12, 10, 16, 19, 18, 20, 15

20, 19, 18, 16, 15, 12, 11, 10

19, 16, 18, 20, 11, 12, 10, 15

Ques 12 Gate 2020

Let G=(V,E) be a directed, weighted graph with weight function w:E→R.
For some function f:V→R, for each edge (u,v)∈E, define w′(u,v) as w(u,v)+f(u)−f(v).
Which one of the options completes the following sentence so that it is TRUE ? “The shortest paths in G under w are shortest paths under w′ too, _________”.

for every f:V→R

if and only if ∀u∈V, f(u) is positive

if and only if ∀u∈V, f(u) is negative

if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G

Ques 13 Gate 2020

Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB. The size of search key is 12 bytes and the size of tree/disk pointer is 8 bytes. Assume that the database has one million records. Also assume that no node of the B+ tree and no records are present initially in main memory. Consider that each record fits into one disk block. The minimum number of disk accesses required to retrieve any record in the database is ___________ .

4 is the correct answer.

Ques 14 Gate 2020

Graph G is obtained by adding vertex s to K_3,4 and making s adjacent to every vertex of K_3,4 . The minimum number of colours required to edge-colour G is _________ .

7 is the correct answer.

Ques 15 Gate 2020

Consider a graph G=(V, E), where V = { v₁,v₂,…,v₁₀₀ }, E={ (v_i, v_j) ∣ 1<=i<j<=100 is ∣ i–j ∣ . The weight of minimum spanning tree of G is ________ .

99 is the correct answer.

Ques 16 Gate 2020

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _________

511 is the correct answer.

Ques 17 Gate 2020

Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23, and the secondary hash function is h2(k) = 1+(k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ________

13 is the correct answer.

Ques 18 Gate 2019

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) ___________ .

4.24 to 4.26 is the correct answer.

Ques 19 Gate 2019

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 20 Gate 2019

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