Page 1 ?EC?Test ID: 00 All India Mock GATE Test Series Q.1 â€“ Q.20 Carry One Mark Each 1. Consider the polynomial ( ) 2 2 0 1 2 3 , p x a a x a x a x = + + + where 0, . i a i ? ? The minimum number of multiplications needed to evaluate pon an input x is: (A) 3 (B) 4 (C) 6 (D) 9 2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set of all subsets of W. The number of functions from Z to E is: (A) 2 xy Z (B) 2 xy Z× (C) 2 x y Z + (D) 2 xyz 3. The set { } 1,2,3,5,7,8,9 under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false? (A) It is not closed (B) 2 does not have an inverse (C) 3 does not have an inverse (D) 8 does not have an inverse 4. A relation R is defined on ordered pairs of integers as follows: ( ) ( ) , , x y R u v if and . x u y v < > Then R is: (A) Neither a Partial Order nor an Equivalence Relation (B) A Partial Order but not a Total Order (C) A Total Order (D) An Equivalence Relation 5. For which one of the following reasons does Internet Protocol (IP) use the time- to-live (TTL) field in the IP datagram header? (A) Ensure packets reach destination within that time (B) Discard packets that reach later than that time (C) Prevent packets from looping indefinitely (D) Limit the time for which a packet gets queued in intermediate routers. 6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are Page 2 ?EC?Test ID: 00 All India Mock GATE Test Series Q.1 â€“ Q.20 Carry One Mark Each 1. Consider the polynomial ( ) 2 2 0 1 2 3 , p x a a x a x a x = + + + where 0, . i a i ? ? The minimum number of multiplications needed to evaluate pon an input x is: (A) 3 (B) 4 (C) 6 (D) 9 2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set of all subsets of W. The number of functions from Z to E is: (A) 2 xy Z (B) 2 xy Z× (C) 2 x y Z + (D) 2 xyz 3. The set { } 1,2,3,5,7,8,9 under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false? (A) It is not closed (B) 2 does not have an inverse (C) 3 does not have an inverse (D) 8 does not have an inverse 4. A relation R is defined on ordered pairs of integers as follows: ( ) ( ) , , x y R u v if and . x u y v < > Then R is: (A) Neither a Partial Order nor an Equivalence Relation (B) A Partial Order but not a Total Order (C) A Total Order (D) An Equivalence Relation 5. For which one of the following reasons does Internet Protocol (IP) use the time- to-live (TTL) field in the IP datagram header? (A) Ensure packets reach destination within that time (B) Discard packets that reach later than that time (C) Prevent packets from looping indefinitely (D) Limit the time for which a packet gets queued in intermediate routers. 6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are ?EC?Test ID: 00 All India Mock GATE Test Series needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end. (A) 1 (B) 2 (C) 3 (D) 4 7. Consider the following grammar. * S S E S E E F E E F F id ? ? ? + ? ? Consider the following ( ) 0 LR items corresponding to the grammar above. (i) *. S S E ? (ii) . E F E ? + (iii) . E F E ? + Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar? (A) (i) and (ii) (B) (ii) and (iii) (C) (i) and (iii) (D) None of the above 8. You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of f by 180°? (A) (B) f clk D Q D Q f clk D D Q Q Page 3 ?EC?Test ID: 00 All India Mock GATE Test Series Q.1 â€“ Q.20 Carry One Mark Each 1. Consider the polynomial ( ) 2 2 0 1 2 3 , p x a a x a x a x = + + + where 0, . i a i ? ? The minimum number of multiplications needed to evaluate pon an input x is: (A) 3 (B) 4 (C) 6 (D) 9 2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set of all subsets of W. The number of functions from Z to E is: (A) 2 xy Z (B) 2 xy Z× (C) 2 x y Z + (D) 2 xyz 3. The set { } 1,2,3,5,7,8,9 under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false? (A) It is not closed (B) 2 does not have an inverse (C) 3 does not have an inverse (D) 8 does not have an inverse 4. A relation R is defined on ordered pairs of integers as follows: ( ) ( ) , , x y R u v if and . x u y v < > Then R is: (A) Neither a Partial Order nor an Equivalence Relation (B) A Partial Order but not a Total Order (C) A Total Order (D) An Equivalence Relation 5. For which one of the following reasons does Internet Protocol (IP) use the time- to-live (TTL) field in the IP datagram header? (A) Ensure packets reach destination within that time (B) Discard packets that reach later than that time (C) Prevent packets from looping indefinitely (D) Limit the time for which a packet gets queued in intermediate routers. 6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are ?EC?Test ID: 00 All India Mock GATE Test Series needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end. (A) 1 (B) 2 (C) 3 (D) 4 7. Consider the following grammar. * S S E S E E F E E F F id ? ? ? + ? ? Consider the following ( ) 0 LR items corresponding to the grammar above. (i) *. S S E ? (ii) . E F E ? + (iii) . E F E ? + Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar? (A) (i) and (ii) (B) (ii) and (iii) (C) (i) and (iii) (D) None of the above 8. You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of f by 180°? (A) (B) f clk D Q D Q f clk D D Q Q ?EC?Test ID: 00 All India Mock GATE Test Series (C) (D) 9. A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)? (A) 400 (B) 500 (C) 600 (D) 700 10. In a binary max heap containing n numbers, the smallest element can be found in time (A) ( ) O n (B) ( ) log O n (C) ( ) loglog O n (D) ( ) 1 O 11. Consider a weighted complete graph G on the vertex set { } 1 2 , ,...., n ? ? ? such that the weight of the edge ( ) , is 2 - . i j i j ? ? The weight of a minimum spanning tree of G is: (A) 1 n- (B) 2 2 n- (C) 2 n ? ? ? ? ? ? (D) 2 n 12. To implement Dijkstraâ€™s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: (A) Queue f clk D D Q Q f clk D Q D Q Page 4 ?EC?Test ID: 00 All India Mock GATE Test Series Q.1 â€“ Q.20 Carry One Mark Each 1. Consider the polynomial ( ) 2 2 0 1 2 3 , p x a a x a x a x = + + + where 0, . i a i ? ? The minimum number of multiplications needed to evaluate pon an input x is: (A) 3 (B) 4 (C) 6 (D) 9 2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set of all subsets of W. The number of functions from Z to E is: (A) 2 xy Z (B) 2 xy Z× (C) 2 x y Z + (D) 2 xyz 3. The set { } 1,2,3,5,7,8,9 under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false? (A) It is not closed (B) 2 does not have an inverse (C) 3 does not have an inverse (D) 8 does not have an inverse 4. A relation R is defined on ordered pairs of integers as follows: ( ) ( ) , , x y R u v if and . x u y v < > Then R is: (A) Neither a Partial Order nor an Equivalence Relation (B) A Partial Order but not a Total Order (C) A Total Order (D) An Equivalence Relation 5. For which one of the following reasons does Internet Protocol (IP) use the time- to-live (TTL) field in the IP datagram header? (A) Ensure packets reach destination within that time (B) Discard packets that reach later than that time (C) Prevent packets from looping indefinitely (D) Limit the time for which a packet gets queued in intermediate routers. 6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are ?EC?Test ID: 00 All India Mock GATE Test Series needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end. (A) 1 (B) 2 (C) 3 (D) 4 7. Consider the following grammar. * S S E S E E F E E F F id ? ? ? + ? ? Consider the following ( ) 0 LR items corresponding to the grammar above. (i) *. S S E ? (ii) . E F E ? + (iii) . E F E ? + Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar? (A) (i) and (ii) (B) (ii) and (iii) (C) (i) and (iii) (D) None of the above 8. You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of f by 180°? (A) (B) f clk D Q D Q f clk D D Q Q ?EC?Test ID: 00 All India Mock GATE Test Series (C) (D) 9. A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)? (A) 400 (B) 500 (C) 600 (D) 700 10. In a binary max heap containing n numbers, the smallest element can be found in time (A) ( ) O n (B) ( ) log O n (C) ( ) loglog O n (D) ( ) 1 O 11. Consider a weighted complete graph G on the vertex set { } 1 2 , ,...., n ? ? ? such that the weight of the edge ( ) , is 2 - . i j i j ? ? The weight of a minimum spanning tree of G is: (A) 1 n- (B) 2 2 n- (C) 2 n ? ? ? ? ? ? (D) 2 n 12. To implement Dijkstraâ€™s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: (A) Queue f clk D D Q Q f clk D Q D Q ?EC?Test ID: 00 All India Mock GATE Test Series (B) Stack (C) Heap (D) B-Tree 13. A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be (A) 2 log n (B) n (C) 2 1 n+ (D) 2 1 n - 14. Which one of the following in place sorting algorithms needs the minimum number of swaps? (A) Quick sort (B) Insertion sort (C) Selection sort (D) Heap sort 15. Consider the following C-program fragment in which , and n i j are integer variables. ( ) for i = n, j = 0; i > 0; i /= 2, j +=i ; Let ( ) val j denote the value stored in the variable j after termination of the for loop. Which one of the following is true? (A) ( ) ( ) log val j n ? = (B) ( ) ( ) val j n ? = (C) ( ) ( ) val j n ? = (D) ( ) ( ) log val j n n ? = 16. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? (A) R is NP-complete (B) R is NP-hard (C) Q is NP-complete (D) Q is NP-hard Page 5 ?EC?Test ID: 00 All India Mock GATE Test Series Q.1 â€“ Q.20 Carry One Mark Each 1. Consider the polynomial ( ) 2 2 0 1 2 3 , p x a a x a x a x = + + + where 0, . i a i ? ? The minimum number of multiplications needed to evaluate pon an input x is: (A) 3 (B) 4 (C) 6 (D) 9 2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W X Y = × and E be the set of all subsets of W. The number of functions from Z to E is: (A) 2 xy Z (B) 2 xy Z× (C) 2 x y Z + (D) 2 xyz 3. The set { } 1,2,3,5,7,8,9 under multiplication modulo 10 is not a group. Given below are four plausible reasons. Which one of them is false? (A) It is not closed (B) 2 does not have an inverse (C) 3 does not have an inverse (D) 8 does not have an inverse 4. A relation R is defined on ordered pairs of integers as follows: ( ) ( ) , , x y R u v if and . x u y v < > Then R is: (A) Neither a Partial Order nor an Equivalence Relation (B) A Partial Order but not a Total Order (C) A Total Order (D) An Equivalence Relation 5. For which one of the following reasons does Internet Protocol (IP) use the time- to-live (TTL) field in the IP datagram header? (A) Ensure packets reach destination within that time (B) Discard packets that reach later than that time (C) Prevent packets from looping indefinitely (D) Limit the time for which a packet gets queued in intermediate routers. 6. Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are ?EC?Test ID: 00 All India Mock GATE Test Series needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end. (A) 1 (B) 2 (C) 3 (D) 4 7. Consider the following grammar. * S S E S E E F E E F F id ? ? ? + ? ? Consider the following ( ) 0 LR items corresponding to the grammar above. (i) *. S S E ? (ii) . E F E ? + (iii) . E F E ? + Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar? (A) (i) and (ii) (B) (ii) and (iii) (C) (i) and (iii) (D) None of the above 8. You are given a free running clock with a duty cycle of 50% and a digital waveform f which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of f by 180°? (A) (B) f clk D Q D Q f clk D D Q Q ?EC?Test ID: 00 All India Mock GATE Test Series (C) (D) 9. A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of the following is a legal program counter (all values in decimal)? (A) 400 (B) 500 (C) 600 (D) 700 10. In a binary max heap containing n numbers, the smallest element can be found in time (A) ( ) O n (B) ( ) log O n (C) ( ) loglog O n (D) ( ) 1 O 11. Consider a weighted complete graph G on the vertex set { } 1 2 , ,...., n ? ? ? such that the weight of the edge ( ) , is 2 - . i j i j ? ? The weight of a minimum spanning tree of G is: (A) 1 n- (B) 2 2 n- (C) 2 n ? ? ? ? ? ? (D) 2 n 12. To implement Dijkstraâ€™s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: (A) Queue f clk D D Q Q f clk D Q D Q ?EC?Test ID: 00 All India Mock GATE Test Series (B) Stack (C) Heap (D) B-Tree 13. A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be (A) 2 log n (B) n (C) 2 1 n+ (D) 2 1 n - 14. Which one of the following in place sorting algorithms needs the minimum number of swaps? (A) Quick sort (B) Insertion sort (C) Selection sort (D) Heap sort 15. Consider the following C-program fragment in which , and n i j are integer variables. ( ) for i = n, j = 0; i > 0; i /= 2, j +=i ; Let ( ) val j denote the value stored in the variable j after termination of the for loop. Which one of the following is true? (A) ( ) ( ) log val j n ? = (B) ( ) ( ) val j n ? = (C) ( ) ( ) val j n ? = (D) ( ) ( ) log val j n n ? = 16. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? (A) R is NP-complete (B) R is NP-hard (C) Q is NP-complete (D) Q is NP-hard ?EC?Test ID: 00 All India Mock GATE Test Series 17. An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array (A) Solves it in linear time using a left to right pass of the array (B) Solves it in linear time using a right to left pass of the array (C) Solves it using divide and conquer in time ( ) log n n ? (D) Solves it in time ( ) 2 n ? 18. We are given a set { } 1 ,...... where 2. i n i X x x x = = A sample S X ? is drawn by selecting each i x independently with probability 1 . 2 i p = The expected value of the smallest number in sample S is: (A) 1 n (B) 2 (C) n (D) n 19. Let { } { } 1 2 0 1 0 , 0 , 0 1 0 , 0 , n m n m n m n m m L n m L n m + + + = = = = and { } 3 0 1 0 , 0 . n m n m n m L n m + + + = = Which of these languages are NOT context free? (A) 1 L only (B) 3 L only (C) 1 2 and L L (D) 2 3 and L L 20. Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest. 1. T1 start 2. T1 B old=1200 new=10000 3. T1 M old=0 new=2000 4. T1 commit 5. T2 start 6. T2 B old=10000 new=10500 7. T2 commit Suppose the database system crashes just before log record 7 is written. When the system is restarted, which one statement is true of the recovery procedure? (A) We must redo log record 6 to set B to 10500 (B) We must undo log record 6 to set B to 10000 and then redo log records 2 and 3Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!