TITLE
代做Algorithm – 该题目是一个常规的Algorithm的练习题目代写, 是比较有代表性的Algorithm等代写方向
Enrolment number (student number):
Practice Exam Paper
School of Computing and Information Systems
COMP90038 Algorithms and Complexity
Reading Time: 15 minutes
Exam Duration: 3 hours
This paper has 11 pages, including this front page.
Authorised Materials:
None. This is a closed book exam. Electronic devices, including calculators and laptop
computers arenotpermitted.
Instructions to Invigilators:
Students will provide answers in the exam paper itself. The exam paper must remain in
the exam venue and must be returned to the examiner.
Instructions to Students:
This is not an actual exam paper. It is a practice paper which has been put together
to show you the format that you can expect in the exam. Many aspects of this papers
contents do not necessarily reflect the contents of the actual exam paper: The selection
of topics, the number of questions or sub-questions, the perceived difficulty of individual
questions, and the distribution of weights are all aspects that maybe different. When
preparing for the exam, you should cover the entire syllabus and not focus only on topics
or question types used in this practice paper. If anything, the exam paper can be expected
to be harder than this practice paper.
There are 12 questions. As in the exam, you should attempt them all. Of course
your answers must bereadable. Any unreadable parts will be considered wrong. You will
find some questions easier than others; in the actual exam you should allocate your time
accordingly. Marks are indicated for each question, adding to a total of 70.
The actual exam paper will be printed single-sided, so you will have plenty of space
for rough work on the flip sides. Only what you write inside the allocated boxes will be
marked. Page 11 is overflow space, in case you need more writing space for some question.
Examiners use:
1 2 3 4 5 6 7 8 9 10 11 12
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 twounstablesorting algorithms, together with their worst-case time complexities. Write the names and complexities in the box:
Question 2 (4 marks)
We are given an arrayAholdingnintegers, for some largen. The array is sorted, and the values inArange from -2147483648 to 2147483647, evenly distributed. Give expressions for the following tasks:
A. Running the insertion sort Algorithm on the arrayA:
B. Running the selection sort algorithm on the arrayA:
C. Performing binary search for integerkwhich is not inA:
D. Performing interpolation search for integerknot inA:
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 arevisited during a breadth- first (BFS) traversal. As always, assume that anyties are resolvedby taking nodes in alphabetical order. Write the answers in the boxes given.
a
b c d
e
h g f
x
DFS sequence:
BFS sequence:
Question 4 (4 marks)
Given the patternA T G Aand 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 Horspools algorithm make before locating the pattern in the text? Write the number in the box:
Question 5 (4 marks)
Assume the arrayAholds 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.
Question 6 (4 marks)
The functionsADare defined recursively as follows (all divisions round down, to the closest integer): A(n) = 2A(n/3) + 2, withA(1) = 1 B(n) = B(n/2) +n/ 2 , withB(1) = 1 C(n) = 512C(n/8) + 4n^2 , withC(1) = 4 D(n) = 4D(n/2) +n^2 , withD(1) = 2
In the following table, for each of the four functions, tick the mostprecise correct statement about the functions rate of growth:
O(n) (n) O(nlogn) (n^2 ) O(n^2 logn) (n^2
n) O(n^3 )
A
B
C
D
Question 7 (4 marks)
For each ofADbelow, answer yes or no, and, in each case, briefly explain your reasoning (just a justification of your answer, rather than detailed calculations). A yes/no answer that is not justified will not attract marks, even if correct.
Question Answer/explanation
A.
Is
n(n)?
B.
Isn2 lognO(nlogn)?
C.
Is (log(n2 logn)) =
(log(nlogn))?
D.
Is (log(2n)) =
(log(3n))?
Question 8 (6 marks)
A.The box below contains a weighted undirected graph with eight nodes. Give a minimum spanning tree for the graph. You may do that either by outlining a minimum spanning tree on the graph itself, or by drawing the tree in the empty space next to the graph.
a b
c
d
f e
g
h
5
4 7
6 4
9
(^37)
5
8
4
8
6
B.Given a weighted graphG=V, E, a subgraphV, E(that is,EE) which is a tree with minimal weight is amaximum spanning treeforG. We want a transformation of the graphGso that we can run Prims algorithm on the transformed graphG, and the algorithm will find a maximum spanning tree forG. Describe such a (systematic) transformation fromGtoG.
Question 9 (6 marks)
Consider the functionFbelow. The function takes as input an integer arrayA, and the size nofA. The array indices run from 1 ton. The division used is integer division, that it, it rounds down to the closest smaller (or equal) integer value.
In the box, give a expression for the functions time complexity.
functionF(A[], n)
s 0
mn
whilem > 0 do
fori 1 tomdo
ss+A[i]
mm/ 2
Question 10 (10 marks)
Using pseudo-code, give an algorithm for deleting the smallest element of a binary search tree (a BST). Assume a non-empty binary treeThas attributesT.left,T.right, andT.root which denoteTs left sub-tree, right sub-tree, and the key ofTs root node, respectively. You can use these tests if they seem useful: IsLeaf(T) tests whether the binary treeTis a leaf, andIsEmpty(T) tests whether it is empty.
Question 11 (10 marks)
Consider an arrayAofndistinct integers (that is, all elements are different). It is known thatAwas originally sorted in ascending order, butAwas then right-rotatedrplaces, where 0 < r < n. In other words, the lastrelements were moved from the end of the array to the beginning, with all other elements being pushedrpositions to the right. For example, for n= 7 andr= 3, the result may look like this:
[43, 46 , 58 , 12 , 20 , 29 ,34]
Forr= 5, the result, based on the same original array, would be
[29, 34 , 43 , 46 , 58 , 12 ,20]
You know that the givenA[0..n1] has this particular form, that is, for somer, the sequence A[r],… , A[n1], A[0],… A[r1] is in ascending order, but you do not know whatris. Design an algorithm to find the largest integer inA. Full marks are given for an algorithm that works in time O(logn); half marks are given for a solution that is correct, but less efficient.
Question 12 (10 marks)
Two programmers face the following problem. Given an array containingnrandom integers in random order, find the largest integer. The integers are placed incellsA[1]… A[n]. ProgrammerXhas come up with the code shown below, on the left. (In the programming language used, arrays are indexed from 0, butXs method does not useA[0].)
functionX(A[], n)
maxA[1]
i 2
whileindo
ifA[i]>maxthen
maxA[i]
ii+ 1
returnmax
functionY(A[], n)
in
whilei > 0 do
A[0]A[i]
ii 1
whileA[0]> A[i]do
ii 1
returnA[0]
ProgrammerY has solved the same problem differently, as shown above on the right.
Compare the two solutions using three criteria: Correctness, timecomplexity class, and the number of comparisons performed. Write your analysis in the box:
[COMP90038] [end of exam]
Overflow space
Use this page if you ran out of writing space in some question. Make sure to leave a pointer to this page from the relevant question.