2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 1/18
Mid-semester test: COMP20003
Started: Sep 16 at 15:15
Quiz Instructions
The University of Melbourne
School of Computing and Information Systems
Mid-Semester Test, Semester 2, 2022
COMP20003 Algorithms and Data Structures
Duration: 30 minutes
Instructions to Students:
The test includes 13 questions worth a total of 15 marks, making up 10% of the total assessment for the subject.
This exam may include a combination of multiple-choice questions, and short-answer questions. Please answer all questions in the fields
provided.
This is a timed quiz. The time remaining is shown in the quiz window and will continue to count down even if you leave the Canvas site.
It is recommended that you do not close your browser while working on this quiz.
At the end of the time limit, your answers will be submitted automatically.
Authorised Materials: This exam is open-book. While undertaking this assessment you are permitted to:
make use of textbooks and lecture slides (including electronic versions) and lecture recordings
make use of your own personal notes and material provided as part of tutorials and practicals in this subject
make use of code that has been provided as part of this subject, or that you have written yourself
use calculators, code, or mathematical software to compute numeric answers
While you are undertaking this assessment you must not:

2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 2/18
make use of any messaging or communications technology
make use of any world-wide web or internet-based resources such as Wikipedia, Stack Overflow, or Google and other search services
act in any manner that could be regarded as providing assistance to another student who is undertaking this assessment, or will in the future be
undertaking this assessment.
The work you submit must be based on your own knowledge and skills, without assistance from any other person.
Technical support
This exam is a Canvas Quiz. Technical support for this exam can be accessed at: https://students.unimelb.edu.au/your-course/manage-your-
course/exams-assessments-and-results/exams/technical-support (https://students.unimelb.edu.au/your-course/manage-your-course/exams-
assessments-and-results/exams/technical-support)
Additional information about Canvas Quizzes, including troubleshooting tips, can be found here (https://students.unimelb.edu.au/your-
course/manage-your-course/exams-assessments-and-results/exams/exam-types) (scroll down to the Canvas Quiz section).
If you have questions about the exam content, please post in the LMS Discussion board
($CANVAS_OBJECT_REFERENCE$/discussion_topics/g55bdfb8d2de0918fb0b2db1a0f25a128) .
1 ptsQuestion 1
c = 17, N = 1
c = 1, N = 53
c = 3, N = 3
Consider a function:
f(n) = 3n + 4n + 2n + 8
What values of c and N could be used to prove that f(n) is in O(n )?
3 2
0
3
0
0
0
A
o
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 3/18
c = 3, N = 10
1 ptsQuestion 2
2
(n+1)(n+1)
2n
n + 2
Which of the following are in Θ(n )?2
n
2
1 ptsQuestion 3
arrays
linked lists
neither
Is the following statement true of arrays, linked lists, both, or neither?
The worst case time complexity to access one item is Θ(n).
co
A
X
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 4/18
both
1 ptsQuestion 4
neither
both
arrays
linked lists
Is the following statement true of arrays, linked lists, both, or neither?
Items are stored in contiguous locations in memory.
1 ptsQuestion 5
Suppose you use a post-order traversal to free the nodes in this binary search tree. In what order will the nodes be freed?
c.cn
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 5/18
D H L Q P T Z N
D L H Q P Z T N
D H L P Q Z T N
D L Q P Z H T N
1 ptsQuestion 6
Consider the following binary search tree:
DH t Paz TN
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 6/18
Which of the following trees is produced after the deletion of node 12?
曲
X
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 7/18
1 ptsQuestion 7
Consider the following AVL tree:
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 8/18
What would be the result after doing any rotations required to balance this tree?
C ⽤ 四
忍
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 9/18
1 ptsQuestion 8
Consider the following array:
A = [7,1,8,5,4,3,2,9,0,6];
What are the first three swaps performed during static insertion sort, when applied to the above array?
x
NC 145432906
o
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 10/18
Swap 1 and 7, swap 5 and 8, swap 4 and 8
Swap 1 and 7, swap 7 and 8, swap 5 and 7
Swap 1 and 7, swap 5 and 8, swap 5 and 7
Swap 0 and 7, swap 2 and 8, swap 3 and 5
1 ptsQuestion 9
Insertion sort is an in-place sorting algorithm
Insertion sort has a (tightest bound) average-case time complexity of O(n )
Selection sort is a stable sorting algorithm
Selection sort has a (tightest bound) best-case time complexity of O(n)
Which of the following statements are true about sorting algorithms? (Select all that are true)
2
1 ptsQuestion 10
Suppose you wish to sort the array A below using distribution counting. What are the state of the count and cumulative count
arrays after copying the first 2 items to the auxillary array?
y
AB
ˇ
ˇ
Y.ec
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 11/18
count = [1,4,4,2,1];
cumulativeCount = [0,2,5,7,9];
count = [1,4,4,2,1];
cumulativeCount = [0,1,4,7,9];
count = [1,3,3,2,1];
cumulativeCount = [0,1,4,7,9];
count = [1,3,3,2,1];
cumulativeCount = [0,2,5,7,9];
A = [1,2,0,4,2,2,1,3,3,1];
aux_array = [ ,1, , ,2, , , , , ];
1 ptsQuestion 11
Given the following sequence of numbers
14, 6, 13, 8, 11, 10, 2
We want to insert each item starting from left to right into a hash table of size 7, where the first position of the table is indexed by
0, and the last by 6.
If we use the following hashkey(n) = n%7
X
i
X
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 12/18
and use linear probing, we should find the hash table places the values in this order:
, , , , , ,
Please enter the number for each position.
2 ptsQuestion 12
64
8 10 2 11 13
年
fzut 47
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 13/18
Your task is to match the lines to the correct positions
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 14/18
D
⾼
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 15/18
sum_divisors += i; [ Choose ]
sum_non_divisors += i; [ Choose ]
perfect_num % i == 0 [ Choose ]
perfect_num % i != 0 [ Choose ]
printf("Number %d is not a perfect number, the sum of it's
divisors is %d\n",perfect_num, sum_divisors);
[ Choose ]
printf("Number %d is a perfect number!\n",perfect_num); [ Choose ]
2 ptsQuestion 13
哥
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 16/18
Your task is to match the lines to the correct positions
how的 to7讹了
⼗四了㓚
⼗ I
2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 17/18
row[i] += magic[i][j]; [ Choose ]
col[j] += magic[i][j];

2022/9/16 15:15 Quiz: Mid-semester test: COMP20003
https://canvas.lms.unimelb.edu.au/courses/125386/quizzes/172927/take 18/18
Not saved
[ Choose ]
if(i==j) diagLR += magic[i][j]; [ Choose ]
printf(" %d ", magic[i][j]); [ Choose ]
diagRL += magic[i][j - (i+1)]; [ Choose ]
printf("\n"); [ Choose ]
Submit Quiz