Advanced Algorithms And Complexity In Data Structures Quiz
(544).jpg "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(N2)
- C.
O(N3)
- D.
O(N4)
- E.
None of the above
Correct Answer
C. 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:
-
- 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(N2)
- C.
O(N3)
- D.
O(N4)
- E.
None of the above
Correct Answer
D. 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:
-
- 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(N4)
- B.
O(N5)
- C.
O(N6)
- D.
O(N7)
- E.
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:
-
- 4.
Suppose T1(n) = O(f(n)) and T2(n) = O(g(n)). Which of the following are true?
- A.
T1(n) + T2(n) = O(max(f(n), g(n)))
- B.
T1(n) * T2(n) = O(f(n) * g(n))
- C.
T1(n) / T2(n) = O(f(1))
- D.
T1(n) = O(T2(n))
- E.
None of the above
Correct Answer(s)
A. T1(n) + T2(n) = O(max(f(n), g(n)))
B. 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:
-
- 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(N2)
Correct Answer
C. 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:
-
- 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
Correct Answer
A. Find an element in an unsorted arrayExplanation
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:
-
- 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
Correct Answer
B. PostorderExplanation
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.
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
Correct Answer
A. InorderExplanation
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:
-
- 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
Correct Answer
B. With minimum weight so that cost of MST is always minimumExplanation
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:
-
- 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
Correct Answer(s)
A. Heap sort
B. Selection sort
C. Shell sort
F. Quick sortExplanation
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:
-
- 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
Correct Answer
D. 7Explanation
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:
-
- 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 2n for quadratic probing
- D.
None of these
Correct Answer
B. Should be a prime number greater than n for linear probingExplanation
For linear probing, the size of the hash table should be a prime number greater than n. This is because linear probing uses a simple linear function to resolve collisions, which means that if two keys hash to the same index, the second key will be placed in the next available slot in the table. Using a prime number as the size of the table helps to minimize clustering and distribute the keys more evenly, reducing the number of collisions and improving the performance of the hash table. Therefore, the correct answer is that the size of the hash table should be a prime number greater than n for linear probing.Rate this question:
-
- 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
Correct Answer
C. Merge sortExplanation
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:
-
- 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
Correct Answer
D. O(log n) worst case and O(1) average caseExplanation
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 runs in O(n log n) average time but O(n2) worst-case time?
- A.
Heapsort
- B.
Insertion sort
- C.
Mergesort
- D.
Quicksort
- E.
Shellsort
Correct Answer
D. QuicksortExplanation
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:
-
Quiz Review Timeline +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Jun 18, 2023Quiz Edited by
ProProfs Editorial Team -
Jun 13, 2022Quiz Created by
Themes
- Binary Code Quizzes
- Computer Concept Quizzes
- Computer Essential Quizzes
- Computer Forensics Quizzes
- Computer Hardware Quizzes
- Computer Networking Quizzes
- Computer Parts Quizzes
- Computer Programming Quizzes
- Computer Science Quizzes
- Computer Security Quizzes
- Computer Shortcut Key Quizzes
- Computer Skills Quizzes
- Computer Virus Quizzes
- Cyber Security Quizzes
- Data Quizzes
- Data Security Quizzes
- Hacking Quizzes
- HCI Quizzes
- Internet Quizzes
- IT SecurITy Quizzes
- Malware Quizzes
- Microprocessor Quizzes
- Network Quizzes
- Operating System Quizzes
- Phishing Quizzes
- Programming Language Quizzes
- Server Quizzes
- Software Quizzes
Back to top