代做CSCI2100D程序、代写CS，Python编程、c++代写编程调试

日期：2021-03-31 11:35

CSCI2100D 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 after

dequeue(),

– (ii) [4 marks] Given a queue with size 5, what will be the output of the following

operations. 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 starting

configuration shown on the left, and finishing condition shown on the right. Give a

sequence of dequeue and enqueue operations that take you from start to finish. For

example, to dequeue an element of q1 and enqueue it into q2, you may write down

"dequeue q1 and enqueue to q2" as your answer.

start

front front front

∗Departmental Guideline for Plagiarism (Department of Systems Engineering and Engineering Management): If

a student is found plagiarizing, his/her case will be reported to the Department Examination Panel. If the case is

proven 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, programming

exercises, reports, quiz papers, mid-term examinations and final examinations. The penalty will apply to both

the one who copies the work and the one whose work is being copied, unless the latter can prove his/her

work has been copied unwittingly. Furthermore, inclusion of others’ works or results without citation in

assignments and reports is also regarded as plagiarism with similar penalty to the offender. A student caught

plagiarizing during tests or examinations will be reported to the Faculty office and appropriate disciplinary

authorities 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 Chapter

4. 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 pseudocode

in slide 42 of Chapter 6. Sorting, sort 𝐴1 in ascending order using heap

sort. 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 sort

this 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 how

to sort this array by quick sort as in slide 16 of Chapter 6. Sorting with the

following strategies:

∗ (a) [5 marks] Pick the median-of-three as the pivot. Use partition method

at slide 19 chapter 6. (When the (sub)array contains even number of elements,

there are two "middle" elements. Please pick the first middle

element (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 middle

element.

∗ (b) [5 marks] Pick the first element as the pivot. Use In-Place partition method

at slide 20 chapter 6.

– (iv) [8 marks] Given an array 𝐴4 [0..𝑛 − 1] which contains 𝑛 integers, design an

algorithm, denoted by kthLargest(𝐴4, 𝑘), in pseudocode to find the 𝑘-th largest

integer 𝑠𝑘 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. Note

we 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 array

is reorganized (Fig. 1). Let the # of elements larger than 𝑣 be 𝑛𝑟

. By comparing 𝑛𝑟 with

𝑘, we will know whether 𝑙𝑘 = 𝑣, 𝑙𝑘 < 𝑣 or 𝑙𝑘 > 𝑣. Then, we can proceed the search

in one of the subarrays recursively, until the target is found. For convenience, in

your algorithm, you can call partition to represent the in-place partition method

described 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. Partitioning

CSCI2100D 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 each

insertion.

– (ii) [4 marks] Delete 8 and 2 sequentially from (the original) 𝑇0, using the approach

as 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 time

complexities (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 𝑇0

respectively.

■ Q5. [22 marks]

– (i) [6 marks] Consider the binary search tree 𝑇0 shown in Fig. 2, write down the

Inorder, Preorder and Postorder traversal of the given tree.

– (ii) [6 marks] From the following traversals of a complete binary tree, reconstruct

and 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 your

answer 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 the

sequences of preorder and postorder traversals of it.

∗ (b) [4 marks] There must be more non-internal nodes than internal nodes in

a complete binary tree. (In a binary tree, an internal node is any node that is

neither the root nor a leaf. A non-internal node, thus, refers to either the root

4

or a leaf. For instance, 2, 4, 10 and 12 are the internal nodes, and 8, 1, 3, 11 and

14 are the non-internal nodes of 𝑇0.)