2022 p1

Question 1

Big-O time complexity for Bubble sort

Answer 1

O(n^2)

Question 2

Big-O time complexity for Linear search

Answer 2

O(n)

Question 3

Big-O time complexity for Merge sort

Answer 3

O(nlogn)

Question 4

Describe the method that would need to be followed to attempt to remove an item from a circular queue implemented as a static data structure using an array

Answer 4

1. check if the queue is empty by comparing the front and rear pointer. if equal, the queue is empty and no item can be removed.
2. if not empty, remove the front item from the front of the queue.
3. update the front pointer to the next item in the queue. if the front pointer exceeds the size of the array, reset it to 0.
4. reduce the count of items in the queue by 1

Question 5

three differences between dynamic and static data structures

Answer 5

static data structures memory are allocated at compile time/dynamic data structure memory are allocated at run time.

static data structure size is fixed and cannot change during runtime/ dynamic data structure size can be changed during runtime

static data structure memory is managed by compiler/ dynamic data structure memory is managed by the programmer

Question 6

explain how a single stack can be used to reverse the order of the items in a queue

Answer 6

1. deque all the items from the queue and push them onto the stack
2. pop them off one by one and enqueue them back into the original queue
3. the order of the items in the queue will be reversed