COMP2038代写、代写Java，c++程序设计

日期：2022-01-09 11:07

4 COMP2038-E1

COMP2038-E1 Turn over

3. Questions on Algorithm Analysis, Stack/Queue, B-Tree.

(a) “An O(1) algorithm whose running time is independent of the problem size will always be

superior to an O(n3) algorithm whose running time grows as the cube of the problem size.”

Is the above argument valid? If it is valid, justify your answer. If it is not, give a

counterexample.

[5 marks]

(b) A simple algorithm called copy sort sorts an array into ascending order. Copy sort

searches an array A to find the smallest element, copies it to array B, and “destroys” the

original value in A by setting it to a very large value. The process of searching A, copying the

value into the next cell of B, and destroying the value in A is repeated until the entire array

has been copied, in ascending order, into array B.

What is the time complexity of copy sort? Justify your answer.

[5 marks]

(c) Let Q be a non-empty queue and let S be an empty stack. Using only the stack and

queue abstract data type functions and a single Object variable X, write a pseducode/function

reverse(Queue Q, Stack S) to reverse the order of the elements.

[6 marks]

(d) Consider the following 2-3 tree, so every internal node has either two children (if it has

one key) or three children (if it has two keys). A leaf node can also contain 1 or two keys.

(i) Insert the following keys in the B- tree: 19, 29;

that is, insert key 19, then insert key 29 in the new B- tree. You must show all the

steps after each insertion.

[6 marks]

(ii) Delete the following key: 8;

that is, insert key 8 in the B-tree after insertion operations from (i)

[3 marks]

5 COMP2038-E1

COMP2038-E1 Turn over

4. Questions on Heap and Data Structures.

(a) Consider the heap structure.

(i) Is a heap containing n nodes guaranteed to have the minimum possible height? If

so, why? If not, justify your answer by drawing a max-heap that does not have

minimum height.

[4 marks]

(ii) What property of a heap makes it possible to easily store it in an array?

[4 marks]

(iii) Draw the resulting tree if the root of the max-heap shown above is deleted. You

must show the steps involved:

[4 marks]

continue on next page

6 COMP2038-E1

COMP2038-E1 END

(b) You are interviewing for a job with UNM Inc., a provider of Web-based information

services. They want to know what is the appropriate data structure would be for holding

pending requests for web pages while their web server takes a break, so that when the web

server comes back it can process requests in the order in which they arrived.

Describe:

(i) what is the abstract data type UNM Inc should use for this problem.

[1 marks]

(ii) what are operations on the ADT they will need.

[2 marks]

(iii) what is the data structure they should use to implement the ADT. Justify your

answer.

[3 marks]

(iv) what is the cost of the operations will be (in O() terms) as a function of the

number of unprocessed requests using this particular implementation; and

[3 marks]

(v) why do you choose this particular ADT and implementation.

[4 marks]

Provide short reasonable answers you can to the above five questions. You do not need to

write any code for this problem.