All Programming & Data Structures questions

Let $n$ be an odd number greater than 100. Consider a binary minheap with $n$ elements stored in an array $P$ whose index starts from 1. Which of the following indices of $P$ do/does NOT correspond to any leaf node of the minheap?

Consider a hash table $P[0, 1, \ldots, 10]$ that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is $h(x) = (x + 7) \bmod 11$. Consider the following sequence of insertions performed on $P$: $$1, 13, 22, 15, 11, 24$$ Which of the following positions in the hash table is/are empty after these insertions are performed?

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is _________. (*answer in integer*)

Consider the following program in C:

#include <stdio.h>

void func(int i, int j) {
  if(i < j) {
    int i = 0;
    while (i < 10) {
      j += 2;
      i++;
    }
  }
  printf("%d", i);
}

int main() {
  int i = 9, j = 10;
  func(i, j);
  return 0;
}

The output of the program is _________. (*answer in integer*) *Note*: Assume that the program compiles and runs successfully.

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.

struct node{
  int elt;
  struct node *next;
};
int getListSize (struct node *head)
{
  if( E1 ) return 1;
  return E2;
}

Which one of the following options gives the correct replacements for the expressions E1 and E2?

Let $P$ be the set of all integers from 1 to 15. Consider any order of insertion of the elements of $P$ into a binary search tree that creates a complete binary tree. Which one of the following elements can NEVER be the third element that is inserted?

Consider the recursive functions represented by the following code segment:

int bar(int n){
     if (n == 1) return 0;
     else return 1 + bar(n/2);
}
int foo(int n){
     if (n == 1) return 1;
     else return 1 + foo(bar(n));
}

The smallest positive integer n for which foo(n) returns 5 is ______. (*answer in integer*) *Note:* Ignore syntax errors (if any) in the function.

The following sequence corresponds to the preorder traversal of a binary search tree $T$: $$50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77$$ The position of the element 60 in the postorder traversal of $T$ is ______. (*answer in integer*) *Note:* The position begins with 1.

The set T represents various traversals over binary tree. The set S represents the order of visiting nodes during a traversal.

T                   S
I:   Inorder        L: left subtree, node, right subtree
II:  Preorder       M: node, left subtree, right subtree
III: Postorder      N: left subtree, right subtree, node

Which one of the following is the correct match from T to S?

Consider the following three ANSI-C programs, P1, P2, and P3. P1

#include <stdio.h>
int a=5;
int main(){
  int a=7;
  return(0);
}

P2

#include <stdio.h>
int main(){
  int a=5;
  int a=7;
  return(0);
}

P3

#include <stdio.h>
int main(){
  int a=5;
  float a=7;
  return(0);
}

Which one of the following statements is true?

The keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are inserted into a hash table using the hash function $h(k) = k \bmod 9$. The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is __________. (*answer in integer*)

Consider a binary search tree (BST) with $n$ leaf nodes ($n > 0$). Given any node $V$, the key present in the node is denoted as $Val(V)$. All the keys present in the given BST are distinct. The keys belong to the set of real numbers. For a node $V$, let $Suc(V)$ denote the node that is its inorder successor. If a node $V$ does not have an inorder successor, then $Suc(V)$ is $NULL$. As there are no duplicates, if $Suc(V)$ is not $NULL$, then $Val(V) < Val(Suc(V))$. Corresponding to every leaf node $L_i$ that has a non-NULL $Suc(L_i)$, a new key $k_i$ with the following property is to be inserted into the BST. $$Val(L_i) < k_i < Val(Suc(L_i))$$ Let $K$ represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?

Consider a stack $S$ and a queue $Q$. Both of them are initially empty and have the capacity to store ten elements each. The elements 1, 2, 3, 4, and 5 arrive one by one, in that order. When an element arrives, it is assigned either to $S$ (pushed on $S$) or to $Q$ (enqueued to $Q$). Once all the five elements are stored, the output is generated in two steps. First, stack $S$ is emptied by popping all elements. Then queue $Q$ is emptied by dequeueing all elements. The output obtained by following this process is 4 3 1 2 5. Given the output, the objective is to predict whether an element was assigned to $S$ or $Q$. Which of the following options is/are possible valid assignment(s) of the elements? *Note:* In the options, the notation $xS$ denotes that element $x$ was assigned to $S$ and $yQ$ denotes that element $y$ was assigned to $Q$.

Consider the following ANSI-C program.

#include <stdio.h>
int main(){
  int *ptr, a, b, c;
  a=5; b=11; c=20;
  ptr=&a; *ptr=c; ptr=&c;
  a=*(&b); c=*ptr-a;
  printf("%d",c);
  return(0);
}

The output of this program is ____________. (*answer in integer*) *Note*: Assume that the program compiles and runs successfully.

Consider the following ANSI-C function.

int func(int start, int end){
  int length=end+1-start;
  if((length<1)||(start<0)||(end<0)){ return(0); }
  if(length%3==0){
    return(func(start+1, end));
  } else if(length%3==1){
    return(1+func(start, end-1));
  } else {
    return(func(start+2, end));
  }
}

The maximum possible value that can be returned from this function is ____________. (*answer in integer*) *Note*: Ignore syntax errors (if any) in the function.

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;
}