Sample Exam
Thu 19th August 2021
Solutions will be provided over the next week.
Changelog
All changes to the exam paper and files will be listed here.
Rules & Overview
By starting this exam you acknowledge that you are fit to sit the exam and cannot apply for Special Consideration
for issues that existed prior to the exam
If during the exam a circumstance arises that prevents you from completing the exam, please email
.edu.au immediately and apply for special consideration shortly after
During the exam no communication is allowed with other people, excluding any common sense exceptions (e.g.
answering “how are you?” if a parent asks you)
If you have any questions during the exam, make a private post on the Ed forum (the same one we’ve been using
all term)
Admin
Marks Contributes 40% towards your final mark
Submit See the submission instructions for each question
Date and time Thursday 19th August 9am-12pm
Total Marks 100
Total number of questions 9 (not worth equal marks)
Structure
This exam consists of a series of questions:
30 marks for written short/extended answers
70 marks for programming questions
Setting Up
Change into the directory you created for the sample exam and run the following command:
$ unzip /web/cs2521/21T2/sample-exam/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 (6 marks)
Consider the following function to multiply two N x N matrices:
void multiply(int a[N][N], int b[N][N], int c[N][N])
{
int i, j, k;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
c[i][j] = 0;
}
}
for (i = 0 i < N; i++) {
for (j = 0; j < N; j++) {
for (k = 0; k < N; k++) {
c[i][j] += a[i][k] * b[k][j];
}
}
}
}
Question 1a: How many multiplications are performed if N == 3? Type your answer in q1a.txt
Question 1b: How many multiplications are performed if N == 20? Type your answer in q1b.txt
Question 1c: What is the algorithmic complexity of this function (relative to N)?Type your answer in q1c.txt
Submission
Submit via the give command
$ give cs2521 sample_exam_q1 q1a.txt q1b.txt q1c.txt
Question 2 (7 marks)
Consider the following trie. Finishing nodes are shown in red.
https://cgi.cse.unsw.edu.au/~cs2521/21T2/sample-exam/downloads/files.zip
Question 2a: How many words are stored in this trie? Type your answer in q2a.txt
Question 2b: Which nodes would be visited in searching for "deeds"? (Exclude the root node; write the letters in
the order visited.) Type your answer in q2b.txt
Question 2c: How many new nodes would be added if the word "bogus" was added to the trie? (Do not count
nodes whose colour has changed; they are not new nodes.) Type your answer in q2c.txt
Question 2d: How many new nodes would be added if the word "do" was added to the trie? (Do not count nodes
whose colour has changed; they are not new nodes.) Type your answer in q2d.txt
Submission
Submit via the give command
$ give cs2521 sample_exam_q2 q2a.txt q2b.txt q2c.txt q2d.txt
Question 3 (4 marks)
Now consider the the following 2-3-4 tree:
Question 3a: What is the maximum number of values that could be stored in a 2-3-4 tree of this height? Type
your answer in q3a.txt
Question 3b: After the value 42 was inserted into this 2-3-4 tree, what values would be in the root node? Type
your answer in q3b.txt
Submission
Submit via the give command
$ give cs2521 sample_exam_q3 q3a.txt q3b.txt
Question 4 (7 marks)
Consider the following binary search tree with 7 nodes:
Question 4a: What is the height of the tree? (Height = number of edges on the longest path from the root to a
leaf) Type your answer in q4a.txt
Question 4b: What is the maximum height of a binary search tree with 7 nodes? Type your answer in q4b.txt
Question 4c: If 26 was inserted into the tree, using simple BST insertion, what node would it be a child of? Would
it be a left child or right child? Type your answer in q4c.txt
Question 4d: Give an insertion order for the values in the tree that could have produced this tree. Type your
answer in q4d.txt
Submission
Submit via the give command
$ give cs2521 sample_exam_q4 q4a.txt q4b.txt q4c.txt q4d.txt
Question 5 (6 marks)
Consider the following digraph in answering the questions below:
Question 5a: How many cliques does the graph have? Type your answer in q5a.txt
Question 5b: How many connected components does the graph have? Type your answer in q5b.txt
Question 5c: Which nodes are reachable from node C? Type your answer in q5c.txt
Question 5d: Which nodes are reachable from node G? Type your answer in q5d.txt
Question 5e: If an edge is added from C to H, how many components does the graph now have? Type your
answer in q5e.txt
Question 5f: If an edge is added from G to I, which nodes are now reachable from G? Type your answer in q5f.txt
Submission
Submit via the give command
$ give cs2521 sample_exam_q5 q5a.txt q5b.txt q5c.txt q5d.txt q5e.txt q5f.txt
Question 6 (20 marks)
Consider a small database of student records in a text file like:
5012345:Smith, John:3707:65.0
9912345:Parameswaran, Sri:3707:99.0
5054321:Wang, David:3778:85.0
5012346:Smith, Janet:3778:75.0
6543210:Smith, James:3978:55.0
Each line has the following information about one student: zID, name, program code, WAM.
We have provided you with a program in stu.c that reads such text files via its standard input, stores the data into an
array of Student records, and then displays the contents of this array.
If the above data was in a file called data1 and if we were to compile and use stu.c unmodified, it would produce the
following output:
$ make
gcc -Wall -Werror -g -c -o stu.o stu.c
gcc -o stu stu.o
$ ./stu < tests/data1
5012345 Smith, John 3707 65.0
9912345 Parameswaran, Sri 3707 99.0
5054321 Wang, David 3778 85.0
5012346 Smith, Janet 3778 75.0
6543210 Smith, James 3978 55.0
The students records are in the same order as they were in the original file. We want to be able to sort the records
two ways: by zID or by name.
Your task is to complete the sortStudents function which sorts the array of Student records in an order determined
by one of its parameters. The function is defined as:
void sortStudents(Student *stu, int n, Ordering order);
The first parameter is a pointer to the first element in an array of Student records. The second parameter tells how
many records are in the array. The third parameter determines which field is used for sorting and has two possible
values: BY_ZID and BY_NAME.
The zID values are unique, so there is no issue in sorting them. However, names are not unique. If there are several
students with the same name, they should appear as a group in the sorted array, ordered by zID.
You should not change any other part of stu.c except for the sortStudents() function, and any extra helper
functions that you want to add. If you change the input and output functions or the main() function, then you will
probably fail all of the tests.
The code for this question is in the q6 directory, which contains:
stu.c ... program for reading/sorting/displaying student records
Makefile ...for building the program
tests/ ... directory containing a sample input and output
You ought to look at the data structures, the main program and the reading and writing functions, to familiarise
yourself with the enviroment in which the sortStudents() function operates.
You can compile the program using the make command. This will give you an executable file called stu. Examples of
running the stu command are given below.
Now, complete the sortStudents() function. You can define as many helper functions as you want. It requires
around 15-30 lines of code to solve this problem, depending on how you solve it.
Submissions that don't compile are worth zero marks. Submissions that compile, but fail all tests are worth up to 10
marks. Submissions that compile and pass some tests are worth between 11 and 20 marks, depending on how close
they are to a working solution. Submissions that compile and pass all tests are worth 20 marks.
Examples of how the program ought to behave when working correctly:
$ ./stu < tests/data2
3333333 Smith, John 3645 75.0
5012345 Smith, John 3707 65.0
5012346 Smith, John 3778 75.0
6123456 Apple, Steve 3648 85.5
6543210 Smith, John 3978 55.0
$ ./stu name < tests/data2
6123456 Apple, Steve 3648 85.5
3333333 Smith, John 3645 75.0
5012345 Smith, John 3707 65.0
5012346 Smith, John 3778 75.0
6543210 Smith, John 3978 55.0
You should also be able to devise your own test cases.
Submission
Submit via the give command
$ give cs2521 sample_exam_q6 stu.c
Question 7 (15 marks)
Trees can be viewed as a special case of directed graphs. A directed graph (digraph) is a binary tree provided it
satisfies the following conditions:
only one node has no incoming edges
all other nodes have exactly one incoming edge
nodes may have 0, 1 or 2 outgoing edges
The following diagram shows two example directed graphs, only one of which is an binary tree:
Graphs are represented internally using a DiGraph data structure. Graphs are read from files which look like:
0 1 2 5
1 3 4
2 1
3 -
4 -
5 -
This is the readable representation of the graph on the left above. Each line contains a node number and then a list of
all the nodes that this node has outgoing edges to.
We have provided a program that reads in a representation of a graph, builds a DiGraph data structure (adjacency
matrix), displays the graph structure on standard output, and then calls a function to determine whether the graph is
a binary tree. Your task is to complete the graphIsBinTree() function, which takes a DiGraph, and returns true if
the graph satisfies the three conditions given above, and returns false otherwise.
The graphIsBinTree() function is defined as:
bool graphIsBinTree(DiGraph g)
Note that the DiGraph object is not passed to the function via a pointer. The whole structure is copied to the function
to be tested.
The code for this question is in the q7 directory, which contains:
gist.c ... program for testing graph-is-binary-tree
Makefile ... for building the program
tests/ ... directory containing a few sample inputs and outputs
You ought to look at the data structures, the main program and the reading and writing functions, to familiarise
yourself with the environment in which the graphIsBinTree() function operates.
You can compile the program using the make command. This will give you an executable file called gist. As supplied,
the graphIsBinTree() function always returns false, regardless of the DiGraph.
You should complete the graphIsBinTree() function. You can define as many auxiliary functions as you want. It
requires around 15-20 lines of code to solve this problem.
You should not change any other part of gist.c except for the graphIsBinTree() function, and any extra helper
functions that you want to add. If you change the input and output functions or the main() function, then you will
probably fail all of the tests.
Submissions that don't compile are worth zero marks. Submissions that compile, but fail all tests are worth up to 7
marks. Submissions that compile and pass some tests are worth between 8 and 14 marks, depending on how close
they are to a working solution. Submissions that compile and pass all tests are worth 15 marks.
Examples of how the program ought to behave when working correctly:
$ ./gist tests/01
V Connected to
-- ------------
0 1 2 5
1 3 4
2 1
3 -
4 -
5 -
Graph is not a tree
$ ./gist tests/02
V Connected to
-- ------------
0 2 5
1 3 4
2 1
3 -
4 -
5 -
Graph is a tree
Submission
Submit via the give command
$ give cs2521 sample_exam_q7 gist.c
Question 8 (15 marks)
Your task is to write a function, TreeSumOdds, that returns the sum of all of the odd values in the given tree.
Files
Tree.c Contains code for reading and printing a binary tree
Tree.h Contains the definition of the binary tree data structure and function prototypes
testTreeSumOdds.c
Contains the main function, which reads in a binary tree from standard input, calls
TreeSumOdds, and prints out the result.
TreeSumOdds.c Contains TreeSumOdds, the function you must implement
Makefile A makefile to compile your code
tests/ A directory containing the inputs and expected outputs for some basic tests
Examples
Your program should behave like these examples:
$ ./testTreeSumOdds
Enter the preorder traversal of the tree: 3 2 1 4 5
Enter the in-order traversal of the tree: 1 2 3 4 5
Tree:
3
/ \
2 4
/ \
1 5
TreeSumOdds returned 9
$ ./testTreeSumOdds
Enter the preorder traversal of the tree: 8 4 2 6 12 14
Enter the in-order traversal of the tree: 2 4 6 8 12 14
Tree:
8
/ \
/ \
4 12
/ \ \
2 6 14
TreeSumOdds returned 0
$ ./testTreeSumOdds
Enter the preorder traversal of the tree: 3 -9 -5 1 6 4
Enter the in-order traversal of the tree: -9 -5 1 3 4 6
Tree:
3
/ \
/ \
/ \
-9 6
\ /
-5 4
\
1
TreeSumOdds returned -10
Submission
Submit via the give command
$ give cs2521 sample_exam_q8 TreeSumOdds.c
Question 9 (20 marks)
Your task is to write a function, numReachable, that returns the number of vertices that are reachable from a source
vertex in the given graph, including the source vertex itself.
Files
Graph.c Contains the implementation of a graph ADT
Graph.h Contains the interface of the graph ADT
testNumReachable.c
Contains the main function, which reads in a graph from standard input, calls
numReachable for each vertex read in, and prints out the results.
numReachable.c Contains numReachable, the function you must implement
Makefile A makefile to compile your code
tests/ A directory containing the inputs and expected outputs for some basic tests
Examples
Your program should behave like these examples:
$ ./testNumReachable
Enter number of vertices: 12
Enter number of edges: 11
Enter edges in the form v-w: 0-8 0-3 3-8 0-10 10-2 1-9 1-5 5-9 4-6 4-7 4-11
Graph: nV = 12
Edges:
0: 0-3 0-8 0-10
1: 1-5 1-9
2: 2-10
3: 3-0 3-8
4: 4-6 4-7 4-11
5: 5-1 5-9
6: 6-4
7: 7-4
8: 8-0 8-3
9: 9-1 9-5
10: 10-0 10-2
11: 11-4
Enter the source vertex: 2
Number of vertices reachable from vertex 2: 5
Enter the source vertex: 1
Number of vertices reachable from vertex 1: 3
Enter the source vertex: 4
Number of vertices reachable from vertex 4: 4
Enter the source vertex: Ctrl-D
$ ./testNumReachable
Enter number of vertices: 12
Enter number of edges: 7
Enter edges in the form v-w: 0-1 2-3 3-4 5-9 5-10 9-11 10-11
Graph: nV = 12
Edges:
0: 0-1
1: 1-0
2: 2-3
3: 3-2 3-4
4: 4-3
5: 5-9 5-10
6:
7:
8:
9: 9-5 9-11
10: 10-5 10-11
11: 11-9 11-10
Enter the source vertex: 3
Number of vertices reachable from vertex 3: 3
Enter the source vertex: 6
Number of vertices reachable from vertex 6: 1
Enter the source vertex: 5
Number of vertices reachable from vertex 5: 4
Enter the source vertex: Ctrl-D
Submission
Submit via the give command
$ give cs2521 sample_exam_q9 numReachable.c
COMP2521 21T2: 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 .edu.au
CRICOS Provider 00098G
https://www.cse.unsw.edu.au/
https://www.unsw.edu.au/
mailto: .edu.au