GATE 1993 Computer Science Questions and Solutions

# Recent questions tagged gate1993 6 votes
1 answer
1
The following relations are used to store data about students, courses, enrollment of students in courses and teachers of courses. Attributes for primary key in each relation are marked by *'. Students (rollno*, sname, saddr) courses (cno*, cname) enroll(rollno*, cno*, grade) teach ... )? If yes, prove that it is in 3 NF. If not normalize, the relations so that they are in 3NF (without proving)?
31 votes
9 answers
2
Multiple choices can be correct. Mark all of them. For the initial state of $000$, the function performed by the arrangement of the $J-K$ flip-flops in figure is: Shift Register $Mod- 3$ Counter $Mod- 6$ Counter $Mod- 2$ Counter None of the above
15 votes
3 answers
3
If the state machine described in figure should have a stable state, the restriction on the inputs is given by $a.b=1$ $a+b=1$ $\bar{a} + \bar{b} =0$ $\overline{a.b}=1$ $\overline{a+b} =1$
21 votes
3 answers
4
Let $\left(\{ p,q \},*\right)$ be a semigroup where $p*p=q$. Show that: $p*q=q*p$ and $q*q=q$
26 votes
5 answers
5
Draw the state transition of a deterministic finite state automaton which accepts all strings from the alphabet $\{a,b\}$, such that no string has $3$ consecutive occurrences of the letter $b$.
8 votes
2 answers
6
A stack is used to pass parameters to procedures in a procedure call. If a procedure $P$ has two parameters as described in procedure definition: procedure P (var x :integer; y: integer); and if $P$ is called by ; $P(a, b)$ State precisely in a sentence what is pushed ... $b$ In the generated code for the body of procedure $P$, how will the addressing of formal parameters $x$ and $y$ differ?
5 votes
1 answer
7
A simple Pascal like language has only three statements. assignment statement e.g. x:=expression loop construct e.g. for i:=expression to expression do statement sequencing e.g. begin statement ;&hellip;; statement end Write a context-free grammar (CFG) for statements in the above ... in CFG. Show the parse tree for the following statements: for j:=2 to 10 do begin x:=expr1; y:=expr2; end
18 votes
4 answers
8
The following relations are used to store data about students, courses, enrollment of students in courses and teachers of courses. Attributes for primary key in each relation are marked by *'. Students (rollno*, sname, saddr) courses (cno*, cname) enroll(rollno* ... number and name of students who got A grade in at least one course taught by teacher names Ramesh for the above relational database.
24 votes
4 answers
9
Write a concurrent program using $\text{parbegin-parend}$ and semaphores to represent the precedence constraints of the statements $S_1$ to $S_6$, as shown in figure below.
13 votes
2 answers
10
The following page addresses, in the given sequence, were generated by a program: $\text{1 2 3 4 1 3 5 2 1 5 4 3 2 3}$ This program is run on a demand paged virtual memory system, with main memory size equal to $4$ pages. Indicate the page references for which page faults occur for the following page replacement algorithms. LRU FIFO Assume that the main memory is initially empty
0 votes
0 answers
11
17 votes
1 answer
12
A control algorithm is implemented by the NAND – gate circuitry given in figure below, where $A$ and $B$ are state variable implemented by $D$ flip-flops, and $P$ is control input. Develop the state transition table for this controller.
9 votes
3 answers
13
Show that proposition $C$ is a logical consequence of the formula$A\wedge \left(A \to \left(B \vee C\right)\right) \wedge \left( B \to \neg A\right)$using truth tables.
27 votes
3 answers
14
Out of a group of $21$ persons, $9$ eat vegetables, $10$ eat fish and $7$ eat eggs. $5$ persons eat all three. How many persons eat at least two out of the three dishes?
16 votes
2 answers
15
Prove by the principal of mathematical induction that for any binary tree, in which every non-leaf node has $2$-descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.
13 votes
1 answer
16
Consider the recursive algorithm given below: procedure bubblesort (n); var i,j: index; temp : item; begin for i:=1 to n-1 do if A[i] > A[i+1] then begin temp := A[i]; A[i] := A[i+1]; A[i+1] := temp; end; bubblesort (n-1) end Let $a_n$ be ... ' statement gets executed when the algorithm is run with value $n$. Set up the recurrence relation by defining $a_n$ in terms of $a_{n-1}$. Solve for $a_n$.
29 votes
3 answers
17
An $\text{ISAM}$ (indexed sequential) file consists of records of size $64$ $bytes$ each, including key field of size $14$ $bytes$. An address of a disk block takes $2$ $bytes$. If the disk block size is $512$ $bytes$ and there are $16$ $K$ records, compute the size of the data and index areas in terms of number blocks. How many levels of $\text{tree}$ do you have for the index?
8 votes
3 answers
18
Consider a singly linked list having $n$ nodes. The data items $d_1, d_2, \dots d_n$ are stored in these $n$ nodes. Let $X$ be a pointer to the $j^{th}$ node $(1 \leq j \leq n)$ in which $d_j$ is stored. A new data item $d$ ... algorithm to insert $d$ into the list to obtain a list having items $d_1, d_2, \dots, d_{j}, d,\dots, d_n$ in order without using the header.
20 votes
2 answers
19
The following Pascal program segments finds the largest number in a two-dimensional integer array $A[0\dots n-1, 0\dots n-1]$ using a single loop. Fill up the boxes to complete the program and write against $\fbox{A}, \fbox{B}, \fbox{C} \text{ and } \fbox{D}$ in your answer book Assume that max is ... begin if A[i, j]>max then max:=A[i, j]; if |C| then j:=j+1; else begin j:=0; i:=|D| end end end
37 votes
6 answers
20
In the three-level memory hierarchy shown in the following table, $p_i$ denotes the probability that an access request will refer to $M_i$ ... for such a page swap is $T_i$. Calculate the average time $t_A$ required for a processor to read one word from this memory system.
25 votes
2 answers
21
The instruction format of a CPU is: \begin{array}{|c|c|c|} \hline \text {OP CODE} & \text{MODE}& \text{RegR} \\\hline \end{array}\begin{array}{|c||} \text {___one memory word___} \end{array} $\text{Mode}$ and $\text{RegR}$ together specify the ... (PC). What is the address of the operand? Assuming that is a non-jump instruction, what are the contents of PC after the execution of this instruction?
14 votes
1 answer
22
Assume that only half adders are available in your laboratory. Show that any binary function can be implemented using half adders only.
31 votes
7 answers
23
$\displaystyle \sum_{1\leq k\leq n} O(n)$, where $O(n)$ stands for order $n$ is: $O(n)$ $O(n^2)$ $O(n^3)$ $O(3n^2)$ $O(1.5n^2)$
17 votes
3 answers
24
Let $A$ and $B$ be sets with cardinalities $m$ and $n$ respectively. The number of one-one mappings from $A$ to $B$, when $m < n$, is $m^n$ $^nP_m$ $^mC_n$ $^nC_m$ $^mP_n$
13 votes
3 answers
25
The less-than relation, $<,$ on reals is a partial ordering since it is asymmetric and reflexive a partial ordering since it is antisymmetric and reflexive not a partial ordering because it is not asymmetric and not reflexive not a partial ordering because it is not antisymmetric and reflexive none of the above
17 votes
2 answers
26
Let A be a finite set of size n. The number of elements in the power set of $A\times A$ is: $2^{2^n}$ $2^{n^2}$ $(2^n)^2$ $(2^2)^n$ None of the above
23 votes
3 answers
27
Let $S$ be an infinite set and $S_1 \dots , S_n$ be sets such that $S_1 \cup S_2 \cup \dots \cup S_n = S$. Then at least one of the sets $S_i$ is a finite set not more than one of the sets $S_i$ can be finite at least one of the sets $S_i$ is an infinite not more than one of the sets $S_i$ can be infinite None of the above
17 votes
4 answers
28
The proposition $p \wedge (\sim p \vee q)$ is: a tautology logically equivalent to $p \wedge q$ logically equivalent to $p \vee q$ a contradiction none of the above
17 votes
2 answers
29
Consider a simple connected graph $G$ with $n$ vertices and $n$ edges $(n > 2)$. Then, which of the following statements are true? $G$ has no cycles The graph obtained by removing any edge from $G$ is not connected $G$ has at least one cycle The graph obtained by removing any two edges from $G$ is not connected None of the above
20 votes
3 answers
30
Assume that the following jobs are to be executed on a single processor system ... Calculate the departure time (completion time) for job $p$ if scheduling is round robin with time slice $1$ $4$ $10$ $11$ $12$ None of the above