# Python代写 | DSA1002 Data Structures and Algorithms Final Assessment

Question 1 (Total 10 marks): General
a) Consider a situation where you must store a collection of movies to be stored for a
movie theatre program. The movies should be kept in order of when they are played
in the cinema. Films are also accessed regularly to check what movie is playing at a
particular time.

a. (3 marks) What ADT would you use to store this data? Justify your choice.

b. (3 marks) How does your choice handle retrieving a movie based on the
time? Explain this with reference to Big O time complexity.

b) A university wants to set up a student peer tutoring system. The system needs to
keep track of which students are tutoring other students. There are plans for this
system to operate globally with students helping each other learn internationally so it
needs to be able to support a large number of students. Any student can tutor any
other student and some students are both tutors and learners. The students can also
rate each other’s tutoring ability. The university also wants to do research into the
structure of these student tutoring networks.
a. (4 marks) What ADT would you use to store this data? Justify your choice.

Question 2 (Total 20 marks): Sorting and Recursion

a) (3 marks). If you had to use a sorting algorithm in a low memory environment, what
would be the most important factor to consider? Would a mergesort be an
appropriate choice? Justify your answer.

b) (5 marks). Do you agree with the statement: “The best pivot to select for a
quicksort is the median of all the values.”? Justify your answer with reference to Big
O time complexity.

c) (3 marks). What kind of problems could occur when recursively sorting very large
datasets? Can this be mitigated, or should a different algorithm be used?

d) (5 marks). Rewrite the following recursive algorithm as an iterative one.

Python Java

def searchRobots(robots):
recurseSearchRobots(robots, len(robots)-1)

def recurseSearchRobots (robots, i):
if robots[i] == ‘RADBOT-6102’:
print(‘Found the robot!’)
else:
print(‘Not the right robot’)
if(i>0):
recurseSearchRobots(robots, i-1)
public static void searchRobots (String[] robots)
{
recurseSearchRobots (robots, robots.length-1);
}

public static void recurseSearchRobots (String[] robots, int i)
{
if(robots[i] == “RADBOT-6102”)
System.out.println(“Found the robot!”);
else
System.out.println(“Not the right robot”);
if(i>0)
recurseSearchRobots (robots, i-1);
} E-mail: itcsdx@outlook.com  微信:itcsdx 