KXA Exam Template Student ID No: Click or tap here to enter text.Pages: 13 Questions: 7 UNIVERSITY OF TASMANIA EXAMINATIONS FOR DEGREES AND DIPLOMAS June 2020 KIT107 Programming First and Only Paper...

Exam


KXA Exam Template Student ID No: Click or tap here to enter text.Pages: 13 Questions: 7 UNIVERSITY OF TASMANIA EXAMINATIONS FOR DEGREES AND DIPLOMAS June 2020 KIT107 Programming First and Only Paper Ordinary Examination Examiners: Dr J Dermoudy & Dr S Xu Time Allowed: THREE (3) hours Reading Time[footnoteRef:1]: FIFTEEN (15) minutes [1: You may write during the Reading Time.] Instructions: There is a total of 180 marks available. You are required to answer ALL SEVEN (7) questions — attempt ALL FOUR (4) questions from Section A, BOTH OF THE TWO (2) questions from Section B, and THE ONE (1) question from Section C. Answers for each question should be provided in this document and the document uploaded to MyLO before the deadline. This is an individual assessment task. You may not consult with anyone while completing the examination. Your work will be checked for plagiarism and severe penalties may be applied under the Ordinance of Student Academic Integrity if academic integrity breaches are identified. SECTION A — SHORT ANSWER QUESTIONS Attempt ALL questions available in Section A. All questions in Section A are of equal value. Each question is worth 12 marks. This section is worth 48 marks, or 26.7% of the examination. (Assessing ILOs: 1, 2, and 3) Given the following inclusions and type definitions: #include #include struct node_int; typedef struct node_int *node; struct node_int { void *data; node next; }; struct list_int; typedef struct list_int *list; struct list_int { node first; }; And the following function definition: void f1(list l, void *o) { node n; n = (node)malloc(sizeof(struct node_int)); n->data = o; n->next = NULL; while (l->first->next != NULL) { l->first = l->first->next; } l->first->next = n; } a. What does the function f1() do? Click or tap here to enter text. [6 marks] b. What possible situation(s) could cause the code to fail? Click or tap here to enter text. [6 marks] (Assessing ILOs: 1, 2, and 3) A doubly-linked list may be defined as shown below on lines 4–20. The function declared on lines 22–74 creates a new list (l1)containing every second node of l2 (starting with its first) and every second node of l3 (starting with its first), alternatively drawing from l2 and l3. When one of these lists is empty, every second remaining node from the other list is appended at the back. The lists l2 and l3 are destroyed in the process; this is not an error. There are, unfortunately, six lines in the splice() function with errors. Please identify the line number on which each error occurs and re-write the line in your answer book in its corrected form. Do not rewrite lines that do not contain errors. -11-KIT107 Programming Continued... Continued… #include #include struct dnode_int; typedef struct dnode_int *dnode; struct dnode_int { dnode prev; void *data; dnode next; }; struct list_int; typedef struct list_int *list; struct list_int { dnode first; }; void splice(list* l1, list l2, list l3) { dnode c1; dnode c2 = l2->first; dnode c3 = l2->first; *l1 = (list)malloc(sizeof(list)); *l1->first = NULL; while ((c2 != NULL) || (c3 != NULL)) { if (c2 != NULL) { if (c1 == NULL) { (*l1)->first = c2; c1 = (*l1)->first; } else { c1->next = c2; c2->prev = c1; c1 = c2; c2 = c2->next; if (c2 != NULL) { c2 = c2->next; } } } if (c3 != NULL) { if (c1 == NULL) { (*l1)->first = c3; c1 = (*l1)->first; } else { c1->next = c3; c3->prev = c1; c1 = c3; c3 = c3->next; if (c3 != NULL) { c3 = c3->next; } } } c1 = NULL; } } Click or tap here to enter text. [12 marks] (Assessing ILOs: 1 and 3) A computer Mouse has two buttons (left and right) which can be pressed or released. Clicking a button is a press followed by a release. The mouse can also be moved by providing a double distance forward/backward and a double distance left/right. Distances forward and right are positive numbers; distances backward and left are negative numbers. a. Produce a UML diagram for the Mouse ADT as described above. [4 marks] b. Convert the UML diagram into a Java interface. Click or tap here to enter text. [4 marks] c. Convert the UML diagram into a C header file. Click or tap here to enter text. [4 marks] (Assessing ILOs: 2 and 3) a. Explain why we implement polymorphic data structures and give examples in each of Java and C. Click or tap here to enter text. [6 marks] b. Explain how a function pointer aids genericity in C and give code which includes an example of the use of a function pointer. Click or tap here to enter text. [6 marks] SECTION B — LONG ANSWER QUESTIONS Answer ALL questions available in Section B. All questions in Section B are of equal value. Each question is worth 51 marks. This section is worth 102 marks, or 56.7% of the examination. (Assessing ILOs: 1, 2, and 3) Yoyos! Thought to be invented in China at least 2500 years ago, these were a huge worldwide craze in many centuries — most recently perhaps in the 1970s. You’ve been asked to measure the craze across Europe (only 44 countries), looking at where manufacturing started through to markets large and small for a fixed six-week period during the height of the craze. See part (e) ii for details on required functionality. The data are organised by country (and are presented in alphabetical order) and by ‘date’ (ascending order of week number and year). For each week the data value is the cumulative number of yoyos sold (in hundreds) for that country. A sale may be defined as follows: struct sale_int { char *date; int num_sold; }; typedef struct sale_int *sale; and you may assume the existence of those types and the following types and functions: void init_sale(sale *s, char *d, int n); char *get_date(sale s); int get_num_sold(sale s); void set_date(sale s, char *d); void set_num_sold(sale s, int n); char *to_string(sale s); The types and variables required to implement countries and the collection of sales include the following: typedef ??? collection; typedef struct { char country_name[35]; collection sales; int num_weeks; } country; typedef ??? countries; countries craze; int num_countries; a. Which underlying data structure (array or linked-list) will you use as a basis to model the overall collection of countries (i.e. the countries type)? In two–three sentences, justify your answer. Click or tap here to enter text. [4 marks] b. Which kind of abstract data type (binary tree, general tree, array, stack, priority queue, double-ended queue, set, list, etc.) would you use to model the collection of countries? In two–three sentences, justify your answer by indicating the functionality required. Click or tap here to enter text. [4 marks] c. Which underlying data structure (array or linked-list) will you use as a basis to model the collection of sales for each country (i.e. the collection type)? In two–three sentences, justify your answer. Click or tap here to enter text. [4 marks] d. Which kind of abstract data type (binary tree, general tree, array, stack, priority queue, double-ended queue, set, list, etc.) would you use to model the collection of sales for each country? In two–three sentences, justify your answer by indicating the functionality required. Click or tap here to enter text. [4 marks] e. Given your definition for the collection of sessions in parts (a) and (c) above: i. Using typedefs, define the types countries and collection that represent a collection of countries and sales respectively. Click or tap here to enter text. [5 marks] ii. Implement the following functions that allow the manipulation of a collection of countries given your answers above: · void init_craze() — create an empty data set; Click or tap here to enter text. [5 marks] · void add_sale(char *p, sale s) — add the sale s to the end of the collection for the named country p; Click or tap here to enter text. [9 marks] · void display_sales(char *p) — print all sales in the collection c for the named country p including the country name as a title, and rows comprising the date and number of sales; Click or tap here to enter text. [6 marks] · int count_range(int min, int max) — calculate and return the count of all countries with sales within the given sales range (min–max inclusive); and Click or tap here to enter text. [5 marks] · int lag() — count all sales entries for which the num_sold value is 0. Click or tap here to enter text. [5 marks] (Assessing ILOs: 1, 2, and 3) Consider the following digits: 9, 5, 7, 3, 6, 4, 2, 0, 8, 1 For each of the Abstract Data Types (ADTs) in (a)–(e) below: iShow, by using a conceptual diagram, the following ADTs after the digits have been inserted in the order that they are encountered. [4 marks for ADTs (a)–(d), 5 marks for ADT (e)] iiIndicate the best-case time complexity of searching the ADT for an arbitrary digit which is stored. (Do this for the general case, i.e. consider the ADT as having n values and convert to order (big-Oh) notation.) In a sentence, explain why this time complexity will occur. [2 marks for each ADT] iiiIndicate the average-case time complexity of searching the ADT for an arbitrary digit which is stored. (Do this for the general case, i.e. consider the ADT as having n values and convert to order (big-Oh) notation.) In a sentence, explain why this time complexity will occur. [2 marks for each ADT] ivIndicate the worst-case time complexity of searching the ADT for an arbitrary digit which is not stored. (Do this for the general case, i.e. consider the ADT as having n values and convert to order (big-Oh) notation.) In a sentence, explain why this time complexity will occur. [2 marks for each ADT] a. queue; i. Click or tap here to enter text. Click or tap here to enter text. Click or tap here to enter text. b. binary search tree; i. Click or tap here to enter text. Click or tap here to enter text. Click or tap here to enter text. c. priority queue (in descending order); i. Click or tap here to enter text. Click or tap here to enter text. Click or tap here to enter text. d. bag; and i. Click or tap here to enter text. Click or tap here