Week 09 Weekly Test Questions
Test Conditions
These questions must be completed under self-administered exam-like conditions. You must time the test yourself and ensure you comply with the conditions below.
- You may complete this test in CSE labs or elsewhere using your own machine.
- You may complete this test at any time before Week 10 Thursday 17:00.
- Weekly tests are designed to act like a past paper - to give you an idea of how well you are progressing in the course, and what you need to work on. Many of the questions in weekly tests are from past COMP1511 final exams.
- You must treat the first hour as a real exam - no access to external help from other people or the internet.
- Once the first hour has finished, you should take note of how far you got, which parts you didn't understand, and ask questions to clarify your understanding with course staff or on the course forum.
- Failure to follow the above instructions will result in a lower quality learning experience and ultimately a lower mark in the final exam.
- Once the first hour has finished, you may use the internet, get help from other people, and still submit your solutions afterwards.
You may access this language documentation while attempting this test:
You may also access manual entries (the man
command).
Any violation of the test conditions will results in a mark of zero for the entire weekly test component.
You should not write any code. Test in Progress — working time You have just over minutes left in the test. Test Complete! Your time for this test has finished. You may submit your work. You may choose to keep working, but you should reflect on how you went in this hour, and discuss with your tutor if you have concerns.
weekly test question:
Find the length of a Linked List
Linked lists are made up of nodes, which store one element of the list each, as well as the location (in memory) of the next element.
Nodes can store data of any type, but for this week we will be looking at nodes which store integers, which are defined like this:
struct node { struct node *next; int data; };
Download list_length.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/20T1/activities/list_length/list_length.c .
Your task is to add code to this function in list_length.c:
// Return the length of the linked list pointed by head
int length(struct node *head) {
// PUT YOUR CODE HERE (change the next line!)
return 42;
}
Add code to length so that its returns the length of the list.
For example if the linked list contains these 8 elements:
1, 7, 8, 9, 13, 19, 21, 42
length should return 8.
Testing
list_length.c also contains a main function which allows you to test your length function.This main function:
- converts the command-line arguments to a linked list
- assigns a pointer to the first node in the linked list to head
- calls list_length(head)
- prints the result.
Do not change this main function. If you want to change it, you have misread the question.
Your list_length function will be called directly in marking. The main function is only to let you test your list_length function
Here is how you use main function allows you to test list_length:
dcc list_length.c -o list_length ./list_length 1 2 4 8 16 32 64 128 256 9 ./list_length 2 4 6 5 8 9 6 ./list_length 13 15 17 17 18 5 ./list_length 42 4 2 ./list_length 0
Assumptions/Restrictions/Clarifications.
length should return a single integer.length should not change the linked list it is given. Your function should not change the next or data fields of list nodes.
length should not use arrays.
length should not call malloc.
length should not call scanf (or getchar or fgets).
length should not print anything. It should not call printf.
Do not change the supplied main function. It will not be tested or marked.
When you think your program is working you can autotest
to run some simple automated tests:
1511 autotest list_lengthWhen you are finished working on this exercise you must submit your work by running give:
give cs1511 test09_list_length list_length.c
weekly test question:
Delete the last element of a Linked List
Download list_delete_last.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/20T1/activities/list_delete_last/list_delete_last.c .
Your task is to add code to this function in list_delete_last.c:
//
// Delete the last node in list.
// The deleted node is freed.
// The head of the list is returned.
//
struct node *delete_last(struct node *head) {
// PUT YOUR CODE HERE (change the next line!)
return NULL;
}
struct node { struct node *next; int data; };delete_last is given one argument, head, which is the pointer to the first node in a linked list.
Add code to delete_last so that it deletes the last node from list.
delete_last should return a pointer to the new list.
If the list is now empty delete_last should return NULL.
delete_last should call free to free the memory of the node it deletes.
For example if the linked list contains these 8 elements:
16, 7, 8, 12, 13, 19, 21, 12
delete_last should return a pointer to a list with these elements:
16, 7, 8, 12, 13, 19, 21
Testing
list_delete_last.c also contains a main function which allows you to test your delete_last function.This main function:
- converts the command-line arguments to a linked list
- assigns a pointer to the first node in the linked list to head
- calls delete_last(head)
- prints the result.
Do not change this main function. If you want to change it, you have misread the question.
Your delete_last function will be called directly in marking. The main function is only to let you test your delete_last function
cp -n /web/cs1511/20T1/activities/list_delete_last/list_delete_last.c . dcc list_delete_last.c -o list_delete_last ./list_delete_last 16 7 8 12 13 19 21 12 [16, 7, 8, 12, 13, 19, 21] ./list_delete_last 2 4 6 2 4 6 [2, 4, 6, 2, 4] ./list_delete_last 42 [] ./list_delete_last []
Assumptions/Restrictions/Clarifications.
delete_last should call free to free the memory for the node it deletesdelete_first should not change the data fields of list nodes.
delete_last should not use arrays.
delete_last should not call malloc.
delete_last should not call scanf (or getchar or fgets).
delete_last should not print anything. It should not call printf.
Do not change the supplied main function. It will not be tested or marked.
When you think your program is working you can autotest
to run some simple automated tests:
1511 autotest list_delete_lastWhen you are finished working on this exercise you must submit your work by running give:
give cs1511 test09_list_delete_last list_delete_last.c
weekly test question:
Delete elements from a Linked List until it's ordered
Download list_delete_ordered.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/20T1/activities/list_delete_ordered/list_delete_ordered.c .
Your task is to add code to this function in list_delete_ordered.c:
// Remove any nodes in a list that are higher
// than the node directly after them.
// Return the head of the list.
// The returned list must have no disorder in it!
struct node *remove_disorder(struct node *head) {
// WRITE YOUR CODE HERE (you may need to change the line below)
return head;
}
struct node { int data; struct node *next; };
The node struct is a normal linked list node containing an integer.
remove_disorder should take a pointer to the head of a node list and return the head of the node list after it has removed any disorder in the list. A list is considered to have disorder if there are any nodes in it that are higher in value (using the integer data) than the node directly after them.
remove_disorder should remove nodes from the list, but otherwise make no changes to the list itself.
For example if the list of nodes looks like this:
{1, 3, 2}
remove_disorder should return
{1, 2}
However, if the list looks like this:
{2, 4, 5, 1}
remove_disorder should return
{1}The 5 is definitely removed for being higher than the 1. After that, the 4 is then disordered because it is now next to the 1 and higher than it. Then, the 2 must be removed because it will be next to the 1 and higher than it.
remove_disorder should always return a list with no disorder in it. If any removals cause more disorder, these disordered nodes must also be removed before remove_disorder returns.
Assumptions/Restrictions/Clarifications.
struct node cannot be edited. It must be used as it is.
You may not use arrays in this solution. Arrays are not necessary to complete this task.
You can assume that you'll never receive an empty list of nodes.
When you think your program is working you can autotest
to run some simple automated tests:
1511 autotest list_delete_orderedWhen you are finished working on this exercise you must submit your work by running give:
give cs1511 test09_list_delete_ordered list_delete_ordered.c
Submission
You can run give multiple times. Only your last submission will be marked.
Don't submit any exercises you haven't attempted.
If you are working at home, you may find it more convenient to upload your work via give's web interface.
Remember you have until Week 10 Thursday 17:00 to complete this test.
Automarking will be run by the lecturer several days after the submission deadline
for the test, using test cases that you haven't seen:
different to the test cases autotest
runs for
you.
(Hint: do your own testing as well as running
autotest
)
Test Marks
After automarking is run by the lecturer you can view it here the resulting mark will also be available via via give's web interface or by running this command on a CSE machine:
1511 classrun -sturec
The test exercises for each week are worth in total 1 marks.
The best 7 of your 8 test marks for weeks 3-10 will be summed to give you a mark out of 7.