GATE CSE 2004

## GATE CSE

The tightest lower bound on the number of comparisons, in the worst case, for
comparison-based sorting is of the order o

View Question
Let A[1,...,n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is O(m)

View Question
The time complexity of the following C function is (assume n > 0)
int recursive(int n){
if(n == 1){
return (1);

View Question
What does the following algorithm approximate? (Assume m > 1, $$ \in > 0$$)
x = m;
y = 1;
while(x - y > ε){
x

View Question
The recurrence equation
T(1) = 1
T(n) = 2T(n - 1)+n, $$n \ge 2$$
Evaluates to

View Question
The elements 32, 15, 20, 30, 12, 25, 16, are inserted one by one in the given
order into a max Heap. The resultant max H

View Question
Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge-weighted directed graph with verte

View Question
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order o

View Question
The problems 3-SAT and 2-SAT are

View Question
Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are nonterminals, and r, s

View Question
Consider the grammar with the following translation rules and E as the start symbol.
$$\eqalign{
& E \to {E_1}\# T

View Question
Consider the grammar rule $$E \to {E_1} - {E_2}$$ for arithmetic expressions. The code generated is targeted to a CPU ha

View Question
Choose the best matching between Group 1 and Group 2 :
Group –1
P. Data link layer
Q. Network layer
R. Transport lay

View Question
A and B are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both A and B attempt to tra

View Question
Which of the following is NOT true with respect to a transparent bridge and a router?

View Question
The routing table of a router is shown below:
On which interface will the router forward packets addressed to destinati

View Question
Consider three IP networks A, B and C. Host HA in networks A sends messages each containing 180 bytes of application dat

View Question
Consider three IP networks A, B and C. Host HA in networks A sends messages each containing 180 bytes of application dat

View Question
A TCP message consisting of 2100 bytes is passed to IP for delivery across two networks. The first network can carry a m

View Question
Suppose that the maximum transmit window size for a TCP connection is 12000 bytes. Each packet consists of 2000 bytes. A

View Question
A sender is employing public key Cryptography to send a secret message to a receiver. Which one of the following stateme

View Question
What is the result of evaluating the following two expressions using three $$-$$ digit floating point arithmetic with ro

View Question
$$A$$ $$4$$-bit carry look ahead adder, which adds two $$4$$-bit numbers, is designed using $$AND,$$ $$OR,$$ $$NOT,$$ $$

View Question
Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced,

View Question
A $$4$$-stage pipeline has the stage delays as $$150, 120,160$$ and $$140$$ nano seconds respectively. Registers that ar

View Question
Which of the following addressing modes are suitable for program relocation at run time?
$$1.$$ Absolute addressing
$$2

View Question
Consider the following program segment for a hypothetical $$CPU$$ having three user registers $$R1,R2, $$ and $$R3.$$

View Question
Consider the following program segment for a hypothetical $$CPU$$ having three user registers $$R1,R2, $$ and $$R3.$$

View Question
Which one of the following is true for a $$CPU$$ having a single interrupt request line and single interrupt grant line?

View Question
How many $$8$$-bit characters can be transmitted per second over $$9600$$ baud serial communication link using a parity

View Question
A Hard disk with a transfer rate of $$10Mbytes/second$$ is constantly transferring data to memory using $$DMA.$$ The pro

View Question
The microinstructions stored in the control memory of a processor have a width of $$26$$ bits. Each microinstruction is

View Question
A single array A[1..MAXSIZE] is used to implement two stacks, The two stacks grow from opposite ends of the array. Varia

View Question
Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or

View Question
The best data structure to check whether an arithmetic expression has balanced parentheses is a

View Question
Assume that the operators +, -, ×, are left associative and ^ is right associative. The order of precedence (from highes

View Question
A program attempts to generate as many permutation as possible of the string “abcd” by pushing the character a,b,c,d in

View Question
A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node sh

View Question
Let P be a singly linked list, Let Q be the pointer to an intermediate node x in the list.What is the worst-case time co

View Question
Level order traversal of a rooted tree can be done by starting from the root and performing

View Question
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is

View Question
Consider the following C program segment
struct CellNode{
struct CellNode *leftChild;
int element;
struc

View Question
Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pair

View Question
In a depth-first traversal of a graph G with n vertices,k edges are marked as tree edges. The number of connected compon

View Question
Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the

View Question
A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for e

View Question
Consider the following entity relationship diagram $$(ERD),$$ where two entities $$E1$$ and $$E2$$ have a relation $$R$$

View Question
A relation Empdt $$1$$ is defined with attributes empcode (unique), name, street, city, state and pincode. For any pinco

View Question
The relation scheme student Performance (Name, CourseNo, RollNo, Grade) has the following functional dependencies:
Name,

View Question
Consider the following relation schema pertaining to a students database:
Students (rollno, name, address)
Enroll(rollno

View Question
The employee information in a company is stored in the relation
Employee (name, sex, salary, deptName)
Consider the foll

View Question
A relational database contains two table student and department in which student table has columns roll_no, name and dep

View Question
Consider two tables in a relational database with columns and rows as follows:
Table: Student
.tg {border-collap

View Question
Let R1 (A, B, C) and R2 (D, E) be two relation schema, where the primary keys are shown underlined, and let C be a forei

View Question
Consider the relation Student (name, sex, marks), where the primary key is shown underlined, pertaining to students in a

View Question
Which level of locking provides the highest degree of concurrency in a relational database?

View Question
Consider the following schedule S of transactions T1 and T2:
Which of the following is TRUE about the schedule S?

View Question
Consider a table T in a relational database with a key field K. A B-tree of order p is used as an access structure on K,

View Question
The order of an internal node in a B+ tree index is the maximum number of children it can have. Suppose that a child poi

View Question
$${73_x}$$ (in base $$-$$ $$x$$ number system) is equal to $${54_y}$$ (in base $$-y$$ number system), the possible value

View Question
Let $$A=1111$$ $$1010$$ and $$B=0000$$ $$1010$$ be two $$8$$-bit $$2's$$ complement numbers. Their product in $$2's$$ co

View Question
The Boolean function $$x'y' +xy +x'y$$ is equivalent to

View Question
Which are the essential prime implicants of the following Boolean function? $$F\left( {a,b,c} \right) = {a^1}c + a{c^1}

View Question
A circuit outputs a digit in the form of $$4$$ bits. $$0$$ is represented by $$0000$$, $$1$$ by $$0001..., $$ $$9$$ by $

View Question
Consider a multiplexer with $$X$$ and $$Y$$ as data inputs and $$Z$$ as control input. If $$z=0$$ select input $$x,$$ an

View Question
$$SR.$$ latch made by cross coupling two $$NAND$$ gates if $$S=R=0,$$ Then it will result in

View Question
Consider the partial implementation of a $$2$$-bit counter using $$T$$ flip-flops following the sequence $$0$$-$$2$$-$$3

View Question
Identify the correct translation into logical notation of the following assertion.
$$Some\,boys\,in\,the\,class\,are\,t

View Question
Let $$a(x,y)$$, $$b(x,y)$$ and $$c(x,y)$$ be three statements with variables $$x$$ and $$y$$ chosen from some universe.

View Question
The following propositional statement is $$$\left( {P \to \left( {Q \vee R} \right)} \right) \to \left( {\left( {P \wedg

View Question
Let $$p, q, r$$ and $$s$$ be four primitive statements. Consider the following arguments:
$$P:\left[ {\left( {\neg p \ve

View Question
In a population of N families, 50% of the families have three children, 30% of the families have two children and the re

View Question
If a fair coin is tossed four times, what is the probability that two heads and two tails will result?

View Question
A point is randomly selected with uniform probability in the X-Y plane within the rectangle with corners at
(0, 0), (1

View Question
An examination paper has 150 multiple-choice questions of one mark each, with each question having four choices. Each in

View Question
Two n bit binary stings, S1 and, are chosen randomly with uniform probability. The probability that the Hamming distance

View Question
The following is the incomplete operation table of a 4-element group.
The last row of the table is

View Question
The inclusion of which of the following sets into
S = { {1, 2}, 1, 2, 3}, {1, 3, 5}, {1, 2, 4},
{1, 2, 3, 4, 5} }
Is

View Question
The number of different $$n$$ $$x$$ $$n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is (No

View Question
Consider the binary relation: $$S = \left\{ {\left( {x,y} \right)|y = x + 1\,\,and\,\,x,y \in \left\{ {0,1,2,...} \right

View Question
Let $${R_1}$$ be a relation from $$A = \left\{ {1,3,5,7} \right\}$$ to $$B = \left\{ {2,4,6,8} \right\}$$ and $${R_2}$$

View Question
In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures

View Question
Let A, B, C, D be $$n\,\, \times \,\,n$$ matrices, each with non-zero determination. If ABCD = I, then $${B^{ - 1}}$$ is

View Question
What values of x, y and z satisfy the following system of linear equations?
$$$\left[ {\matrix{
1 & 2 & 3 \c

View Question
What is the maximum number of edges in an acyclic undirected graph with $$n$$ vertices?

View Question
Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints wi

View Question
In how many ways can we distribute 5 distinct balls, $${B_1},{B_2},......,{B_5}$$ in 5 distinct cells, $${C_1},{C_2},...

View Question
The recurrence equation
$$\,\,\,\,\,\,\,T\left( 1 \right) = 1$$
$$\,\,\,\,\,\,T\left( n \right) = 2T\left( {n - 1} \rig

View Question
How many solutions does the following system of linear equations have?
- x + 5y = - 1x - y = 2x + 3y = 3

View Question
Let $$A$$ be and n$$ \times $$n matrix of the folowing form.
What is the value of the determinant of $$A$$?

View Question
The minimum number of colours required to colour the following graph, such that
no two adjacent vertices are assigned th

View Question
If matrix $$X = \left[ {\matrix{
a & 1 \cr
{ - {a^2} + a - 1} & {1 - a} \cr
} } \right]$$
and $${X^

View Question
In an M$$ \times $$N matrix such that all non-zero entries are covered in $$a$$ rows and $$b$$ columns. Then the maximum

View Question
How many graphs on $$n$$ labeled vertices exist which have at least $$\left( {{n^2} - 3n} \right)/2\,\,\,$$ edges?

View Question
Let $${G_1} = \left( {V,\,{E_1}} \right)$$ and $${G_2} = \left( {V,\,{E_2}} \right)$$ be connected graphs on the same ve

View Question
What is the number of vertices in an undirected connected graph with $$27$$ edges, $$6$$ vertices of degree $$2$$, $$\,\

View Question
The number of different $$n \times n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is

View Question
Consider the following statements with respect to user-level threads and kernel-supported threads.
i) Context switch is

View Question
Consider the following set of processes, with the arrival times and the $$CPU$$-burst times given in milliseconds.
Wh

View Question
Consider a program $$P$$ that consists of two source modules $${M_1}$$ and $${M_2}$$ contained in two different files. I

View Question
Which of the following addressing modes are suitable for program relocation at run time?
$$1.$$ Absolute addressing
$$2.

View Question
The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determi

View Question
Consider a System with a two-level paging scheme in which a regular memory access takes $$150$$ nanoseconds, and servici

View Question
Consider an operating system capable of loading and executing a single sequential user process at a time. The disk head

View Question
The goal of structured programming is to

View Question
Choose the best matching between the programming style in Group 1 and their characteristics in Group 2
Group 1
P. Functi

View Question
Consider the following C function:
int f(int n)
{
static int i = 1;
if(n>=5) return n;
n = n+1;
i++;
return f(n);
}
T

View Question
Consider the following C program
main ( )
{
int x, y, m, n;
scanf("%d %d", &x, &y);
/* Assume x > 0 an

View Question
Consider the following C function:
void swap (int a, int b)
{
int temp;
temp = a;
a = b;
b = temp;
}
In orde

View Question
Consider the following C program segment:
char p[20];
char *s = "string";
int length = strlen(s);
for(i=0; i < length

View Question
The following finite state machine accepts all those binary strings in which the number of $$1's$$ and $$0's$$ are respe

View Question
Which of the following grammar rules violate the requirements of an operator grammar ? $$P,$$ $$Q, R$$ are non-terminals

View Question
Consider the following grammar $$G:$$
$$\eqalign{
& S \to bS\,\left| {\,aA\,\left| {\,b} \right.} \right. \cr

View Question
The language $$\left\{ {{a^m}{b^n}{c^{m + n}}\left| {m,n \ge } \right.} \right\}$$ is

View Question
Let $$M = \left( {K,\,\sum {,\,F,\,\Delta ,\,s,\,F} } \right)$$ be a pushdown automation. Where $$K = \left\{ {s,\,f} \r

View Question