CS and IT GATE 2015 Set-1 Questions with Answer

Ques 14 Computer Networks

Suppose that the stop-and-wait protocol is used on a link with a bit rate of 64 kilobits per second and 20 milliseconds propagation delay. Assume that the transmission time for the acknowledgement and the processing time at nodes are negligible. Then the minimum frame size in bytes to achieve a link utilization of at least 50% is _______.

Ques 15 Computer Organization and Architecture

Consider a non-pipelined processor with a clock rate of 2.5 gigahertz and average cycles per instruction of four. The same processor is upgraded to a pipelined processor with five stages, but due to the internal pipeline delay, the clock speed is reduced to 2 gigahertz. Assume that there are no stalls in the pipeline. The speed up achieved in this pipelined processor is _______.

Ques 16 Data Structure

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

Ques 17 Data Structure

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

Ques 18 Data Structure

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?

I. 3, 5, 7, 8, 15, 19, 25
II. 5, 8, 9, 12, 10, 15, 25
III. 2, 7, 10, 8, 14, 16, 20
IV. 4, 6, 7, 9, 18, 20, 25

Ques 19 Data Structures and Algorithms

Consider a max heap, represented by the array:

Ques 20 Data Structures and Algorithms

Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is _______.

Ques 21 Data Structures and Algorithms

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x ∈ V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u) - d(v)?

Ques 22 Data Structures and Algorithms

An algorithm performs √(log N) find operations, N insert operations, √(log N) delete operations, and (log N)^1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

Ques 23 Data Structures and Algorithms

The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is _______.

Ques 24 Data Structures and Algorithms

Consider the following C function.

Ques 25 Databases

Consider an Entity-Relationship (ER) model in which entity sets E₁ and E₂ are connected by an m:n relationship R₁₂. E₁ and E₃ are connected by a 1:n (1 on the side of E₁ and n on the side of E₃) relationship R₁₃. E₁ has two single-valued attributes a₁₁ and a₁₂ of which a₁₁ is the key attribute. E₂ has two single-valued attributes a₂₁ and a₂₂ of which a₂₁ is the key attribute. E₃ has two single-valued attributes a₃₁ and a₃₂ of which a₃₁ is the key attribute. The relationships do not have any attributes. If a relational model is derived from the above ER model, then the minimum number of relations that would be generated if all the relations are in 3NF is _______.

Ques 26 Databases

Consider the following relations: