Advanced Algorithms And Complexity In Data Structures Quiz

Reviewed by Editorial Team
The ProProfs editorial team is comprised of experienced subject matter experts. They've collectively created over 10,000 quizzes and lessons, serving over 100 million users. Our team includes in-house content moderators and subject matter experts, as well as a global network of rigorously trained contributors. All adhere to our comprehensive editorial guidelines, ensuring the delivery of high-quality content.
Learn about Our Editorial Process
| By Themes
T
Themes
Community Contributor
Quizzes Created: 424 | Total Attempts: 1,019,578
| Attempts: 156
SettingsSettings
Please wait...
  • 1/15 Questions

    Which of a) to d) is true: The size of a hash table with n keys:

    • Should be n for double-hashing
    • Should be a prime number greater than n for linear probing
    • Should be a prime number and less than 2n for quadratic probing
    • None of these
Please wait...
About This Quiz

How strong are your concepts in data structure? Can you score well on this 'Advanced algorithms and complexity in data structures quiz'? Try the quiz and see for yourself. It contains the top 15 practice questions related to advanced algorithms and time complexities. The advanced data structure and algorithms are used for storing, managing, and organizing data and information to make it more efficient and easier to access. Learn and test your understanding of it with the quiz below.

Advanced Algorithms And Complexity In Data Structures Quiz - Quiz

