锐客网

  1. 首页 > it技术 > >

CSCI2100D 分析

后端

CSCI2100D 2020-21: Assignment 2?
This assignment is due at 17:00 (5pm), 23rd April 2021. 【CSCI2100D 分析】■ 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

  1. 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
  2. are the non-internal nodes of 0.)

    推荐阅读


    上一篇：二.|二. 手写SpringMVC框架

    下一篇：大数定律