Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

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?

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

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 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 AVL-tree with n elements initially?

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, _______”.

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.

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

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

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?

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

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

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

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?

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

Which of the following statements is false?

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

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

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.

The number of articulation points of the following graph is

(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 most appropriate matching for the following pairs

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

is

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

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?

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.

The results returned by function under value-result and reference parameter passing conventions

Consider the following declaration of a two dimensional array in C:

          char a[100][100];    

Assuming that the main memory is byte-addressable and that the array is stored starting from memory address 0, the address of a [40][50] is:

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left subtree is at least half and at most twice the number of nodes in the right subtree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

To evaluate an expression without any embedded function calls

Draw all binary trees having exactly three nodes labeled A, B and C on which Preorder traversal gives the sequence C, B, A.

The following recursive function in C is a solution to the Towers of Hanoi problem.

 Void move (int n, char A, char B, char C)
 {
     if (…………………………………) {
         move (…………………………………);
         printf(“Move disk %d from pole %c to pole %c\n”, n,A,C);
         move (………………………………….); 

Fill in the dotted parts of the solution.

Assume the following C variable declaration

int *A [10], B[10][10]; 

Of the following expressions

I. A[2]     II. A[2][3]     III. B[1]     IV. B[2][3]  

which will not give compile-time errors if used as left hand sides of assignment statements in a C program?

Let T(n) be the number of different binary search trees on n distinct elements. Then , where x is

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

Consider the following graph

Among the following sequences:

(I) a b e g h f    (II) a b f e h g    (III) a b f h g e    (IV) a f g h b e 

Which are depth first traversals of the above graph?

In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time