# GATE- Computer Science(CS)- 2009

16 pages
96 views

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
CS GATE Paper 2009 Q. No. 1 – 20 Carry One Mark Each 1. 2. Which one of the following in NOT necessarily a property of a Group? (A) Commutativity (B) Associativity (C) Existence of inverse for every element (D) Existence of identity What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n 2. (A) 2 (B) 3 (C) n-1 (D) n 3. 4. 5. Which one of the following is TRUE for any simple connected undirect
Tags

## Computer Engineering

Transcript
CS  GATE Paper 2009 Q. No. 1 – 20 Carry One Mark Each1. 2. Which one of the following in NOT necessarily a property of a Group?(A) Commutativity (B) Associativity(C) Existence of inverse for every element (D) Existence of identityWhat is the chromatic number of an n-vertex simple connected graph which doesnot contain any odd length cycle? Assume n 2.(A) 2 (B) 3 (C) n-1 (D) n3. 4.5. Which one of the following is TRUE for any simple connected undirected graphwith more than 2 vertices?(A) No two vertices have the same degree.(B) At least two vertices have the same degree.(C) At least three vertices have the same degree.(D) All vertices have the same degree.Consider the binary relation R = {(x,y), (x,z), (z,x), (z,y)} on the set {x,y,z}.Which one of the following is TRUE?(A) R is symmetric but NOT antisymmetric(B) R is NOT symmetric but antisymmetric(C) R is both symmetric and antisymmetric(D) R is neither symmetric nor antisymmetric(1217) 8 is equivalent to(A) (1217) 16 (B) (028F) 16 (C) (2297) 10 (D) (0B17) 16 6. What is the minimum number of gates required to implement the Booleanfunction (AB+C) if we have to use only 2-input NOR gates?(A) 2 (B) 3 (C) 4 (D) 57. How many 32K x 1 RAM chips are needed to provide a memory capacity of 256K- bytes?(A) 8 (B) 32 (C) 64 (D) 1288. A CPU generally handles an interrupt by executing an interrupt service routine(A) As soon as an interrupt is raised(B) By checking the interrupt register at the end of fetch cycle.(C) By checking the interrupt register after finishing the execution of the currentinstruction.(D) By checking the interrupt register at fixed time intervals. .Page 1 of 13  CS  GATE Paper 2009 9. In which one of the following page replacement policies, Belady’s anomaly mayoccur?(A) FIFO (B) Optimal (C) LRU (D) MRU10. The essential content(s) in each entry of a page table is / are(A) Virtual page number (B) Page frame number (C) Both virtual page number and page frame number (D) Access right information11. What is the number of swaps required to sort n elements using selection sort, inthe worst case?(A) (n)(B) (n log n)(C)   (n ) 2 (D)   (n log n) 2 12. S → aSa bSb a b ;The language generated by the above grammar over thealphabet {a,b} is the set of (A) All palindromes.(B) All odd length palindromes.(C) Strings that begin and end with the same symbol(D) All even length palindromes. 13. Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm?P. Always finds a negative weighted cycle, if one exists.Q. Finds whether any negative weighted cycle is reachable from the source.(A) P only(C) both P and Q(B) Q only(D) Neither P nor Q14. Let  A be a problem that belongs to the class NP. Then which one of thefollowing is TRUE?(A) There is no polynomial time algorithm for   A .(B) If   A can be solved deterministically in polynomial time, then P = NP.(C) If   A is NP-hard, then it is NP-complete.(D)  A may be undecidable.15. Which one of the following languages over the alphabet {0,1} is described by theregular expression: (0+1)*0(0+1)*0(0+1)*?(A) The set of all strings containing the substring 00.(B) The set of all strings containing at most two 0’s.(C) The set of all strings containing at least two 0’s.(D) The set of all strings that begin and end with either 0 or 1. . Page 2 of 13  CS  GATE Paper 2009 16. Which one of the following is FALSE?(A) There is unique minimal DFA for every regular language(B) Every NFA can be converted to an equivalent PDA.(C) Complement of every context-free language is recursive.(D) Every nondeterministic PDA can be converted to an equivalent deterministicPDA.17. Match all items in Group 1 with correct options from those given in Group 2.Group 1P. Regular expressionQ. Pushdown automataR. Dataflow analysisS. Register allocation(A) P-4. Q-1, R-2, S-3(C) P-3, Q-4, R-1, S-218. Consider the program below: # include < stdio.h >int fun(int n, int * f_p) {int t, f;if (n <= 1) {* f_p = 1;return 1;}t = fun (n- 1, f_p);f = t+ * f_p;* f_p = t;return f;}int main() {int x = 15; printf ( % d\ n , fun(5, & x));return 0;} The value printed isGroup 21. Syntax analysis2. Code generation3. Lexical analysis4. Code optimization(B) P-3, Q-1, R-4, S-2(D) P-2, Q-1, R-4, S-3(A) 6 (B) 8 (C) 14 (D) 1519. The coupling between different modules of a software is categorized as follows:I. Content coupling III. Control coupling V. Data couplingII. Common couplingIV Stamp couplingCoupling between modules can be ranked in the order of strongest (leastdesirable) to weakest (most desirable) as follows:(A) I-II-III-IV-V (B) V-IV-III-II-I (C) I-III-V -II-IV (D) IV-II-V -III-I . Page 3 of 13  CS  GATE Paper 2009 20. Consider the HTML table definition given below: < table border=1><tr> <td rowspan=2> ab </td><td colspan=2> cd </td></tr><tr> <td> ef </td><td rowspan=2> gh </td></tr><tr> <td colspan=2> ik </td></tr></table>The number of rows in each column and the number of columns in each row are:(A) 2,2, 3 and 2,3,2 (C) 2,3,2 and 2,3,2 (B) 2,2, 3 and 2,2, 3(D) 2,3,2 and 2,2, 3Q. No. 21 – 56 Carry Two Marks Each21. An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The  probability that the face value is odd is 90% of the probability that the face value is even. The probability of getting any even numbered face is the same. If the probability that the face is even given that it is greater than 3 is 0.75,which one of the following options is closest to the probability that the face value exceeds 3?(A) 0.453 (B) 0.468 (C) 0.485 (D) 0.49222. For the composition table of a cyclic group shown below* a b c da bc d a bcd badccd badca bWhich one of the following choices is correct?(A) a, b are generators(C) c, d are generators(B) b, c are generators(D) d, a are generators23. Which one of the following is the most appropriate logical formula to representthe statement? “Gold and silver ornaments are precious”.The following notations are used:G(x): x is a gold ornamentS(x): x is a silver ornamentP(x): x is precious ∀ ( ( ) → ( ( ) ∧ S x ( ) ) ) ∀ ( ( ( ) ∧ Sx ( ) ) → ( ) ) (A) x P xG x(B) x G xP x ∃ ( ( ( ) ∧ Sx ( ) ) → ( ) ) ∀ ( ( ( ) ∨ Sx ( ) ) → ( ) ) (C) x G xP x(D) x G xP x
Related Search
Similar documents

### Faculty of Computer Science 16 Na 21

View more...

#### The Ecosystems Culture

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us. Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x