19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 2 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
Special Consideration
By completing the acknowledgement and starting this exam you have acknowledged that you are fit to sit the exam and
cannot apply for Special Consideration for issues that existed prior to the exam.
If a circumstance arises during the exam that prevents you from completing the exam, please email [email protected]
immediately and apply for special consideration within 3 days of the exam, preferably as soon as possible.
Before your final exam, you should read the section "Important Information for Online Assessments" on the Special Consideration
webpage. It contains information on what you should do if you experience a technical issue that is beyond your control and
impacts your ability to complete an assessment - in particular, how and what to document for a special consideration application.
Submission
All submissions must be done via give.
See the submission instructions under each question.
You can submit multiple times. Only your last submission will be marked.
Do not wait until just before the deadline to submit all your answers. Submit each question as soon as you finish working
on it or submit incrementally throughout the exam.
There will be a 5 minute buffer after the deadline (5pm) to allow students to resolve last-minute submission issues. Do not use
this buffer as an excuse to continue working on the exam until 5:05pm. You must attempt all submissions before 5pm.
Submissions will be disabled after 5:05pm (except for ELS students), and requests for leniency with respect to this
deadline will be ignored. You have been warned.
To check your submission status for a particular question, use the command 2521 classrun check question, where
question is the name of a particular submission. For example:
$ 2521 classrun check exam_q1
Programming Questions
General Constraints and Assumptions
All inputs will be valid.
No error checking is necessary.
You may define your own helper functions in the files to be submitted.
You may not #include any additional libraries.
You may use any functions provided by the #included libraries.
You may add your own #defines and define your own structs/enums.
You must not use global variables or static variables. Solutions that do so will receive zero marks.
You must not start any new programs or communicate with external programs.
Marking
You should ensure that your code works on CSE machines.
Solutions which do not attempt to solve the question generally but instead only hardcode return values for specific tests will
receive zero marks.
Code style is not marked (except that global variables and static variables are strictly forbidden). However, good style may help a
marker understand your code better, which will give you a greater chance of being awarded partial marks if your code does not
work.
Memory leaks/errors will not be penalised. However, we advise that you ensure there are no memory errors in your code, as
programs containing memory errors are not guaranteed to behave correctly or consistently. A program that works when you test it
during the exam but contains memory errors may not work during autotesting. There will be no chances to fix memory errors after
the exam.
Admin
Marks Contributes 50% towards your final mark
Submit See the submission instructions for each question
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 3 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
Submit See the submission instructions for each question
Date and time 2pm to 5pm Thursday 5 May 2022 (Sydney time)
Total Marks 100
Total number of questions 11 (not worth equal marks)
Note: the actual final exam may have a different number of questions
Structure
This exam consists of two parts:
Written short/extended answers (50 marks)
Programming questions (50 marks)
Setting Up
Change into the directory you created for the sample exam and run the following command:
$ unzip /web/cs2521/22T1/exams/sample/downloads/files.zip
If you're working at home, download files.zip by clicking on the above link and then unzip the downloaded file.
Question 1 (5 marks)
An algorithm solves a problem of size recursively by breaking it down into two subproblems of size with the same structure,
until the size of a subproblem is one or zero. It takes time to solve a (sub)problem of size one or zero. It takes time to
convert a problem of size into two subproblems and it takes time to combine the results of these subproblems into the result
of the problem of size . What is the time complexity of this algorithm? Justify your answer.
Write your answer in q1.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q1 q1.txt
NOTE:
Since this is the sample exam, these submission commands will not actually work.
Question 2 (5 marks)
Please note that the topics covered in the final exam may be different to the topics covered in this sample exam. Also, the mark
distribution across topics may vary.
n n/2
O(1) O(n)
n O(n)
n
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 4 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
Consider the following algorithm, which converts a positive integer to its binary representation.
BinaryConversion:
Input positive integer n
Output binary representation of n on a stack

