search
Log In
GATE Computer Science 2007 questions and solutions

Recent questions tagged gate2007

61 votes
6 answers
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.
asked Sep 22, 2014 in Databases Kathleen 9.3k views
35 votes
7 answers
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.
asked Sep 22, 2014 in Operating System Kathleen 7.8k views
15 votes
1 answer
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
asked Sep 22, 2014 in Operating System Kathleen 3.4k views
27 votes
3 answers
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.
asked Sep 22, 2014 in Operating System Kathleen 6.3k views
18 votes
4 answers
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$
asked Sep 22, 2014 in Operating System Kathleen 2.7k views
35 votes
5 answers
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$
asked Sep 22, 2014 in CO and Architecture Kathleen 5.6k views
48 votes
9 answers
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
asked Sep 22, 2014 in Compiler Design Kathleen 13.2k views
20 votes
5 answers
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
asked Sep 22, 2014 in Compiler Design Kathleen 4.2k views
25 votes
6 answers
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
asked Sep 22, 2014 in Algorithms Kathleen 4.9k views
39 votes
10 answers
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
asked Sep 22, 2014 in Algorithms Kathleen 8k views
21 votes
3 answers
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
asked Sep 22, 2014 in Algorithms Kathleen 3.4k views
34 votes
4 answers
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.
asked Sep 22, 2014 in Digital Logic Kathleen 5.9k views
43 votes
3 answers
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)$
asked Sep 22, 2014 in DS Kathleen 6.4k views
21 votes
4 answers
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
asked Sep 22, 2014 in DS Kathleen 2.6k views
29 votes
9 answers
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)$
asked Sep 22, 2014 in Algorithms Kathleen 9.6k views
39 votes
6 answers
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})$
asked Sep 22, 2014 in Algorithms Kathleen 8.7k views
22 votes
5 answers
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$
asked Sep 22, 2014 in DS Kathleen 5.7k views
21 votes
1 answer
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$
asked Sep 22, 2014 in Programming Kathleen 3.1k views
25 votes
5 answers
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$.
asked Sep 22, 2014 in Algorithms Kathleen 6k views
18 votes
3 answers
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$
asked Sep 22, 2014 in DS Kathleen 3.1k views
15 votes
2 answers
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}$
asked Sep 22, 2014 in DS Kathleen 2.1k views
24 votes
3 answers
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$
asked Sep 22, 2014 in DS Kathleen 5.5k views
22 votes
4 answers
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$
asked Sep 22, 2014 in CO and Architecture Kathleen 6.4k views
51 votes
6 answers
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$
asked Sep 22, 2014 in Digital Logic Kathleen 8.6k views
42 votes
3 answers
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$
asked Sep 22, 2014 in Digital Logic Kathleen 4.6k views
44 votes
6 answers
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
asked Sep 22, 2014 in Digital Logic Kathleen 9.6k views
29 votes
3 answers
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.
asked Sep 22, 2014 in Digital Logic Kathleen 3.4k views
24 votes
4 answers
28
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
asked Sep 22, 2014 in Digital Logic Kathleen 3.3k views
22 votes
2 answers
29
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\}$
asked Sep 22, 2014 in Theory of Computation Kathleen 4.6k views
19 votes
4 answers
30
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
asked Sep 22, 2014 in Theory of Computation Kathleen 2.9k views
...