GATE CSE 2007
View Questions

GATE CSE

1
Consider the following segment of C-code:
int j, n;
j=1;
while(j <= n)
 j = j * 2;
The number of comparisons made in the execution of the loop for any n > 0 is:
2
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?
3
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
4
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. What is the average length of Huffman codes?
5
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?
6
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?
7
In the following C function, let n $$ \ge $$ 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?
8
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:
9
Consider the following C code segment:
int IsPrime(n){
 int i, n;
 for(i=2; i<=sqrt(n);i++){
  if(n % i == 0){
    printf("No prime\n"); return 0;
  }
  return 1;
 }
}
Let T(n) denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?
10
What is the time complexity of the following recursive function?
int DoSomething(int n){
 if(n <= 2)
     return 1;
 else
     return (floor(sqrt(n)) + n);
}
11
Which of the following sorting algorithms has the lowest worst-case complexity?
12
Consider the DAG with $$V = \{1,2,3,4,5,6\}$$, shown below. GATE CSE 2007 Algorithms - Searching and Sorting Question 38 English Which of the following is NOT a topological ordering?
13

Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules:

$$\eqalign{ & S \to bA\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,S \to aB \cr & A \to a\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to b \cr & A \to aS\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to bS \cr & S \to bAA\,\,\,\,\,\,\,\,\,\,\,B \to aBB \cr} $$

Which of the following strings is generated by the grammar?

14

Consider the grammar with non-terminals N = { S, C, S1 }, terminals T = { a, b, i, t, e }, with S as the start symbol, and the following set of rules:

$$\eqalign{ & S \to iCtS{S_1}\,|\,\,a \cr & {S_1} \to eS\,|\,\,\varepsilon \cr & C \to b \cr} $$

The grammar is NOT LL(1) because:

15
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?
16
Which one of the following is a top-down parser?
17

Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules:

$$\eqalign{ & S \to bA\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,S \to aB \cr & A \to a\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to b \cr & A \to aS\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,B \to bS \cr & S \to bAA\,\,\,\,\,\,\,\,\,\,\,B \to aBB \cr} $$

For the correct answer strings to the previous question, how many derivation trees are there?

18
Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute (bn mod m),$$0 \le b,n \le m$$?
19
The minimum positive integer p such that (3p modulo 17) = 1 is
20
Consider the following two statements:

i. A hash function (these are often used for computing digital signatures) is an injective function.
ii. encryption technique such as DES performs a permutation on the elements of its input alphabet.

Which one of the following options is valid for the above two statements?
21
Match the following:

List - I

(P) SMTP
(Q) BGP
(R) TCP
(S) PPP

List - II

(1) Application layer
(2) Transport layer
(3) Data link layer
(4) Network layer
(5) Physical layer
22
Which one of the following uses UDP as the transport protocol?
23
The address of a class B host is to be split into subnets with a 6-bit subnet number. What is the maximum number of subnets and the maximum number of hosts in each subnet?
24
The distance between two stations M and N is L kilometers. All frames are K bits long. The propagation delay per kilometer is t seconds. Let R bits/second be the channel capacity. Assuming that processing delay is negligible, the minimum number of bits for the sequence number field in a frame for maximum utilization, when the sliding window protocol is used, is:
25
The message 11001001 is to be transmitted using the CRC polynomial x3 + 1 to protect it from errors. The message that should be transmitted is:
26
There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is the probability that ONLY one station transmits in a given time slot?
27
In Ethernet when Manchester encoding is used, the bit rate is:
28
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 $$ADD$$ and $$SUB$$ instructions need $$1$$ clock cycle and the $$MUL$$ instruction needs $$3$$ clock cycles in the $$EX$$ stage. Operand forwarding is used in the pipelined processor. What is the number of clock cycles taken to complete the following sequence of instructions?

GATE CSE 2007 Computer Organization - Pipelining Question 31 English
29
Consider a machine with a byte addressable main memory of $${2^{16}}$$ bytes. Assume that a direct mapped data cache consisting of $$32$$ lines of $$64$$ bytes each is used in the system. $$A\,\,50 \times 50$$ two-dimensional array of bytes is stored in the main memory starting from memory location $$1100H.$$ Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses.

