# Multiple choice question for engineering

## Set 1

1. Wagner–Fischer is a ____________ algorithm.

a) Brute force

b) Greedy

c) Dynamic programming

d) Recursive

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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;

### View Answer

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)

### View Answer

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)

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

## 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

### View Answer

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

a) True

b) False

### View Answer

3. What is the other name of weak heap ?

a) Min-heap

b) Max-heap

c) Relaxed -heap

d) Leonardo heap

### View Answer

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)

### View Answer

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) n^{2}

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

## 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

### View Answer

2. What are the applications of weight balanced tree?

a) dynamic sets, dictionaries, sequences, maps

b) heaps

c) sorting

d) storing strings

### View Answer

3. A node of the weight balanced tree has

a) key, left and right pointers, size

b) key, value

c) key, size

d) key

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

## 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

### View Answer

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

### View Answer

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

### View Answer

4. Disadvantages of xor lists

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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; new_node->nodepointerxored = xor (*head_ref, NULL); if (*head_pointer == NULL) { 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. } *head_pointer = new_node; }

how would you convert the english sentences in above to code

a)

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

b)

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

c) that cannot be achieved

d) both a and b are correct

### View Answer

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

### View Answer

## 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

### View Answer

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

### View Answer

3. What can be the minimum sum of digits for a 4 digit number?

a) 0

b) 1

c) 16

d) 36

### View Answer

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

### View Answer

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

### View Answer

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)

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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