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 &gt; 0) int recursive(int n){ if(n == 1){ return (1);
View Question
What does the following algorithm approximate? (Assume m &gt; 1, $$\in &gt; 0$$) x = m; y = 1; while(x - y &gt; ε){ 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{ &amp; E \to {E_1}\# T View Question Consider the grammar ruleE \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$$A4$$-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: &nbsp;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=11111010$$and$$B=00001010$$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 &amp; 2 &amp; 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 &amp; 1 \cr { - {a^2} + a - 1} &amp; {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&gt;=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", &amp;x, &amp;y); /* Assume x &gt; 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; char *s = "string"; int length = strlen(s); for(i=0; i &lt; 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{ &amp; 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