GATE CS question library

​Consider the following logic circuit diagram. Which is/are the CORRECT option(s) for the output function $F$ ?

The following two signed $2$ 's complement numbers (multiplicand M and multiplier Q) are being multiplied using Booth's algorithm: M: $1100110111101101$ and Q: $1010010010101010$ The total number of addition and subtraction operations to be performed is_____________. (Answer in integer)

int x=126,y=105; do { if(x>y) x=x-y; else y=y-x; } while(x!=y); printf("%d",x); The output of the given C code segment is _________. (Answer in integer)

In a $4$-bit ripple counter, if the period of the waveform at the last flip-flop is $64$ microseconds, then the frequency of the ripple counter in kHz is _________. (Answer in integer)

Suppose the values $10,-4,15,30,20,5,60,19$ are inserted in that order into an initially empty binary search tree. Let $T$ be the resulting binary search tree. The number of edges in the path from the node containing $19$ to the root node of $T$ is _________. (Answer in integer)

​​​​Suppose we are transmitting frames between two nodes using Stop-and-Wait protocol. The frame size is $3000$ bits. The transmission rate of the channel is $2000$ bps (bits/second) and the propagation delay between the two nodes is $100$ milliseconds. Assume that the processing times at the source and destination are negligible. Also, assume that the …

​​​​Let $\text{G}$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in $\text{G}$ before and after the edge weight update?

​A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures: P. Unsorted doubly linked list with pointers to the head node and tail node of the list. Q. Min-heap implemented using an array. R. Binary Search Tree. Which ONE of the following options gives the …

​​​​For a direct-mapped cache, $4$ bits are used for the tag field and $12$ bits are used to index into a cache block. The size of each cache block is one byte. Assume that there is no other information stored for each cache block. Which ONE of the following is the CORRECT option for the sizes of the main memory and the cache memory in this system (byte …

​​Given a Context-Free Grammar $\text{G}$ as follows: $$\begin{array}{l} S \rightarrow A a|b A c| d c \mid b d a \\ A \rightarrow d \end{array}$$ Which ONE of the following statements is TRUE?

​​An array $A$ of length $n$ with distinct elements is said to be bitonic if there is an index $1 \leq i \leq n$ such that $A[1 . . i]$ is sorted in the non-decreasing order and $A[i+1 \ldots n]$ is sorted in the non-increasing order. Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons …

​​Let $\mathcal{F}$ be the set of all functions from $\{1, \ldots, n\}$ to $\{0,1\}$. Define the binary relation $\leqslant$ on $\mathcal{F}$ as follows: $\forall f, g \in \mathcal{F}, f \preccurlyeq g$ if and only if $\forall x \in\{1, \ldots, n\}, f(x) \leq g(x)$, where $0 \leq 1$. Which of the following statement(s) is/are TRUE?

​​​​Given the following Karnaugh Map for a Boolean function $F(w, x, y, z)$ : Which one or more of the following Boolean expression(s) represent(s) $F$ ?

​​​Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct. We wish to augment the stack data structure with an $O(1)$ time MIN operation that returns a pointer to the record with smallest key present in the stack without deleting the …

Consider a system of linear equations $P X=Q$ where $P \in \mathbb{R}^{3 \times 3}$ and $\mathrm{Q} \in \mathbb{R}^{3 \times 1}$. Suppose $P$ has an LU decomposition, $P=L U$, where …

​​​​Consider the following relational schema along with all the functional dependencies that hold on them. $$\begin{array}{l} R 1(A, B, C, D, E):\{D \rightarrow E, E A \rightarrow B, E B \rightarrow C\} \\ R 2(A, B, C, D):\{A \rightarrow D, A \rightarrow B, C \rightarrow A\} \end{array}$$ Which of the following statement(s) is/are TRUE?

​Consider a demand paging system with three frames, and the following page reference string: 1 2 3 4 5 4 1 6 4 5 1 3 2 . The contents of the frames are as follows initially and after each reference (from left to right): …

$P=\left\{P_{1}, P_{2}, P_{3}, P_{4}\right\}$ consists of all active processes in an operating system. $R=\left\{R_{1}, R_{2}, R_{3}, R_{4}\right\}$ consists of single instances of distinct types of resources in the system. The resource allocation graph has the following assignment and claim edges. Assignment edges: …

Three floating point numbers $X, Y$, and $Z$ are stored in three registers $\mathrm{R}_{\mathrm{X}}, \mathrm{R}_{\mathrm{Y}}$, and $\mathrm{R}_{\mathrm{Z}}$, respectively in $IEEE$ $754$ single precision format as given below in hexadecimal: …

Which of the following Boolean algebraic equation(s) is/are CORRECT?