” 写作CSCI2100D程序、 辅导CS，PythonCSCI2100D 2020-21: Assignment 2# This assignment is due at 17:00 (5pm), 23rd April 2021.■ Q1. [18 marks] Answer the following questions related to queue. (i) [4 marks] Given the following queue (size is 6), what will it look like afterdequeue(), (ii) [4 marks] Given a queue with size 5, what will be the output of the followingoperations. Assume that initially the queue is empty.enqueue(2), enqueue(4), enqueue(6), dequeue(), enqueue(5), dequeue(), enqueue(7),dequeue(), enqueue(9), dequeue() (iii) [10 marks] Suppose you have three queues q1, q2, q3 (size = 4) with startingconfiguration shown on the left, and Finishing condition shown on the right. Give asequence of dequeue and enqueue operations that take you from start to finish. Forexample, to dequeue an element of q1 and enqueue it into q2, you may write downdequeue q1 and enqueue to q2 as your answer.startfront front frontDepartmental Guideline for Plagiarism (Department of Systems Engineering and Engineering Management): Ifa student is found plagiarizing, his/her case will be reported to the Department Examination Panel. If the case isproven after deliberation, the student will automatically fail the course in which he/she committed plagiarism.The definition of plagiarism includes copying of the whole or parts of written assignments, programmingexercises, reports, quiz papers, mid-term examinations and final examinations. The penalty will apply to boththe one who copies the work and the one whose work is being copied, unless the latter can prove his/herwork has been copied unwittingly. Furthermore, inclusion of others works or results without citation inassignments and reports is also regarded as plagiarism with similar penalty to the offender. A student caughtplagiarizing during tests or examinations will be reported to the Faculty office and appropriate disciplinaryauthorities for further action, in addition to failing the course.2■ Q2. [8 marks] (i) [4 marks] Consider the queue introduced on the slide 4-5 of Chapter 4. Queues.What is the time complexity of int dequeue(queue *q). (ii) [4 marks] Consider the circular queue introduced on the slide 16-18 of Chapter4. Queues, what are the advantage of circular queue, compared with the queue in (i).■ Q3. [34 marks] Answer the following questions related to sorting. (i) [8 marks] Consider an array 1 [1..6] = (15, 10, 5, 2, 20, 25). Following the pseudocodein slide 42 of Chapter 6. Sorting, sort 1 in ascending order using heapsort. You need to show the Contents of 1 after each step as in slide 43. (ii) [8 marks] Given an array 2 [0..7] = (2, 1, 4, 9, 6, 5, 8, 3), illustrate how to sortthis array by merge sort in ascending order as in slide 33 of Chapter 6. Sorting. (iii) [10 marks] Given an array 3 [0..8] = (7, 10, 9, 1, 11, 6, 4, 8, 2), illustrate howto sort this array by quick sort as in slide 16 of Chapter 6. Sorting with thefollowing strategies: (a) [5 marks] Pick the median-of-three as the pivot. Use partition methodat slide 19 chapter 6. (When the (sub)array contains even number of elements,there are two middle elements. Please pick the first middleelement (the one with smaller array index) as the middle element), e.g.,among [1 3 2 4], middle elements are 3 and 2 and we pick 3 as the middleelement. (b) [5 marks] Pick the first element as the pivot. Use In-Place partition methodat slide 20 chapter 6. (iv) [8 marks] Given an array 4 [0.. 1] which contains integers, design analgorithm, denoted by kthLargest(4, ), in pseudocode to find the -th largestinteger in 4, where 1 . For example, consider = 5 and 4 [0..4] =(3, 3, 0, 1, 4). Then 1 =kthLargest(4, 2) = 3 and 2 =kthLargest(4, 3) = 3. Notewe do not accept trivial solutions such as returning 4 [ ] after sorting 4.(Hint: In quicksort, an element is randomly selected as the pivot value and the arrayis reorganized (Fig. 1). Let the # of elements larger than be . By comparing with, we will know whether = , or . Then, we can proceed the searchin one of the subarrays recursively, until the target is found. For convenience, inyour algorithm, you can Call partition to represent the in-place partition methoddescribed in slide 20 of Chapter 6. Sorting, and with adequate explanation,reasonable helper functions may also be used, e.g. declaring randomInt(,)that returns an integer randomly between [,].)elements smaller than elements larger than Fig. 1. PartitioningCSCI2100D 2020-21: Assignment 2 3■ Q4. [18 marks] Consider the binary search tree 0 shown in Fig. 2. (i) [4 marks] Insert 5 and 9 sequentially into 0. Show the resulting trees after eachinsertion. (ii) [4 marks] Delete 8 and 2 sequentially from (the original) 0, using the approachas described in the lecture. Show the resulting trees after each deletion. (iii) [6 marks] Generally, given a binary search tree of height , what are the timecomplexities (in Big-Oh) of the following operations? Explain briefly. (a) [2 marks] Searching (b) [2 marks] Deletion (c) [2 marks] Insertion (iv) [4 marks] Show the Nodes visited in order when searching for 6 and 13 in 0respectively.■ Q5. [22 marks] (i) [6 marks] Consider the binary search tree 0 shown in Fig. 2, write down theInorder, Preorder and Postorder traversal of the given tree. (ii) [6 marks] From the following traversals of a complete binary tree, reconstructand draw the complete binary tree. Some nodes are hidden as #. Inorder: ## ### Preorder: ##### Postorder: ### ## (iii) [8 marks] Determine if the following statement is true. If true, justify youranswer by giving a brief proof; if false, give a counter-example. (a) [4 marks] The structure of a binary tree can be determined given only thesequences of preorder and Postorder traversals of it. (b) [4 marks] There must be more non-internal nodes than internal nodes ina complete binary tree. (In a binary tree, an internal node is any node that isneither the root nor a leaf. A non-internal node, thus, refers to either the root4or a leaf. For instance, 2, 4, 10 and 12 are the internal nodes, and 8, 1, 3, 11 and14 are the non-internal nodes of 0.)请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
