CS 302 midterm UPDATED Exam Questions
and CORRECT Answers
In the context of data structures, why would using a language with the Standard Template
Library (STL) be advantageous? - CORRECT ANSWER -
Suppose I wanted to implement a sequence container by using an linked list using a single
pointer (e.g., front). What would be the complexity in terms of Big-O for the following
operations:
- Locate an element based on its value
- Insert an element in the front
- Insert an element in the back - CORRECT ANSWER - locate = O(n)
insert front = O(1)
insert back = O(n)
Describe one operation where a doubly linked list would have a better time complexity when
compared to the same operation applied on a more "generic" singly linked list? - CORRECT
ANSWER - adding, removing, accessing data is all O(1) compared to O(n) for singly
linked lists
Trace the execution of insertion sort for an array containing {9, 6, 0, 0, 7}, i.e., show the contents
of the array after each iteration of the sorting algorithm. - CORRECT ANSWER - Initial
Array:
[9, 6, 0, 0, 7]
Iteration 1:
Compare 6 with 9
[6, 9, 0, 0, 7]
Iteration 2:
Compare 0 with 9
, Compare 0 with 6
[0, 6, 9, 0, 7]
Iteration 3:
Compare 0 with 9
Compare 0 with 6
Compare 0 with 0 (first 0) and shift the first 0 to the right.
[0, 0, 6, 9, 7]
Iteration 4:
Compare 7 with 9
Compare 7 with 6
[0, 0, 6, 7, 9]
Final Sorted Array:
[0, 0, 6, 7, 9]
quick sort is another, but more complicated example, of a divide and conquer algorithm. Explain
what happens during the partitioning phase of the algorithm and why the choice of a pivot is
important for efficiency. If it helps, think of the best and worse case pivots and how they affect
the big-Oh of this sorting method. - CORRECT ANSWER -
merge sort is the prototypical example of a divide and conquer algorithm. In your own words,
explain what happens during the divide portion of the algorithm and what happens during the
conquer phase of merge sort. Finally, in your own words why is this an O(n log n) algorithm? -
CORRECT ANSWER - in the divide phase, the array is recursively split into subarrays
until each contains 1 element. conquer mergers the subarrays recursively while maintaining the
sorted order of the elements. The time complexity is log(n) for division and O(n) during merge,
so the overall time complexity is O(n log n)
and CORRECT Answers
In the context of data structures, why would using a language with the Standard Template
Library (STL) be advantageous? - CORRECT ANSWER -
Suppose I wanted to implement a sequence container by using an linked list using a single
pointer (e.g., front). What would be the complexity in terms of Big-O for the following
operations:
- Locate an element based on its value
- Insert an element in the front
- Insert an element in the back - CORRECT ANSWER - locate = O(n)
insert front = O(1)
insert back = O(n)
Describe one operation where a doubly linked list would have a better time complexity when
compared to the same operation applied on a more "generic" singly linked list? - CORRECT
ANSWER - adding, removing, accessing data is all O(1) compared to O(n) for singly
linked lists
Trace the execution of insertion sort for an array containing {9, 6, 0, 0, 7}, i.e., show the contents
of the array after each iteration of the sorting algorithm. - CORRECT ANSWER - Initial
Array:
[9, 6, 0, 0, 7]
Iteration 1:
Compare 6 with 9
[6, 9, 0, 0, 7]
Iteration 2:
Compare 0 with 9
, Compare 0 with 6
[0, 6, 9, 0, 7]
Iteration 3:
Compare 0 with 9
Compare 0 with 6
Compare 0 with 0 (first 0) and shift the first 0 to the right.
[0, 0, 6, 9, 7]
Iteration 4:
Compare 7 with 9
Compare 7 with 6
[0, 0, 6, 7, 9]
Final Sorted Array:
[0, 0, 6, 7, 9]
quick sort is another, but more complicated example, of a divide and conquer algorithm. Explain
what happens during the partitioning phase of the algorithm and why the choice of a pivot is
important for efficiency. If it helps, think of the best and worse case pivots and how they affect
the big-Oh of this sorting method. - CORRECT ANSWER -
merge sort is the prototypical example of a divide and conquer algorithm. In your own words,
explain what happens during the divide portion of the algorithm and what happens during the
conquer phase of merge sort. Finally, in your own words why is this an O(n log n) algorithm? -
CORRECT ANSWER - in the divide phase, the array is recursively split into subarrays
until each contains 1 element. conquer mergers the subarrays recursively while maintaining the
sorted order of the elements. The time complexity is log(n) for division and O(n) during merge,
so the overall time complexity is O(n log n)
