1. Root of T can never be an articulation point in G.
2. If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.
3. A leaf of T can be an articulation point in G.
4. Root of T is an articulation point in G if and only if it has 2 or more children

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

A stack is used to pass parameters to procedures in a procedure call.
(a) If a procedure P has two parameters as described in procedure definition:

    procedure P (var x :integer; y: integer); 
    and if P is called by ; P(a,b) 

State precisely in a sentence what is pushed on stack for parameters a and b.

(b) In the generated code for the body of procedure P, how will the addressing of formal parameters x and y differ?

Prove by the principal of mathematical induction that for any binary tree, in which every non-leaf node has 2 descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.

Consider a singly linked list having n nodes. The data items d₁, d₂, ...d_n are stored in these n nodes. Let X be a pointer to the j-th node (1≤j≤n) in which d_j is stored. A new data item d stored in node with address Y is t be inserted. Give an algorithm to insert d into the list to obtain a list having items d₁, d₂, ..., d_j-1, d_j, ..., d_n in the order without using the header.

A queue Q containing n items and an empty stack S are given. It is required to transfer all the items from the queue to the stack, so that the item at the front of queue is on the top of the stack, and the order of all other items is preserved. Show how this can be done in O(n) time using only a constant amount of additional storage. Note that the only operations which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.

A rooted tree with 12 nodes has its nodes numbered 1 to 12 in pre-order. When the tree is traversed in post-order, the nodes are visited in the order 3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, 1.
Reconstruct the original tree from this information, that is, find the parent of each node, and show the tree diagrammatically.

Linked lists are not suitable data structures of which one of the following problems?

Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that order?

An unrestricted use of the “goto” statement is harmful because

What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A, B, C? Draw all these binary trees.

Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.

In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.

Let G = (V,E) be a directed, weighted graph with weight function w:E → R. For some function f:V → R, for each edge (u,v) ∈ E, define w'(u,v) as w(u,v) + f(u) - f(v).
Which one of the options completes the following sentence so that it is TRUE?

“The shortest paths in G under w are shortest paths under w’ too, _______”.

What is the worst case time complexity of inserting n² elements into an AVL-tree with n elements initially?

Consider the following C program.

#include 
int main ()  {
     int a [4] [5] = {{1, 2, 3, 4, 5},
                      {6, 7, 8, 9, 10},
                      {11, 12, 13, 14, 15},
                      {16, 17, 18, 19, 20}};
     printf (“%d\n”, *(*(a+**a+2) +3));
     return (0);
} 

The output of the program is _______.

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

Consider a double hashing scheme in which the primary hash function is h₁(k) = k mod 23, and the secondary hash function is h₂(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k=90 is _______.

The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19.

Which one of the following is the postorder traversal of the tree?

A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which are not? Explain.

A binary search tree is generated by inserting in order the following integers:

 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24  

The number of nodes in the left subtree and right subtree of the root respectively is

The minimum number of interchanges needed to convert the array

 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70  

into a heap with the maximum element at the root is

In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?

Which of the following sequences denotes the post order traversal sequence of the tree of question 14?

Consider the following statements:

(i) First-in-first out types of computations are efficiently supported by STACKS.
(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
(iv) Last-in-first-out type of computations are efficiently supported by QUEUES.

Which of the following is correct?

An advantage of chained hash table (external hashing) over the open addressing scheme is

Let T be a full binary tree with 8 leaves. (A full binary tree has every level full). Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) _____.

A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?

A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in

The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list should be used?

Which of the following is essential for converting an infix expression to the postfix from efficiently?

Let p be a pointer as shown in the figure in a single linked list.

What do the following assignment statements achieve?

q: = p → next
p → next:= q → next
q → next:=(q → next) → next
(p → next) → next:= q

(b) Compute the postfix equivalent of the following Infix expression

  3 * log(x+1) - a/2  

Draw the binary tree with node labels a, b, c, d, e, f and g for which the inorder and postorder traversals result in the following sequences:

 Inorder       a f b c d g e
 Postorder     a f c g e d b 

(a) Derive a recurrence relation of the size of the smallest AVL tree with height h.

Let A be a two dimensional array declared as follows:

  A: array [1 ... 10] [1 ... 15] of integer;  

Assuming that each integer takes one memory location, the array is stored in row-major order and the first element of the array is stored at location 100, what is the address of the element a[i][j]?

Faster access to non-local variables is achieved using an array of pointers to activation records called a

A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by

Which of the following statements is false?

(a) In a binary tree, a nil node is defined to be a node with 2 children. Use induction on the height of the binary tree to prove that the number of full nodes plus one is equal to the number of leaves.

(b) Draw a min-heap that results from insertion of the following elements in order into an initially empty min-heap: 7, 6, 5, 4, 2, 3, 1. Show the result after the deletion of the root of this heap.

The number of articulation points of the following graph is

Suppose you are given arrays p[1…..N] and q[1…….N] both uninitialized that is, each location may contain an arbitrary value), and a variable count, initialized to 0. Consider the following procedures set and iset:

 set (i) {
      count = count + 1;
      q [count] = i;
      p[i] = count;
 }
 is_set(i) {
      if (p[i] ≤ 0 or p[i] > count)
      return false;
      if (q[p[i]] ≠i)
      return false;
 return true;
 } 

(a) Suppose we make the following sequence of calls: set (7); set (3); set(9);
After these quence of calls, what is the value of count, and what do q[1], q[2], q[3], p[7], p[3] and p[9] contain?

(b) Complete the following statement “The first count elements of _______ contain values i such that set (__________) has been called”.

(c) Show that if set (i) has not been called for some i, then regardless of what p[i] contains, is_set (i) will return false.

Suppose a stack implementation supports, in addition to PUSH and POP, an operation REVERSE, which reverses the order of the elements on the stack.
(a) To implement a queue using the above stack implementation, show how to implement ENQUEUE using a single operation and DEQUEUE using a sequence of 3 operations.
(b) The following postfix expression, containing single digit operands and arithmetic operators + and *, is evaluated using a stack.

 5 2 * 3 4 + 5 2 * * + 

Show the contents of the stack.

(i) After evaluating 5 2 * 3 4 +
(ii) After evaluating 5 2 * 3 4 + 5 2
(iii) At the end of evaluation.

Suppose you are given an array s[1...n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence do, where 1 ≤ k ≤ n:

         reverse(s, 1, k) ;
         reverse(s, k + 1, n);
         reverse(s, l, n);  

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let ν be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

The most appropriate matching for the following pairs

          X: depth first search            1: heap
          Y: breadth-first search          2: queue
          Z: sorting                       3: stack  

is