代写data留学生、代做C++设计、C++程序语言调试

日期：2020-09-29 07:15

This assessment paper consists of 4 questions on 8 printed pages

JANUARY 2020 TRIMESTER

MAIN FINAL ASSESMENT

SATURDAY, 16 MAY 2020 TIME: 9.00 AM – 4.00 PM (3 HOURS)

BACHELOR OF COMPUTER SCIENCE (HONS)

BACHELOR OF INFORMATION SYSTEMS (HONS)

INFORMATION SYSTEMS ENGINEERING

BACHELOR OF INFORMATION TECHNOLOGY (HONS)

COMMUNICATIONS AND NETWORKING

BACHELOR OF INFORMATION TECHNOLOGY (HONS)

COMPUTER ENGINEERING

Instructions to Students:

General

1. This Final Assessment (FA) is an Individual, Open-Book assessment which consists

of FOUR (4) questions. Each question carries 25 marks.

2. You are required to answer ALL questions, and submit the ANSWER SCRIPT by

12:00pm, 16 MAY 2020.

3. During the period of 3 hours of this FA, the examiner(s) can be reached at

You may use the above e-platform(s) to check with the examiner(s) if you need any

clarification on this FA question paper

4. You may refer to any books, lecture notes, published materials, online resources, etc

when answering the questions. However, COPY-AND-PASTE, DISCUSSION, and

SHARING OF ANSWERS are STRICTLY PROHIBITED during the FA.

Answer Script File

5. The answer script MUST be either a Microsoft Word or PDF file, in A4 size format.

Note: Please keep the file size NOT exceeding 10MB.

UCCD1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

2

UCCD 1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

___________________________________________________________________________

This assessment paper consists of 4 questions on 8 printed pages.

6. Please check you index number generated by the Division of Examinations, Awards,

For example, if you are from the degree programme IB, and your Index Number is

A01234CBIBF, then your answer script should be named as

UCCD1024_ FA_ IB_A01234CBIBF.doc

Answer Script Submission

before the due time/date.

i. CN students please send your answer script to:

Note: For the title of your email, please use the file name of your answer

script. That is,

UCCD1024_FA_[Programme Abbreviation]_[Your Index Number]

8. Please make sure that you submit the same copy of answer scripts to the above

platforms. If different answer scripts are received, the examiner will just randomly

choose one of them to mark and the other will be totally ignored.

9. The answer script submitted after the due time/date may incur a late penalty as shown

below:

pre:

t to:

.

r

and Scholarships (DEAS). You MUST name your answer script using the following

file name for submission:

[UCCD1024]_FA_[Programme Abbreviation]_[Your Index Number]

3

UCCD 1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

___________________________________________________________________________

This assessment paper consists of 4 questions on 8 printed pages.

i. 0 hour < lateness ≤ 1 hour: 10% mark deduction

ii. 1 hour < lateness ≤ 3 hour: 20% mark deduction

iii. 3 hour < lateness ≤ 5 hours: 30% mark deduction

iv. 5 hours < lateness ≤ 7 hours: 40% mark deduction

v. 7 hours < lateness ≤ 9 hours: 50% mark deduction

vi. Lateness > 9 hours : 100% mark deduction

Contents of Answer Script

10. The first page of your answer script is the cover page. You MUST use the template

given in Appendix 1 and fill up the following information

? You Degree Programme (Abbreviation)

? Your Index Number

? Your Name

? Your Student ID

11. The second page of your answer script is the Declaration Form. You MUST use the

template given in Appendix 2, and sign on this form to indicate your authenticity of

submitted work without plagiarism.

12. Each question should be answered starting on a new page. It is recommended that the

answer to each question is limited to [5] pages or [500] words, whichever is lower.

13. In your answer script, all texts MUST be typed using Times New Roman characters

with font size no less than 12, except for the drawings and equations/calculations.

14. For the drawings and equations/calculations, you MUST draw/write them on a blank

paper, and then take pictures and include the pictures in the Word document as part of

your answers.

15. Please include a page number on each and every page of your answer script.

WARNING OF PLAGIARISM

16. All answer scripts will be uploaded by the examiners to Turnitin for similarity

check. In the case of plagiarism being suspected, the evidences will be submitted

to the University Examination Disciplinary Committee for further investigation

and trial. If found guilty, serious disciplinary action will be taken against the

students.

4

UCCD 1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

___________________________________________________________________________

This assessment paper consists of 4 questions on 8 printed pages.

Questions: [Total: 100 Marks]

Q1. (a) Derive a suitable data structure for a data storage system that supports

insertion of large and unknown number (N) of data records. The design should

