GATE CS question library

The following program consists of $3$ concurrent processes and $3$ binary semaphores. The semaphores are initialized as $S0=1, S1=0$ and $S2=0.$ …

The following program is to be tested for statement coverage: begin if (a==b) {S1; exit;} else if (c==d) {S2;} else {S3; exit;} S4; end The test cases T1, T2, T3 and T4 given below are expressed in terms of the properties satisfied by the values of variables $a,\:b,\:c$ and $d$. The exact values are not given. T1: a, b, c and d are all equal T2: a, b, c …

The following functional dependencies hold for relations $R(A, B, C)$ and $S(B, D, E).$ $B \to A$ $A \to C$ The relation $R$ contains $200$ tuples and the relation $S$ contains $100$ tuples. What is the maximum number of tuples possible in the natural join $R \bowtie S$?

Consider the following schedule for transactions $T1, T2$ and $T3:$ …

Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automation that accepts $L$?

Consider the languages $L1=\{0^i1^j\ \mid i \neq j\},$ $L2=\{0^i1^j\mid i=j\},$ $L3=\{0^i1^j \mid i=2j+1\},$ $L4=\{0^i1^j \mid i\neq2j\}$

Let $L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$. i.e., $L$ is the set of all the bit strings with even numbers of $1$s. Which one of the regular expressions below represents $L$?

The grammar $S \to aSa \mid bS \mid c$ is

The program below uses six temporary variables $a, b, c, d, e, f$. a = 1 b = 10 c = 20 d = a + b e = c + d f = c + e b = c + e e = b + f d = 5 + e return d + f Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?

The following C function takes a singly-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. typedef struct node { int value; struct node *next; } Node; Node *move_to-front(Node *head) { Node *p, *q; if ((head == NULL) || (head -> next == …

What is the value printed by the following C program? #include<stdio.h> int f(int *a, int n) { if (n <= 0) return 0; else if (*a % 2 == 0) return *a+f(a+1, n-1); else return *a - f(a+1, n-1); } int main() { int a[] = {12, 7, 13, 4, 11, 6}; printf("%d", f(a, 6)); return 0; }

The weight of a sequence $a_0,a_1, \dots, a_{n-1}$ of real numbers is defined as $a_0+a_1/2+ \dots + a_{n-1}/2^{n-1}$. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let $X$ denote the maximum possible weight of a subsequence of $a_o,a_1, \dots, a_{n-1}$ and …

A $5-$stage pipelined processor has Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Write Operand (WO) stages. The IF, ID, OF and WO stages take $1$ clock cycle each for any instruction. The PO stage takes $1$ clock cycle for ADD and SUB instructions, $3$ clock cycles for MUL instruction and $6$ clock …

In the sequential circuit shown below, if the initial value of the output $Q_1Q_0$ is $00$. What are the next four values of $Q_1Q_0$?

What is the boolean expression for the output $f$ of the combinational logic circuit of NOR gates given below?

Which of the following statements are true? Shortest remaining time first scheduling may cause starvation Preemptive scheduling may cause starvation Round robin is better than FCFS in terms of response time

A system uses FIFO policy for system replacement. It has $4$ page frames with no pages loaded to begin with. The system first accesses $100$ distinct pages in some order and then accesses the same $100$ pages but now in the reverse order. How many page faults will occur?

What is the appropriate pairing of items in the two columns listing various activities encountered in a software life cycle? P. Requirements Capture 1. Module Development and Integration Q. Design 2. Domain Analysis R. Implementation 3. Structural and Behavioral Modeling S. Maintenance 4. Performance Tuning

Consider the methods used by processes $P1$ and $P2$ for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables $S1$ and $S2$ are randomly assigned. …

The cyclomatic complexity of each of the modules $\text{A}$ and $\text{B}$ shown below is $10.$ What is the cyclomatic complexity of the sequential integration shown on the right hand side?