Select Page
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

# Multiple choice question for engineering

## Set 1

1. Wagner–Fischer is a ____________ algorithm.
a) Brute force
b) Greedy
c) Dynamic programming
d) Recursive

Answer: c [Reason:] Wagner–Fischer belongs to the dynamic programming type of algorithms.

2. Wagner–Fischer algorithm is used to find ____________
a) Longest common subsequence
b) Longest increasing subsequence
c) Edit distance between two strings
d) All of the mentioned

Answer: c [Reason:] Wagner–Fischer algorithm is used to find the edit distance between two strings.

3. What is the edit distance between the strings “abcd” and “acbd” when the allowed operations are insertion, deletion and substitution?
a) 1
b) 2
c) 3
d) 4

Answer: b [Reason:] The string “abcd” can be changed to “acbd” by substituting “b” with “c” and “c” with “b”. Thus, the edit distance is 2.

4. For which of the following pairs of strings is the edit distance maximum?
a) sunday & monday
b) monday & tuesday
c) tuesday & wednesday
d) wednesday & thursday

Answer: d [Reason:] The edit distances are 2, 4, 4 and 5 respectively. Hence, the maximum edit distance is between the strings wednesday and thursday.

5. Consider the following implementation of the Wagner–Fischer algorithm:

```int get_min(int a, int b)
{
if(a < b)
return a;
return b;
}
int edit_distance(char *s1, char *s2)
{
int len1,len2,i,j,min;
len1 = strlen(s1);
len2 = strlen(s2);
int arr[len1 + 1][len2 + 1];
for(i = 0;i <= len1; i++)
arr[i][0] = i;
for(i = 0; i <= len2; i++)
arr[0][i] = i;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
if(s1[i - 1] == s2[j - 1])
{
if(arr[i-1][j-1] < min)
____________;
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1;
}
arr[i][j] = min;
}
}
return arr[len1][len2];
}```

Which of the following lines should be inserted to complete the above code?
a) arr[i][j] = min
b) min = arr[i-1][j-1] – 1;
c) min = arr[i-1][j-1].
d) min = arr[i-1][j-1] + 1;

Answer: c [Reason:] The line min = arr[i-1][j-1] completes the above code.

6. What is the time complexity of the Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?
a) O(1)
b) O(n+m)
c) O(mn)
d) O(nlogm)

Answer: c [Reason:] The time complexity of the Wagner–Fischer algorithm is O(mn).

7. What is the space complexity of the above implementation of Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?
a) O(1)
b) O(n+m)
c) O(mn)
d) O(nlogm)

Answer: c [Reason:] The space complexity of the above Wagner–Fischer algorithm is O(mn).

8. What is the output of the following code?

```#include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
if(a < b)
return a;
return b;
}
int edit_distance(char *s1, char *s2)
{
int len1,len2,i,j,min;
len1 = strlen(s1);
len2 = strlen(s2);
int arr[len1 + 1][len2 + 1];
for(i = 0;i <= len1; i++)
arr[i][0] = i;
for(i = 0; i <= len2; i++)
arr[0][i] = i;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
if(s1[i - 1] == s2[j - 1])
{
if(arr[i-1][j-1] < min)
min = arr[i-1][j-1];
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1;
}
arr[i][j] = min;
}
}
return arr[len1][len2];
}
int main()
{
char s1[] = "somestring", s2[] = "anotherthing";
int ans = edit_distance(s1, s2);
printf("%d",ans);
return 0;
}```

a) 6
b) 7
c) 8
d) 9

Answer: a [Reason:] The program prints the edit distance between the strings “somestring” and “anotherthing”, which is 6.

9. What is the value stored in arr[3][3] when the below code is executed?

```#include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
if(a < b)
return a;
return b;
}
int edit_distance(char *s1, char *s2)
{
int len1,len2,i,j,min;
len1 = strlen(s1);
len2 = strlen(s2);
int arr[len1 + 1][len2 + 1];
for(i = 0;i <= len1; i++)
arr[i][0] = i;
for(i = 0; i <= len2; i++)
arr[0][i] = i;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
if(s1[i - 1] == s2[j - 1])
{
if(arr[i-1][j-1] < min)
min = arr[i-1][j-1];
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1;
}
arr[i][j] = min;
}
}
return arr[len1][len2];
}
int main()
{
char s1[] = "somestring", s2[] = "anotherthing";
int ans = edit_distance(s1, s2);
printf("%d",ans);
return 0;
}```

