GATE CS Programming and Data Structures questions

​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 …

​​​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 the following $\mathrm{C}$ program: #include <stdio.h> int main() { int a=6; int b = 0; while (a<10) { a = a / 12+1 ; a += b ;} printf ("%d", a); return 0 ; } Which one of the following statements is CORRECT?

​​​Consider the following $\mathrm{C}$ program: #include <stdio.h> void fX (); int main(){ fX(); return 0 }; void fX () { char a; if ((a=g e t c h a r()) ! = '\n') fX(); if (a ! = '\n') putchar (a); } Assume that the input to the program from the command line is $1234$ followed by a newline character. Which one of the following statements is …

Consider a binary min-heap containing $105$ distinct elements. Let $k$ be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of $k$ is

​​Consider the following $\mathrm{C}$ function definition. int f (int x, int y){ for (int i=0 ; i<y ; i++ ) { x= x + x + y; } return x; } Which of the following statements is/are TRUE about the above function?

Consider the following $\text{C}$ program. Assume parameters to a function are evaluated from right to left. #include <stdio.h> int g(int p) { printf("%d", p); return p; } int h(int q) { printf("%d", q); return q; } void f(int x, int y) { g(x); h(y); } int main() { f(g(10), h(20)); } Which one of the following options is the CORRECT output of the …

​​​Consider the following $\mathrm{C}$ function definition. int fX(char *a) { char *b = a; while (*b) b++; return b - a; } Which of the following statements is/are TRUE?

​​​​​What is the output of the following $\text{C}$ program? #include <stdio.h> int main() { double a[2]={20.0,25.0},* p,* q; p=a ; q=p+1 ; printf("%d,%d", (int) (q-p),( int)(* q- * p)); return 0;}

​​​​​​You are given a set $V$ of distinct integers. A binary search tree $T$ is created by inserting all elements of $V$ one by one, starting with an empty tree. The tree $T$ follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in …

​​​​​Let $\mathrm{S} 1$ and $\mathrm{S} 2$ be two stacks. $\mathrm{S} 1$ has capacity of $4$ elements. $\mathrm{S} 2$ has capacity of $2$ elements. $\text{S1}$ already has $4$ elements: $100,200,300$, and $400$, whereas $\text{S2}$ is empty, as shown below. …

Which one of the following sequences when stored in an array at locations $A[1], \ldots, A[10]$ forms a max-heap?

Let $\textsf{SLLdel}$ be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let $\textsf{DLLdel}$ be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let $n$ denote the number of nodes in each …

The integer value printed by the $\textsf{ANSI-C}$ program given below is _______________ #include<stdio.h> int funcp(){ static int x = 1; x++; return x; } int main(){ int x,y; x = funcp(); y = funcp()+x; printf("%d\n", (x+y)); return 0; }

Let $A$ be a priority queue for maintaining a set of elements. Suppose $A$ is implemented using a max-heap data structure. The operation $\text{EXTRACT-MAX} (A)$ extracts and deletes the maximum element from $A$. The operation $\operatorname{INSERT}(A, key )$ inserts a new element $key$ in $A$. The properties of a max-heap are preserved at the …

Consider the $\text{C}$ function $\text{foo}$ and the binary tree shown. typedef struct node { int val; struct node *left, *right; } node; int foo(node *p) { int retval; if (p == NULL) return 0; else { retval = p->val + foo(p->left) + foo(p->right); printf("%d ", retval); return retval; } } When $\textsf{foo}$ is called with a pointer to the …

Consider a sequence $a$ of elements $a_{0}=1, a_{1}=5, a_{2}=7, a_{3}=8, a_{4}=9$, and $a_{5}=2$. The following operations are performed on a stack $S$ and a queue $Q,$ both of which are initially empty. $\textsf{push}$ the elements of $a$ from $a_{0}$ to $a_{5}$ in that order into $S$. $\textsf{enqueue}$ the elements of $a$ from …

Consider the problem of reversing a singly linked list. To take an example, given the linked list below, the reversed linked list should look like Which one of the following statements is $\text{TRUE}$ about the time complexity of algorithms that solve the above problem in $O(1)$ space?

What is printed by the following $\text{ANSI C}$ program? #include<stdio.h> int main(int argc, char *argv[]) { int x = 1, z[2] = {10, 11}; int *p = NULL; p = &x; *p = 10; p = &z[1]; *(&z[0] + 1) += 3; printf(“%d, %d, %d\n”, x, z[0], z[1]); return 0; }

Suppose a binary search tree with $1000$ distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with $0,$ the $3^{\text{rd}}$ largest element of the tree is stored at index ______________ .