GATE CSE 2002
View Questions

GATE CSE

1
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
2
Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values:
1. Choose an i uniformly at random fro 1..n;
2. If A[i]=x then stop else Goto 1;
Assuming that x is present A, what is the expected number of comparisons made by the algorithm before it terminates?
3
The running time of the following algorithm Procedure A(n)
If n<=2 return (1) else return (A([$$\sqrt n $$])); is best described by
4
The solution to the recurrence equation
T(2k) = 3 T(2k-1) + 1, T (1) = 1, is:
5
Which of the following is not a form of memory?
6
Sign extension is the step in
7
The performance of a pipelined processor suffers if
8
In $$2’s$$ complement addition, the overflow
9
In absolute addressing mode
10
Horizontal micro programming
11
In serial data transmission, every byte of data is padded with a $$‘0’$$ in the beginning and one or two $$‘1’s$$ at the end of byte because
12
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
13
The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
14
Relation $$R$$ with an associated set of functional dependencies, $$F,$$ is decomposed into $$BCNF.$$ The redundancy (arising out of functional dependencies) in the resulting set of relations is
15
From the following instance of a relation schema $$R(A, B, C),$$ we can conclude that: GATE CSE 2002 Database Management System - Functional Dependencies and Normalization Question 28 English
16
Relation $$R$$ is decomposed using a set of functional dependencies, $$F,$$ and relation $$S$$ is decomposed using another set of functional dependencies, $$G.$$ One decomposition is definitely $$BCNF,$$ the other is definitely. $$3NF,$$ but it is not known which is which. To make a guaranteed identification, which one of the following tests should be used on the decompositions? (Assume that the closures of $$F$$ and $$G$$ are available).
17
With regard to the expressive power of the formal relational query languages, which of the following statements is true?
18
A B+ - tree index is to be built on the Name attribute of the relation STUDENT. Assume that all student names are of length 8 bytes, disk blocks are of size 512 bytes, and index pointers are of size 4 bytes. Given this scenario, what would be the best choice of the degree (i.e. the number of pointers per node) of the B+ - tree?
19
Consider the following multiplexer where $$10, 11, 12, 13$$ are four data input lines selected by two address line combinations $${A_1}\,{A_0} = 00,01,10,11$$ respectively and $$f$$ is the output of the multiplex (or). $$EN$$ is the Enable input. GATE CSE 2002 Digital Logic - Combinational Circuits Question 15 English

The function $$f(x,y,z)$$ implemented by the above circuit is

