Figures (i) and (ii) represent intercity highway systems. The black dots represent cities and the line segments between them represent intercity highways.
A salesperson needs to make a trip. She needs to start from a city, visit each of the remaining cities exactly once, and finally return to the same city from which she started.
Which one of the following options is then true?

Question

A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of $b$ blocks needs $\lceil \log_2 b \rceil$ block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.

Answer 1

Step 1: Translate the trip into graph language.
A trip that starts at a city, visits every other city exactly once, and returns to the start is what graph theory calls a Hamiltonian cycle: a closed loop using the highways that touches every city exactly once.

Step 2: Use a known fact about grid networks for figure (i).
Figure (i) is a rectangular grid network with 4 rows and 4 columns of cities, each joined only to its up, down, left, and right neighbour. For this kind of grid, a round trip covering every city exists whenever the total number of cities is even, because the cities split evenly into two alternating groups, like the black and white squares of a chessboard, and a closed loop can always snake through the grid, going down one lane and up the next, ending exactly where it began. Since $4\times4=16$ is even, this round trip exists for figure (i).

Step 3: Count highways at each city in figure (ii).
In figure (ii), two of the five cities, call them $V_1$ and $V_5$, each have three highways touching them. The other three cities, $V_2$, $V_3$, $V_4$, each have exactly two highways, and in every case one of those two highways goes to $V_1$ and the other goes to $V_5$.

Step 4: See how many highways a round trip actually needs.
A round trip through all five cities uses exactly five highways, one connecting each consecutive pair of cities in the loop, and every city touches exactly two of those used highways. There are only six highways in the whole network, so a round trip would use all but exactly one of them.

Step 5: Show that leaving out one highway cannot fix both busy cities.
Removing a single highway can lower the highway count at, at most, two cities. But there is no highway directly joining $V_1$ and $V_5$, so any single highway we leave out touches only one of $V_1$ or $V_5$. That means the other one of $V_1$, $V_5$ is stuck with three highways in the loop, which is not allowed since a round trip needs exactly two at every city. So no round trip can use all five cities in figure (ii).

Final Answer:
The round trip works for figure (i) but fails for figure (ii).
\[ \boxed{\text{Possible for (i), not for (ii)}} \]

Show Hint

The Correct Option is A

Solution and Explanation

Questions Asked in GATE CS exam