a) 1
b) 2
c) 3
d) 4

Answer: c [Reason:] The value stored in arr[3][3] is 3.

10. What is the output of the following code?

```#include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
if(a < b)
return a;
return b;
}
int edit_distance(char *s1, char *s2)
{
int len1,len2,i,j,min;
len1 = strlen(s1);
len2 = strlen(s2);
int arr[len1 + 1][len2 + 1];
for(i = 0;i <= len1; i++)
arr[i][0] = i;
for(i = 0; i <= len2; i++)
arr[0][i] = i;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
if(s1[i - 1] == s2[j - 1])
{
if(arr[i-1][j-1] < min)
min = arr[i-1][j-1];
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1;
}
arr[i][j] = min;
}
}
return arr[len1][len2];
}
int main()
{
char s1[] = "abcd", s2[] = "dcba";
int ans = edit_distance(s1, s2);
printf("%d",ans);
return 0;
}```

a) 1
b) 2
c) 3
d) 4

Answer: d [Reason:] The program prints the edit distance between the strings “abcd” and “dcba”, which is 4.

## Set 2

1. Tick the properties of weak-heap.
a) Every node has value greater than the value of child node
b) Every right child of node has greater value than parent node
c) Every left child of node has greater value than parent node
d) None of the mentioned

Answer: b [Reason:] This is the property of a weak -heap.

2. Left child of parent node has value lesser than the parent node. Comment The statement True or False.
a) True
b) False

Answer: b [Reason:] Weak heap has no left child.

3. What is the other name of weak heap ?
a) Min-heap
b) Max-heap
c) Relaxed -heap
d) Leonardo heap

Answer: c [Reason:] Relaxed heap is just another name of weak heap.

4. What is the worst case time in searching minimum value in weak -heap?
a) O(log n)
b) O(n)
c) O(n logn)
d) O(1)

Answer: d [Reason:] Weak heap is an array based form that supports the operation of finding minimum in O(1).

5. The total comparisons in finding both smallest and largest elements are
a) 2*n +2
b) n + ((n+1)/2) -2
c) n+logn
d) n2

6. What is the complexity of given function of insertion.

```	insert(int n)
{
if(buffer_size()< maxi_biffer_size())
buffer_aar[ind]==n;
else
move_to_heap(buffer,buffer+maxi_buffer_size())
}```

a) O(logn)
b) amortized O(1)
c) O(n)
d) None of the mentioned

Answer: b [Reason:] e use a buffer array to store a fixed number of elements when the buffer is full the content of buffer is moved to heap.As a result the complexity is amotized O(1) .

7. Does there exist a heap with seven distinct elements so that the Inorder traversal gives the element in sorted order.
a) Yes
b) No

Answer: b [Reason:] No, The inorder traversal will not give elements in sorted order. As heap is implemented as either min-heap or max-heap ,the root will be have highest or lowest value than remaining values of the nodes .So this traversal will not give a sorted list.

8. The leaf node for a heap of height h will be at which position.
a) h
b) h-1
c) a or b
d) None of the mentioned

Answer: c [Reason:] A complete binary tree is also a heap so by the property of binary tree the leaf nodes will be must at height h or h-1.

## Set 3

1. What is a weight balanced tree?
a) A binary tree that stores the sizes of subtrees in nodes
b) A binary tree with an additional attribute of weight
c) A height balanced binary tree
d) A normal binary tree

Answer: a [Reason:] Unlike AVL and redblack trees which uses height and color as book keeping information, weight balanced trees use the size of subtrees.

2. What are the applications of weight balanced tree?
a) dynamic sets, dictionaries, sequences, maps
b) heaps
c) sorting
d) storing strings

Answer: a [Reason:] They are a type of self balancing trees which are mostly used in storing key-value pairs, which is mostly used in functional programming languages. they are very useful to maintain big set of ordered objects.

3. A node of the weight balanced tree has
a) key, left and right pointers, size
b) key, value
c) key, size
d) key

Answer: a [Reason:] As a weight balanced tree stores height of the subtrees, we need to use size as an additional attribute to every node. also value(for mappings) may be an optional attribute.

