CS计算机代考程序代写 data structure database algorithm Sample Exam

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