Test 1 - Programming and Data Structure | Computer Science

A data structure is required for storing a set of integers such that each of the following operations can be done in O (log n) time, where n is the number of elements in the set.
I. Deletion of the smallest element
II. Insertion of an element if it is not already present in the set
Which of the following data structures can be used for this purpose?

Let S be a stack of size n $\ge$1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m $\ge$1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

Consider the following C-function in which a [n] and b [m] are two sorted integer
arrays and c [n + m] be another integer array.

void xyz(int a[], int b[], int c[]) {
  int i, j, k;
  i = j = k = 0;
  while ((i < n) && (j < m))
    if (a[i] < b[j]) c[k++] = a[i++];
    else c[k++] = b[j++];
}

Which of the following condition(s) hold(s) after the termination of the while loop?

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4]location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

Consider this C code to swap two integers and these five statements: the code.

S1: will generate a compilation error
S2: may generate a segmentation fault at runtime depending on the arguments passed
S3: correctly implements the swap procedure for all input pointers referring to integers stored in
memory locations accessible to the process
S4: implements the swap procedure correctly for some but not all valid input pointers
S5: may add or subtract integers and pointers.

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4]location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Q.76. Which one of the following is the sequence of items in the array representing the resultant heap?

In the following C program fragment, j, k, n and TwoLog_n are integer variables, and A is an array of
integers. The variable n is initialized to an integer $\ge$3, and TwoLog_n is initialized to the value of 2
*$\lceil log_2(n) \rceil$

for (k = 3; k & lt; = n; k++)
  A[k] = 0;
for (k = 2; k & lt; = TwoLog_n; k++)
  for (j = k + 1; j & lt; = n; j++)
    A[j] = A[j] || (j % k);
for (j = 3; j & lt; = n; j++)
  if (!A[j]) print f(” % d”, j);

The set of numbers printed by this program fragment is

Consider the following C program segment where CellNode represents a node in a binary tree:

Struct Cell Node {
  Struct Cell Node * left child;
  Int element;
  Struct Cell Node * right Child;
};
Int Get Value(struct Cell Node * ptr) {
  Int Value = 0;
  if (ptr! = NULL)
    if ((ptr - > left child == NULL) &&
      (ptr - > right Child == NULL))
      Value = 1;
    else
      Value = value + GetValue(ptr - > left Child) + Get Value(ptr - > right child);
}
return (value);
}

The value returned by GetValue when a pointer to the root of a binary tree is passed as its argument is:

An implementation of a queue Q, using two stacks S1 and S2, is given below:

void insert(Q, x) {
  push(S1, x);
}
void delete(Q) {
  if (stack - empty(S2)) then
  if (stack - empty(S1)) then {
    print(“Q is empty”);
    return;
  } else
    while (!(stack - empty(S1))) {
      x = pop(S1);
      push(S2, x);
    }
  x = pop(S2);
}

Let n insert and m ($\le$ n) delete operations be performed in an arbitrary order on an empty queue Q. Let
x and y be the number of push and pop operations performed respectively in the process. Which one of
the following is true for all m and n?

The following C function takes a single-linked list of integers as a parameter and rearranges the
elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given
order. What will be the contents of the list after the function completes execution?

struct node {
  int value;
  struct node * next;
};
Void rearrange struct node * list {
  struct node * p, * q;
  int temp;
  if (!list || !!list - > ; next) return;
  p = list; | q = list - > ;
  next;
  while q {
    temp = p - > ;
    value;
    p - > ;
    value = q - > ;
    value;
    q - > ;
    value = temp;
    p = q - > ;
    next;
    q = p ? p - > ;
    next: 0;
  }
}