CS and IT Gate 2015 Set-1 Questions with Answer

Ques 14 GATE 2015 SET-1

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

(160) is the correct answer.

Ques 15 GATE 2015 SET-1

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

(3.2) is the correct answer.

Ques 16 Gate 2015 Set-1

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

63 and 6, respectively

64 and 5, respectively

32 and 6, respectively

31 and 5, respectively

(Tree ) is the correct answer.

Ques 17 Gate 2015 Set-1

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

Θ(logn) for both insertion and deletion

Θ(n) for both insertion and deletion

Θ(n) for insertion and Θ(logn) for deletion

Θ(logn) for insertion and Θ(n) for deletion

(Binary Search Tree) is the correct answer.

Ques 18 Gate 2015 Set-1

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

I and IV only

II and III only

II and IV only

II only

(Tree Traversal) is the correct answer.

Ques 19 GATE 2015 SET-1

Consider a max heap, represented by the array:

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

40, 30, 20, 10, 15, 16, 17, 8, 4, 35

40, 35, 20, 10, 30, 16, 17, 8, 4, 15

40, 30, 20, 10, 35, 16, 17, 8, 4, 15

40, 35, 20, 10, 15, 16, 17, 8, 4, 30

(d) is the correct answer.

Ques 20 GATE 2015 SET-1

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

(24) is the correct answer.

Ques 21 GATE 2015 SET-1

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)?

-1

(d) is the correct answer.

Ques 22 GATE 2015 SET-1

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?

Unsorted array

Min-heap

Sorted array

Sorted doubly linked

Ques 23 GATE 2015 SET-1

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

(69) is the correct answer.

Ques 24 GATE 2015 SET-1

Consider the following C function.

Which one of the following most closely approximates the return value of the function fun1?

n³

n(log n)²

n log n

n log(log n)

(d) is the correct answer.

Ques 25 GATE 2015 SET-1

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

(4) is the correct answer.

Ques 26 GATE 2015 SET-1

Consider the following relations:

Consider the following SQL query.
SELECT S.Student_Name, sum(P.Marks)
FROM Student S, Performance P
WHERE S.Roll_No = P.Roll_No
GROUP BY S.Student_Name
The number of rows that will be returned by the SQL query is _______.

(2) is the correct answer.

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT Gate 2015 Set-1 Questions with Answer

Question Options

Sign in to ExamPrev