CONFIOENTIAL cD/JUL 2025/CSC508/51 8
UNIVERSITI TEKNOLOGI MARA
FINAL EXAMINATION
COURSE DATA STRUCTURES/ DATA STRUCTURE AND
ALGORITHM ANALYSIS
COURSE CODE csc508/518
EXAMINATION JULY 2025
TIME 3 HOURS
INSTRUCTIO NS TO CAN DIDATES
1 This question paper consists of five (5) questions.
2 Answer ALL questions in the Answer Booklet. Start each answer on a new page
3 Do not bring any material into the examination room unless permission is given by the
invigilator.
4 Please check to make sure that this examination pack consists of:
i) the Question Paper
ii) an Answer Booklet - provided by the Faculty
5 Answer ALL questions in English.
DO NOT TURN THIS PAGE UNTIL YOU ARE TOLD TO DO SO
This examination paper consists of 7 pinted pages
O Hak cipta Unive6iti Teknologi MARA CONFIDENTIAL
CONFIDENTIAL 2 cD/JUL 2025/CSC508/51 8
QUESTION I
a) lmagine a system designed to catalog and manage historical artifacts from museums
around the world. Artifacts can range from ancient tools and manuscripts to sculptures
and s. Given the followi Abstract Data ES S
public class Artifact {
private String artifactlDr/* Unique identifier for the
artifact */
private String name; // Name of the artifact
private String origin; // [Link] or region of origin
private int age; / / ege of the artifact in years
prj-vate String categoryi /* Category of the artifact
(e.9,, Sculpture, l'lanuscript,
Tool ) */
private String currentMuseum; / / Artifacts current location
private char condition; /* Condition of the artifact:
'Er (ExceIlent),
*7
'Gr (cood),
'P' ( Poorl
[Link] getArtifactlD ( ) {...
publ i c }
public Strj-ng getName O t...)
string qetorigino {...}
publ i c
publ icint getage O i...)
public string getcategoryO {.. .}
public String getcurrentMuseum ( ) {. .. )
publi c char getconditionO {...}
)
public class Arti factArrayList {
pubtic ArtifactArrayList O {...}
public void add (Artifact artifact) { . . . }
public inr size O i. . . )
public Artifact get (int index) { . . . }
public void remove (int index) {. . . }
public int countoldManuscript (ArtifactArraylist) )
// Ot-het relevant methods
)
public class Artifactlinkedlist {
public Artifactlinkedlist O {...}
public void add(Artifact artifact) i.. .)// \dd at the end
public Altifact get (int index) { . . . }
public int size O {. . . }
public Artifact removeE romFront O {...}
public void displayO {...}// oisptay current noders dara
public Artifact getFirst O {. . . }
pubLic Artifact getNext O {. . . }
public void excel-lents culptures (Artifactfinkedfist ) {. .. }
/ / o|.het relevant methods
)
O Hak Cipta Universiti Teknologi MARA CONFIDENTIAL
CONFIDENTIAL 3 cD/JUL 2025/CSC508/518
An object of Art i factArrayli s t named artifactAl, is created and populated with
35 artifacts information. An object of Arti factlinkedLi s t, artifactLL, is created
and populated with 40 artifacts information
i) Create and initialize two attributes in the Artifactlinkedlist class that are
relevant to manage a linked list.
(2 marks)
ii) Define the method countoldManuscript O in Arti factArrayli st that
receives artifactAl as a parameter to calculate and return the total number of
artifacts in the artifactAl that are categorized as'Manuscripts" and are over 500
years old.
(3 marks)
iii) Define a method exce l l- ents cutpture s O in Artifactlinkedlj-st that
receives artifactI-], as parameter and display names and origins of artifacts in
the artifactLL that are in excellent condition and belongs to the "Sculpture"
category.
(4 marks)
iv) Declare a new Arrifacrrinkedlist object named anci entArt i facts. write
the code to remove all artifacts from the "Tool' category in the in artif act],], and
add them to anci entArt i facts. Then, display all artifacts stored in
anci entArti facts '
(6 marks)
v) write a sorting method to anange all artifacts in the Artj. factArrayli st by their
age, in descending order.
(6 marks)
b) Specify the modification needed on a singly linked list to make it a circular linked list, and
describe one practical use case for a circular linked list in computing.
(4 marks)
QUESTION 2
a) stacks and queues are linear data structures that differ in the way elements are being
inserted and removed.
i) Assume an empty stack, mystack, and an empty queue, yourQueue' Determine
the content ofmystack and yourQueue after the following code segment executed.
O Hak Cipta Universiti Teknologi MARA CONFIDENTIAL
CONFIOENTIAL 4 cD/JUL 2025/CSC508/518
mystack. push ( "Perodua" ) ;
mystack. push ( "Proton" ) ;
mystack. push ( "Honda" ) ;
mystack. push ( "Toyota" ) ;
youroueue , enqueue ( "BYD" ) ;
youroueue. enqueue ("NETA") ;
yourQueue. enqueue ( "XPENG" ) ,
youroueue. enqueue ([Link] ( ) ) ;
yourQueue. enqueue ([Link] O ) ,
mystack. push ( yourQueue . dequeue ( ) ) ;
mystack. push (youroueue. dequeue O ) ;
(5 marks)
ii) Evaluate the following equation using stack. Show the content of the stack at every
slep. Given A= 6, B = 2, C =3, D = 9, E = 8.
D+C
A+B*C
E
(5 marks)
b) Write the definition forthe method toralrnput (int inp) that uses recursion to sum
all individual integers of a given input inp.
Example:
inp operation result
't2345 1+2+3+4+5 15
3647 3+5+4+7 20
Trace the method, given inp = 8385.
(5 marks)
@ Hak Cipta Universiti Teknologi MARA CONFIDENTIAL
CONFIDENTIAL 5 co/JUL 202s/CSC508/518
QUESTION 3
a) Tree 1, as shown in Figure 1; visualizes a Binary Search Tree (BST)
Figure 1: Tree 1
i) Determine the output after the following program is executed on Tree 1.
public void print ( ) {
printRef ( root ),
)
private void printRef ( TreeNode node ) t
if ( node == nuII )
return;
[Link] ( [Link] + "'r );
printRef ([Link] );
printRef ( node. right ),
)
Then, identify the order of traversal
(3 marks)
ii) Write the code to insert a new node into the BST, given the node ADT as follows:
class TreeNode {
int data;
TreeNode 1e ft;
TreeNode right;
)
(5 marks)
@ Hak cipta Universitl Teknologi MARA CONFIDENTIAL
CONFIDENTIAL 6 cD/JUL 2025/CSC508/51 8
iii) Drawthe updated binary search tree (BST) after removing nodes 45 and 69 from Tree
1 in sequence and then inserting node 37.
(5 marks)
b) Construct the AVL tree if the following data are added in sequence.
ABC, DEF, GHt, JKL, MNO, pQR, STU, \rVl/X
(7 marks)
OUESTION 4
a) Sort the following array:
2a o 3'l 29 4 47 15
i) in ASCENDING order using merge sort. Show your step.
(5 marks)
ii) in DESGENDING order using heap sort. Show the first two heaps
(5 marks)
b) Binary search, linear search, and hashing are all fundamental techniques used in
computer science to search for elements in a collection of data, but they differ in terms
of efficiency and use cases.
i) Using the following information, explain the difference between linear search and
binary search.
Data : 14 17 JZ EE 82
Search key : 57
(5 marks)
ii) The data series: 28, 134, 93, 212, 45, are to be stored in a hash table of eight buckets.
Use mod method as hash function and solve the collision using quadratic probing.
Show the content of the hash table.
(5 marks)
@ Hak Cipta Universiti Teknologi MARA CONFIDENTIAL
CONFIDENTIAL 7 co/JUL 2025/CSCs08/s18
QUESTION 5
a) A directed graph fl = {V, E}, has a set of vertices V = {0, 1, 2, 3, 4, 5}.
i) The adjacency and weight of the vertices are defined as follows:
Vertex Adjacent vertices Weights
0 (1,2) (0.5, 6)
I (0, 3,4) (0.5,4, 1.5)
2 (0,1,3) (6,3,1)
(1,2,4,5) (4 1
2 1)
4 (1, 3, 5) (1.5,3,1.5)
q (1.4) (0.s, 1.5)
Visualize graph A
(6 marks)
ii) Find the shortest path from vertex 2 to all the other vertices.
(8 marks)
b) A logistics company wants to optimize delivery routes between six districts in Kuala
Lumpur: Ampang, Bangsar, Cheras, Sentul, Gombak, and Setapak. The roads
connecting these districts form a weighted undirecled graph, where the edge weights
represent travel costs in kilometers. Using the adjacency matrix below, determine the
Minimal Spanning Tree (MST), using Kruskal's Algorithm, to identify the leaslcost
connections between districts.
Ampang Bangsar Cheras Sentul Gombak Setapak
Ampang lt
Bangsar 21 17 40
Cheras 17 29 43
Sentul 40 ,o 24 ct
43 '19
Gombak
Setapak JI 19
(6 marks)
END OF QUESTION PAPER
@ Hak Cipta Universiti Teknologl iIARA CONFIDENTIAL