How many data cache misses will occur in total?

30
Consider a machine with a byte addressable main memory of $${2^{16}}$$ bytes. Assume that a direct mapped data cache consisting of $$32$$ lines of $$64$$ bytes each is used in the system. $$A\,\,50 \times 50$$ two-dimensional array of bytes is stored in the main memory starting from memory location $$1100H.$$ Assume that the data cache is initially empty. The complete array is accessed twice. Assume that the contents of the data cache do not change in between the two accesses.

Which of the following lines of the data cache will be replaced by new blocks in accessing the array?

31
Consider a $$4$$-way set associative cache consisting of $$128$$ lines with a line size of $$64$$ words. The $$CPU$$ generates a $$20$$-bit address of a word in main memory. The numbers of bits in the TAG, LINE and WORD fields are respectively
32
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}$$ and $${G_i} = {A_i}{B_i}.$$

The expressions for the sum bit $${S_i}$$ and the carry bit $${C_{i + 1}}$$ of the look ahead carry adder are given by $${S_i} = {P_i} \oplus {C_i}$$ and $${C_{i + 1}} = {G_i} + {P_i}{C_i},$$ where $${C_0}$$ is the input carry. Consider a two $$-$$ level logic implementation of the look $$-$$ ahead carry generator. Assume that all $${P_i}$$ and $${G_i}$$ are available for the carry generator circuit and that the $$AND$$ and $$OR$$ gates can have any number of inputs. The number of $$AND$$ gates and $$OR$$ gates needed to implement the look $$-$$ ahead carry generator for a $$4$$-bit adder with $${S_3},\,\,{S_2},\,\,{S_1},\,\,{S_0}$$ and $${C_4}$$ as its outputs are respectively

33
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.
34
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. 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 table.
35
Consider the following two statements:
i. A hash function (these are often used for computing digital signatures) is an injective function.
ii. encryption technique such as DES performs a permutation on the elements of its input alphabet.
Which one of the following options is valid for the above two statements?
36
The following postfix expression with single digit operands is evaluated using a stack: 8 2 3 ^ / 2 3 * + 5 1 * - Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
37
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?
38
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?
39
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?
40
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->leftChild == NULL) && 
        (ptr->rightChild == NULL)) 
       value = 1; 
       else 
         value = value + GetValue(ptr->leftChild) 
             + GetValue(ptr->rightChild); 
     } 
     return(value); 
} 
The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:
41
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
42
The maximum number of binary trees that can be formed with three unlabeled nodes is:
43
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
44
Consider the following C program:
#include 
#define EOF -1 
     void push (int); /* push the argument on the stack */ 
     int pop (void); /* pop the top of the stack */ 
     void flagError (); 
     int main () { 
       int c, m, n, r; 
       while ((c = getchar ()) != EOF) { 
         if (isdigit (c) ) 
           push (c); 
         else if ((c == '+') || (c == '*')) { 
           m = pop (); 
           n = pop (); 
           r = (c == '+') ? n + m : n*m; 
           push (r); 
         } else if (c != ' ') 
           flagError (); 
       } 
       printf("% c", pop ()); 
    } 
What is the output of the program for the following input ? 5 2 * 3 3 2 + * +
45
Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:
i. isEmpty (Q) — returns true if the queue is empty, false otherwise.
ii. delete (Q) — deletes the element at the front of the queue and returns its value.
iii. insert (Q, i) — inserts the integer i at the rear of the queue.
Consider the following function:
void f (queue Q) { 
  int i ; 
  if (!isEmpty(Q)) { 
      i = delete(Q); 
      f(Q); 
      insert(Q, i); 
  } 
} 
What operation is performed by the above function f ?
46
The order of a leaf node in a B+- tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?
47
Consider the B+ tree in the adjoining figure, where each node has at most two keys and three links. GATE CSE 2007 Database Management System - File Structures and Indexing Question 13 English 1

Keys K 15 and then K 25 are inserted into this tree in that order. Exactly how many of the following nodes (disregarding the links) will be present in the tree after the two insertions?

GATE CSE 2007 Database Management System - File Structures and Indexing Question 13 English 2
48
Consider the B+ tree in the adjoining figure, where each node has at most two keys and three links. GATE CSE 2007 Database Management System - File Structures and Indexing Question 12 English 1

