Data Structure and Algorithm- Exam Questions with Correct Solutions Latest Update 2024 (Already Passed)

Data Structure and Algorithm- Exam Questions with Correct Solutions Latest Update 2024 (Already Passed) 1.1.1.1. What will you typically need to implement yourself in the programming assignments if you program in C++, Java or Python? A. Reading input, writing output and the solution to the problem. B. Just reading the input. C. Just the solution of the problem. D. Just writing the output. - Answers C. Just the solution of the problem. . 1.1.1.2. Your program in C, C++ or Java thinks that the product of numbers 50000 and 50000 is equal to -. What is the most probable reason? A. Compiler error. B. The problem statement is wrong. C. The input data is incorrect. D. Integer overflow. - Answers D. Integer overflow. 1.1.1.3. Which tests should you perform before submitting a solution to the programming assignment? A. Just submit the program and see if it passes the assignment. B. Test on the examples from the problem statement. Then make a few other small tests, solve them manually and check that your program outputs the correct answer. After all these tests passed, submit the solution. C. Test on the examples from the problem statement. Then make a few other small tests, solve them manually and check that your program outputs the correct answer. Generate a big input and launch your program to check that it works fast enough and doesn't consume too much memory. Test for corner cases: smallest allowed values and largest allowed values of all input parameters, equal numbers in the input, very long strings, etc. Then make a stress test. After all these tests passed, submit the solution. D. Just check that the answers for the exampl - Answers C. Test on the examples from the problem statement. Then make a few other small tests, solve them manually and check that your program outputs the correct answer. Generate a big input and launch your program to check that it works fast enough and doesn't consume too much memory. Test for corner cases: smallest allowed values and largest allowed values of all input parameters, equal numbers in the input, very long strings, etc. Then make a stress test. After all these tests passed, submit the solution. 1.1.1.4. Where does the input data come from when you implement a stress test? A. You download and use the tests we've prepared to check your solution to the problem. B. You generate valid input data as a part of the stress test implementation. C. You enter the input data manually. - Answers B. You generate valid input data as a part of the stress test implementation. 1.1.1.5. If you submit a solution of a programming assignment, but it does not pass some of the tests, what feedback will you get from the system? A. You will see the input data, the answer of your program, the correct answer, how long did your program work and how much memory did it use for each of the tests. B. You will only get the feedback that your program either passed or did not pass. C. If it is one of the first few tests, you will see the input data, the answer of your program and the correct answer. Otherwise, you will only see either that the answer of your program is wrong or that your program is too slow or that your program uses too much memory. - Answers C. If it is one of the first few tests, you will see the input data, the answer of your program and the correct answer. Otherwise, you will only see either that the answer of your program is wrong or that your program is too slow or that your program uses too much memory. 1.2.1.1. Is it true that (log5_n)2=2log5_n? - Answers B. No 1.2.1.2. log2_n⋅log3_2=log3_n - Answers A. Yes 1.2.1.3. n^(log2_n)=n - Answers B. No 1.2.1.4. log3_2n=log3_2⋅log3_n - Answers B. No 1.2.1.5. log10_n2=10_n - Answers A. Yes 1.2.1.6. 7_3=3_n - Answers B. No 1.2.2.1. Is it true that log_2n=O(n^2) - Answers A. Yes 1.2.2.2. 2_n=O(n) - Answers B. No 1.2.2.3. n^2=O(n^3) - Answers A. Yes 1.2.2.4. n=O(sqrt(n)) - Answers B. No 1.2.2.5. 5^(log2-n)=O(n^2) - Answers B. No 1.2.2.6. n^5=O(2^(2_n)) - Answers B. No 1.2.2.7. 2^n=O(2^(n+1)) - Answers A. Yes 1.2.3.1. f_1(n)=n^3 f_2(n)=n^0.3 f_3(n)=n f_4(n)=sqrt(n) f_5(n)=(n^2)sqrt(n) f_6(n)=n^2 - Answers 243561 1.2.3.2 f_1(n)=3^n f_2(n)=_2n f_3(n)=log_4n f_4(n)=n f_5(n)=5^(log2_n} f_6(n)=n^2 f_7(n)=sqrt(n) f_8(n)=2^(2n) - Answers 1.3.1.1. You work as a freelancer and have a pool of 10 projects to work on. For each project you know how much money you will get for completing the project. You can complete any 3 projects this month. You want to select such projects that you will get the most money by completing them. What are the safe moves in this problem? (Mark all that apply.) - Answers B. Take the project with the highest payment for completion, complete it and remove it from the pool of projects. D. If there are more than 3 projects in the pool, remove the project with the lowest payment for completion, don't work on this project. In the other case, remove the first project from the pool and work on this project. 1.3.1.2. In the previous problem, what is the subproblem you need to solve after you've made a safe move? - Answers Choose projects with highest payment to work on from the pool of projects which now contains only 9 projects. 1.3.1.3. You need to find an integer 7323≤x≤73 with the largest product of digits. You use a greedy strategy: first, determine the largest possible first digit (tens) of xx, then determine the largest possible second digit (ones) of xx (among all the numbers in the range from 23 to 73 whose first digit is equal to the digit selected at the first step). Will this greedy strategy work - Answers No 1.3.2.1. You have a knapsack of capacity 10kg and three items. First item has weight 20kg and value 20, second item has weight 5kg and value 10. Third item has weight 4 kg and value 20. You want to maximize the total value of the fractions of items that fit into your knapsack. What is the safe move? A. Take the whole first item. B. Take 10 kg of the first item. C. Take 2kg of third item and 8 kg of first item. D. Take the whole third item. E. Take the whole second item. - Answers Take the whole third item. 1.3.2.2. What is the next safe move in the previous problem? A. Take the whole first item. B. Take 6 kg of the first item. C. Take the whole second item. D. Take 10 kg of the first item. E. Take the whole third item. - Answers Take the whole second item 1.3.2.3. What is the last move? A. Take the whole second item. B. Take 1 kg of the first item. C. Take the whole third item. D. Take 1 kg of the second item. E. Take 10 kg of the first item. - Answers Take 1 kg of the first item. 1.4.1.1. You have an array with 1023 numbers. You use linear search to determine whether number 239 is in this array or not. How many elements of the array will you look at if number 239 is not present in the array? A. 1023 B. 10 C. 11 D. 1 E. 0 - Answers 1023 1.4.1.2. Can you use binary search to find number 8 in the array [1, 24, 25, 23, 17, 8, 9]? A. Yes, you can. B. No, you cannot. - Answers No, you cannot. 1.4.1.3. You have a sorted array with 1023 elements. You use binary search to determine whether number 239 is present in this array or not. How many elements of the array will you compare it with if number 239 is not present in this array? A. 10 B. 1023 C. 1 D. 0 - Answers 10 1.4.1.4. What is the maximum number of iterations a binary search will make to find some number in the array [1, 2, 3, 5, 8, 13, 21, 34]? A. 4 B. 3 C. 8 - Answers 4 1.4.2.1. For n = 1024, compute how many operations will the faster divide and conquer algorithm from the lectures perform, using the formula 3^(log2_n) for the number of operations. A. 1024 B. 1048576