# 数据结构代写 | Midterm Practice

Question 1

Given an array of n elements containing all but one of the integers from 1 to n + 1.

1. Give the best algorithm you can for determining which number is missing if the array is
sorted, and analyze its asymptotic worst-case running time.

2. Give the best algorithm you can for determining which number is missing if the array is
not sorted, and analyze its asymptotic worst-case running time.

Question 2

The column on the left is an array of strings to be sorted or shuffled. The column on the right is
in sorted order. The other columns are the contents of the array at some intermediate step
during one of the algorithms below. Write the number of each algorithm under the
corresponding column. Use each number exactly once. This seems hard, its not, take your time
and be systematic…oh, I a gave you a sort we have not covered you say? You could look it up but
in a test, what would you do? Be confident and use process of elimination. (0) Original input
(1) Knuth shuffle
(2) Selection sort
(3) Insertion sort
(4) Mergesort
(5) Heapsort
(6) Quicksort
(7) Sorted

Question 3

You have been hired by UWEC DeepBlu to implement a priority-queue-like data structure
supporting the following operations:

• insert() an item in O(logN) time.
• fortyTwo() which returns the 42nd smallest item in constant time.
• delFortyTwo() which deletes the 42nd smallest item in O(logN) time.

Explain how you would implement the required functionality, using one or more data structures.
Write pseudocode for each of the three operations listed above. You may assume that N > 42,
and omit all checks for smaller N. For full credit, your implementation should support finding
the kth smallest item with an order-of-growth running time independent of k. That is, it should
be possible to change 42 to some other constant (at compile time) without changing the
order-of-growth running time. E-mail: itcsdx@outlook.com  微信:itcsdx 