All Programming & Data Structures questions

A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$?

Consider the following sequence of operations on an empty stack. push(54); push(52); pop(); push(55); push(62); s = pop(); Consider the following sequence of operations on an empty queue. enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue(); The value of s + q is __________.

Consider the following ANSI C program.

#include <stdio.h>
int main()
{
    int i, j, count;
    count = 0;
    i = 0;
    for (j = -3; j <= 3; j++)
    {
        if ((j >= 0) && (i++))
            count = count + j;
    }
    count = count + i;
    printf("%d", count);
    return 0;
}

Which one of the following options is correct?

Consider a *dynamic* hashing approach for 4-bit integer keys: 1. There is a main hash table of size 4. 2. The 2 least significant bits of a key is used to index into the main hash table. 3. Initially, the main hash table entries are empty. 4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand. 5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees. 6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit. 7. A split is done only if it is needed, i.e., only when there is a collision. Consider the following state of the hash table (see figure). Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

Consider the following ANSI C function:

int SimpleFunction(int Y[], int n, int x)
{
  int total = Y[0], loopIndex;
  for (loopIndex = 1; loopIndex <= n - 1; loopIndex++)
       total = x * total + Y[loopIndex];
  return total;
}

Let Z be an array of 10 elements with Z[$i$]=1, for all $i$ such that $0 le i le 9$. The value returned by SimpleFunction(Z, 10, 2) is __________.

Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$?

Consider the following ANSI C program.

#include <stdio.h>
int main(){
  int arr[4][5];
  int i, j;
  for (i=0; i<4; i++){
    for (j=0; j<5; j++){
      arr[i][j] = 10*i + j;
    }
  }
  printf("%d", *(arr[1] + 9));
  return 0;
}

What is the output of the above program?

Consider a complete binary tree with 7 nodes. Let $A$ denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let $B$ denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root. The value of $|A - B|$ is __________.

Consider the following ANSI C function:

int SomeFunction(int x, int y)
{
  if ((x == 1) || (y == 1)) return 1;
  if (x == y) return x;
  if (x > y) return SomeFunction(x - y, y);
  if (y > x) return SomeFunction(x, y - x);
}

The value returned by SomeFunction(15, 255) is __________.

Consider the following ANSI C program:

#include <stdio.h>
#include <stdlib.h>
struct Node{
        int value;
        struct Node *next;};
int main(){
    struct Node *boxE, *head, *boxN; int index = 0;
    boxE = head = (struct Node *) malloc(sizeof(struct Node));
    head->value = index;
    for (index = 1; index <= 3; index++){
        boxN = (struct Node *) malloc(sizeof(struct Node));
        boxE->next = boxN;
        boxN->value = index;
        boxE = boxN; }
    for (index = 0; index <= 3; index++) {
        printf("Value at index %d is %d\n", index, head->value);
        head = head->next;
        printf("Value at index %d is %d\n", index+1, head->value); } }

Which one of the statements below is correct about the program?

Consider the following ANSI C program.

#include <stdio.h>

int foo(int x, int y, int q)
{
    if ((x <= 0) && (y <= 0))
        return q;
    if (x <= 0)
        return foo(x, y-q, q);
    if (y <= 0)
        return foo(x-q, y, q);
    return foo(x, y-q, q) + foo(x-q, y, q);
}

int main()
{
    int r = foo(15,15,10);
    printf("%d", r);
    return 0;
}

The output of the program upon execution is ________.