Pages: 10
Questions: 7
UNIVERSITY OF TASMANIA
EXAMINATIONS FOR DEGREES AND DIPLOMAS
November 2019
KIT107 Programming
First and Only Paper
Ordinary Examination
Time Allowed: THREE (3) hours
Reading Time: FIFTEEN (15) minutes
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 section should be written in a DIFFERENT book.
Student ID No: _________________
-2- KIT107 Programming
Continued…
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.
Question 1. (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)
{
node c;
c = l->first;
while (c->next->next != NULL)
{
c = c->next;
}
c->next = NULL;
}
a. What does the function f1() do?
[6 marks]
b. What possible situation(s) could cause the code to fail?
[6 marks]
-3- KIT107 Programming
Continued…
Question 2. (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–62 re-creates the list l1 so that it contains all the nodes in both the original
non-empty l1 and non-empty l2 with the first node coming from l1, the second from
l2, the third from l1, the fourth for l2, and so on until one of these original lists is
empty in which case all remaining nodes from the other list are appended at the back.
There are, unfortunately, six lines in the program 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.
1 #include
2 #include
3
4 struct dnode_int;
5 typedef struct dnode_int *dnode;
6
7 struct dnode_int
8 {
9 dnode prev;
10 void *data;
11 dnode next;
12 };
13
14 struct list_int;
15 typedef struct list_int *list;
16
17 struct list_int
18 {
19 dnode first;
20 };
21
22 void zip(list l1, list l2)
23 {
24 dnode c1 = l1->first;
25 dnode c2 = l2->first;
26 dnode r = NULL;
27
28 while ((c1 != NULL) && (c2 != NULL))
29 {
30 if (r->prev == NULL)
31 {
32 r = c1;
33 l2->first = r;
34 }
35 else
36 {
37 r->next = c1;
38 r->next->prev = r;
39 }
40 c1 = c1->next;
41 r->next = c2;
-4- KIT107 Programming
Continued…
42 r->next->prev = r;
43 c2 = c2->next;
44 r = r->next;
45 }
46
47 while (c2 != NULL)
48 {
49 r->next = c2;
50 r->prev->next = r;
51 c2 = c2->next;
52 r = r->next;
53 }
54
55 while (c2 != NULL)
56 {
57 r->next = c2;
58 r->next->prev = r;
59 c2 = c2->next;
60 r = r->next;
61 }
62 }
[12 marks]
Question 3. (Assessing ILOs: 1 and 3)
A Robot has a male or female voice and can speak when spoken to by a Human. It can
be created (by advising its Voice), and can also have its speaking volume
increased/decreased by a specified amount from its current value (initially 25) to a value
not less than 0 and not greater than 50 by a Human, or examined for its value.
a. Produce a UML diagram for the Robot ADT as described above.
[4 marks]
b. Convert the UML diagram into a Java interface.
[4 marks]
c. Convert the UML diagram into a C header file.
[4 marks]
Question 4. (Assessing ILOs: 2 and 3)
a. Explain polymorphism of values and, using examples, how this is implemented
in each of Java and C.
[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.
[6 marks]
-5- KIT107 Programming
Continued…
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.
Question 5. (Assessing ILOs: 1, 2, and 3)
Marbles! Large ones, medium-sized ones, small ones. Cats-eye ones, plain ones, swirly
ones. Glass ones, wooden ones, plastic ones. Old ones, new ones. Marbles!
A Toy Company has asked you to develop an app to manage a club’s collection of
marbles, to add marbles to the collection, and to remove marbles from the collection.
See part (e) ii for details on required functionality.
There are an unknown number of members and membership changes all the time with
new members added weekly. All marbles belonging to the same member should be
stored in the computerised collection together for ease of access. There will be at most
1000 marbles per member.
Each marble should have its diameter in millimetres (a double), content (an
enumeration), material (an enumeration), and age (a bool) stored. The collection of
marbles for each member should be stored in increasing order of diameter (smallest
first).
Given the following enumerations:
typedef enum {plain, swirled, cats_eye} content;
typedef enum {glass, wooden, plastic} material;
A marble may be defined as follows:
struct marble_int {
double diameter;
content look;
material made_of;
bool new;
};
typedef struct marble_int *marble;
and you may assume the existence of those types and the following types and functions:
void init_marble(marble *mp, double d, content c, material
t, bool n);
double get_diameter(marble m);
material get_look(marble m);
content get_material(marble m);
bool get_age(marble m);
void set_diameter(marble m, double d);
void set_look(marble m, content c);
void set_material(marble m, material t);
void set_age(marble m, bool n);
char *to_string(marble m);
-6- KIT107 Programming
Continued…
The types and variable required to implement members and the Club include the
following:
typedef collection;
typedef struct {
char *name;
collection marbles;
} member;
typedef members;
members club;
a. Which underlying data structure (array or linked-list) will you use as a basis to
model the overall collection of members (i.e. the members type)? In two–
three sentences, justify your answer.
[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 members? In two–three sentences, justify your answer by
indicating the functionality required.
[4 marks]
c. Which underlying data structure (array or linked-list) will you use as a basis to
model the collection of marbles for each member (i.e. the collection
type)? In two–three sentences, justify your answer.
[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 marbles for each member? In two–three sentences, justify
your answer by indicating the functionality required.
[4 marks]
e. Given your definition for the collection of sessions in parts (a) and (c) above:
i. Using typedefs, define the types members and collection
that represent a collection of members and marbles respectively.
[5 marks]
ii. Implement the following functions that allow the manipulation of a
collection of marbles given your answers above:
• void init_collection(collection *cp) — create
an empty collection;
[5 marks]
• void add_marble(collection c, marble m) —
add the marble m to the beginning of the specified collection
c;
[4 marks]
-7- KIT107 Programming
Continued…
• void display_marbles(collection c, content k)
— print all marbles in the collection c which have content k;
[5 marks]
• int display_range(collection c, double
min_diameter, double max_diameter) — print all
marbles in the collection c within the given diameter range
(min_diameter–max_diameter inclusive); and
[6 marks]
• void remove(collection c) — delete all marbles in
the collection c which are ‘old’.
[10 marks]
-8- KIT107 Programming
Continued…
Question 6. (Assessing ILOs: 1, 2, and 3)
Consider the following digits:
1, 2, 0, 4, 9, 8, 5, 7, 3, 6
For each of the Abstract Data Types (ADTs) in (a)–(e) below:
i Show, 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)]
ii Indicate 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]
iii Indicate 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]
iv Indicate 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. stack;
b. binary search tree (in ascending order);
c. priority queue (in ascending order);
d. set; and
e. search tree of degree four (4) which is kept as compact as possible but which
is not re-balanced after values are inserted.
[51 marks]
-9- KIT107 Programming
Continued…
SECTION C — MEDIUM ANSWER QUESTIONS
Answer ALL questions available in Section C. The question in Section C is worth 30
marks. This section is worth 30 marks, or 16.7% of the examination.
Question 7. (Assessing ILOs: 1, 2, and 3)
A node in a table of strings can be defined as follows:
struct tblnode_int;
typedef struct tblnode_int *tblnode;
struct tblnode_int
{
char *data;
tblnode prev_column;
tblnode next_column;
tblnode prev_row;
tblnode next_row;
};
and you may assume the existence of those types and the following functions:
void init_tblnode(tblnode *tp, void *o);
char *get_data(tblnode t);
tblnode get_prev_column(tblnode t);
tblnode get_next_column(tblnode t);
tblnode get_prev_row(tblnode t);
tblnode get_next_row(tblnode t);
void set_data(tblnode t, char *s);
void set_prev_column(tblnode t, tblnode c);
void set_next_column(tblnode t, tblnode c);
void set_prev_row(tblnode t, tblnode r);
void set_next_row(tblnode t, tblnode r);
A table (with possibly varying numbers of columns per row and rows per column) can be
defined as follows:
struct table_int;
typedef struct table_int *table;
struct table_int
{
tblnode top_left;
};
An append() function can be written which takes a table to extend (t), and which adds
another row below the last. This new row should have as many columns as the existing
final row and each data item in the new row should be set to "".
A constructive — rather than destructive — implementation could comprise the following
functions:
void init_table(table *tp);
bool is_empty(table t);
table clone(table t);
table append(table t);
-10- KIT107 Programming
a. Implement the clone() function. You may write other functions to assist
your implementation.
[20 marks]
b. Using the clone() function, implement the append() function.
[10 marks]