CS and IT GATE 2020 Questions with Answer

Ques 27 Compiler Design

Consider the following grammar.

Ques 28 Computer Network

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 ?

Ques 29 Computer Network

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 _________ .

Ques 30 Computer Network

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 ________ .

Ques 31 Data Structure

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.

Ques 32 Data Structure

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

Ques 33 Data Structure

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 ?

Ques 34 Data Structure

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

Ques 35 Data Structure

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 ___________ .

Ques 36 Data Structure

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 _________ .

Ques 37 Data Structure

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 ________ .

Ques 38 Data Structure

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 _________

Ques 39 Data Structure

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 ________