CS/IT Gate Yearwise 


CS and IT Gate 2020 Questions with Answer

Ques 27 Gate 2020

Consider the following grammar.

S → aSB ∣ d
B → b

The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is ________ .


(7) is the correct answer.

Ques 28 Gate 2020

Consider the following statements about the functionality of an IP based router.

I. A router does not modify the IP packets during forwarding.
II. It is not necessary for a router to implement any routing protocol.
III. A router should reassemble IP fragments if the MTU of the outgoing link is larger than the size of the incoming IP packet.

Which of the above statements is/are TRUE ?

A

I and II only

B

I only

C

II and III only

D

II only


(d) is the correct answer.

Ques 29 Gate 2020

Consider a TCP connection between a client and a server with the following specifications; the round trip time is 6 ms, the size of the receiver advertised window is 50 KB, slow-start threshold at the client is 32 KB, and the maximum segment size is 2 KB. The connection is established at time t=0. Assume that there are no timeouts and errors during transmission. Then the size of the congestion window (in KB) at time t+60 ms after all acknowledgements are processed is _________ .


(44) is the correct answer.

Ques 30 Gate 2020

Assume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the browser is configured to send HTTP requests in non-persistent mode. The web page contains text and five very small images. The minimum number of TCP connections required to display the web page completely in your browser is ________ .


(6) is the correct answer.

Ques 31 Gate 2020

In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b] ? Assume that the number of reported elements is k.

A

Θ(log n)

B

Θ(log(n)+k)

C

Θ(k log n)

D

Θ(n log k)


(b) is the correct answer.

Ques 32 Gate 2020

Let G = (V, G) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighed edge (u, v) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

A

Θ(∣E∣ + ∣V∣)

B

Θ(∣E∣.∣V∣)

C

Θ(E∣ log ∣V∣)

D

Θ(∣V∣)


(d) is the correct answer.

Ques 33 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 ?

A

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

B

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

C

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

D

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


(b) is the correct answer.

Ques 34 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, _________”.

A

for every f:V→R

B

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

C

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

D

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


(a) is the correct answer.

Ques 35 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 36 Gate 2020

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


(7) is the correct answer.

Ques 37 Gate 2020

Consider a graph G=(V, E), where V = { v1,v2,…,v100 }, E={ (vi, vj) ∣ 1<=i<j<=100 is ∣ i–j ∣ . The weight of minimum spanning tree of G is ________ .


(99) is the correct answer.

Ques 38 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 39 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.

Unique Visitor Count

Total Unique Visitors

Loading......

Question Options

Contributed by: