Consider the following statements:

I. The smallest element in a max-heap is always at a leaf node.
II. The second largest element in a max-heap is always a child of the root node.
III. A max-heap can be constructed from a binary search tree in Θ(n) time.
IV. A binary search tree can be constructed from a max-heap in Θ(n) time.

Which of the above statements are TRUE?

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) _____.

The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _______.

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let 'enqueue' be implemented by inserting a new node at the head, and 'dequeue' be implemented by deletion of a node from the tail.

Which one of the following is the time complexity of the most time-efficient implementation of 'enqueue' and 'dequeue, respectively, for this data structure?

Let G be a simple undirected graph. Let T_D be a depth first search tree of G. Let T_B be a breadth first search tree of G. Consider the following statements.

(I) No edge of G is a cross edge with respect to T_D.
    (A cross edge in G is between two nodes neither of which is an ancestor of the other in T_D.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in T_B, then ∣i−j∣ = 1.

Which of the statements above must necessarily be true?

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ___________.

Consider the C code fragment given below.

typedef struct node   {
    int data;
    node* next;
}   node;

void join(node* m, node* n)   {
    node*  p = n;
    while(p→next  !=NULL)    {
       p = p→next; 
    }
    p→next=m;
}

Assuming that m and n point to valid NULL-terminated linked lists, invocation of join will

Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _________.

A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time?

I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is __________.

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change

An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?

Consider the weighted undirected graph with 4 vertices, where the weight of edge {i,j} is given by the entry W_ij  in the matrix W.

The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x 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.

The maximum possible number of iterations of the while loop in the algorithm is _________.

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is _________.

N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order: Θ(N) delete,O(logN) insert, O(logN) find, and Θ(N) decrease-key. What is the time complexity of all these operations put together?

A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _________.

Consider the following New-order strategy for traversing a binary tree:

• Visit the root;
• Visit the right subtree using New-order;
• Visit the left subtree using New-order;

The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ˆ 6 7 * 1 + - is given by:

The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _________.

In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?

The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.

Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

A binary tree T has 20 leaves. The number of nodes in T having two children is _________.

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

Assume that the bandwidth for a TCP connection is 1048560 bits/sec. Let α be the value of RTT in milliseconds (rounded off to the nearest integer) after which the TCP window scale option is needed. Let β be the maximum possible window size the window scale option. Then the values of α and β are

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 ∞, and hence there cannot be any entry to the right of, or below a ∞. The following Young tableau consists of unique entries.

1     2     5      14
3     4     6      23       
10    12    18     25  
31    ∞     ∞       ∞ 

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 ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is ____________.

Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is ___________.

Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The minimum number of interchanges needed to convert it into a max-heap is

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

The result evaluating the postfix expression  10  5 +  60 6 /  * 8 -   is

Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ____.

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O(n^alog^bn). Then the value of a+10b is ________.

Consider the directed graph given below.

Which one of the following is TRUE?

Let P be a quicksort program to sort numbers in ascending order using the first elements as the pivot. Let t₁ and t₂ be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?

Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

Consider the following C function in which size is the number of elements in the array E: The value returned by the function MyX is the

int MyX(int *E, unsigned int size)
{
    int Y = 0;
    int Z;
    int i, j, k;
    for(i = 0; i < size; i++)
        Y = Y + E[i];
    for(i = 0; i < size; i++)
        for(j = i; j < size; j++)
        {
            Z = 0;
            for(k = i; k <= j; k++)
                Z = Z + E[k];
            if (Z > Y)
                Y = Z;
        }
    return Y;
}

Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2
for i = 1 to n do
   for j = i to n do
      for k = j + 1 to n do
           D = D * 3

Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is _________.

An access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of associativity A≥k exercising least-recently-used replacement policy?

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

The worst case running time to search for an element in a balanced binary search tree with n2ⁿ elements is

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

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

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.

The appropriate expression for the two boxes B1 and B2 are

A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?

We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

typedef struct node 
{
  int value;
  struct node *next;
}Node;
  
Node *move_to_front(Node *head) 
{
  Node *p, *q;
  if ((head == NULL: || (head->next == NULL)) 
    return head;
  q = NULL; p = head;
  while (p-> next !=NULL) 
  {
    q = p;
    p = p->next;
  }
  _______________________________
  return head;
}

Choose the correct alternative to replace the blank line.

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_ij in the matrix W below is the weight of the edge {i, j}.

What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

Consider a binary max-heap implemented using an array.

Which one of the following array represents a binary max-heap?

Consider a binary max-heap implemented using an array.

What is the content of the array after two delete operations on the correct answer to the previous question?

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

Given f₁, f₃ and f in canonical sum of products form (in decimal) for the circuit

f₁ = Σm(4,5,6,7,8)
f₃ = Σm(1,6,15)
f = Σm(1,6,8,15)

then f₂ is

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

G is a graph on n vertices and 2n–2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

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

Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

The maximum number of binary trees that can be formed with three unlabeled nodes is:

The following postfix expression with single digit operands is evaluated using a stack:

            8 2 3 ^ / 2 3 * + 5 1 * -  

Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.

A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?

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

  struct CellNode {
      struct CellNOde *leftChild;
        int element;
      struct CellNode *rightChild;
  };
 
  int GetValue(struct CellNode *ptr) {
      int value = 0;
      if (ptr != NULL)            {
        if ((ptr->leftChild == NULL) &&
              (ptr->rightChild == NULL))
           value = 1;
  else
           value = value + GetValue(ptr->leftChild)
                         + GetValue(ptr->rightChild);
    }
    return(value);
  }
The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:

In a binary max heap containing n numbers, the smallest element can be found in time

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.

Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?

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(<=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?

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?

An Abstract Data Type (ADT) is:

A program P reads in 500 integers in the range [0, 100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

An undirected graph C has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are l's. Which one of the following is TRUE?

Postorder traversal of a given binary search tree T produces the following sequence of keys

   10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 

Which one of the following sequences of keys can be the result of an inorder traversal of the tree T?

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:

   10, 8, 5, 3, 2 

Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

How many distinct binary search trees can be created out of 4 distinct keys?

In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is:

Let s and t be two vertices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y.

The edge e must definitely belong to:

Let s and t be two vertices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y.

Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?

A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl < top2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

The best data structure to check whether an arithmetic expression has balanced parentheses is a

Level order traversal of a rooted tree can be done by starting from the root and performing

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?

i) 9679, 1989, 4199 hash to the same value
ii) 1471, 6171 hash to the same value
iii) All elements hash to the same value
iv) Each element hashes to a different value

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?

