Data Structures and Algorithms

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 function f defined below.

struct item {
  int data;
  struct item * next;
};
int f(struct item * p) {
  return ((p == NULL) || (p - > next == NULL) ||
    ((p - > data <= p - > next - > data) & amp; & amp; f(p - > next)));
}

For a given linked list p, the function f returns 1 if and only if

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?

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?

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;
  }
}