Advanced Algorithms And Complexity In Data Structures Quiz

15 Questions | By Themes | Updated: Jun 18, 2022 | Attempts: 84

Questions

Settings

Advanced Algorithms And Complexity In Data Structures Quiz - 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.

Questions and Answers

1.

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?
- A.
  
  O(N)
- B.
  
  O(N²)
- C.
  
  O(N³)
- D.
  
  O(N⁴)
- E.
  
  None of the above
2.

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?
- A.
  
  O(N)
- B.
  
  O(N²)
- C.
  
  O(N³)
- D.
  
  O(N⁴)
- E.
  
  None of the above
3.

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?
- A.
  
  O(N⁴)
- B.
  
  O(N⁵)
- C.
  
  O(N⁶)
- D.
  
  O(N⁷)
- E.
  
  None of the above
4.

Suppose T₁(n) = O(f(n)) and T₂(n) = O(g(n)). Which of the following are true?
- A.
  
  T₁(n) + T₂(n) = O(max(f(n), g(n)))
- B.
  
  T₁(n) * T₂(n) = O(f(n) * g(n))
- C.
  
  T₁(n) / T₂(n) = O(f(1))
- D.
  
  T₁(n) = O(T₂(n))
- E.
  
  None of the above
5.

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?
- A.
  
  O(logN)
- B.
  
  O(N)
- C.
  
  O(NlogN)
- D.
  
  O(N²)
6.

Which of the following can be done in O(N)?
- A.
  
  Find an element in an unsorted array
- B.
  
  Find an element in a sorted array
- C.
  
  Find an element in a binary tree
- D.
  
  None of these
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
- A.
  
  Inorder
- B.
  
  Postorder
- C.
  
  Preorder
- D.
  
  None of the above
8.

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?
- A.
  
  Inorder
- B.
  
  Postorder
- C.
  
  Preorder
- D.
  
  None of the above
9.

For minimum spanning tree (MST) construction, Kruskal’s algorithm selects an edge:
- A.
  
  With maximum number of vertices connected to it
- B.
  
  With minimum weight so that cost of MST is always minimum
- C.
  
  That does not introduce a cycle
- D.
  
  None of the above
10.

Which of the following algorithms is non stable? (select all that apply)
- A.
  
  Heap sort
- B.
  
  Selection sort
- C.
  
  Shell sort
- D.
  
  Merge sort
- E.
  
  Insertion sort
- F.
  
  Quick sort
11.

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?
- A.
  
  5
- B.
  
  1
- C.
  
  3
- D.
  
  7
12.

Which of a) to d) is true: The size of a hash table with n keys:
- A.
  
  Should be n for double-hashing
- B.
  
  Should be a prime number greater than n for linear probing
- C.
  
  Should be a prime number and less than 2ⁿ for quadratic probing
- D.
  
  None of these
13.

Which of the following algorithms requires the most extra space memory (not in place algorithm)?
- A.
  
  Insertion sort
- B.
  
  Selection sort
- C.
  
  Merge sort
- D.
  
  Shell sort
14.

N elements are inserted from a min-heap with N elements. The total running time is:
- A.
  
  O(n) worst case and O(1) average case
- B.
  
  O(log n) worst case and O(log n) average case
- C.
  
  O(n) worst case and O(n log n) average case
- D.
  
  O(log n) worst case and O(1) average case
- E.
  
  O(n log n) worst case and O(n log n) average case
15.

Which of the following algorithms runs in O(n log n) average time but O(n²) worst-case time?
- A.
  
  Heapsort
- B.
  
  Insertion sort
- C.
  
  Mergesort
- D.
  
  Quicksort
- E.
  
  Shellsort