List of top Programming and Data Structures Questions

Consider the following ANSI-C function.

int func(int start, int end){
    int length=end+1-start;
    if((length<1)||(start<0)||(end<0)){ return(0); }
    if(length%3==0){
        return(func(start+1, end));
    } else if(length%3==1){
        return(1+func(start, end-1));
    } else {
        return(func(start+2, end));
    }
}

The maximum possible value that can be returned from this function is ______.

Note: Ignore syntax errors (if any) in the function.

Consider the following ANSI-C program.

#include <stdio.h>

int main(){
    int *ptr, a, b, c;
    a=5; b=11; c=20;
    ptr=&a; *ptr=c; ptr=&c;
    a=*(&b); c=*ptr-a;
    printf("%d",c);
    return(0);
}

The output of this program is ______.

Note: Assume that the program compiles and runs successfully.

Consider the following three ANSI-C programs, P1, P2, and P3.

P1:
#include <stdio.h>
int a=5;
int main(){
int a=7;
return(0);
}

P2:
#include <stdio.h>
int main(){
int a=5;
int a=7;
return(0);
}

P3:
#include <stdio.h>
int main(){
int a=5;
float a=7;
return(0);
}

Which one of the following statements is true?

Consider a binary search tree (BST) with \(n\) leaf nodes (\(n>0\)). Given any node \(V\), the key present in the node is denoted as \(Val(V)\). All the keys present in the given BST are distinct. The keys belong to the set of real numbers.

For a node \(V\), let \(Suc(V)\) denote the node that is its inorder successor. If a node \(V\) does not have an inorder successor, then \(Suc(V)\) is \(NULL\). As there are no duplicates, if \(Suc(V)\) is not \(NULL\), then \(Val(V) < Val(Suc(V))\).

Corresponding to every leaf node \(L_i\) that has a non-NULL \(Suc(L_i)\), a new key \(k_i\) with the following property is to be inserted into the BST. \[ Val(L_i) < k_i < Val(Suc(L_i)) \] Let \(K\) represent the list of all such new keys to be inserted into the BST. Which of the following statements is/are true?

The keys \(5, 28, 19, 15, 26, 33, 12, 17, 10\) are inserted into a hash table using the hash function \(h(k) = k \bmod 9\). The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is _____. (answer in integer)

The set T represents various traversals over a binary tree. The set S represents the order of visiting nodes during a traversal.

T	S
I: Inorder	L: left subtree, node, right subtree
II: Preorder	M: node, left subtree, right subtree
III: Postorder	N: left subtree, right subtree, node

Which one of the following is the correct match from T to S?

In a C runtime environment, which one of the following is stored in the heap?

Consider a stack \(S\) and a queue \(Q\). Both of them are initially empty and have the capacity to store ten elements each. The elements \(1, 2, 3, 4\), and \(5\) arrive one by one, in that order. When an element arrives, it is assigned either to \(S\) (pushed on \(S\)) or to \(Q\) (enqueued to \(Q\)). Once all the five elements are stored, the output is generated in two steps. First, stack \(S\) is emptied by popping all elements. Then queue \(Q\) is emptied by dequeueing all elements. The output obtained by following this process is \(4\ 3\ 1\ 2\ 5\).

Given the output, the objective is to predict whether an element was assigned to \(S\) or \(Q\).

Which of the following options is/are possible valid assignment(s) of the elements?

Note: In the options, the notation \(xS\) denotes that element \(x\) was assigned to \(S\) and \(yQ\) denotes that element \(y\) was assigned to \(Q\).

Let \( n \) be an odd number greater than 100. Consider a binary minheap with \( n \) elements stored in an array \( P \) whose index starts from 1.

Which of the following indices of \( P \) do/does NOT correspond to any leaf node of the minheap?

Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head.

struct node{
  int elt;
  struct node *next;
};

int getListSize (struct node *head)
{
  if( E1 ) return 1;
  return E2;
}

