# Programming and data structures questions and answers

## Programming and data structures questions and answers

(1) Consider a program that reads 500 integers in the range of [0, 100] that represents the score of 500 students. Frequency of each score above 50 is then printed. For the program to store the frequencies the best way is

(A) A dynamically allocated array of 550 numbers
(B) An array of 100 numbers
(C) An array of 500 numbers
(D) An array of 50 numbers

ANSWER: An array of 50 numbers

(2) What is the output of the following program?

Int f (int a, int *pb, int **ppc)
{
int b, c;
**ppc += 1;
c = *ppc;
*pb += 2;
b = *pb;
a += 3;
return a + b + c;
}
void main()
{
int z, *y, **x,
z = 4;
y = &z;
x = &y;
printf (“%d”, f (z, y, x));
}

(A) 19
(B) 18
(C) 22
(D) 24

(3) Consider a C variable declaration

int *i, j;

Which one of the following expression if used as left hand sides of assignment statements will not give compile time?

(A) i
(B) i
(C) j
(D) j

For Questions 4 and 5 refer to the data given below:
We have a binary max-heap that is implemented using an array.

(4) The array that represents a binary max-heap is

(A) {25, 12, 16, 13, 10, 8, 14}
(B) {25, 14, 16, 13, 10, 8, 12}
(C) {25, 14, 12, 13, 10, 8, 16}
(D) {25, 14, 13, 16, 10, 8, 12}

ANSWER: {25, 14, 16, 13, 10, 8, 12}

(5) On the correct answer to the previous question, the content of the array after two delete operations is

(A) {14, 13, 8, 12, 10}
(B) {14, 13, 12, 10, 8}
(C) {14, 12, 13, 8, 10}
(D) {14, 13, 12, 8, 10}

ANSWER: {14, 13, 12, 8, 10}

(6) What is the goal of structured programming?

(A) Able to infer the flow of control from the program text
(B) Able to infer the flow of control from the Compiled code
(C) To avoid the use of GOTO statements
(D) None of the above

ANSWER: Able to infer the flow of control from the program text

(7) Consider the two functions assg1 and assg2 given below:

int assg1(int *x, int y, int z)
{
int a = x[y + 2];
x[z] = a + 1;
return x[y + 2] – 3;
}

int assg2(int *x, int y, int z)
{
int t1 = y + 2;
int t2 = x[t1];
x[z] = t2 + 1;
return t2 – 3;
}

Let Y1 and Y2 are two statements about these two functions.
Y1 : The transformation from assg1 to assg2 is valid, i.e., for any program state and input arguments, assg2 will compute the same output and have the same effect on program state as assg1.
Y2 : All the transformations applied to assg1 to get assg2 will always improve the performance i.e. it will reduce CPU time of assg2 compared to assg1.

(A) Y1 is correct and Y2 is incorrect
(B) Y1 and Y2 both are correct
(C) Y1 is incorrect and Y2 is correct
(D) Y1 and Y2 both are incorrect

ANSWER: Y1 and Y2 both are correct

(8) To check whether an arithmetic expression has balanced parenthesis, the best data structure that can be used is

(A) Stack
(B) Tree
(C) List
(D) Queue

(9) Consider a stack S of size n ≥ 1 which is initially empty. In an empty stack first n natural numbers are pushed in sequence and then n pop operations are performed. Push and pop operations take x seconds each. The time elapse between the end of one stack operation and the start of the next operation is y. 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 stack S. What is the average stack-life of an element of this stack?

(A) 3y + 2x
(B) n (x + y) - x
(C) n (x + y)
(D) y + 2x

ANSWER: n (x + y) - x

(10) The logic programming languages and functional languages have the common properties that

(A) Both use Horn-clauses
(B) Both are declarative
(C) Both are procedural languages
(D) Both are based on ?-calculus.

