MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 15 Mcqs, each offering curated multiple-choice questions to sharpen your Data Structures and Algorithms knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
A text is made up of the characters a, b, c, d, e each occurring with the probability 0.11, 0.40, 0.16, 0.09 and 0.24 respectively. The optimal Huffman coding technique will have the average length of : |
| A. | 2.4 |
| B. | 2.16 |
| C. | 2.26 |
| D. | 2.15 |
| Answer» C. 2.26 | |
| 2. |
Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties:1. For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter.2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter.Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string? |
| A. | 23 |
| B. | 21 |
| C. | 25 |
| D. | 30 |
| Answer» B. 21 | |
| 3. |
Consider the following table: Algorithms Design Paradigms (P) Kruskal (i) Divide and Conquer (Q) Quicksort (ii) Greedy (R) Floyd-Warshall (iii) Dynamic Programming Match the algorithms to the design paradigms they are based on. |
| A. | (P) ↔ (ii), (Q) ↔ (iii), (R) ↔ (i) |
| B. | (P) ↔ (iii), (Q) ↔ (i), (R) ↔ (ii) |
| C. | (P) ↔ (ii), (Q) ↔ (i), (R) ↔ (iii) |
| D. | (P) ↔ (i), (Q) ↔ (ii), (R) ↔ (iii) |
| Answer» D. (P) ↔ (i), (Q) ↔ (ii), (R) ↔ (iii) | |
| 4. |
Consider the following two sequences :X = < B, C, D, C, A, B, C >and Y = < C, A, D, B, C, B >The length of longest common subsequence of X and Y is : |
| A. | 5 |
| B. | 3 |
| C. | 4 |
| D. | 2 |
| Answer» D. 2 | |
| 5. |
Four matrices M1, M2, M3 and M4 of dimensions p×q, q×r, r×s and s×t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as [(M1 × M2) × (M3 × M4)] the total number of scalar multiplications is pqr + rst + prt. When multiplied as [((M1 × M2)× M3)) × M4], the total number of scalar multiplications is pqr + prs + pst.If p = 10, q = 100, r = 20, s = 5 and t = 80, then the minimum number of scalar multiplications needed is: |
| A. | 248000 |
| B. | 44000 |
| C. | 19000 |
| D. | 25000 |
| Answer» D. 25000 | |
| 6. |
Assume that multiplying a matrix G1 of dimension |
| A. | F1F2 and F3F4 only |
| B. | F2F3 only |
| C. | F3F4 only |
| D. | F1F2 and F4F5 only |
| Answer» D. F1F2 and F4F5 only | |
| 7. |
Match the following and choose the correct answer for the order A, B, C, D.A.Strassen matrix multiplicationp.Decrease and ConquerB.Insertion sortq.Dynamic ProgrammingC.Gaussian Eliminationr.Divide and ConquerD.Floyd shortest path algorithms.Transform and Conquer |
| A. | r, s, p, q |
| B. | r, p, s, q |
| C. | q, s, p, r |
| D. | s, p, q, r |
| Answer» C. q, s, p, r | |
| 8. |
Consider the following codes :1. Hamming code.2. Huffman code3. Shannon-Fano code4. Convolutional codeWhich of these are source codes ? |
| A. | 1 and 2 only |
| B. | 2 and 3 only |
| C. | 3 and 4 only |
| D. | 1, 2, 3 and 4 |
| Answer» C. 3 and 4 only | |
| 9. |
In case of the dynamic programming approach the value of an optimal solution is computed in: |
| A. | Top down fashion |
| B. | Bottom up fashion |
| C. | Left to Right fashion |
| D. | Right to Left fashion |
| Answer» C. Left to Right fashion | |
| 10. |
Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denotes the selling price of a rod whose length is i meters. Consider the array of prices:p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18Which of the following statements is/are correct about R7? |
| A. | R7 cannot be achieved by a solution consisting of three pieces. |
| B. | R7 = 19 |
| C. | R7 = 18 |
| D. | R7 is achieved by three different solutions. |
| Answer» D. R7 is achieved by three different solutions. | |
| 11. |
Match List I with List IIList IList II(A) Topological sort of DAG(I) O(V + E)(B) Kruskal's MST algorithm(II) O(VE)(C) Bellman-Ford's single-source shortest path algorithm(III) θ (V + E)(D) Floyd-Warshall's all-pair shortest path algorithm(IV) θ(V3) Choose the correct answer from the options given below: |
| A. | A - I, B - III, C - IV, D - II |
| B. | A - III, B - I, C - IV, D - II |
| C. | A - III, B - I, C - II, D - IV |
| D. | A - I, B - III, C - II, D - IV |
| Answer» E. | |
| 12. |
Assembly line scheduling and Longest Common Subsequence problems are an example of __________ |
| A. | Dynamic Programming |
| B. | Greedy Algorithms |
| C. | Greedy Algorithms and Dynamic Programming respectively |
| D. | Dynamic Programming and Branch and Bound respectively |
| Answer» B. Greedy Algorithms | |
| 13. |
Huffman tree is constructed for the following data: {A, B, C, D, E} with frequency {0.17, 0.11, 0.24, 0.33 and 0.15} respectively. 100 00 01101 is decoded as |
| A. | BACE |
| B. | CADE |
| C. | BAD |
| D. | CADD |
| Answer» B. CADE | |
| 14. |
If b is the branching factor and m is the maximum depth of the search tree, what is the space complexity of greedy search ? |
| A. | O (b + m) |
| B. | O (bm) |
| C. | O(bm) |
| D. | O(mb) |
| Answer» D. O(mb) | |
| 15. |
A sorting technique is called stable if |
| A. | If it takes O(n log n) time |
| B. | It uses divide and conquer technique |
| C. | Relative order of occurrence of non-distinct elements is maintained |
| D. | It takes O(n) space |
| Answer» D. It takes O(n) space | |