# 算法代写｜COMP90038 Algorithms and Complexity Practice Exam

Question 1 (4 marks)

A. Give the names of two stable sorting algorithms, together with their worst-case time
complexities. Write the names and complexities in the box:

B. Give the names of two unstable sorting algorithms, together with their worst-case time
complexities. Write the names and complexities in the box:

Question 2 (4 marks)

We are given an array A holding n integers, for some large n. The array is sorted, and the
values in A range from -2147483648 to 2147483647, evenly distributed. Give Θ expressions

A. Running the insertion sort algorithm on the array A:
B. Running the selection sort algorithm on the array A:
C. Performing binary search for integer k which is not in A:
D. Performing interpolation search for integer k not in A:

Question 3 (4 marks)

For the directed graph below, list the order in which the nine nodes are visited during a
depth-first (DFS) traversal, as well as the order in which they are visited during a breadth
first (BFS) traversal. As always, assume that any ties are resolved by taking nodes in
alphabetical order. Write the answers in the boxes given Question 4 (4 marks)

Given the pattern A T G A and the text

T C A T C A T C C A T G C A C A A T G A C T T T

how many character comparisons will Horspool’s algorithm make before locating the pattern
in the text? Write the number in the box:

Question 5 (4 marks)

Assume the array A holds the keys 77, 64, 15, 43, 28, 91, 80, 32, 56 in index positions 1 to 9.
Show the heap that results after application of the linear-time bottom-up heap construction
algorithm. You may show the heap as a tree or as an array. E-mail: itcsdx@outlook.com  微信:itcsdx 