4. The size value of various nodes in a weight balanced tree are
leaf – zero
internal node – size of it’s two children
is this true?
a) true
b) false

Answer: a [Reason:] Size of a node k is size[k] = size[k.left] + 1 + size[k.right] and based on this the weight will be given as weight[k] = size[k] + 1.

5. What is the condition for a tree to be weight balanced. where a is factor and n is a node?
a) weight[n.left] >= a*weight[n] and weight[n.right] >= a*weight[n].
b) weight[n.left] >= a*weight[n.right] and weight[n.right] >= a*weight[n].
c) weight[n.left] >= a*weight[n.left] and weight[n.right] >= a*weight[n].
d) weight[n] is a non zero

Answer: a Explantion: The tree is said to be a-balanced if the condition is satisfied. and ‘a’ value will be determined during tree formation. large value of ‘a’ is more effective.

6. What are the operations that can be performed on weight balanced tree?
a) all basic operations and set intersection, set union and subset test
b) all basic operations
c) set intersection, set union and subset test
d) only insertion and deletion

Answer: a [Reason:] The speciality of a weight balanced tree is a part from basic operations we can perform collective operations like set intersection, which helps in rapid prototyping in functional programming languages.

7. Consider a weight balanced tree such that, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on k nodes can be described as
a) log2 n
b) log4/3 n
c) log3 n
d) log3/2 n

Answer: d [Reason:] Total number of nodes can be described by the recurrence T(n) = T((n-1)/3)) + T(2(n-1)/3) + 1 T(1) = 1. height of the tree will be H(n) = H(2/3(n-1)) + 1, H(1). drawing a recurrence tree and the cost at each level is 1 and the height will be log(3/2)n.

8. Why the below pseudo code where x is a value, wt is weight factor and t is root node can’t insert?

```WeightBalanceTreeNode insert(int x, int wt, WeightBalanceTreeNode k) :

if (k == null)
k = new WeightBalanceTreeNode(x, wt, null, null)
else if (x < t.element) :

k.left = insert (x, wt, k.left)
if (k.left.weight < k.weight)
k = rotateWithRightChild (k)

else if (x > t.element) :

k.right = insert (x, wt, k.right)
if (k.right.weight < k.weight)
k = rotateWithLeftChild (k)```

a) when x>t. element Rotate-with-left-child should take place and vice versa
b) the logic is incorrect
c) the condition for rotating children is wrong
d) insertion cannot be performed in weight balanced trees

Answer: a [Reason:] The rotations of children must be interchanged in the code.

9. What does the below definations convey?
i. A binary tree is balanced if for every node it is gonna hold that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.
ii. A binary tree is balanced if for any two leaves the difference of the depth is at most 1.
a) weight balanced and height balanced tree definations
b) height balanced and weight balanced tree definations
c) definations of weight balanced tree
d) definations of height balanced tree

Answer: a [Reason:] They are the definations of weight and height balanceness. height balanced trees wont convey weight balanceness but opposite can be true.

10. Elements in a tree can be indexed by its position under the ordering of the keys and the ordinal position of an element can be determined, both with good efficiency.
a) true
b) false

Answer: a [Reason:] In a weight balanced tree we can even store the key information so as to use as a key value pair.

## Set 4

1. What is xor linked list ?
a) uses of bitwise XOR operation to decrease storage requirements for doubly linked lists
b) uses of bitwise XOR operation to decrease storage requirements for linked lists
c) uses of bitwise operations to decrease storage requirements for doubly linked lists
d) just another form of linked list

Answer: a [Reason:] Why we use bitwise XOR operation is to decrease storage requirements for doubly linked lists.

2. What does a xor linked list have ?
a) every node stores the XOR of addresses of previous and next nodes
b) actuall memory address of next node
c) every node stores the XOR of addresses of previous and next two nodes
d) every node stores xor 0 and the current node address

3. What does first and last nodes of a xor linked lists contain ? (let address of first and last be A and B)
a) NULL xor A and B xor NULL
b) NULL and NULL
c) A and B
d) NULL xor A and B

Answer: a [Reason:] NULL xor A and B xor NULL.