Now the key K 50 is deleted from the B+ tree resulting after the two insertions made earlier. Consider the following statements about the B+ tree resulting after this deletion.

i) The height of the tree remains the same.

ii) The node GATE CSE 2007 Database Management System - File Structures and Indexing Question 12 English 2 (disregarding the links) is present in the tree.

iii) The root node remains unchanged (disregarding the links).

Which one of the following options is true ?
49
Consider the following two transactions: T1 and T2.
T1: read (A);                  T2: read (B);
    read (B);                      read (A);
    if A = 0 then B ← B + 1;       if B ≠ 0 then A ← A - 1;
    write (B);                     write (A);
Which of the following schemes, using shared and exclusive locks, satisfy the requirements for strict two phase locking for the above transactions?
50
Consider the following schedules involving two transactions. Which one of the following statements is TRUE?

S1: r1(X); r1(Y); r2(Y); r2(X); w2(Y); w1(X);

S2: r1(X); r2(X); r2(Y); w2(Y); r1(Y); w1(X);

51
Consider the following relation schemas :

b-Schema = (b-name, b-city, assets)
a-Schema = (a-num, b-name, bal)
d-Schema = (c-name, a-number)

Let branch, account and depositor be respectively instances of the above schemas. Assume that account and depositor relations are much bigger than the branch relation.

Consider the following query:
Пc-nameb-city = “Agra” ⋀ bal < 0 (branch $$ \Join $$ (account $$ \Join $$ depositor))

Which one of the following queries is the most efficient version of the above query ?

52

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?

$$\eqalign{ & \{ e.name\,|\,employee(e) \wedge \cr & (\forall x)[\neg employee(x) \vee \cr & x.\sup ervisorName \ne e.name\, \vee \cr & x.sex = 'male']\} \cr} $$
53
Consider a selection of the form σA ≤ 100(r), where r is a relation with 1000 tuples. Assume that the attribute values for A among the tuples are uniformly distributed in the interval [ 0, 500 ]. Which one of the following options is the best estimate of the number of tuples returned by the given selection query?
54

Information about a collection of students is given by the relation studInfo(studId, name, sex). The relation enroll(studId, courseId) gives which student has enrolled for (or taken) what course(s). Assume that every course is taken by at least one male and at least one female student. What does the following relational algebra expression represent?

$$\eqalign{ & \prod\nolimits_{courseId} {((\prod\nolimits_{studId} {({\sigma _{sex = 'female'}}} } \cr & (studInfo)) \times \prod\nolimits_{courseId} {(enroll)) - enroll)} \cr} $$
55
Consider the table employee(empId, name, department, salary) and the two queries Q1, Q2 below. Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary than anyone in the department 5, which one of the statements is TRUE for any arbitrary employee table?
Q1:
Select e.empId 
From employee e 
Where not exists 
  (Select * From employee s
   where s.department = "5" and 
   s.salary >=e.salary);
Q2:
Select e.empId 
From employee e 
Where e.salary > Any 
( Select distinct salary 
From employee s 
Where s.department = "5");
56
Which one of the following statements if FALSE?
57
The control signal functions of a $$4$$-bit binary counter are given below $$($$where $$X$$ “don’t care”$$):$$ GATE CSE 2007 Digital Logic - Sequential Circuits Question 21 English 1

The counter is connected as follows:

GATE CSE 2007 Digital Logic - Sequential Circuits Question 21 English 2

Assume that the counter and gate delays are negligible. If the counter starts at $$0,$$ then it cycles through the following sequence:

58
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?
59
How many $$3$$ to $$8$$ decodes with an enable input are needed to construct to constant $$6$$ to $$64$$ line decoder without using any other logic gates
60
Let $$f\left( {w,x,y,z} \right) = \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$$
61
Consider the following Boolean function with four variables
$$F\left( {w,\,x,\,y,\,z} \right) = \sum {\left( {1,\,3,\,4,\,6,\,9,\,11,\,12,\,14} \right)} $$ the function is
62
Let $$G$$ be the non-planar graph with minimum possible number of edges. Then $$G$$ has
63
Let $$A$$ be the matrix $$\left[ {\matrix{ 3 & 1 \cr 1 & 2 \cr } } \right]$$. What is the maximum value of $${x^T}Ax$$ where the maximum is taken over all $$x$$ that are the unit eigenvectors of $$A$$?
64
Let $$A$$ be $$a$$ $$4$$ $$x$$ $$4$$ matrix with eigen values $$-5$$, $$-2, 1, 4$$.

