GATE CSE 2004 PYQ

Suppose we run Dijkstra's single source shortest-path algorithm on the following edge-weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of verti

Let f(n), g(n) and h(n) be functions defined for positive integers such that Which one of the following statements is FALSE?

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

Let A[1,..., n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose Asymptotic Notation is (m). Consider the following program fragment written in a C like language: coun

Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of th

The recurrence equation T(1) = 1 T(n) = 2T(n - 1) + n, n 2 evaluates to

Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in whic

The Asymptotic Notation of the following C function is (assume n 0) int recursive (int n) { if (n == 1) return (1); else return (recursive (n - 1) + recursive (n - 1)); }

Consider a program P that consists of two source modules M1 and M2 contained in two different files. If M1 contains a reference to a function defined in M2 the reference will be resolved at

Consider the grammar with the following translation rules and E as the start symbol. Compute E.value for the root of the parse tree for the expression:2 # 3 & 5 # 6 & 4.

Consider the grammar rule for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register.

A subnet has been assigned a subnet mask of 255.255.255.192. What is the maximum number of hosts that can belong to this subnet?

In TCP, a unique sequence number is assigned to each

In a sliding window ARQ scheme, the transmitter's window size is N and the receiver's window size is M. The minimum number of distinct sequence numbers required to ensure correct operation of the ARQ

Consider the following statements: I. telnet, ftp and http are application layer protocols. II. EJB (Enterprise Java Beans) components can be deployed in a J2EE (Java2 Enterprise Edition) application

A 20 Kbps satellite link has a propagation delay of 400 ms. The transmitter employs the "go back n ARQ" scheme with n set to 10. Assuming that each frame is 100 byte long, what is the maximum data rat

Which one of the following statements is FALSE?

A sender is employing public key cryptography to send a secret message to a receiver. Which one of the following statements is TRUE?

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

How many 8-bit characters can be transmitted per second over a 9600 baud serial communication link using asynchronous mode of transmission with one start bit, eight data bits, two stop bits, and one p

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

Consider three IP networks A, B and C. Host HA in network A sends messages each containing 180 bytes of application data to a host HC in network C. The TCP layer prefixes a 20 byte header to the messa

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 network can carry a maximu

Consider three IP networks A, B and C. Host HA in network A sends messages each containing 180 bytes of application data to a host HC in network C. The TCP layer prefixes a 20 byte header to the messa

Consider a simplified time slotted MAC protocol, where each host always has data to send and transmits with probability p = 0.2 in every slot. There is no backoff and one frame can be transmitted in o

In a data link protocol, the frame delimiter flag is given by 0111. Assuming that bit stuffing is employed, the transmitter sends the data sequence 01110110 as

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. At the end of this su

Choose the best matching between Group 1 and Group 2

A serial transmission T1 uses 8 information bits, 2 start bits, 1 stop bit and 1 parity bit for each character. A synchronous transmission T2 uses 3 eight-bit sync characters followed by 30 eight-bit

In the TCP/IP protocol suite, which one of the following is NOT part of the IP header?

Consider a parity check code with three data bits and four parity check bits. Three of the Code Words are 0101011,1001101 and 1110001. Which of the following are also code words? I. 0010111 II. 011011

Consider a 10 Mbps token ring LAN with a ring latency of 400 . A host that needs to transmit seizes the token. Then it sends a frame of 1000 bytes, removes the frame after it has circulated all around

A host is connected to a Department network which is part of a University network. The University network, in turn, is part of the Internet. The largest network in which the Ethernet address of the ho

The routing table of a router is shown below: On which interface will the router forward packets addressed to destinations 128.75.43.16 and 192.12.17.10 respectively?

Which one of the following statements is FALSE?

In an enhancement of a design of a CPU, the speed of a floating point unit has been increased by 20% and the speed of a fixed point unit has been increased by 10%. What is the overall speedup achieved

The storage area of a disk has the innermost diameter of 10 cm and outermost diameter of 20 cm. The maximum storage density of the disk is 1400 bits/cm. The disk rotates at a speed of 4200 RPM. The ma

The microinstructions stored in the control memory of a processor have a width of 26 bits. Each microinstruction is divided into three fields: a micro-operation field of 13 bits, a next address field

Consider a fully associative cache with 8 cache blocks (numbered 0-7) and the following sequence of memory block requests: 4,3,25,8,19,6,25,8,16,35,45,22,8,3,16,25,7 If LRU replacement policy is used,

What is the bit rate of a video terminal unit with 80 characters/line, 8 bits/character and horizontal sweep time of 100 (including 20 of retrace time)?

Which of the following Addressing Modess are suitable for program relocation at run time? (i) Absolute addressing (ii) Based addressing (iii) Relative addressing (iv) Indirect addressing

A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 nanoseconds respectively. Registers that are used between the stages have a delay of 5 nanoseconds each. Assuming constant clocking rat

A CPU has only three instructions I1, I2 and I3, which use the following signals in time steps T1-T5: I1 : T1 : Ain, Bout, Cin T2 : PCout, Bin T3 : Zout, Ain T4 : Bin, Cout T5 : End I2 : T1 : Cin, Bou

If we use internal data forwarding to speed up the performance of a CPU (R1, R2 and R3 are registers and M[100] is a memory reference), then the sequence of operations R1 M[100] M[100] R2 M[100] R3 ca

Consider a system with 2 level cache. Access times of Level 1 cache, Level 2 cache and main memory are 1 ns, 10 ns, and 500 ns respectively. The hit rates of Level 1 and Level 2 caches are 0.8 and 0.9

Consider the following program segment for a hypothetical CPU having three user registers R1, R2 and R3. Consider that the memory is byte addressable with size 32 bits, and the program has been loaded

What is the minimum size of ROM required to store the complete truth table of an 8-bit 8-bit multiplier?

A hard disk with a transfer rate of 10 Mbytes/second is constantly transferring data to memory using DMA. The processor runs at 600 MHz, and takes 300 and 900 clock cycles to initiate and complete DMA

Consider the following program segment for a hypothetical CPU having three user registers R1, R2 and R3. Let the clock cycles required fro various operations be as follows: Register to/from memory tra

Consider a pipeline processor with 4 stages S1 to S4. We want to execute the following loop: for (i = 1; i < = 1000; i++) {I1, I2, I3, I4} where the time taken (in ns) by instructions I1 to I4 for sta

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

A table T1 in a relational database has the following rows and columns: The following sequence of SQL statements was successfully executed on table T1. Update T1 set marks = marks + 5 Select avg(marks

A relation Empdtl 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 street, city and state, the

A relational database contains two tables student and department in which student table has columns roll_no, name and dept_id and department table has columns dept_id and dept_name. The following inse

The relation scheme Student Performance (name, courseNo, rollNo, grade) has the following functional dependencies: name, courseNo, grade rollNo, courseNo grade name rollNo rollNo name The highest norm

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

Consider the following entity relationship diagram (ERD), where two entities E1 and E2 have a relation R of cardinality 1:m. The attributes of E1 are A11, A12 and A13 where A11 is the key attribute. T

The employee information in a company is stored in the relation Employee ( , sex, salary, deptName) Consider the following SQL query select deptName from Employee where sex = 'M' group by deptName hav

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

Consider two tables in a relational database with columns and rows as follows: Roll_no is the primary key of the Student table, Dept_id is the primary key of the Department table and Student.Dept_id i

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-tree index node. Ass

Consider the following relation schema pertaining to a students database: Students ( , name, address) Enroll ( , , coursename) Where the primary keys are shown underlined. The number of tuples in the

Let R1( ,B,(C)) and R2( ,E) be two relation schema, where the primary keys are shown underlined, and let C be a foreign key in R1 referring to R2 . Suppose there is no violation of the above referenti

Consider the relation Student ( , sex, marks), where the primary key is shown underlined, pertaining to students in a class that has at least one boy and one girl. What does the following relational a

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, and the block size is

Consider the partial implementation of a 2-bit counter using T flip-flops following the sequence 0-2-3- 1-0, as shown below. To complete the circuit, the input X should be

Consider a multiplexer with X and Y as data inputs and Z as control input. Z = 0 selects input X, and Z = 1 selects input Y. What are the connections required to realize the 2-variable Boolean functio

A Boolean function x'y' + xy + x'y is equivalent

Which are the essential prime implicants of the following Boolean function? f(a, b, c) = a'c + ac' + b'c

A 4-bit carry look ahead Combinational Circuit, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and

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 takes these 4 bits as input and outputs 1 if the di

The function is equivalent to

If (in base-x number system) is equal to (in base y-number system), the possible values of x and y are

What is the minimum number of NAND gates required to implement a 2-input EXCLUSIVE-OR function without using any other logic gate?

What is the result of evaluating the following two expressions using three-digit floating point arithmetic with rounding? (113. + - 111.) + 7.51 113. + (- 111. + 7.51)

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

The number is equivalent to

Using a 4-bit 2's complement arithmetic, which of the following additions will result in an overflow? I. 1100 + 1100 II. 0011 + 0111 III. 1111 + 0111

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

Let G1=(V, E1) and G2=(V, E2) be connected graphs on the same vertex set V with more than two vertices. If G1 G2 = (V, E1 E2) is not a connected graph, then the graph G1 G2 = (V, E1 E2)

If matrix and ( is the identity matrix and is the zero matrix), then the inverse of is

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 that a randomly picked

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 vector of the point, the e

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

Consider the following iterative root finding methods and convergence properties: The correct matching of the methods and properties is

In how many ways can we distribute 5 distinct balls, in 5 distinct cells, such that Ball is not in cell and each cell contains exactly one ball?

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?

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

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

Let be harmonic numbers. Then, for can be expressed as

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

Let p,q,r and s be four primitive statements. Consider the following arguments: Which of the above arguments are valid?

Let A,B,C,D be n x n matrices, each with non-zero determinant. If ABCD=I, then is

Let A be an matrix of the following form. What is the value of the determinant of A?

Let be a relation from to be another relation from B to C = {1, 2, 3, 4} as defined below: i. An element x in A is related to an element y in B (under ) if x + y is divisible by 3. ii. An element x in

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

How many graphs on n labeled vertices exist which have at least edges ?

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: Which one of the following is its equivalent?

Let and be two exponentially distributed and independent random variables with mean , respectively. If , then the mean of is given by

In an M x 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 same row or column, is

What values of x, y and z satisfy the following system of linear equations?

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 he colour pairs used to colour any two letters ar

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

If f(l) = 2, f(2) = 4 and f(4) = 16, what is the value of f(3) using Lagrange's interpolation formula?

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

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

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

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 partial order define

The following propositional statement is

A disk has 200 tracks (numbered 0 through 199). At a given time, it was servicing the request of reading data from track 120, and at the previous request, service was for track 90. The pending request

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). If FCFS is replaced

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 instruction takes 100 nanoseconds o

A process executes the following segment of code : for(i = 1; i <= n; i++) fork (); The number of new processes created is

Consider two processes P1 and P2 accessing the shared variables X and Y protected by two binary semaphores Sx and Sy respectively, both initialized to 1. P and V denote the usual semaphore operators,

Which of the following commands or sequences of commands will rename a file x to file y in a Unix system ? I. mv y, x II. mv x, y III. cp y, x (rm x) IV. cp x, y (rm x)

The semaphore variables full, empty and mutex are initialized to 0, n and 1, respectively. Process P1 repeatedly adds one item at a time to a buffer of size n, and process P2 repeatedly removes one it

A unix-style I-node has 10 direct pointers and one single, one double and one triple indirect pointers. Disk block size is 1 Kbyte, disk block address is 32 bits, and 48-bit integers are used. What is

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 threads, a system call

In a virtual memory system, size of the virtual address is 32-bit, size of the physical address is 30-bit, page size is 4 Kbyte and size of each page table entry is 32-bit. The main memory is byte add

In a certain operating system, deadlock prevention is attemped using the following scheme. Each process is assigned a unique timestamp, and is restarted with the same timestamp if killed. Let be the p

In a particular Unix OS, each data block is of size 1024 bytes, each node has 10 direct data block addresses and three additional addresses: one for single indirect block, one for double indirect bloc

Which one of the following is NOT shared by the threads of the same process ?

Consider the following set of processes, with the arrival times and the CPU-burst times given in milliseconds. What is the average turnaround time for these processes with the preemptive shortest rema

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; } print f ("% d", n

Which one of the following binary trees has its inorder and preorder traversals as BCAD and ABCD, respectively?

Consider the following C program which is supposed to compute the transpose of a given matrix M. Note that, there is an X in the program which indicates some missing statements. Choose the correct opt

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 leaf-nodes in left-subtr

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 maximum distance of a l

Choose the correct option to fill the ?1 and ?2 so that the program prints an input string in reverse order. Assume that the input string is terminated by a new line character. #include void wrt_it (v

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) inorder and postorde

