GATE CS Programming and Data Structures questions

A complete binary min-heap is made by including each integer in $[1, 1023]$ exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth $0$. The maximum depth at which integer $9$ can appear is _________.

The following function computes $X^{Y}$ for positive integers $X$ and $Y$. int exp (int X, int Y) { int res =1, a = X, b = Y; while (b != 0) { if (b % 2 == 0) {a = a * a; b = b/2; } else {res = res * a; b = b - 1; } } return res; } Which one of the following conditions is TRUE before every iteration of the loop?

The value printed by the following program is _______. void f (int * p, int m) { m = m + 5; *p = *p + m; return; } void main () { int i=5, j=10; f (&i, j); printf ("%d", i+j); }

$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: $\Theta \left(N\right)$ delete, …

What is the output of the following C code? Assume that the address of $x$ is $2000$ (in decimal) and an integer requires four bytes of memory. int main () { unsigned int x [4] [3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}}; printf ("%u, %u, %u", x + 3, *(x + 3), *(x + 2) + 3); }

Consider the following pseudo code, where $x$ and $y$ are positive integers. begin q := 0 r := x while r ≥ y do begin r := r - y q := q + 1 end end The post condition that needs to be satisfied after the program terminates is

Consider a max heap, represented by the array: $40, 30, 20, 10, 15, 16, 17, 8, 4$. …

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height $5$ are

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

The output of the following C program is_____________. void f1 ( int a, int b) { int c; c = a; a = b; b = c; } void f2 ( int * a, int * b) { int c; c = * a; *a = *b; *b = c; } int main () { int a = 4, b = 5, c = 6; f1 ( a, b); f2 (&b, &c); printf ("%d", c - a - b); }

Which of the following is/are correct in order traversal sequence(s) of binary search tree(s)? $3, 5, 7, 8, 15, 19, 25$ $5, 8, 9, 12, 10, 15, 25$ $2, 7, 10, 8, 14, 16, 20$ $4, 6, 7, 9, 18, 20, 25$

Consider the C program below #include <stdio.h> int *A, stkTop; int stkFunc (int opcode, int val) { static int size=0, stkTop=0; switch (opcode) { case -1: size = val; break; case 0: if (stkTop < size ) A[stkTop++]=val; break; default: if (stkTop) return A[--stkTop]; } return -1; } int main() { int B[20]; A=B; stkTop = -1; stkFunc (-1, 10); stkFunc …

Which one of the following hash functions on integers will distribute keys most uniformly over $10$ buckets numbered $0$ to $9$ for $i$ ranging from $0$ to $2020$?

A Young tableau is a $2D$ array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with $\infty$, and hence there cannot be any entry to the right of, or below a $\infty$. The following Young tableau consists of unique entries. …

Consider a complete binary tree where the left and right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

Consider the following function written in the C programming langauge : void foo(char *a) { if (*a && *a != ' ') { foo(a+1); putchar(*a); } } The output of the above function on input "$ABCD \ EFGH$" is

A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.

Consider the following C program: #include<stdio.h> int f1(void); int f2(void); int f3(void); int x=10; int main() { int x=1; x += f1() + f2 () + f3() + f2(); printf("%d", x); return 0; } int f1() { int x = 25; x++; return x;} int f2() { static int x = 50; x++; return x;} int f3() { x *= 10; return x;} The output of the program is ______.

Consider the following C program: #include<stdio.h> int main() { int i, j, k = 0; j=2 * 3 / 4 + 2.0 / 5 + 8 / 5; k-=--j; for (i=0; i<5; i++) { switch(i+k) { case 1: case 2: printf("\n%d", i+k); case 3: printf("\n%d", i+k); default: printf("\n%d", i+k); } } return 0; } The number of times printf statement is executed is _______.

Consider the following two C code segments. $Y$ and $X$ are one and two dimensional arrays of size $n$ and $n \times n$ respectively, where $2 \leq n \leq 10$. Assume that in both code segments, elements of $Y$ are initialized to $0$ and each element $X[i][j]$ of array $X$ is initialized to $i+j$. Further assume that when stored in main …