a) Almost of debugging tools cannot follow the XOR chain, making debugging difficult
b) You need to remember the address of the previously accessed node in order to calculate the next node’s address
c) In some contexts XOR of pointers is not defined
d) All of the mentioned

Answer: d [Reason:] All the listed options are right.

5. What are the important properties of xor lists
a) X⊕X = 0
b) X⊕0 = X
c) (X⊕Y)⊕Z = X⊕(Y⊕Z)
d) All of the mentioned

Answer: d [Reason:] The above are properties of xor lists.

6. Which of the following statements are true ?
i) practical application of XOR linked lists are in environments with limited space requirements, such as embedded devices.
ii)xor lists are not suitable because most garbage collectors will fail to work properly with classes or structures that don’t contain literal pointers
iii)in order to calculate the address of the next node you need to remember the address of the previous node
iv)xor lists are much efficient than single, doubly linked lists and arrays
a) i,ii,iii,iv
b) i,ii,iii
c)i,ii
d)i

Answer: b [Reason:] Xor lists requires same time for most of the operations as arrays would require.

7. What’s wrong with this code which returns xor of two nodes address ?

```//struct is common userdefined datatype in c/c++ and class is it's alternative

struct node* XOR (struct node *a, struct node *b)
{
return  ((int) (a) ^ (int) (b));   //this logic is used to fill the nodes with address of a xor linked list
}```

a) nothing wrong. everything is fine
b) type casting at return is missing
c) parameters are wrong
d) total logic is wrong

Answer: b [Reason:] It must be typecasted– return (struct node*)((int) (a) (int) (b));

8. Given 10,8,6,7,9
swap the above numbers such that finally you got 6,7,8,9,10
so now reverse 10
9,7,6,8,10
now reverse 9
8,6,7,9,10
7,6,8,9,10
6,7,8,9,10
at this point 6 is ahead so no more reversing can be done so stop.
To implement above algorithm which datastructure is better and why ?
a) linked list. because we can swap elements easily
b) arrays. because we can swap elements easily
c) xor linked list. because there is no overhead of pointers and so memory is saved
d) doubly linked list. because you can traverse back and forth

Answer: c [Reason:] As in the option, you will store xored value of pointer rather than two pointers.

9. Consider insert at begin into xor linked list logic

```void xor-linked-list insert(struct node **head_ref, int value)
{
node *new_node  = new (struct node);
new_node->value = value;
{
printf("invalid");
}
else
{
let b,c,d are nodes and a is to be inserted at beginning, a address field must contain NULL xor b and b
address filed must be a xor c.
}
}```

how would you convert the english sentences in above to code
a)

```node* next = XOR ((*head_ref)->npx,  NULL);

b)

```node* next = XOR ((*head_ref)->npx,  NULL);

c) that cannot be achieved
d) both a and b are correct

Answer: a [Reason:] They code for the english is as shown in option a.

10. In the above question would using arrays and swaping of elements in place of xor linked list would have been more efficient ?
a) no not all
b) yes arrays would have been better than xor lists
c) both would be same in efficiency
d) can’t say

Answer: b [Reason:] The locality of a normal array is faster in memory and moreover one has to traverse n-nodes to reach the target to reverse in case of xor linked list.

## Set 5

1. Which of the following methods can be used to find the sum of digits of a number?
a) Recursion
b) Iteration
c) Greedy algorithm
d) Both recursion and iteration

Answer: d [Reason:] Both recursion and iteration can be used to find the sum of digits of a number.

2. What can be the maximum sum of digits for a 4 digit number?
a) 1
b) 16
c) 36
d) none of the mentioned

Answer: c [Reason:] The sum of digits will be maximum when all the digits are 9. Thus, the sum will be maximum for the number 9999, which is 36.

3. What can be the minimum sum of digits for a 4 digit number?
a) 0
b) 1
c) 16
d) 36

Answer: b [Reason:] The sum of digits will be minimum for the number 1000 and the sum is 1.

4. Consider the following iterative implementation to find the sum of digits of a number:

```#include<stdio.h>
int sum_of_digits(int n)
{
int sm = 0;
while(n != 0)
{
_________;
n /= 10;
}
return sm;
}
int main()
{
int n = 1234;
int ans = sum_of_digits(n);
printf("%d",ans);
return 0;
}```

Which of the following lines should be inserted to complete the above code?
a) sm += n
b) sm += n%10
c) sm += n-10
d) sm += n/10

