GATE CSE 2004
View Questions

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
EXAM MAP
Joint Entrance Examination
JEE MainJEE AdvancedWB JEEBITSATMHT CET
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN