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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(3) Consider a C variable declaration

int *i[10], j[10][10];

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

(A) i[5]
(B) i[1][2]
(C) j[2][3]
(D) j[6]

View Answer / Hide Answer


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}

View Answer / Hide Answer


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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


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

View Answer / Hide Answer


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

View Answer / Hide Answer


(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

View Answer / Hide Answer


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

View Answer / Hide Answer


(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)

View Answer / Hide Answer


(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

View Answer / Hide Answer


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

View Answer / Hide Answer


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

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

View Answer / Hide Answer


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[0] root is stored. In the next level nodes are stored from left to right from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored

from a[4] location onward. 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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


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

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

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

View Answer / Hide Answer


(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∧ ∧-

View Answer / Hide Answer


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

View Answer / Hide Answer


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

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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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) j^1/3
(B) j^1/2
(C) j^²
(D) log j

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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) ²ⁿ Cn
(B) n!
(C) 0
(D) 1

View Answer / Hide Answer


(39) Match the following

List I List II
P. Activation record 1. Linking loader
Q. Location counter 2. Garbage collection
R. Reference counts 3. Subroutine call
S. Address relocation 4. Assembler

(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(47) struct {
short a[5]
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

View Answer / Hide Answer


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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer


(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

View Answer / Hide Answer

ANSWER: 0 2

(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))

View Answer / Hide Answer

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

(53) Consider the macro definition as given below:

macro Add a, b
Load b
Mul a
Store b
end macro

In the above macro a and b are

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

View Answer / Hide Answer

ANSWER: Formal parameters

(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)

View Answer / Hide Answer

ANSWER: (7, 4)

(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

View Answer / Hide Answer

ANSWER: Easier deletion is possible

(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

View Answer / Hide Answer

ANSWER: One stack

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

char p[20]
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

View Answer / Hide Answer

ANSWER: 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

View Answer / Hide Answer

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

View Answer / Hide Answer

ANSWER: 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

View Answer / Hide Answer

ANSWER: The one that allow dynamic data structures