GATE CSE 2009
View Questions

## GATE CSE

Consider a binary max-heap implemented using an array. What is the content of the array {25, 14, 16, 13, 10, 8, 12} afte
View Question
Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?
View Question
What is the number of swaps required to sort n elements using selection sort, in the worst case?
View Question
Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a n
View Question
The running time of an algorithm is represented by the following recurrence relation: $$T(n) = \begin{cases} n &amp View Question In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. W View Question Consider the following graph: Which one of the following is NOT the sequence of edges added to the minimum spanning tree View Question A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are View Question A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are View Question Let$${\pi _A}$$be a problem that belongs to the class NP. Then which one of the following is TRUE? View Question Match all items in Group 1 with correct options from those given in Group 2. Group 1 P. Regular expression Q. Pushdown a View Question Let G(x) be the generator polynomial used for CRC checking. What is the condition that should be satisfied by G(x) to de View Question Frames of 1000 bits are sent over a 106 bps duplex link between two hosts. The propagation time is 25 ms. Frames are to View Question Frames of 1000 bits are sent over a 106 bps duplex link between two hosts. The propagation time is 25 ms. Frames are to View Question While opening a TCP connection, the initial sequence number is to be derived using a time-of-day (ToD) clock that keeps View Question In the RSA public key cryptosystem, the private and public keys are (e, n) and (d, n) respectively, where n = p$$ \times
View Question
How many $$32k$$ x $$1$$ $$RAM$$ chips are needed to provide a memory capacity of $$256$$ $$K$$-bytes?
View Question
Consider a $$4$$-way set associative cache (initially empty) with total $$16$$ cache blocks. The main memory consists of
View Question
Consider a $$4$$ stage pipeline processor. The number of cycles needed by the four instructions $${\rm I}1,$$ $${\rm I}2 View Question A$$CPU$$generally handles an interrupt by executing an interrupt service routine View Question 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. View Question The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressi View Question Consider the following relational schema: Suppliers(sid : integer, sname : string, city : string, street : string) Parts View Question Consider the following relational schema: Suppliers(sid : integer, sname : string, city : string, street : string) Parts View Question Consider two transactions T1 and T2 and four schedules S1, S2, S3, S4 of T1 and T2 as given below: T1: R1[ x ] W1[ x ] View Question Let R and S be relational schemes such that R = { a, b, c } and S = { c }. Now consider the following queries on the dat View Question The following key values are inserted into a B+-tree in which order of the internal nodes is 3, and that of the leaf nod View Question$${\left( {1217} \right)_8}$$is equivalent to View Question What is the minimum number of gates required to implement the Boolean function$$(AB+C)$$if we have to use only$$2$$-i View Question Given the following state table of an$$FSM$$with two states$$A$$and$$B,$$one input and one output: If the initial View Question An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of View Question Which one of the following is the most appropriate logical formula to represent the statement: "$$Gold\,and\,silver\,orn
View Question
Consider the following well-formed formulae: $${\rm I}.$$ $$\,\,\neg \forall x\left( {P\left( x \right)} \right)$$ $${ View Question Which one of the following in NOT necessarily a property of Group? View Question consider the binary relation$$R = \left\{ {\left( {x,y} \right),\,\left( {x,z} \right),\,\left( {z,x} \right),\,\left(
View Question
The binary operation ◻ is defined as follows: Which one of the following is equivalence to $$P \vee Q$$?
View Question
For the compositive table of a cyclic group shown below Which one of the following choices is correct?
View Question
What is the chromatic number of an $$n$$-vertex simple connected graph which does not contain any odd length cycle? Assu
View Question
Which one of the following is TRUE for any simple connected undirected graph with more than $$2$$ vertices?
View Question
$$\int\limits_0^{\pi /4} {\left( {1 - \tan x} \right)/\left( {1 + \tan x} \right)dx}$$ $$\,\,\,\,\,\,$$ evaluates to
View Question
A CPU generally handles an interrupt by executing an interrupt service routine
View Question
In the following process state transition diagram for a uniprocessor system, assume that there are always some processes
View Question
The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instr
View Question
In which one of the following page replacement policies, Belady’s anomaly may occur?
View Question
The essential content(s) in each entry of a page table is / are:
View Question
How many $$32K\,\, \times \,\,1RAM$$ chips are needed to provide a memory capacity of $$256$$ $$K$$-bytes?
View Question
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
View Question
A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physi
View Question
Consider a disk system with $$100$$ cylinders. The requests to access the cylinders occur in following sequence: $$4, 34 View Question Consider a system with 4 types of resources R1 (3 units), R2 (2 units), R3 (3 units), R4 (2 units). A non-preemptive res View Question The coupling between different modules of a software is categorized as follows$${\rm I}.\,\,\,\,\,\,\,\,\,\,\,$$Conte View Question Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which o View Question Which of the following statements are TRUE?$${\rm I}.\,\,\,\,\,\,$$The content diagram should depict the system as a s View Question Which one of the following languages over the alphabet$$\left\{ {0,\left. 1 \right)} \right.$$is described by the regu View Question$$L = {L_1} \cap {L_2}$$where$${L_1}$$and$${L_2}$$are languages defined as follows.$${L_1} = \left\{ {{a^m}{b^m}
View Question
The above $$DFA$$ accepts the set of all strings over $$\left\{ {0,\,\,1} \right\}$$ that
View Question
Which one of the following is FALSE?
View Question
$$S \to aSa\,\left| {\,bSb\,\left| {\,a\,\left| {\,b} \right.} \right.} \right.$$ The language generated by the above g
View Question
EXAM MAP
Medical
NEET