Practice exam Department of Computer Science ALGORITHMS AND DATA STRUCTURES
Time Restricted Exam: You have 150 minutes to complete the exam, which includes 30 minutes for uploading files.
Please ensure you have read and understood the examination instructions below before you start this practice exam:
Examination Instructions
Copyright By PowCoder代写 加微信 powcoder
Read before starting:
1. Once you start the exam, you must complete it within the allocated time. You cannot return to the same attempt once the allocated time runs out. It is not possible to pause the timer and return to your unsubmitted attempt at a later date.
2. You must answer all questions.
3. This is an open book examination, which means that you may access academic
resources.
4. You are responsible for time-keeping during your exam attempt: we recommend that
you use a third-party time-keeping device to manage your time.
5. We recommend using a computer and a reliable internet connection.
6. In the event of connection failure which adversely affects your ability to take the exam,
we would recommend capturing evidence.
7. If you experience any technical difficulties when taking the exam, we advise you to
contact Canvas support on or +44 80 0060 8442 (available 24hrs).
Guidance for taking the practice exam:
1. Unlike the summative exam, you may attempt the practice exam as many times as you want.
2. You can attempt the practice exam at any time.
3. The examination instructions (attached above) are the same as those that you will be
given for the summative exam, plus any ‘sit as if for the first time’ or reassessment
exams that you are eligible to sit on this module. Please ensure you have read and understood these instructions in advance of starting the Algorithms and Data Structures summative exam.
4. The practice exam has a maximum of 32 marks. The summative exam will have a maximum of 100 marks, so there will be more questions in the final exam (based on the format of questions found in the practice exam).
5. You will be provided with the sample answers as a separate document, and you should use this to check your own answers. Please ignore any ‘incorrect’ messages in Canvas.
6. The marks for the practice exam do not count towards your final marks for this module.
7. Please note that late submissions, exceptional circumstances and release of marks DO
NOT apply to the practice exam.
Data Structure Concepts (4%)
{MCQ statement combinations}
1. [2 marks each] For the following graphs
(Fig. 1) (Fig. 2)
Circle all strongly connected graphs:
{Numeric response question}
2. [2 marks] Given the following red-black tree,
What is the black height of node 4?
Algorithms Understanding (10%)
Note: The operations referred to are the ones taught in the module. {Single answer response (non-numeric)}
1. [5 marks] The key operation in quick-sort is partition algorithm. Consider the following array A, give the output after partition using the element with key 6 as the pivot. Fill in your answers in the blank array below.
PARTITION(A, 1, 7) A 1 5 6 9 11 7 8
8 7 1 9 11 5 6
2. [5 marks] Using the binary search tree T below:
Draw the binary search tree after RIGHT-ROTATE (T, x), where x is the element with key 10.
Your answer:
Time Complexities (5%)
Note: the big O and Ω notations refer to the tight bound throughout the exam paper. {Multiple answer response (non-numeric)}
1 [5 marks] Perform worst case analysis on the following algorithm. Assuming each line of code takes ci time.
1 forr=1ton
2 for c=1 to n
3 sum = sum+1
4 returnsum
T(n)= c1(n+1)+c2(n2+n)+c3*n2 + c4=an2+bn+c
cost times c1 n+1
c2 n* (n+1) c3 n2
{Paragraph entry}
print x.key PREORDER-TREE-WALK (x.left) PREORDER-TREE-WALK (x.right)
Section D Psedocode Construction (10%)
Note: In order to receive credit, you must follow the pseudo-code conventions.
1. [10 marks] A recursive version of a preorder tree walk algorithm and basic stack
operations are provided below
PREORDER-TREE-WALK (x) 1 ifx≠NIL
Basic stack operations:
STACK-EMPTY(S): indicates whether the stack S is empty PUSH (S, x) : inserts an element x into the stack S POP(S): removes and returns the last inserted element
You are required to complete the nonrecursive version of preorder tree walk algorithm below. The algorithm uses stack as an auxiliary data structure.
PREORDER-TREE-WALK-WITH-STACK (x)
2 3 4 5 6 7 8
create a new stack S
► You code begins here if x≠NIL
PUSH (S, x)
while STACK-EMPTY(S)==false
x= POP(S) print x.key
if x.right ≠NIL
PUSH (S, x.right) if x.left ≠ NIL
PUSH (S, x.left)
all agree, not cold
someone disagree
Java Programming (3%) Circle the correct answers
1. What is the correct terminal output after the execution of the following method?
public void vote() {
String s1=new String (“Iceland is not cold”); String s2=new String (“Iceland is not cold”); String s3=new String (“Iceland is not cold”); if ((s1==s2)&&(s2==s3)){
System.out.println(“all agree, not cold”);} else System.out.println(“someone disagree”);
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com