All Programming & Data Structures questions

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?

What is the worst case time complexity of inserting $n^2$ elements into an AVL-tree with $n$ elements initially?

What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?

Consider the following C program.

#include <stdio.h>
int main() {
    int a[4][5]={{1, 2, 3, 4, 5},
                 {6, 7, 8, 9, 10},
                 {11, 12, 13, 14, 15},
                 {16, 17, 18 , 19, 20}};
    printf("%d\n", *(*(a+**a+2)+3));
    return(0);
}

The output of the program is ___________.

Consider a double hashing scheme in which the primary hash function is $h_1(k) = k \bmod 23$, and the secondary hash function is $h_2(k) = 1 + (k \bmod 19)$. Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value $k = 90$ is ____________.

In a balanced binary search tree with $n$ elements, what is the worst case time complexity of reporting all elements in range $[a, b]$? Assume that the number of reported elements is $k$.

Consider the following C functions.

int fun1(int n) {               int fun2(int n) {
  static int i = 0;                static int i = 0;
  if (n > 0) {                     if (n > 0) {
     ++i;                             i = i + fun1(n);
     fun1(n-1);                       fun2(n-1);
  }                                }
  return(i);                       return(i);
}                                }

The return value of fun2(5) is __________.

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is __________.

Consider the following C functions.

int tob(int b, int* arr){          int pp(int a,int b) {
   int i;                              int arr[20];
   for(i=0; b>0; i++){                 int i, tot = 1, ex, len;
      if(b%2) arr[i]=1;                ex = a;
      else    arr[i]=0;                len = tob(b,arr);
      b = b/2;                         for(i=0; i<len; i++){
   }                                      if(arr[i]==1)
   return(i);                                tot = tot * ex;
}                                         ex = ex * ex;
                                       }
                                       return(tot);
                                    }

The value returned by pp(3,4) is ____________.