123456789101112131415161718192021222324252627282930313233343536373839404142434445Show paginator Hide paginator 2% Question 1 of 45 1. Time Complexity MCQ Question 8 Consider the following C function. int fun(int n) { int i, j; for (i = 1; i < = n; i++) { for (j = 1; j < n; j + = i) { printf (‘’ %d %d’’, i, j); } } } Time complexity of fun in terms of Θ notation is Θ (n√n)Θ (n2)Θ (nlog n)Θ (n2log n)Question 1 of 45Question 2 of 45 2. Which of the following statements is/are true? Recurrence relation for number of comparisons in binary search is T(n) = T(n/2) + 2Recurrence relation of merge sort in worst case is T(n) = 2T(n/2) + Θ(n)Recurrence of quicksort in worst case is T(n) = 2T(n/2) + O(1)3-way merge sort is T(n) = 3T(n/3) + O(n)Question 2 of 45Question 3 of 45 3. Dijkstra’s algorithm is used to solve __________ problems? Network lock Single source shortest path All pair shortest path SortingQuestion 3 of 45Question 4 of 45 4. The Bellmann Ford Algorithm returns __________ value? String BooleanDouble IntegerQuestion 4 of 45Question 5 of 45 5. Which of the following statements is true about AVL Trees? The difference between the heights of left and right nodes cannot be more than 1.The height of an AVL Tree always remains of the order of O(logn)AVL Trees are a type of self-balancing Binary Search Trees.All of the above.Question 5 of 45Question 6 of 45 6. Representation of data structure in memory is known as? Storage structure File structureRecursiveAbstract Data TypeQuestion 6 of 45Question 7 of 45 7. In what time complexity can we find the diameter of a binary tree optimally? O(V + E)O(V)O(E)O(V * logE)Question 7 of 45Question 8 of 45 8. To main measures of the efficiency of an algorithm are? Time and space complexity Data and space Processor and memoryComplexity and capacityQuestion 8 of 45Question 9 of 45 9. Which of the following sorting algorithms provide the best time complexity in the worst-case scenario? Merge Sort Quick Sort Bubble Sort Selection SortQuestion 9 of 45Question 10 of 45 10. Which of the following is a Divide and Conquer algorithm? Bubble Sort Selection SortHeap Sort Merge SortQuestion 10 of 45Question 11 of 45 11. Which of the following data structure is used to perform recursion? Linked listArrayQueueStackQuestion 11 of 45Question 12 of 45 12. Identify the best case time complexity of selection sort? O(nlogn)O(n^2) O(n) O(1)Question 12 of 45Question 13 of 45 13. Another name of the fractional knapsack is? Non-continuous knapsack problem Divisible knapsack problem 0/1 knapsack problem Continuous Knapsack ProblemQuestion 13 of 45Question 14 of 45 14. Identify the approach followed in Floyd Warshall’s algorithm? Linear programming Dynamic ProgrammingGreedy TechniqueBacktrackingQuestion 14 of 45Question 15 of 45 15. Hamiltonian path problem is _________? NP problemP class problemNP-complete problemN class problemQuestion 15 of 45Question 16 of 45 16. What is the time complexity of the following code snippet in C++? void solve() { string s = "scaler"; int n = s.size(); for(int i = 0; i < n; i++) { s = s + s[i]; } cout << s << endl; } O(n) O(n^2)O(1)O(log n)Question 16 of 45Question 17 of 45 17. When a pop() operation is called on an empty queue, what is the condition called? Overflow UnderflowSyntax ErrorGarbage ValueQuestion 17 of 45Question 18 of 45 18. What will be the best sorting algorithm, given that the array elements are small (<= 1e6)? Bubble Sort Merge Sort Counting Sort Heap SortQuestion 18 of 45Question 19 of 45 19. What is the time complexity of the Sieve of Eratosthenes to check if a number is prime? O(nlog(logn)) Precomputation, O(1) for check. O(n) Precomputation, O(1) for the check. O(n * logn) Precomputation, O(logn) for check.O(n) Precomputation, O(logn) for check.Question 19 of 45Question 20 of 45 20. The worst-case time complexity of Quicksort is? O(n) O(1) O(log2n) O(n^2)Question 20 of 45Question 21 of 45 21. What is the technique called in which it does not require extra memory for carrying out the sorting procedure? Stable Unstable In-placeIn-partitionQuestion 21 of 45Question 22 of 45 22. Select the correct recurrence relation for Tower of Hanoi? T(N) = 2T(N-1)+1 T(N) = 2T(N/2)+1 T(N) = 2T(N-1)+N T(N) = 2T(N-2)+2Question 22 of 45Question 23 of 45 23. Identify the sorting technique which compares adjacent elements in a list and switches whenever necessary? Merge Sort Quick Sort Bubble Sort Selection SortQuestion 23 of 45Question 24 of 45 24. Among the following options which is the best sorting algorithm when the list is already sorted? Merge Sort Insertion Sort Bubble Sort Selection SortQuestion 24 of 45Question 25 of 45 25. What is the best case time complexity of the binary search algorithm? O(1) O(n) O(log2n) O(n^2)Question 25 of 45Question 26 of 45 26. Which of the following algorithms are used to find the shortest path from a source node to all other nodes in a weighted graph? BFS Djikstra’s Algorithm Prims Algorithm Kruskal’s AlgorithmQuestion 26 of 45Question 27 of 45 27. Which of the following are applications of Topological Sort of a graph? Sentence Ordering Course Scheduling OS Deadlock Detection All of the aboveQuestion 27 of 45Question 28 of 45 28. What is the time complexity in decreasing the node value in a binomial heap? O(1) O(N) O(logN) O(NlogN)Question 28 of 45Question 29 of 45 29. An algorithm is __________? A problem A procedure for solving a problem A real-life mathematical problem None of the aboveQuestion 29 of 45Question 30 of 45 30. Which of the following is incorrect? Algorithms can be represented: As programs As flow charts As syntaxAs pseudo-codesQuestion 30 of 45Question 31 of 45 31. What is the time complexity to insert an element to the front of a LinkedList(head pointer given)? O(n) O(1) O(logn) O(n * logn)Question 31 of 45Question 32 of 45 32. What should be considered when designing an algorithm? If this software is used correctly In the hardware is used correctly If there is more than one way to solve the problem All of the above are correctQuestion 32 of 45Question 33 of 45 33. Which of the following is known to be not an NP-Hard Problem? Vertex Cover Problem 0/1 Knapsack Problem Maximal Independent Set Problem Travelling Salesman ProblemQuestion 33 of 45Question 34 of 45 34. The worst-case time complexity of Selection Exchange Sort is? O(n) O(1) O(log2n) O(n^2)Question 34 of 45Question 35 of 45 35. Tree structure Complete binary treeBinary treeNone of the aboveQuestion 35 of 45Question 36 of 45 36. What is the maximum number of swaps that can be performed in the Selection Sort algorithm? n - 1n1n - 2Question 36 of 45Question 37 of 45 37. Worst-case time complexity to access an element in a BST can be? O(n) O(n * logn)O(1)O(logn)Question 37 of 45Question 38 of 45 38. In a graph of n nodes and n edges, how many cycles will be present? Exactly 1At most 1At most 2Depending on the graphQuestion 38 of 45Question 39 of 45 39. Kruskal’s Algorithm for finding the Minimum Spanning Tree of a graph is a kind of a? DP Problem Greedy Algorithm Adhoc ProblemNone of the aboveQuestion 39 of 45Question 40 of 45 40. Which of the following algorithms are used for string and pattern matching problems?? Z Algorithm Rabin Karp Algorithm KMP Algorithm All of the aboveQuestion 40 of 45Question 41 of 45 41. The time complexity for travel Singh all nodes in a binary search tree with n nodes and printing them in order is? O(n) O(1) O(nlog2n) O(n^2)Question 41 of 45Question 42 of 45 42. Identify the function of the stack that returns the top data element of the stack? pop() peek() push() findTop()Question 42 of 45Question 43 of 45 43. What is the best time complexity we can achieve to precompute all-pairs shortest paths in a weighted graph? O(n^3) O(n^2) O(n) O(n^4)Question 43 of 45Question 44 of 45 44. Which of the following functions provides the maximum asymptotic complexity? f1(n) = n^(3/2) f2(n) = n^(logn) f3(n) = nlogn f4(n) = 2^n.Question 44 of 45Question 45 of 45 45. The time complexity to find the longest common subsequence of two strings of length M and N is? O(N) O(M * N) O(M) O(log N)Question 45 of 45 Loading...