A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed

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

The elements 32, 15, 20, 30, 12, 25, 16, are inserted one by one in the given order into a MaxHeap. The resultant MaxHeap is

What does the following algorithm approximate? (Assume ). x = m; y = 1; while (x - y > e) { x = (x + y)/2; y = m/x; } print(x);

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let . int n, rev; rev = 0; while (n > 0) { rev = rev*10 + n%10; n = n/10; } The loop invari

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

Suppose each set is represented as a linked list with elements in arbitray order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

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 from the list ?

Consider the following C function: int f(int n) { static int i = 1; if (n > = 5) return n; n = n+i; i++; return f(n); } The value returned by f(1) is

What is the output of the following program? #include int funcf (int x); int funcg (int y); main () { int x = 5, y = 10, count; for (count = 1; count <= 2; ++count) { y += funcf(x) + funcg(x); printf

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

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 the same value ii) 14

Consider the following C program: #include typedef struct { char *a; char *b; } t; void f1 (t s); void f2 (t *p); main() { static t s = {"A", "B"}; printf ("%s %s ", s.a, s.b); f1(s); printf ("%s %s "

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

A program attempts to generate as many permutations as possible of the string, 'abcd' by pushing the characters a,b,c,d in the same order onto a stack, but it may pop off the top character at any time

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 column-major order in contiguous memory locations. The time complexity of an alg

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.

Let x be an integer which can take a value of 0 or 1. The statement if (x == 0) x = 1; else x = 0; is equivalent to which one of the following ?

An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node , and doing this adjustment up to the r

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 top 2 (top1 top 2) point to the location of the topmost element i

Consider the following C program segment struct CellNode { struct CelINode *leftchild; int element; struct CelINode *rightChild; } int Dosomething(struct CelINode *ptr) { int value = 0; if (ptr != NUL

L1 is a recursively enumerable language over . An algorithm A effectively enumerates its words as w1, w2, w3, ... define another language L2 over U{#} as {wi # wj : wi, wj L1, i j}. Here # is a new sy

Consider the following grammar G: Let Na(w) and Nb(w) denote the number of a's and b's in a string w respectively. The language generated by G is

The language { } 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.

Which one of the following statements is FALSE?

The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively.

Which one of the following regular expressions is NOT equivalent to the regular expression

Let be a pushdown automaton, where Which one of the following strings is not a member of L(M)?

Let be a finite state automaton, where A grammar to generate the language accepted by M can be specified as Which one of the following set of rules will make L(G) = L(M) ?