GATE 2005 CSE & IT
92 questions across 1 session
Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets $${S_1}$$ and $${S_2}$$ in C, either $${S_1}\, \subset \,{S_2}$$ or $${...
The time complexity of computing the transitive closure of a binary relation on a set of elements is known to be:
Consider the following C - function: double foo(int n){ int i; double sum; if(n == 0) return 1.0; sum = 0.0; for (i = 0; i < n; i++){ sum += foo(i); } return sum; } The space compl...
Consider a disk drive with the following specifications: $$16$$ surfaces, $$512$$ tracks/surface, $$512$$ sectors/track, $$1$$KB/Sector, rotation speed $$3000$$ rpm. The disk is op...
Consider the following code fragment: if (fork() == 0) { a = a + 5; printf("%d, %d \n", a, &a); } else { a = a - 5; printf ("%d, %d \n", a, &a); } Let $$u,v$$ be the values printed...
What is the value of $$\int\limits_0^{2\pi } {{{\left( {x - \pi } \right)}^3}\left( {\sin x} \right)dx} $$
A $$5$$ stage pipelined $$CPU$$ has the following sequence of stages $$IF$$-Instruction fetch from instruction memory, $$RD$$-Instruction decode and register read, $$EX$$-Execute:...
Consider the grammar $$S \to \left( S \right)\,|\,a$$ Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n 1 , n 2 and n 3 respectively. The following...
A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then the maximum number of nodes that could be...
In a packet switching network, packets are routed from source to destination along a single path having two intermediate nodes. If the message size is 24 bytes and each packet cont...
An Abstract Data Type (ADT) is
Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production. $$\eqalign{ & E \to number\,\,\,\,\,E.val = nu...
A table ‘student’ with schema (roll, name, hostel, marks), and another table ‘hobby’ with schema (roll, hobbyname) contains records as shown below: Table: student Roll Name Hostel...
The maximum window size for data transmission using the selective reject protocol with n-bit frame sequence numbers is:
A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i. If a stack S contai...
Let $$G$$ be the simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of $$G$$ is 8. Then, the size of the maximum independent set of $$G$$ is:
Consider line number 3 of the following C - program. int main ( ) { /* Line 1 */ int I, N; /* Line 2 */ fro (I = 0, I < N, I++); /* Line 3 */ } Identify the compiler's response abo...
What are the eigen values of the following $$2x2$$ matrix? $$$\left[ {\matrix{ 2 & { - 1} \cr { - 4} & 5 \cr } } \right]$$$
A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is drawn from the bag, its colour recorded and it is put back in the bag. This process is repeated 3 t...
What does the following C statement declare? int (*f)(int *);
Increasing the $$RAM$$ of a computer typically improves performance because
Let $$A$$, $$B$$ and $$C$$ be non-empty sets and let $$X = (A - B) - C$$ and $$Y = (A - C) - (B - C)$$ Which one of the following is TRUE?
The address resolution protocol (ARP) is used for
Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production. $$\eqalign{ & E \to number\,\,\,\,\,E.val = nu...
Let $$G\left( x \right) = 1/\left( {1 - x} \right)2 = \sum\limits_{i = 0}^\infty {g\left( i \right)\,{x^1}} \,\,\,,$$ where $$\left| x \right| < 1$$ What is $$g(i)$$?
An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the tails are independent, the expected number of tosses are
What is the swap space in the disk used for?
Amongst the ACID properties of a transaction, the 'Durability' property requires that the changes made to the database by a successful transaction persist
A program P reads in 500 integers in the range [0, 100] representing the cores of 500 students. It then print the frequency of each score above 50. What would be the best way for P...
Let $$P, Q$$ and $$R$$ be three atomic prepositional assertions. Let $$X$$ denotes $$\left( {P \vee Q} \right) \to R$$ and $$Y$$ denote $$\left( {P \to R} \right) \vee \left( {Q \t...
Consider a three word machine instruction $$ADD$$ $$A$$ $$\left[ {{R_0}} \right],\,@\,B$$ The first operand (destination) ''$$A$$ $$\left[ {{R_0}} \right]''$$ uses indexed addressi...
Normally user programs are prevented from handling $${\rm I}/O$$ directly by $${\rm I}/O$$ instructions in them. For $$CPUs$$ having explicit $${\rm I}/O$$ instructions, such $${\r...
The determination of the matrix given below is $$$\left[ {\matrix{ 0 & 1 & 0 & 2 \cr { - 1} & 1 & 1 & 3 \cr 0 & 0 & 0 & 1 \cr 1 & { - 2} & 0 & 1 \cr } } \right]$$$
An organization has a class B network and wishes to form subnets for 64 departments. The subnet mask would be
Consider the following C program: void foo (int n, int sum) { int k = 0, j = 0; if(n==0) return; k=n%10; j = n /10; sum = sum + k; foo(j, sum); printf("%d",k); } int main () { int...
Consider the following system of equations in three real variables $$x1, x2$$ and $$x3$$ : $$2x1 - x2 + 3x3 = 1$$ $$3x1 + 2x2 + 5x3 = 2$$ $$ - x1 + 4x2 + x3 = 3$$ This system of eq...
Suppose that two parties A and B wish to setup a common secret key (D - H key) between themselves using the Diffie-Hellman key exchange technique. They agree on 7 as the modulus an...
Let $$f(x)$$ be the continuous probability density function of a random variable X. The probability that $$a\, < \,X\, \le \,b$$, is:
The grammar $$A \to AA\,|\,\left( A \right)\,|\,\varepsilon $$ is not suitable for predictive-parsing because the grammar is
The numbers 1, 2, ........, n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inse...
Box P has 2 red balls and 3 blue balls and box Q has 3 red balls and 1 blue ball. A ball is selected as follows: (i) select a box (ii) choose a ball from the selected box such that...
The relation book (title, price) contains the titles and prices of different books. Assuming that no two books have the same price, what does the following SQL query list? Select t...
In an inventory management system implemented at a trading corporation, there are several tables designed to hold all the information. Amongst these, the following two tables hold...
Consider the grammar $$E \to E + n\,|\,E \times n\,|\,n$$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are
Let $$n = {p^2}q,$$ where $$p$$ and $$q$$ are distinct prime numbers. How many numbers $$m$$ satisfy $$1 \le m \le n$$ and $$gcd\left( {m.n} \right) = 1?$$ Note that $$gcd(m,n)$$ i...
Consider the following C program: double foo(double); /* Line 1 */ int main () { double da, db; //input da db = foo(da); } double foo(double a){ return a; } The above code compiled...
Let $$P(x)$$ and $$Q(x)$$ be arbitrary predicates. Which of the following statement is always TRUE?
A table has fields, $$F1, F2, F3, F4, F5,$$ with the following functional dependencies: $$F1 \to F3.\,F2 \to F4.\,\,\,\left( {F1\,.\,F2} \right) \to F5$$ in terms of Normalization,...
Which one of the following are essential features of an object-oriented programming language? i) Abstraction and encapsulation ii) Strictly-typedness iii) Type-safe property couple...
Packets of the same session may be routed through different paths in
What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs $$(a, b)$$ and $$(c, d)$$ in the chosen set such that $...
A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained i...
A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that tw...
Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which one of the following is FALSE?
Consider the following C - function: double foo(int n){ int i; double sum; if(n == 0) return 1.0; sum = 0.0; for (i = 0; i < n; i++){ sum += foo(i); } return sum; } Suppose we modi...
Consider three decision problems P 1 , P 2 and P 3 . It is known that P 1 is decidable and P 2 is undecidable. Which one of the following is TRUE ?
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements '1' and '7' are i...
Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \over {\log n}}} \right\rfloor $$ elements each. The time complexity of producing a sorted list of all...
A common property of logic programming languages and functional languages is:
The set $$\left\{ {1,\,\,2,\,\,4,\,\,7,\,\,8,\,\,11,\,\,13,\,\,14} \right\}$$ is a group under multiplication modulo $$15$$. The inverse of $$4$$ and $$7$$ are respectively:
Let $${E_1}$$ and $${E_2}$$ be two entities in an E-R diagram with simple single-valued attributes, $${E_1}$$ and $${E_2}$$ are two relationships between $${E_1}$$ and $${E_2}$$, W...
Consider a relation scheme $$R = \left( {A,\,B,\,C,\,D,\,E,\,H} \right)$$ on which the following functional dependencies hold: $$\left\{ {A \to B,\,\,BC \to D,\,\,E \to C,\,\,D \to...
Let r be a relation instance with schema R = (A, B, C, D). We define $${r_1} = {\pi _{A,B,C}}\left( r \right)$$ and $${r_1} = {\pi _{A,D}}\left( r \right)$$. Let $$s = {r_1}*{r_2}$...
Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 μs. The minimum frame size is
Consider the disk drive with the following specifications $$16$$ surfaces, $$512$$ tracks/surface, $$512$$ sectors/track, $$1$$ $$KB/sector$$, rotation speed $$3000$$ $$rpm.$$ The...
In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may h...
Let $$G$$ be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:
What is the first order predicate calculus statement equivalent to the following? Every teacher is liked by some student
Which one of the following statements about normal forms is FALSE?
Suppose n processes, P 1 ,......., P n share m identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process P i is S i ,...
A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123,...
In a schema with attributes $$A, B, C, D,$$ and $$E,$$ following set of functional dependencies are given $$\eqalign{ & \,\,\,A \to B \cr & \,\,\,A \to C \cr & CD \to E \cr & \,\,\...
Consider a direct mapped cache of size $$32$$ $$KB$$ with block size $$32$$ bytes. The $$CPU$$ generates $$32$$ bit addresses. The number of bits needed for cache indexing and the...
Consider the set $$H$$ of all $$3$$ $$X$$ $$3$$ matrices of the type $$$\left[ {\matrix{ a & f & e \cr 0 & b & d \cr 0 & 0 & c \cr } } \right]$$$ Where $$a, b, c, d, e$$ and $$f$$...
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are i...
Let $$f$$ be a function from a set $$A$$ to a set $$B$$, $$g$$ a function from $$B$$ to $$C$$, and $$h$$ a function from $$A$$ to $$C$$, such that $$h\left( a \right) = g\left( {f\...
Normally user programs are prevented from handling $${\rm I}/O$$ directly by $${\rm I}/O$$ instructions in the for $$CPU$$ having explicit $${\rm I}/O$$ instructions, such $${\rm I...
In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is
Let R and S be any two equivalence relations on a non-emply set A. Which one of the following statements is TRUE?
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number...
A device with data transfer rate $$10$$ $$KB/sec$$ is connected to a $$CPU.$$ Data is transferred byte-wise. Let the interrupt overhead be $$4$$ $$\mu \sec $$. The byte transfer ti...
The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers...
Let f: $$\,B \to \,C$$ and g: $$\,A \to \,B$$ be two functions and let h = fog. Given that h is an onto function which one of the following is TRUE?
A company maintains records of sales made by its salespersons and pays them commission based on each individual’s total sales made in a year. This data is maintained in a table wit...
How many distinct binary search trees can be created out of 4 distinct keys?
Postorder traversal of a given binary search tree T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of ke...
Consider three decision problems $${P_1},$$ $${P_2}$$ and $${P_3}.$$ It is known that $${P_1}$$ is decidable and $${P_2}$$ is un-decidable. Which of the following is TRUE?
Let $${L_1}$$ be a recursive language, and Let $${L_2}$$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
Consider the language : $${L_1}\, = \left\{ {w\,{w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$ $${L_2}\, = \left\{ {w\, \ne {w^R}\,\left| {w \in \left\{ {0,...
Consider the language : $${L_1} = \left\{ {{a^n}{b^n}{c^m}\left| {n,m > 0} \right.} \right\}$$ and $${L_2} = \left\{ {{a^n}{b^m}{c^m}\left| {n,m > 0} \right.} \right\}$$ Which of t...
Let $${N_f}$$ and $${N_p}$$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $${D_f}$$ and...
Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time compl...