GATE 1989 Computer Science Questions

# Recent questions tagged gate1989 18 votes
4 answers
1
Symbolize the expression "Every mother loves her children" in predicate logic.
19 votes
3 answers
2
Find the number of single valued functions from set A to another set B, given that the cardinalities of the sets A and B are $m$ and $n$ respectively.
13 votes
3 answers
3
Find a solution to the following recurrence equation: $T(n)=\sqrt{n}+T(\frac{n}{2})$ $T(1)=1$
5 votes
2 answers
4
A language uses an alphabet of six letters, $\left\{a, b, c, d, e, f\right\}$ ... Design a prefix binary code for the language which would minimize the average length of the encoded words of the language.
0 votes
0 answers
5
Consider a database with the following three relations: CREDITS (STUDENT; COURSE) OFFERS (TEACHER; COURSE) BELONGS (TEACHER; DEPARTMENT) Given below is a code in query language QUEL. Describe in one English sentence the query posed by the given QUEL program. range of s is CREDITS range of t ... is LIST1 range of e2 is LIST2 range of e3 is LIST3 retrieve(E1.I) where e1.I=e2.I and where e1.I=e3.I
27 votes
3 answers
6
Fig.7 shows a $B+$ tree where only key values are indicated in the records. Each block can hold upto three records. A record with a key value $34$ is inserted into the $B+$ tree. Obtain the modified $B+$ tree after insertion.
5 votes
1 answer
7
Consider the following precedence graph (Fig.6) of processes where a node denotes a process and a directed edge from node $P_{i}$ to node $P_{j}$ implies; that $P_{i}$ must complete before $P_{j}$ commences. Implement the graph using FORK and JOIN constructs. The actual computation done by a process may be indicated by a comment line.
11 votes
4 answers
8
A system of four concurrent processes, $P, Q, R$ and $S$, use shared resources $A, B$ and $C$. The sequences in which processes, $P, Q, R$ and $S$ ... processes. What strategies can be used to prevent deadlocks in a system of concurrent processes using shared resources if preemption of granted resources is not allowed?
0 votes
0 answers
9
Consider the following grammar for variable declarations: <vardecl> $\rightarrow$ <vardecl><idlist> : <type>; <vardecl> $\rightarrow \in$ <idlist> $\rightarrow$ <idlist>, id <idlist> $\rightarrow$ id <type> $\rightarrow$ integer <type> ... error messages wherever necessary. Make suitable assumptions regarding procedures operating on the symbol table; you need not elaborate upon these procedures.
0 votes
1 answer
10
Will recursion work correctly in a language with static allocation of all variables? Explain.
9 votes
1 answer
11
An input files has $10$ records with keys as given below: $25\quad 7\quad 34\quad 2\quad 70\quad 9\quad 61\quad 16\quad 49\quad 19$ This is to be sorted in non-decreasing order. Sort the input file using QUICKSORT by correctly positioning ... brackets to demarcate subfiles. Sort the input file using 2-way- MERGESORT showing all major intermediate steps. Use square brackets to demarcate subfiles.
1 vote
1 answer
12
Indicate the result of the following program if the language uses (i) static scope rules and (ii) dynamic scope rules. var x, y:integer; procedure A (var z:integer); var x:integer; begin x:=1; B; z:= x end; procedure B; begin x:=x+1 end; begin x:=5; A(y); write (y) ...end.
1 vote
2 answers
13
What is the output produced by the following program, when the input is "HTGATE" Function what (s:string): string; var n:integer; begin n = s.length if n <= 1 then what := s else what :=contact (what (substring (s, 2, n)), s.C ) end; Note type string=record length:integer; ... $s_{1}$ length + $s_{2}$ - length obtained by concatenating $s_{1}$ with $s_{2}$ such that $s_{1}$ precedes $s_{2}$.
0 votes
0 answers
14
An 8085-based microcomputer consisting of 16 kbytes of ROM, 16kbytes of RAM and four 8-bit I/O ports is to be designed using RAM and ROM chips each of 2 kbytes capacity. The chip to be used for I/O ports realization consists of two 8-bit ports and requires four ... in the memory address space. The I/O locations are to occupy lower order I/O address space. Give memory map and I/O address map.
0 votes
0 answers
15
In a certain computer system, there is special instruction implemented to call subroutines. The instruction is JSR Reg.Sub Microsequence: Temp ← Sub SP ← (SP)+2 (SP) ← (Reg) Reg ← (PC) PC ← (Temp) Where Temp is an internal CPU register Sub is calling ... you would implement co-routine using the JSR instruction. Show the control flow diagram and the contents of the stack before and after the call.
0 votes
0 answers
16
A certain computer system was designed with cache memory of size $1$ Kbytes and main memory size of $256$ Kbytes. The cache implementation was fully associative cache with $4$ bytes per block. The CPU memory data path was $16$ ... Answer the following questions: What is the hit ratio? Suggest a change in the program size of model to improve the hit ratio significantly.
5 votes
0 answers
17
It is required to implement a stack using bidirectional shift registers providing stack under flow and overflow detection capability. How many shift registers are needed for a stack capacity of $n$ $k-$bit words? Show the schematic diagram of the implementation, clearly indicating all the data and control lines.
19 votes
5 answers
18
Find values of Boolean variables $A, B, C$ which satisfy the following equations: A+ B = 1 AC = BC A + C = 1 AB = 0
5 votes
2 answers
19
Provide short answers to the following questions: For secondary key processing which of the following file organizations is preferred? Give a one line justification: Indexed sequential file organization. Two-way linked list. Inverted file organization. Sequential file organization.
0 votes
0 answers
20
Provide short answers to the following questions: Consider the following sequence of UNIX commands: grep main a.c b.c c.c > grepout & wc < grepout & rm grepout & Why is this not equivalent to the following? grep main a.c.b.c c.c | wc
20 votes
2 answers
21
Provide short answers to the following questions: Disk requests come to disk driver for cylinders $10, 22, 20, 2, 40, 6$ and $38$, in that order at a time when the disk drive is reading from cylinder $20$. The seek time is $6$ msec per cylinder. Compute the total seek time if the disk arm scheduling algorithm is. First come first served. Closest cylinder next.
2 votes
1 answer
22
Provide short answers to the following questions: Express the following list in terms of a linked list structure suitable for internal representation. $(((ab)c)d((e)))$
3 votes
1 answer
23
Provide short answers to the following questions: A switching function is said to be neutral if the number of input combinations for which its value is 1 is equal to the number of input combinations for which its value is 0. Compute the number of neutral switching functions of $n$ variables (for a given n).
7 votes
2 answers
24
Provide short answers to the following questions: Explain the behaviour of the following logic circuit (Fig.4) with level input A and output B
2 votes
1 answer
25
Provide short answers to the following questions: $P_{n} (t)$ is the probability of $n$ events occurring during a time interval $t$. How will you express $P_{0} (t + h)$ in terms of $P_{0} (h)$, if $P_{0} (t)$ has stationary independent increments? (Note: $P_{t} (t)$is the probability density function).
4 votes
2 answers
26
Provide short answers to the following questions: In the graph shown above, the depth-first spanning tree edges are marked with a 'T'. Identify the forward, backward and cross edges.
0 votes
0 answers
27
Provide short answers to the following questions: Consider the definition of macro B, nested within the definition of a macro A. Can a call to macro B also appear within macro A? If not, why not? If yes, explain if there are any restrictions.
1 vote
1 answer
28
Is the following code template for the if-then-else statement correct? if not, correct it. if expression then statement $1$ else statement $2$ Template: Code for expression (*result in $E, E > O$ indicates true *) Branch on $E > O$ to $L1$ Code for statement $1$ $L1$: Code for statement $2$
7 votes
3 answers
29
Provide short answers to the following questions: Show that {NOR} is a functionally complete set of Boolean operations.
2 votes
1 answer
30
Provide short answers to the following questions: Compute the postfix equivalent of the following infix arithmetic expression $a + b * c + d * e ↑ f$ where $↑$ represents exponentiation. Assume normal operator precedences.