Never mind what others do; do better than yourself, beat your own record from day to day, and you are a success.
1. What does the following C-statement declare?
int (*f)(int*) ;
(A) A function that takes an integer pointer as argument and returns an integer.
(B) A function that takes an integer as argument and returns an integer pointer.
(C) A pointer to a function that takes an integer pointer as argument and returns an integer.
(D) function that takes an integer pointer as argument and returns a function pointer
View/Hide Ans
Correct Answer is C
2. An Abstract Data Type(ADT) is:
(A) Same as an abstract class
(B) A data type that cannot be instantiated
(C) A data type type for which only the operations defined on it can be used, but none else
(D) All of the above
View/Hide Ans
Correct Answer is C
3. A common property of logic programming languages and functional languages is:
(A) both are procedural languages
(B) both are based on λ-calculus
(C) both are declarative
(D) both use Horn-clauses
View/Hide Ans
Correct Answer is C
4. 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 coupled with sub-type rule
(iv) Polymorphism in the presence of inheritance
(A) (i) and (ii) only
(B) (i) and (iv) only
(C) (i), (ii) and (iv) only
(D) (i), (iii) and (iv) only
View/Hide Ans
Correct Answer is B
5. A program P reads in 500 integers in the range [0..100] representing the scores of 500 students. It then prints the frequency of each score above 50.
What would be the best way for P to store the frequencies?
(A) An array of 50 numbers
(B) An array of 100 numbers
(C) An array of 500 numbers
(D) A dynamically allocated array of 550 numbers
View/Hide Ans
Correct Answer is A
6. An undirected graph C has n nodes. Its adjacency matrix is given by an n×n square matrix whose
(i) diagonal elements are 0's and
(ii) non-diagonal elements are 1's.
Which one of the following is TRUE?
(A) Graph G has no minimum spanning tree(MST)
(B) Graph G has a unique MST of cost n-1
(C) Graph G has multiple distinct MSTs, each of cost n-1
(D) Graph G has multiple spanning trees of different costs
View/Hide Ans
Correct Answer is C
7. The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be
(A) O (n)
(B) O (n log n)
(C) O(n3/2)
(D) O(n3)
View/Hide Ans
Correct Answer is D
8. 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?
(A) X=Y
(B) X⊂Y
(C) Y⊂X
(D) none of these
View/Hide Ans
Correct Answer is A
9. The following is the Hasse diagram of the poset [{a, b, c, d, e}, ≤]
10. 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
(A) 6
(B) 8
(C) 9
(D) 13
View/Hide Ans
Correct Answer is B
11. Let G be a 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
(A) 12
(B) 8
(C) Less than 8
(D) More than 12
View/Hide Ans
Correct Answer is A
12. Let f(x) be the continuous probability density function of a random variable X.
The probability that a < X ≤ b, is
View/Hide Ans
Correct Answer is C
13. The set {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15.
The inverses of 4 and 7 are respectively
(A) 3 and 13
(B) 2 and 11
(C) 4 and 13
(D) 8 and 14
View/Hide Ans
Correct Answer is C
14. The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is
(A) ambiguous
(B) left-recursive
(C) right-recursive
(D) an operator-grammar
View/Hide Ans
Correct Answer is B
15. Consider the following circuit
16. The range of integers that can be represented by an n bit 2's complement number system is
(A) -2n-1 to (2n-1 - 1)
(B) -(2n-1 - 1) to (2n-1 - 1)
(C) -2n-1 to 2n-1
(D) -(2n-1 + 1) to (2n-1 + 1)
View/Hide Ans
Correct Answer is A
17. The hexadecimal representation of (657)8 is
(A) 1AF
(B) D78
(C) D71
(D) 32F
View/Hide Ans
Correct Answer is A
18. The switching expression corresponding to f(A, B, C, D) = ∑ (1, 4, 5, 9, 11, 12) is
(A) BC'D' + A'C'D + AB'D
(B) ABC' + ACD + B'C'D
(C) ACD' + A'BC' + AC'D'
(D) A'BD + ACD' + BCD'
View/Hide Ans
Correct Answer is A
19. Which one of the following is true for a CPU having a single interrupt request line and a single interrupt grant line?
(A) Neither vectored interrupt nor multiple interrupting devices are possible.
(B) Vectored interrupts are not possible but multiple interrupting devices are possible.
(C) Vectored interrupts and multiple interrupting devices are both possible.
(D) Vectored interrupt is possible but multiple interrupting devices are not possible.
View/Hide Ans
Correct Answer is B
20. Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instructions privileged. In a CPU with memory mapped I/O, there is no explicit I/O instruction.
Which one of the following is true for a CPU with memory mapped I/O?
(A) I/O protection is ensured by operating system routine (s)
(B) I/O protection is ensured by a hardware trap
(C) I/O protection is ensured during system configuration
(D) I/O protection is not possible
View/Hide Ans
Correct Answer is A
21. What is the swap space in the disk used for?
(A) Saving temporary html pages
(B) Saving process data
(C) Storing the super-block
(D) Storing device drivers
View/Hide Ans
Correct Answer is B
22. Increasing the RAM of a computer typically improves performance because:
(A) Virtual memory increases
(B) Larger RAMs are faster
(C) Fewer page faults occur
(D) fewer segmentation faults occur
View/Hide Ans
Correct Answer is C
23. Packets of the same session may be routed through different paths in
(A) TCP, but not UDP
(B) TCP and UDP
(C) UDP, but not TCP
(D) Neither TCP, nor UDP
View/Hide Ans
Correct Answer is B
24. The address resolution protocol(ARP) is used for
(A) Finding the IP address from the DNS
(B) Finding the IP address of the default gateway
(C) Finding the IP address that corresponds to a MAC address
(D) Finding the MAC address that corresponds to an IP address
View/Hide Ans
Correct Answer is D
25. The maximum window size for data transmission using the selective reject protocol with n-bit frame sequence numbers is:
(A) 2n
(B) 2n-1
(C) 2n-1
(D) 2n-2
View/Hide Ans
Correct Answer is B
26. 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 have to be routed through multiple bridges.
Why is the spanning tree algorithm used for bridge-routing?
(A) For shortest path routing between LANs
(B) For avoiding loops in the routing paths
(C) For fault tolerance
(D) For minimizing collisions
View/Hide Ans
Correct Answer is B
27. An organization has a class B network and wishes to form subnets for 64 departments.
The subnet mask would be
(A) 255.255.0.0
(B) 255.255.64.0
(C) 255.255.128.0
(D) 255.255.252.0
View/Hide Ans
Correct Answer is D
28. Which one of the following is a key factor for preferring B+ trees to binary search trees for indexing database relations?
(A) Database relations have a large number of records
(B) Database relations are sorted on the primary key
(C) B+ trees require less memory than binary search trees
(D) Data transfer from disks is in blocks
View/Hide Ans
Correct Answer is D
29. Which one of the following statements about normal forms is FALSE?
(A) BCNF is stricter than 3NF
(B) Lossless, dependency-preserving decomposition into 3NF is always possible
(C) Lossless, dependency-preserving decomposition into BCNF is always possible
(D) Any relation with two attributes is in BCNF
View/Hide Ans
Correct Answer is C
30. Let r be a relation instance with schema R = (A, B, C, D).
We define r1 = πA,B,C(r) and r2 = πA,D(r).
Let s = r1 * r2 where * denotes natural join.
Given that the decomposition of r into r1 and r2 is lossy,
which one of the following is TRUE?
(A) s⊂r
(B) r∪s=r
(C) r⊂s
(D) r*s=s
View/Hide Ans
Correct Answer is C
31. 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 a = 2048, sum = 0;
foo (a, sum);
printf ("%d\n", sum);
getchar();
}
What does the above program print?
(A) 8, 4, 0, 2, 14
(B) 8, 4, 0, 2, 0
(C) 8, 4, 0, 2, 0
(D) 2, 0, 4, 8, 0
View/Hide Ans
Correct Answer is D
32. 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 without any error or warning. If Line 1 is deleted, the above code will show:
(A) no compile warning or error
(B) some compiler-warnings not leading to unintended results
(C) some compiler-warnings due to type-mismatch eventually leading to unintended results
(D) compiler errors
View/Hide Ans
Correct Answer is D
33. 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 keys can be the result of an inorder traversal of the tree T?
(A) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95
(B) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
(C) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
(D) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
View/Hide Ans
Correct Answer is A
34. 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 inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
(A) 10, 8, 7, 5, 3, 2, 1
(B) 10, 8, 7, 2, 3, 1, 5
(C) 10, 8, 7, 1, 2, 3, 5
(D) 10, 8, 7, 3, 2, 1, 5
View/Hide Ans
Correct Answer is D
35. How many distinct binary search trees can be created out of 4 distinct keys?
(A) 5
(B) 14
(C) 24
(D) 42
View/Hide Ans
Correct Answer is B
36. 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
(A) nk
(B) (n - 1)k + 1
(C) n(k - 1) + 1
(D) n(k - 1)
View/Hide Ans
Correct Answer is C
37. Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE?
(A) T(n) = O(n2)
(B) T(n) = θ(n log n)
(C) T(n) = Ω(n2)
(D) T(n) = O(n log n)
View/Hide Ans
Correct Answer is C
38. 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 complexity:
(A) O(|V|2)
(B) O(|E|+|V|log|V|)
(C) O(|V|log|V|)
(D) O((|E|+|V|)log|V|)
View/Hide Ans
Correct Answer is D
39. Suppose there are ⌈logn⌉ sorted lists of ⌊nlogn ⌋ elements each.
The time complexity of producing a sorted list of all these elements is :
(Hint : Use a heap data structure)
(A) O(n log log n)
(B) θ(n log n)
(C) Ω(n log n)
(D) Ω(n3/2)
View/Hide Ans
Correct Answer is A
40. Let P, Q and R be three atomic prepositional assertions.
Let X denote (P v Q) → R and Y denote (P → R) v (Q → R).
Which one of the following is a tautology?
(A) X=Y
(B) X→Y
(C) Y→X
(D) ¬Y→X
View/Hide Ans
Correct Answer is B
41. What is the first order predicate calculus statement equivalent to the following?
"Every teacher is liked by some student".
(A) ∀(x) [teacher (x) → ∃(y) [student (y) → likes (y, x)]]
(B) ∀ (x) [teacher (x) → ∃(y) [student (y) ∧ likes (y, x)]]
(C) ∃ (y) ∀ (x) [teacher (x) → [student (y) ^ likes (y, x)]]
(D) ∀ (x) [teacher (x) ^ ∃(y) [student (y) → likes (y, x)]]
View/Hide Ans
Correct Answer is B
42. Let R and S be any two equivalence relations on a non-empty set A.
Which one of the following statements is TRUE?
(A) R ∪ S, R ∩ S are both equivalence relations
(B) R ∪ S is an equivalence relation
(C) R ∩ S is an equivalence relation
(D) Neither R ∪ S nor R ∩ S is an equivalence relation
View/Hide Ans
Correct Answer is C
43. Let f: B → C and g: A → B be two functions and let h = f o g. Given that h is an onto function.
Which one of the following is TRUE?
(A) f and g should both be onto functions.
(B) f should be onto but g need not be onto
(C) g should be onto but f need not be onto
(D) both f and g need not be onto
View/Hide Ans
Correct Answer is B
44. 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 ≡ c mod 3" and "b ≡ d mod 5"
(A) 4
(B) 6
(C) 16
(D) 24
View/Hide Ans
Correct Answer is C
45. Consider three decision problems P1, P2 and P3.
It is known that P1 is decidable and P2 is undecidable.
Which one of the following is TRUE?
(A) P3 is decidable if P1 is reducible to P3
(B) P3 is undecidable if P3 is reducible to P2
(C) P3 is undecidable if P2 is reducible to P3
(D) P3 is decidable if P3 is reducible to P2's complement
View/Hide Ans
Correct Answer is C
46. Consider the set H of all 3×3 matrices given below.
47. Which one of the following graphs is NOT planar?
48. 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 equations has
(A) no solution
(B) a unique solution
(C) more than one but a finite number of solutions
(D) an infinite number of solutions
View/Hide Ans
Correct Answer is B
49. What are the eigenvalues of the following 2×2 matrix?
(A) -1 and 1
(B) 1 and 6
(C) 2 and 5
(D) 4 and -1
View/Hide Ans
Correct Answer is B
50. Let
where |x|<1.
What is g(i) ?
(A) i
(B) i+1
(C) 2i
(D) 2i
View/Hide Ans
Correct Answer is B
51. 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 each ball in
the box is equally likely to be chosen.
The probabilities of
selecting boxes P and Q are 1/3 and 2/3, respectively.
Given that a ball selected in the above process is a red ball, the probability that it came from the box P is
(A) 4/19
(B) 5/19
(C) 2/9
(D) 19/30
View/Hide Ans
Correct Answer is A
52. 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 two such randomly generated strings are not identical is
(A) 1/2n
(B) 1 - (1/n)
(C) 1/n!
(D) 1 - (1/2n)
View/Hide Ans
Correct Answer is D
53. Consider the machine M:
54. Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively.
Let Df and Dp denote the classes of languages accepted by deterministic
finite automata and deterministic push-down automata, respectively.
Which one of the following is TRUE?
(A) Df ⊂ Nf and Dp ⊂ Np
(B) Df ⊂ Nf and Dp = Np
(C) Df = Nf and Dp = Np
(D) Df = Nf and Dp ⊂ Np
View/Hide Ans
Correct Answer is D
55. Consider the languages:
L1 = {anbncm | n, m > 0}
L2 = {anbmcm | n, m > 0}
Which one of the following statements is FALSE?
(A) L1 ∩ L2 is a context-free language
(B) L1 ∪ L2 is a context-free language
(C) L1 and L2 are context-free language
(D) L1 ∩ L2 is a context sensitive language
View/Hide Ans
Correct Answer is A
56. Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language.
Which one of the following is TRUE?
(A) L1' is recursive and L2' is recursively enumerable
(B) L1' is recursive and L2' is not recursively enumerable
(C) L1' and L2' are recursively enumerable
(D) L1' is recursively enumerable and L2' is recursive
View/Hide Ans
Correct Answer is B
57. Consider the languages:
L1 = {wwR | w ∈ {0, 1}*}
L2 = {w#wR | w ∈ {0, 1}*}, where # is a special symbol
L3 = {ww | w ∈ (0, 1}*)
Which one of the following is TRUE?
(A) L1 is a deterministic CFL
(B) L2 is a deterministic CFL
(C) L3 is a CFL, but not a deterministic CFL
(D) L3 is a deterministic CFL
View/Hide Ans
Correct Answer is B
58. Consider the following two problems on undirected graphs
∝ : Given G(V, E), does G have an independent set of size |V|-4?
β : Given G(V, E), does G have an independent set of size 5?
Which one of the following is TRUE?
(A) ∝ is in P and β is NP-complete
(B) ∝ is NP-complete and β is in P
(C) Both ∝ and β are NP-complete
(D) Both ∝ and β are in P
View/Hide Ans
Correct Answer is C
59. Consider the grammar
E → E+n | E×n | n
For a sentence n+n×n, the handles in the right-sentential form of the reduction are
(A) n, E+n and E+n×n
(B) n, E+n and E+E×n
(C) n, n+n and n+n×n
(D) n, E+n and E×n
View/Hide Ans
Correct Answer is D
60. Consider the grammar
S → (S)|a
Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be
n1, n2 and n3 respectively.
The following relationship holds good
(A) n1 < n2 < n3
(B) n1 = n3 < n2
(C) n1 = n2 = n3
(D) n1 ≥ n3 ≥ n2
View/Hide Ans
Correct Answer is B
61. Consider line number 3 of the following C- program.
int main( ) { /* Line 1 */
int I, N; /* Line 2 */
for (I = 0, I < N, I++); /* Line 3 */
}
(A) No compilation error
(B) Only a lexical error
(C) Only syntactic errors
(D) Both lexical and syntactic errors
View/Hide Ans
Correct Answer is C
62. Consider the following circuit involving a positive edge triggered DFF.
63. The following diagram represents a finite state machine which takes as input a binary number from the least significant bit.
64. Consider the following circuit.
65. Consider a three word machine instruction
ADD A[R0], @B
The first operand (destination) "A [R0]" uses indexed addressing mode with R0 as the index register. The second operand (source) "@ B" uses indirect addressing mode.
A and B are memory addresses residing at the second and the third words, respectively.
The first word of the instruction specifies the opcode,
the index register designation and the source and destination addressing modes.
During execution of ADD instruction, the two operands are added and stored in the destination
(first operand).
The number of memory cycles needed during the execution cycle of the instruction is
(A) 3
(B) 4
(C) 5
(D) 6
View/Hide Ans
Correct Answer is B
66. Match each of the high level language statements given on the left hand side with the most natural addressing mode from those listed on the right hand side.
Codes:
List I
List II
1 A[I]=B[J];
a Indirect addressing
2 while (*A++);
b Indexed, addressing
3 int temp=*x;
c Autoincrement
(A) (1, c), (2, b), (3, a)
(B) (1, a), (2, c), (3, b)
(C) (1, b), (2, c), (3, a)
(D) (1, a), (2, b), (3, c)
View/Hide Ans
Correct Answer is C
67. 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 number of tag bits are respectively
(A) 10, 17
(B) 10, 22
(C) 15, 17
(D) 5, 17
View/Hide Ans
Correct Answer is A
68. 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: ALU operation for data and address computation,
MA - Data memory access - for write access, the register read at RD stage is used,
WB - Register write back.
Consider the following sequence of instructions:
I1 : Load R0, loc1; R0 ← M[loc1]
I2 : Add R0, R0; R0 ← R0 + R0
I3 : Sub R2, R0; R2 ← R2 - R0
Let each stage take one clock cycle.
What is the number of clock cycles taken to complete the above sequence of instructions starting from the fetch of I1 ?
(A) 8
(B) 10
(C) 12
(D) 15
View/Hide Ans
Correct Answer is A
69. 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 msec. The byte transfer time between the device interface register and CPU or memory is negligible.
What is the minimum performance gain of operating the device under interrupt mode over operating it under program controlled mode?
(A) 15
(B) 25
(C) 35
(D) 45
View/Hide Ans
Correct Answer is B
70. 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 operated in cycle stealing mode whereby whenever one byte word is ready it is sent to memory; similarly, for writing, the disk interface reads a 4 byte word from the memory in each DMA cycle. Memory cycle time is 40 nsec.
The maximum percentage of time that the CPU gets blocked during DMA operation is:
(A) 10
(B) 25
(C) 40
(D) 50
View/Hide Ans
Correct Answer is B
71. Suppose n processes, P1, ..... Pn share m identical resource units,
which can be reserved and released one at a time.
The maximum resource requirement of process Pi is Si,
where Si *gt; 0.
Which one of the following is a sufficient condition for ensuring that deadlock does not occur?
View/Hide Ans
Correct Answer is C
72. 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 by the parent process, and x, y be the values printed by the child process.
Which one of the following is TRUE?
(A) u=x+10 and v=y
(B) u=x+10 and v!=y
(C) u+10=x and v=y
(D) u+10=x and v!=y
View/Hide Ans
Correct Answer is C
73. 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 contains a header of 3 bytes, then the optimum packet size is:
(A) 4
(B) 6
(C) 7
(D) 9
View/Hide Ans
Correct Answer is D
74. Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 ms.
The minimum frame size is
(A) 94
(B) 416
(C) 464
(D) 512
View/Hide Ans
Correct Answer is C
75. Let E1 and E2 be two entities
in an E/R diagram with simple single-valued attributes.
R1 and R2 are two relationships between E1 and E2,
where R1 is one-to-many and R2 is many-to-many.
R1 and R2 do not have any attributes of their own.
What is the minimum number of tables required to represent this situation in the
relational model?
(A) 2
(B) 3
(C) 4
(D) 6
View/Hide Ans
Correct Answer is B
76. The following table has two attributes A and C where A is the primary key and C is the foreign key referencing A with on-delete cascade.
The set of all tuples that must be additionally deleted to preserve referential integrity when the tuple (2,4) is deleted is:
(A) (3,4) and (6,4)
(B) (5,2) and (7,2)
(C) (5,2), (7,2) and (9,5)
(D) (3,4), (4,3) and (6,4)
View/Hide Ans
Correct Answer is C
77. 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 title
from book as B
where (select count(*)
from book as T
where (T.price > B.price) < 5)
(A) Titles of the four most expensive books
(B) Title of the fifth most inexpensive book
(C) Title of the fifth most expensive bookTitles of the five most expensive books
(D) Titles of the five most expensive books
View/Hide Ans
Correct Answer is D
78. Consider a relation scheme R = (A, B, C, D, E, H) on which the following functional dependencies hold:
(A → B, BC → D, E → C, D → A).
What are the candidate keys of R?
(A) AE, BE
(B) AE, BE, DE
(C) AEH, BEH, BCH
(D) AEH, BEH, DEH
View/Hide Ans
Correct Answer is D
79. Consider the following data path of a CPU.
80. Consider the following data path of a CPU.
81. Consider the following C-function:
double foo (int n)
{
int i;
double sum;
if (n = = 0) return 1.0;
else
{
sum = 0.0;
for (i = 0; i < n; i++)
sum += foo (i);
return sum;
}
}
The space complexity of the above function is:
(A) O(1)
(B) O(n)
(C) O(n!)
(D)O(nn)
View/Hide Ans
Correct Answer is B
82. Consider the following C-function:
double foo (int n)
{
int i;
double sum;
if (n = = 0) return 1.0;
else
{
sum = 0.0;
for (i = 0; i < n; i++)
sum += foo (i);
return sum;
}
}
Suppose we modify the above function foo() and store the values of foo(i), 0<=i<n, as
and when they are computed.
With this modification, the time complexity for function foo() is significantly reduced.
The space complexity of the modified function would be:
(A) O(1)
(B) O(n)
(C) O(n!)
(D) O(nn)
View/Hide Ans
Correct Answer is B
83. Let s and r be two vertices in a undirected graph G=(V,E) having distinct
positive edge weights.
Let [X,Y] be a partition of V such that s∈X and t∈ Y.
Consider the edge e having the minimum weight amongst all those edges that
have one vertex in X and one vertex in Y.
The edge e must definitely belong to:
(A) the minimum weighted spanning tree of G
(B) the weighted shortest path from s to t
(C) each path from s to t
(D) the weighted longest path from s to t
View/Hide Ans
Correct Answer is A
84. Let s and r be two vertices in a undirected graph G=(V,E) having distinct
positive edge weights.
Let [X,Y] be a partition of V such that s∈X and t∈ Y.
Consider the edge e having the minimum weight amongst all those edges that
have one vertex in X and one vertex in Y.
Let the weight of an edge e denote the congestion on that edge.
The congestion on a path is defined to be the maximum of the congestions on the edges of
the path.
We wish to find the path from s to t having minimum congestion.
Which one of the following paths is always such a path of minimum congestion?
(A) a path from s to t in the minimum weighted spanning tree
(B) a weighted shortest path from s to t
(C) an Euler walk from s to t
(D) a Hamiltonian path from s to t
View/Hide Ans
Correct Answer is A
85. Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production.
E → number E.val = number. val
| E '+' E E(1).val = E(2).val + E(3).val
| E '×' E E(1).val = E(2).val × E(3).val
The above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1)
parser generator) for parsing and evaluating arithmetic expressions.
Which one of the following is true about the action of yacc for the given grammar?
(A) It detects recursion and eliminates recursion
(B) It detects reduce-reduce conflict, and resolves
(C) It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action
(D) It detects shift-reduce conflict, and resolves the conflict in
favor of a reduce over a shift action
View/Hide Ans
Correct Answer is C
86.Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production.
E → number E.val = number. val
| E '+' E E(1).val = E(2).val + E(3).val
| E '×' E E(1).val = E(2).val × E(3).val
Assume the conflicts in Part (a) of this question are resolved and an LALR(1)
parser is generated for parsing arithmetic expressions as per the given grammar.
Consider an expression 3 × 2 + 1.
What precedence and associativity properties does the generated parser realize?
(A) Equal precedence and left associativity; expression is evaluated to 7
(B) Equal precedence and right associativity; expression is evaluated to 9
(C) Precedence of '×' is higher than that of '+', and both operators are left associative; expression is evaluated to 7
(D) Precedence of '+' is higher than that of '×', and both operators
are left associative; expression is evaluated to 9
View/Hide Ans
Correct Answer is C
87. We are given 9 tasks T1, T2.... T9.
The execution of each task requires one unit of time.
We can execute one task at a time.
Each task Ti has a profit Pi and a deadline di Profit Pi is
earned if the task is completed before the end of the dith unit of time.
88. We are given 9 tasks T1, T2.... T9.
The execution of each task requires one unit of time.
We can execute one task at a time.
Each task Ti has a profit Pi and a deadline di Profit Pi is
earned if the task is completed before the end of the dith unit of time.
89. Consider the following floating point format
90. Consider the following floating point format
© 2022. All Rights Reserved | Copyright | Terms of Use & Privacy Policy