Quiz Preview

  • 2. 

    The next question relates to the following binary tree with root A: The root has left child B and right child C. B has left child D and right child E. C has right child F. There are no other nodes in the tree. Which of the following traversals yields DBEACF?

    • Inorder

    • Postorder

    • Preorder

    • None of the above

    Correct Answer
    A. Inorder
    Explanation
    Inorder traversal visits the left subtree first, then the root, and finally the right subtree. In this case, the inorder traversal DBEACF would visit the nodes in the following order: D, B, E, A, C, F. Therefore, the correct answer is Inorder.

    Rate this question:

  • 3. 

    Which of the following can be done in O(N)?

    • Find an element in an unsorted array

    • Find an element in a sorted array

    • Find an element in a binary tree

    • None of these

    Correct Answer
    A. Find an element in an unsorted array
    Explanation
    Finding an element in an unsorted array can be done in O(N) time complexity, where N is the number of elements in the array. This is because in the worst case scenario, we may have to iterate through all the elements of the array to find the desired element. Therefore, the time taken to find an element in an unsorted array is directly proportional to the size of the array, making it O(N).

    Rate this question:

  • 4. 

    Which of the following algorithms requires the most extra space memory (not in place algorithm)?

    • Insertion sort

    • Selection sort

    • Merge sort

    • Shell sort

    Correct Answer
    A. Merge sort
    Explanation
    Merge sort requires the most extra space memory compared to the other algorithms listed. This is because merge sort uses a temporary array to merge the sorted subarrays, resulting in additional space usage. In contrast, insertion sort, selection sort, and shell sort do not require additional space for merging or creating temporary arrays.

    Rate this question:

  • 5. 

    The following items are inserted in the given order into an AVL-tree: 6, 3, 5, 2, 4, 1, 7. Which node is in the deepest node?

    • 5

    • 1

    • 3

    • 7

    Correct Answer
    A. 7
    Explanation
    The given AVL-tree is built by inserting the nodes in the following order: 6, 3, 5, 2, 4, 1, 7. The deepest node in this tree is the node with the value 7. The AVL-tree is a self-balancing binary search tree, and the depth of a node is the length of the longest path from that node to a leaf node. In this case, the node with the value 7 is at the deepest level of the tree, meaning it has the longest path to a leaf node compared to the other nodes in the tree.

    Rate this question:

  • 6. 

    Which of the following algorithms runs in O(n log n) average time but O(n2) worst-case time?

    • Heapsort

    • Insertion sort

    • Mergesort

    • Quicksort

    • Shellsort

    Correct Answer
    A. Quicksort
    Explanation
    Quicksort is the correct answer because it has an average time complexity of O(n log n), which means that on average it will take a time proportional to n multiplied by log n to sort the elements. However, in the worst-case scenario, where the pivot chosen is always the smallest or largest element, the time complexity can degrade to O(n2), which means it will take a time proportional to n squared to sort the elements. Therefore, quicksort runs in O(n log n) average time but O(n2) worst-case time.

    Rate this question:

  • 7. 

    The next question relates to the following binary tree with root A: The root has left child B and right child C. B has left child D and right child E. C has right child F. There are no other nodes in the tree. Which of the following traversals yields DEBFCA

    • Inorder

    • Postorder

    • Preorder

    • None of the above

    Correct Answer
    A. Postorder
    Explanation
    Postorder traversal visits the nodes in the following order: left subtree, right subtree, and then the root. In this case, the postorder traversal would be DEBFCA.

    Rate this question:

  • 8. 

    For minimum spanning tree (MST) construction, Kruskal’s algorithm selects an edge:

    • With maximum number of vertices connected to it

    • With minimum weight so that cost of MST is always minimum

    • That does not introduce a cycle

    • None of the above

    Correct Answer
    A. With minimum weight so that cost of MST is always minimum
    Explanation
    Kruskal's algorithm for constructing a minimum spanning tree (MST) selects an edge with the minimum weight so that the cost of the MST is always minimum. This is because the algorithm aims to connect all the vertices in the graph with the minimum total weight possible. By selecting edges with the minimum weight, the algorithm ensures that it is adding the least expensive connections to the tree, resulting in the overall minimum cost for the MST.

    Rate this question:

  • 9. 

    The next question applies to the following  code fragment: 1.   for i in 1..N loop 2.       for j in 1..i loop 3.            for k in i..j loop 4.                 Sum := Sum + 1; 5.            end loop; 6.       end loop; 7.   end loop; 8.   for p in 1..N*N loop 9.       for q in 1..p loop 10.          Sum := Sum - 1; 11.     end loop; 12. end loop What is the running time of this fragment?

    • O(N4)

    • O(N5)

    • O(N6)

    • O(N7)

    • None of the above

    Correct Answer
    A. O(N4)
    Explanation
    The running time of this code fragment is O(N4). This is because there are three nested loops in lines 1-7, with the outer loop running N times, the middle loop running i times, and the innermost loop running j-i+1 times. The loop in lines 8-12 also runs N2 times. Therefore, the total number of iterations is approximately N * (N * (N+1) * (N+2)) / 6, which simplifies to O(N4).

    Rate this question:

  • 10. 

    The next question applies to the following  code fragment: 1.   for i in 1..N loop 2.       for j in 1..i loop 3.            for k in i..j loop 4.                 Sum := Sum + 1; 5.            end loop; 6.       end loop; 7.   end loop; 8.   for p in 1..N*N loop 9.       for q in 1..p loop 10.          Sum := Sum - 1; 11.     end loop; 12. end loop How many times is statement 4 executed?

    • O(N)

    • O(N2)

    • O(N3)

    • O(N4)

    • None of the above

    Correct Answer
    A. O(N3)
    Explanation
    The code fragment contains three nested loops: i, j, and k. The outermost loop, i, iterates N times. The second loop, j, iterates i times for each value of i. The innermost loop, k, iterates from i to j. Therefore, the number of times statement 4 is executed is equal to the sum of the number of iterations of the innermost loop for each iteration of the second loop, for each iteration of the outermost loop. This can be represented as the sum of the cubes of the numbers from 1 to N, which is O(N^3).

    Rate this question:

  • 11. 

    Suppose that you have the following algorithm to sort a list of N integer numbers: 1. Build an AVL-tree with the input list of N integer numbers. 2. Incorporate in-order traversal for the N nodes of the AVL-tree. This step allows to print the value of the nodes of the AVL-tree in sorted order. What is the total running time complexity of this algorithm?

    • O(logN)

    • O(N)

    • O(NlogN)

    • O(N2)

    Correct Answer
    A. O(NlogN)
    Explanation
    The algorithm first builds an AVL-tree, which has a time complexity of O(NlogN) since each insertion or deletion operation takes O(logN) time. Then, it performs an in-order traversal of the AVL-tree to print the values in sorted order, which also takes O(N) time. Therefore, the total running time complexity of the algorithm is O(NlogN).

    Rate this question:

  • 12. 

    The next question applies to the following  code fragment: 1.   for i in 1..N loop 2.       for j in 1..i loop 3.            for k in i..j loop 4.                 Sum := Sum + 1; 5.            end loop; 6.       end loop; 7.   end loop; 8.   for p in 1..N*N loop 9.       for q in 1..p loop 10.          Sum := Sum - 1; 11.     end loop; 12. end loop How many times is statement 10 executed?

    • O(N)

    • O(N2)

    • O(N3)

    • O(N4)

    • None of the above

    Correct Answer
    A. O(N4)
    Explanation
    The given code fragment consists of nested loops. The outermost loop iterates N times, and the second loop iterates i times, where i ranges from 1 to N. The innermost loop iterates from i to j, where j ranges from 1 to i.

    Therefore, the number of times statement 10 is executed can be calculated as the sum of the product of the iterations of each loop. The outer loop iterates N times, the second loop iterates i times, and the innermost loop iterates (i-j+1) times.

    Hence, the total number of times statement 10 is executed is the sum of (N * i * (i-j+1)) for all values of i and j. This simplifies to O(N^4) as the number of iterations.

    Rate this question:

  • 13. 

    Suppose T1(n) = O(f(n)) and T2(n) = O(g(n)). Which of the following are true?

    • T1(n) + T2(n) = O(max(f(n), g(n)))

    • T1(n) * T2(n) = O(f(n) * g(n))

    • T1(n) / T2(n) = O(f(1))

    • T1(n) = O(T2(n))

    • None of the above

    Correct Answer(s)
    A. T1(n) + T2(n) = O(max(f(n), g(n)))
    A. T1(n) * T2(n) = O(f(n) * g(n))
    Explanation
    The given answer is correct.

    When we add the time complexities T1(n) and T2(n), the worst-case time complexity will be the maximum of f(n) and g(n). Hence, T1(n) + T2(n) = O(max(f(n), g(n))).

    Similarly, when we multiply the time complexities T1(n) and T2(n), the worst-case time complexity will be the product of f(n) and g(n). Hence, T1(n) * T2(n) = O(f(n) * g(n)).

    However, T1(n) / T2(n) is not equal to O(f(1)). The division of time complexities does not follow the same rules as addition and multiplication.

    Lastly, we cannot conclude that T1(n) = O(T2(n)) without knowing the specific functions f(n) and g(n). Therefore, the correct answers are T1(n) + T2(n) = O(max(f(n), g(n))) and T1(n) * T2(n) = O(f(n) * g(n)).

    Rate this question:

  • 14. 

    N elements are inserted from a min-heap with N elements. The total running time is:

    • O(n) worst case and O(1) average case

    • O(log n) worst case and O(log n) average case

    • O(n) worst case and O(n log n) average case

    • O(log n) worst case and O(1) average case

    • O(n log n) worst case and O(n log n) average case

    Correct Answer
    A. O(log n) worst case and O(1) average case
    Explanation
    When inserting N elements into a min-heap with N elements, the worst-case running time is O(log n) because each insertion requires traversing the height of the heap, which is log n. The average case running time is O(1) because on average, each insertion only requires a constant amount of operations regardless of the size of the heap. Therefore, the correct answer is O(log n) worst case and O(1) average case.

    Rate this question:

  • 15. 

    Which of the following algorithms is non stable? (select all that apply)

    • Heap sort

    • Selection sort

    • Shell sort

    • Merge sort

    • Insertion sort

    • Quick sort

    Correct Answer(s)
    A. Heap sort
    A. Selection sort
    A. Shell sort
    A. Quick sort
    Explanation
    The stability of an algorithm refers to whether it maintains the relative order of elements with equal keys. In a stable sorting algorithm, elements with equal keys appear in the same order in the sorted output as they do in the input. Heap sort, selection sort, shell sort, and quick sort are all non-stable sorting algorithms. They do not guarantee the preservation of the relative order of elements with equal keys. Merge sort and insertion sort, on the other hand, are stable sorting algorithms as they maintain the relative order of equal elements.

    Rate this question:

Quiz Review Timeline (Updated): Jun 18, 2023 +

Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.

  • Current Version
  • Jun 18, 2023
    Quiz Edited by
    ProProfs Editorial Team
  • Jun 13, 2022
    Quiz Created by
    Themes
Back to Top Back to top
Advertisement
×

Wait!
Here's an interesting quiz for you.

We have other quizzes matching your interest.