be efficient with respect to memory usage and search with timing complexities

of (1) best case as O(1), (2) worst case as O(log(N)), and (3) average case as

O(log(N/c)) where c is a constant.

(i) Provide a diagram of the proposed data structure design and label each

component. Briefly explain the design on how it can work. (5 marks)

(ii) Describe the scenario when the best-case timing can be achieved.

(2 marks)

(iii) Describe the scenario when the worst-case timing is encountered.

(3 marks)

(iv) Describe the scenario when the average case timing can be achieved.

(2 marks)

(v) What could be the meaning of c in your design? (1 mark)

(b) A simplified company structure is displayed in Figure 1 where each person

can have an unknown number of staffs under his/her care. In Figure 1, only the

technical manager branch has been expanded due to space restriction. The

company structure can be modeled by a tree where each parent node can have

multiple descendants.

Figure 1. A simplified company structure tree.

CEO A

Finance

Manager B

Technical

Manager C

HR

Manager D

Admin

Manager E

Senior

Manager F

Assistant

Manager G

Staff H Staff I

5

UCCD 1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

___________________________________________________________________________

This assessment paper consists of 4 questions on 8 printed pages.

struct BTNode {

string item;

BTNode *left, *right;

};

struct BT {

BTNode *root;

}; (4 marks)

(ii) Based on Q1(i), give a diagram of the data structure generated for the

company tree structure shown in Figure 1. (2 marks)

(iii) Based on Q1(i), provide a method staffSupervisors(string

staffName) to search for a staff name and then print all his/her

immediate supervisor names. For example, if "H" is the input

parameter to staffSupervisors(), the names printed will be F,

C and A with respect to Figure 1. Give C++ code or pseudo-code as

your answer. (6 marks)

[Total: 25 marks]

Q2. (a) Assume the following initializations:

#include <iostream>

using namespace std;

struct Node{

int num;

Node *next;

};

struct Node *head=NULL;

Given the tree definitions below, design a new scheme to represent acompany structure in general.

The new scheme can change the namesand meanings of ‘left’ and ‘right’

but it cannot add any newvariable or link into BTNode. In addition, no new definition of

struct can be added too. Your answer should give the modified

BTNode definition and brief explanation of the changes.

(i)

Q1.(b) (Continued)

6

UCCD 1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

___________________________________________________________________________

This assessment paper consists of 4 questions on 8 printed pages.

Q2.(a) (Continued)

(i) Write a program to insert Node at the beginning. Meanwhile, you

should have to include the program to traverse and display all nodes

(print items). (6 marks)

(ii) Write a program that the outer loop will run for n number of iterations.

In each iteration of the outer loop, inner loop will run for 3 iterations of

their own. The time complexity of the code is O(n3

) and the final

complexity will be n*n*n. (6 marks)

(iii) Based on the stack algorithm below, provide the output? Of the

inserted items and deleted items. (8 marks)

#include <iostream>

#include "Stack.h"

#include <iomanip>

#include <string>

using namespace std;

int main() {

int item = 0;

Stack s;

s.push(8);

s.push(16);

s.push(32);

s.push(43);

s.push(55);

s.push(68);

if (s.pop(item))

cout << "\nDeleted item : " << item;

if (s.pop(item))

cout << "\nDeleted item : " << item;

if (s.pop(item))

cout << "\nDeleted item : " << item;

if (s.pop(item))

cout << "\nDeleted item : " << item;

if (s.pop(item))

cout << "\nDeleted item : " << item;

if (s.pop(item))

cout << "\nDeleted item : " << item;

cout << endl;

system("pause");

return 0;

}

7

UCCD 1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

___________________________________________________________________________

This assessment paper consists of 4 questions on 8 printed pages.

Q2. (Continued)

(iv) Evaluate the following program and provide the queue elements. (5 marks)

[Total: 25 marks]

Q3. According to Wikipedia, a roundabout road junction is a type of

circular intersection or junction in which road traffic is permitted to flow in one

direction around a central island, and priority is typically given to traffic already in

the junction. For example, the grey car will yield to the black car in Figure 2 when the

grey car driver can see the black car inside the circle. In Figure 2, the arrows indicate

the directions of the traffic. It is assumed that the car speed is slow and uniform at the

junction.

#include "linkedQueue.h"

int main()

{

linkedQueue Type<int> queue;

int x, y;

queue.initializeQueue(NULL);

x = 4;

y = 5;

queue.addQueue(x);

queue.addQueue(y);

x = queue.front();

queue.deleteQueue(x);

queue.addQueue(x + 5);

queue.addQueue(16);

queue.addQueue(x);

queue.addQueue(y - 3);

cout << "Queue Elements: ";

while (!queue.isEmptyQueue())

{cout << queue.front() << " ";

queue.deleteQueue();}

cout << endl;

return 0;

}

