
#2
 
 
Re: GATE computer science old question papers with solution
This is the GATE computer science old question papers with solution: 1. This question consists of (Twentyfive) multiplechoice questions each carrying one mark. For each ques¬tion, four options are provided out of which exactly one is correct. Write the correct option for each question ONLY in the box provided for the question in the first sheet of the answer book. (25 x 1 = 25) 1.1 Suppose that the expectation of a random variable X is 5. Which of the following statements is true? • There is a sample point at which X has the value 5. • There is a sample point at which X has value greater than 5. • There is a sample point at which X has a value greater than or equal to 5. • None of the above. 1.2 The number of binary relations on a set with n elements is: • n 2 • 2 n • • None of the above 1.3 The number of binary strings of n zeros and k ones that no two ones are adjacent is • n1 C k • n C k • n C k+l • None of the above 1.4 Consider the regular expression (0 + 1) (0 + 1)……..n times. The minimum state finite automation that recognizes the language represented by this regular expression contains • n states • n + I states • n + 2 states (d) None of the above 1.5 Contextfree languages are closed under: • Union , intersection • Union , Kleene closure • Intersection, complement • Complement, Kleene Closure 1.6 Let L p be the set of all languages accepted by a PDA by final state and L E the set of all languages accepted by empty stack. Which of the following is true? (a) L D = L E (b) L D É L E (c) L D = L E (d) None of the above 1.7 Which of the following expressions is not equivalent to ? • x NAND x • x NOR x • x NAND 1 • x NOR 1 1.8 Which of the following functions implements the Karnaugh map shown below? AB/CD 00 00 11 10 00 0 0 1 0 01 X X 1 X 11 0 1 1 0 10 0 1 1 0 (a) (b) D (C + A) (c) (d) 1.9 Listed below are some operating system abstractions (in the left column) and the hardware components (in the right column)? • Thread 1. Interrupt • Virtual address space 2. Memory • File system 3. CPU • Signal 4. Disk • (A)2, (B)4, (C)3, (D)1 • (A)I, (B)2, (C)3, (D)4 • (A)3, (B)2, (C)4, (D)1 • (A)4, (B)1, (C)2, (D)3 1.10 Which of the following disk scheduling strategies is likely to give the best through put? • Farthest cylinder next • Nearest cylinder next • First come first served • Elevator algorithm 1.11 System calls are usually invoked by using • a software interrupt • polling • an indirect jump • a privileged instruction 1.12 A sorting technique is called stable if • it takes 0 (n log n) time • it maintains the relative order of occurrence of nondistinct elements • it uses divide and conquer paradigm (d) it takes 0 (n) space. 1.13 Suppose we want to arrange the n numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is • nI • n • n + 1 • None of the above 1.14 If one uses straight twoway, merge sort algorithm to sort the following elements in ascending order: 20, 47, 15, 8, 9, 4, 40, 30, 12, 17 then the order of these elements after second pass of the algorithm is : • 8,9, 15,20,47,4, 12, 17,30,40 • 8, 15,20,47,4,9,30,40, 12, 17 • 15,20,47, 4, 8, 9,12,30,40,17 • 4,8,9,15, 20,47, 12, 17,30,40 • The number of articulation points of the following graph is • 0 • 1 • 2 • 3 1.16 If n is a power of 2, then the minimum number of multiplications needed to compute a* is • log 2n • • nI • n 1.17 Which of the following is the most powerful parsing method? • LL (I) • Canonical LR • SLR • LALR 1.18 Consider the join of a relation R with a relation S. If R has m tuples and S has n tuples then the maximum and minimum sizes of the join respectively are • m+n and O • mn and O • m+ n and mn  • mn and m+ n 1.19 The relational algebra expression equivalent to the following tuple calculus expression: {t  t Î r Ù (t [A] = 10 Ù t[B] = 20)} is : • s (A=10vB=20) (r) • s (A=l0) (r) È s (B=20) (r) • s (A= 10) (r) Ç s (B=20) (r) • s (A=IO) (r)  s (B=20) (r) 1.20 Booth's coding in 8 bits for the decimal number  57 is • 0  100 + 1000 • 0  100 + 100 – I • 0  1 + 100 10 + I • 00 10 + 1001 1.21 The maximum gate delay for any output to appear in an array multiplier for multiplying two n bit number is • O(n 2) • O(n) • O (log n) • O (I) 1.22 The main memory of a computer has 2 cm blocks while the cache has 2 c blocks. If the cache uses the set associative mapping scheme with 2 blocks per set, then block k of the main memory maps to the set • (k mod m) of the cache • (k mod c) of the cache • (k mod 2c) of the cache • (k mod 2 cm) of the cache 1.23 The NewtonRaphson method is to be used to find the root of the equation f (x) = 0 where Xo is the initial approximation and f 1 is the derivative of f. The method converges • always • only if f is a polynomial • only if f (x o) < 0 • none of the above 1.24 Let R = (a, b, c, d, e, f) be a relation scheme with the following dependencies c ® f, e ® a, ec ® d, a ® b. Which of the following is a key for R ? • CD • EC • AE • AC 1.25 Which of the following is correct? • Btrees are for storing data on disk and B* trees are for main memory. • Range queries are faster on B* trees. • Btrees are for primary indexes and B* trees are for secondary indexes. • The height of a B* tree is independent of the number of records. 2. This question consists of 25 (Twentyfive) multiplechoice questions each carrying 2 marks. For each question , 4 options are provided out of which one or more are correct. Write ALL the correct options for each question, only in the box provided for the question in the second sheet of the answer book. Credit will be given only if all and only the correct options are written. (25 x 2 = 50) • Consider two events E 1 and E 2 such that probability of E 1, Pr [E 1] = ½ probability of E 2, Pr [E 21 ] = 1/3, and probability of E 1 and E 2, Pr [E 1 and E 2] = 1/5. Which of the following statements is/are true? • Pr [E 1 or E 2] is 2/3 • Events E 1 and E 2 are independent • Events E 1 and E 2 are not independent • • Two girls have picked 10 roses, 15 sunflowers and 15 daffodils. What is the number of ways they can divide the flowers amongst themselves? • 1638 • 2100 • 2640 • None of the above 2.3 Let L be a set with a relation R which is transitive, antisymmetric and reflexive and for any two elements a, b Î L let the least upper bound lub (a, b) and the greatest lower bound glb (a, b) exist. Which of the following is/are true? • L is a poset • L is a boolean algebra • L is a lattice • None of the above 2.4 If L1 is context free language and L2 is a regular language which of the following is/are false? • L1  L2 is not context free • L1 Ç L2 is context free • ~ L1 is context free • ~ L2 is regular 2.5 Given the programming constructs (i) assignment (ii) for loops where the loop parameter cannot be changed within the loop (iii) Ifthenelse (iv) forward go to (v) arbitrary go to (vi) nonrecursive proce dure call (vii) recursive procedure/function call (viii) repeat loop, which constructs will you not include in a programming language such that it should be possible to program the terminates (i.e. halting) function in the same programming language. • (ii), (iii), (iv) • (v), (vii), (viii) • (vi), (vii), (viii) • (iii), (vii), (viii) • For the schedule given below, which of the following is correct: 1 Read A 2 Read B 3 Write A 4 Read A 5 Write A 6 Write B 7 Read B 8 Write B (a) This schedule is serialisable and can occur in a scheme using 2PL protocol. (b) This schedule is serialisable but cannot occur in a scheme using 2PL protocol. (c) This schedule is not serialisable but can occur in a scheme using 2PL protocol. (d) This schedule is not serialisable and cannot occur in a scheme using 2PL protocol. 2.7 Consider the schema R = (S T U V) and the dependencies S ® T, T ® U. U ® V and V ® S. Let R = (R1 and R2) be a decomposition such that R1 Ç R2 = Æ . The decomposition is • not in 2NF • in 2NF but not 3NF • in 3NF but not in 2NF • in both 2NF and 3NF • Consider the circuit shown below. In a certain steady state, the line Y is at '1 '. What are the possible values of A, B, and C in this state? • A = 0, B = 0, C = I • A = 0, B = 1, C = 1 • A = 1, B = 0, C = 1 • A = 1, B = 1, C = 1 2.9 Which of the following sets of component (s) is/are sufficient to implement any arbitrary boolean func¬ tion? • XOR gates, NOT gates • 2 to I multiplexors • AND gates, XOR gates • Threeinput gates that output (A. B) + C for the inputs A B. and C. 2.10 A multiuser, multiprocessing operating system cannot be implemented on hardware that does not support • Address translation • DMA for disk transfer • At least two modes of CPU execution (privileged and nonprivileged) • Demand paging. 2.11 Which of the following is/are advantages of virtual memory? (a) Faster access to memory on an average. (b) Processes can be given protected address spaces. (c) Linker can assign addresses independent of where the program will be loaded in physical memory. (d) Programs larger than the physical memory size can be run. 2.12 Which of the following actions is/are typically not performed by the operating system when switching context from process A to process B? (a) Saving current register values and restoring saved register values for process B. (b) Changing address translation tables. (c) Swapping out the memory image of process A to the disk (d) Invalidating the translation lookaside buffer. • Consider the following program in a language that has dynamic scoping var x: real; procedure show: begin print (x) ; end; procedure small : var x: real; begin x : = 0.125; show; end: begin x : = 0.25; show; small end. Then the output of the program is : • 0.125 0.125 • 0.25 0.25 • 0.25 0.125 • 0.125 0.25 • The number of tokens in the Fortran statement DO 10I= 1.25 is • 3 • 4 • 5 • None of the above 2.15 A grammar that is both left and right recursive for a nonterminal, is • Ambiguous • Unambiguous • Information is not sufficient to decide whether it is ambiguous or unambiguous • None of the above 2.16 The number of full and halfadders required to add 16bit numbers is • 8 halfadders, 8 fulladders • 1 halfadder, 15 fulladders • 16 halfadders, 0 fulladders • 4 halfadders, 12 fulladders 2.17 Zero has two representations in • Sign magnitude • 1's complement • 2's complement • none of the above • Raid configurations of disks are used to provide • Faulttolerance • High speed • High data density • None of the above 2.19 Arrange the following configurations for. CPU in decreasing order of operating speeds: Hard wired control, vertical microprogramming, horizontal microprogramming. • Hard wired control, vertical microprogramming, horizontal microprogramming • Hard wired control, horizontal microprogramming, vertical microprogramming • Horizontal microprogramming, vertical microprogramming, hard wired control. • Vertical microprogramming, horizontal microprogramming, hard wired control. 2.20 The minimum number of record movements required to merge five files A (with 10 records), B (with 20 records), C (with 15 records), D (with 15 records), D (with 5 records) and E (with 25 records) is: • 165 • 90 • 75 • 65 2.21 If T 1 = 0 (1), give the correct matching for the following pairs: (M) T n = T n1 + n (U) T n = 0 (n) (N) T n = T n/2 + n (V) T n = 0 (nlog n) (0) T n =T n/2+n1ogn (W) T n=0(n 2) (P) T n = T n1 + log n (X) T n = 0 (log 2 n) • MW, NV, OU, PX • MW, NU, OX, PV • MV, NW, OX, PU • MW, NU, OV, PX 2.22 The main difference(s) between a ClSC and a RISC processor is/are that a RISC processor typically • has fewer instructions • has fewer addressing ,modes • has more registers • is easier to implement using hardwired control logic 2.23 A certain processor supports only the immediate and the direct addressing modes. Which of the follow¬ing programming language features cannot be implemented on this processor? • Pointers • Arrays • Records • Recursive procedures with local variable • Consider the following C function definition int Trial (int a, int b, int c) { if ((a> = b)&& (c < b) return b; else if (a> = b) return Trial (a, c, b); else return Trial (b, a, c) ; } The function Trial : • finds the maximum of a, b and c • finds the minimum of a, b and c • finds the middle number of a, b, c • none of the above 2.25 Which of the following is/are correct ? • An SQL query automatically eliminates duplicates • An SQL query will not work if there are no indexes on the relations • SQL permits attribute names to be repeated in the same relation • None of the above 
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
MTECH Question Papers Computer Science PTU  Unregistered  Main Forum  2  1st June 2018 04:15 PM 
MSC computer science entrance question papers  Tysrmm  Main Forum  5  9th June 2016 06:44 PM 
GATE Computer Science Last year Question Papers  Unregistered  Main Forum  3  21st May 2015 04:38 PM 
TRB computer science question papers  Unregistered  Main Forum  3  21st May 2015 04:31 PM 
KVS PGT Computer Science old question papers  Unregistered  Main Forum  3  23rd February 2015 12:21 PM 
DRDO question papers of computer science  Unregistered  Main Forum  1  16th December 2014 12:02 PM 
Computer Science Question Papers  Unregistered  Main Forum  1  19th November 2014 04:26 PM 
GATE Computer Science And IT Exam Question Paper  Unregistered  Main Forum  1  17th November 2014 09:48 AM 
Bsc computer science question papers  Unregistered  Main Forum  1  30th October 2014 09:13 AM 
GATE Computer Science Exam Question Paper  Unregistered  Main Forum  3  2nd September 2014 04:49 PM 
GATE (Computer Science) Previous Papers  Unregistered  Main Forum  1  21st August 2014 09:47 AM 
GATE (Electrical Engineering) Previous year papers with solution  Unregistered  Main Forum  1  13th August 2014 01:52 PM 
GATE Computer Science Question Paper  Unregistered  Main Forum  1  5th August 2014 11:22 AM 
GATE previous year question papers of Computer Science and Information Technology  Unregistered  Main Forum  3  4th August 2014 03:24 PM 
Solved papers for GATE Computer Science and Engineering  Unregistered  Main Forum  1  2nd August 2014 12:28 PM 
HAL Computer Science Question Papers  Unregistered  Main Forum  1  2nd August 2014 11:15 AM 
GATE Computer Science question papers  Unregistered  Main Forum  1  1st August 2014 11:37 AM 
GATE Computer Science Previous year question paper  Unregistered  Main Forum  1  30th July 2014 12:40 PM 
Computer Science and Information Technology GATE previous year question papers  Unregistered  Main Forum  1  22nd July 2014 10:36 AM 
GATE in Computer Science Solved question papers  Unregistered  Main Forum  1  20th July 2014 09:04 AM 
Thread Tools  Search this Thread 
