GATE CSE 2021 SET-2
Q21.
Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter. Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string?Q22.
Which one of the following circuits implements the Boolean function given below?f(x,y,z) = m_0+m_1+m_3+m_4+m_5+m_6where m_i is the i^{th} minterm.Q23.
In the context of compilers, which of the following is/are NOT an intermediate representation of the source program?Q24.
Consider a computer system with DMA support. The DMA module is transferring one 8-bit character in one CPU cycle from a device to memory through cycle stealing at regular intervals. Consider a 2 MHz processor. If 0.5% processor cycles are used for DMA, the data transfer rate of the device is __________ bits per second.Q25.
Consider the following ANSI C program:#include < stdio.h > #include < stdlib.h > struct Node{ int value; struct Node *next;}; int main( ) { struct Node *boxE, *head, *boxN; int index=0; boxE=head= (struct Node *) malloc(sizeof(struct Node)); head -> value = index; for (index =1; index < = 3; index++){ boxN = (struct Node *) malloc (sizeof(struct Node)); boxE -> next = boxN; boxN -> value = index; boxE = boxN; } for (index=0; index < = 3; index++) { printf("Value at index %d is %d\n", index, head -> value); head = head -> next; printf("Value at index %d is %d\n", index+1, head -> value); } } Which one of the following statements below is correct about the program?Q26.
Suppose that P is a 4x5 matrix such that every solution of the equation Px=0 is a scalar multiple of \begin{bmatrix} 2 & 5 & 4 &3 & 1 \end{bmatrix}^T. The rank of P is _______Q27.
Consider a three-level page table to translate a 39-bit virtual address to a physical address as shown below: The page size is 4 KB = (1KB =2^{10} bytes) and page table entry size at every level is 8 bytes. A process P is currently using 2 GB (1 GB =2^{30} bytes) virtual memory which os mapped to 2 GB of physical memory. The minimum amount of memory required for the page table of P across all levels is _________ KBQ28.
Let G be a connected undirected weighted graph. Consider the following two statements. S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G. S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree. Which one of the following options is correct?Q29.
Consider the following deterministic finite automaton (DFA)The number of strings of length 8 accepted by the above automaton is _________Q30.
Suppose we want to design a synchronous circuit that processes a string of 0's and 1's. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1's by a 0. Consider the following example. \begin{array}{ll} \text{Input sequence:} & 00100011000011100 \\ \text{Output sequence:} & 00000001000001100 \end{array} A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input. The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables s, t, b and y respectively. Assume the initial state of the Mealy machine is 0. What are the Boolean expressions corresponding to t and y in terms of s and b?