8

UCCD 1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

___________________________________________________________________________

This assessment paper consists of 4 questions on 8 printed pages.

Q3. (Continued)

Figure 2. A roundabout road junction.

(a) Derive a suitable data structure capable to model traffic flow at a roundabout

road junction similar to that in Figure 2. Briefly explain the design on how it

can work. (10 marks)

(b) Based on the design from (a), provide a procedure or pseudo-code to simulate

traffic flow at the junction. Your answer should utilize the component names

from the data structure and be presented in bullet point format to specify what

to do in steps (1), (2), (3), … etc. The simulation would consider the following

scenario. At the start of every 10 seconds, an unknown number of cars arrive

at the junction. Each car will enter the circle according to the rule mentioned

above. Each car will have a specified exit for destination. (4 marks)

(c) Generalize the design from (a) and (b) to have the capability to simulate traffic

flow at a larger roundabout junction similar to that in Figure 3. The additional

rule is “cars at outer circle yield to cars in the inner circle”. For example, the

grey car will yield to the black car in Figure 3 when the black car is in front

and put on the signal to turn left to get to the outer circle. (11 marks)

Exit 1

Exit 2

Entrance 2

Entrance 1

Circle

9

UCCD 1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

___________________________________________________________________________

This assessment paper consists of 4 questions on 8 printed pages.

Q3.(c) (Continued)

Figure 3. A bigger roundabout road junction with two lanes.

[Total: 25 marks]

Q4. (a) Figure 4 shows a 15-node Binary Search Tree Traversals.

Figure 4: 15-node Binary Search Tree.

According to the BST in Figure 4, answer the following questions.

(i) Fill in the blanks and complete the In-order traversals of the binary

search tree. (4 marks)

__ __ 19 __ 32 __ 44 49 __ 71 72 __ 92 __ 99

10

UCCD 1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

___________________________________________________________________________

This assessment paper consists of 4 questions on 8 printed pages.

Q4.(a) (Continued)

(ii) Fill in the blanks and complete the Pre-order traversals of the binary

search tree. (4 marks)

49 __ __ 11 19 __ 32 __ 83 71 __ 72 __ 92 __

(iii) Fill in the blanks and complete the Post-order traversals of the binary

search tree. (4 marks)

11 __ 18 __ 44 __ __ 69 72 __ 92 99 __ 83 __

(b) Figure 5 shows an adjacency list representation of a directed graph where

there have no weights assigned to the edges. Provide the adjacency matrix for

the graph shown in Figure 5. (7 marks)

Figure 5: An adjacency list representation of a directed graph.

(c) Draw the Minimum Spanning Tree (MST) for the Graph A shown in Figure 6

using Prim’s algorithm. The starting vertex is V1. (6 marks)

Figure 6: Graph A

[Total: 25 marks]

_____________________________________________

11

UCCD 1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

___________________________________________________________________________

This assessment paper consists of 4 questions on 8 printed pages.

Appendix 1: Final Assessment Cover Page

(Remark: This must be placed as the FIRST PAGE of your Answer Script)

Answer Script

Main Final Assessment - Jan 2020 Trimester

UCCD1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

Degree Programme CN / CS / CT / IA

Exam Index Number:

Student Name:

Student ID:

Marks Awarded

Q1.

Q2.

Q3.

Q4.

Total:

Remark: Late Submission? _____

If Yes, Lateness: ______________

Marks after Deduction: ________

12

UCCD 1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVING

___________________________________________________________________________

This assessment paper consists of 4 questions on 8 printed pages.

Appendix 2: Final Assessment Declaration Statement

(Remark: This must be placed as the SECOND PAGE of your Answer Script)

Final Assessment Declaration Statement

DECLARATION

I, ___________________________________(Name), Student ID. ____________________

hereby solemnly and fully declare and confirm that during my programme of study at

Universiti Tunku Abdul Rahman, I shall abide and comply with all the rules, regulations and

lawful instructions of Universiti Tunku Abdul Rahman and endeavour at all times to uphold

the good name of the University.

I hereby declare that my submission for this Final Assessment is based on my original work,

not plagiarised from any source(s) except for citations and quotations which have been duly

acknowledged. I am fully aware that students who are suspected of violating this pledge are

liable to be referred to the Student Disciplinary Committee of the University.

Programme: ________________________________________

(Digital) Signature: ___________________________________

Student’s I.C. / Passport No:: ___________________________

Exam Index No: _____________________________________

Date of Submission: __________________________________