讲解CSCI2100D程序、辅导CS，Python编程、c++编程调试 解析Java程序|讲解SPSS
- 首页 >> Matlab编程 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.)
# 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.)