GATE 2006 CSE & IT

If all the edge weights of an undirected graph are positive, then any subject of edges that connects all the vertices and has minimum total weight is a

Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are Did and cid respectively and the records are stored in ascendi...

Consider a Boolean function $$f(w, x, y, z).$$ Suppose that exactly one of its inputs is allowed to change at a time. If the function happens to be true for two input vectors $${i_...

Which one of the first order predicate calculus statements given below correctly expresses the following English statement? Tigers and lion attack if they are hungry of threatened.

Which of the following sequences of array elements forms a heap?

$$F$$ is an $$n$$ $$x$$ $$n$$ real matrix. $$b$$ is an $$n$$ $$x$$ $$1$$ real vector. Suppose there are two $$n$$ $$x$$ $$1$$ vectors, $$u$$ and $$v$$ such that $$u \ne v$$, and $$...

A relation $$R$$ is defined on ordered pairs of integers as follows: $$\left( {x,y} \right)R\left( {u,v} \right)\,if\,x < u$$ and $$y > v$$. Then $$R$$ is

In a certain town, the probability that it will rain in the afternoon is known to be 0.6. Moreover, meteorological data indicates that if the temperature at noon is less than or eq...

Consider the relation account (customer, balance) where customer is a primary key and there are no null values. We would like to rank customers according to decreasing balance. The...

Consider the set S = {a, b, c, d}. Consider the following 4 partitions $$\,{\pi _1},\,{\pi _2},\,{\pi _3},\,{\pi _4}$$ on $$S:\,{\pi _1} = \left\{ {\overline {a\,b\,c\,d} } \right\...

An implementation of a queue Q, using two stacks S1 and S2, is given below : void insert(Q, X){ push(S1, X); } void delete(Q){ if(stack - empty(S2)) then { if(stack - empty(S1)) th...

The following function computes the value of m C n correctly for all legal values m and n (m≥1,n≥0 and m>n) int func(int m, int n) { if (E) return 1; else return(func(m -1, n) + fu...

Consider the following snapshot of a system running n processes. Process i is holding x i instances of a resource R, for $$1 \le i \le n$$. Currently, all instances of R are occupi...

Station A needs to send a message consisting of 9 packets to Station B using a sliding window (window size 3) and go-back-n error control strategy. All packets are ready and immedi...

The set $$\left\{ {1,\,\,2,\,\,3,\,\,5,\,\,7,\,\,8,\,\,9} \right\}$$ under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is fal...

In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is

When a coin is tossed, the probability of getting a Head is p, 0 < p < 1. Let N be the random variable denoting the number of tosses till the first Head appears, including the toss...

Consider a weighted complete graph $$G$$ on the vertex set $$\left\{ {{v_1},\,\,\,{v_2},....,\,\,\,{v_n}} \right\}$$ such that the weight of the edge $$\left( {{v_i},\,\,\,\,{v_j}}...

What are the eigen values of the matrix $$P$$ given below? $$$P = \left( {\matrix{ a & 1 & 0 \cr 1 & a & 1 \cr 0 & 1 & a \cr } } \right)$$$

Let $$X,. Y, Z$$ be sets of sizes $$x, y$$ and $$z$$ respectively. Let $$W = X x Y$$ and $$E$$ be the set of all subjects of $$W$$. The number of functions from $$Z$$ to $$E$$ is

Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examin...

Consider two cache organization: The first one is $$32$$ $$KB$$ $$2$$-way set associate with $$32$$-byte block size. The second one is of the same size but direct mapped. The size...

Consider the relations r 1 (P, Q, R) and r 2 (R, S, T) with primary keys P and R respectively. The relation r 1 contains 2000 tuples and r 2 contains 2500 tuples. The maximum size...

Let T be a depth first search tree in an undirected graph G. Vertices u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. which one of the following...

Consider two cache organization: The first one is $$32$$ $$KB$$ $$2$$-way set associate with $$32$$-byte block size. The second one is of the same size but direct mapped. The size...

The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices of $$G$$ are adjacent if and only if the corresponding sets...

A CPU has five stages pipeline and runs at $$1$$ $$GHz$$ frequency. Instruction fetch happens in the first stage of the pipeline. A conditional branch instruction computes the targ...

Station A uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip delay between A and B is 80 milliseconds and the bottleneck bandwid...

What is the cardinality of the set of integers $$X$$ defined below? $$X = $$ {$$n\left| {1 \le n \le 123,\,\,\,\,\,n} \right.$$ is not divisible by either $$2, 3$$ or $$5$$ }

Consider the following C code segment. for (i = 0; i < n; i++) { for (j=0; j < n; j++) { if (i%2) { x += (4*j + 5*i); y += (7 + 4*j); } } } Which one of the following is false ?

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any...

Consider the polynomial $$P\left( x \right) = {a_0} + {a_1}x + {a_2}{x^2} + {a_3}{x^3},$$ where $${a_i} \ne 0,\forall i$$. The minimum number of multiplications needed to evaluate...

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If the root node is at level 0, the level of element X...

Let E, F and G be finite sets. Let $$X = \,\left( {E\, \cap \,F\,} \right)\, - \,\left( {F\, \cap \,G\,} \right)$$ and $$Y = \,\left( {E\, - \left( {E\, \cap \,G} \right)} \right)\...

Two computers C1 and C2 are configured as follows. C1 has IP address 203.197.2.53 and netmask 255.255.128.0. C2 has IP address 203.197.75.201 and netmask 255.255.192.0. which one o...

Consider the relation "enrolled (student, course)" in which (student, course) is the primary key, and the relation "paid (student, amount)" where student is the primary key. Assume...

A Computer system supports $$32$$-bit virtual addresses as well as $$32$$-bit physical addresses. Since the virtual address space is of the same size as the physical address space,...

The atomic fetch-and-set x, y instruction unconditionally sets the memory location x to 1 and fetches the old value of x n y without allowing any intervening access to the memory l...

For each elements in a set of size $$2n$$, an unbiased coin in tossed. The $$2n$$ coin tosses are independent. An element is chhoosen if the corresponding coin toss were head.The p...

A $$CPU$$ has a cache with block size $$64$$ bytes. The main memory has $$k$$ banks, each bank being $$c$$ bytes wide. Consecutive $$c$$-byte chunks are mapped on consecutive banks...

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and the...

Which of the following relational query languages have the same expressive power? I) Relational algebra II) Tuple relational calculus restricted to safe expressions III) Domain rel...

In the correct grammar of the previous question, what is the length of the derivation (number of steps starring from S) to generate the string $${a^l}{b^m}$$ with $$l \ne m$$?

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of t...

The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the firs...

Which one of the following in place sorting algorithms needs the minimum number of swaps?

Consider the following recurrence: $$T\left( n \right){\rm{ }} = {\rm{ 2T(}}\left\lceil {\sqrt n } \right\rceil {\rm{) + }}\,{\rm{1 T(1) = 1}}$$ Which one of the following is true?

Given two arrays of numbers a 1 ,......,a n and b 1 ,......, b n where each number is 0 or 1, the fastest algorithm to find the largest span (i, j) such that a i +a i+1 ......a j =...

Consider a weighted complete graph G on the vertex set {v1, v2, ..vn} such that the weight of the edge (vi, vj) is $$2|i-j|$$. The weight of a minimum spanning tree of G is:

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the firs...

In a binary max heap containing n numbers, the smallest element can be found in time

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

Let SHAM 3 be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM 3 be the problem of determining if a Hamiltonian cycle exists in suc...

For the set $$N$$ of natural numbers and a binary operation $$f:N \times N \to N$$, an element $$z \in N$$ is called an identity for $$f$$ if $$f\left( {a,z} \right) = a = f\left(...

Consider three processes, all arriving at time zero, with total execution time of $$10,20,$$ and $$30$$ units, respectively. Each process spends the first $$20$$% of execution time...

The following functional dependencies are given : $$\eqalign{ & AB \to CD,\,AF \to D,\,\,DE \to F, \cr & C \to G.\,\,\,\,\,\,\,\,\,\,F \to E.\,\,\,\,\,\,\,\,\,G \to A. \cr} $$ Whic...

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. The index of the parent of element X[i],i≠0 is?

Consider this C code to swap two integers and these five statements: void swap(int *px, int *py) { *px = *px - *py; *py = *px + *py; *px = *py - *px; } S1: will generate a compilat...

Given two three bit number $${a_2}{a_1}{a_0}$$ and $${b_2}{b_1}{b_0}$$ and $$c,$$ the carry in the function that represents the carry generate function when these two numbers are a...

Consider the undirected graph $$G$$ defined as follows. The vertices of $$G$$ are bit strings of length $$n$$. We have an edge between vertex $$u$$ and vertex $$v$$ if and only if...

Which one of the following grammars generates the following language? $$L = \left( {{a^i}{b^j}|i \ne j} \right)$$

Let S = {1, 2, 3,....., m} , m > 3. Let $${X_1},\,....,\,{X_n}$$ be subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f (i) is the number of...

An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node does not satisfy the heap proper...

Consider the following propositional statements: $${\rm P}1:\,\,\left( {\left( {A \wedge B} \right) \to C} \right) \equiv \left( {\left( {A \to C} \right) \wedge \left( {B \to C} \...

The $${2^n}$$ vertices of a graph $$G$$ correspond to all subsets of a set of size $$n$$, for $$n \ge 6$$. Two vertices of $$G$$ are adjacent if and only if the corresponding sets...

Consider the following first order logic formula in which $$R$$ is a binary relation symbol. $$\forall x\forall y\left( {R\left( {x,\,y} \right) \Rightarrow R\left( {y,x} \right)}...

For which one of the following reasons does Internet Protocol (IP) use the time-to-live (TTL) field in the IP datagram header?

Let $$P, Q$$, and $$R$$ be sets. Let $$\Delta $$ denote the symmetric difference operator defined as $$P\Delta Q = \left( {P \cup Q} \right) - \left( {P \cap Q} \right)$$. Using ve...

You are given a free running clock with a duty cycle of $$50$$% and a digital waveform $$f$$ which changes only at the negative edge of the clock. Which one of the following circui...

Consider the following grammar. $$\eqalign{ & S \to S*E \cr & S \to E \cr & E \to F + E \cr & E \to F \cr & F \to id \cr} $$ Consider the following LR(0) items corresponding to the...

Given a set of elements N = {1, 2, ....., n} and two arbitrary subsets $$A\, \subseteq \,N\,$$ and $$B\, \subseteq \,N\,$$, how many of the n! permutations $$\pi $$ from N to N sat...

Consider three $$CPU$$-intensive process, which require $$10,20$$ and $$30$$ time units and arrive at times $$0,2$$ and $$6$$ respectively. How many context switches are needed if...

Let T be a depth-first search tree in an undirected graph G. Vertices u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following...

Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are Did and cid respectively and the records are stored in ascendi...

A $$CPU$$ has $$24$$-bit instructions. A program starts at address $$300$$ (in decimal). Which one of the following is a legal program counter (all values in decimal)?

Consider the following grammar: $$\eqalign{ & S \to FR \cr & R \to *S\,|\,\varepsilon \cr & F \to id \cr} $$ In the predictive parser table, M, of the grammar the entries $$M\left[...

Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finis...

Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and the...

Consider three processes (process id $$0,1,2,$$ respectively) with compute time bursts $$2, 4,$$ and $$8$$ time units. All processes arrive at time zero. Consider the longest remai...

Consider the following translation scheme. $$\eqalign{ & S \to ER \cr & R \to *E\left\{ {pr{\mathop{\rm int}} ('*');} \right\}R\,|\,\varepsilon \cr & E \to F + E\left\{ {pr{\mathop...

Let $${L_1} = \left\{ {{0^{n + m}}{1^n}{0^m}\left| {n,m \ge 0} \right.} \right\},$$ $$\,\,\,{L_2} = \left\{ {{0^{n + m}}{1^{n + m}}{0^m}\left| {n,m \ge 0} \right.} \right\},$$ and...

If $$s$$ is a string over $${\left( {0 + 1} \right)^ * }$$ then let $${n_0}\left( s \right)$$ denote the number of $$0'$$ s in $$s$$ and $${n_1}\left( s \right)$$ the number of $$1...

For $$s \in {\left( {0 + 1} \right)^ * },$$ let $$d(s)$$ denote the decimal value of $$s(e. g.d(101)=5)$$ Let $$L = \left\{ {s \in {{\left( {0 + 1} \right)}^ * }\left| {\,d\left( s...

Consider the regular language $$L = {\left( {111 + 11111} \right)^ * }.$$ The minimum number of states in any $$DFA$$ accepting this language is

Consider the following statements about the context-free grammar $$G = \left\{ {S \to SS,\,S \to ab,\,S \to ba,\,S \to \varepsilon } \right\}$$ $$1.$$ $$G$$ is ambiguous $$2.$$ $$G...

Let $${L_1}$$ be a regular language, $${L_2}$$ be a deterministic context-free language and $${L_3}$$ a recursively enumerable, but not recursive, language. Which one of the follow...

Consider the following C-program fragment in which i, j and n are integer variables. for (i = n, j = 0; i > 0; i /= 2, j += i); let val (j) denote the value stored in the variable...