Use the 27 quiz questions to prepare yourself and test whether you know the subject matter.

Buy the quiz questions and be prepared for your next test.

Add to cart◄

►

What does it mean that the lower-bound on the worst-case time complexity for comparison-based sorting is Omega (n log(n))?

A) It means that the worst-case of a comparison-based sorting algorithm is at most n log(n).

B) It means that the worst-case of a comparison-based sorting algorithm is at least n log(n).

C) It means that using comparison-based sorting we cannot sort slower than in n log(n).

D) It means that using comparison-based sorting we cannot sort faster than in n log(n).

We consider bucket sort.

What is the worst-case running time of bucket sort?

A) It is in Theta (n), because the for-loops are not nested.

B) It is in Theta (n^2), because we may call insertion sort, which is quadratic, on an input of size n, namely if (floor of nA[i]) is the same for all indices i.

C) It is in Theta (n^2), because worst-case sorting is always in n^2.

D) It is in Theta (n^3), because we may call insertion sort which is quadratic n times.

Which of the following is(are) in increasing rate of growth?

A) n log(n), n^2, 2^7, n!

B) 3n, 2^3, n log(n), n^3

C) 2^7, n log(n), n^2, n!

D) n log(n), n^2, n^7, 2^n

E) n^2, n^3, n log(n), 2^n

In the recurrence tree for merge sort

A) The height is n and the work per layer is the linear work to merge

B) The height is log(n) and the work per layer is the linear work to split.

C) The height is n and the work per layer is the linear work to split.

D) The height is log(n) and the work per layer is the linear work to merge.

We consider a decision tree for a comparison-based sorting tree for sorting an array of size n. The smallest possible depth of a leaf is

A) n

B) n log(n)

C) n!

D) log(n)

Buy the quiz questions and be prepared for your next test.

Add to cart◄

►

Do you prefer to learn the quiz questions from paper? Then download the 27 questions as PDF.

Add to cartEarn money by making quiz questions and learn directly for your upcoming test.

Create quizData structures and algorithms midterm practice test. can be used to practice

27 questions

English

06-01-2022

Universiteit / Vrije Universiteit Amsterdam / Business Analytics / Data Structures and Algorithms

gabigonza

- 1 quizzes available