GATE CS question library

Consider the process of inserting an element into a $\text{Max Heap}$, where the $\text{Max Heap}$ is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:

Consider the following C program segment where $\text{CellNode}$ represents a node in a binary tree: struct CellNode { struct CellNode *leftChild; int element; struct CellNode *rightChild; }; int Getvalue (struct CellNode *ptr) { int value = 0; if (ptr != NULL) { if ((ptr->leftChild == NULL) && (ptr->rightChild == NULL)) value = 1; else value …

What is the $\text{time complexity}$ of the following recursive function? int DoSomething (int n) { if (n <= 2) return 1; else return (DoSomething (floor (sqrt(n))) + n); }

In the following C function, let $n \geq m$. int gcd(n,m) { if (n%m == 0) return m; n = n%m; return gcd(m,n); } How many recursive calls are made by this function?

A complete $n-ary$ tree is a tree in which each node has $n$ children or no children. Let $I$ be the number of internal nodes and $L$ be the number of leaves in a complete $n-ary$ tree. If $L = 41$ and $I = 10$, what is the value of $n$?

Consider the following C function: int f(int n) { static int r = 0; if (n <= 0) return 1; if (n > 3) { r = n; return f(n-2) + 2; } return f(n-1) + r; } What is the value of $f(5)$?

Consider a hash table of size seven, with starting index zero, and a hash function $(3x + 4)\mod 7$. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence $1, 3, 8, 10$ is inserted into the table using closed hashing? Note that − denotes an empty location in the table.

The inorder and preorder traversal of a binary tree are $\text{d b e a f c g}$ and $\text{a b d e c f g}$, respectively The postorder traversal of the binary tree is:

In an unweighted, undirected connected graph, the shortest path from a node $S$ to every other node is computed most efficiently, in terms of time complexity, by

Consider a pipelined processor with the following four stages: IF: Instruction Fetch ID: Instruction Decode and Operand Fetch EX: Execute WB: Write Back The IF, ID and WB stages take one clock cycle each to complete the operation. The number of clock cycles for the EX stage depends on the instruction. The ADD and SUB instructions need $1$ clock cycle and …

The control signal functions of a $4$-$bit$ binary counter are given below (where $X$ is “don’t care”): …

In a look-ahead carry generator, the carry generate function $G_i$ and the carry propagate function $P_i$ for inputs $A_i$ and $B_i$ are given by: $$P_i = A_i \oplus B_i \text{ and }G_i = A_iB_i$$ The expressions for the sum bit $S_i$ and the carry bit $C_{i+1}$ of the look ahead carry adder are given by: …

Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of $n$ variables. What is the minimum size of the multiplexer needed?

Define the connective $*$ for the Boolean variables $X$ and $Y$ as: $$X * Y = XY + X'Y'.$$ Let $Z = X * Y$. Consider the following expressions $P$, $Q$ and $R$. $$P : X = Y * Z, \\ Q :Y = X * Z, \\ R : X *Y * Z = 1$$ Which of the following is TRUE?

Let $f(w, x, y, z) = \sum {\left(0,4,5,7,8,9,13,15\right)}$. Which of the following expressions are NOT equivalent to $f$? P: $x'y'z' + w'xy' + wy'z + xz$ Q: $w'y'z' + wx'y' + xz$ R: $w'y'z' + wx'y' + xyz+xy'z$ S: $x'y'z' + wx'y'+ w'y$

The language $L=\left\{0^i21^i \mid i \geq 0\right\}$ over the alphabet $\left\{0, 1, 2\right\}$ is:

Which of the following languages is regular?

A minimum state deterministic finite automaton accepting the language $L=\{w\mid w \in \{0, 1\}^*,$ number of $0$s and $1$s in $w$ are divisible by $3$ and $5$, respectively $\}$ has

Consider the set of (column) vectors defined by$$X = \left \{x \in R^3 \mid x_1 + x_2 + x_3 = 0, \text{ where } x^T = \left[x_1,x_2,x_3\right]^T\right \}$$.Which of the following is TRUE?

Consider the set $S =\{ a , b , c , d\}.$ Consider the following $4$ partitions $π_1,π_2,π_3,π_4$ on $S : π_1 =\{\overline{abcd}\},\quad π_2 =\{\overline{ab}, \overline{cd}\},$ $\quad π_3 = \{\overline{abc}, \overline{d}\},\quad π_4 =\{\bar{a}, \bar{b}, \bar{c}, \bar{d}\}$. Let $\prec$ be the partial order on the set of partitions …