Answer: b [Reason:] The line “sm += n % 10” adds the last digit(LSB) of the number to the current sum. Thus, the line “sm += n%10” should be added to complete the above code.

5. What is the output of the following code?

```#include<stdio.h>
int sum_of_digits(int n)
{
int sm = 0;
while(n != 0)
{
sm += n%10;
n /= 10;
}
return sm;
}
int main()
{
int n = 1234;
int ans = sum_of_digits(n);
printf("%d",ans);
return 0;
}```

a) 1
b) 3
c) 7
d) 10

Answer: d [Reason:] The above code prints the sum of digits of the number 1234, which is 10.

6. Consider the following recursive implementation to find the sum of digits of number:

```#include<stdio.h>
int recursive_sum_of_digits(int n)
{
if(n == 0)
return 0;
return _________;
}
int main()
{
int n = 1201;
int ans = recursive_sum_of_digits(n);
printf("%d",ans);
return 0;
}```

Which of the following lines should be inserted to complete the above code?
a) (n / 10) + recursive_sum_of_digits(n % 10)
b) (n) + recursive_sum_of_digits(n % 10)
c) (n % 10) + recursive_sum_of_digits(n / 10)
d) (n % 10) + recursive_sum_of_digits(n % 10)

Answer: c [Reason:] The line “(n % 10) + recursive_sum_of_digits(n / 10)” should be inserted to complete the above code.

7. What is the time complexity of the above recursive implementation to find the sum of digits of a number n?
a) O(n)
b) O(1)
c) O(len(n)), where len(n) is the number of digits in n
d) none of the mentioned

Answer: c [Reason:] The time complexity of the above recursive implementation to find the sum of digits of a number is O(len(n)).

8. What is the output of the following code?

```#include<stdio.h>
int recursive_sum_of_digits(int n)
{
if(n == 0)
return 0;
return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
int n = 1234321;
int ans = recursive_sum_of_digits(n);
printf("%d",ans);
return 0;
}```

a) 10
b) 16
c) 15
d) none of the mentioned

Answer: b [Reason:] The above code prints the sum of digits of the number 1234321, which is 16.

9. How many times is the function recursive_sum_of_digits() called when the following code is executed?

```#include<stdio.h>
int recursive_sum_of_digits(int n)
{
if(n == 0)
return 0;
return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
int n = 1201;
int ans = recursive_sum_of_digits(n);
printf("%d",ans);
return 0;
}```

a) 6
b) 7
c) 8
d) 9

Answer: c [Reason:] The function recursive_sum_of_digits() is called 8 times, when the following code is executed.

10. You have to find the sum of digits of a number given that the number is always greater than 0. Which of the following base cases can replace the base case for the below code?

```#include<stdio.h>
int recursive_sum_of_digits(int n)
{
if(n == 0)
return 0;
return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
int n = 1201;
int ans = recursive_sum_of_digits(n);
printf("%d",ans);
return 0;
}```

a) if(n == 0) return 1
b) if(n == 1) return 0
c) if(n == 1) return 1
d) none of the mentioned

Answer: d [Reason:] None of the above mentioned base cases can replace the base case if(n == 0) return 0.

11. What is the output of the following code?

```#include<stdio.h>
int recursive_sum_of_digits(int n)
{
if(n == 0)
return 0;
return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
int n = 10000;
int ans = recursive_sum_of_digits(n);
printf("%d",ans);
return 0;
}```

a) 0
b) 1
c) runtime error
d) none of the mentioned

Answer: b [Reason:] The program prints the sum of digits of the number 10000, which is 1.

12. What is the output of the following code?

```#include<stdio.h>
int cnt =0;
int my_function(int n, int sm)
{
int i, tmp_sm;
for(i=1;i<=n;i++)
{
tmp_sm = recursive_sum_of_digits(i);
if(tmp_sm == sm)
cnt++;
}
return cnt;
}
int recursive_sum_of_digits(int n)
{
if(n == 0)
return 0;
return n % 10 + recursive_sum_of_digits(n/10);
}
int main()
{
int n = 20, sum = 3;
int ans = my_function(n,sum);
printf("%d",ans);
return 0;
}```

a) 0
b) 1
c) 2
d) 3