Multiple choice question for engineering
Set 1
1. For the tree below, write the in-order traversal.
a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 6, 9, 5, 11, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9
Answer
Answer: d [Reason:] In-order traversal follows LNR(Left-Node-Right).
2. For the tree below, write the level-order traversal.
a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 6, 9, 5, 11, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9
Answer
Answer: b [Reason:] Level order traversal follows a breadth first search approach.
3. Select the code snippet which performs in-order traversal.
a)
public void inorder(Tree root) { System.out.println(root.data); inorder(root.left); inorder(root.right); }
b)
public void inorder(Tree root) { inorder(root.left); System.out.println(root.data); inorder(root.right); }
c)
public void inorder(Tree root) { System.out.println(root.data); inorder(root.right); inorder(root.left); }
d) None of the mentioned
Answer
Answer: b [Reason:] In-order traversal follows LNR(Left-Node-Right).
4. Select the code snippet which performs level-order traversal.
a)
public static void levelOrder(Tree root) { Queue<Node> queue=new LinkedList<Node>(); queue.add(root); while(!queue.isEmpty()) { Node tempNode=queue.poll(); System.out.println("%d ",tempNode.data); if(tempNode.left!=null) queue.add(tempNode.left); if(tempNode.right!=null) queue.add(tempNode.right); } }
b)
public static void levelOrder(Tree root) { Queue<Node> queue=new LinkedList<Node>(); queue.add(root); while(!queue.isEmpty()) { Node tempNode=queue.poll(); System.out.println("%d ",tempNode.data); if(tempNode.left!=null) queue.add(tempNode.right); if(tempNode.right!=null) queue.add(tempNode.left); } }
c)
public static void levelOrder(Tree root) { Queue<Node> queue=new LinkedList<Node>(); queue.add(root); while(!queue.isEmpty()) { Node tempNode=queue.poll(); System.out.println("%d ",tempNode.data); if(tempNode.right!=null) queue.add(tempNode.left); if(tempNode.left!=null) queue.add(tempNode.right); } }
d) None of the mentioned
Answer
Answer: a [Reason:] Firstly add the root node to the queue. Then for all the remaining nodes, pop the front end of the queue and print it, add the left and right children of the popped node to the queue.
5. What is the space complexity of the in-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)
a) O(1)
b) O(nlogd)
c) O(logd)
d) O(d)
Answer
Answer: d [Reason:] In the worst case we have d stack frames in the recursive call, hence the complexity is O(d).
6. What is the time complexity of level order traversal?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
Answer
Answer: b [Reason:] Since you have to go through all the nodes, the complexity becomes O(n).
7. Which of the following graph traversals closely imitates level order traversal of a binary tree?
a) Depth First Search
b) Breadth First Search
c) Both of the mentioned
d) None of the mentioned
Answer
Answer: b [Reason:] Both level order tree traversal and breadth first graph traversal follow the principle that visit your neighbors first and then move on to further nodes.
8. In a binary search tree, which of the following traversals would print the numbers in the ascending order?
a) Level-order traversal
b) Pre-order traversal
c) Post-order traversal
d) In-order traversal
Answer
Answer: d [Reason:] In a binary search tree, a node’s left child is always lesser than the node and right child is greater than the node, hence an in-order traversal would print them in a non decreasing fashion.
Set 2
1. Consider the following iterative implementation to find the length of the string:
#include<stdio.h> int get_len(char *s) { int len = 0; while(________) len++; return len; } int main() { char *s = "harsh"; int len = get_len(s); printf("%d",len); return 0; }
Which of the following lines should be inserted to complete the above code?
a) s[len-1] != 0
b) s[len+1] != 0
c) s[len] != ‘ ’
d) none of the mentioned
Answer
Answer: c [Reason:] The line “s[len] != ‘ ′” should be inserted to complete the above code.
2. What is the output of the following code?
#include<stdio.h> int get_len(char *s) { int len = 0; while(s[len] != ' ') len++; return len; } int main() { char *s = "lengthofstring"; int len = get_len(s); printf("%d",len); return 0; }
a) 14
b) 0
c) Compile time error
d) Runtime error
Answer
Answer: a [Reason:] The program prints the length of the string “lengthofstring”, which is 14.
3. What is the time complexity of the above code used to find the length of the string?
a) O(1)
b) O(n)
c) O(n2)
d) O(logn)
Answer
Answer: b [Reason:] The time complexity of the code used to find the length of the string is O(n).
4. What is the output of the following code?
#include<stdio.h> int get_len(char *s) { int len = 0; while(s[len] != ' ') len++; return len; } int main() { char *s = ""; int len = get_len(s); printf("%d",len); return 0; }
a) 0
b) 1
c) Runtime error
d) Garbage value
Answer
Answer: a [Reason:] The program prints the length of an empty string, which is 0.
5. Which of the following can be the base case for the recursive implementation used to find the length of a string?
a) if(string[len] == 1) return 1
b) if(string[len+1] == 1) return 1
c) if(string[len] == ‘ ’) return 0
d) if(string[len] == ‘ ’) return 1
Answer
Answer: c [Reason:] “if(string[len] == ‘ ’) return 0” can be used as base case in the recursive implementation used to find the length of the string.
6. Consider the following recursive implementation used to find the length of a string:
#include<stdio.h> int recursive_get_len(char *s, int len) { if(s[len] == 0) return 0; return ________; } int main() { char *s = "abcdef"; int len = recursive_get_len(s,0); printf("%d",len); return 0; }
Which of the following lines should be inserted to complete the above code?
a) 1
b) len
c) recursive_get_len(s, len+1)
d) 1 + recursive_get_len(s, len+1)
Answer
Answer: d [Reason:] The line “1 + recursive_get_len(s, len+1)” should be inserted to complete the code.
7. What is the output of the following code?
#include<stdio.h> int recursive_get_len(char *s, int len) { if(s[len] == 0) return 0; return 1 + recursive_get_len(s, len+1); } int main() { char *s = "abcdef"; int len = recursive_get_len(s,0); printf("%d",len); return 0; }
a) 5
b) 6
c) 7
d) 8
Answer
Answer: b [Reason:] The above code prints the length of the string “abcdef”, which is 6.
8. What is the time complexity of the above recursive implementation used to find the length of the string?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
Answer
Answer: b [Reason:] The time complexity of the above recursive implementation used to find the length of the string is O(n).
9. How many times is the function recursive_get_len() called when the following code is executed?
#include<stdio.h> int recursive_get_len(char *s, int len) { if(s[len] == 0) return 0; return 1 + recursive_get_len(s, len+1); } int main() { char *s = "adghjkl"; int len = recursive_get_len(s,0); printf("%d",len); return 0; }
a) 6
b) 7
c) 8
d) 9
Answer
Answer: c [Reason:] The function recursive_get_len() is called 8 times when the above code is executed.
10. What is the output of the following code?
#include<stdio.h> int recursive_get_len(char *s, int len) { if(s[len] == 0) return 0; return 1 + recursive_get_len(s, len+1); } int main() { char *s = "123-1-2-3"; int len = recursive_get_len(s,0); printf("%d",len); return 0; }
a) 3
b) 6
c) 9
d) 10
Answer
Answer: c [Reason:] The above program prints the length of the string “123-1-2-3”, which is 9.
Set 3
1. Where is linear searching used?
a) When the list has only a few elements
b) When performing a single search in an unordered list
c) Used all the time
d) Both a and b
Answer
Answer: d [Reason:] It is practical to implement linear search in the situations mentioned in a and b, but for larger elements the complexity becomes larger and it makes sense to sort the list and employ binary search or hashing.
2. Select the code snippet which performs unordered linear search iteratively?
a)
int unorderedLinearSearch(int arr[], int size, int data) { int index; for(int i = 0; i < size; i++) { if(arr[i] == data) { index = i; break; } } return index; }
b)
int unorderedLinearSearch(int arr[], int size, int data) { int index; for(int i = 0; i < size; i++) { if(arr[i] == data) { break; } } return index; }
c)
int unorderedLinearSearch(int arr[], int size, int data) { int index; for(int i = 0; i <= size; i++) { if(arr[i] == data) { index = i; break; } } return index; }
d) None of the mentioned
Answer
Answer: a [Reason:] Unordered term refers to the given array, that is, the elements need not be ordered. To search for an element in such an array, we need to loop through the elements until the desired element is found.
3. What is the best case for linear search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Answer
Answer: d [Reason:] The element is at the head of the array, hence O(1).
4. What is the worst case for linear search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(1)
Answer
Answer: c [Reason:] Worst case is when the desired element is at the tail of the array or not present at all, in this case you have to traverse till the end of the array, hence the complexity is O(n).
5. Select the code snippet which performs ordered linear search iteratively?
a)
public int linearSearch(int arr[],int key,int size) { int index = -1; int i = 0; while(size > 0) { if(data[i] == key) { index = i; } if(data[i] > key)) { index = i; break; } i++; } return index; }
b)
public int linearSearch(int arr[],int key,int size) { int index = -1; int i = 0; while(size > 0) { if(data[i] == key) { index = i; } if(data[i] > key)) { break; } i++; } return index; }
c)
public int linearSearch(int arr[],int key,int size) { int index = -1; int i = 0; while(size > 0) { if(data[i] == key) { break; } if(data[i] > key)) { index = i; } i++; } return index; }
d) None of the mentioned
Answer
Answer: b [Reason:] The term ordered refers to the items in the array being sorted(here we assume ascending order). So traverse through the array until the element, if at any time the value at i exceeds key value, it means the element is not present in the array. This provides a slightly better efficiency than unordered linear search.
6. What is the best case and worst case complexity of ordered linear search?
a) O(nlogn), O(logn)
b) O(logn), O(nlogn)
c) O(n), O(1)
d) O(1), O(n)
Answer
Answer: d [Reason:] Although ordered linear search is better than unordered when the element is not present in the array, the best and worst cases still remain the same, with the key element being found at first position or at last position.
7. Choose the code snippet which uses recursion for linear search.
a)
public void linSearch(int[] arr, int first, int last, int key) { if(first == last) { System.out.print("-1"); } else { if(arr[first] == key) { System.out.print(first); } else { linSearch(arr, first+1, last, key); } } }
b)
public void linSearch(int[] arr, int first, int last, int key) { if(first == last) { System.out.print("-1"); } else { if(arr[first] == key) { System.out.print(first); } else { linSearch(arr, first+1, last-1, key); } } }
c)
public void linSearch(int[] arr, int first, int last, int key) { if(first == last) { System.out.print("-1"); } else { if(arr[first] == key) { System.out.print(last); } else { linSearch(arr, first+1, last, key); } } }
d)
public void linSearch(int[] arr, int first, int last, int key) { if(first == last) { System.out.print("-1"); } else { if(arr[first] == key) { System.out.print(first); } else { linSearch(arr, first+1, last+1, key); } } }
Answer
Answer: a [Reason:] Every time check the key with the array value at first index, if it is not equal then call the function again with an incremented first index.
8. What does the following piece of code do?
for (int i = 0; i < arr.length-1; i++) { for (int j = i+1; j < arr.length; j++) { if( (arr[i].equals(arr[j])) && (i != j) ) { System.out.println(arr[i]); } } }
a) Print the duplicate elements in the array
b) Print the element with maximum frequency
c) Print the unique elements in the array
d) None of the mentioned
Answer
Answer: a [Reason:] The print statement is executed only when the items are equal and their indices are not.
9. Select the code snippet which prints the element with maximum frequency.
a)
public int findPopular(int[] a) { if (a == null || a.length == 0) return 0; Arrays.sort(a); int previous = a[0]; int popular = a[0]; int count = 1; int maxCount = 1; for (int i = 1; i < a.length; i++) { if (a[i] == previous) count++; else { if (count > maxCount) { popular = a[i-1]; maxCount = count; } previous = a[i]; count = 1; } } return count > maxCount ? a[a.length-1] : popular; }
b)
public int findPopular(int[] a) { if (a == null || a.length == 0) return 0; Arrays.sort(a); int previous = a[0]; int popular = a[0]; int count = 1; int maxCount = 1; for (int i = 1; i < a.length; i++) { if (a[i] == previous) count++; else { if (count > maxCount) { popular = a[i]; maxCount = count; } previous = a[i]; count = 1; } } return count > maxCount ? a[a.length-1] : popular; }
c)
public int findPopular(int[] a) { if (a == null || a.length == 0) return 0; Arrays.sort(a); int previous = a[0]; int popular = a[0]; int count = 1; int maxCount = 1; for (int i = 1; i < a.length; i++) { if (a[i+1] == previous) count++; else { if (count > maxCount) { popular = a[i-1]; maxCount = count; } previous = a[i]; count = 1; } } return count > maxCount ? a[a.length-1] : popular; }
d) None of the mentioned
Answer
Answer: a [Reason:] Traverse through the array and see if it is equal to the previous element, since the array is sorted this method works with a time complexity of O(nlogn), without sorting a Brute force technique must be applied for which the time complexity will be O(n^2).
10. Which of the following is a disadvantage of linear search?
a) Requires more space
b) Greater time complexities compared to other searching algorithms
c) Not easy to understand
d) All of the mentioned
Answer
Answer: b [Reason:] The complexity of linear search as the name suggests is O(n) which is much greater than other searching techniques like binary search(O(logn)).
Set 4
1. What is the order of a matrix?
a) number of rows X number of columns
b) number of columns X number of rows
c) number of rows X number of rows
d) number of columns X number of columns
Answer
Answer: a [Reason:] By definition, the order of a matrix is number of rows X number of columns, generally denoted by mXn(not compulsory).
2. Which of the following property does not hold for matrix multiplication?
a) Associative
b) Distributive
c) Commutative
d) None of the mentioned
Answer
Answer: c [Reason:] In matrix multiplication, AB != BA
3. How do you allocate a matrix using a single pointer in C?(r and c are the number of rows and columns respectively)
a) int *arr = malloc(r * c * sizeof(int));
b) int *arr = (int *)malloc(r * c * sizeof(int));
c) int *arr = (int *)malloc(r + c * sizeof(int));
d) int *arr = (int *)malloc(r * c * sizeof(arr));
Answer
Answer: b [Reason:] Total number of elements in the matrix will be r*c
4. Select the code snippet which performs matrix multiplication.(a and b are the two given matrices, resultant marix is c)
a)
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { c[i][j] = c[i][j] + a[i][k] * b[k][j]; } } }
b)
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { c[i][j] = c[i][j] * a[i][k] * b[k][j]; } } }
c)
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { c[i][j] = c[i][j] + a[i][k] + b[k][j]; } } }
d) None of the mentioned
Answer
Answer: a [Reason:] The corresponding elements from the row and column are multiplied and a cumulative sum is formed.
5. What does the following piece of code do?
for(int i = 0; i < row; i++) { for(int j = 0; j < column; j++) { if(i == j) sum = sum + (array[i][j]); } } System.out.println(sum);
a) Normal of a matrix
b) Trace of a matrix
c) Square of a matrix
d) Transpose of a matrix
Answer
Answer: b [Reason:] trace of a matrix is the sum of the principal diagonal elements.
6. If row-major order is used, how is the following matrix stored in memory?
a b c
d e f
g h i
a) ihgfedcba
b) abcdefghi
c) cfibehadg
d) adgbehcfi
Answer
Answer: b [Reason:] It starts with the first element and continues in the same row until the end of row is reached and then proceeds with the next row. C follows row-major order.
7. 6. If row-major order is used, how is the following matrix stored in memory?
a b c
d e f
g h i
a) ihgfedcba
b) abcdefghi
c) cfibehadg
d) adgbehcfi
Answer
Answer: d [Reason:] It starts with the first element and continues in the same column until the end of column is reached and then proceeds with the next column. Fortran follows column-major order.
8. Which of the following are the uses of matrices?
a) In solving linear equations
b) Image processing
c) Graph theory
d) All of the mentioned
Answer
Answer: d [Reason:] Solving linear equations is a separate field in Mathematics involving matrices, Image processing stores the pixels in the form of matrices, and the graphs are represented with the help of matrices to indicate the nodes and edges.
9. What is the disadvantage of matrices?
a) Internal complexity
b) Searching through a matrix is complex
c) Not space efficient
d) All of the mentioned
Answer
Answer: d [Reason:] time complexity of a matrix is O(n2) and sometimes the internal organization becomes tedious.
10. Matrix A when multiplied with Matrix C gives the Identity matrix I, what is C?
a) Identity matrix
b) Inverse of A
c) Square of A
d) Transpose of A
Answer
Answer: b [Reason:] Any square matrix when multiplied with its inverse gives the identity matrix. Note that non square matrices are not invertible.
Set 5
1. Which of the following methods can be used to solve the matrix chain multiplication problem?
a) Dynamic programming
b) Brute force
c) Recursion
d) All of the mentioned
Answer
Answer: d [Reason:] All of the mentioned methods can be used to solve the matrix chain multiplication problem.
2. Which of the following is the recurrence relation for the matrix chain multiplication problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?
a) dp[i,j] = 1 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]}
b) dp[i,j] = 0 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]}
c) dp[i,j] = 1 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].
d) dp[i,j] = 0 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].
Answer
Answer: d [Reason:] The recurrence relation is given by:
dp[i,j] = 0 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].
3. Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?
a) 10*20
b) 20*30
c) 10*30
d) 10*20*30
Answer
Answer: d [Reason:] The number of multiplications required is 10*20*30.
4. Consider the matrices P, Q and R which are 10 x 20, 20 x 30 and 30 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the three matrices?
a) 18000
b) 12000
c) 24000
d) 32000
Answer
Answer: a [Reason:] The minimum number of multiplications are 18000. This is the case when the matrices are parenthesized as (P*Q)*R.
5. Consider the matrices P, Q, R and S which are 20 x 15, 15 x 30, 30 x 5 and 5 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the four matrices?
a) 6050
b) 7500
c) 7750
d) 12000
Answer
Answer: c [Reason:] The minimum number of multiplications required is 7750.
6. Consider the brute force implementation in which we find all the possible ways of multiplying the given set of n matrices. What is the time complexity of this implementation?
a) O(n!)
b) O(n3)
c) O(n2)
d) Exponential
Answer
Answer: d [Reason:] The time complexity of finding all the possible ways of multiplying a set of n matrices is given by (n-1)th Catalan number which is exponential.
7. Consider the following dynamic programming implementation of the matrix chain problem:
#include<stdio.h> #include<limits.h> int mat_chain_multiplication(int *mat, int n) { int arr[n][n]; int i,k,row,col,len; for(i=1;i<n;i++) arr[i][i] = 0; for(len = 2; len < n; len++) { for(row = 1; row <= n - len + 1; row++) { col = row + len - 1; arr[row][col] = INT_MAX; for(k = row; k <= col - 1; k++) { int tmp = ________________________; if(tmp < arr[row][col]) arr[row][col] = tmp; } } } return arr[1][n - 1]; } int main() { int mat[6] = {20,5,30,10,40}; int ans = mat_chain_multiplication(mat,5); printf("%d",ans); return 0; }
Which of the following lines should be inserted to complete the above code?
a) arr[row][k] – arr[k + 1][col] + mat[row – 1] * mat[k] * mat[col];
b) arr[row][k] + arr[k + 1][col] – mat[row – 1] * mat[k] * mat[col];
c) arr[row][k] + arr[k + 1][col] + mat[row – 1] * mat[k] * mat[col];
d) arr[row][k] – arr[k + 1][col] – mat[row – 1] * mat[k] * mat[col];
Answer
Answer: c [Reason:] The line arr[row][k] + arr[k + 1][col] + mat[row – 1] * mat[k] * mat[col] should be inserted to complete the above code.
8. What is the time complexity of the above dynamic programming implementation of the matrix chain problem?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
Answer
Answer: d [Reason:] The time complexity of the above dynamic programming implementation of the matrix chain multiplication is O(n3).
9. What is the space complexity of the above dynamic programming implementation of the matrix chain problem?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
Answer
Answer: c [Reason:] The space complexity of the above dynamic programming implementation of the matrix chain multiplication is O(n2).
10. What is the output of the following code?
#include<stdio.h> #include<limits.h> int mat_chain_multiplication(int *mat, int n) { int arr[n][n]; int i,k,row,col,len; for(i=1;i<n;i++) arr[i][i] = 0; for(len = 2; len < n; len++) { for(row = 1; row <= n - len + 1; row++) { col = row + len - 1; arr[row][col] = INT_MAX; for(k = row; k <= col - 1; k++) { int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col]; if(tmp < arr[row][col]) arr[row][col] = tmp; } } } return arr[1][n - 1]; } int main() { int mat[6] = {20,30,40,50}; int ans = mat_chain_multiplication(mat,4); printf("%d",ans); return 0; }
a) 64000
b) 70000
c) 120000
d) 150000
Answer
Answer: a [Reason:] The program prints the minimum number of multiplications required ,which is 64000.
11. What is the value stored in arr[2][3] when the following code is executed?
#include<stdio.h> #include<limits.h> int mat_chain_multiplication(int *mat, int n) { int arr[n][n]; int i,k,row,col,len; for(i=1;i<n;i++) arr[i][i] = 0; for(len = 2; len < n; len++) { for(row = 1; row <= n - len + 1; row++) { col = row + len - 1; arr[row][col] = INT_MAX; for(k = row; k <= col - 1; k++) { int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col]; if(tmp < arr[row][col]) arr[row][col] = tmp; } } } return arr[1][n - 1]; } int main() { int mat[6] = {20,30,40,50}; int ans = mat_chain_multiplication(mat,4); printf("%d",ans); return 0; }
a) 64000
b) 60000
c) 24000
d) None of the mentioned
Answer
Answer: b [Reason:] The value stored in arr[2][3] when the above code is executed is 60000.
12. What is the output of the following code?
#include<stdio.h> #include<limits.h> int mat_chain_multiplication(int *mat, int n) { int arr[n][n]; int i,k,row,col,len; for(i=1;i<n;i++) arr[i][i] = 0; for(len = 2; len < n; len++) { for(row = 1; row <= n - len + 1; row++) { col = row + len - 1; arr[row][col] = INT_MAX; for(k = row; k <= col - 1; k++) { int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col]; if(tmp < arr[row][col]) arr[row][col] = tmp; } } } return arr[1][n-1]; } int main() { int mat[6] = {10,10,10,10,10,10}; int ans = mat_chain_multiplication(mat,6); printf("%d",ans); return 0; }
a) 2000
b) 3000
c) 4000
d) 5000
Answer
Answer: c [Reason:] The program prints the minimum number of multiplications required to multiply the given matrices, which is 4000.
13. What is the output of the following code?
#include<stdio.h> #include<limits.h> int mat_chain_multiplication(int *mat, int n) { int arr[n][n]; int i,k,row,col,len; for(i=1;i<n;i++) arr[i][i] = 0; for(len = 2; len < n; len++) { for(row = 1; row <= n - len + 1; row++) { col = row + len - 1; arr[row][col] = INT_MAX; for(k = row; k <= col - 1; k++) { int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col]; if(tmp < arr[row][col]) arr[row][col] = tmp; } } } return arr[1][n-1]; } int main() { int mat[6] = {20,25,30,35,40}; int ans = mat_chain_multiplication(mat,5); printf("%d",ans); return 0; }
a) 32000
b) 28000
c) 64000
d) 70000
Answer
Answer: c [Reason:] The output of the program is 64000.
