51. Let
G = (V, E) be a simple undirected graph, and sbe a particular vertex in it
called the source. For xÏµV, let d(x) denote the shortest distance in G from s to
x. A breadth first search (BFS) is performed starting at s. Let T be the
resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one
of the following CANNOT be the value of d(u)–d(v)?

(A) -1 (B)
0

(C) 1 (D)
2

Answer: D

52. Consider
a uniprocessor system executing three tasks T

_{1}, T_{2}and T_{3}, each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively. The priority of each task is the inverse of its period, and the available tasks are scheduled in order of priority, with the highest priority task scheduled first. Each instance of T_{1}, T_{2}and T_{3}requires an execution time of 1, 2 and 4 milliseconds, respectively. Given that all tasks initially arrive at the beginning of the 1^{st}millisecond and task preemptions are allowed, the first instance of T_{3}completes its execution at the end of .................. milliseconds.
Answer: 12

53. A
positive edge-triggered D flip-flop is connected to a positive edge-triggered
JK flip-flop as follows. The Q output of the D flip-flop is connected to both
the J and K inputs of the JK flip-flop, while the Q output of the JK flip-flop
is connected to the input of the D flip-flop. Initially, the output of the D
flip-flop is set to logic one and the output of the JK flip-flop is cleared.
Which one of the following is the bit sequence (including the initial state)
generated at the Q output of the JK flip-flop when the flip-flops are connected
to a free-running common clock? Assume that J = K = 1 is the toggle mode and J
= K = 0 is the state-holding mode of the JK flip-flop. Both the flip-flops have
non-zero propagation delays.

(A) 0110110… (B)
0100100…

(C) 011101110… (D) 011001100…

Answer: A

54. Consider
a disk pack with a seek time of 4 milliseconds and rotational speed of 10000
rotations per minute (RPM). It has 600 sectors per track and each sector can
store 512 bytes of data. Consider a file stored in the disk. The file contains
2000 sectors. Assume that every sector access necessitates a seek, and the
average rotational latency for accessing each sector is half of the time for
one complete rotation. The total time (in milliseconds) needed to read the
entire file is ...................

Answer: 14020

55. Consider
a non-pipelined processor with a clock rate of 2.5 gigahertz and average cycles
per instruction of four. The same processor is upgraded to a pipelined
processor with five stages; but due to the internal pipeline delay, the clock
speed is reduced to 2 gigahertz. Assume that there are no stalls in the
pipeline. The speed up achieved in this pipelined processor is
...................

Answer: 3.2

56. Suppose
the following disk request sequence (track numbers) for a disk with 100 tracks
is given: 45, 20, 90, 10, 50, 60, 80, 25, 70. Assume that the initial position
of the R/W head is on track 50. The additional distance that will be traversed
by the R/W head when the Shortest Seek Time First (SSTF) algorithm is used
compared to the SCAN (Elevator) algorithm (assuming that SCAN algorithm moves
towards 100 when it starts execution) is ............... tracks.

Answer: 10

57. Consider
a main memory with five page frames and the following sequence of page
references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. Which one of the
following is true with respect to page replacement policies First In First Out
(FIFO) and Least Recently Used (LRU)?

(A) Both incur the same number of page faults

(B) FIFO incurs 2 more page faults than LRU

(C) LRU incurs 2 more page faults than FIFO

(D) FIFO incurs 1 more page faults than LRU

Answer: A

58.

Answer: -1

59. Consider
the following 2×2 matrix A where two elements are unknown and are marked by a
and b. The eigenvalues of this matrix are -1 and 7. What are the values of a
and b?

(A) a = 6, b = 4 (B) a = 4, b = 6

(C) a = 3, b = 5 (D) a = 5, b = 3

Answer: D

60. An
algorithm performs (log N)

^{1/2}find operations, N insert operations, (log N)^{1/2 }delete operations, and (log N)^{1/2}decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?
(A) Unsorted array (B) Min-heap

(C) Sorted array (D) Sorted doubly linked list

Answer: A

## 0 Comments