GATE CSE 2020

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] ?

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

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?

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?

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?

What is the worst case time complexity of inserting n^2 elements into an AVL-tree with n elements initially?

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?

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?

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?

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?