微信客服：xiaoxionga100
微信客服：ITCS521
COMP2521-C代写
时间：2021-11-20
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 1/10
Sample Exam
Thu 2nd December 2021
Changelog
All changes to the exam paper and files will be listed here.
Exam Conditions
You can start reading the exam at 2pm Thursday 2 December 2021 Sydney time (AEST).
You can start typing at 2pm Thursday 2 December 2021 Sydney time (AEST).
You have until 5pm Thursday 2 December 2021 Sydney time (AEST) to complete this exam.
Only submissions before 5pm Thursday 2 December 2021 Sydney time (AEST) will be marked.
Students with extra exam time approved by Equitable Learning Services (ELS) can make submissions after 5pm Thursday 2 December
2021 Sydney time (AEST) within their approved extra time.
You are not permitted to communicate (email, phone, message, talk, social networks, etc.) with anyone during this exam, except
COMP2521 staff.
Again, please note that you are not permitted to get help from anyone except COMP2521 staff during this exam.
You are not permitted to access web pages or other internet resources, except the the following web pages (for the exam, the lecture
notes and documentation):
you can access and read this exam paper!
you can access the course material available on the course webpage and your course work (your tut/lab solutions and assignment
work).
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)
You are not permitted to access any other papers, books or computer files, except for the following: this exam, your tut/lab solutions
and assignment work for this course.
You are not permitted to use code-synthesis tools such as GitHub Copilot and other similar tools.
Importantly, please make sure that you submit your original work and don't copy! We will use sophisticated plagiarism
software/techniques to detect any possible breaches.
Even after you finish the exam, on the day of the exam, on the day of the exam do not communicate your exam answers to anyone.
Some students have extended time to complete the exam.
Do not place your exam work in any location, including file sharing services such as Dropbox or GitHub, accessible to any other
person.
Ensure during the exam no other person in your household can access your work.
Your zpass should not be disclosed to any other person. If you have disclosed your zpass, you should change it immediately.
Deliberate violation of exam conditions will be referred to Student Integrity as serious misconduct.
Special Consideration
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 cs2521@cse.unsw.edu.au
immediately and apply for special consideration shortly after.
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.
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 2/10
Admin
Marks Contributes 45% towards your final mark
Submit See the submission instructions for each question
Date and time Thursday 2nd December 2pm-5pm (AEST)
Total Marks 100
Total number of questions 9 (not worth equal marks)
Note: the actual final exam will have 12-16 questions
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/21T3/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 (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 q1.txt.
Question 1b: How many multiplications are performed if N == 20? Type your answer in q1.txt.
Question 1c: What is the algorithmic complexity of this function (relative to N)? Type your answer in q1.txt.
Submission
Submit via the give command
$ give cs2521 sample exam q1 q1.txt
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.
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 3/10
$ g p _ _q q
Question 2 (7 marks)
Consider the following trie. Finishing nodes are shown in red.
Question 2a: How many words are stored in this trie? Type your answer in q2.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 q2.txt.
Question 2c: How many new nodes would be added if the word "bogus" was added to the trie? Justify your answer. Type your
answer in q2.txt.
Question 2d: How many new nodes would be added if the word "do" was added to the trie? Justify your answer. Type your answer
in q2.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q2 q2.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? Justify your answer. Type
your answer in q3.txt.
Question 3b: After the value 42 was inserted into this 2-3-4 tree, what values would be in the root node? Justify your answer. Type
your answer in q3.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q3 q3.txt
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 4/10
Question 4 (7 marks)
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. Type your answer in q4.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q4 q4.txt
Question 5 (6 marks)
Question 5a: What is the difference between an Euler path/tour and a Hamilton path/tour? Type your answer in q5.txt.
Question 5b: Does the following graph have any Euler/Hamilton paths/tours? If so, give the paths/tours. Type your answer in q5.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q5 q5.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:
n
O(1)
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 5/10
$ 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:
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 6/10
conditions:
only one node has no incoming edges - this node is the root of the tree
all other nodes have exactly one incoming edge
nodes may have 0, 1 or 2 outgoing edges
there is exactly one path from the root to every other node
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:
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 7/10
$ ./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
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 8/10
$ ./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:
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 9/10
$ ./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 21T3: 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 cs2521@cse.unsw.edu.au
CRICOS Provider 00098G
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 10/10
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 1/10
Sample Exam
Thu 2nd December 2021
Changelog
All changes to the exam paper and files will be listed here.
Exam Conditions
You can start reading the exam at 2pm Thursday 2 December 2021 Sydney time (AEST).
You can start typing at 2pm Thursday 2 December 2021 Sydney time (AEST).
You have until 5pm Thursday 2 December 2021 Sydney time (AEST) to complete this exam.
Only submissions before 5pm Thursday 2 December 2021 Sydney time (AEST) will be marked.
Students with extra exam time approved by Equitable Learning Services (ELS) can make submissions after 5pm Thursday 2 December
2021 Sydney time (AEST) within their approved extra time.
You are not permitted to communicate (email, phone, message, talk, social networks, etc.) with anyone during this exam, except
COMP2521 staff.
Again, please note that you are not permitted to get help from anyone except COMP2521 staff during this exam.
You are not permitted to access web pages or other internet resources, except the the following web pages (for the exam, the lecture
notes and documentation):
you can access and read this exam paper!
you can access the course material available on the course webpage and your course work (your tut/lab solutions and assignment
work).
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)
You are not permitted to access any other papers, books or computer files, except for the following: this exam, your tut/lab solutions
and assignment work for this course.
You are not permitted to use code-synthesis tools such as GitHub Copilot and other similar tools.
Importantly, please make sure that you submit your original work and don't copy! We will use sophisticated plagiarism
software/techniques to detect any possible breaches.
Even after you finish the exam, on the day of the exam, on the day of the exam do not communicate your exam answers to anyone.
Some students have extended time to complete the exam.
Do not place your exam work in any location, including file sharing services such as Dropbox or GitHub, accessible to any other
person.
Ensure during the exam no other person in your household can access your work.
Your zpass should not be disclosed to any other person. If you have disclosed your zpass, you should change it immediately.
Deliberate violation of exam conditions will be referred to Student Integrity as serious misconduct.
Special Consideration
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 cs2521@cse.unsw.edu.au
immediately and apply for special consideration shortly after.
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.
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 2/10
Admin
Marks Contributes 45% towards your final mark
Submit See the submission instructions for each question
Date and time Thursday 2nd December 2pm-5pm (AEST)
Total Marks 100
Total number of questions 9 (not worth equal marks)
Note: the actual final exam will have 12-16 questions
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/21T3/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 (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 q1.txt.
Question 1b: How many multiplications are performed if N == 20? Type your answer in q1.txt.
Question 1c: What is the algorithmic complexity of this function (relative to N)? Type your answer in q1.txt.
Submission
Submit via the give command
$ give cs2521 sample exam q1 q1.txt
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.
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 3/10
$ g p _ _q q
Question 2 (7 marks)
Consider the following trie. Finishing nodes are shown in red.
Question 2a: How many words are stored in this trie? Type your answer in q2.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 q2.txt.
Question 2c: How many new nodes would be added if the word "bogus" was added to the trie? Justify your answer. Type your
answer in q2.txt.
Question 2d: How many new nodes would be added if the word "do" was added to the trie? Justify your answer. Type your answer
in q2.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q2 q2.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? Justify your answer. Type
your answer in q3.txt.
Question 3b: After the value 42 was inserted into this 2-3-4 tree, what values would be in the root node? Justify your answer. Type
your answer in q3.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q3 q3.txt
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 4/10
Question 4 (7 marks)
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. Type your answer in q4.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q4 q4.txt
Question 5 (6 marks)
Question 5a: What is the difference between an Euler path/tour and a Hamilton path/tour? Type your answer in q5.txt.
Question 5b: Does the following graph have any Euler/Hamilton paths/tours? If so, give the paths/tours. Type your answer in q5.txt.
Submission
Submit via the give command
$ give cs2521 sample_exam_q5 q5.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:
n
O(1)
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 5/10
$ 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:
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 6/10
conditions:
only one node has no incoming edges - this node is the root of the tree
all other nodes have exactly one incoming edge
nodes may have 0, 1 or 2 outgoing edges
there is exactly one path from the root to every other node
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:
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 7/10
$ ./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
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 8/10
$ ./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:
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 9/10
$ ./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 21T3: 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 cs2521@cse.unsw.edu.au
CRICOS Provider 00098G
11/18/21, 1:11 PM COMP2521 21T3 - Sample Exam
https://cgi.cse.unsw.edu.au/~cs2521/21T3/sample-exam 10/10
