COMP90038程序写作、辅导Java，c++

” COMP90038程序写作、辅导Java，c++Enrolment number (student number):The University of MelbournePractice Exam PaperSchool of Computing and Information SystemsCOMP90038 Algorithms and ComplexityReading Time: 15 minutesExam Duration: 3 hoursThis paper has 11 pages, including this front page.Authorised Materials:None. This is a Closed book exam. Electronic devices, including calculators and laptopcomputers are not permitted.Instructions to Invigilators:Students will provide answers in the exam paper itself. The exam paper must remain inthe 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 togetherto show you the format that you can expect in the exam. Many aspects of this paperscontents do not necessarily reflect the contents of the actual exam paper: The selectionof topics, the number of questions or sub-questions, the perceived difficulty of individualquestions, and the distribution of weights are all aspects that may be different. Whenpreparing for the exam, you should cover the entire syllabus and not focus only on topicsor question types used in this practice paper. If anything, the exam paper can be expectedto be harder than this practice paper.There are 12 questions. As in the exam, you should attempt them all. Of courseyour answers must be readable. Any unreadable parts will be considered wrong. You willfind some questions easier than others; in the actual exam you should allocate your timeaccordingly. 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 spacefor rough work on the flip sides. Only what you write inside the allocated boxes will bemarked. 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 12Page 2 of 11Question 1 (4 marks)A. Give the names of two Stable sorting algorithms, together with their worst-case timecomplexities. Write the names and complexities in the box:B. Give the names of two unstable sorting algorithms, together with their worst-case timecomplexities. 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 thevalues in A range from -2147483648 to 2147483647, evenly distributed. Give expressionsfor the following tasks: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:[COMP90038] [please turn over . . . ]Page 3 of 11Question 3 (4 marks)For the directed graph below, list the order in which the nine nodes are visited during adepth-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 inalphabetical order. Write the answers in the boxes given.DFS sequence:BFS sequence:Question 4 (4 marks)Given the pattern A T G A and the textT C A T C A T C C A T G C A C A A T G A C T T Thow many character Comparisons will Horspools algorithm make before locating the patternin the text? Write the number in the box:[COMP90038] [please turn over . . . ]Page 4 of 11Question 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 constructionalgorithm. You may show the heap as a tree or as an array.Question 6 (4 marks)The functions AD are defined recursively as follows (all divisions round down, to the closestinteger):A(n) = 2 A(n/3) + 2, with A(1) = 1B(n) = B(n/2) + n/2, with B(1) = 1C(n) = 512 C(n/8) + 4n2, with C(1) = 4D(n) = 4 D(n/2) + n2, with D(1) = 2In the following table, for each of the four functions, tick the most precise correct statementabout the functions rate of growth:[COMP90038] [please turn over . . . ]Page 5 of 11Question 7 (4 marks)For each of AD below, 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 thatis not justified will not attract marks, even if correct.Question Answer/explanationQuestion 8 (6 marks)A. The box below contains a weighted undirected graph with eight nodes. Give a minimumspanning tree for the graph. You may do that either by outlining a minimum spanning treeon the graph itself, or by drawing the tree in the empty space next to the graph.B. Given a weighted graph G = 〈V,E〉, a subgraph 〈V,E 〉 (that is, E ? E) which is a treewith minimal weight is a maximum spanning tree for G.We want a transformation of the graph G so that we can run Prims algorithm on thetransformed graph G, and the algorithm will find a maximum spanning tree for G.Describe such a (systematic) transformation from G to G.[COMP90038] [please turn over . . . ]Page 7 of 11Question 9 (6 marks)Consider the function F Below. The function takes as input an integer array A, and the sizen of A. The array indices run from 1 to n. The division used is integer division, that it, itrounds down to the closest smaller (or equal) integer value.In the box, give a expression for the functions time complexity.function F(A[], n)s 0m nwhile m 0 dofor i 1 to m dos s+ A[i]m m/2[COMP90038] [please turn over . . . ]Page 8 of 11Question 10 (10 marks)Using pseudo-code, give an algorithm for deleting the smallest element of a binary searchtree (a BST). Assume a non-empty binary tree T has attributes T.left , T.right , and T.rootwhich denote T s left sub-tree, right sub-tree, and the key of T s root node, respectively.You can use these tests if they seem useful: IsLeaf(T ) tests whether the binary tree T isa leaf, and IsEmpty(T ) tests whether it is empty.[COMP90038] [please turn over . . . ]Page 9 of 11Question 11 (10 marks)Consider an array A of n distinct integers (that is, all elements are different). It is knownthat A was originally sorted in ascending order, but A was then right-rotated r places, where0 r n. In other words, the last r elements were moved from the end of the array to thebeginning, with all other elements being pushed r positions to the right. For example, forn = 7 and r = 3, the result may look like this:[43, 46, 58, 12, 20, 29, 34]For r = 5, the result, based on the same original array, would be[29, 34, 43, 46, 58, 12, 20]You know that the given A[0..n?1] has this particular form, that is, for some r, the sequenceA[r], . . . , A[n ? 1], A[0], . . . A[r ? 1] is in ascending order, but you do not know what r is.Design an algorithm to find the largest integer in A. Full marks are given for an algorithmthat works in time O(logn); half marks are given for a solution that is correct, but lessefficient.[COMP90038] [please turn over . . . ]Page 10 of 11Question 12 (10 marks)Two programmers face the Following problem. Given an array containing n random integersin random order, find the largest integer. The integers are placed in cells A[1] . . .A[n].ProgrammerX has come up with the code shown below, on the left. (In the programminglanguage used, arrays are indexed from 0, but X s method does not use A[0].)function X(A[], n)max A[1]i 2while i n doif A[i] max thenmax A[i]i i+ 1return maxfunction Y(A[], n)i nwhile i 0 doA[0] A[i]i i? 1while A[0] A[i] doi i? 1return A[0]Programmer Y has solved the same problem differently, as shown above on the right.Compare the two solutions using three criteria: Correctness, time complexity class, and thenumber of comparisons performed. Write your analysis in the box:[COMP90038] [end of exam]Page 11 of 11Overflow spaceUse this page if you ran out of writing Space in some question. Make sure to leave a pointerto this page from the relevant question.请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp

“