CS/IT Gate Yearwise 


CS and IT Gate 2016 Set-1 Questions with Answer

Ques 27 Gate 2016 Set-1

For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of 1 megabyte and the maximum output rate is 20 megabytes per second. Tokens arrive at a rate to sustain output at a rate of 10 megabytes per second. The token bucket is currently full and the machine needs to send 12 megabytes of data. The minimum time required to transmit the data is _________________ seconds.


(a) is the correct answer.

Ques 28 Gate 2016 Set-1

Consider that B wants to send a message m that is digitally signed to A. Let the pair of private and public keys for A and B be denoted by K-x and K+x
for x = A,B, respectively. Let Kx(m)
represent the operation of encrypting m with a key Kx and H(m) represent the message digest.
Which one of the following indicates the CORRECT way of sending the message m along with the digital signature to A?

A

{m,K+B (H(m))}

B

{m,K-B (H(m))}

C

{m,K-A (H(m))}

D

{m,K+A (H(m))}


(Cryptography) is the correct answer.

Ques 29 Gate 2016 Set-1

Which of the following is/are example(s) of stateful application layer protocols?

(i) HTTP
(ii) FTP
(iii) TCP
(iv) POP3

A

(i) and (ii) only

B

(ii) and (iii) only

C

(ii) and (iv) only

D

(iv) only


(Protocal) is the correct answer.

Ques 30 Gate 2016 Set-1

Which one of the following protocols is NOT used to resolve one form of address to another one?

A

DNS

B

ARP

C

DHCP

D

RARP


(IP Address) is the correct answer.

Ques 31 Gate 2016 Set-1

Which one of the following protocols is NOT used to resolve one form of address to another one?

A

DNS

B

ARP

C

DHCP

D

RARP


(IP Address) is the correct answer.

Ques 32 Gate 2016 Set-1

Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below.

while Q is not Empty do
    if S is Empty OR Top(S) ≤ Head(Q) then
        x := Dequeue(Q);
        Push(S, x);
    else
        x := Pop(S);
        Enqueue(Q, x);
    end
end


The maximum possible number of iterations of the while loop in the algorithm is_____


(a) is the correct answer.

Ques 33 Gate 2016 Set-1

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is_____


(a) is the correct answer.

Ques 34 Gate 2016 Set-1

G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE

I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e

A

I only

B

II only

C

both I and II

D

neither I nor II


(Graph Theory) is the correct answer.

Ques 35 Gate 2016 Set-1

An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?

A

O(1)

B

O(d) but not O(1)

C

O(2d) but not O(d)

D

O(d2d) but not O(2d)


(Binary Heap) is the correct answer.

Ques 36 Gate 2016 Set-1

What will be the output of the following C program?

void count(int n)
{
    static int d = 1;
    printf("%d ", n);
    printf("%d ", d);
    d++;
    if(n > 1) count(n-1);
    printf("%d ", d);
}
int main()
{
    count(3);
}


A

3 1 2 2 1 3 4 4 4

B

3 1 2 1 1 1 2 2 2

C

3 1 2 2 1 3 4

D

3 1 2 1 1 1 2


(C code) is the correct answer.

Ques 37 Gate 2016 Set-1

What will be the output of the following C program?

void count(int n)
{
    static int d = 1;
    printf("%d ", n);
    printf("%d ", d);
    d++;
    if(n > 1) count(n-1);
    printf("%d ", d);
}
int main()
{
    count(3);
}


A

3 1 2 2 1 3 4 4 4

B

3 1 2 1 1 1 2 2 2

C

3 1 2 2 1 3 4

D

3 1 2 1 1 1 2


(C code) is the correct answer.

Ques 38 Gate 2016 Set-1

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change

A

P only

B

Q only

C

Both P and Q

D

Neither P nor Q


(Graph Theory) is the correct answer.

Ques 39 Gate 2016 Set-1

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

A

Both operations can be performed in O(1) time

B

At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)

C

The worst case time complexity for both operations will be Ω(n)

D

Worst case time complexity for both operations will be Ω(logn)


(Queue) is the correct answer.

Unique Visitor Count

Total Unique Visitors

Loading......

Question Options

Contributed by: