GATE CS 2014 — Previous Year Questions

Suppose \(P\), \(Q\), \(R\), \(S\), \(T\) are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ______.

Which one of the following is FALSE?

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 ________.

Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is ______.

Consider the following relational schema:

employee(empId, empName, empDept)
customer(custId, custName, salesRepId, rating)

salesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return?

SELECT empName
FROM   employee E
WHERE  NOT EXISTS (SELECT custId
                   FROM   customer C
                   WHERE  C.salesRepId = E.empId
                     AND  C.rating <> 'GOOD');

Consider the equation \((123)_5 = (x8)_y\) with \(x\) and \(y\) as unknown. The number of possible solutions is _______ .

If \(G\) is a forest with \(n\) vertices and \(k\) connected components, how many edges does \(G\) have?

The maximum number of edges in a bipartite graph on 12 vertices is ______.

Which one of the following propositional logic formulas is TRUE when exactly two of \(p\), \(q\) and \(r\) are TRUE?

Each of the nine words in the sentence “The quick brown fox jumps over the lazy dog” is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of the pieces is drawn at random from the box. The expected length of the word drawn is ______. (The answer should be rounded to one decimal place.)

The function \(f(x) = x\sin x\) satisfies the following equation: \(f''(x) + f(x) + t\cos x = 0\). The value of \(t\) is ______.

Four fair six-sided dice are rolled. The probability that the sum of the results being 22 is \(\dfrac{X}{1296}\). The value of \(X\) is ______.

A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?

4, 7, 6, 1, 7, 6, 1, 2, 7, 2

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?

Four fair six-sided dice are rolled. The probability of the sum of the results being 22 is \(\dfrac{X}{1296}\). The value of \(X\) is ______.

Consider the following function:

int f(int n) {
    static int r = 0;
    if (n <= 0) return 1;
    if (n > 3) {
        r = n;
        return f(n - 2) + 2;
    }
    return f(n - 1) + r;
}

What is the value of f(5)?

Let \(L\) be a language and \(\bar{L}\) be its complement. Which one of the following is NOT a viable possibility?

Let \(L_1 = \{w \in \{0,1\}^* \mid w\) has at least as many occurrences of (110)'s as (011)'s\(\}\). Let \(L_2 = \{w \in \{0,1\}^* \mid w\) has at least as many occurrences of (000)'s as (111)'s\(\}\). Which one of the following is TRUE?