GATE CS question library

Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute $M_1 \times M_2$ will be

The elements $32, 15, 20, 30, 12, 25, 16,$ are inserted one by one in the given order into a maxHeap. The resultant maxHeap is

A circularly linked list is used to represent a Queue. A single variable $p$ is used to access the Queue. To which node should $p$ point such that both the operations $\text{enQueue}$ and $\text{deQueue}$ can be performed in constant time?

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely? preorder and postorder inorder and postorder preorder and inorder level order and postorder

It is desired to design an object-oriented employee record system for a company. Each employee has a name, unique id, and salary. Employees belong to different categories and their salary is determined by their category. The functions get name, getId and compute salary are required. Given the class hierarchy below, possible locations for these functions are: …

Consider the following C program segment: char p[20]; int i; char* s = "string"; int length = strlen(s); for(i = 0; i < length; i++) p[i] = s[length-i]; printf("%s", p); The output of the program is:

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let $n = d_1\, d_2\, \ldots\, d_m$. int n, rev; rev = 0; while(n > 0) { rev = rev * 10 + n%10; n = n/10; } The loop invariant condition at the end of the $i^{th}$ iteration is:

Consider the following C function: int f(int n) { static int i = 1; if(n >= 5) return n; n = n+i; i++; return f(n); } The value returned by $f(1)$ is:

The problem $\text{3-SAT}$ and $\text{2-SAT}$ are

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

What is the result of evaluating the following two expressions using three-digit floating point arithmetic with rounding? $(113. + -111.) + 7.51$ $113. + (-111. + 7.51)$

Let $A, B, C, D$ be $n \times n$ matrices, each with non-zero determinant. If $ABCD = I$, then $B^{-1}$ is

The number of different $n \times n$ symmetric matrices with each element being either 0 or 1 is: (Note: $\text{power} \left(2, X\right)$ is same as $2^X$)

If a fair coin is tossed four times. What is the probability that two heads and two tails will result?

Consider the binary relation: $S= \left\{\left(x, y\right) \mid y=x+1 \text{ and } x, y \in \left\{0, 1, 2\right\} \right\}$ The reflexive transitive closure is $S$ is

Identify the correct translation into logical notation of the following assertion. Some boys in the class are taller than all the girls Note: $\text{taller} (x, y)$ is true if $x$ is taller than $y$.

How many $8-bi$t characters can be transmitted per second over a $9600$ baud serial communication link using asynchronous mode of transmission with one start bit, eight data bits, two stop bits and one parity bit?

The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by

Which of the following addressing modes are suitable for program relocation at run time? Absolute addressing Based addressing Relative addressing Indirect addressing

If $73_x$ (in base-x number system) is equal to $54_y$ (in base $y$-number system), the possible values of $x$ and $y$ are