(11) main()
{
int a, b, x, y;
scanf (“%d %d”, &a, &b);
/*Assume a and b are greater that 0 */
x = a;
y = b;
while(x != y)
{
if (x>y)
x = x - y;
else
y = y – x;
}
printf (“%d”, y);
}

Which one of the following statement is true for the above program?

(A) The program computes a mod b using repeated subtraction
(B) The program computes a ÷ b using repeated subtraction
(C) The program computes the least common multiple of a and b.
(D) The program computes the greatest common divisor of a and b.

ANSWER: The program computes the greatest common divisor of a and b.

(12) Consider a two dimensional array of integers arr[1…. 10][1…. 15]. One memory location is occupied by each integer. The first element of array is stored at location 100 and the array is stored in row-major order. The address of the element arr[i][j] is

(A) 15j + i + 84
(B) 15i + j + 84
(C) 21i + j + 93
(D) 21j + I + 93

ANSWER: 15i + j + 84

(13) Consider the set of operations as given below:

i. Deletion of the smallest element
ii. If the element is not already present then inserting an element.

For storing a set of integers a data structure is required in such a way that the above mentioned set of operations can be done in O(log n) time where n is the number of elements in the set.

The data structure that can be used for this purpose is

(A) A balanced binary search tree but not a heap
(B) A heap but not a balanced binary search tree
(C) Both a heap and a balanced binary search tree both
(D) Neither a heap nor a balanced binary search tree.

ANSWER: A balanced binary search tree but not a heap

(14) void swap (int x, int y)
{ int temp;
temp = x;
x = y;
y = temp;
}

Which one of the following statements hold true in order to exchange the values of two variables a and b?

(A) Swap (a, b) cannot be used, as the parameters are passed by value.
(B) Swap (a, b) cannot be used, as it does not return any value.
(C) Call swap (&a, &b)
(D) Call swap (a, b)

ANSWER: Swap (a, b) cannot be used, as the parameters are passed by value.

(15) Assuming that the height of a tree with a single node is 0, the maximum height of any AVL-tree with 7 nodes is

(A) 5
(B) 4
(C) 3
(D) 2

For Questions 16 and 17 refer to the data given below:

Unsigned int max (unsigned int, i, unsigned int a)
{
if i>0
return i%max (i/a, a);
else
return 0;
}
This recursive C function takes 2 arguments.

(16) When the function max is called as max (513, 2) the return value will be

(A) 2
(B) 1
(C) 7
(D) 6

(17) When the function max is called as max (345, 10) the return value will be

(A) 11
(B) 20
(C) 12
(D) 23

For Questions 18 and 19 refer to the data given below:

We have a 3-ary max heap, which is similar to a binary max heap, but instead of 2 children, nodes have 3 children. Representation of 3-ary max heap is as follows:
In the first location a root is stored. In the next level nodes are stored from left to right from a to a. The nodes from the second level of the tree from left to right are stored

from a location onward. Consider an item x that can be inserted into 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.

(18) The valid sequence of elements in an array representing 3-ary max heap is

(A) 9, 5, 6, 8, 3,1
(B) 9, 6, 3, 1, 8,5
(C) 9, 3, 6, 8, 5,1
(D) 1, 3, 5, 6, 8,9

ANSWER: 9, 5, 6, 8, 3,1

(19) Once the valid 3-ary heap is found from question 18, the elements 7, 2, 10 and 4 are inserted in that order into this 3-ary heap. The sequence of items in the array representing the resultant heap is

