KIT107留学生代做、C++编程语言调试、data代写、代做c++代写

日期：2020-06-22 11:13

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 <stdlib.h>

#include <stdio.h>

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 <stdlib.h>

2 #include <stdio.h>

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]