Sample Language Quiz
A SAMPLE GATE QUIZ FOR THOSE WHO ARE PREPARING FOR THE GATE
- 1.
The minimum number of D flip-flops needed to design a mod-258 counter is?
- A.
9
- B.
8
- C.
512
- D.
258
Correct Answer
A. 9 -
- 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
Correct Answer
A. Commutativity -
- 3.
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
Correct Answer
A. 2 -
- 4.
Which one of the following is TRUE for any simple connected undirected graph with 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.
Correct Answer
D. All vertices have the same degree. -
- 5.
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
Correct Answer
D. R is neither symmetric nor antisymmetric -
- 6.
(1217)8 is equivalent to
- A.
(1217)16
- B.
(028F)16
- C.
(2297)10
- D.
(0B17)16
Correct Answer
B. (028F)16 -
- 7.
What is the minimum number of gates required to implement the Boolean function (AB+C) if we have to use only 2-input NOR gates?
- A.
2
- B.
3
- C.
4
- D.
5
Correct Answer
D. 5 -
- 8.
How many 32K x 1 RAM chips are needed to provide a memory capacity of 256Kbytes?
- A.
8
- B.
32
- C.
64
- D.
128
Correct Answer
C. 64 -
- 9.
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 current instruction.
- D.
By checking the interrupt register at fixed time intervals.
Correct Answer
C. By checking the interrupt register after finishing the execution of the current instruction. -
- 10.
In which one of the following page replacement policies, Belady’s anomaly may occur?
- A.
FIFO
- B.
OPTIMAL
- C.
LRU
- D.
MRU
Correct Answer
A. FIFO -
- 11.
The essential content(s) in each entry of a page table is / are
- A.
Virtual page numbe
- B.
Page frame number
- C.
Both virtual page number and page frame number
- D.
Access right information
Correct Answer
B. Page frame number -
- 12.
What is the number of swaps required to sort n elements using selection sort, in the worst case
- A.
θ(n)
- B.
θ(n log n)
- C.
θ(n )
- D.
θ(n log n)
Correct Answer
C. θ(n ) -
- 13.
S->aSa|bSb|a|b ;The language generated by the above grammar over the alphabet {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.
Correct Answer
B. All odd length palindromes. -
- 14.
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
- B.
Q only
- C.
Both P and Q
- D.
Neither P nor Q
Correct Answer
A. P only -
- 15.
Let π be a problem that belongs to the class NP. Then which one of the following is TRUE?
- A.
There is no polynomial time algorithm for π
- 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.
π may be undecidable.
Correct Answer
C. If A π is NP-hard, then it is NP-complete. -
- 16.
Which one of the following languages over the alphabet {0,1} is described by the regular 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.
Correct Answer
C. The set of all strings containing at least two 0’s. -
- 17.
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 deterministic PDA.
Correct Answer
D. Every nondeterministic PDA can be converted to an equivalent deterministic PDA. -
- 18.
Match all items in Group 1 with correct options from those given in Group 2. Group 1(P. Regular expression, Q. Pushdown automata, R. Dataflow analysis, S. Register allocation) Group 2(1. Syntax analysis, 2. Code generation, 3. Lexical analysis, 4. Code optimization )
- A.
P-4. Q-1, R-2, S-3
- B.
P-3, Q-1, R-4, S-2
- C.
P-3, Q-4, R-1, S-2
- D.
P-2, Q-1, R-4, S-3
Correct Answer
B. P-3, Q-1, R-4, S-2 -
- 19.
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 is
- A.
6
- B.
8
- C.
14
- D.
15
Correct Answer
B. 8 -
- 20.
The coupling between different modules of a software is categorized as follows: I. Content coupling II. Common coupling III. Control coupling IV Stamp coupling V. Data coupling Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows:
- A.
I-II-III-IV-V
- B.
I-II-III-IV-V
- C.
I-III-V -II-IV
- D.
IV-II-V -III-I
Correct Answer
A. I-II-III-IV-V -
- 21.
The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows: ( ) void enter_CS(X) } while test-and-set(X) ; { void leave_CS(X) } X=0; { In the above solution, X is a memory location associated with the CS and is initialized to 0. Now consider the following statements: I. The above solution to CS problem is deadlock-free II. The solution is starvation free. III. The processes enter CS in FIFO order. IV More than one process can enter CS at the same time. Which of the above statements is TRUE?
- A.
I only
- B.
I and II
- C.
II and III
- D.
IV only
Correct Answer
A. I only -
- 22.
A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because
- A.
It reduces the memory access time to read or write a memory location.
- B.
It helps to reduce the size of page table needed to implement the virtual address space of a process
- C.
It is required by the translation lookaside buffer.
- D.
It helps to reduce the number of page faults in page replacement algorithms.
Correct Answer
B. It helps to reduce the size of page table needed to implement the virtual address space of a process -
- 23.
In quick sort, for sorting n elements, the (n/4) the smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?
- A.
θ(n)
- B.
θ(n log n)
- C.
θ(n*n)
- D.
θ(n*n log n)
Correct Answer
B. θ(n log n) -
- 24.
Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence: 4, 34, 10, 7, 19, 73, 2, 15, 6, 20 Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is used?
- A.
95ms
- B.
119ms
- C.
233ms
- D.
276ms
Correct Answer
B. 119ms -
- 25.
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
- A.
2
- B.
3
- C.
4
- D.
5
Correct Answer
C. 4 -
Quiz Review Timeline +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Mar 18, 2022Quiz Edited by
ProProfs Editorial Team -
Oct 14, 2011Quiz Created by
Jithcooool
Back to top