All Programming & Data Structures questions

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?

#include <stdio.h>
void foo(int *p, int x){
    *p=x;
}
int main(){
    int *z;
    int a = 20, b = 25;
    z = &a;
    foo(z,b);
    printf("%d",a);
    return 0;
}

The output of the given C program is __________. (Answer in integer)

The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node. Suppose a Min-Heap $T$ stores 32 keys. The height of $T$ is _____________. (Answer in integer)

#include <stdio.h>
int foo(int S[],int size){
    if(size == 0) return 0;
    if(size == 1) return 1;
    if(S[0] != S[1]) return 1+foo(S+1,size-1);
    return foo(S+1,size-1);
}
int main(){
    int A[]={0,1,2,2,2,0,0,1,1};
    printf("%d",foo(A,9));
    return 0;
}

The value printed by the given C program is _______. (Answer in integer)

Let LIST be a datatype for an implementation of linked list defined as follows:

typedef struct list {
    int data;
    struct list *next;
} LIST;

Suppose a program has created two linked lists, L1 and L2, whose contents are given in the figure below (code for creating L1 and L2 is not provided here). L1 contains 9 nodes, and L2 contains 7 nodes.

L1: 1 -> 7 -> 12 -> 3 -> 9 -> 5 -> 11 -> 15 -> 8 -> NULL
L2: 1 -> 11 -> 6 -> 9 -> 15 -> 12 -> 4 -> NULL

Consider the following C program segment that modifies the list L1. The number of nodes that will be there in L1 after the execution of the code segment is ________. (Answer in integer)

int find (int query, LIST *list) {
    while (list != NULL){
        if(list->data == query) return 1;
        list = list->next;
    }
    return 0;
}
int main () {
    … … …
    ptr1=L1; ptr2=L2;
    while (ptr1->next != NULL){
        query = ptr1->next->data;
        if (find (query, L2))
            ptr1->next = ptr1->next->next;
        else ptr1 = ptr1->next;
    }
    … … …
    return 0;
}

Consider the following C program:

#include <stdio.h>
int gate (int n) {
    int d, t, newnum, turn;
    newnum = turn = 0; t=1;
    while (n>=t) t *= 10;
    t /=10;
    while (t>0) {
        d = n/t;
        n = n%t;
        t /= 10;
        if (turn) newnum = 10*newnum + d;
        turn = (turn + 1) % 2;
    }
    return newnum;
}
int main () {
    printf ("%d", gate(14362));
    return 0;
}

The value printed by the given C program is _______. (Answer in integer)

In a double hashing scheme, $h_1(k) = k \bmod 11$ and $h_2(k) = 1 + (k \bmod 7)$ are the auxiliary hash functions. The size $m$ of the hash table is 11. The hash function for the $i$-th probe in the open address table is $[h_1(k) + i\, h_2(k)] \bmod m$. The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24. The slot at which key 24 gets stored is ___________. (Answer in integer)

Consider a binary tree $T$ in which every node has either zero or two children. Let $n > 0$ be the number of nodes in $T$. Which ONE of the following is the number of nodes in $T$ that have exactly two children?

Consider the following C program:

#include <stdio.h>
void stringcopy(char *, char *);
int main(){
  char a[30] = "@#Hello World!";
  stringcopy(a, a + 2);
  printf("%s\n", a);
  return 0;
}
void stringcopy(char *s, char *t) {
  while(*t)
    *s++ = *t++;
}

Which ONE of the following will be the output of the program?

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)

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)

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 worst-case time complexities for meld operation on instances of size $n$ of these data structures?

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 1) without deleting the corresponding record, and 2) without increasing the complexities of the standard stack operations. Which one or more of the following approach(es) can achieve it?

Consider the following C program:

#include <stdio.h>
int main(){
  int a;
  int arr[5] = {30,50,10};
  int *ptr;
  ptr = &arr[0] + 1;
  a = *ptr;
  (*ptr)++;
  ptr++;
  printf("%d", a + (*ptr) + arr[1]);
  return 0;
}

The output of the above program is ___________. (Answer in integer)

Consider the following C program:

#include <stdio.h>

int g(int n) {
    return (n+10);
}

int f(int n) {
    return g(n*2);
}

int main() {
    int sum, n;
    sum=0;
    for (n=1; n<3; n++)
        sum += g(f(n));
    printf ("%d", sum);
    return 0;
}

The output of the given C program is ________. (Answer in integer)