create empty stack S
while n > 0 do
push (n mod 2) onto S
n = floor(n / 2)
end while
return S
What is the time complexity of the algorithm? Assume that creating a stack and pushing an element onto a stack are both
operations (i.e., constant). Justify your answer.
Write your answer in q2.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q2 q2.txt
Question 3 (5 marks)
Consider the the following 2-3-4 tree :
(a) (2 marks) What value(s) would be stored in the root node of the above 2-3-4 tree after the insertion of the value 8? What
value(s) would be stored in the node that now contains 8? Note: if you need to promote a value, you must promote the smaller of the
two middle values. Justify your answer.
(b) (3 marks) What value(s) would be stored in the root node of the above 2-3-4 tree after the insertion of the value 50? What
value(s) would be stored in the node that now contains 50? Note: if you need to promote a value, you must promote the smaller of
the two middle values. Justify your answer.
Write your answers in q3.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q3 q3.txt
Question 4 (7 marks)
Consider the following trie. Finishing nodes are shown in red.
n
O(1)
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 5 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
(a) (1 mark) How many words are stored in this trie?
(b) (2 marks) Which nodes would be visited in searching for "deeds"?
(c) (2 marks) What new nodes would be created if the word "bogus" was added to the trie? Justify your answer.
(d) (2 marks) What new nodes would be created if the word "do" was added to the trie? Justify your answer.
Write your answers in q4.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q4 q4.txt
Question 5 (6 marks)
(a) (2 marks) What is the difference between an Euler path and a Hamilton path?
(b) (2 marks) Does the graph below have any Euler paths? If so, give one of them. If not, explain why.
(c) (2 marks) Does the graph below have any Hamilton paths? If so, give one of them. If not, explain why.
Write your answers in q5.txt.
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 6 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
Submission
Submit via the give command
$ give cs2521 sample_exam_q5 q5.txt
Question 6 (6 marks)
This question is about the array-based implementation of a max heap.
(a) (3 marks) Suppose the original state of the heap is:
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
--- Q N H D K E --- --- ---
Show the state of the heap after performing each of the following operations:
join(pq, S)
join(pq, P)
Note that the "join(pq, P)" operation should be performed on the state of the heap obtained after performing the "join(pq, S)"
operation.
(b) (3 marks) Suppose the original state of the heap is:
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
--- Q N H D K E --- --- ---
Show the state of the heap after performing each of the following operations. What are the values of it1 and it2?
it1 = leave(pq)
it2 = leave(pq)
Note that the "it2 = leave(pq)" operation should be performed on the state of the heap obtained after performing the "it1 =
leave(pq)" operation.
Write your answers in q6.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q6 q6.txt
Question 7 (8 marks)
Consider a hash table of integer keys with 11 slots and a primary hash function of .
Consider the following sequence of values:
10, 12, 28, 35, 25, 32, 20, 17, 24, 39
(a) (4 marks) Suppose the hash table described above uses linear probing for collision resolution. Show the final contents of the
hash table after the values above have been inserted into an initially empty table in the order given. Give the cost, in terms of the
number of keys examined, when searching for the key value 6 in the resulting table.
(b) (4 marks) Suppose the hash table described above uses double hashing for collision resolution, with a secondary hash function
of . Show the final contents of the hash table after the values above have been inserted into an initially empty
table in the order given. Give the cost, in terms of the number of keys examined, when searching for the key value 6 in the resulting
table.
h(k) = k % 11
h2(k) = 1 + (k % 5)
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 7 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
Write your answers in q7.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q7 q7.txt
Question 8 (8 marks)
Suppose you are given four sort programs each implementing one of the following sorting algorithms, but you are not told which one
is which:
bubble sort
insertion sort
merge sort
naive quicksort
Describe in detail the steps you would perform to tell the sort programs apart. Note: It is not known whether the bubble sort scans
from left to right or from right to left.
Write your answer in q8.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q8 q8.txt
Question 9 (10 marks)
Implement the function totalTextSize in q9/totalTextSize.c, which takes a pretend file system (represented by a system
of linked lists) and returns the total size of all the text files in the pretend file system. The size of a text file is simply the length of the
text in the file.
The pretend file system contains two types of files: directories (also known as folders) and text files. (Yes - directories are a type of
file.)
The data structures used to implement the pretend file system are defined in Fs.h. Each file is represented by an instance of
struct File, where the type field is used to distinguish between file types (directory or text file).
Each directory has a linked list of files that are contained within that directory. Each text file contains some text, represented by a
string. The file system as a whole is represented by an instance of struct Fs, which contains a pointer to the root/top-level
directory.
Constraints
All general constraints and assumptions at the top of this exam paper apply
You must not open any files - you are given a pretend file system represented by linked lists, not a real file system.
The given pretend file system must not be modified
You must not use arrays or any variant of malloc (malloc, calloc or realloc). If you do, you will receive zero for this
question.
Files
Makefile A Makefile to compile your code
Fs.c Contains the implementation of some in-memory file system functions
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 8 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
Fs.h Contains the definition of the in-memory file system data structure and function prototypes
testFs.c A testing program. This program takes a test number as a command-line argument, sets up the file system
corresponding to that test number, calls totalTextSize, and outputs the result to stdout.
totalTextSize.c Contains totalTextSize, the function you must implement. This is the only file you should modify (except
when adding your own tests in testFs.c).
tests/ A directory containing the expected outputs for some basic tests
Example
$ ./testFs 1
File system:
/
a
b.txt
c.txt
d
e.txt
Total text size: 49
Testing
You can compile and test your function using the following commands:
$ make # compiles the program
$ ./testFs 1 # runs test 1, outputs to terminal (now compare with tests/output1.txt)
$ ./testFs 2 # runs test 2, outputs to terminal (now compare with tests/output2.txt)
It is possible to devise your own tests by modifying testFs.c. See the existing test functions for a demonstration of how to
construct a file system.
Submission
Submit via the give command
$ give cs2521 sample_exam_q9 totalTextSize.c
Question 10 (20 marks)
A contiguous subsequence of a list is a sequence made up of consecutive elements of . For example, the contiguous
subsequences of the list [5, 3, 8] are:
[5, 3, 8]
[5, 3]
[3, 8]
[5]
[3]
[8]
[]
For this question, we introduce the notion of a tolerance, which indicates the number of mismatches allowed while looking for a
contiguous subsequence.
Your task is to implement the following function in the file q10/numSubsequences.c:
int numSubsequences(List listA, List listB, int tolerance);
The function takes two lists, listA and listB, and a tolerance, and returns the number of times listB appears as a contiguous
L L
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 9 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
subsequence of listA with the given tolerance.
Important: You must clearly state the worst case time complexity (in big O notation as discussed in the lectures) of your solution in a
comment just above the function. The time complexity should be in terms of and , where is the length of list and is the
length of list .
Example
Consider the two lists below:
List :
50 25 25 12 67 50 9 25 67 98 34 9 25 67 25 9
List :
50 9 25 67
If the tolerance is zero (no mismatch is allowed), list only appears once in as shown below:
50 25 25 12 67 50 9 25 67 98 34 9 25 67 25 9
If the tolerance is one (one mismatch is allowed), list appears twice in : from index 5 to 8, and from index 10 to 13 (index 10 is a
mismatch):
50 25 25 12 67 50 9 25 67 98 34 9 25 67 25 9
If the tolerance is two (two mismatches are allowed), list appears three times in : from index 0 to 3 (with mismatches at indices 1
and 3), from index 5 to 8 and from index 10 to 13 (with a mismatch at index 10):
50 25 25 12 67 50 9 25 67 98 34 9 25 67 25 9
Please note that it is possible for the subsequences that appear to overlap. For example, suppose we have the following lists:
List :
5 5 5 5 6 6
List :
5 5 5
If the tolerance is zero, list appears twice in list :
5 5 5 5 6 6
5 5 5 5 6 6
If the tolerance is one, list appears three times in list :
5 5 5 5 6 6
5 5 5 5 6 6
5 5 5 5 6 6
If the tolerance is two, list appears four times in list :
5 5 5 5 6 6
5 5 5 5 6 6
5 5 5 5 6 6
5 5 5 5 6 6
Constraints and Assumptions
All general constraints and assumptions at the top of this exam paper apply
will be non-empty
The tolerance will be between and (inclusive)
The given lists must not be modified
You must not use arrays or any variant of malloc (malloc, calloc or realloc). If you do, you will receive zero for this
question.
n m n A m
B
A
B
B A
B A
B A
A
B
B A
B A
B A
B
0 length(B)− 1
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 10 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
Files
Makefile A Makefile to compile your code
list.c Contains the implementation of basic linked list functions
list.h Contains the definition of the linked list data structure and function prototypes
testNumSubsequences.c
A testing program. The program reads list data and the tolerance from stdin, calls
numSubsequences, and outputs the result to stdout.
numSubsequences.c
Contains numSubsequences, the function you must implement. This is the only file you should
modify.
tests/ A directory containing the inputs and expected outputs for some basic test cases
Examples
$ ./testNumSubsequences
5 5 5 5 6 6
List A: 5, 5, 5, 5, 6, 6
5 5 5
List B: 5, 5, 5
2
Tolerance: 2
numSubsequences returned: 4
$ ./testNumSubsequences
50 25 25 12 67 50 9 25 67 98 34 9 25 67 25 9
List A: 50, 25, 25, 12, 67, 50, 9, 25, 67, 98, 34, 9, 25, 67, 25, 9
50 9 25 67
List B: 50, 9, 25, 67
1
Tolerance: 1
numSubsequences returned: 2
$ ./testNumSubsequences
List A:
1 2 3
List B: 1, 2, 3
0
Tolerance: 0
numSubsequences returned: 0
In the last example, an empty list was created by pressing enter without typing any numbers.
Testing
You can compile and test your function using the following commands:
$ make # compiles the program
$ ./testNumSubsequences # tests with manual input, outputs to terminal
$ ./testNumSubsequences < input-file # tests with input from a file, outputs to terminal
$ ./testNumSubsequences < tests/input1.txt # for example, tests with input from tests/input1.txt
# (then compare with tests/output1.txt)
It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note that you will
need to check the output yourself.
Submission
Submit via the give command
$ give cs2521 sample_exam_q10 numSubsequences.c
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 11 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
Question 11 (20 marks)
Implement the following function in the file q11/findPopularFollowers.c:
void findPopularFollowers(Graph g, int src, int followers[]);
findPopularFollowers takes three arguments: a directed graph g, a source node src, and an array followers.
Given a graph g, the function should find all popular followers of a given node (src) and for each popular follower i, sets
followers[i] to 1. For example, followers[2] should contain 1 if node 2 is a popular follower of the given source (src).
Initially, all values in the followers array are set to -1. followers[i] should remain as -1 if i is not a popular follower of src.
We say a node A is a popular follower of node B if the following two conditions are true.
There is a directed path from node A to node B, OR A = B (node itself).
For node A, inA > outA, where inA represents incoming links of node A and outA represents outgoing links of node A.
Important: You must clearly state the worst case time complexity (in big O notation as discussed in the lectures) of your solution in a
comment just above the function. The time complexity should be in terms of , the number of vertices in the graph.
Important: You must implement your solution efficiently; we will consider how efficiently you have implemented your solution when
we award you marks. Inefficient solutions will be penalised.
In the following example graph, for the source node 2, there are two popular followers: nodes 2 and 3. Both these nodes satisfy the
requirements mentioned above. Just to clarify, there is a directed path from node 0 to node 2 (src), however for node 0, in-degree is
not greater than out-degree, so node 0 is not considered as a popular follower of node 2.
Examples
n
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 12 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
$ ./testFindPopularFollowers < tests/input3.txt
nV: 7
src: 2
Edge inserted: 1 -> 6
Edge inserted: 0 -> 5
Edge inserted: 3 -> 1
Edge inserted: 1 -> 4
Edge inserted: 4 -> 3
Edge inserted: 0 -> 3
Edge inserted: 0 -> 1
Edge inserted: 1 -> 0
Edge inserted: 5 -> 6
Edge inserted: 1 -> 2
Popular followers of node 2:
node 2
node 3
$ ./testFindPopularFollowers < tests/input2.txt
nV: 8
src: 7
Edge inserted: 1 -> 3
Edge inserted: 0 -> 3
Edge inserted: 2 -> 3
Edge inserted: 4 -> 3
Edge inserted: 3 -> 0
Edge inserted: 0 -> 5
Edge inserted: 1 -> 5
Edge inserted: 4 -> 5
Edge inserted: 5 -> 2
Edge inserted: 5 -> 7
Edge inserted: 1 -> 4
Edge inserted: 2 -> 4
Edge inserted: 0 -> 6
Edge inserted: 3 -> 7
Popular followers of node 7:
node 3
node 5
node 7
Note that the first example corresponds to the diagram above.
Constraints and Assumptions
All general constraints and assumptions at the top of this exam paper apply
The size of the followers array is equal to the number of vertices in the graph.
All values in the followers array are initially -1.
Files
Makefile A Makefile to compile your code
Graph.c
Contains the implementation of the Directed Graph ADT (using the adjacency matrix
representation)
Graph.h Contains the definition of the Directed Graph ADT and function prototypes
testFindPopularFollowers.c A testing program. The program reads graph data from stdin, calls findPopularFollowers,
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 13 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
and outputs the result to stdout.
findPopularFollowers.c
Contains findPopularFollowers, the function you must implement. This is the only file you
should modify.
tests/ A directory containing the inputs and expected outputs for some basic test cases
Testing
You can compile and test your function using the following commands:
$ make # compiles the program
$ ./testFindPopularFollowers # tests with manual input, outputs to terminal
$ ./testFindPopularFollowers < input-file # tests with input from a file, outputs to terminal
$ ./testFindPopularFollowers < tests/input1.txt # for example, tests with input from tests/input1.txt
# (then compare with tests/output1.txt)
It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note that you will
need to check the output yourself.
Submission
Submit via the give command
$ give cs2521 sample_exam_q11 findPopularFollowers.c
This is the end of the exam paper.
19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam
Page 14 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam
COMP2521 22T1: Data Structures and Algorithms is brought to you by
the School of Computer Science and Engineering
at the University of New South Wales, Sydney.
For all enquiries, please email the class account at [email protected]
CRICOS Provider 00098G

欢迎咨询51作业君