COMP2123 Data Structures and Algorithms - final exam

• 作业标题：Data Structures and Algorithms final exam
• 课程名称：The university of Sydney COMP2123 Data Structures and Algorithms
• 完成周期：1天

Problem 1

Suppose we have a binary search tree T containing n keys and some integer x. [5 marks]

1: def foo(T, x)
2: result ← 0
3: current ← T.root
4: while not current.isExternal() and current.key > x2 do
5: result ← result + current.key
6: current ← current.left_child
7: return result

Analyze the time complexity of running foo.

a)
We are given a set W of positive integer weights w1, …, wn and we have an [5 marks]
(infinite) set of identical boxes, each able to store a certain weight wmax. All
weights in W are at most wmax. We want to determine the minimum number of
boxes needed to store all n weights.

Example:

W = {3, 5, 3, 1, 2}

wmax = 7

In the example above, we need only two boxes, as we can store weights 3, 3, and 1 in one box and weights 5 and 2 together in a second box.

Construct a counterexample to show that the following algorithm doesn’t compute the minimum number of boxes: Sort the weights in non-increasing order.

For every weight wi, check if there exists a box that can still store wi. If there is,
add wi to the fullest box that can still take wi (i.e., the one with least weight left
out of all boxes having at least wi weight left). If no such box exists, open a new
box and put wi in that.

Problem 2

Consider the following undirected graph:

Assuming that ties are broken lexicographically, your task is to:

a) Compute the breadth first search tree T of the graph starting from A. List the [5 marks] edges in T.

b) Compute the depth first search tree T of the graph starting from H. List the [5 marks] edges in T. (You do not have to explain your answer.)

Problem 3.

Computer scientists have decided to play the Hunger Games, but were unhappy about the small number of players per district and the rules being too simple. So they came up with a new version of the game, and asked you to come up with an efficient data structure to handle the Games.

Rules: There are n districts, numbered 1 to n. Each district has its own number of players: initially, each district has m > 0 players. Each player has a score (non-negative integer), initially set to 1. Each district also has an integer score, initially set to 0.

• When two districts play against each other, their best players compete (one from
  each district). The winning player and their district both have their score incremented; the losing player and their district both have their score decremented.
• When a player reaches score 0, they are disqualified (removed from their district
  and the game).
• When a district reaches 0 players, it is disqualified (removed from the game).
• The last district in play wins.

Your task: Your data structure should use O(nm) space, and implement the following operations:

。。。