GATE CSE 2014 SET-1
Q21.
Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%, the minimum number of bits required to represent the sequence number field is ________.Q22.
An operating system uses the Banker's algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the current system state. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution. There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state: REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z REQ2: P1 requests 2 units of x, 0 units of Y and 0 units of Z Which one of the following is TRUE?Q23.
Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.Q24.
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.Q25.
Consider the following Boolean Algebra for F: F(P,Q,R,S)=PQ+\bar{P}QR+\bar{P}Q\bar{R}S The minimal sum-of products form of F isQ26.
Let S denote the set of all functions f:{\{0,1\}}^{4} \rightarrow \{0,1\}. Denote by N the number of functions from S to the set {0,1}. The value of log_{2} log_{2}N is______.Q27.
Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?Q28.
Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i,f):1\leqi\leq12, 1\leqj\leq12}. There is an edge between (a,b) and (c,d) if |a-c|\leq1 and |b-d| \leq1. The number of edges in the graph is ____.Q29.
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?