GATE Networks 2 — Questions and Answers
Question 1: In a network with n nodes, the maximum number of edges in a simple undirected graph is:
- n(n-1)
- n(n-1)/2 (Correct answer)
- n^2
- 2n-1
Correct answer: n(n-1)/2
A simple undirected graph can have at most one edge between any two nodes, giving n(n-1)/2 edges.
Question 2: Which routing algorithm guarantees the shortest path by exploring nodes in order of their cumulative distance from the source?
- Bellman-Ford
- Floyd-Warshall
- Dijkstra's algorithm (Correct answer)
- DFS-based routing
Correct answer: Dijkstra's algorithm
Dijkstra's algorithm uses a greedy approach with a priority queue to always expand the closest unvisited node, guaranteeing shortest paths in graphs with non-negative weights.
Question 3: A token ring network with 4 stations has a token rotation time of 40 ms. If each station transmits for at most 10 ms, what is the maximum efficiency?
- 25%
- 50% (Correct answer)
- 75%
- 100%
Correct answer: 50%
With 4 stations each transmitting 10 ms in a 40 ms rotation, total transmission = 40 ms, but overhead means efficiency = 4×10/(4×10 + token overhead); assuming 40 ms total cycle, efficiency = 40/80 = 50%.
Question 4: The Nyquist theorem states that the maximum data rate of a noiseless channel with bandwidth B Hz and M discrete signal levels is:
- B log2(M)
- 2B log2(M) (Correct answer)
- B/2 log2(M)
- B log2(2M)
Correct answer: 2B log2(M)
Nyquist's formula: Maximum data rate = 2B log2(M) bits per second for a noiseless channel.
Question 5: Which field in the IPv4 header is used to prevent packets from circulating indefinitely in the network?
- Protocol
- Time to Live (TTL) (Correct answer)
- Identification
- Flags
Correct answer: Time to Live (TTL)
The TTL field is decremented by each router, and a packet is discarded when TTL reaches zero, preventing infinite looping.
Question 6: In TCP slow start, the congestion window (cwnd) grows:
- Linearly by 1 MSS per RTT
- Exponentially, doubling each RTT (Correct answer)
- Quadratically per RTT
- Stays constant until congestion
Correct answer: Exponentially, doubling each RTT
In TCP slow start, cwnd doubles each RTT (one MSS added per ACK), leading to exponential growth until the slow start threshold is reached.
Question 7: A subnet mask of 255.255.255.192 means the subnet has how many usable host addresses?
- 30
- 62 (Correct answer)
- 126
- 254
Correct answer: 62
255.255.255.192 = /26, giving 2^6 = 64 addresses; subtracting network and broadcast gives 62 usable hosts.
GATE Networks 2
In a network with n nodes, the maximum number of edges in a simple undirected graph is: