SYLLABUS
Programming in C. Recursion. Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs.
Q1 – Consider the following C program:
#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;
}
Which one of the following statements is CORRECT?
(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
Ans – (C)
Explanation –
Since int a = 6 and b = 0, therefore
1st iteration
- while(a < 10) — Condition True
- a = a/12 + 1 = 6/12 + 1 = 0 + 1 [because of int]
- a += b means a gets the value of b and is increased by 1 So, a = 0 + 1 = 1
- Result is a = 1, b = 0
2nd iteration
- while(a < 10) — Condition True
- a = a/12 + 1 = 1/12 + 1 = 0 + 1 [because of int]
- a += b means a gets the value of b and is increased by 1 So, a = 0 + 1 = 1
- Result is a = 1, b = 0
Since, a is not increasing it always remains on 1 and b is 0. So, the loop will run forever.
Hence option C is the answer, the program gets stuck in an infinite loop.
Q2 – Consider the following C program:
#include <stdio.h>
void fX();
int main(){
fX();
return 0;
}
void fX(){
char a;
if((a=getchar()) != ’\n’)
fX();
if(a != ’\n’)
putchar(a);
}
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?
(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
Ans – (C)
Explanation – The program begins execution at the main() function, which invokes a function called fX().
Inside fX(), a character named a is read from input using getchar().
If a is not a newline character, the function invokes itself recursively to read the next character. The recursion continues until a newline character is read, at which point it stops.
The function will now start to return from the subsequent recursive calls. When the function returns from each recursive call, it checks to see if the character a is not a newline character. If it is not a newline character, it prints out that character using putchar(a). This is what causes the characters to be printed in reverse order of how they were read.
For example, if input was 1234 and was followed by a newline character, the function would read ‘1’, ‘2’, ‘3’ and then ‘4’. As the function starts to return, it prints ‘4′, then ‘3′, then ‘2’, then finally ‘1’.This is how the program ends with the output 4321. Therefore, this means the answer is (C).
Q3 – In a B+ tree, the requirement of at least half-full (50%) node occupancy is relaxed for which one of the following cases?
(A) Only the root node
(B) All leaf nodes
(C) All internal nodes
(D) Only the leftmost leaf node
Ans – (A)
Explanation – The significant rule for a B+ tree is that keeps it at least 50% full (no children or half-full nodes) helps to balance the B+ tree structure and keep the search efficient. However, this rule is relaxed only for the root node.
B+ Tree Properties –
- All nodes (except for the root) must contain at least ⌈n/2⌉ children, where n is the maximum number of children a node can have.
- All data records are only stored in leaf nodes.
- The leaf nodes are linked together to facilitate range searches.
Q4 – 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
Ans – (D)
Explanation – Heapifying an array is the act of transforming an array into a heap data type (either a max- or min-heap).
In a given max-heap, for each parent node, the value of each parent node is greater than or equal to the value of each of its children. The last non-leaf node is computed from the last element in the array, moving up toward element one in the array. Processing each parent node upward fixes the heap property of the nodes held to ensure a valid heap property.
Q5 – Consider the following C function definition.
int f(int x, int y) {
for (int i=0; i<y; i++) {
x = x+x+y;
}
return x;
}
Which of the following statements is/are TRUE about the above function?
(A) If the inputs are x=20, y=10, then the return value is greater than 220
(B) If the inputs are x=20, y=20, then the return value is greater than 220
(C) If the inputs are x=20, y=10, then the return value is less than 210
(D) If the inputs are x=10, y=20, then the return value is greater than 220
Ans – (B, D)
Explanation – x₁ = 2x₀ + y
x₂ = 2x₁ + y = 2(2x₀ + y) + y = 4x₀ + 3y
x₃ = 2x₂ + y = 8x₀ + 7y
So, we can say that
xₙ = 2ⁿ * x + (2ⁿ – 1) * y
Option (A) – 210*20 + (210-1)*10 = 20480 + 10230 = 30710
But 30710 is not greater than 220. Hence, its incorrect.
Option(B) – 220*20 + (220-1)*20
It is clearly seen that the result is greater than 220.
Option (C) – 210*20 + (210-1)*10 = 20480 + 10230 = 30710
But 30710 is greater than 210 (1024). Hence, its incorrect.
Option (D) – 220*10 + (220-1)*20
It is clearly seen that the result is greater than 220.
So, answer is option (B, D).