CS and IT GATE 2016 Set-1 Questions with Answer

Ques 27 Computer Network

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 Computer Network

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 K_x(m)
represent the operation of encrypting m with a key K_x 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?

{m,K⁺_B (H(m))}

{m,K^-_B (H(m))}

{m,K^-_A (H(m))}

{m,K⁺_A (H(m))}

Ques 29 Computer Network

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

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

(i) and (ii) only

(ii) and (iii) only

(ii) and (iv) only

(iv) only

Ques 30 Computer Network

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

DNS

ARP

DHCP

RARP

Ques 31 Computer Network

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

DNS

ARP

DHCP

RARP

Ques 32 Data Structure

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 Data Structure

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 Data Structure

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

I only

II only

both I and II

neither I nor II

Ques 35 Data Structure

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?

O(1)

O(d) but not O(1)

O(2^d) but not O(d)

O(d2^d) but not O(2^d)

Ques 36 Data Structure

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);
}

3 1 2 2 1 3 4 4 4

3 1 2 1 1 1 2 2 2

3 1 2 2 1 3 4

3 1 2 1 1 1 2

Ques 37 Data Structure

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);
}

3 1 2 2 1 3 4 4 4

3 1 2 1 1 1 2 2 2

3 1 2 2 1 3 4

3 1 2 1 1 1 2

Ques 38 Data Structure

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

P only

Q only

Both P and Q

Neither P nor Q

Ques 39 Data Structure

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

Both operations can be performed in O(1) time

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

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

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

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT GATE 2016 Set-1 Questions with Answer