Company: iGATE Global Solutions Limited
COMPUTER SCIENCE & ENGINEERING
Q.1 — Q.21 are one mark Questions.
1. What does the following C-statement declare? mt ( * f) (mt * ) (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) A function that takes an integer pointer as argument and returns a function pointer
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 ofthe above
3. A common property of logic programming languages and functional languages is:
(a) both are procedural languages
(b) both are based on 2k-calculus
(c) both are declarative
(d) both use Horn-clauses
4. Which one of the following are essential features of an object-oriented programming language?
(i) Abstraction and encapsulatoin
(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
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
6. An undirected graph G has n nodes. Its adjacency matrix is given by an n x n square matrix whose
(i) diagonal elements are 0’s and
(ii) non-diagonal elements are l’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-i
(c) Graph G has multiple distinct MSTs, each of cost n-i
(d) Graph G has multiple spanning trees of different costs
7. The time complexity of computing the transitive closure of set of n elements is known to be: (a) 0(n) (b) 0(n log n)
8. Let A, B and C be non-empty sets and let X=(A-B)-CandY=(A-C)-(B-C) Which one of the following is TRUE? (a) X=Y (b) XciY (c) YciX
9. 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
10. 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
11. 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
12. What is the swap space in the disic used for? (a) Saving temporary html pages (b) Saving process data (c) Storing the super-block (d) Storing device drivers
13. 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
14. 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
15. 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
16. The maximum window size for data transmission using the selective reject protocol with n-bit frame sequence numbers is: (a) 2 (b) 2?_1 (c) 2 —1 (d) 2n_2
17. 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 LAN5 (b) For avoiding loops in the routing paths (c) For fault tolerance (d) For minimizing collisions
18. 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
19. 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 form disks is’in thldks orum
20. 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
21. Let r be a relation instance with schema R = (A, B, C, D). We define r1 = 11A,B,C (R) and r2 = 11A,D (r). Let s = * r where * denotes natural join. Given that the decomposition of r into r1 and r2 is lossy, which one of the following is TRUE? (a) scr (b) rus=r (c) rcs (d)r*s=s Q.21 — Q.58 are two mark Questions.
22. Consider the following C-program: void foo (mt n, mt sum 0) mt k = 0, j = 0; if (n==0) return; k = n % 10; j = n / 10; sum = sum + k; foo (j, sum); printf (“%d,”, k); mt main () mt a = 2048, sum = 0; foo (a, sum); printf (“%dn”, sum) What does the above program print? (a) 8, 4, 0, 2, 14 (b) 8, 4, 0, 2, 0 (C) 2, 0, 4, 8, 14 (d) 2, 0, 4, 8, 0
23. Consider the following C-program: double foo (double); /* Line 1 */ mt 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
24. 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 in-order 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
25.A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elemnts. 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
26. How many distinct binary search trees can be created out of 4 distinct keys?
(a) 5
(b) 14
(c) 24
(d) 42
27. 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—i) k+ 1
(c) n(k— 1) + 1
(d)n(k— 1)
28. Suppose T(n) =2T +n,T(0) =T(i)=i Which one of the following is FALSE?
(a) T(n)=O(n2)
(b) T(n)=9(nlogn)
(c) T(n)=c(n2)
(d) T(n)=O(nlogn)
29. Let G(V,E) be 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 (v2) (b) 0 (E + V log v) (c) 0 (v log v) (d) 0 ((E + v) log v)
30. Suppose there are logn sorted lists of n/logn]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) O(n log n) (c) O(n log n) (d) O(n2 )
31. Let P, Q and R be tree 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) XY (b) X-Y (c) Y-X (d)—1Y—X
32. What is the first order predicate calculus statement equivalent to the following? Every teacher is liked by some student (a) V(x)[teacher(x) – (y) [student(y) – likes (y,x)]] (b) V(x)[teacher(x) – (y) [student(y) A likes (y,x)]] (c) (y) V(x)[teacher(x) – [student(y) A likes (y,x)]] (d) V(x)[teacher(x) A (y) [student(y) – likes (y,x)]]
33. 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 uS, R nS are both equivalence relations. (b) R uS is an equivalence relation. (c) R nS is an equivalence relation. (d) Neither R uS nor R nS is an equivalence relation
34. Let f: B – C and g: A- B be two functions let h = f 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 to be onto (c) g should be onto but f need not be onto (d) both f and g need to be onto
35. 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 ac mod 3andbd mod 5 (a) 4 (b) 6 (c) 16 (d) 24
36. Consider three decision problems P1,1’2 and P3. It is known that P1is decidable and P2 is undecidable. Which one of the following is TRUE? (a) P3 is decidable if P 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
37. Consider the set H of all 3 x 3 matrices of the type afe Obd OOc where a,b,c,d,e and f are real numbers and abcO. under the matrix multiplication operation, the set H is: (a) a group (b) a monoid but not a group (c) a semi group but not a monoid (d) neither a group nor a semi group
38. Consider the following system of equations in three real variables x1,x2 and x3 2×1 — x2 + 3×3 = 1 3×1 + 2×2 + 5×3 = 2 + 4×2 + x3 = 3 (a) no solution (b) a unique solution (c) more than one but a finite number of solutions (d) an infinite number of solutions
39. What are the eigen values of the following 2 x 2 matrix? 2 —1 —4 5 (a) -1 and 1 (b) 1 and 6 (C) 2 and 5 (d) 4 and -1 (a) i (b) i+1 (C) 2i (d) 2’
40. Let Nf and Ndenote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Ddenote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. Which one of the following is TRUE? (a) Df C Nf and D c (b) Df C Nf and D = (c) Df = Nf and D = (d) Df = Nf and D c
41. Consider the languages: L1 ={anbncmn,m >01 and L2 ={anbmcmn,m> o) Which one of the following statements is FALSE? (a) L1 n L2 is a context-free language (b) L1 u L2 is a context-free language (c) L1 and L2 are context-free languages (d) L1 n L2 is a context sensitive language
42. 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) L1is recursive and L2is recursively enumerable (b) L1is recursive and L2is not recursively enumerable (c) L1 and L2are recursively enumerable (d) L1is recursively enumerable and L2is recursive
43. Consider the languages: L1 = {wwR w {0, 1} *1 L2 ={w#wwE {O,1}*},where # is a special symbol L3 ={wwwE {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
44. The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which one of the following is TRUE? (a) It computes l’s complement of the input number (b) It computes 2’s complement of the input number (c) It increments the input number (d) It decrements the input number
45. 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
46. A 5 stage pipelined CPU has the following sequence of stages: IF — Instruction fetch from instrution 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 state is used. WB — Register write back. Consider the following sequence of instructions: Ii: L RO, bc 1; RO <= M[locl] 12: ARO, RO 1; RO <= RO + RO 13: S R2, RO 1; R2 <= R2 - RO 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 I? (a) 8 (b) 10 (c) 12 (d) 15 47. 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 psec. The byte transfer time between the device interfaces 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 48. 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 4 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 49. Suppose n processes, P1. .... P share m identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process P, is s,, where s, >0. Which one of the following is a sufficient condition for ensuring that deadlock does not occur? (a) Vi,s1 <(m+n) (d) s1 <(m*n) 50. Consider the following code fragment: if (fork () ==O) a = a + 5; printf(”%d,%dn”, a, &a); else { a = a —5; printf(”%d, %dn”, 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 is y (c) u + 10 = x and v = y (d) u + 10 = x and v y 51. 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 52. Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 ps. The minimum frame size is: (a) 94 (b) 416 (c) 464 (d) 512 53. 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) 5 54. 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. A C 2 4 3 4 4 3 5 2 7 2 9 5 6 4 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) 55. 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 book (d) Titles of the five most expensive books 56. 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 Common Data for questions 79 and 80: Consider the following data path of a CPU. MAR MDR ST IR PC GPRs _J/LU The ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation — the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR. 57. The instruction “add RO, Ri” has the register transfer interpretation RO<= RO+R1. The minimum number of clock cycles needed for execution cycle of this instruction is: (a) 2 (b) 3 (c) 4 (d) 5 58. The instruction ‘call Rn, sub” is a two word instruction. Assuming that PC is incremented during the fetch cycle of the first word of the instruction, its register transfer interpretation is Rn<= PC+1; PC<=M[PC]; The minimum number of CPU clock cycles needed during the execution cycle of this instruction is: (a) 2 (b) 3 (c) 4 (d) 5 Linked Answer Questions: Q.59a to Q.59b carry two marks each. Statement for Linked Answer Questions 59a & 59b: Consider the following C-function: - double foo (mt n) { I- mt ±; double sum; if (n==O) return 1.0; else sum = 0.0; for (± =0; ±<=I