Which of the following is an eigen value of $$\left[ {\matrix{ {\rm A} & {\rm I} \cr {\rm I} & {\rm A} \cr } } \right]$$, where $$I$$ is the $$4$$ $$x$$ $$4$$ identity matrix?

65
Which of the following graphs has an Eulerian circuit?
66
Let Graph$$(x)$$ be a predicate which denotes that $$x$$ is a graph. Let Connected$$(x)$$ be a predicate which denotes that $$x$$ is connected. Which of the following first order logic sentences DOES NOT represent the statement: $$Not\,\,\,every\,\,\,graph\,\,\,is\,\,\,connected?$$
67
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $$(i, j)$$ then it can move to either $$(i+1, j)$$ or $$(i, j+1)$$

Suppose that the robot is not allowed to traverse the line segment from $$(4, 4)$$ to $$(5,4)$$. With this constraint, how many distinct path are there for the robot to reach $$(10, 10)$$ starting from $$(0,0)$$?

68
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $$(i, j)$$ then it can move to either $$(i+1, j)$$ or $$(i, j+1)$$

How many distinct path are there for the robot to reach the point $$(10, 10)$$ starting from the initial position $$(0, 0)$$?

69
Consider the following two statements about the function $$$f\left( x \right) = \left| x \right|:$$$

$$P.\,\,f\left( x \right)$$ is continuous for all real values of $$x$$
$$Q.\,\,f\left( x \right)$$ is differentiable for all real values of $$x$$

Which of the following is True?

70
Consider a weighted undirected graph with positive edge weights and let $$uv$$ be an edge in the graph. It is known that the shortest path from the source vertex $$s$$ to $$u$$ has weight 53 and the shortest path from $$s$$ to $$v$$ has weighted 65. Which one of the following statements is always true?
71
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height $$h$$ is:
72
The maximum number of binary trees that can be formed with three unlabeled nodes is:
73
Consider the set of (column) vectors defined by $$X = \,\{ \,x\, \in \,{R^3}\,\left| {{x_1}\, + \,{x_2}\, + \,{x_3} = 0} \right.$$, where $${x^T} = \,{[{x_1}\, + \,{x_2}\, + \,{x_3}]^T}\} .$$ Which of the following is TRUE?
74
A partial order P is defined on the set of natural numbers as following. Herw x/y denotes integer division.
i) (0, 0) $$ \in \,P$$.
ii) (a, b) $$ \in \,P$$ if and only a %
$$10\, \le $$ b % 10 and
)a/10, b/10) $$ \in \,P$$.

Consider the following ordered pairs:
$$\matrix{ {i)\,\,\,(101,\,22)} & {ii)\,\,\,(22,\,\,101)} \cr {iii)\,\,\,(145,\,\,265)} & {iv)\,\,\,(0,\,153)} \cr } $$
Which of these ordered pairs of natural numbers are comtained in P?

75
Consider the following Hasse diagrams.
GATE CSE 2007 Discrete Mathematics - Set Theory & Algebra Question 40 English 1
GATE CSE 2007 Discrete Mathematics - Set Theory & Algebra Question 40 English 2
GATE CSE 2007 Discrete Mathematics - Set Theory & Algebra Question 40 English 3
GATE CSE 2007 Discrete Mathematics - Set Theory & Algebra Question 40 English 4

Which all of the above represent a lattice?

