GATE Computer Science 2007 questions and solutions

# Recent questions tagged gate2007 1
Consider the relation employee(name, sex, supervisorName) with name as the key, supervisorName gives the name of the supervisor of the employee under consideration. What does the following Tuple Relational Calculus query produce? ... with no immediate male subordinates. Names of employees with no immediate female subordinates. Names of employees with a female supervisor.
2
Two processes, $P1$ and $P2$, need to access a critical section of code. Consider the following synchronization construct used by the processes: /* P1 */ while (true) { wants1 = true; while (wants2 == true); /* Critical Section */ ... ensure bounded waiting. It requires that processes enter the critical section in strict alteration. It does not prevent deadlocks, but ensures mutual exclusion.
3
A single processor system has three resource types $X, Y$ and $Z$, which are shared by three processes. There are $5$ units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column ... $P0$ $P1$ $P2$ None of the above, since the system is in a deadlock
4
A virtual memory system uses First In First Out (FIFO) page replacement policy and allocates a fixed number of frames to a process. Consider the following statements: P: Increasing the number of page frames allocated to a process sometimes increases the page fault rate. Q: Some programs do not ... and Q are true, but Q is not the reason for P. P is false but Q is true Both P and Q are false.
5
An operating system used Shortest Remaining System Time first (SRT) process scheduling algorithm. Consider the arrival times and execution times for the following processes: ... $P2$ ? $5$ $15$ $40$ $55$
6
In a simplified computer the instructions are: $\begin{array}{|l|l|} \hline \text {OP$R _j , R _i$} & \text{Perform$R _j $OP$R _i$and store the result in register$R _j$} \\\hline \text{OP$m,R _i$} & \text{Perform$val$OP$ ... value of the computation should be in memory. What is the minimum number of MOV instructions in the code generated for this basic block? $2$ $3$ $5$ $6$
7
Consider the following two statements: P: Every regular grammar is LL(1) Q: Every regular set has a LR(1) grammar Which of the following is TRUE? Both P and Q are true P is true and Q is false P is false and Q is true Both P and Q are false
8
Consider the grammar with non-terminals $N=\left\{S,C,S_1\right\}$, terminals $T=\left\{a, b, i, t, e\right\}$, with $S$ as the start symbol, and the following set of rules: $S \rightarrow iCtSS_1 \mid a$ $S_1 \rightarrow eS \mid \epsilon$ $C \rightarrow b$ The grammar is NOT LL(1) because: it is left recursive it is right recursive it is ambiguous it is not context-free
9
Consider the following C program segment: int IsPrime (n) { int i, n; for (i=2; i<=sqrt(n);i++) if(n%i == 0) {printf("Not Prime \n"); return 0;} return 1; } Let $T(n)$ denote number of times the $for$ loop is executed by the program on input $n$ ... $T(n) = O(n) \: \text{ and } T(n) = \Omega(\sqrt{n})$ None of the above
10
An array of $n$ numbers is given, where $n$ is an even number. The maximum as well as the minimum of these $n$ numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed? At least $2n-c$ comparisons, for some constant $c$ are needed. At most $1.5n-2$ comparisons are needed. At least $n\log_2 n$ comparisons are needed None of the above
11
Let $w$ be the minimum weight among all edge weights in an undirected connected graph. Let $e$ be a specific edge of weight $w$. Which of the following is FALSE? There is a minimum spanning tree containing $e$ If $e$ is not in a minimum spanning tree $T$, then ... $w$ $e$ is present in every minimum spanning tree
12
Which of the following is TRUE about formulae in Conjunctive Normal Form? For any formula, there is a truth assignment for which at least half the clauses evaluate to true. For any formula, there is a truth assignment for which all the clauses evaluate to true. There is a formula such that for each truth assignment, at most one-fourth of the clauses evaluate to true. None of the above.
13
Consider the process of inserting an element into a $Max \: Heap$, where the $Max \: Heap$ is represented by an $array$. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of $comparisons$ performed is: $\Theta(\log_2n)$ $\Theta(\log_2\log_2n)$ $\Theta(n)$ $\Theta(n\log_2n)$
14
Consider the following C program segment where $CellNode$ represents a node in a binary tree: struct CellNode { struct CellNode *leftChild; int element; struct CellNode *rightChild; }; int Getvalue (struct CellNode *ptr) { int value = 0; if (ptr != NULL) { if ((ptr-> ... number of nodes in the tree the number of internal nodes in the tree the number of leaf nodes in the tree the height of the tree
15
What is the $\text{time complexity}$ of the following recursive function? int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor (sqrt(n))) + n); } $\Theta(n^2)$ $\Theta(n \log_2n)$ $\Theta(\log_2n)$ $\Theta(\log_2\log_2n)$
16
In the following C function, let $n \geq m$. int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function? $\Theta(\log_2n)$ $\Omega(n)$ $\Theta(\log_2\log_2n)$ $\Theta(\sqrt{n})$
17
A complete $n-ary$ tree is a tree in which each node has $n$ children or no children. Let $I$ be the number of internal nodes and $L$ be the number of leaves in a complete $n-ary$ tree. If $L = 41$ and $I = 10$, what is the value of $n$? $3$ $4$ $5$ $6$
18
Consider the following C 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)$? $5$ $7$ $9$ $18$
19
In an unweighted, undirected connected graph, the shortest path from a node $S$ to every other node is computed most efficiently, in terms of time complexity, by Dijkstra’s algorithm starting from $S$. Warshall’s algorithm. Performing a DFS starting from $S$. Performing a BFS starting from $S$.
20
Consider a hash table of size seven, with starting index zero, and a hash function $(3x + 4)\mod 7$. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence $1, 3, 8, 10$ is inserted into the table using closed hashing? Note that − denotes an empty location in the ... $3$ $1$, −, −, −, −, −, $3$ $1, 10, 8$, −, −, −,$3$
21
The inorder and preorder traversal of a binary tree are $\text{d b e a f c g}$ and $\text{a b d e c f g}$, respectively The postorder traversal of the binary tree is: $\text{d e b f g c a}$ $\text{e d b g f c a}$ $\text{e d b f g c a}$ $\text{d e f g b c a}$
22
The following postfix expression with single digit operands is evaluated using a stack: $8 \ 2 \ 3 \ {}^\hat{\mkern6mu} / \ 2 \ 3 * + 5 \ 1 * -$ Note that $^\hat{}$ is the exponentiation operator. The top two elements of the stack after the first $*$ is evaluated are $6, 1$ $5, 7$ $3, 2$ $1, 5$
23
Consider a pipelined processor with the following four stages: IF: Instruction Fetch ID: Instruction Decode and Operand Fetch EX: Execute WB: Write Back The IF, ID and WB stages take one clock cycle each to complete the operation. The number of clock cycles for the EX stage depends on the instruction. The ... $R5$-$R4} \\ \end{array}$ $7$ $8$ $10$ $14$
24
The control signal functions of a $4$-$bit$ binary counter are given below (where $X$ ... $0, 3, 4$ $0, 3, 4, 5$ $0, 1, 2, 3, 4$ $0, 1, 2, 3, 4, 5$
25
In a look-ahead carry generator, the carry generate function $G_i$ and the carry propagate function $P_i$ for inputs $A_i$ and $B_i$ are given by: $P_i = A_i \oplus B_i \text{ and }G_i = A_iB_i$ The expressions for the sum bit $S_i$ and the carry bit $C_{i+1}$ of the look ahead carry ... 4-bit adder with $S_3, S_2, S_1, S_0$ and $C_4$ as its outputs are respectively: $6, 3$ $10, 4$ $6, 4$ $10, 5$
26
Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of $n$ variables. What is the minimum size of the multiplexer needed? $2^n$ line to $1$ line $2^{n+1}$ line to $1$line $2^{n-1}$ line to $1$line $2^{n-2}$ line to $1$line
27
Define the connective $*$ for the Boolean variables $X$ and $Y$ as: $X * Y = XY + X'Y'.$ Let $Z = X * Y$. Consider the following expressions $P$, $Q$ and $R$. $P : X = Y * Z, \\ Q :Y = X * Z, \\ R : X *Y * Z = 1$ Which of the following is TRUE? Only $P$ and $Q$ are valid. Only $Q$ and $R$ are valid. Only $P$ and $R$ are valid. All $P$, $Q$, $R$ are valid.
Let $f(w, x, y, z) = \sum {\left(0,4,5,7,8,9,13,15\right)}$. Which of the following expressions are NOT equivalent to $f$? P: $x'y'z' + w'xy' + wy'z + xz$ Q: $w'y'z' + wx'y' + xz$ R: $w'y'z' + wx'y' + xyz+xy'z$ S: $x'y'z' + wx'y'+ w'y$ P only Q and S R and S S only
Which of the following languages is regular? $\left\{ww^R \mid w \in \{0, 1\}^+\right\}$ $\left\{ww^Rx \mid x,w \in \{0, 1\}^+\right\}$ $\left\{wxw^R \mid x, w \in \{0, 1\}^+\right\}$ $\left\{xww^R \mid x, w \in \{0, 1\}^+\right\}$
The language $L=\left\{0^i21^i \mid i \geq 0\right\}$ over the alphabet $\left\{0, 1, 2\right\}$ is: not recursive is recursive and is a deterministic CFL is a regular language is not a deterministic CFL but a CFL