(A) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(B) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
(C) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
(D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5

ANSWER: 10, 7, 9, 8, 3, 1, 5, 2, 6, 4

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

(A) 2
(B) 4
(C) 3
(D) 8

(21) What is the output of the following program?

Char m[ ] = “HATE 2020”
Char *a = x;
Printf (“%s”, a + a – a);

(A) E2020
(B) 2020
(C) HATE 2020
(D) 020

(22) The order of precedence from highest to lowest is ∧, x, +, - assuming that the operators +, -, x are left associative and ∧ is right associative. The infix expression is a + b x c – d ∧ e ∧ f. The postfix expression corresponding to infix expression is

(A) -+axbc∧ ∧def
(B) ab+cxd-e∧f∧
(C) abc x +de∧f∧
(D) abcx+def∧ ∧-

(23) Which one of the following statement is true for Abstract Data type (ADT)?

(A) It is same as an abstract class
(B) It is a data type for which only the operations defined on it can be used but none else
(C) It is the data type that cannot be instantiated
(D) None of the above.

ANSWER: It is a data type for which only the operations defined on it can be used but none else

(24) Linked list are not suitable data structures of _________________

(A) Binary search
(B) Insertion sort
(C) Polynomial manipulation

(25) For efficiently converting an infix expression to the post fix form, use

(A) A parse tree
(B) An operand stack
(C) An operator stack
(D) Both an operator and an operand stack

(26) a = j;
b = 1;
while(a – b > ε)
{
a = (a + b)/2;
b = j / a;
}
print (a);

Assuming j > 1 and ε > 0, the algorithm will approximate to

(A) j1/3
(B) j1/2
(C) j²
(D) log j

(27) Consider a binary tree that is initially empty. The numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in a binary tree in that order. The binary search tree uses the usual ordering on natural numbers. The in-order traversal sequence of the resultant tree will be

(A) 7 6 5 4 8 9 0 1 2 3
(B) 1 9 2 7 3 8 5 6 0 4
(C) 0 1 2 3 4 5 6 7 8 9
(D) 0 3 2 5 6 4 8 1 9 7

ANSWER: 0 1 2 3 4 5 6 7 8 9

(28) Faster access to non-local variables is achieved using an array of pointers to activation records called a

(A) Activation tree
(B) Stack
(C) Heap
(D) None of the above

(29) To implement a queue of size n the minimum number of stacks of size n required is

(A) 4
(B) 3
(C) 2
(D) 1

(30) The C statement int ( *f)(int *), declares

(A) A pointer to a function that takes an integer pointer as argument and returns an integer.
(B) A function that takes an integer pointer as argument and returns a function pointer.
(C) A function that takes an integer as argument and returns an integer pointer
(D) A function that takes an integer pointer as argument and returns an integer

ANSWER: A pointer to a function that takes an integer pointer as argument and returns an integer

(31) Consider a binary tree whose inorder traversal is d b e a f c g and preorder traversal is a b d e c f g. What is the postorder traversal of the binary tree?

(A) d e f g b c a
(B) e d b f g c a
(C) e d b g f c a
(D) d e b f g c a

ANSWER: d e b f g c a

(32) begin
if (x == y)
{
D1;
Exit;
}
else,
if (i ==j)
{
D2;
}
else
{
D3;
Exit;
}
D4;
end

This program is to be tested for statement coverage. Let M1, M2, M3 and M4 be the test cases that are expressed in terms of the properties satisfied by the values of the variables x, y, i and
j. The exact values are not given.

M1 : x, y, i and j all are equal.
M2 : x, y, i and j all are different.
M3 : x = y and i != j
M4 : x != y and i = j

The test cases that ensures coverage of statements D1, D2, D3 and D4 is

(A) M1, M2 and M4
(B) M1, M2 and M3
(C) M1 and M4
(D) M2 and M4

(33) Program A1
var x:int :
procedure S(var t:int)
Begin
t = t+1
print t;
End

procedure M
Begin
var x:int;
x = 3;
S(x);
End
Begin \\begin A1
x = 10;
M;
End

Assume parameters are passed by reference and the language has dynamic scopping. The output of the program will be

(A) 11
(B) 10
(C) 3
(D) None of the above

(34) Consider four modules whose lengths are 200, 800, 600 and 500. These modules are read by a linker and are loaded in that order. The relocation constants are

(A) 0, 200, 1000, 1600
(B) 0, 200, 500, 600
(C) 200, 500, 600, 800
(D) 200, 700, 1300, 2100

(35) A value is returned by a function and the result thus returned under value–result and reference parameter passing conventions

(A) Do not differ
(B) May differ in the presence of exception
(C) Differ in all cases
(D) Differ in the presence of loops

ANSWER: Differ in the presence of loops

(36) int a, n;
a = 1;
while (a <=n)
a = a * 2;

For any value of n > 0, the number of comparisons made in the execution of the loop is

(A) [log2 n]
(B) [log2 n] +1
(C) [log2 n] - 1
(D) n

(37) A queue is represented by a circularly linked list and to access this queue single variable x is used. In order to perform both the operations en-queue and de-queue in constant time x should point to (A) Rear node
(B) Front node
(C) Any node after the front node
(D) It is not possible with a single pointer

ANSWER: It is not possible with a single pointer

(38) Consider an unlabelled binary tree with n number of nodes and a set of n distinct elements. With the given set, in how many ways the tree can be populated so that it becomes a binary search tree?

(A) (1 / n +1) 2n Cn
(B) n!
(C) 0
(D) 1

ANSWER: (1 / n +1) 2n Cn

(39) Match the following

List I List II
Q. Location counter 2. Garbage collection
R. Reference counts 3. Subroutine call

(A) P – 4, Q – 3, R – 2, S - 1
(B) P – 3, Q – 4, R – 2, S - 1
(C) P – 3, Q – 4, R – 2, S - 1
(D) P – 4, Q – 3, R – 1, S - 2

ANSWER: P – 3, Q – 4, R – 2, S - 1

(40) Insertion of a record in a circular linked list organization involves modification of

(A) No pointers are required
(B) Multiple pointers
(C) 2 pointers
(D) 1 pointer

(41) PUSH(10), PUSH(20), POP, PUSH(10), PUSH(20), POP, POP, POP, PUSH(20), POP. This is the sequence of operation on stack. What will be the sequence of values that will be popped out?

(A) 20, 20, 10, 10, 20
(B) 20, 10, 10, 10, 20
(C) 20, 10, 20, 10, 20
(D) 20, 20, 10, 20, 10

ANSWER: 20, 20, 10, 10, 20

(42) Consider the expression a = (x > y)? ((x > z)? x : z) : ((y > z)? y : z).

To get the value 4 to the variable a the combination of integer variables x, y and z is

(A) x = 6, y = 5, z = 3
(B) x = 5, y = 4, z = 5
(C) x = 3, y = 4, z = 2
(D) x = 6, y = 3, z = 5

ANSWER: x = 3, y = 4, z = 2

(43) struct margin
{
int data;
struct margin * next;
};

int f(struct margin * m)
{
return ((m==NULL) II (m->next==NULL) II
((m->data <=m-> next-> data) && f (m->next)));
}
For the given linked list m, the function f returns 1, only if

(A) The elements in the list are sorted in the decreasing order of data value
(B) The elements in the list are sorted in non-decreasing order of data value
(C) The list is either empty or it has a single element
(D) All the elements in the list do not have same data value

ANSWER: All the elements in the list do not have same data value

(44) For what type of languages heap allocation is required?

(A) Languages that use dynamic scope rules
(B) Languages that support recursion
(C) Languages that support dynamic data structures
(D) None of the above

ANSWER: Languages that support dynamic data structures

(45) The programming language feature that cannot be implemented on a certain processor, which supports only immediate and the direct addressing modes is

(A) Pointers
(B) Records
(C) Arrays
(D) Recursive procedures with local variables

(46) Consider a binary tree that has n number of nodes and every node has an odd number of descendants. Every node is considered to be its own descendents. The number of nodes in the tree that have exactly one child is

(A) n/2
(B) n
(C) 1
(D) 0

(47) struct {
short a
union {
float m;
long n;
} x;
} z;

The object of type short occupy 2 byte of memory, float occupy 4 byte and long occupy 8 byte. Ignoring alignment considerations, the memory required for variable z is

(A) 20 byte
(B) 18 byte
(C) 10 byte
(D) 14 byte

(48) Why there are security concerns in case of dynamic linking?

(A) Because cryptographic procedures are not available for dynamic linking.
(B) Because security is dynamic
(C) Because linking is not secured
(D) Because the path for searching dynamic libraries is not known till runtime.

(49) We have an array arr[1… n] and a procedure reverse(arr, a, b) which reverses the order of elements in a between positions a and b (both inclusive). Consider the sequence given below:

reverse (arr, 1,s);
reverse (arr, s+1, n);
reverse (arr, 1, n)

where 1≤s≤n

This sequence will

(A) No changes will be made on arr
(B) Reverse all the elements of arr
(C) Rotate arr left by s positions
(D) None of the above

ANSWER: Rotate arr left by s positions

(50) The process in which load addresses are assigned to various parts of the program and to reflect the assigned addresses, code and date in a program are adjusted is called

(A) Relocation
(B) Symbol resolution
(C) Parsing
(D) Assembly

(51) What is the output of the following program?

#include
void f (int *a, int *b)
{ a = b;
*a = 2;
}
int x = 0, y = 1;
int main ()
{ f (&x, &y);
printf (“%d %d/n”, x, y);
return 0;
}

(A) 0 1
(B) 0 2
(C) 2 2
(D) 2 1

(52) In the nested representation of binary tree ABC, A is the node and B and C are the left and right sub trees respectively of node A. B and C may be NULL or they can be further nested.

The valid binary tree is

(A) (1 (2 3 4)(5 6 7))
(B) (1 (2 3 4) 5 6) 7)
(C) (1 (2 3 NULL)(4 5))
(D) (1 2 (4 5 6 7))