(i) preorder and postorder     (ii) inorder and postorder
(iii) preorder and inorder     (iv) level order and postorder 

A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?

The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

Consider the following C program segment

struct CellNode
{
  struct CelINode *leftchild;
  int element;
  struct CelINode *rightChild;
}
 
int Dosomething(struct CelINode *ptr)
{
    int value = 0;
    if (ptr != NULL)
    {
      if (ptr->leftChild != NULL)
        value = 1 + DoSomething(ptr->leftChild);
      if (ptr->rightChild != NULL)
        value = max(value, 1 + DoSomething(ptr->rightChild));
    }
    return (value);
}

The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is

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

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≥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 operation 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≥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 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree.

What is the result of inserting G in the above tree?

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) &&
            f(p->next)));
} 

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

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.

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i≤n), the index of the parent is

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?

What is the minimum number of stacks of size n required to implement a queue of size n?

Consider the following three C functions:

[PI]            int*g(void) 
             { 
                int x = 10; 
                return(&x); 
             }  
    
[P2]            int*g(void) 
             { 
                int*px; 
                *px = 10; 
                return px; 
             } 
    
[P3]            int*g(void) 
             { 
                int*px; 
                px = (int *) malloc(sizeof(int)); 
                *px = 10; 
                return px; 
             } 

Which of the above three functions are likely to cause problems with pointers?

(a) Insert the following keys one by one into a binary search tree in the order specified.

         15, 32, 20, 9, 3, 25, 12, 1  

Show the final binary search tree after the insertions.
(b) Draw the binary search tree after deleting 15 from it.
(c) Complete the statements S1, S2 and S3 in the following function so that the function computes the depth of a binary rooted at t.

              typedef struct tnode{
                  int key;
                  struct tnode *left, *right;
              } *Tree;
              int depth(Tree t)
              {
                  int x,y;
                  it (t == NULL) return0;
                  x=depth(t → left);
 S1:              ____________;
 S2:              if(x>y) return _____________:
 S3:              else return _____________;
              } 

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 number of articulation points of the following graph is

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

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

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

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

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?

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

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

A 2-3 tree is tree such that

(a) all internal nodes have either 2 or 3 children
(b) all paths from root to the leaves have the same length

The number of internal nodes of a 2-3 tree having 9 leaves could be

How many edges are there in a forest with p components having n vertices in all?

Match the pairs in the following questions:

(a) A heap construction                            (p) Ω(n log10 n)
(b) Constructing Hash table with linear probing    (q) O(n)
(c) AVL Tree construction                          (r) O(n2)
(d) Digital trie construction                      (s) O(n log10 n)

Choose the correct alternatives (More than one may be correct). The number of rooted binary trees with n nodes is,