All Programming & Data Structures questions

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT ($n$ refers to the number of items in the queue)?

Consider the following C program.

void f(int, short);
void main()
{
     int i = 100;
     short s = 12;
     short *p = &s;
     __________ ;    // call to f()
}

Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?

Consider the following C program.

#include<stdio.h>

void mystery(int *ptra, int *ptrb) {
     int *temp;
     temp = ptrb;
     ptrb = ptra;
     ptra = temp;
}
int main() {
     int a=2016, b=0, c=4, d=42;
     mystery(&a, &b);
     if (a < c)
          mystery(&c, &a);
     mystery(&a, &d);
     printf("%d\n", a);
}

The output of the program is ________.

The following function computes the maximum value contained in an integer array p[] of size n (n >= 1).

int max(int *p, int n) {
     int a=0, b=n-1;
     while (__________) {
          if (p[a] <= p[b]) { a = a+1; }
          else              { b = b-1; }
     }
     return p[a];
}

The missing loop condition is

What will be the output of the following C program?

void count(int n){
     static int d=1;
     printf("%d ", n);
     printf("%d ", d);
     d++;
     if(n>1) count(n-1);
     printf("%d ", d);
}
void main(){
     count(3);
}

An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?

Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns the element at the top of S without removing it from S. Consider the algorithm given below.

while Q is not Empty do
     if S is Empty OR Top(S) ≤ Head(Q) then
          x := Dequeue(Q);
          Push(S,x);
     else
          x := Pop(S);
          Enqueue(Q,x);
     end
end

The maximum possible number of iterations of the while loop in the algorithm is ________.

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n$-th vertex in this BFS traversal, then the maximum possible value of $n$ is ________.

The value printed by the following program is ________.

void f(int* p, int m){
    m = m + 5;
    *p = *p + m;
    return;
}
void main(){
    int i=5, j=10;
    f(&i, j);
    printf("%d", i+j);
}

$N$ items are stored in a sorted doubly linked list. For a *delete* operation, a pointer is provided to the record to be deleted. For a *decrease-key* operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: $\Theta(N)$ *delete*, $O(\log N)$ *insert*, $O(\log N)$ *find*, and $\Theta(N)$ *decrease-key*. What is the time complexity of all these operations put together?

A complete binary min-heap is made by including each integer in $[1, 1023]$ exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is ________.

The following function computes $X^Y$ for positive integers X and Y.

int exp(int X, int Y) {
    int res = 1, a = X, b = Y;

    while ( b != 0 ){
        if ( b%2 == 0) { a = a*a; b = b/2; }
        else           { res = res*a; b = b-1; }
    }
    return res;
}

Which one of the following conditions is TRUE before every iteration of the loop?

Consider the following New-order strategy for traversing a binary tree: • Visit the root; • Visit the right subtree using New-order; • Visit the left subtree using New-order; The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:

Consider the following program:

int f(int *p, int n)
{
    if (n <= 1) return 0;
    else return max(f(p+1,n-1),p[0]-p[1]);
}
int main()
{
    int a[] = {3,5,2,6,4};
    printf("%d", f(a,5));
}

*Note*: max(x,y) returns the maximum of x and y. The value printed by this program is ________.

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is ________. *Note: The height of a tree with a single node is 0.*