Dsa Midterm Review Exam Questions & Answers

DSA MIDTERM REVIEW EXAM
QUESTIONS & ANSWERS



What is the worst case computational complexity of the following code snippet in terms
of Big O notation?

int sum = 0
for (int i=0; i<n; i++)
for (int j=0; j<i; j++)
sum = sum+j; - Correct Answers -O(n^2) (n squared)

What is the computational complexity of the following code snippet?

int result = 0
for (int i = 0; i < n; i++)
for (int j = i; j > 0; j--)
result += 1; - Correct Answers -O(n^2)

What is the worst case computational complexity of the following code snippet in terms
of Big O notation?

int x = 1
while (x < n)
x *= 2 - Correct Answers -O(log n)

What is the worst case computational complexity of the following code snippet in terms
of Big O notation?

result = 0
for (int i = 0; i < n; i++)
result += i;
for (int j = 1; j < m; j *= 2)
result *= j; - Correct Answers -O(n + log m)

Which of the following functions T(n), belongs to the family of O(n^3*(log2n)) - Correct
Answers -n^3*(log2(log2n))
n^2+n+5000
1000000
n^3

, n^3*(log3n)


Which of the following statements about linked lists and arrays are TRUE? - Correct
Answers --Both data structures can use iterators
-Both are linear data types

What is the computational complexity of deleting an element, e from a doubly linked list
with tail in the worst case in terms of Big O notation? Assume the list has n items. -
Correct Answers -O(n)

Which of the following container(s) is/are List ADT implementation(s) in C++? [Select all
that apply] - Correct Answers --Array
-Forward List
-Vector

What is the worst case computational complexity of the following code snippet in terms
of Big O notation?
result = 0
for (i=0; i<10; i++)
for (j=0; j<i; j++)
result += i*j; - Correct Answers -O(1)

An algorithm's runtime is given by T(n, m) = 3m^3+4m^3*log2⁡m+3n^2+n+100. -
Correct Answers -O(m^3*log2(m)+n^2)

Which family/families does the following function T(n) = n^5*log2(n) belong to? Check
all that apply. - Correct Answers -Ω(10000)
O(2000n^5+2000^n)
O(n^5log3(n))

Which of the following are FALSE? Select all that apply. - Correct Answers --The best
case time complexity of linear search is O(1) and occurs when there is just one element
in an array
-If the growth rate for algorithm A can be represented by T(n) = n and the growth rate for
algorithm B can be represented by U(n) = log(n) we can say that algorithm A is faster
than algorithm B.

Examine the following code snippets below and determine which has a slower growth
rate. Consider "c" to be a positive integer constant (c > 1) :

Snippet A:
for(int i = 0; i < n; i++){
for(int j = n; j > 0; j /= c){
print("Hello");}}