GATE 2004 CSE & IT

Consider a System with a two-level paging scheme in which a regular memory access takes $$150$$ nanoseconds, and servicing a page fault takes $$8$$ milliseconds. An average instruc...

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

Consider a program $$P$$ that consists of two source modules $${M_1}$$ and $${M_2}$$ contained in two different files. If $${M_1}$$ contains a reference to a function defined in $$...

Two matrices M 1 and M 2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The tim...

A point is randomly selected with uniform probability in the X-Y plane within the rectangle with corners at (0, 0), (1, 0), (1, 2) and (0, 2). If p is the length of the position ve...

Consider the following C program main ( ) { int x, y, m, n; scanf("%d %d", &x, &y); /* Assume x > 0 and y > 0 */ m=x; n=y; while(m!=n) { if(m>n) m=m-n; else n=n-m; } printf("%d", n...

Let $$a(x,y)$$, $$b(x,y)$$ and $$c(x,y)$$ be three statements with variables $$x$$ and $$y$$ chosen from some universe. Consider the following statement: $$$\left( {\exists x} \rig...

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

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{ no. of lea...

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

Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, uses the least recently used $$(LRU)$$ scheme. The number o...

Which of the following addressing modes are suitable for program relocation at run time? $$1.$$ Absolute addressing $$2.$$ Based addressing $$3.$$ Relative addressing $$4.$$ Indire...

A $$4$$-stage pipeline has the stage delays as $$150, 120,160$$ and $$140$$ nano seconds respectively. Registers that are used between the stages have a delay of $$5$$ nanoseconds...

Identify the correct translation into logical notation of the following assertion. $$Some\,boys\,in\,the\,class\,are\,taller\,than\,all\,the\,girls$$ Note: taller$$\left( {x,\,y} \...

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

Consider the grammar rule $$E \to {E_1} - {E_2}$$ for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requi...

How many $$8$$-bit characters can be transmitted per second over $$9600$$ baud serial communication link using a parity synchronous mode of transmission with one start bit & Eight...

A single array A[1..MAXSIZE] is used to implement two stacks, The two stacks grow from opposite ends of the array. Variables top1 and top2 (top1 < top2) point to the location of th...

The number of different $$n$$ $$x$$ $$n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is (Note: power ($$2,$$ $$x$$) is same as $${2^x}$$)

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 necessary and sufficient to make S a complete lattice under the...

Consider the following C program segment: char p[20]; char *s = "string"; int length = strlen(s); for(i=0; i < length; i++) p[i] = s[length-i]; printf("%s",p); The output of the pr...

Let R 1 ( A, B, C) and R 2 ( D, E) be two relation schema, where the primary keys are shown underlined, and let C be a foreign key in R 1 referring to R 2 . Suppose there is no vio...

A program attempts to generate as many permutation as possible of the string “abcd” by pushing the character a,b,c,d in the same order onto a stack, but it may pop off the top char...

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

Consider an operating system capable of loading and executing a single sequential user process at a time. The disk head scheduling algorithm used is First Come First Served $$(FCFS...

The goal of structured programming is to

An examination paper has 150 multiple-choice questions of one mark each, with each question having four choices. Each incorrect answer fetches-0.25 mark. Suppose 1000 students choo...

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

A TCP message consisting of 2100 bytes is passed to IP for delivery across two networks. The first network can carry a maximum payload of 1200 bytes per frame and the second networ...

What is the result of evaluating the following two expressions using three $$-$$ digit floating point arithmetic with rounding? $$\eqalign{ & \left( {113. + - 111.} \right) + 7.51...

Assume that the operators +, -, ×, are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, ×, +, -. The postfix expression correspon...

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 transmit a frame, collide, and A wins the first backoff race. A...

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i) 9679, 1989, 4199 hash to t...

A relational database contains two table student and department in which student table has columns roll_no, name and dept_id and department table has columns dept_id and detp_name...

A Hard disk with a transfer rate of $$10Mbytes/second$$ is constantly transferring data to memory using $$DMA.$$ The processor runs at $$600MHz$$ and takes $$300$$ and $$900$$ cloc...

$${73_x}$$ (in base $$-$$ $$x$$ number system) is equal to $${54_y}$$ (in base $$-y$$ number system), the possible values of $$x$$ and $$y$$ are

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

Consider the following C program segment struct CellNode{ struct CellNode *leftChild; int element; struct CellNode *rightChild; }; int Dosomething (struct CellNode *ptr) { int valu...

In an M$$ \times $$N matrix such that all non-zero entries are covered in $$a$$ rows and $$b$$ columns. Then the maximum number of non-zero entries, such that no two are on the sam...

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

Consider the following relation schema pertaining to a students database: Students ( rollno , name, address) Enroll( rollno,courseno , coursename) Where the primary keys are shown...

Consider two tables in a relational database with columns and rows as follows: Table: Student Roll_no Name Dept_id 1 ABC 1 2 DEF 1 3 GHI 2 4 JKL 3 Table: Department Dept_id Dept_na...

What is the number of vertices in an undirected connected graph with $$27$$ edges, $$6$$ vertices of degree $$2$$, $$\,\,$$ $$3$$ vertices of degree 4 and remaining of degree 3?

What values of x, y and z satisfy the following system of linear equations? $$$\left[ {\matrix{ 1 & 2 & 3 \cr 1 & 3 & 4 \cr 2 & 3 & 3 \cr } } \right]\,\,\left[ {\matrix{ x \cr y \c...

Consider the following C function: void swap (int a, int b) { int temp; temp = a; a = b; b = temp; } In order to exchange the values of two variables x and y.

The relation scheme student Performance (Name, CourseNo, RollNo, Grade) has the following functional dependencies: Name, courseNo $$\,\, \to \,\,$$ grade RollNo, courseNo $$\,\, \t...

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

The problems 3-SAT and 2-SAT are

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

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

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

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 Heap is

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). Consider the following program fragment written in a C lik...

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

What does the following algorithm approximate? (Assume m > 1, $$ \in > 0$$) x = m; y = 1; while(x - y > ε){ x = (x + y) / 2; y = m/x; } print(x);

Consider a multiplexer with $$X$$ and $$Y$$ as data inputs and $$Z$$ as control input. If $$z=0$$ select input $$x,$$ and $$z=1$$ selects input $$Y$$. what are the connections requ...

A sender is employing public key Cryptography to send a secret message to a receiver. Which one of the following statement is true?

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

$$A$$ $$4$$-bit carry look ahead adder, which adds two $$4$$-bit numbers, is designed using $$AND,$$ $$OR,$$ $$NOT,$$ $$NAND,$$ $$NOR$$ gates only. Assuming that all the inputs are...

Let $${G_1} = \left( {V,\,{E_1}} \right)$$ and $${G_2} = \left( {V,\,{E_2}} \right)$$ be connected graphs on the same vertex set $$V$$ with more than two vertices. If $${G_1} \cap...

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

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

A circuit outputs a digit in the form of $$4$$ bits. $$0$$ is represented by $$0000$$, $$1$$ by $$0001..., $$ $$9$$ by $$1001.$$ A combinational circuit is to be designed which tak...

In a depth-first traversal of a graph G with n vertices,k edges are marked as tree edges. The number of connected components in G is

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); } The value returned by f(1) is

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

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely? i) preorder and postorder ii) in...

Suppose that the maximum transmit window size for a TCP connection is 12000 bytes. Each packet consists of 2000 bytes. At some point of time, the connection is slow start phase wit...

Choose the best matching between the programming style in Group 1 and their characteristics in Group 2 Group 1 P. Functional Q. Logic R. Object-oriented S. Imperative Group 2 1. Co...

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 complexity of the best known algorithm to delete the node x fr...

A relation Empdt $$1$$ is defined with attributes empcode (unique), name, street, city, state and pincode. For any pincode, there is only one city and state. Also, for any given st...

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

Which of the following addressing modes are suitable for program relocation at run time? $$1.$$ Absolute addressing $$2.$$ Based addressing $$3.$$ Relative addressing $$4.$$ Indire...

The order of an internal node in a B + tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes,...

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

Consider the binary relation: $$S = \left\{ {\left( {x,y} \right)|y = x + 1\,\,and\,\,x,y \in \left\{ {0,1,2,...} \right\}} \right\}$$ The reflexive transitive closure of $$S$$ is

Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are nonterminals, and r, s, t are terminals. $$\eqalign{ & 1.\,P \to QR \cr & 2.\,P \t...

Consider the following statements with respect to user-level threads and kernel-supported threads. i) Context switch is faster with kernel- supported threads ii) For user-level thr...

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}$$ be another relation from $$B$$ to $$C$$ $$ = \left\{ {1,2,3,...

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

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

In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 student have taken Computer Organization coures;...

Two n bit binary stings, S1 and, are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where th...

Choose the best matching between Group 1 and Group 2 : Group –1 P. Data link layer Q. Network layer R. Transport layer Group – 2 1. Ensures reliable transport of data over a physic...

The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by.

Consider the grammar with the following translation rules and E as the start symbol. $$\eqalign{ & E \to {E_1}\# T\,\,\left\{ {E.value = {E_1}.value*T.value} \right\} \cr & \,\,\,\...

Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of $$k$$ colours, such that the colour-pairs used to...

In a population of N families, 50% of the families have three children, 30% of the families have two children and the remaining families have one child. What is the probability tha...

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, where p denotes the maximum number of tree pointers in a B-...

If matrix $$X = \left[ {\matrix{ a & 1 \cr { - {a^2} + a - 1} & {1 - a} \cr } } \right]$$ and $${X^2} - X + 1 = 0$$ ($${\rm I}$$ is the identity matrix and $$O$$ is the zero matrix...

The employee information in a company is stored in the relation Employee (name, sex, salary, deptName) Consider the following SQL query Select deptName From Employee Where sex = ‘M...

The recurrence equation $$\,\,\,\,\,\,\,T\left( 1 \right) = 1$$ $$\,\,\,\,\,\,T\left( n \right) = 2T\left( {n - 1} \right) + n,\,n \ge 2$$ evaluates to

Let $$p, q, r$$ and $$s$$ be four primitive statements. Consider the following arguments: $$P:\left[ {\left( {\neg p \vee q} \right) \wedge \left( {r \to s} \right) \wedge \left( {...

In how many ways can we distribute 5 distinct balls, $${B_1},{B_2},......,{B_5}$$ in 5 distinct cells, $${C_1},{C_2},.....,{C_5}$$ such that Ball $${B_i}$$ is not in cell $${C_i}$$...

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

Consider the following grammar $$G:$$ $$\eqalign{ & S \to bS\,\left| {\,aA\,\left| {\,b} \right.} \right. \cr & A \to bA\,\left| {\,aB} \right. \cr & B \to bB\,\left| {\,aS\,\left|...

Which of the following grammar rules violate the requirements of an operator grammar ? $$P,$$ $$Q, R$$ are non-terminals and $$r, s, t$$ are terminals. $$$\eqalign{ & 1)\,\,\,P \to...

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