GATE CSE 2020

Question 1
Consider the functions

I. e^{-x}
II. x^2-\sin x
III. \sqrt{x^3+1}

Which of the above functions is/are increasing everywhere in [0,1] ?
A
III only
B
II only
C
II and III only
D
I and III only
Engineering Mathematics   Calculus
Question 2
For parameters a and b, both of which are \omega(1) , T(n)=T(n^{1/a})+1, and T(b)=1. Then T(n) is
A
\Theta (\log _a \log_b n)
B
\Theta (\log _{ab} n)
C
\Theta (\log _b \log_a n)
D
\Theta (\log _2 \log_2 n)
Algorithm   Recurrence Relation
Question 3
Consider the following statements.

I. Daisy chaining is used to assign priorities in attending interrupts.
II. When a device raises a vectored interrupt, the CPU does polling to identify the source of interrupt.
III. In polling,the CPU periodically checks the status bits to know if any device needs its attention.
IV. During DMA, both the CPU and DMA controller can be bus masters at the same time.

Which of the above statements is/are TRUE?
A
I and II only
B
I and IV only
C
I and III only
D
III only
Computer Organization   Interrupt
Question 4
Consider the following data path diagram.

Consider an instruction: R0\leftarrow R1+R2. The following steps are used to execute it over the given data path. Assume that PC is incremented appropriately. The subscripts r and w indicate read and write operations, respectively.

1. \; R2_r,TEMP1_r,ALU_{add},TEMP2_w
2. \; R1_r,TEMP1_w
3. \; PC_r,MAR_w,MEM_r
4. \; TEMP2_r,R0_w
5. \; MDR_r,IR_w

Which one of the following is the correct order of execution of the above steps?
A
2,1,4,5,3
B
1,2,4,3,5
C
3,5,2,1,4
D
3,5,1,2,4
Computer Organization   Machine Instruction
Question 5
The preorder traversal of a binary search tree is 15,10,12,11,20,18,16,19. Which one of the following is the postorder traversal of the tree?
A
10,11,12,15,16,18,19,20
B
11,12,10,16,19,18,20,15
C
20,19,18,16,15,12,11,10
D
19,16,18,20,11,12,10,15
Data Structure   Binary Search Tree
Question 6
What is the worst case time complexity of inserting n^2 elements into an AVL-tree with n elements initially?
A
\Theta (n^4)
B
\Theta (n^2)
C
\Theta (n^2 \log n)
D
\Theta (n^3)
Data Structure   AVL Tree
Question 7
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
A
((0+1)^* 1(0+1)^*1)^*10^*
B
(0^*10^*10^*)^*0^*1
C
10^*(0^*10^*10^*)^*
D
(0^*10^*10^*)^*10^*
Theory of Computation   Regular Expression
Question 8
Consider the following statements.

I. If L_1\cup L_2 is regular, then both L_1 \; and \; L_2 must be regular.
II. The class of regular languages is closed under infinite union.

Which of the above statements is/are TRUE?
A
I only
B
II only
C
Both I and II
D
Neither I nor II
Theory of Computation   Regular Language
Question 9
Consider the following statements.

I. Symbol table is accessed only during lexical analysis and syntax analysis.
II. Compilers for programming languages that support recursion necessarily need heap storage for memory allocation in the run-time environment.
III. Errors violating the condition 'any variable must be declared before its use' are detected during syntax analysis.

Which of the above statements is/are TRUE?
A
I only
B
I and III only
C
II only
D
None of I, II and III
Compiler Design   Lexical Analysis
Question 10
Consider the language L=\{a^n|n\geq 0\}\cup \{a^nb^n|n\geq 0\} and the following statements.

I. L is deterministic context-free.
II. L is context-free but not deterministic context-free.
III. L is not LL(k) for any k.

Which of the above statements is/are TRUE?
A
I only
B
II only
C
I and III only
D
III only
Theory of Computation   Context Free Language
There are 10 questions to complete.

Leave a Comment