GATE 1989 Computer Science Questions

# Recent questions tagged gate1989

1
Provide short answers to the following questions: How many substrings (of all lengths inclusive) can be formed from a character string of length $n$? Assume all characters to be distinct, prove your answer.
2
Answer the following: Which one of the following statements (s) is/are FALSE? Overlaying is used to run a program, which is longer than the address space of the computer. Optimal binary search tree construction can be performed efficiently by using dynamic programming ... components of a graph. Given the prefix and postfix walls over a binary tree, the binary tree can be uniquely constructed.
3
Answer the following: Which of the following statements are FALSE? For poisson distribution, the mean is twice the variance. In queuing theory, if arrivals occur according to poisson distribution, then the inter-arrival time is exponentially distributed. The ... the time between successive arrivals is exponential, then the time between the occurences of every third arrival is also exponential.
4
Which of the following graphs is/are planner?
5
Answer the following: Which of the following well-formed formulas are equivalent? $P \rightarrow Q$ $\neg Q \rightarrow \neg P$ $\neg P \vee Q$ $\neg Q \rightarrow P$
6
Answer the following questions: Which of the following problems are undecidable? Membership problem in context-free languages. Whether a given context-free language is regular. Whether a finite state automation halts on all inputs. Membership problem for type $0$ languages.
7
Context-free languages and regular languages are both closed under the operation (s) of : Union Intersection Concatenation Complementation
8
An unrestricted use of the "go to" statement is harmful because of which of the following reason (s): It makes it more difficult to verify programs. It makes programs more inefficient. It makes it more difficult to modify existing programs. It results in the compiler generating longer machine code.
9
Match the pairs in the following: ...
10
Match the pairs in the following:$\begin{array}{ll|ll}\hline \text{(A)} & \text{$O (\log n)$} & \text{(p)} & \text{Heapsort} \\\hline \text{(B)} & \text{$O (n)$} & \text{(q)}& \text{Depth-first search} \\\hline \text{(C)}& \text{$ ... $} &\text{(s)} & \text{Selection of the$k^{th}$smallest element in a set of$n$elements} \\\hline \end{array}$
11
Match the pairs in the following questions: ...
12
Match the pairs in the following questions: $\begin{array}{|l|l|l|} \hline \text {(A) Cyclic Redundancy Code} & \text {(p) Error Correction} \\\hline \text {(B) Serial Communication} & \text{(q) Wired-OR } \\\hline \text{(C) Open Collector} & \text{(r) Error detection} \\\hline \text{(D) Hamming Code} & \text{(s) RS-232-C} \\\hline \end{array}$
13
Consider an excess - 50 representation for floating point numbers with $4 BCD$ digit mantissa and $2 BCD$ digit exponent in normalised form. The minimum and maximum positive numbers that can be represented are __________ and _____________ respectively.
14
The number of possible commutative binary operations that can be defined on a set of $n$ elements (for a given n) is ___________.
15
The transitive closure of the relation $\left\{(1, 2), (2, 3), (3, 4), (5, 4)\right\}$ on the set $\left\{1, 2, 3, 4, 5\right\}$ is ___________.
A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols $S1$ to $S7$ initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is $4$ $5$ $6$ $3$