代做CSE310留学生、data structure代写、代写Java、Python，c++程序语言

日期：2020-04-12 10:24

Spring 2020 CSE310 Midterm 2

Instructions:

? This is a take home examination. While you can check the textbook/lectures and

other resources while working on the examination, it should be your own work.

The instructor may ask any of the students to have a one-on-one recorded zoom video

session (up to 30 minutes) to ask questions either on the exam paper or closely related

to the questions on the exam paper. Depending on the zoom session, the student’s

score on this exam may be adjusted. Refusing the zoom session will result in the

student’s score on this exam invalid. The zoom session is a way to validate that

the student knows the answers submitted.

? There are six problems in this exam. You have to typeset your answers and submit

a PDF file on canvas before 11:59pm on 04/11/2020. You should name your file using

the format CSE310-MD02-LastName-FirstName, where LastName is your last name

and FirstName is your first name.

? Hand-written answers (or photo of hand-written answers) are not accepted.

Problem 1. (21 points: 3+3+3+3+3+3+3)

A max-heap with 11 elements is given in the following array format. The first three subquestions

all refer to this max-heap (not the heap you obtained after doing some operations).

i 1 2 3 4 5 6 7 8 9 10 11

A[i] 11 10 6 7 9 2 5 1 4 3 8

(a) Show the result after applying Heap-Increase-Key(A, 9, 12) to the max-heap at

the top of this page (in array format):

i 1 2 3 4 5 6 7 8 9 10 11

A[i]

(b) Show the result after applying Heap-Extract-Max(A) to the max-heap at the top of

this page (in array format):

i 1 2 3 4 5 6 7 8 9 10

A[i]

(c) At the end of the Heap-Extract-Max(A) operation in (b), will reading A[11] result in

a memory fault or not? Answer YES or NO.

(d) Given the sequence of numbers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. Show the max-heap obtained

by applying the linear time buildheap algorithm (in array format):

i 1 2 3 4 5 6 7 8 9 10 11

A[i]

(e) In (d), how many Max-Heapify operations will be called in total?

(f) What is the worst case time complexity of Heap-Extract-Max in a heap with n elements?

Use the most accurate asymptotic notation to write your answer.

(g) What is the maximum number of Max-Heapify calls when we perform Heap-Extract-Max

in a heap with n elements? Use the most accurate asymptotic notation to write your

answer.

1

Problem 2. (19 points: 3+3+4+3+3+3)

This problem is related to disjoint set operations. Assume that we are using union by rank

and find with path compression. Suppose that you are given a disjoint set structure

described by the following array representation.

i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|

A |-2 |-2 |-3 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 5 | 10| 11| 11| 15|

(a) Write the array representation of the disjoint set structure after applying union(12,

8) to the given disjoint set structure at the top of this page.

i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|

A | | | | | | | | | | | | | | | | |

(b) Write the array representation of the disjoint set structure after applying union(16,

12) to the given disjoint set structure at the top of this page.

i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|

A | | | | | | | | | | | | | | | | |

(c) Write the array representation of the disjoint set structure after applying union(8,

12) followed by union(16, 12) to the given disjoint set structure at the top of this

page.

i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|

A | | | | | | | | | | | | | | | | |

(d) Using the most accurate asymptotic notation, write down the worst-case time complexity

for link in a disjoint set with n elements.

(e) Using the most accurate asymptotic notation, write down the worst-case time complexity

for union in a disjoint set with n elements.

(f) Using the most accurate asymptotic notation, write down the worst-case time complexity

for find-set in a disjoint set with n elements.

2

Problem 3. (20 points: 16 + 1 + 3)

Figure 1 shows a directed graph G. Assume that the adjacency list lists the edges in

alphabetical order.

Figure 1: Graph for P3.

(a) Apply depth first search (DFS) to graph G, and show the discovery and finish times

of each vertex. In the main-loop of DFS, check the vertices in alphabetical

order. You can write the results on the graph in Figure 1.

(b) Draw the transpose graph GT of the graph in Figure 1. The vertices are given for your

convenience.

Figure 2: The transpose graph

(c) Apply DFS to GT

to compute the strongly connected components. You need to show

the strongly connected components and indicate the order they are computed.

3

Problem 4. (14 points: 7+7)

This problem is concerned with shortest paths in graphs.

(a) Figure 3 shows an edge-weighted undirected graph G. Assume that the adjacency

list lists the edges in alphabetical order. Compute the shortest A-v path for each

Figure 3: Graph for P4(a).

vertex v in the graph. Write the shortest A-v distance next to vertex v. Show the

predecessor field of vertex v by adding a direction on the edge connecting vertex v and

its predecessor, where the arrow points to the predecessor.

(b) Figure 4 shows an edge-weighted directed graph G. Assume that the adjacency

list lists the edges in alphabetical order. Compute the shortest A-v path for each

Figure 4: Graph for P4(b).

vertex v in the graph. Write the shortest A-v distance next to vertex v. Show the

predecessor field of vertex v by adding a direction on the edge connecting vertex v and

its predecessor, where the arrow points to the predecessor.

4

Problem 5. (17 points: 3+4+3+4+3)

Figure 5 illustrates a red-black tree, where a black square denotes a black node, a red circle

denotes a red node, and the nil nodes are omitted. Alternatively, you may use a square to

represent a black node, and use a circle to represent a red node.

Figure 5: A red-black tree.

(a) Treat the tree in Figure 5 as a binary search tree, draw the resulting binary search tree

(not necessarily a red-black tree) after inserting 28 into the tree in Figure 5. Which

property of red-black tree is violated after this insertion?

(b) Draw the red-black tree after inserting 28 into the red-black tree in Figure 5.

(c) Treat the tree in Figure 5 as a binary search tree, draw the resulting binary search tree

(not necessarily a red-black tree) after deleting 40 from the tree in Figure 5. Which

property of red-black tree is violated after this insertion?

(d) Draw the red-black tree after deleting 40 from the red-black tree in Figure 5.

(e) Use the most accurate asymptotic notation to denote the worst-case time complexity

of rotation in a red-black tree with n internal nodes.

5

Problem 6. (9 points: 3+3+3)

This problem is concerned with your understanding of various data structures studied in

class.

(a) Suppose that you are asked to choose a data structure to accomplish a given task that

involves insertion and delete-min, and your choice are limited to (1) binary min heap,

(2) binary search tree, and (3) red-black tree. Assume that worst-case time complexity

is the main metric for selection, and ease of implementation is the secondary metric

for selection. Which data structure is the best choice? Why?

(b) Suppose that you are asked to choose a data structure to accomplish a given task that

involves insertion and deletion, and your choice are limited to (1) binary min heap, (2)

binary search tree, and (3) red-black tree. Assume that worst-case time complexity is

the main metric for selection, and ease of implementation is the secondary metric for

selection. Which data structure is the best choice? Why?

(c) Suppose that you are asked to choose a data structure to accomplish a given task

that involves insertion, deletion, and search, and your choice are limited to (1) binary

min heap, (2) binary search tree, and (3) red-black tree. Assume that worst-case time

complexity is the main metric for selection, and ease of implementation is the secondary

metric for selection. Which data structure is the best choice? Why?

6