Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

Electrical Engineering & Computer Science

EECS 281: Data Structures and Algorithms

Fall 2024

PRACTICE MIDTERM EXAM

KEY 1

Multiple Choice Portion [60 points]

MULTIPLE CHOICE INSTRUCTIONS:

• Select only ONE answer per multiple choice question.
• There are 24 multiple choice questions worth 2.5 points each.
• Record your choices for all multiple choice questions using the circles in the boxed area next to each question. Use a number 2 pencil, not a pen (so that you may change your answer).  Fill the circle completely. There is no partial credit for multiple-choice questions.  Make sure you bubble in the correct letter. See the example below for how to select your answer.
• There is no penalty for wrong answers: it is to your benefit to record an answer to each multiple- choice question, even if you’re not sure what the correct answer is.
• The questions vary in difficulty — try not to spend too much time on any one question. Use your time wisely.
• When asked about memory complexity, consider all possible sources (stack and heap).
• The term "heap" as a data structure refers to a binary heap, unless explicitly stated otherwise.
• The term "binary search tree" refers to a standard implementation that does not self-balance, unless explicitly stated otherwise.

1. Master Theorem

Which of the following recurrence relations can one solve by applying the Master Theorem?

A) T(n) = 2/1T(4/n) + Θ(n)

B) T(n) = T(2/n) + Θ(nlog2 4)

C) T(n) = 4T(n — 1) + Θ(1)

D) T(n) = 4T(2/n) + 2T(4/n) + Θ(n2)

E) None of the above.

2. Measuring Runtime

Consider the following function:

1 int func(double m, double n)  {

2 int c  =  0;

3 while (m  >  n)  {

4                          m  =  m/2;

5 for (int i  =  1;  i  < n; i *=3;)

6                                      ++c;

7                }  //  while

8

9 return c;

10        }  //  func

What best characterizes the running time of a call to this function?

A) O(nlog m)

B) O( log n)

C) O((log ) · (log n))

D) O(mnlog(mn))

E) O(mn · (log m) · (log n))

5. Recursion

Consider the following recurrence relation:

T(n) = {c0, n             n= 1

nT(n - 1) + c, n>1

What is the complexity of T(n)?

A) Θ(nlog n)

B) Θ(n2 )

C) Θ(n3 )

D) Θ(cn )

E) Θ(n!)

6. Queues

What is the best possible space complexity for a function printing out the contents of a std::queue of size n in order, such that the contents and order of the queue are the same before and after the function is called and executed? 

This means the auxiliary, or additional, space required to make this occur, not the space taken up by the data that was in the queue to begin with. You can assume that the queue is passed by reference.

A) O(1)

B) O(n)

C) O(n2 )

D) O(n3 )

7. Code Analysis

NOTE: Same code as next page, different question

Consider an array data of size n which contains 0s and 1s.  Each element of this array containing 0 appears before all those elements containing 1. For example, [0, 0, 0, 0, 1] is such an array.

1 int myFunction(int data[], int length)  {

2 int mid  =  0,  left  =  0; int right  =  length  -  1;

3 if (data[0]  ==  1)

4 return 0;

5 else if (data[length  -  1]  ==  0)

6 return length;

7 else {

8 bool isFound  = false ;

9 while (!isFound)  {

10                                        mid  =  left  +   (right  -  left)  /  2;

11 if (data[mid]  ==  0)

12                                                    left  =  mid  +  1;

13 else {

14 if (data[mid  -  1]  ==  0)

15                                                               isFound  = true ;

16 else

17                                                               right  =  mid  -  1; 18                                         }  //  else

19                              }  //  while

20 return mid;

21                   }  //  else

22        }  //  myFunction()

In general, what does the function return when it is given such an array?

A) Number of 0’s in data[]

B) Number of 1’s in data[]

C) (Number of 0’s in data[]) + 1

D) (Number of 1’s in data[]) + 1

E) (Number of 1’s in data[]) - 1

8. Complexity of Code

NOTE: Same code as previous page, different question

Consider an array data of size n which contains 0s and 1s.  Each element of this array containing 0 appears before all those elements containing 1. For example, [0, 0, 0, 0, 1] is such an array.

1 int myFunction(int data[], int length)  {

2 int mid  =  0,  left  =  0; int right  =  length  -  1;

3 if (data[0]  ==  1)

4 return 0;

5 else if (data[length  -  1]  ==  0)

6 return length;

7 else {

8 bool isFound  = false ;

9 while (!isFound)  {

10                                        mid  =  left  +   (right  -  left)  /  2;

11 if (data[mid]  ==  0)

12                                                    left  =  mid  +  1;

13 else {

14 if (data[mid  -  1]  ==  0)

15                                                               isFound  = true ;

16 else

17                                                               right  =  mid  -  1; 18                                         }  //  else

19                              }  //  while

20 return mid;

21                   }  //  else

22        }  //  myFunction()

What is the complexity of the above algorithm?

A) Θ(1)

B) Θ(log(log n))

C) Θ(log n)

D) Θ(n)

E) Θ(nlog n)

11. Heaps

Suppose that we wanted to add a function popRandom() to our priority queues in Project 2.  When implementing it with the binary heap, we could generate a random index, swap values between that index and the last element of the data vector, and call the vector’s pop_back() function.  What else would we have to do to preserve the binary heap property?  Choose the answer with the smallest worst-case complexity.

A) Call update_priorities().

B) Call fixDown() followed by fixUp(), both on the random index.

C) Call fixDown(), starting at the root of the heap.

D) Call fixUp(), starting at the last element of the heap.

E) Call exactly one of fixUp() or fixDown(), depending on the values swapped.

12. Reversing an Array

You are asked to reverse the order of an arbitrary array of length n in constant memory.  Your code skeleton looks like:

1 for ( . . . )  {

2                    std::swap(array[i],  array[n  -  i  -  1]);

3        }

What belongs in the for loop header?

A) for   (size_t  i  =  0;  i  < n; ++i)

B) for   (size_t  i  =  0;  i  < (n / 2); ++i)

C) for   (size_t  i  =  n;  i  >=  0;  --i)

D) None of the above