search
Log In
GATE 1993 Computer Science Questions and Solutions

Recent questions tagged gate1993

4 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)?
asked Feb 5, 2018 in Databases jothee 593 views
28 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
asked Sep 20, 2015 in Digital Logic jothee 4.6k views
11 votes
2 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$
asked Sep 20, 2015 in Digital Logic jothee 2.3k views
20 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$
asked Sep 30, 2014 in Set Theory & Algebra Kathleen 1.4k views
23 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$.
asked Sep 30, 2014 in Theory of Computation Kathleen 3.1k views
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?
asked Sep 30, 2014 in Compiler Design Kathleen 961 views
4 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 ;…; 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
asked Sep 30, 2014 in Compiler Design Kathleen 495 views
16 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.
asked Sep 30, 2014 in Databases Kathleen 1.2k views
23 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.
asked Sep 30, 2014 in Operating System Kathleen 2.3k views
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
asked Sep 30, 2014 in Operating System Kathleen 1.3k views
0 votes
0 answers
11
14 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.
asked Sep 30, 2014 in Digital Logic Kathleen 1.4k views
8 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.
asked Sep 30, 2014 in Mathematical Logic Kathleen 1.1k views
21 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?
asked Sep 30, 2014 in Set Theory & Algebra Kathleen 2.6k views
15 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.
asked Sep 30, 2014 in DS Kathleen 924 views
12 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$.
asked Sep 30, 2014 in Algorithms Kathleen 868 views
26 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?
asked Sep 30, 2014 in Databases Kathleen 2.1k views
7 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.
asked Sep 30, 2014 in DS Kathleen 1.1k views
15 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
asked Sep 30, 2014 in DS Kathleen 1.7k views
33 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.
asked Sep 30, 2014 in CO and Architecture Kathleen 4.2k views
22 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?
asked Sep 30, 2014 in CO and Architecture Kathleen 2.7k views
12 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.
asked Sep 30, 2014 in Digital Logic Kathleen 749 views
26 votes
6 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)$
asked Sep 30, 2014 in Algorithms Kathleen 2.7k views
15 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$
asked Sep 30, 2014 in Set Theory & Algebra Kathleen 1.3k views
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
asked Sep 30, 2014 in Set Theory & Algebra Kathleen 2k views
16 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
asked Sep 30, 2014 in Set Theory & Algebra Kathleen 2k views
22 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 set $S_i$ is a finite set not more than one of the set $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
asked Sep 30, 2014 in Set Theory & Algebra Kathleen 2.2k views
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
asked Sep 30, 2014 in Mathematical Logic Kathleen 1.6k views
16 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
asked Sep 30, 2014 in Graph Theory Kathleen 2.3k views
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
asked Sep 30, 2014 in Operating System Kathleen 3.3k views
...