76
Let $$S$$ be a set6 of $$n$$ elements. The number of ordered pairs in the largest and the smallest equivalence relations on $$S$$ are
77
What is the maximum number of different Boolean functions involving $$n$$ Boolean variables?
78
How many different non-isomorphic Abelian groups of order 4 are there?
79
Which one of these first-order logic formulae is valid?
80
Suppose we uniformly and randomly select a permutation from the 20! permutations of 1, 2, 3,..., 20. What is the promutations that 2 appears at an earlier position than any other even number in the selected permutation?
81
Suppose there are two coins. The first coin gives heads with probability 5/8 when tossed, while the second coin gives heads with probability 1/4. On e of the two coins is picked up at random with equal probability and tossed. What is the probability of obtaining heads?
82
A process has been allocated $$3$$ page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): $$$1, 2, 1, 3, 7, 4, 5, 6, 3, 1$$$

If optimal page replacement policy is used, how many page faults occur for the above reference string?

83
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 exhibit locality of reference.

Which one of the following is TRUE?

84
A process has been allocated $$3$$ page frames. Assume that none of the pages of the process are available in the memory initially. The process makes the following sequence of page references (reference string): $$$1, 2, 1, 3, 7, 4, 5, 6, 3, 1$$$

Least Recently Used (LRU) page replacement policy is a practical approximation to optimal page replacement. For the above reference string, how many more page faults occur with LRU than with the optimal page replacement policy?

85
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 request denotes the number of units of each resource type requested by a process in order to complete execution. Which of these processes will finish LAST? GATE CSE 2007 Operating Systems - Deadlocks Question 17 English
86
Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk are respectively:
87
Group-1 contains some $$CPU$$ scheduling algorithms and Group-2 contains some applications. Match entries in Group-1 to entries in Group-2.

Group-1
(P) Gang Scheduling
(Q) Rate Monotonic Scheduling
(R) Fair Share Scheduling

Group-2
(1) Guaranteed Scheduling
(2) Real-time Scheduling
(3) Thread Scheduling

88
Consider the following statements about user level threads and kernel level threads.

Which one of the following statements is FALSE?

89
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){
  want s1=true;
  while(wants2 == true){
  /* Critical Section */
   wants1 = false;
  }
  /* Reminder Section */
 }
 /* P2 */
  while(true){
  want s2=true;
  while(wants1 == true){
  /* Critical Section */
   Wants2 = false;
  }
  /* Reminder Section */
 }
Here wants1 and wants2 are shared variables, which are initialized to false. Which one of the following statements is TRUE about the above construct?
90
An operating system uses Shortest Remaining Time first $$(SRT)$$ process scheduling algorithm. Consider the arrival times and execution times for the following processes: GATE CSE 2007 Operating Systems - Process Concepts and Cpu Scheduling Question 25 English

What is the total waiting time for process $$P2?$$

91
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)?
92
Consider the following finite state automation GATE CSE 2007 Theory of Computation - Finite Automata and Regular Language Question 60 English

The minimum state automation equivalent to the above $$FSA$$ has the following number of states

93
Consider the following finite state automation GATE CSE 2007 Theory of Computation - Finite Automata and Regular Language Question 61 English

The language accepted by this automation is given by the regular expression

94
Which of the following languages is regular?
95
A minimum state deterministic finite automation accepting the language $$L = \left\{ {w\left| {w \in } \right.\,\,{{\left\{ {0,1} \right\}}^ * },\,\,} \right.$$ number of $$0'$$s and $$1'$$s in $$w$$ are divisible by $$3$$ and $$5$$, respectively$$\left. \, \right\}$$ has
96
Consider the $$CFG$$ with $$\left\{ {S,A,B} \right\}$$ as the non-terminal alphabet, $$\left\{ {a,b} \right\}$$ as the terminal alphabet, $$S$$ as the start symbol and the following set of production rules: GATE CSE 2007 Theory of Computation - Push Down Automata and Context Free Language Question 32 English

Which of the following strings is generated by the grammar?

97
The language $$L = \left\{ {{0^i}{{21}^i}\,|\,i \ge 0} \right\}$$ over the alphabet $$\left\{ {0,1,2} \right\}$$ is
98
Consider the $$CFG$$ with $$\left\{ {S,A,B} \right\}$$ as the non-terminal alphabet, $$\left\{ {a,b} \right\}$$ as the terminal alphabet, $$S$$ as the start symbol and the following set of production rules: GATE CSE 2007 Theory of Computation - Push Down Automata and Context Free Language Question 31 English

For the correct string of (earlier question) how many derivation trees are there?

EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12