GATE 2009 CSE & IT

While opening a TCP connection, the initial sequence number is to be derived using a time-of-day (ToD) clock that keeps running even when the host is down. The low order 32 bits of...

The following key values are inserted into a B + -tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of interna...

Consider the following relational schema: Suppliers(sid : integer, sname : string, city : string, street : string) Parts(pid : integer, pname : string, color : string) Catalog(sid...

Consider the following relational schema: Suppliers(sid : integer, sname : string, city : string, street : string) Parts(pid : integer, pname : string, color : string) Catalog(sid...

What is the minimum number of gates required to implement the Boolean function $$(AB+C)$$ if we have to use only $$2$$-input NOR gates?

Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE? $${\rm I}.\,\,\,\,\,\,$$ The cyclomatic co...

How many $$32K\,\, \times \,\,1RAM$$ chips are needed to provide a memory capacity of $$256$$ $$K$$-bytes?

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face valueis even. The probability...

In the RSA public key cryptosystem, the private and public keys are (e, n) and (d, n) respectively, where n = p$$ \times $$q and p and q are large primes. Besides, n is public and...

What is the chromatic number of an $$n$$-vertex simple connected graph which does not contain any odd length cycle? Assume $$n \ge 2$$.

Consider a disk system with $$100$$ cylinders. The requests to access the cylinders occur in following sequence: $$4, 34, 10, 7, 19, 73, 2, 15, 6, 20$$ Assuming that the head is cu...

Frames of 1000 bits are sent over a 10 6 bps duplex link between two hosts. The propagation time is 25 ms. Frames are to be transmitted into this link to maximally pack them in tra...

$${\left( {1217} \right)_8}$$ is equivalent to

The essential content(s) in each entry of a page table is / are:

$$\int\limits_0^{\pi /4} {\left( {1 - \tan x} \right)/\left( {1 + \tan x} \right)dx} $$ $$\,\,\,\,\,\,$$ evaluates to

Frames of 1000 bits are sent over a 10 6 bps duplex link between two hosts. The propagation time is 25 ms. Frames are to be transmitted into this link to maximally pack them in tra...

Which one of the following in NOT necessarily a property of Group?

Consider two transactions T 1 and T 2 and four schedules S 1 , S 2 , S 3 , S 4 of T 1 and T 2 as given below: T 1 : R 1 [ x ] W 1 [ x ] W 1 [ y ] T 2 : R 2 [ x ] R 2 [ y ] W 2 [ y...

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. Wh...

Which one of the following is TRUE for any simple connected undirected graph with more than $$2$$ vertices?

Consider the virtual page reference string $$$1,2,3,2,4,1,3,2,4,1$$$ On a demand paged virtual memory system running on a computer system that has main memory size of $$3$$ page fr...

What is the number of swaps required to sort n elements using selection sort, in the worst case?

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respe...

In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respe...

Consider a binary max-heap implemented using an array. What is the content of the array {25, 14, 16, 13, 10, 8, 12} after two delete operations?

Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one exist s. Q: Finds whether any...

The running time of an algorithm is represented by the following recurrence relation: $$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$$ Wh...

Let $${\pi _A}$$ be a problem that belongs to the class NP. Then which one of the following is TRUE?

A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because.

In which one of the following page replacement policies, Belady’s anomaly may occur?

A $$CPU$$ generally handles an interrupt by executing an interrupt service routine

How many $$32k$$ x $$1$$ $$RAM$$ chips are needed to provide a memory capacity of $$256$$ $$K$$-bytes?

Consider a $$4$$-way set associative cache (initially empty) with total $$16$$ cache blocks. The main memory consists of $$256$$ blocks and the request for memory blocks is in the...

The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows: void enter_CS(X) { while test-and-set(X)...

Which of the following statements are TRUE? $${\rm I}.\,\,\,\,\,\,$$ The content diagram should depict the system as a single bubble. $${\rm II}.\,\,\,\,$$ External entities should...

The coupling between different modules of a software is categorized as follows $${\rm I}.\,\,\,\,\,\,\,\,\,\,\,$$ Content coupling $${\rm II}.\,\,\,\,\,\,\,\,\,$$ Common coupling $...

Match all items in Group 1 with correct options from those given in Group 2. Group 1 P. Regular expression Q. Pushdown automata R. Dataflow analysis S. Register allocation Group 2...

Consider the following well-formed formulae: $${\rm I}.$$ $$\,\,\neg \forall x\left( {P\left( x \right)} \right)$$ $${\rm I}{\rm I}.\,\,\,\,\,\,\neg \exists x\left( {P\left( x \rig...

A CPU generally handles an interrupt by executing an interrupt service routine

Let R and S be relational schemes such that R = { a, b, c } and S = { c }. Now consider the following queries on the database: I. $$\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \t...

consider the binary relation $$R = \left\{ {\left( {x,y} \right),\,\left( {x,z} \right),\,\left( {z,x} \right),\,\left( {z,y} \right)} \right\}$$ on the set $$\left\{ {x,\,y,\,z} \...

Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to detect odd number of bits in error?

Which one of the following is the most appropriate logical formula to represent the statement: "$$Gold\,and\,silver\,ornaments\,are\,precious$$" The following notations are used: $...

$$L = {L_1} \cap {L_2}$$ where $${L_1}$$ and $${L_2}$$ are languages defined as follows. $${L_1} = \left\{ {{a^m}{b^m}\,c\,{a^n}{b^n}\left| {m,n \ge 0} \right.} \right\}$$ $${L_2}...

Which one of the following languages over the alphabet $$\left\{ {0,\left. 1 \right)} \right.$$ is described by the regular expression $${\left( {0 + 1} \right)^ * }0{\left( {0 + 1...

$$S \to aSa\,\left| {\,bSb\,\left| {\,a\,\left| {\,b} \right.} \right.} \right.$$ The language generated by the above grammar over the alphabet $$\left\{ {a,\,b} \right\}$$ is the...

Which one of the following is FALSE?