You are given the following Pre-order and In-order traversals of a Binary Tree T with nodes E, F, G, P, Q, R, S.
Pre-order: P Q S E R F G
In-order: S Q E P F R G
Which of the following statements is/are true about the Binary Tree T?
- (A)Node P is the root of T
- (B)The Post-order traversal of T is: SEQFGRP
- (C)Node Q has only one child
- (D)The left subtree of node R contains the node G
Pre-order starts with P, so P is the root. In-order splits into left {S, Q, E} and right {F, R, G}. Left pre-order Q S E: Q is its root with S left and E right. Right pre-order R F G: R is its root with F left and G right. Post-order: S E Q F G R P. So (A) true, (B) true, (C) false (Q has two children), (D) false (G is R's right child). Answer: (A), (B).
Concept: Rebuilding a tree from pre-order and in-order. The trap is misreading which side of R holds G.
A recursive function in Python is given. Now, consider the function call mystery(4). Assume that a typical runtime stack is used to manage function calls. Each function call is pushed onto the stack and removed only after it finishes execution.
Which of the following options denotes the total number of function calls (i.e., the total number of stack activations), including the initial call, to compute mystery(4)?
def mystery(n):
if n <= 0:
return 1
else:
return mystery(n-1) + mystery(n-2)- (A)5
- (B)9
- (C)15
- (D)17
Let C(n) be the number of calls made by mystery(n). C(n) = 1 for n ≤ 0, else C(n) = 1 + C(n-1) + C(n-2). C(0) = C(-1) = 1; C(1) = 1 + 1 + 1 = 3; C(2) = 1 + 3 + 1 = 5; C(3) = 1 + 5 + 3 = 9; C(4) = 1 + 9 + 5 = 15. Answer: (C) 15.
Concept: Counting nodes of a recursion tree. The trap is forgetting that mystery(1) still calls mystery(0) and mystery(-1), since the base case is n ≤ 0.
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?
- (A)(n + 1)/2
- (B)(n - 1)/2
- (C)(n - 3)/2
- (D)n
In a 1-indexed heap, node i has a left child 2i if 2i ≤ n. Internal nodes are 1..floor(n/2); leaves are floor(n/2)+1..n. For odd n, floor(n/2) = (n - 1)/2, so leaves start at (n + 1)/2. Hence (n - 1)/2 and (n - 3)/2 are internal; (n + 1)/2 and n are leaves. Answer: (B), (C).
Concept: Heap array indexing: a node is a leaf iff 2i > n. The question asks for NON-leaves; misreading that flips the answer.
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)
A full binary tree (every node has 0 or 2 children) with n nodes has (n - 1)/2 = 11 internal nodes. Height is maximised by a 'caterpillar' where each level has one internal node and one leaf, so each internal node adds one edge of depth. Height = number of internal nodes = 11. Answer: 11.
Concept: Full binary tree facts: internal i, leaves i + 1, n = 2i + 1. Maximum height is i, minimum is about log₂ n. Do not confuse with a complete tree.
Consider the following program in C. The output of the program is _________. (answer in integer) Note: Assume that the program compiles and runs successfully.
#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;
}func is called with i = 9, j = 10. Since 9 < 10 the block runs, but it declares a new local int i that shadows the parameter; the loop changes only that inner i (and j). When the block ends the inner i goes out of scope, and printf uses the parameter i, still 9. Answer: 9.
Concept: Block scope and shadowing in C. The trap is answering 10 by assuming the loop modified the parameter i.
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. Which one of the following options gives the correct replacements for the expressions E1 and E2?
struct node{
int elt;
struct node *next;
};
int getListSize (struct node *head)
{
if( E1 ) return 1;
return E2;
}- (A)E1: head == NULL E2: 1 + getListSize(head)
- (B)E1: head->next == NULL E2: 1 + getListSize(head->next)
- (C)E1: head == NULL E2: 1 + getListSize(head->next)
- (D)E1: head->next == NULL E2: 1 + getListSize(head)
The base case returns 1, so it must fire at the last node: head->next == NULL. The recursive case counts this node and recurses on the rest: 1 + getListSize(head->next). Option (C) returns 1 for an empty list and over-counts by one (and with head == NULL it would return 1 at the end, giving n + 1). Options (A) and (D) recurse on head itself and never terminate. Answer: (B).
Concept: Recursive list length: the base case must match the return value. Returning 1 means stop at the last node, not at NULL.
Let S be the set of all integers from 1 to 15. Consider any order of insertion of the elements of S 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?
- (A)4
- (B)2
- (C)10
- (D)5
A complete BST on 1..15 is the perfect tree with root 8, level-2 nodes 4 and 12, level-3 nodes 2, 6, 10, 14, leaves the odd numbers. In any insertion order a parent must be inserted before its children, so the first element is 8 and the second is 4 or 12. The third is either the other of 4/12 or a child of the second (2 or 6 if second is 4; 10 or 14 if second is 12). So the third element is in {2, 4, 6, 10, 12, 14}. 5 is a leaf, needing 8, 4 and 6 before it. Answer: (D) 5.
Concept: BST shape is fixed by the set of ancestors inserted first. Count how many ancestors an element has: a node at depth d can appear no earlier than position d + 1.
Consider the recursive functions represented by the following code segment. The smallest positive integer n for which foo(n) returns 5 is ______. (answer in integer) Note: Ignore syntax errors (if any) in the function.
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));
}bar(n) = floor(log₂ n). foo(1) = 1 and foo(n) = 1 + foo(floor(log₂ n)). Smallest n with foo = 2: need bar(n) = 1, n = 2. foo = 3: bar(n) = 2 (smallest m with foo(m) = 2), n = 4. foo = 4: bar(n) = 4, n = 2⁴ = 16. foo = 5: bar(n) = 16, n = 2¹⁶ = 65536. Answer: 65536.
Concept: foo counts how many times floor(log₂) must be applied to reach 1 (an iterated logarithm). Working backwards from the base case gives a tower of powers of two.
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 ______. (answer in integer) Note: The position begins with 1.
Build the BST from the preorder: root 50; left subtree from 25, 13, 40, 30, 47 (25 with left 13 and right 40, 40 with children 30 and 47); right subtree from 75, 60, 70, 80, 77 (75 with left 60 whose right child is 70, and right 80 whose left child is 77). Postorder: 13, 30, 47, 40, 25, 70, 60, 77, 80, 75, 50. 60 is at position 7. Answer: 7.
Concept: Preorder of a BST determines the tree: the first element is the root, smaller elements form the left subtree. Postorder lists children before parents.
The set T represents various traversals over 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?
- (A)I → L, II → M, III → N
- (B)I → M, II → L, III → N
- (C)I → N, II → M, III → L
- (D)I → L, II → N, III → M
Inorder visits left subtree, node, right subtree (L). Preorder visits node first, then left, then right (M). Postorder visits left, right, then node (N). Answer: (A) I → L, II → M, III → N.
Concept: Definitions of the three depth-first traversals: the prefix (pre/in/post) tells where the node is visited relative to its subtrees. Mixing up pre and post is the common slip.
Consider the following three ANSI-C programs, P1, P2, and P3. Which one of the following statements is true?
/* 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);
}- (A)Only P1 will compile without any error
- (B)Only P2 will compile without any error
- (C)Only P3 will compile without any error
- (D)All three programs P1, P2, and P3 will compile without any error
P1: the global a and the local a are in different scopes; the local one shadows the global. Legal. P2: a is defined twice in the same block - redefinition error. P3: a is declared as int and then as float in the same block - conflicting types error. Only P1 compiles. Answer: (A).
Concept: Scope and redeclaration rules in C: an inner scope may shadow an outer name, but the same block cannot define a name twice, whatever the type. The trap is thinking a different type makes P3 legal.
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ᵢ that has a non-NULL Suc(Lᵢ), a new key kᵢ with the following property is to be inserted into the BST.
Val(Lᵢ) < kᵢ < Val(Suc(Lᵢ))
Let K represent the list of all such new keys to be inserted into the BST.
Which of the following statements is/are true?
- (A)K cannot have any duplicates
- (B)K will have at least one element
- (C)After inserting all keys from K, the height of the BST can increase at most by one
- (D)Number of nodes in the BST will double after inserting all keys from K
(A) Each interval (Val(Lᵢ), Val(Suc(Lᵢ))) lies between consecutive keys in sorted order, so different leaves give disjoint open intervals: no duplicates. True. (B) If the only leaf holds the maximum key (e.g. a single-node tree or a right-skewed chain), it has no successor and K is empty. False. (C) A leaf has no right child, and kᵢ lies just after Val(Lᵢ) in order, so kᵢ is inserted as the right child of Lᵢ. Each new node hangs one level below an old leaf, so height grows by at most one. True. (D) Only leaves get new keys, so nodes do not double in general. False. Answer: (A) and (C).
Concept: A key between a node and its inorder successor is inserted as that node's right child if it has none. The trap is (B): the single-leaf case can have no successor.
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.
- (A)1S, 2Q, 3S, 4S, 5Q
- (B)1Q, 2Q, 3S, 4S, 5Q
- (C)1Q, 2Q, 3Q, 4S, 5S
- (D)1S, 2S, 3S, 4Q, 5Q
Stack output is its elements in decreasing arrival order, then the queue in increasing order. (A) S = {1,3,4} → 4 3 1, Q = {2,5} → 2 5: output 4 3 1 2 5. Valid. (B) S = {3,4} → 4 3, Q = {1,2,5} → 1 2 5: 4 3 1 2 5. Valid. (C) S = {4,5} → 5 4 first. Invalid. (D) S = {1,2,3} → 3 2 1 first. Invalid. Answer: (A) and (B).
Concept: Simulate each assignment. The output can be split as a decreasing prefix (stack) and an increasing suffix (queue); element 1 can sit on either side of the split, giving two valid answers.
Consider the following ANSI-C program. The output of this program is ____________. (answer in integer)
Note: Assume that the program compiles and runs successfully.
#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);
}a=5, b=11, c=20. ptr=&a; *ptr=c sets a=20. ptr=&c. a=*(&b) sets a=11. c=*ptr-a = c - a = 20 - 11 = 9. Output: 9.
Concept: Track which variable ptr points to after each assignment; *(&b) is simply b. The trap is using the stale value of a or thinking *ptr still refers to a.
Consider the following ANSI-C function. The maximum possible value that can be returned from this function is ____________. (answer in integer)
Note: Ignore syntax errors (if any) in the 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));
}
}Only the length%3==1 branch adds 1, and each call reduces length. Track length L mod 3: L ≡ 1 → add 1, L-1 (≡ 0). L ≡ 0 → L-1 (≡ 2). L ≡ 2 → L-2 (≡ 0). From ≡ 0 the chain alternates 0 → 2 → 0 → 2 ... and never returns to ≡ 1, ending at length 0 or -1 which returns 0. So at most one +1 can occur, when the initial length is ≡ 1 mod 3 (e.g. func(0,0) = 1). Maximum = 1. Answer: 1.
Concept: Analyse the recursion as a state machine on length mod 3. The trap is assuming each cycle adds 1 and getting a value growing with n.
Consider the following Python code snippet.
The value printed by the code snippet is ______ (Answer in integer)
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))b = 10 throughout. (a-1)/2 is a float in Python 3, but the comparisons still work (7.0 == 7).
f(15) = 2 f(7); f(7) = 2 f(3); f(3) = 2 f(1); f(1) = 2 f(0); f(0) = 10.
So f(1) = 20, f(3) = 40, f(7) = 80, f(15) = 160.
The even branch b + f(a-1, b) is never reached. Printed value: 160 (as 160.0 in Python 3; the integer answer is 160).
Concept: Recursion tracing: unwind the calls to the base case and multiply back up. The trap is assuming the even branch is used, or worrying that / produces a float, which does not change the value.
Consider the following pseudocode.
The value of sum output by a program executing the above pseudocode is ______ (Answer in integer)
Create empty stack S
Set x=0, flag=0, sum=0
Push x onto S
while (S is not empty){
if (flag equals 0){
Set x = x+1
Push x onto S}
if (x equals 8):
Set flag=1
if (flag equals 1){
x = Pop(S)
if (x is odd):
Pop(S)
Set sum = sum + x}
}
Output sumWhile flag = 0 the loop pushes 1, 2, ..., 8, so S = [0, 1, ..., 8]. In the iteration that pushes 8, flag becomes 1, and from then on each iteration pops.
Pop 8 (even): sum = 8.
Pop 7 (odd), also pop 6: sum = 15.
Pop 5, pop 4: sum = 20.
Pop 3, pop 2: sum = 23.
Pop 1, pop 0: sum = 24. S is empty, the loop ends.
Answer: 24.
Concept: Stack trace with a conditional extra pop: odd values are added and the even value below them is discarded. The trap is adding every popped value (giving 36).
Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n distinct integers?
- (A)The maximum length of a path from the root node to any other node is (n - 1).
- (B)An inorder traversal will always produce a sorted sequence of elements.
- (C)Finding an element takes O(log₂ n) time in the worst case.
- (D)Every BST is also a Min-Heap.
(A) A path from the root can visit at most all n nodes, i.e. n - 1 edges, reached by a skewed tree: true as the maximum. (B) Inorder visits left subtree, root, right subtree, which is ascending order by the BST property: true. (C) A skewed BST needs O(n) search, so O(log n) worst case is false. (D) In a BST the left child is smaller than the parent, violating the min-heap property: false. Answer: (A), (B).
Concept: BST height ranges from log n to n - 1; only balanced BSTs guarantee logarithmic search. Inorder-sorted is the defining BST property.
The output of the given C program is __________. (Answer in integer)
#include <stdio.h>
void foo(int *p, int x){
*p=x;
}
int main(){
int *z;
int a = 20, b = 25;
z = &a;
foo(z,b);
printf("%d",a);
return 0;
}z holds the address of a. foo receives a copy of that address in p and the value 25 in x. *p = x writes 25 into the location p points to, which is a. So a becomes 25 and the program prints 25. Answer: 25.
Concept: Passing a pointer lets a function modify the caller's variable. The trap is thinking call-by-value leaves a at 20 - the pointer is copied, but it still points to a.
The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node.
Suppose a Min-Heap T stores 32 keys. The height of T is _____________. (Answer in integer)
A binary heap is a complete binary tree. Levels 0 to 4 hold 1 + 2 + 4 + 8 + 16 = 31 nodes, so the 32nd key starts level 5. Height = floor(log₂ 32) = 5 edges. Answer: 5.
Concept: Heap height is floor(log₂ n). The trap is ceil(log₂ 32) - 1 = 4, forgetting that 32 nodes overflow a perfect tree of height 4 (31 nodes).
The value printed by the given C program is _______. (Answer in integer)
#include <stdio.h>
int foo(int S[],int size){
if(size == 0) return 0;
if(size == 1) return 1;
if(S[0] != S[1]) return 1+foo(S+1,size-1);
return foo(S+1,size-1);
}
int main(){
int A[]={0,1,2,2,2,0,0,1,1};
printf("%d",foo(A,9));
return 0;
}foo adds 1 for every adjacent pair that differs, and 1 for the last element, i.e. it counts runs of equal values. Array: 0 | 1 | 2 2 2 | 0 0 | 1 1. Differing adjacent pairs: 0-1, 1-2, 2-0, 0-1 = 4, plus 1 at size 1. Total 5 (the number of runs). Answer: 5.
Concept: Recognise the recursion's meaning (count of maximal runs) instead of tracing nine calls. Trap: forgetting the base case returns 1, not 0.
Let LIST be a datatype for an implementation of linked list (definition below). Suppose a program has created two linked lists, L1 and L2, whose contents are given below (code for creating L1 and L2 is not provided here). L1 contains 9 nodes, and L2 contains 7 nodes.
L1: 1 → 7 → 12 → 3 → 9 → 5 → 11 → 15 → 8 → NULL
L2: 1 → 11 → 6 → 9 → 15 → 12 → 4 → NULL
Consider the following C program segment that modifies the list L1. The number of nodes that will be there in L1 after the execution of the code segment is ________. (Answer in integer)
typedef struct list {
int data;
struct list *next;
} LIST;
int find (int query, LIST *list) {
while (list != NULL){
if(list->data == query) return 1;
list = list->next;
}
return 0;
}
int main () {
... ... ...
ptr1=L1; ptr2=L2;
while (ptr1->next != NULL){
query = ptr1->next->data;
if (find (query, L2))
ptr1->next = ptr1->next->next;
else ptr1 = ptr1->next;
}
... ... ...
return 0;
}The loop deletes every node after the head whose value occurs in L2; the head itself (1) is never tested. L2 values: {1, 11, 6, 9, 15, 12, 4}. Walk L1 after the head: 7 keep, 12 delete, 3 keep, 9 delete, 5 keep, 11 delete, 15 delete, 8 keep. Remaining: 1 → 7 → 3 → 5 → 8. Answer: 5.
Concept: Deleting via ptr1->next without advancing ptr1 handles consecutive deletions (11, 15). Trap: deleting the head 1 as well (giving 4), though only next nodes are ever checked.
Consider the following C program. The value printed by the given C program is _______. (Answer in integer)
#include <stdio.h>
int gate (int n) {
int d, t, newnum, turn;
newnum = turn = 0; t=1;
while (n>=t) t *= 10;
t /=10;
while (t>0) {
d = n/t;
n = n%t;
t /= 10;
if (turn) newnum = 10*newnum + d;
turn = (turn + 1) % 2;
}
return newnum;
}
int main () {
printf ("%d", gate(14362));
return 0;
}First loop: t becomes 100000, then t /= 10 gives 10000, the place value of the leading digit. Second loop extracts digits left to right: 1, 4, 3, 6, 2, with turn = 0, 1, 0, 1, 0. Only digits with turn = 1 are appended: 4 then 6, so newnum = 46. Answer: 46.
Concept: The function keeps the 2nd, 4th, ... digits from the left. Trap: starting turn at 1 (giving 132) or reading digits right to left.
Consider a binary tree T in which every node has either zero or two children. Let n > 0 be the number of nodes in T. Which ONE of the following is the number of nodes in T that have exactly two children?
- (A)(n - 2)/2
- (B)(n - 1)/2
- (C)n/2
- (D)(n + 1)/2
Let I be internal nodes (two children each) and L leaves. Edges = n - 1 = 2I, so I = (n - 1)/2. Check: a single node gives 0; a root with two leaves gives n = 3, I = 1. Answer: (B) (n - 1)/2.
Concept: Full binary tree counting: every non-root node has one parent edge, and every internal node contributes two. Also L = I + 1, so n is always odd.
Consider the following C program. Which ONE of the following will be the output of the program?
#include <stdio.h>
void stringcopy(char *, char *);
int main(){
char a[30] = "@#Hello World!";
stringcopy(a, a + 2);
printf("%s\n", a);
return 0;
}
void stringcopy(char *s, char *t) {
while(*t)
*s++ = *t++;
}- (A)@#Hello World!
- (B)Hello World!
- (C)ello World!
- (D)Hello World!d!
a holds "@#Hello World!" in a[0..13] with '\0' at a[14]. stringcopy copies from a+2 to a, character by character, while *t is not '\0': the 12 characters "Hello World!" go to a[0..11]. The loop stops at the terminator without copying it. a[12] and a[13] still hold 'd' and '!', and a[14] is '\0'. printf prints "Hello World!d!". Answer: (D).
Concept: The copy loop omits the null terminator, so leftover characters of the old string stay visible. The trap is answering (B), assuming a normal strcpy.
The output of the given C code segment is ________. (Answer in integer)
int x=126,y=105;
do {
if(x>y) x=x-y;
else y=y-x;
} while(x!=y);
printf("%d",x);This is the subtraction form of Euclid's algorithm, ending at gcd(x, y). Trace: (126,105) -> (21,105) -> (21,84) -> (21,63) -> (21,42) -> (21,21), stop. gcd(126, 105) = 21. Answer: 21.
Concept: Recognising repeated subtraction as Euclid's GCD saves tracing. The do-while runs its body at least once, harmless here since x ≠ y initially.
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 ___________. (Answer in integer)
10 is the root. -4 goes left of 10, 15 right of 10, 30 right of 15, 20 left of 30, 5 right of -4, 60 right of 30, 19 left of 20. Path from 19 to the root: 19 - 20 - 30 - 15 - 10, which has 4 edges. Answer: 4.
Concept: Insert in order, comparing from the root each time. Count edges, not nodes: 5 nodes on the path means 4 edges.
A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:
P: Unsorted doubly linked list with pointers to the head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size n of these data structures?
- (A)P: Θ(1), Q: Θ(n), R: Θ(n)
- (B)P: Θ(1), Q: Θ(n log n), R: Θ(n)
- (C)P: Θ(n), Q: Θ(n log n), R: Θ(n²)
- (D)P: Θ(1), Q: Θ(n), R: Θ(n log n)
P: link the first list's tail to the second list's head and update the tail pointer: Θ(1). Q: concatenate the two arrays and run bottom-up build-heap on 2n elements: Θ(n); any method must at least move n elements. R: in-order traverse both trees to get two sorted lists (Θ(n)), merge them (Θ(n)) and build a BST from the sorted list (Θ(n)); every node must be visited, so Θ(n). Answer: (A).
Concept: Build-heap is linear, not n log n, and sorted sequences let a BST be rebuilt in linear time. The traps are repeated insertion costs (n log n or n²).
Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct. We wish to augment the stack data structure with an O(1) time MIN operation that returns a pointer to the record with smallest key present in the stack 1) without deleting the corresponding record, and 2) without increasing the complexities of the standard stack operations. Which one or more of the following approach(es) can achieve it?
- (A)Keep with every record in the stack, a pointer to the record with the smallest key below it.
- (B)Keep a pointer to the record with the smallest key in the stack.
- (C)Keep an auxiliary array in which the key values of the records in the stack are maintained in sorted order.
- (D)Keep a Min-Heap in which the key values of the records in the stack are maintained.
(A) On PUSH, store with the new record a pointer to the minimum among the records below it (computed in O(1) from the previous top's own value and pointer). MIN compares the top with its stored pointer: O(1), and POP needs no work. Works. (B) A single global pointer cannot be restored in O(1) after the minimum is popped. Fails. (C) Inserting into a sorted array costs O(n) per PUSH. Fails. (D) Heap insert and delete cost O(log n), raising PUSH/POP above O(1). Fails. Answer: (A).
Concept: The min-stack technique: each stack level remembers the minimum of everything at or below it, so the answer is restored automatically on pop. The trap is (B), which breaks on popping the minimum.
Consider the following C program. The output of the above program is ___________. (Answer in integer)
#include <stdio.h>
int main(){
int a;
int arr[5] = {30,50,10};
int *ptr;
ptr = &arr[0] + 1;
a = *ptr;
(*ptr)++;
ptr++;
printf("%d", a + (*ptr) + arr[1]);
return 0;
}arr = {30, 50, 10, 0, 0}. ptr = &arr[1], so a = 50. (*ptr)++ makes arr[1] = 51. ptr++ points to arr[2] = 10. Output = a + *ptr + arr[1] = 50 + 10 + 51 = 111. Answer: 111.
Concept: Distinguish (*ptr)++ (increments the pointed-to value) from ptr++ (moves the pointer). a was copied before the increment, so it stays 50.
Consider the following C program. The output of the given C program is ________. (Answer in integer)
#include <stdio.h>
int g(int n) {
return (n+10);
}
int f(int n) {
return g(n*2);
}
int main() {
int sum, n;
sum=0;
for (n=1; n<3; n++)
sum += g(f(n));
printf ("%d", sum);
return 0;
}g(f(n)) = (2n + 10) + 10 = 2n + 20. The loop runs for n = 1 and 2: 22 + 24 = 46. Answer: 46.
Concept: Compose the functions symbolically before tracing. The trap is running the loop three times; n < 3 stops after n = 2.
Match the items in Column 1 with the items in Column 2 in the following table:
Column 1 Column 2
(p) First In First Out (i) Stacks
(q) Lookup Operation (ii) Queues
(r) Last In First Out (iii) Hash Tables
- (A)(p) - (ii), (q) - (iii), (r) - (i)
- (B)(p) - (ii), (q) - (i), (r) - (iii)
- (C)(p) - (i), (q) - (ii), (r) - (iii)
- (D)(p) - (i), (q) - (iii), (r) - (ii)
A queue removes elements in the order they arrived: FIFO, so (p) - (ii). A hash table is built for fast key lookup: (q) - (iii). A stack removes the most recently added element: LIFO, so (r) - (i). Answer: (A).
Concept: Defining property of basic data structures. The trap is swapping stack and queue.
Consider the following tree traversals on a full binary tree:
(i) Preorder
(ii) Inorder
(iii) Postorder
Which of the following traversal options is/are sufficient to uniquely reconstruct the full binary tree?
- (A)(i) and (ii)
- (B)(ii) and (iii)
- (C)(i) and (iii)
- (D)(ii) only
Assume distinct node labels. Inorder together with preorder (or postorder) reconstructs any binary tree: the root comes from the first preorder (last postorder) element, and its position in the inorder splits the left and right subtrees; recurse. So (A) and (B) work. Preorder with postorder is ambiguous in general only when a node has a single child (it cannot tell left from right); in a full binary tree every internal node has exactly two children, so the element after the root in preorder is the left child, which splits the postorder: (C) works too. Inorder alone does not fix the root, so (D) fails. Answer: (A), (B), (C).
Concept: Pre + post fails for general binary trees but succeeds for full binary trees. The trap is forgetting that the word 'full' removes the one-child ambiguity.
The fundamental operations in a double-ended queue D are:
insertFirst(e) - Insert a new element e at the beginning of D.
insertLast(e) - Insert a new element e at the end of D.
removeFirst() - Remove and return the first element of D.
removeLast() - Remove and return the last element of D.
In an empty double-ended queue, the following operations are performed (shown below). The value of a is ______.
insertFirst(10)
insertLast(32)
a ← removeFirst()
insertLast(28)
insertLast(17)
a ← removeFirst()
a ← removeLast()
Trace the deque (front on the left): insertFirst(10) → [10]; insertLast(32) → [10, 32]; removeFirst() → a = 10, [32]; insertLast(28) → [32, 28]; insertLast(17) → [32, 28, 17]; removeFirst() → a = 32, [28, 17]; removeLast() → a = 17, [28]. The final value of a is 17. Answer: 17.
Concept: Simulating a deque. The trap is reporting an earlier value of a; only the last assignment counts.
Consider the following Python code. Which ONE of the following is the output of this code?
def count(child_dict, i):
if i not in child_dict.keys():
return 1
ans = 1
for j in child_dict[i]:
ans += count(child_dict, j)
return ans
child_dict = dict()
child_dict[0] = [1,2]
child_dict[1] = [3,4,5]
child_dict[2] = [6,7,8]
print(count(child_dict,0))- (A)6
- (B)1
- (C)8
- (D)9
count(d, i) returns 1 for a node with no children, and otherwise 1 plus the counts of its children, i.e. the number of nodes in the subtree rooted at i. Nodes 3 to 8 are leaves, so each returns 1. count(1) = 1 + 3 = 4, count(2) = 1 + 3 = 4, count(0) = 1 + 4 + 4 = 9. Answer: (D) 9.
Concept: Recursive subtree-size computation over a dictionary-encoded tree. The trap is counting only the leaves (6) or only the non-root nodes (8).
Consider the function computeS(X) whose pseudocode is given below.
Which ONE of the following values is returned by the function computeS(X) for X = [6, 3, 5, 4, 10]?
computeS(X)
S[1] ← 1
for i ← 2 to length(X)
S[i] ← 1
if X[i - 1] ≤ X[i]
S[i] ← S[i] + S[i - 1]
end if
end for
return S- (A)[1, 1, 2, 3, 4]
- (B)[1, 1, 2, 3, 3]
- (C)[1, 1, 2, 1, 2]
- (D)[1, 1, 2, 1, 5]
S[i] is the length of the non-decreasing run ending at i. S[1] = 1. i = 2: 6 ≤ 3 false, S[2] = 1. i = 3: 3 ≤ 5 true, S[3] = 1 + S[2] = 2. i = 4: 5 ≤ 4 false, S[4] = 1. i = 5: 4 ≤ 10 true, S[5] = 1 + S[4] = 2. Result [1, 1, 2, 1, 2]. Answer: (C).
Concept: Tracing a loop that compares only adjacent elements. The trap is reading it as a stock-span computation (which would give 5 for the last element, option D); here only the immediate predecessor is compared.
Consider the following Python function. What does this Python function fun() do? Select the ONE appropriate option below.
def fun(D, s1, s2):
if s1 < s2:
D[s1], D[s2] = D[s2], D[s1]
fun(D, s1+1, s2-1)- (A)It finds the smallest element in D from index s1 to s2, both inclusive.
- (B)It performs a merge sort in-place on this list D between indices s1 and s2, both inclusive.
- (C)It reverses the list D between indices s1 and s2, both inclusive.
- (D)It swaps the elements in D at indices s1 and s2, and leaves the remaining elements unchanged.
Each call swaps the outermost pair D[s1], D[s2] and recurses on the inner range s1+1 .. s2-1, stopping when the indices meet or cross. Swapping successive outer pairs moving inward reverses the segment. E.g. D = [1, 2, 3, 4], fun(D, 0, 3) gives [4, 2, 3, 1] then [4, 3, 2, 1]. Answer: (C).
Concept: Recognising the two-pointer reversal pattern written recursively. The trap is (D): reading only the first swap and missing the recursive call.
Let H, I, L, and N represent height, number of internal nodes, number of leaf nodes, and the total number of nodes respectively in a rooted binary tree.
Which of the following statements is/are always TRUE?
- (A)L ≤ I + 1
- (B)H + 1 ≤ N ≤ 2^(H+1) - 1
- (C)H ≤ I ≤ 2^H - 1
- (D)H ≤ L ≤ 2^(H-1)
Height H = edges on the longest root-to-leaf path, so levels 0..H exist. (A) In a binary tree, L = (number of nodes with 2 children) + 1 ≤ I + 1: true. (B) The longest path has H + 1 nodes, and at most 2⁰ + ... + 2^H = 2^(H+1) - 1 nodes fit: true. (C) The H nodes above the deepest leaf on that path are internal, so I ≥ H; internal nodes lie on levels 0..H-1, at most 2^H - 1: true. (D) A path-shaped tree has L = 1 < H for H ≥ 2, so H ≤ L fails (and the upper bound is 2^H, not 2^(H-1)): false. Answer: (A), (B), (C).
Concept: Counting bounds for binary trees. The trap is (D): a skewed tree has many levels but only one leaf.
Consider the following C program. Which one of the following statements is CORRECT?
#include <stdio.h>
int main(){
int a = 6;
int b = 0;
while(a < 10) {
a = a / 12 + 1;
a += b;}
printf("%d", a);
return 0;}- (A)The program prints 9 as output
- (B)The program prints 10 as output
- (C)The program gets stuck in an infinite loop
- (D)The program prints 6 as output
Start a = 6. Iteration 1: a = 6/12 + 1 = 0 + 1 = 1 (integer division), then a += 0 keeps 1. Next: a = 1/12 + 1 = 1 again. Since b = 0 never changes, a stays 1, which is always < 10, so the loop never exits and nothing is printed. Answer: (C) The program gets stuck in an infinite loop.
Concept: Integer division truncates, and a loop whose variable reaches a fixed point never terminates. The trap is treating 6/12 as 0.5.
Consider the following C program. Assume that the input to the program from the command line is 1234 followed by a newline character. Which one of the following statements is CORRECT?
#include <stdio.h>
void fX();
int main(){
fX();
return 0;}
void fX(){
char a;
if((a=getchar()) != '\n')
fX();
if(a != '\n')
putchar(a);}- (A)The program will not terminate
- (B)The program will terminate with no output
- (C)The program will terminate with 4321 as output
- (D)The program will terminate with 1234 as output
Each call reads one character into its own local a and recurses until it reads the newline. Calls hold '1', '2', '3', '4', then a call reads '\n' and returns without printing. As the stack unwinds, each call prints its own character after the deeper call returns: 4, 3, 2, 1. Output 4321 and the program terminates. Answer: (C).
Concept: Printing after the recursive call reverses the input order, since each frame keeps its own local variable. The trap is expecting 1234.
An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the following options represents the first three elements in the heapified array?
- (A)82, 90, 101
- (B)82, 11, 93
- (C)131, 11, 93
- (D)131, 111, 90
Build a max-heap bottom-up on [82, 101, 90, 11, 111, 75, 33, 131, 44, 93]. i = 5 (111, child 93): no change. i = 4 (11, children 131, 44): swap with 131. i = 3 (90, children 75, 33): no change. i = 2 (101, children 131, 111): swap with 131; 101 then beats 11, 44. i = 1 (82, children 131, 90): swap with 131; 82 sinks below 111, then below 93. Result starts 131, 111, 90. A min-heap would start with 11, which no option matches with correct children. Answer: (D) 131, 111, 90.
Concept: Heapify sifts down from the last internal node to the root. The trap is inserting one element at a time or forgetting to continue the sift-down after a swap.
Consider a binary min-heap containing 105 distinct elements. Let k be the index (in the underlying array) of the maximum element stored in the heap. The number of possible values of k is
- (A)53
- (B)52
- (C)27
- (D)1
In a min-heap the maximum has no larger descendant, so it must be a leaf, and any leaf can hold it. With 1-based indexing, nodes 1 to ⌊105/2⌋ = 52 are internal and 53 to 105 are leaves, i.e., 105 − 52 = 53 leaves. Answer: (A) 53.
Concept: Number of leaves in an n-node heap is ⌈n/2⌉. The trap is counting only the last level.
Consider the following C program. Assume parameters to a function are evaluated from right to left.
Which one of the following options is the CORRECT output of the above C program?
#include <stdio.h>
int g(int p) { printf("%d", p); return p; }
int h(int q) { printf("%d", q); return q; }
void f(int x, int y) {
g(x);
h(y);
}
int main() {
f(g(10),h(20));
}- (A)20101020
- (B)10202010
- (C)20102010
- (D)10201020
Evaluating f's arguments right to left: h(20) runs first and prints 20, then g(10) prints 10. Output so far: 2010. Inside f, x = 10 and y = 20; g(x) prints 10 and then h(y) prints 20. Full output: 20101020. Answer: (A) 20101020.
Concept: Argument evaluation order (given here as right to left) versus statement order inside the body, which is always sequential. The trap is applying right-to-left to the body too.
Consider the following C function definition.
Which of the following statements is/are TRUE?
int fX(char *a){
char *b = a;
while(*b)
b++;
return b - a;}- (A)The function call fX("abcd") will always return a value
- (B)Assuming a character array c is declared as char c[] = "abcd" in main(), the function call fX(c) will always return a value
- (C)The code of the function will not compile
- (D)Assuming a character pointer c is declared as char *c = "abcd" in main(), the function call fX(c) will always return a value
fX advances b to the terminating null character and returns the pointer difference, i.e. the string length; it is valid C and compiles (C false). A string literal, a char array initialised from a literal, and a char pointer to a literal are all null-terminated, so the loop always stops and fX returns 4 in each case. Answer: (A), (B), (D).
Concept: A strlen written with pointer subtraction. All three forms of "abcd" carry the terminating null, and the function only reads, so none of them misbehaves.
What is the output of the following C program?
#include <stdio.h>
int main() {
double a[2]={20.0, 25.0}, *p, *q;
p = a;
q = p + 1;
printf("%d,%d", (int)(q - p), (int)(*q - *p));
return 0;
}- (A)4,8
- (B)1,5
- (C)8,5
- (D)1,8
q = p + 1 points to the next double, and pointer subtraction counts elements, not bytes: q − p = 1. *q − *p = 25.0 − 20.0 = 5.0, cast to int gives 5. Both values are ints, so %d prints them correctly: 1,5. Answer: (B) 1,5.
Concept: Pointer arithmetic is scaled by element size: the difference of two double pointers is in elements. The trap is answering 8 (sizeof(double)).
You are given a set V of distinct integers. A binary search tree T is created by inserting all elements of V one by one, starting with an empty tree. The tree T follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which these values were inserted into T, and you do not have access to T.
Which one of the following statements is TRUE?
- (A)Inorder traversal of T can be determined from V
- (B)Root node of T can be determined from V
- (C)Preorder traversal of T can be determined from V
- (D)Postorder traversal of T can be determined from V
For any BST, the inorder traversal lists the keys in increasing order, so it is just V sorted - independent of insertion order. The shape of T, and hence the root, preorder and postorder, depend on the insertion order (the root is the first inserted element), which is unknown. Answer: (A).
Concept: Inorder of a BST is always the sorted order. Other traversals encode the tree shape, which varies with insertion order.
Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400 (400 on top), whereas S2 is empty.
Only the following three operations are available:
PushToS2: Pop the top element from S1 and push it on S2.
PushToS1: Pop the top element from S2 and push it on S1.
GenerateOutput: Pop the top element from S1 and output it to the user.
Note that the pop operation is not allowed on an empty stack and the push operation is not allowed on a full stack.
Which of the following output sequences can be generated by using the above operations?
- (A)100, 200, 400, 300
- (B)200, 300, 400, 100
- (C)400, 200, 100, 300
- (D)300, 200, 400, 100
(A) Outputting 100 first needs 400, 300, 200 parked in S2, but S2 holds only 2 - impossible. (B) PushToS2 (400), PushToS2 (300), output 200, PushToS1, output 300, PushToS1, output 400, output 100 - possible. (C) Output 400, PushToS2 (300), output 200, output 100, PushToS1, output 300 - possible. (D) PushToS2 (400), output 300, output 200, PushToS1, output 400, output 100 - possible. Answer: (B), (C), (D).
Concept: Simulating stack permutations with a bounded auxiliary stack. The capacity of S2 is what rules out reaching the bottom element first.
Which one of the following sequences when stored in an array at locations A[1], . . . , A[10] forms a max-heap?
- (A)23, 17, 10, 6, 13, 14, 1, 5, 7, 12
- (B)23, 17, 14, 7, 13, 10, 1, 5, 6, 12
- (C)23, 17, 14, 6, 13, 10, 1, 5, 7, 15
- (D)23, 14, 17, 1, 10, 13, 16, 12, 7, 5
With 1-based indexing, the children of A[i] are A[2i] and A[2i+1]. (A): A[3] = 10 has child A[6] = 14 > 10, fails. (C): A[5] = 13 has child A[10] = 15, fails. (D): A[4] = 1 has children 12 and 7, fails. (B): 23 ≥ 17, 14; 17 ≥ 7, 13; 14 ≥ 10, 1; 7 ≥ 5, 6; 13 ≥ 12. Every parent is at least its children. Answer: (B).
Concept: Max-heap property: every node is at least as large as its children. Check each parent at index i against 2i and 2i+1; a sorted-looking prefix does not guarantee validity deep in the array.
Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?
- (A)SLLdel is O(1) and DLLdel is O(n)
- (B)Both SLLdel and DLLdel are O(log(n))
- (C)Both SLLdel and DLLdel are O(1)
- (D)SLLdel is O(n) and DLLdel is O(1)
To delete a node from a singly-linked list, its predecessor's next pointer must be changed, and the only way to find the predecessor is to walk from the head: O(n) in the worst case (the node may be last). In a doubly-linked list the node's prev pointer gives the predecessor directly, so unlinking takes a constant number of pointer updates: O(1). Answer: (D) SLLdel is O(n) and DLLdel is O(1).
Concept: The cost of deletion is the cost of finding the predecessor. The copy-next-node trick for singly-linked lists fails for the last node, so the worst case remains O(n).
The integer value printed by the ANSI-C program given below is ________.
#include<stdio.h>
int funcp(){
static int x = 1;
x++;
return x;
}
int main(){
int x,y;
x = funcp();
y = funcp()+x;
printf("%d\n", (x+y));
return 0;
}The static x in funcp is initialised once to 1 and keeps its value between calls. First call: x becomes 2 and returns 2, so main's x = 2. Second call: static x becomes 3 and returns 3, so y = 3 + 2 = 5. Printed value: x + y = 2 + 5 = 7. Answer: 7.
Concept: A static local variable is initialised once and persists across calls. The trap is re-initialising it to 1 on every call, which would give 2 + 4 = 6.
Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the maximum element from A. The operation Insert(A,key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations. When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
- (A)Both Extract-Max(A) and Insert(A,key) run in O(1).
- (B)Both Extract-Max(A) and Insert(A,key) run in O(log(n)).
- (C)Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(n).
- (D)Extract-Max(A) runs in O(1) whereas Insert(A,key) runs in O(log(n)).
Extract-Max removes the root, moves the last element to the root and sifts it down, at most the tree height: O(log n). Insert places the key at the end and sifts it up, again at most the height: O(log n). Neither can be O(1) in the worst case because restoring the heap may need a full root-to-leaf path. Answer: (B) Both run in O(log(n)).
Concept: Finding the max is O(1), but extracting it is O(log n) because of the heapify step. The trap is (D), which confuses Find-Max with Extract-Max.
Consider the C function foo and the binary tree shown. The tree has root 10; 10 has left child 5 and right child 11; 5 has left child 3 and right child 8; 11 has only a right child 13. When foo is called with a pointer to the root node of the given binary tree, what will it print?
typedef struct node {
int val;
struct node *left, *right;
} node;
int foo(node *p) {
int retval;
if (p == NULL)
return 0;
else {
retval = p->val + foo(p->left) + foo(p->right);
printf("%d ", retval);
return retval;
}
}- (A)3 8 5 13 11 10
- (B)3 5 8 10 11 13
- (C)3 8 16 13 24 50
- (D)3 16 8 50 24 13
foo prints after both recursive calls, i.e. in postorder, and each printed value is the sum of the subtree. Postorder: 3, 8, 5, 13, 11, 10. Sums: subtree 3 = 3; subtree 8 = 8; subtree 5 = 5 + 3 + 8 = 16; subtree 13 = 13; subtree 11 = 11 + 0 + 13 = 24; subtree 10 = 10 + 16 + 24 = 50. Output: 3 8 16 13 24 50. Answer: (C).
Concept: Postorder traversal returning subtree sums. The trap is (A), which prints node values in postorder rather than the accumulated sums.
Consider a sequence a of elements a0 = 1, a1 = 5, a2 = 7, a3 = 8, a4 = 9, and a5 = 2. The following operations are performed on a stack S and a queue Q, both of which are initially empty. I: push the elements of a from a0 to a5 in that order into S. II: enqueue the elements of a from a0 to a5 in that order into Q. III: pop an element from S. IV: dequeue an element from Q. V: pop an element from S. VI: dequeue an element from Q. VII: dequeue an element from Q and push the same element into S. VIII: Repeat operation VII three times. IX: pop an element from S. X: pop an element from S. The top element of S after executing the above operations is .
I: S (bottom to top) = 1 5 7 8 9 2. II: Q (front to back) = 1 5 7 8 9 2. III: pop 2, S = 1 5 7 8 9. IV: dequeue 1. V: pop 9, S = 1 5 7 8. VI: dequeue 5, Q = 7 8 9 2. VII: dequeue 7, push: S = 1 5 7 8 7. VIII: three more times: push 8, 9, 2, S = 1 5 7 8 7 8 9 2. IX: pop 2. X: pop 9. Top of S = 8. Answer: 8.
Concept: Careful simulation of LIFO vs FIFO. The usual error is miscounting "repeat VII three times" as three in total rather than three more after VII.
Consider the problem of reversing a singly linked list. To take an example, given the linked list below,
head → a → b → c → d → e → NULL
the reversed linked list should look like
head → e → d → c → b → a → NULL
Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?
- (A)The best algorithm for the problem takes θ(n) time in the worst case.
- (B)The best algorithm for the problem takes θ(n log n) time in the worst case.
- (C)The best algorithm for the problem takes θ(n²) time in the worst case.
- (D)It is not possible to reverse a singly linked list in O(1) space.
Walk the list once with three pointers prev, curr, next: save next = curr->next, set curr->next = prev, advance prev = curr, curr = next. At the end set head = prev. Each node is touched once and only three pointers are used, so time θ(n) and space O(1). Every node's link must change, so Ω(n) is also needed. Answer: (A).
Concept: In-place iterative pointer reversal. The trap is thinking O(1) space forces repeated scans (θ(n²)) or that recursion is required.
What is printed by the following ANSI C program?
#include<stdio.h>
int main(int argc, char *argv[])
{
int x = 1, z[2] = {10, 11};
int *p = NULL;
p = &x;
*p = 10;
p = &z[1];
*(&z[0] + 1) += 3;
printf("%d, %d, %d\n", x, z[0], z[1]);
return 0;
}- (A)1, 10, 11
- (B)1, 10, 14
- (C)10, 14, 11
- (D)10, 10, 14
p = &x and *p = 10 set x = 10. p is then pointed at z[1] but not used for writing. &z[0] + 1 is the address of z[1], so *(&z[0] + 1) += 3 makes z[1] = 11 + 3 = 14. z[0] stays 10. Output: 10, 10, 14. Answer: (D).
Concept: Pointer arithmetic: &z[0] + 1 equals &z[1]. The trap is thinking the write goes to z[0] or that x is unchanged.
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index_____________.
Complete tree with 1000 nodes in array form: node i has children 2i+1 and 2i+2. Largest element = rightmost node: 0 → 2 → 6 → 14 → 30 → 62 → 126 → 254 → 510; its right child 1022 does not exist, so the maximum is at 510. 510 has no left child (1021 > 999), so the 2nd largest is its parent 254. The 3rd largest is the maximum of 254's left subtree, rooted at 509; 509's children (1019, 1020) do not exist, so it is 509. Answer: 509.
Concept: In-order predecessor in a BST: max of left subtree, else nearest ancestor from which you came right. Heap-style indexing locates the nodes. The trap is assuming the largest is at the last index 999.
What is printed by the following ANSI C program?
#include<stdio.h>
int main(int argc, char *argv[])
{
int a[3][3][3] =
{{1, 2, 3, 4, 5, 6, 7, 8, 9},
{10, 11, 12, 13, 14, 15, 16, 17, 18},
{19, 20, 21, 22, 23, 24, 25, 26, 27}};
int i = 0, j = 0, k = 0;
for( i = 0; i < 3; i++ ){
for(k = 0; k < 3; k++ )
printf("%d ", a[i][j][k]);
printf("\n");
}
return 0;
}- (A)1 2 3
10 11 12
19 20 21
- (B)1 4 7
10 13 16
19 22 25
- (C)1 2 3
4 5 6
7 8 9
- (D)1 2 3
13 14 15
25 26 27
Each inner brace initialises one a[i] (a 3×3 block) in row-major order: a[0] = 1..9, a[1] = 10..18, a[2] = 19..27. Within a[i], a[i][0][k] is the first row: elements 1-3 of that block. j stays 0 throughout. So the loop prints a[0][0][0..2] = 1 2 3, a[1][0][0..2] = 10 11 12, a[2][0][0..2] = 19 20 21, one line each. Answer: (A).
Concept: Brace elision fills a sub-aggregate in row-major order. The trap is assuming j advances (it is never changed) or that k steps by a row (option B).
What is printed by the following ANSI C program?
ASCII encoding for relevant characters: A = 65, B = 66, C = 67, ..., Z = 90; a = 97, b = 98, c = 99, ..., z = 122; * = 42, + = 43, − = 45.
#include<stdio.h>
int main(int argc, char *argv[]){
char a = 'P';
char b = 'x';
char c = (a & b) + '*';
char d = (a | b) - '-';
char e = (a ^ b) + '+';
printf("%c %c %c\n", c, d, e);
return 0;
}- (A)z K S
- (B)122 75 83
- (C)* - +
- (D)P x +
'P' = 80 = 0101 0000 and 'x' = 120 = 0111 1000. a & b = 0101 0000 = 80; 80 + 42 = 122 = 'z'. a | b = 0111 1000 = 120; 120 − 45 = 75 = 'K'. a ^ b = 0010 1000 = 40; 40 + 43 = 83 = 'S'. %c prints characters: z K S. Answer: (A).
Concept: Bitwise operators on character codes, then printing with %c. The trap is (B), the same values printed as integers.
Consider the queues Q1 containing four elements and Q2 containing none (shown as the Initial State). The only operations allowed on these two queues are Enqueue(Q, element) and Dequeue(Q). The minimum number of Enqueue operations on Q1 required to place the elements of Q1 in Q2 in reverse order (shown as the Final State) without using any additional storage is___________.
Initial State: Q1 = [1, 2, 3, 4] (head at 1), Q2 empty.
Final State: Q1 empty, Q2 = [4, 3, 2, 1] (head at 4).
Use Q2 itself, rotating it. Dequeue 1 from Q1, enqueue to Q2: [1]. Dequeue 2, enqueue to Q2: [1, 2]; rotate Q2 once (dequeue 1, enqueue 1): [2, 1]. Dequeue 3, enqueue: [2, 1, 3]; rotate twice: [3, 2, 1]. Dequeue 4, enqueue: [3, 2, 1, 4]; rotate three times: [4, 3, 2, 1]. No element is ever enqueued back into Q1. Answer: 0.
Concept: Rotating a queue (dequeue then enqueue to the same queue) moves the newest element to the front. The question counts only Enqueue operations on Q1, which is the trap.
What is printed by the following ANSI C program?
#include<stdio.h>
int main(int argc, char *argv[])
{
int x = 1, z[2] = {10, 11};
int *p = NULL;
p = &x;
*p = 10;
p = &z[1];
*(&z[0] + 1) += 3;
printf("%d, %d, %d\n", x, z[0], z[1]);
return 0;
}
- (A)1, 10, 11
- (B)1, 10, 14
- (C)10, 14, 11
- (D)10, 10, 14
p = &x; *p = 10; -> x becomes 10 (was 1).
p = &z[1]; -> p now points at z[1] (this line alone changes nothing yet - it only repoints p).
*(&z[0] + 1) += 3; -> &z[0]+1 is the same address as &z[1] (pointer arithmetic on an int array), so this adds 3 to z[1]: 11 + 3 = 14.
Final values: x=10, z[0]=10 (never touched), z[1]=14.
printf prints: 10, 10, 14 -> option (d).
Concept: The trap is assuming `p = &z[1];` itself changes z[1] - it only repoints the pointer p, it never dereferences or writes anything. The actual write to z[1] happens on the NEXT line, via `&z[0] + 1`, a completely separate pointer expression that happens to also reach z[1].
Consider the following C program.
The output of this program is:
#include<stdio.h>
struct Ournode{
char x,y,z;
};
int main(){
struct Ournode p = {'1', '0', 'a'+2};
struct Ournode *q = &p;
printf ("%c, %c", *((char*)q+1), *((char*)q+2));
return 0;
}- (A)0, c
- (B)0, a+2
- (C)'0', 'a+2'
- (D)'0', 'c'
The struct holds three chars x = '1', y = '0', z = 'a' + 2 = 'c'. Chars have no padding between them, so (char*)q points at x, (char*)q + 1 at y and (char*)q + 2 at z. %c prints the character itself without quotes: 0 and c. Output: 0, c. Answer: (A).
Concept: Casting a struct pointer to char* and doing byte arithmetic; 'a'+2 is evaluated as the character 'c'. Traps: thinking %c prints quotes, or that 'a'+2 is stored as text.
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.
(Figure: head points to the first node; each node points to the next; tail points to the last node, whose next pointer is NULL.)
Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?
- (A)θ(1), θ(1)
- (B)θ(1), θ(n)
- (C)θ(n), θ(1)
- (D)θ(n), θ(n)
Enqueue at the head: create a node, point its next to the old head, update head. θ(1). Dequeue at the tail: the last node must be removed and tail moved to its predecessor, but a singly linked list has no back pointer, so we must walk from head to the second-last node. θ(n). Answer: (B) θ(1), θ(n).
Concept: Deleting from the end of a singly linked list needs the predecessor, which costs a traversal even with a tail pointer. The trap is assuming the tail pointer alone makes deletion O(1); it only makes insertion at the tail O(1).
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 ______.
The last postorder element, 1, is the root. Inorder splits into left {8,6,9,4,7,2,5} and right {3}. In the left part the postorder ends with 2, so 2 is its root, with left {8,6,9,4,7} and right {5}. Next root is 4, with left {8,6,9} and right {7}. Then 6 is the root of {8,6,9}, with children 8 and 9. Longest path: 1-2-4-6-8, which has 4 edges. Answer: 4.
Concept: Rebuild the tree recursively: postorder gives the root (last element), inorder splits left and right subtrees. The trap is counting nodes (5) instead of edges, since height here is a path length.
Consider the following C program:
The output of this program is _____.
#include <stdio.h>
int counter = 0;
int calc (int a, int b) {
int c;
counter++;
if (b==3) return (a*a*a);
else {
c = calc(a, b/3);
return (c*c*c);
}
}
int main (){
calc(4, 81);
printf ("%d", counter);
}Each call increments counter once. Calls: calc(4, 81) calls calc(4, 27), which calls calc(4, 9), which calls calc(4, 3); that one hits b == 3 and returns. That is 4 calls in total, so counter = 4 and the program prints 4. (The returned value overflows int, but it is never printed.) Answer: 4.
Concept: Count recursive calls, not the computed value: b goes 81, 27, 9, 3. The trap is getting distracted by the cube computations or stopping the count before the base-case call.
Consider the following C program:
The output of the program above is
#include<stdio.h>
void fun1(char *s1, char *s2){
char *tmp;
tmp = s1;
s1 = s2;
s2 = tmp;
}
void fun2(char **s1, char **s2){
char *tmp;
tmp = *s1;
*s1 = *s2;
*s2 = tmp;
}
int main(){
char *str1 = "Hi", *str2 = "Bye";
fun1(str1, str2); printf("%s %s ", str1, str2);
fun2(&str1, &str2); printf("%s %s", str1, str2);
return 0;
}- (A)Hi Bye Bye Hi
- (B)Hi Bye Hi Bye
- (C)Bye Hi Hi Bye
- (D)Bye Hi Bye Hi
fun1 receives copies of the pointers and swaps only its local copies, so str1 and str2 in main are unchanged: prints "Hi Bye ". fun2 receives the addresses of str1 and str2 and swaps the pointers they hold, so now str1 points to "Bye" and str2 to "Hi": prints "Bye Hi". Output: Hi Bye Bye Hi. Answer: (A).
Concept: C passes everything by value; to change a caller's pointer you must pass a pointer to it (char**). The trap is believing fun1 swaps because it takes pointers.
Consider the following C code. Assume that unsigned long int type length is 64 bits.
The value returned when we call fun with the input 2⁴⁰ is
unsigned long int fun(unsigned long int n){
unsigned long int i, j = 0, sum = 0;
for (i = n; i > 1; i = i/2) j++;
for ( ; j > 1; j = j/2) sum++;
return(sum);
}- (A)4
- (B)5
- (C)6
- (D)40
First loop: i halves from 2⁴⁰ down to 1, running 40 times, so j = 40 (j = log₂ n). Second loop: j goes 40 → 20 → 10 → 5 → 2 → 1, incrementing sum each time while j > 1: 5 iterations. sum = 5 (that is floor(log₂ 40)). Answer: (B) 5.
Concept: Nested logarithms: the result is floor(log₂(log₂ n)). The trap is computing log₂ 40 ≈ 5.3 and rounding to 6, or stopping the trace one step early.
Consider the following program written in pseudo-code. Assume that x and y are integers.
The number of times that the print statement is executed by the call Count(1024,1024) is _____.
Count(x,y) {
if (y != 1){
if (x != 1) {
print("*");
Count(x/2, y);
}
else {
y = y-1;
Count(1024, y);
}
}
}For a fixed y ≠ 1, x halves from 1024 down to 1, printing once for each x in 1024, 512, ..., 2: that is 10 prints. When x reaches 1, y drops by one and x resets to 1024. This repeats for y = 1024, 1023, ..., 2, which is 1023 values; at y = 1 the function stops without printing. Total = 1023 × 10 = 10230. Answer: 10230.
Concept: Nested iteration written as recursion: an outer counter y and an inner halving x (log₂ 1024 = 10 prints). The trap is using 1024 rounds instead of 1023, since y = 1 prints nothing.
The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _____.
A 7-node heap is a complete tree: a root with two subtrees of 3 nodes each. The root must be 1. Choose which 3 of the remaining 6 values go to the left subtree: C(6,3) = 20. In a 3-node subtree the smallest value must be its root and the other two can be in either order: 2 ways for each subtree. Total = 20 × 2 × 2 = 80. Answer: 80.
Concept: Recurrence H(n) = C(n - 1, L) × H(L) × H(R), where L and R are the fixed subtree sizes of the complete tree. The trap is forcing 2 and 3 to be the root's children; 3 can sit below 2 in the same subtree.
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)?
- (A)Both operations can be performed in O(1) time
- (B)At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
- (C)The worst case time complexity for both operations will be Ω(n)
- (D)Worst case time complexity for both operations will be Ω(log n)
Use a circular array with front and rear indices. ENQUEUE writes at rear and advances rear modulo the array size; DEQUEUE reads at front and advances front modulo the size. Neither shifts elements, so both run in O(1). Answer: (A).
Concept: Circular buffer implementation of a queue. The trap is imagining a linear array that shifts elements on every dequeue, which costs Ω(n).
Consider the following C program.
Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?
void f(int, short);
void main()
{
int i = 100;
short s = 12;
short *p = &s;
__________ ; // call to f()
}- (A)f(s,*s)
- (B)i = f(i,s)
- (C)f(i,*s)
- (D)f(i,*p)
s is a short, not a pointer, so *s is invalid; this rules out (A) and (C). f returns void, so assigning its result to i is a type error; this rules out (B). In (D), i is int and *p dereferences a short pointer to give a short, matching f(int, short). Answer: (D) f(i,*p).
Concept: Type checking of function calls: argument types, dereferencing only pointers, and void return values. The trap is (B), which looks harmless but uses a void result as a value.
Consider the following C program.
The output of the program is ________.
#include<stdio.h>
void mystery(int *ptra, int *ptrb) {
int *temp;
temp = ptrb;
ptrb = ptra;
ptra = temp;
}
int main() {
int a=2016, b=0, c=4, d=42;
mystery(&a, &b);
if (a < c)
mystery(&c, &a);
mystery(&a, &d);
printf("%d\n", a);
}mystery swaps its local copies of the pointers, never the values they point to (it never writes through *ptra or *ptrb). So no call changes a, b, c or d. a stays 2016; a < c is false so the second call is skipped anyway; the third call also changes nothing. Output: 2016.
Concept: C passes pointers by value: swapping the pointer variables inside a function has no effect on the caller. The trap is assuming a swap of the integers happened.
The following function computes the maximum value contained in an integer array p[] of size n (n >= 1).
The missing loop condition is
int max(int *p, int n) {
int a=0, b=n-1;
while (__________) {
if (p[a] <= p[b]) { a = a+1; }
else { b = b-1; }
}
return p[a];
}- (A)a != n
- (B)b != 0
- (C)b > (a + 1)
- (D)b != a
Each iteration discards the smaller of p[a] and p[b] (moving a right or b left), so the maximum always stays within [a, b]. When a == b only one candidate remains, and it is the maximum, so the loop must run while b != a.
(A) and (B) let a or b run past each other. (C) stops with two candidates left and returns p[a] even if p[b] is larger, e.g. p = {1, 2}. Answer: (D) b != a.
Concept: Loop invariant reasoning: the maximum lies in p[a..b]. The trap is (C), which stops one step early.
What will be the output of the following C program?
void count(int n){
static int d=1;
printf("%d ", n);
printf("%d ", d);
d++;
if(n>1) count(n-1);
printf("%d ", d);
}
void main(){
count(3);
}- (A)3 1 2 2 1 3 4 4 4
- (B)3 1 2 1 1 1 2 2 2
- (C)3 1 2 2 1 3 4
- (D)3 1 2 1 1 1 2
d is static, so all calls share one d, initialised once.
count(3): prints 3 1; d = 2; calls count(2).
count(2): prints 2 2; d = 3; calls count(1).
count(1): prints 1 3; d = 4; no call; prints 4.
Back in count(2): prints 4. Back in count(3): prints 4.
Output: 3 1 2 2 1 3 4 4 4. Answer: (A).
Concept: Static locals persist across recursive calls; the final printf runs on the way back up, once per call. The traps are treating d as fresh per call or forgetting the unwinding prints.
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?
- (A)O(1)
- (B)O(d) but not O(1)
- (C)O(2ᵈ) but not O(d)
- (D)O(d·2ᵈ) but not O(2ᵈ)
Move the last element of the array into position i and shrink the heap. The moved element may violate the heap property with its parent or its children, so sift it up or down as needed. Either direction moves along a single root-to-leaf path, at most d swaps, so O(d). It is not O(1) in general, since the element may need to travel the full height. Answer: (B).
Concept: Arbitrary deletion in a heap = replace with last element, then heapify up or down along one path. The trap is thinking the whole heap must be rebuilt (O(2ᵈ), i.e. O(n)).
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 ________.
while Q is not Empty do
if S is Empty OR Top(S) ≤ Head(Q) then
x := Dequeue(Q);
Push(S, x);
else
x := Pop(S);
Enqueue(Q, x);
end
endThe loop builds a non-decreasing stack: an element is pushed only if it is not smaller than the top; otherwise the top is popped and sent to the back of the queue. The worst case is when the smallest element is last, e.g. 1, 2, ..., 15, 0 (with n = 16). The first 15 elements are pushed (15 iterations), then 0 forces all 15 to be popped back to the queue (15 iterations), then 0 is pushed, and the 15 elements cycle again; each 'round' fixes one more element. Counting all rounds gives n² iterations; a brute-force check over all permutations for n = 1..7 confirms the maximum is exactly n². For n = 16: 16² = 256. Answer: 256.
Concept: Analysing a stack-queue sorting loop for its worst-case input. The trap is answering 2n or n(n+1)/2 by counting only pushes, not the pops that send elements back to the queue.
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 ______.
BFS visits level by level. To make t as late as possible, levels 0 to 3 are full and t is the last vertex of a full level 4. Vertices before level 4: 1 + 2 + 4 + 8 = 15; level 4 holds at most 16. So t can be vertex 15 + 16 = 31. Answer: 31.
Concept: BFS order on a tree is level order. A complete binary tree maximises the position of a depth-4 vertex: 2⁵ - 1. Off-by-one errors on the number of levels are the usual trap.
The value printed by the following program is ______.
void f(int* p, int m){
m = m + 5;
*p = *p + m;
return;
}
void main(){
int i=5, j=10;
f(&i, j);
printf("%d", i+j);
}j is passed by value, i by address. Inside f, m = 10 + 5 = 15 (a local copy) and *p = 5 + 15 = 20, so i becomes 20 while j stays 10. Printed value = 20 + 10 = 30. Answer: 30.
Concept: Call by value versus passing a pointer: changing m does not affect j, writing through p does change i. Adding 5 to j as well (35) is the trap.
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(log N) insert, O(log N) find, and Θ(N) decrease-key. What is the time complexity of all these operations put together?
- (A)O(log² N)
- (B)O(N)
- (C)O(N²)
- (D)Θ(N² log N)
Delete with a pointer in a doubly linked list is O(1), so Θ(N) deletes cost O(N). Insert into a sorted list needs a linear scan, O(N) each: O(N log N) total. Find is also O(N) each: O(N log N). Decrease-key must move the node backward to keep the order, O(N) each, and Θ(N) of them cost O(N²). Total O(N²). Answer: (C) O(N²).
Concept: Per-operation costs on a sorted doubly linked list: pointer deletes are O(1), searching and repositioning are linear. The Θ(N) decrease-keys dominate.
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 ______.
In a min-heap every ancestor of a node holds a smaller key. Only 1 to 8 are smaller than 9, so 9 can have at most 8 ancestors, i.e. depth at most 8. This is achievable: place 1, 2, ..., 8 along one root-to-node path at depths 0 to 7 and 9 below at depth 8. The heap of 1023 nodes has depths 0 to 9, so depth 8 exists. Answer: 8.
Concept: Heap order bounds depth by the number of smaller keys. Also check that the tree is deep enough (1023 nodes give depth 9). Answering 9 forgets that only eight keys are smaller.
The following function computes Xʸ for positive integers X and Y.
Which one of the following conditions is TRUE before every iteration of the loop?
int exp(int X, int Y) {
int res = 1, a = X, b = Y;
while ( b != 0 ){
if ( b%2 == 0) { a = a*a; b = b/2; }
else { res = res*a; b = b-1; }
}
return res;
}- (A)Xʸ = aᵇ
- (B)(res * a)ʸ = (res * X)ᵇ
- (C)Xʸ = res * aᵇ
- (D)Xʸ = (res * a)ᵇ
Initially res = 1, a = X, b = Y, so res × aᵇ = Xʸ. Even b: a becomes a², b becomes b/2, and (a²)^(b/2) = aᵇ, so res × aᵇ is unchanged. Odd b: res becomes res × a and b becomes b - 1, and (res × a) × a^(b-1) = res × aᵇ, unchanged. So Xʸ = res × aᵇ holds before every iteration, and at b = 0 it gives res = Xʸ. (A) fails once res changes. Answer: (C).
Concept: Loop invariant for fast exponentiation: the quantity res × aᵇ stays equal to Xʸ. Check initialisation and preservation for both branches.
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:
- (A)+ - 1 6 7 * 2 ^ 5 - 3 4 *
- (B)- + 1 * 6 7 ^ 2 - 5 * 3 4
- (C)- + 1 * 7 6 ^ 2 - 5 * 4 3
- (D)1 7 6 * + 2 5 4 3 * - ^ -
Evaluate the RPN to get the tree: ((3 * 4) - 5) ^ 2 is the left operand and (6 * 7) + 1 the right operand of the root "-". New-order is root, right, left. Root: -. Right subtree "+": +, then its right 1, then its left "*": * 7 6. Left subtree "^": ^, its right 2, its left "-": -, then 5, then "*": * 4 3. Sequence: - + 1 * 7 6 ^ 2 - 5 * 4 3. Answer: (C).
Concept: Build the expression tree from postfix with a stack, then apply the custom order. New-order is the reverse of postorder. Option (B) swaps the order inside the leaf pairs, the usual slip.
Consider the following program:
Note: max(x,y) returns the maximum of x and y.
The value printed by this program is ______.
int f(int *p, int n)
{
if (n <= 1) return 0;
else return max(f(p+1,n-1),p[0]-p[1]);
}
int main()
{
int a[] = {3,5,2,6,4};
printf("%d", f(a,5));
}f returns the maximum of p[i] - p[i+1] over adjacent pairs, and 0 from the base case. Differences: 3 - 5 = -2, 5 - 2 = 3, 2 - 6 = -4, 6 - 4 = 2. Maximum of {0, -2, 3, -4, 2} = 3. Answer: 3.
Concept: Recognise what the recursion computes: the largest drop between adjacent elements, floored at 0. Reading p[0]-p[1] as p[1]-p[0] gives 4, the trap.
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 ______. Note: The height of a tree with a single node is 0.
7 nodes with height 6 means the tree is a single path. Each inserted key must be either the smallest or the largest of the keys still to be inserted, otherwise some later key would branch off. The last key is forced, and each of the first 6 insertions has 2 choices (current min or current max). Count = 2⁶ = 64. Answer: 64.
Concept: A degenerate (path) BST arises when each new key is an extreme of the remaining keys. Counting only fully sorted orders (2 ways) misses the zig-zag paths.
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?
- (A)Θ(n²)
- (B)Θ(n + m)
- (C)Θ(m²)
- (D)Θ(n⁴)
Memory is unlimited, so keep an n × n table of entry pointers (allocated without initialising, or with the standard O(1)-initialisation trick). Pass 1: for each vertex u and each entry [v] in its list, store a pointer to that entry at T[u][v]: O(n + m). Pass 2: for each entry [v] in u's list, set its twin to T[v][u]: O(n + m). Every list entry must be touched at least once, so Θ(n + m) is optimal. Answer: (B).
Concept: Unlimited memory permits direct addressing, turning lookups into O(1). Alternatively a radix-sort of the 2m (u, v) pairs also gives linear time. Initialising an n² table naively would cost Θ(n²), the trap behind (A).
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ᵃ logᵇ n). Then the value of a + 10b is __________.
Do one post-order traversal. For each node compute size(node) = 1 + size(left) + size(right), using the sizes already returned by the children, and increment a counter whenever size(node) = 4. Each node is processed once with O(1) work, so the time is O(n) = O(n¹ log⁰ n).
So a = 1, b = 0 and a + 10b = 1. Answer: 1.
Concept: Subtree sizes are computable bottom-up in a single post-order pass. The trap is recomputing each subtree's size from scratch, which suggests O(n²) or O(n log n).
Let A be a square matrix of size n × n. Consider the following pseudocode. What is the expected output?
C = 100;
for i = 1 to n do
for j = 1 to n do
{
Temp = A[i][j] + C;
A[i][j] = A[j][i];
A[j][i] = Temp - C;
}
for i = 1 to n do
for j = 1 to n do
output(A[i][j]);- (A)The matrix A itself
- (B)Transpose of the matrix A
- (C)Adding 100 to the upper diagonal elements and subtracting 100 from lower diagonal elements of A
- (D)None of the above
The body swaps A[i][j] and A[j][i] (Temp holds A[i][j] + 100, and Temp - 100 restores the original value, so C has no net effect).
Both loops run over all (i, j), so each off-diagonal pair is visited twice: once as (i, j) and once as (j, i). The second swap undoes the first. Diagonal elements are swapped with themselves.
The matrix is unchanged, and the output is A itself. Answer: (A).
Concept: Transposing in place must iterate only over j > i (or j < i). The trap is answering 'transpose' without noticing the full double loop swaps every pair twice.
Consider the following rooted tree with the vertex labeled P as the root. P has children Q and R (in that order). Q has one child S. R has children T, U and V (in that order). U has one child W.
The order in which the nodes are visited during an in-order traversal of the tree is
- (A)SQPTRWUV
- (B)SQPTUWRV
- (C)SQPTWUVR
- (D)SQPTRUWV
For a general (ordered) tree, in-order visits the first subtree, then the node, then the remaining subtrees left to right.
At P: in-order(Q), P, in-order(R).
in-order(Q) = in-order(S), Q = S Q.
in-order(R) = in-order(T), R, in-order(U), in-order(V) = T R W U V (U's first subtree is W, then U).
Result: S Q P T R W U V. Answer: (A) SQPTRWUV.
Concept: In-order on a non-binary tree: first child subtree, root, then the other children. The trap is visiting R only after all its children, as in post-order.
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(nᵃ logᵇ n + mᶜ logᵈ n), the value of a + 10b + 100c + 1000d is ____.
Search down the tree for L: O(log n) since the tree is balanced. Then do an in-order walk from there, adding each key until a key exceeds H. The walk visits the m keys in range plus O(log n) boundary nodes, so the total is O(log n + m).
Match O(nᵃ logᵇ n + mᶜ logᵈ n): a = 0, b = 1, c = 1, d = 0.
a + 10b + 100c + 1000d = 0 + 10 + 100 + 0 = 110. Answer: 110.
Concept: Range queries on a balanced BST cost O(log n + m). The trap is O(m log n), from searching for each in-range key separately.
How many distinct binary search trees can be created out of 4 distinct keys?
- (A)5
- (B)14
- (C)24
- (D)42
The number of distinct BSTs on n distinct keys is the nth Catalan number: C(n) = (2n)! / ((n+1)! * n!).
For n=4: C(4) = 8! / (5! * 4!) = 40320 / (120 * 24) = 40320 / 2880 = 14.
Cross-check via the recurrence t(n) = sum over i=0..n-1 of t(i)*t(n-1-i), with t(0)=t(1)=1:
t(2)=2, t(3)=5, t(4) = t(0)t(3)+t(1)t(2)+t(2)t(1)+t(3)t(0) = 5+2+2+5 = 14. Matches.
Concept: This is the canonical Catalan-number question - recognising 'count distinct BST shapes on n distinct keys' as exactly the Catalan number sequence (1,1,2,5,14,42,...) is much faster than deriving the recurrence from scratch under exam time pressure.
