” UCCD 1024程序 写作、programme课程程序 辅导This assessment paper consists of 4 questions on 8 printed pagesJANUARY 2020 TRIMESTERMAIN FINAL ASSESMENTSATURDAY, 16 MAY 2020 TIME: 9.00 AM 4.00 PM (3 HOURS)BACHELOR OF COMPUTER SCIENCE (HONS)BACHELOR OF INFORMATION SYSTEMS (HONS)INFORMATION SYSTEMS ENGINEERINGBACHELOR OF INFORMATION TECHNOLOGY (HONS)COMMUNICATIONS AND NETWORKINGBACHELOR OF INFORMATION TECHNOLOGY (HONS)COMPUTER ENGINEERINGInstructions to Students:General1. This Final Assessment (FA) is an Individual, Open-Book assessment which consistsof FOUR (4) questions. Each question carries 25 marks.2. You are required to answer ALL questions, and submit the ANSWER SCRIPT by12:00pm, 16 MAY 2020.3. During the Reriod of 3 hours of this FA, the examiner(s) can be reached atYou may use the above e-platform(s) to check with the examiner(s) if you need anyclarification on this FA question paper4. You may refer to any books, lecture notes, published materials, online resources, etcwhen answering the questions. However, COPY-AND-PASTE, DISCUSSION, andSHARING OF ANSWERS are STRICTLY PROHIBITED during the FA.Answer Script File5. 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 SOLVING2UCCD 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 isA01234CBIBF, then your answer script should be named asUCCD1024_ FA_ IB_A01234CBIBF.docAnswer Script Submissionbefore the due time/date.UCCD 1024程序 写作、programme课程程序i. CN students please send your answer script to:Note: For the title of your email, please use the file name of your answerscript. That is,UCCD1024_FA_[Programme Abbreviation]_[Your Index Number]8. Please make sure that you submit the same copy of answer scripts to the aboveplatforms. If different answer Scripts are received, the examiner will just randomlychoose 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 shownbelow:pre:t to:.rand Scholarships (DEAS). You MUST name your answer script using the followingfile name for submission:[UCCD1024]_FA_[Programme Abbreviation]_[Your Index Number]3UCCD 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 deductionii. 1 hour lateness 3 hour: 20% mark deductioniii. 3 hour lateness 5 hours: 30% mark deductioniv. 5 hours lateness 7 hours: 40% mark deductionv. 7 hours lateness 9 hours: 50% mark deductionvi. Lateness 9 hours : 100% mark deductionContents of Answer Script10. The first page of your answer script is the cover page. You MUST use the templategiven in Appendix 1 and fill up the following information You Degree Programme (Abbreviation) Your Index Number Your Name Your Student ID11. The second page of your answer script is the Declaration Form. You MUST use thetemplate given in Appendix 2, and sign on this form to indicate your authenticity ofsubmitted work Without plagiarism.12. Each question should be answered starting on a new page. It is recommended that theanswer 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 characterswith 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 blankpaper, and then take pictures and include the pictures in the Word document as part ofyour answers.15. Please include a Page number on each and every page of your answer script.WARNING OF PLAGIARISM16. All answer scripts will be uploaded by the examiners to Turnitin for similaritycheck. In the case of plagiarism being suspected, the evidences will be submittedto the University Examination Disciplinary Committee for further investigationand trial. If found guilty, serious disciplinary action will be taken against thestudents.4UCCD 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 supportsinsertion of large and unknown number (N) of data records. The design shouldbe efficient with respect to memory usage and search with timing complexitiesof (1) best case as O(1), (2) worst case as O(log(N)), and (3) average case asO(log(N/c)) where c is a constant.(i) Provide a diagram of the proposed data structure design and label eachcomponent. 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 personcan have an unknown Number of staffs under his/her care. In Figure 1, only thetechnical manager branch has been expanded due to space restriction. Thecompany structure can be modeled by a tree where each parent node can havemultiple descendants.Figure 1. A simplified company structure tree.CEO AFinanceManager BTechnicalManager CHRManager DAdminManager ESeniorManager FAssistantManager GStaff H Staff I5UCCD 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 thecompany tree structure shown in Figure 1. (2 marks)(iii) Based on Q1(i), provide a method staffSupervisors(stringstaffName) to search for a staff name and then print all his/herimmediate Supervisor names. For example, if H is the inputparameter to staffSupervisors(), the names printed will be F,C and A with respect to Figure 1. Give C++ code or pseudo-code asyour answer. (6 marks)[Total: 25 marks]Q2. (a) Assume the following initializations:#include iostreamusing 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 rightbut it cannot add any newvariable or link into BTNode. In addition, no new definition ofstruct can be added too. Your answer should give the modifiedBTNode definition and brief explanation of the changes.给出下面的树定义，设计一个新的方案来表示a公司结构。新方案可以更改名称以及左和右的含义，但不能增加任何新的含义变量或链接到BTNode。此外，没有新的定义也可以添加struct。你的答案应该给修改BTNode的定义和变更的简要说明(i)Q1.(b) (Continued)6UCCD 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, youshould 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 oftheir own. The time complexity of the code is O(n3) and the finalcomplexity will be n*n*n. (6 marks)(iii) Based on the stack algorithm below, provide the output? Of theinserted items and deleted items. (8 marks)#include iostream#include Stack.h#include iomanip#include stringusing 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;}7UCCD 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 ofcircular intersection or junction in which road traffic is permitted to flow in onedirection around a central island, and priority is typically given to traffic already inthe junction. For example, the grey car will yield to the black car in Figure 2 when thegrey car Driver can see the black car inside the circle. In Figure 2, the arrows indicatethe directions of the traffic. It is assumed that the car speed is slow and uniform at thejunction.#include linkedQueue.hint main(){linkedQueue Typeint 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;}8UCCD 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 roundaboutroad junction similar to that in Figure 2. Briefly explain the design on how itcan work. (10 marks)(b) Based on the Design from (a), provide a procedure or pseudo-code to simulatetraffic flow at the junction. Your answer should utilize the component namesfrom the data structure and be presented in bullet point format to specify whatto do in steps (1), (2), (3), etc. The simulation would consider the followingscenario. At the start of every 10 seconds, an unknown number of cars arriveat the junction. Each car will enter the circle according to the rule mentionedabove. 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 trafficflow at a larger roundabout junction similar to that in Figure 3. The additionalrule is cars at outer circle yield to cars in the inner circle. For example, thegrey car will yield to The black car in Figure 3 when the black car is in frontand put on the signal to turn left to get to the outer circle. (11 marks)Exit 1Exit 2Entrance 2Entrance 1Circle9UCCD 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 binarysearch tree. (4 marks)__ __ 19 __ 32 __ 44 49 __ 71 72 __ 92 __ 9910UCCD 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 binarysearch tree. (4 marks)49 __ __ 11 19 __ 32 __ 83 71 __ 72 __ 92 __(iii) Fill in the blanks and complete the Post-order traversals of the binarysearch tree. (4 marks)11 __ 18 __ 44 __ __ 69 72 __ 92 99 __ 83 __(b) Figure 5 shows an adjacency list representation of a directed graph wherethere have no weights assigned to the edges. Provide the adjacency matrix forthe 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 6using Prims algorithm. The starting vertex is V1. (6 marks)Figure 6: Graph A[Total: 25 marks]_____________________________________________11UCCD 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 ScriptMain Final Assessment – Jan 2020 TrimesterUCCD1024 DATA STRUCTURE AND ALGORITHMIC PROBLEM SOLVINGDegree Programme CN / CS / CT / IAExam Index Number:Student Name:Student ID:Marks AwardedQ1.Q2.Q3.Q4.Total:Remark: Late Submission? _____If Yes, Lateness: ______________Marks after Deduction: ________12UCCD 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 StatementDECLARATIONI, ___________________________________(Name), Student ID. ____________________hereby solemnly and fully declare and confirm that during my programme of study atUniversiti Tunku Abdul Rahman, I shall abide and comply with all the rules, regulations andlawful instructions of Universiti Tunku Abdul Rahman and endeavour at all times to upholdthe 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 dulyacknowledged. I am fully aware that students who are suspected of violating this pledge areliable to be referred to the Student Disciplinary Committee of the University.Programme: ________________________________________(Digital) Signature: ___________________________________Students I.C. / Passport No:: ___________________________Exam Index No: _____________________________________Date of Submission: __________________________________如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