Which one of the following options gives the correct replacements for the expressions E1 and E2?

Consider the following program in C:

#include <stdio.h>

void func(int i, int j) {
  if (i < j) {
    int i = 0;
    while (i < 10) {
      j += 2;
      i++;
    }
  }
  printf("%d", i);
}

int main() {
  int i = 9, j = 10;
  func(i, j);
  return 0;
}

The output of the program is __________. (answer in integer)

Note: Assume that the program compiles and runs successfully.

Let \(P\) be the set of all integers from 1 to 15. Consider any order of insertion of the elements of \(P\) into a binary search tree that creates a complete binary tree.

Which one of the following elements can NEVER be the third element that is inserted?

Consider a hash table \( P[0,1,\ldots,10] \) that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is \( h(x) = (x+7) \bmod 11 \).

Consider the following sequence of insertions performed on \( P \):

\[ 1, 13, 22, 15, 11, 24 \]

Which of the following positions in the hash table is/are empty after these insertions are performed?

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is __________. (answer in integer)

Consider the recursive functions represented by the following code segment:

int bar(int n){
     if (n == 1) return 0;
     else return 1 + bar(n/2);
}
int foo(int n){
     if (n == 1) return 1;
     else return 1 + foo(bar(n));
}

The smallest positive integer n for which foo(n) returns 5 is ______.

Note: Ignore syntax errors (if any) in the function.

The following sequence corresponds to the preorder traversal of a binary search tree \(T\):

50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77

The position of the element 60 in the postorder traversal of \(T\) is ______.

Note: The position begins with 1.

Suppose that insertion sort is applied to the array \( [1, 3, 5, 7, 9, 11, x, 15, 13] \) and it takes exactly two swaps to sort the array. Select all possible values of \( x \).

For which of the following inputs does binary search take time \( O(\log n) \) in the worst case?

Consider game trees Tree-1 and Tree-2 as shown. The first level is a MAX agent and the second level is a MIN agent. The value in the square node is the output of the utility function.

For what ranges of \( x \) and \( y \), the right child of node B and the right child of node E will be pruned by the alpha-beta pruning algorithm?

The state graph shows the action cost along the edges and the heuristic function \( h \) associated with each state. Suppose the A algorithm is applied on this state graph using a priority queue to store the frontier. In what sequence are the nodes expanded?

Consider the following Python code snippet.

def f(a, b):
    if (a == 0):
        return b
    if (a % 2 == 1):
        return 2 * f((a - 1) / 2, b)
    return b + f(a - 1, b)

print(f(15, 10))

The value printed by the code snippet is 160 (Answer in integer).

Consider the following Python code snippet.

def f(a, b):
    if (a == 0):
        return b
    if (a % 2 == 1):
        return 2 * f((a - 1) / 2, b)
    return b + f(a - 1, b)

print(f(15, 10))

The value printed by the code snippet is 160 (Answer in integer).

The pseudocode of a function \( fun() \) is given below:

fun(int A[0, ..., n-1]) {
    for i = 0 to n-2
        for j = 0 to n - i - 2
            if (A[j] > A[j+1])
                then swap A[j] and A[j+1]
}

Let \( A[0, \ldots, 29] \) be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function \( fun() \) is called with \( A[0, \ldots, 29] \) as argument, is __________ (Answer in integer).

Suppose the values 10, −4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let \( T \) be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of \( T \) is \underline{{1cm}}. {(Answer in integer)}

In a B+- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes: \( A = (49, 77, 83, -) \)
\( B = (7, 19, 33, 44) \)
\( C = (20^*, 22^*, 25^*, 26^*) \)
The *-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys \( k_1 \) and \( k_2 \) points to a subtree containing keys in \([ k_1, k_2 )\), and that when a leaf is created, the smallest key in it is copied up into its parent. A record with key value 23 is inserted into the B+- tree. The smallest key value in the parent of the leaf that contains 25* is ___________ . (Answer in integer)