What topics are covered on Page 2 of GATE 2015 CS/IT Set 3?

Page 2 contains Questions 14 to 26. It covers Computer Networks topics including Go-Back-N, TCP and CSMA/CD; Data Structures and Algorithms topics including hashing, mergesort, max-heaps, BSTs and postfix expressions; DBMS topics including functional dependencies and SQL; and Discrete Mathematics topics involving counting, propositional logic and sets.

How many bits are required for the Go-Back-N sequence number field in Question 14?

Using the given bandwidth, propagation delay and packet size, the required sender window is greater than 200 packets. An 8-bit sequence-number field provides enough distinct sequence numbers for the required Go-Back-N window.

Which TCP statement is correct in GATE 2015 Set 3?

TCP connections are full duplex. TCP supports selective acknowledgements as an option and provides a byte-stream service rather than a message-stream service.

What is the hash-table load factor when 2000 elements are stored in 25 slots?

The load factor is the number of stored elements divided by the number of slots, so the load factor is 2000 divided by 25, which is 80.

What maximum mergesort input size can be processed in six minutes?

If mergesort takes 30 seconds for 64 elements and follows n log n growth, an input size of 512 corresponds to approximately twelve times the work and therefore six minutes.

What is the value of the postfix expression 10 5 + 60 6 / * 8 -?

The expression evaluates as (10 + 5) × (60 / 6) - 8, giving 142.

Which SQL condition finds theatres having maximum capacity?

The condition can compare each capacity with ALL capacities in the Cinema relation using P1.Capacity >= ALL (SELECT P2.Capacity FROM Cinema P2).

CS and IT Gate 2015 Set-3 Questions with Answer

1 2 3 4 5

Ques 14 Gate 2015 Set-3

Consider a network connecting two systems located 8000 kilometers apart. The bandwidth of the network is 500 × 106 bits per second. The propagation speed of the media is 4 × 106 meters per second. It is needed to design a Go-Back-N sliding window protocol for this network. The average packet size is 107 bits. The network is to be used to its full capacity. Assume that processing delays at nodes are negligible. Then, the minimum size in bits of he sequence number field has to be ________.

(a) is the correct answer.

Ques 15 Gate 2015 Set-3

Consider the following statements.

I. TCP connections are full duplex.
II. TCP has no option for selective acknowledgment
III. TCP connections are message streams.

Only I is correct

Only I and II are correct

Only II and III are correct

All of I, II and III are correct

(TCP/IP) is the correct answer.

PROCESSED

Ques 16 Gate 2015 Set-3

Consider a CSMA/CD network that transmits data at a rate of 100 Mbps (108 bits per second) over a 1 km (kilometre) cable with no repeaters. If the minimum frame size required for this network is 1250 bytes, what is the signal speed (km/sec) in the cable?

8000

10000

16000

20000

(OSI Model) is the correct answer.

PROCESSED

Ques 17 Gate 2015 Set-3

Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is __________

(a) is the correct answer.

Ques 18 Gate 2015 Set-3

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

256

512

1024

2048

(a) is the correct answer.

Mergesort Time Complexity:
• The worst-case time complexity of Mergesort is Θ(n log n).
• This means that the running time T(n) can be expressed as T(n) = c · n log₂ n, where c is a constant and n is the input size.

Calculate the Constant 'c':
We are given that T(64) = 30 seconds.
• Substitute n = 64 into the formula:
    T(64) = c · 64 log₂ 64
• We know that log₂ 64 = 6 (since 2⁶ = 64).
    30 = c · 64 · 6
    30 = c · 384
• Solve for c:
    c = 30 / 384

Convert Target Time to Seconds:
The new time limit is 6 minutes.
• 6 minutes = 6 · 60 seconds = 360 seconds.

Set Up Equation for New Input Size:
Let n_new be the maximum input size we can solve in 360 seconds.
• T(n_new) = c · n_new log₂ n_new
• Substitute the values for T(n_new) and c:
    360 = (30 / 384) · n_new log₂ n_new

Solve for n_new log₂ n_new:
• Multiply both sides by 384/30:
    360 · (384 / 30) = n_new log₂ n_new
• Simplify the left side:
    (360 / 30) · 384 = n_new log₂ n_new
    12 · 384 = n_new log₂ n_new
    4608 = n_new log₂ n_new

Check the Given Options:
We need to find an n_new such that n_new log₂ n_new is approximately 4608.
• For n = 256:
    256 log₂ 256 = 256 · 8 = 2048
• For n = 512:
    512 log₂ 512 = 512 · 9 = 4608
• For n = 1024:
    1024 log₂ 1024 = 1024 · 10 = 10240
• For n = 2048:
    2048 log₂ 2048 = 2048 · 11 = 22528

Comparing the calculated values with 4608, n = 512 yields an exact match.
Therefore, the maximum input size that can be solved in 6 minutes is 512.

Ques 19 Gate 2015 Set-3

Consider the following array of elements.

〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉.

The minimum number of interchanges needed to convert it into a max-heap is

(Array) is the correct answer.

PROCESSED

Ques 20 Gate 2015 Set-3

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

(Binary Search Tree) is the correct answer.

PROCESSED

Ques 21 Gate 2015 Set-3

The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is

284

213

142

(Stack) is the correct answer.

PROCESSED

Ques 22 Gate 2015 Set-3

Consider the relation X(P, Q, R, S, T, U) with the following set of functional dependencies

F = {
{P, R} → {S,T},
{P, S, U} → {Q, R}
}

Which of the following is the trivial functional dependency in F⁺ is closure of F?

{P,R}→{S,T}

{P,R}→{R,T}

{P,S}→{S}

{P,S,U}→{Q}

(Functional Dependency) is the correct answer.

PROCESSED

Ques 23 Gate 2015 Set-3

Consider the following relation

Cinema (theater, address, capacity)

Which of the following options will be needed at the end of the SQL query

SELECT P1. address FROM Cinema P1

Such that it always finds the addresses of theaters with maximum capacity?

WHERE P1. Capacity> = All (select P2. Capacity from Cinema P2)

WHERE P1. Capacity> = Any (select P2. Capacity from Cinema P2)

WHERE P1. Capacity > All (select max(P2. Capacity) from Cinema P2)

WHERE P1. Capacity > Any (select max (P2. Capacity) from Cinema P2)

(SQL Query) is the correct answer.

PROCESSED

Ques 24 Gate 2015 Set-3

The number of 4 digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set {1, 2, 3} is ____.

(a) is the correct answer.

Ques 25 Gate 2015 Set-3

In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the result from you till you ask for it. Upon asking, the person replies the following:

“The result of the toss is head if and only if I am telling the truth.”

Which of the following options is correct?

The result is head

The result is tail

If the person is of Type 2, then the result is tail

If the person is of Type 1, then the result is tail

(Propositional Logic) is the correct answer.

PROCESSED

Ques 26 Gate 2015 Set-3

Suppose U is the power set of the set S = {1,2,3,4,5,6}. For any T ∈ U, let |T| denote the number of elements in T and T′ denote the complement of T. For any T, R ∈ U, let TR be the set of all elements in T which are not in R. Which one of the following is true?

∀X∈U(|X| = |XX′|)

∃X∈ U∃Y∈U(|X|=5,|Y|=5 and X∩Y= ∅)

∀X∈U∀Y∈U(|X|=2,|Y|=3 and X∖Y=∅)

∀X∈U∀Y∈U(X∖Y=Y′∖X′ )

(Set Theory) is the correct answer.

PROCESSED

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT Gate 2015 Set-3 Questions with Answer

Question Options

Sign in to ExamPrev