联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codehelp

您当前位置:首页 >> OS程序OS程序

日期:2020-10-03 09:45

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
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.给出下面的树定义,设计一个新的方案来表示a
公司结构。新方案可以更改名称
以及“左”和“右”的含义,但不能增加任何新的含义
变量或链接到BTNode。此外,没有新的定义
也可以添加struct。你的答案应该给修改
BTNode的定义和变更的简要说明
(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
#include "Stack.h"
#include
#include
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 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: __________________________________

版权所有:留学生编程辅导网 2021,All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。