Arrays/Stacks/Queues

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 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 an array X that contains n positive integers. A subarray of X is defined to be a sequence of array locations with consecutive indices. The C code snippet given below has been written to compute the length of the longest subarray of X that contains at most two distinct integers. The code has two missing expressions labelled (P) and (Q).

int first=0, second=0, len1=0, len2=0, maxlen=0;
for (int i=0; i < n; i++) {
  if (X[i] == first) {
    len2++; len1++;
  } else if (X[i] == second) {
    len2++;
    len1 = (P);
    second = first;
  } else {
    len2 = (Q);
    len1 = 1; second = first;
  }
  if (len2 > maxlen) {
    maxlen = len2;
  }
  first = X[i];
}

Which one of the following options gives the CORRECT missing expressions? (Hint: At the end of the i-th iteration, the value of len1 is the length of the longest subarray ending with X[i] that contains all equal values, and len2 is the length of the longest subarray ending with X[i] that contains at most two distinct values.)

Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400, whereas S2 is empty, as shown below. Only the following three operations are available: PushToS2: Pop the top element from S1 and push it on S2. PushToS1: Pop the top element from S2 and push it on S1. GenerateOutput: Pop the top element from S1 and output it to the user. Note that the pop operation is not allowed on an empty stack and the push operation is not allowed on a full stack. Which of the following output sequences can be generated by using the above operations?

Consider a sequence $a$ of elements $a_0 = 1, a_1 = 5, a_2 = 7, a_3 = 8, a_4 = 9$, and $a_5 = 2$. The following operations are performed on a stack $S$ and a queue $Q$, both of which are initially empty. I: push the elements of $a$ from $a_0$ to $a_5$ in that order into $S$. II: enqueue the elements of $a$ from $a_0$ to $a_5$ in that order into $Q$. III: pop an element from $S$. IV: dequeue an element from $Q$. V: pop an element from $S$. VI: dequeue an element from $Q$. VII: dequeue an element from $Q$ and push the same element into $S$. VIII: Repeat operation VII three times. IX: pop an element from $S$. X: pop an element from $S$. The top element of $S$ after executing the above operations is __________

What is printed by the following ANSI C program?

#include<stdio.h>
int main(int argc, char *argv[])
{
  int a[3][3][3] =
  {{1, 2, 3, 4, 5, 6, 7, 8, 9},
   {10, 11, 12, 13, 14, 15, 16, 17, 18},
   {19, 20, 21, 22, 23, 24, 25, 26, 27}};
  int i = 0, j = 0, k = 0;
  for( i = 0; i < 3; i++ ){
    for(k = 0; k < 3; k++ )
      printf("%d ", a[i][j][k]);
    printf("\n");
  }
  return 0;
}

Consider the queues $Q_1$ containing four elements and $Q_2$ containing none (shown as the Initial State in the figure). The only operations allowed on these two queues are Enqueue(Q, element) and Dequeue(Q). The minimum number of Enqueue operations on $Q_1$ required to place the elements of $Q_1$ in $Q_2$ in reverse order (shown as the Final State in the figure) without using any additional storage is __________

Consider the following C program:

#include <stdio.h>
int main()
{
    int a[] = {2, 4, 6, 8, 10};
    int i, sum = 0, *b = a + 4;
    for (i = 0; i < 5; i++)
        sum = sum + (*b - i) - *(b - i);
    printf ("%d\n", sum);
    return 0;
}

The output of the above C program is _____.

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 ________.

An algorithm performs $(\log N)^{1/2}$ find operations, $N$ insert operations, $(\log N)^{1/2}$ delete operations, and $(\log N)^{1/2}$ decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

What is the output of the following C code? Assume that the address of x is 2000 (in decimal) and an integer requires four bytes of memory.

int main () {
    unsigned int x[4][3] =
        {{1,2,3},{4,5,6},{7,8,9},{10,11,12}};
    printf("%u, %u, %u", x+3, *(x+3), *(x+2)+3);
}

A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with $\infty$, and hence there cannot be any entry to the right of, or below a $\infty$. The following Young tableau consists of unique entries. $$\begin{array}{|c|c|c|c|} \hline 1 & 2 & 5 & 14 \\ \hline 3 & 4 & 6 & 23 \\ \hline 10 & 12 & 18 & 25 \\ \hline 31 & \infty & \infty & \infty \\ \hline \end{array}$$ When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a $\infty$). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is _____.

Consider the C program below.

#include <stdio.h>
int *A, stkTop;

int stkFunc(int opcode, int val)
{
    static int size=0, stkTop=0;

    switch (opcode) {
        case -1: size = val; break;
        case  0: if (stkTop < size) A[stkTop++] = val; break;
        default: if (stkTop) return A[--stkTop];
    }
    return -1;
}

int main()
{
    int B[20]; A = B; stkTop = -1;

    stkFunc (-1, 10);
    stkFunc ( 0, 5);
    stkFunc ( 0, 10);
    printf ("%d\n", stkFunc(1, 0) + stkFunc(1, 0));
}

The value printed by the above program is _____.

Consider the following C program.

#include<stdio.h>
int main( )
{
    static int a[ ] = {10, 20, 30, 40, 50};
    static int *p[ ] = {a, a+3, a+4, a+1, a+2};
    int **ptr = p;
    ptr++;
    printf("%d%d", ptr-p, **ptr);
}

The output of the program is _____.

Consider the following two C code segments. Y and X are one and two dimensional arrays of size $n$ and $n \times n$ respectively, where $2 \leq n \leq 10$. Assume that in both code segments, elements of Y are initialized to 0 and each element X[i][j] of array X is initialized to i+j. Further assume that when stored in main memory all elements of X are in same main memory page frame.

Code segment 1:
    //initialize elements of Y to 0
    //initialize elements X[i][j] of X to i+j
    for(i = 0; i < n; i++)
        Y[i] += X[0][i];

Code Segment 2:
    //initialize elements of Y to 0
    //initialize elements X[i][j] of X to i+j
    for(i = 0; i < n; i++)
        Y[i] += X[i][0];

Which of the following statements is/are correct? S1: Final contents of array Y will be same in both code segments S2: Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main memory S3: Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main memory

Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

Consider the following operation along with Enqueue and Dequeue operations on queues, where $k$ is a global parameter.

MultiDequeue(Q){
    m = k
    while (Q is not empty) and (m > 0) {
        Dequeue(Q)
        m = m - 1
    }
}

What is the worst case time complexity of a sequence of $n$ queue operations on an initially empty queue?

Suppose a circular queue of capacity $(n - 1)$ elements is implemented with an array of $n$ elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are