20
The decimal value $$0.25$$
21
The $$2's$$ compliment representation of the decimal value $$-15$$ is
22
Sign extension is the step in
23
Consider the following logic circuit whose inputs are functions $${f_1},$$ $${f_2},$$ $${f_3},$$ and output is $$f.$$ GATE CSE 2002 Digital Logic - Boolean Algebra Question 35 English
24
Transform the following logic circuit (without expressing its switching function) into an equivalent logic circuit that employs only $$6$$ $$NAND$$ gates each with $$2$$-inputs. GATE CSE 2002 Digital Logic - Boolean Algebra Question 36 English
25
$$f\left( {A,B} \right) = A' + B$$ Simplified expression for function $$f((x+y,y),z)$$ is
26
Express the function $$f( x, y, z)= xy'+ yz'$$ with only one complement operation and one or more $$AND/OR$$ operations. Draw the logic circuit implementing the expression obtained, using a single NOT gate and one or more $$AND/OR$$ gates.
27
Minimum $$SOP$$ for $$f(w, x, y, z)$$ shown in karnaugh $$-$$ map below is GATE CSE 2002 Digital Logic - K Maps Question 11 English
28
Four fair coins are tossed simultaneously. The probability that at least one head and one tail turn up is
29
The binary relation $$S = \phi $$ (emply set) on set A = {1, 2, 3} is
30
Determine whether each of the following is a tautology, a contradiction, or neither ("$$ \vee $$" is disjunction, "$$ \wedge $$" is conjuction, "$$ \to $$" is implication, "$$\neg $$" is negation, and "$$ \leftrightarrow $$" is biconditional (if and only if).

(i)$$\,\,\,\,\,\,A \leftrightarrow \left( {A \vee A} \right)$$
(ii)$$\,\,\,\,\,\,\left( {A \vee B} \right) \to B$$
(iii)$$\,\,\,\,\,\,A \vee \left( {\neg \left( {A \vee B} \right)} \right)$$

31
The minimum number of colors required to color the vertices of a cycle with $$n$$ nodes in such a way that no two adjacent nodes have the same colour is:
32
The rank of the matrix$$\left[ {\matrix{ 1 & 1 \cr 0 & 0 \cr } } \right]\,\,is$$
33
Maximum number of edges in a n - node undirected graph without self loops is
34
Let $$A$$ be a set of $$n\left( { > 0} \right)$$ elements. Let $${N_r}$$ be the number of binary relations on $$A$$ and Let $${N_r}$$ be the number of functions from $$A$$ to $$A$$.
(a) Give the expression for $${N_r}$$ in terms of $$n$$.
(b) Give the expression for $${N_f}$$ in terms of $$n$$.
(c) Which is larger for all possible $$n, $$ $${N_r}$$ or $${N_f}$$?
35
(a) $$S = \left\{ { < 1,2 > ,\, < 2,1 > } \right\}$$ is binary relation on set $$A = \left\{ {1,2,3} \right\}$$. Is it irreflexive?
Add the minimumnumber of ordered pairs to $$S$$ to make it an $$\,\,\,\,\,$$equivalence relation. Give the modified $$S$$.

(b) Let $$S = \left\{ {a,\,\,b} \right\}\,\,\,\,$$ and let ▢ $$S$$ be the power set of $$S$$. Consider the binary relation $$'\underline \subset $$ (set inclusion)' on ▢ $$S$$. Draw the Hasse diagram corresponding to the lattice (▢$$(S)$$, $$\underline \subset $$)

36
Obtain the eigen values of the matrix $$$A = \left[ {\matrix{ 1 & 2 & {34} & {49} \cr 0 & 2 & {43} & {94} \cr 0 & 0 & { - 2} & {104} \cr 0 & 0 & 0 & { - 1} \cr } } \right]$$$
37
The function $$f\left( {x,y} \right) = 2{x^2} + 2xy - {y^3}$$ has
38
"If X then Y unless Z" is represented by which of the following formulas in propositional logic? (" $$\neg $$ " is negation, " $$ \wedge $$ " is conjunction, and " $$ \to $$ " is implication)
39
Which of the following scheduling algorithms is non-preemptive?
40
Which of the following is not a form of memory?
41
The optimal page replacement algorithm will select the page that.
42
Dynamic linking can cause security concerns because
43
A computer system uses $$32$$-bit virtual address, and $$32$$-bit physical address. The physical memory is byte addressable, and the page size is $$4$$ kbytes. It is decided to use two level page tables to translate from virtual address to physical address. Equal number of bits should be used for indexing first level and second level page table, and the size of each page table entry is $$4$$ bytes.

(a) Give a diagram showing how a virtual address would be translated to a physical address.

(b) What is the number of page table entries that can be contained in each page?

(c) How many bits are available for storing protection and other information in each page table entry?

44
In the index allocation scheme of blocks to a file, the maximum possible size of the file depends on
45
Which of the following scheduling algorithms is non-preemptive?
46
Draw the process state transition diagram of an $$OS$$ in which
(i) each process is in one of the five states: created, ready, running, blocked (i.e. sleep or wait), or terminated, and
(ii) only non-preemptive scheduling is used by the $$OS.$$ Label the transitions appropriately.
47
Which combination of the following features will suffice to characterize an $$OS$$ as a multi-programmed $$OS?$$
$$(a).$$ More than one program may be loaded into main memory at the same time for execution.
$$(b).$$ If a program waits for certain events such as $$I/O$$, another program is immediately scheduled for execution.
$$(c).$$ If the execution of a program terminates, another program is immediately scheduled for execution.
48
Consider the following declaration of a two-dimensional array in C:

char a[100][100];

Assuming that the main memory is byte-addressable and that the array is stored starting from memory address 0, the address of a[40][50] is
49
The results returned by function under value-result and reference parameter passing conventions
50
In the C language
51
Which of the following is true?
52
The $$C$$ language is:
53
The smallest finite automaton which accepts the language
$$L = \left. {\left\{ x \right.} \right|$$ length of $$x$$ is divisible by $$\left. 3 \right\}$$ has
54
The Finite state machine described by the following state diagram with $$A$$ as starting state, where an arc label is $$x/y$$ and $$x$$ stands for $$1-bit$$ input and $$y$$ stands for $$2$$-bit output GATE CSE 2002 Theory of Computation - Finite Automata and Regular Language Question 67 English
55
The language accepted by a pushdown Automation in which the stack is limited to $$10$$ items is best described as
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12