r
vN1vERsr[i UNIVER. SITI TEKNWUI PETRONAS
i
i
R: A
N&'iUt;
COURSE
TBBIO6311CB1063 ALGORITHMS AND DATA STRUCTURES
DATE TIME
: :
13 SEPTEMBER 2011 (TUESDAY) 9.00 AM 12. D0 NOON (3 HOURS)
INSTRUCTIONS TO CANDIDATES
I. 2. 3. 4. Answer ALL questions from the Questions Booklet. Begin EACH answer on a new page in the Answer Booklet. Indicate clearly answers that are cancelled, if any. Where applicable, show clearly steps taken in arriving at the solutions and indicate ALL assumptions, 5. Do not open this Question Booklet until instructed. There are ELEVEN (11) pages in this Question Booklet including the
Note
cover page.
Universit
i.. Teknoloq
PETRONAS
TBB1 063I1CB1 063 I. and vector2 in FIGURE QIa are vector objects of the
Vector
vectorl
(ADT). Abstract Data Type
VectorInteger> Vector<Integer> vectorl vector2 = new = new Vector<Integer>(); Vectcr<lnteger>();
FIGURE QIa
a.
Explain the terms below.
I.
ADT
[2 marks]
IL
vector
[2 marks]
b.
Write the Java code which calls a predefined method of the Vector ADT to:
integer into index 0 of vectcri. add an [2 marks]
IL
the last item stored in vector2. emcarre
[3 marks]
iiL display the index where an integer 3 is stored in vectorl. [2 marks)
TBBI O631TCB1063 Write a new method named extend Vector be added to the which will
c.
ADT. The method receives a vector as its parameter, and
the vector object that calls the the vector's content to appends FIGURE QIb shows the result of a sample call to the method. method extend.
veotorl vector2 vectorl. extend
. '""'
13
(vector2)
1 vectorl
vector2
r-iij LIIi
12 32
10
12
FIGURE Q1b [4 marks]
d.
is a vector containing several objects of Score. for is an ADT that has four public components: a string Score The first vector is three parallel vectors. storing course code and IDs, the second is for student marks and for storing student used Suppose vector3 the third is for student grades. Draw with sample data how acell of vector3 look like. will [3 marks}
i.
II.
Code how the method extend
(c) is caked to of part
to vectors. the content of vector student marks append [2 marks]
TBB1 063/TCBI 063 2. The ADT for a singly linked list node is defined as in FIGURE Q2a.
{ ListNode class public mnt data; public ListNode public next; )
FIGURE Q2a
Trace the code segment in FIGURE Q2b which creates a singly linked list of Lis tod. e. Draw the list, including the external insertion of each node. pointers, after
ListNodo (mnt for ListNodo aNode aNoae data next curr = null; = null, i<::: 5; j++){ (); ListNode aNode = new =i; = null;
aw
aList 1=1;
if
C else
(aList
aList
== null)
= aNode; CurT = No e; ?
i. f { else
of == aNode, next = aList; } aList - aNode; (1 %2
ourr. eurr
next = aNode; } = aNode;
FIGURE Q2b [5 marks]
b.
With an assumption that a (inked list of Li stNode
by pointed
has at least 3 nodes, write an algorithm that deletes its aLl s t: middle node. [NOTE: If the number of nodes is even, both middles will be deleted. ] [5 marks] 4
TBB1 063I1CB1 063
c.
Rewrite the code in FIGURE Q2a so that it defines an ADT for e doubly linked list node.
[2 marks]
d. Rewrite the code in FIGURE Q2b so that it creates a doubly linked list of similar sequence data items. [4 marks] a State ONE (1) advantage and ONE (1) disadvantage of choosing a doubly linked list over a singly linked list in a program. [4 marks]
TBB1 063I1CB1 063 3. Given the following infix expression:
(4+3) * (6* 12 }}}
a.
Write an algorithm for converting the infix expression above to its postfix equivalent using suck. [6 marks]
b.
Give the posthx notation of the above infix expression.
[3 marks] Suppose an infix expression is stored in a queue as shown in FIGURE Q3a beiow
C.
FIGURE Q3a
I.
State the data type of the queue elements in FIGURE Q3a.
[1 mark] Show the resulting content of the queue and/or stete the (whichever applicable) after the execution output produced line of the codes in FIGURE Q3b. of each
deleteQueue C); (queue (queue (queue ln (queue . . front . front ())r { )} (} u3'); +
ii.
queue . System out println . . insertQueue queue . System. system: out . println out . print
deleteQueue ()
rear .
FIGURE Q3b [5 marks]
IBBI 063ITCBI 063 iii. Complete the function in FIGURE Q3c.
public
static
void
leaveoperatorOnly (Queue<... > queue)
{ //this
function
removes
operators
all
(+
data
-
other *) from
than queue .
//mathematical ... ...
FIGURE
Q3c
[5 marks]
063 TBB1 D63i1`CB1 4. a. State with explanation the running time complexity in Big-O notation for each of the program excerpts below. Assume the value for n is during runtime. entered
i_
it-it for for
I (i=O;
j; i<5; j<i; i++) j++) intln pr, . (n) ;
(j=O; Systemout
[3 marks]
I1. Ir M jilt r 11 . :
for for
(i=0; (j-O;
System.
1<n; j<n;
aut i<n; out.
i++) J++)
(n)
prirat1n . z++) println
for
(i=O; Syem.
(i );
[3 marks] FIGURE Q4 shows two lists of numbers, lis tA and li, s tB which to be combined into an ascending order single list. are
b,
FIGURE Q4
L Provide step by step explanation of how insertion sort is applied to sort 1i stB into ascending order. method
[4 marks]
..
II.
Suggest how 1is to and the sorted 1is tB in part (b)(i) can be merged to give a complete, sorted set of numbers.
[4 marks]
C81 063 1"BB10631"f c. A hash function is needed in order to calculate the address at which data sto be stored in a hash table of size I oo. certain Given TABLE Q4, determine the method used (i.e., folding, or modular arithmetic) by hash functions A, B mid-square c based on the data and the address they hashed to. and TABLE Q4
Hash
Data Hash Function 11211 13745 16600 4 49 36 A
Address
Hash Function 33 92 76
Hash Function
ll 45 0
[6 marks]
tiJ
T'BBI 063fTCBI 063 5. Given the following list of integers:
53 12 986 10 7
a,
Insert the integers into a Binary Search Tree (BST) according to the they are given. order [4 marks]
b.
Transform the BST in part (a) into an AVL tree by showing the tree after each rotation performed. resulting [6 marks] Using the BST of FIGURE Q5a, state:
C.
FIGURE Q5a
the node that will replace the node containing 10 if deleted. [1 mark]
IL
the height of the treer [1 mark]
iL
the level of node containing 5.
11mark]
10
TBBI 053fTCB1053 iv. the node which is the sibling of node containing 18. [1 mark] the sequence of the nodes if traversed in post order. [2 marks] d. Trace and give the value returned by the recursive function in FIGURE Q5b using the BST in FIGURE Q5a as the initial parameter.
int null) 0; (root. left! =null left) =null) && root. Q5d(root. + right! right); =null) Q5d (BST {
V.
public if
static (root return
root)
else
if
return else if
Q5d(root. (root. left!
return else if
root. (root.
root.
data right!
data
Q5d(root. + =null)
Q5d(root. +
left);
return else return
right);
0;
}
FIGURE Q5b [4 marks]
OF PAPER-END
11
