GATE CSE 2020
Q21.
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is ___________.Q22.
If there are m input lines and n output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of m+n is ________ .Q23.
A multiplexer is placed between a group of 32 registers and an accumulator to regulate data movement such that at any given point in time the content of only one register will move to the accumulator. The number of select lines needed for the multiplexer is ______.Q24.
Consider the productions A\rightarrow PQ and A\rightarrow XY. Each of the five non-terminals A,P,Q,X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules.Rule 1: P.i=A.i+2, Q.i=P.i+A.i, and A.s=P.s+Q.sRule 2: X.i=A.i+Y.s and Y.i=X.s+A.iWhich one of the following is TRUE?Q25.
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?Q26.
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?Q27.
What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?Q28.
Let A and B be two nxn matrices over real numbers. Let rank(M) and det(M) denote the rank and determinant of a matrix M, respectively. Consider the following statements. I. rank(AB)=rank (A)rank (B) II. det(AB)=det(A)det(B) III. rank(A+B) \leq rank (A) + rank (B) IV. det(A+B) \leq det(A) + det(B) Which of the above statements are TRUE?Q29.
Consider a paging system that uses 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns and TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before the required page is read from disk. TLB update time is negligible. The average memory access time in ns (round off to 1 decimal places) is ___________Q30.
Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process's memory requirement. Hence, a new hole of smaller size will be created if allocation is made in any of the existing holes. Which one of the following statement is TRUE?