ANSWER: (1 (2 3 4)(5 6 7))

(53) Consider the macro definition as given below:

Mul a
Store b
end macro

In the above macro a and b are

(A) Actual parameters
(B) Formal parameters
(C) Variables
(D) Indentifiers

(54) The following integers are inserted in order and a binary tree is generated:

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. How many nodes are in the left and right subtree of the root respectively?

(A) (6, 5)
(B) (10, 1)
(C) (7, 4)
(D) (8, 3)

(55) What is the advantage of chained hash table (external hashing) over open addressing scheme?

(A) Easier deletion is possible
(B) Less space is required
(C) Worst case complexity of search operations is less
(D) None of the above

(56) What is the requirement for evaluating an expression without any embedded function calls?

(A) Two stack
(B) One stack
(C) In general case a turning machine is needed
(D) As many stacks as the height of an expression tree

(57) What is the output of the following program?

char p
char *x = “string”;
Int length = strlen(x);
for (i = 0;i p[i] = x[length –1];
printf (“%s”, p);

(A) string
(B) gnirt
(C) gnirts
(D) Output is not printed

(58) Match the following:

P : m = malloc (5); m = NULL; 1: Using dangling pointers
Q : free (x); x-> value = 5; 2: Using uninitialized pointers
R : char *m; *m = ‘s’; 3: Lost memory

(A) P – 2, Q – 1, R - 3
(B) P – 3, Q – 2, R - 1
(C) P – 3, Q – 1, R - 2
(D) P – 1, Q – 3, R - 2

ANSWER: P – 3, Q – 1, R - 2

(59) A postfix expression with single digit operands that is evaluated using stack is
8 2 3 ∧ / 2 3 * + 5 1 * - (where ∧ is the exponentiation operator).

What are the top two elements of the stack after the first * is evaluated?

(A) 1, 8
(B) 5, 7
(C) 2, 3
(D) 6, 1

(60) In the runtime environment, the languages that necessarily need heap allocation is

(A) The one that use global variables
(B) The one that allow dynamic data structures
(C) The one that support recursion
(D) The one that use dynamic scoping

ANSWER: The one that allow dynamic data structures