Download - pass year 1 DSA
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 1/12
-
-F
7
7
i-
No. Matrik
(Ma,tric
No.)
Semester/Sesi(Senzesl
er
/
Se
s
si,or)
Tarikh
(Date)
Masa
(Ti,nt.e)
Ternpat
(Ventte)
Jangka masa
(Du'ati,on)
Pensyarah
(Lecil
tl'er)
21
20L3
01 April2013
2.30-4.30
p.m
Delirna,
DeTAR
2
jam
(hours)
Dr.
Cheah Wai
Shiang/
Dr
Azrnan
b Bujang
Masli
I(ertas
peperiksaan
ini
mengandungi
sebelas
terrnastili
halauran irr-rlit).
Tlt"is
exa,nt.in.o,ti.on
pa.per
coruslsls
of
eleuen
(11)
pq,ge).
SULIT
UI{I\18
RSITI
MALAYSIA
SARAWAK
94300
Kota
Samal'ahan
Sarawak
Fakulti
Sains
Komputer
&
Teknologi
Maklumat
TMC
1433/TMC
1434
TMC
1433/
TMC
1434
Data
Structure
and
Algorithm
Peperiksaan
Pertengahan
I
(MIDTERM
EXAM
I)
Arahan
lrlnstnt.ction)
1
Jawab SEiVIUA soalan.
(An.st',er
ALL
qtr
est
ion
s).
2 Baca
soalan dengan
teliti
sebelum
menjawab.
(Read
tl'te
qu,estions
co,refu,lly
before
o.nstuering
th,ent).
3 ?'.rlis
jawapan
anda
pada
kertas
jawapan
yang
disediaka;:i
menggunakan daRwat
sahaja.
(Wt'ite
yotlt'
e.rLstuet's
irr, truh
only).
4
Dil"lrang
bercakap
atan mengganggu
calon-calon
dalam
janglia
masa
pel,leriksaan.
(Do
not
,,o.lh
or
d,istu,rb ath.et'
cancl,id,o,tes
clu,ring
tl-te
exo,ntiruation).
5 Calon tidal<
dibenarlian
meninggalkan
biliir
peperiksaan
dalam ternpoh
30
mimt
pertama
dan
15
minit
teralihir
peperihsaau.
(Ca,n,ci.i.cla.tes
ate
not
o.ll,owet
to
l.ea,ue
th,e exq,nirLa.tion.
lwLl
d.u;'in,g
th,e
first
30
ninutes
o.rud
tlrc
la.st 15 nr.intt.tes
of
th,e
exanti,nct.tion).
6
Calon dil<ehendaiii
ni.'matuhi
ETIKA
AKADEMiI{
seperti
yang
tertera dalam
perkara
12
Peraturan Akadernik
ljazah
Sarjana Muda, UNIMAS.
Candidates
are required
to
contply with
ihe Etika Ahadenik
as stated in Clause
12
of
Pe
ra t
u
ra n,4li
a d
e
ntik Ij
a
za h
Sa tj
a
n
a l[u
da,
L\NIMAS.
(11)
halarnau
bercetak
(tidak
printed page (exch,d,ing
the
couer
Unit
Peperiksaan
Bahagian Pengajian
Prasiswazah
(BPPs)
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 2/12
Seciion
A
:
Instruction:
7'/,.'l
C I
1
3 3
iThl
C'
I
4 3 4 Dd
tu
s [t. Lt c
t Lte
u ntl A
lgor
i th
nr
MCQ
Question
[80
marks]
Answer
ALL
Questions
,,.{t
(i'
.'(
n
an
assigtrment
statelneut
a:tr;
Which
of'the
tbllowing
statement
is
TRUE?
a. The
variable
a arrcl
the
variable
b are
equal.
'-
Etl'r"
value
of
b
is
assigned
to
variable
aburt
the
later
ch4nges
on
variable
b will
lot
effbct
the
value
of
var.iable
a
',,/
c.
The
value
of
b
is
assigrred
to variable
a
ancl
the
later
cl-ranges
on
variable
b will
etl-ect
the value
of variable
a
I
d. The
value
of
variable
a
is
assigr-recl
to
variable
b
ancl
the
value
of
variable
b
is
assigtred
to
variable
a.
X
/)
(
7.
AII
of the
tbllowing
are
valicl
expressions
in
C++
I
;
a:2+(b:5);
I
l,
=tr:c:5;
I
la:ll%3
I
$r'*
,tf
False
$
wnicn
of
the
fbllowing
statenrcnt
is
true
regarding
cin
statement?
;14
Lnl
statenrent
must
currtain
a
variable
prececled
by
>>
operator
./
,J
b.
ci.
does
not
Proccss
the
inpyt-qrtir
user
presses
RETURN
keyx
('
c.
yoLl
can
usc
rnclre
than
onq(atuu\
input
fi.om
user
by
using
ciir
d.
all
of
above
\-
/.
st"ay
the
tbllowi,g
piece
of
cocle
ancr
crroose
the
BEST
answer.
int
x:5,
y:-1
,
z;
a:addition(x,y)
.--a:The
tunction
addition
is
called
by
passing
the
values
b. The
fr-urction
addition
is
callecl
by
passing
ret-erence
Qr
lrr
casrr of
arguments
passed
by
values
when
calling
a
fu1ctio1such
as
z:addidion(x,y),
a.Any
rnoditications
to
the variables
x
&
y
t}om insicle
thc
function
will
,ot
have
any
eflbct
outside
the
function.
b'The
variables
x
and
y
will
be
upclated
'uvhen
any
mocliflcatiol
is
done
i1
tl"le
fu,ction
*ff\"rc
variables
x
ancl
y
are
passed
to
trre
functicln
aclditio,
,
d.None
of
above
are
valid.
Page
I
of
1l
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 3/12
7'M
C
I
4 3 3
iTM
C I
4 3 4
D u
rit,r m
c
nr
re,
n n
d,4
lgo r i
t
h
nr
@
Ou.rtoucled functions
are
a.Very
long
functions that
can
hardly run
b.
One
function containing
another
one
or
more
functions
inside it.
gfwo
or
more
functions
with
the
same name
but
different number of
parameters
or type,
d. None
of
above
/{n**rine
the
following
program
ancl detennine
the
output.
#include
<iostream>
using namespace
std;
int
operate
(int
a,
int
b)
1EL
trtum
(a
*
b);
)
float
operate
(float
a,
floa{})
{
5:
return
(a/b);
int x=5,
52;
float
n:5.0,m:2.0;
cout
<<
operate(x,y)
<<"\t";
to
1fi
cout
(<
operate
(n,m);
return
0;
)
a.10.0
5.0
b.5.0 2.5
c.10.0
5
d.ta
2.s
,ffiind
out the error
in
following
block
of
code.
lrqx$rooi
Cout
<<
"x
is
100";
a.100
should
be enclosed
in quotations
-p
b.There
is no
semicolon at
the end
of first
line
y
-e.:Equals
to operator
mistake
d.Variable
x
should not
be inside
quotation
y
)
int
mainQ
t
/?ge2olll
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 4/12
Code
-l:
switch
(x)
{
case
1:
cout
<("x
is
1";
break;
case
2:
TlVl
C I
4
3
3
/Tlvl
C I
4
3 4 Du
tcr
s
tt.
u c
tu re
a
ntl
A
lgo
rit
h m
fiConsider
the
fbllowing
two
pieces
of
codes
and
choose
the
best
answer.
cout
<<"x
is 2";
break;
default:
cout
(("value
of
x
unknown',;
)
r*Eoth
of
the
above
code
fi'agrnents
have
tlie
same
behaviour
b.Both
of
the
above
code
fragrnents
produce
different effects,,
c.The
first
code produces
more
results
than
second
*
d.The
second
code produces
more
results
than
first.
p
10.
Tlie
"retum
0;"
statement
in
main
function
indicates
program
did nothing;
cornpleted
0 tasks
A.rnserting
into
an
anay
may
require
shifting many
other
elements.
b.Anays
cannot
be
sortedsp
c.Not
all
elements
in an
affay
can
be accessed.*
B"'fhe
program
worked
as expected
without
any
erroe
during
its
execution
r
gNot
to end
the
program
yet.
)d
',*'\
oo\
.,r, oinYt
,'d.None
of above
,.J
''
,_,^Lorkof,*1t''
u{
, . r-
--,-t
.,.-l\-,*1,:',"
-^?
l.
t
On
which principle
doesFac[-lwork?
g*r"\";;;'" d
t_l
y\rL_g
/F
\
^.r
B\
G^
l
ii[3]
/,il'ln,'n'1'Si
tr\
v
d.
Both
a and
c
above
lLt--')
gn(\\''
@V/nia'tof
tlie
tbllowing
is
a
dEgd:rul&&
of
using
an
qSQr
versus
using
a
linked
list?
e2
If
(x::1)
Cout
<<"x
is
)
Else
if
(x:=2){
Cout
<<
"x
Page
3 of ll
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 5/12
TM
C
I 4 3
i/I'ivl
C
I
4
i 4 Da
tu
.t trlt
ctu
r(
u
nd,1 lgori t
lr nt
.d.Declaring
an affay is
a
cumbersome programming
task.
(->
l@.'
Wrich
of
the
following
is ar-r.advantage
otusing
an_qlray
versus using
a
linkeci
list?
a.Arrays
are
always
sofied.e
b.Arrays
support
more data
types)
c.Array
indices
staft
at
zero.
y'.Accessing
an
arbitraly
element
in
an aray is
taster.
"/
)4.
push
and
pop
are
operations
aff-ecting
whicli end
of
a
stack?
a.The bottom.
b.The front.
4lhe top.
d.The back.
)6A
class template
in
C+*
has
the
following
structure
ternplate
<class
T>
class
TerrplatedClass
{
i;
What is
the meaning
of T in
the above
declaration?
a.It
is
a
placeholder
for
a
pointer
value
-4.It
is
a
placeholder
for
a
type name
c.It is
a
string
variable
\r
d.lt
rnust
be an integer
constant)
6d
*"there
any dvnamic
lnemory
management
en'ors
in
tlre
fbllowing
cocle?
\-/
int
*p:
new
int;
int
*q:
new
int;
int
*r;
xP:
17;
r:q;
*q:42;
,
p: q;
l=
hr
deleG
r;
a.No, there
are no
emors
b.Yes,
a memory
leak
c.Yes, misuse
of
a
dagglinggointer
,{nes,
both a
memory
leak
and
misuse
of a
dangling
pointer
Page4al'll
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 6/12
TM
C
I
4 3
3
/TM
C
I 4 3
4
Da
to
s t
r
uc tlr
re
a
nd
A
lgo
ri
t
h
nr
(q
Suppose
we
have
the
fbllowing
class
whose
underlying
data
structure
is
a
linked
IISt OI
ListNodes.
class
List
{
public:
ll other
public
tbnctions
-List0;
private:
struct
ListNode
{
int
item;
ListNode
*next;
);
ListNode
*head;
\'
t,
Mrich
of
the
fbllowing
sequences
of
code
could
be
conectly
delete
all
of the nodes
in
the
list?
used
in
the
destructor
-ListQ
to
I.
fbr
(ListNode
*n:
head;
head
=
NULL;
head:
n)
{
n
=
head->next;
delete
head;
)
II.
for
(ListNode
*n
:
head;
n
= NULL;
n->next)
delete
n;
l
IIl,
ListNode*
n;
while
(head
:
NULL)
{
n
=
head->next;
delete
head;
head
:
n;
)
a.I
and
II
only
b.ll
and
III
only
$
and
III
only
l{il
only
w
r*
$2
b
€
/
e
\LE.
Suppose you
were
implernenting
a data
structure
to store
rn&uaatrou
about
the
paintings
on
displM
an art
dealer's
showroom.
Of
the
following
data
structures,
which
one is
the
right
one
to
use?
a.Unordered
array
,6.Sorted
array
c.Linked
list
$It
depends
Oolt
''
ftrkr
6V
Page
5 of
11
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 7/12
TM
C
1
4
3 3/TM
C
I
4 3
4 Du
ta
.s
t nt( tu
t
e o nd,1 lgorith
nt
L{mlecture
we
clefined
a
class
IntStack to implernent
a
stack
of
integers:
class
IntStack
{
public:
IntStack(
);
bool
isErnpty( );
void
push(int
item);
int
pop(
);
int
top(
);
)
What happens if
we execute the
following
staternents?
IntStack
s;
int
nl, n2,n3'
s.push(17);
s.push(la3);
4
s.push(42);
'r,r'
nl
:
s.pop(
);
t
LL
)
n2:
s.top(
);
i?
s.push(n1);
n3
=
s.pop(
);
ni
=
s.top(
);
a.Stack
contains 143
(top),
I
7
(bottorn)
;
n7:42,
n2:42, tt3=42
b.Stack
contains
42
(top),42,
143,17
(bottorn);
n1=42, n2:42;
n3:42
c.Stack is empty; n7:17,
n2:143,
n3:42
ltStack
contains
143
(top),
l7
(bottom);
nl=[43, n2:143,n3:42
\dV*u"of
the
first linked list index
is
a.One
--Merc
c.-1
d.None
of these
@Olinked
list index is
-
that represents
the
position
of
a
node
in'a
linkecl list.
-y'An
Integer
b.A
variable
c.A
character
d.A boolean
fonn
of access
is used
to
add-and
rerrove
nodes
fiom a
stack.
\\
\.
rr '-.q,
.
(hL
,,1
'.
-q
\
'
5\.
-a'f
'
t'\
--
'
t
z'
-{LIFo
b.FIFO
c.Both l and2
d.None
of
these
.-l
i 0
L \"0
Page6ot'll
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 8/12
7/e
TA,l
C
I
1
3 3 /TM
C I 4
-l
4 Do
tq s t,"Lt
c
tu
re
d
nd
A lgo
r i th
m
is
a
data
structure
that
organizes
data
similar
to
a line in
the
'supennarket,
where
the
tlrst
one
in line
is
the
first one
out.
/pue,aelinked
list
b.Stacks
linked
list
c.Both
of
thern
d.Neither
of
thern
Ftf
o
W
r"
an
anay
queue,
data
is
stored
in
an
a.Node
b.Linked
list
,d,+ouy
d.Constnrctor
5'
A\
t\)
.iY
1y
(
-,.-\
G
7{fttepop0
mernber
function
detennines
if
the stack
is
empty
by
callilg
the
member function.
a.rernoveback$
-{f.isEmpty$
c.rernovedfiontQ
d.hasNext0
@
Wtrat
happens
when
you
push
a new
node
onto
a
stack?
df"r.
new
node
is
placed
at the ti-ont
of
the
linked
list.
affihe
new
node
is
placed
at the
back
of
the
linked list.
c.The
new
node
is
placed
at
the rniddle
of tlie
linked
list.
d.No
Changes
happens
@.What
is Data
Structure
?
,{r,/ay
to
qrganize
data
b.Accessing
of data elements
in
c. Orgarrization
of rnathernati
cal
S[11
of Above
@.
Vni"h
operation
is
not possible on Data Structure
?
a.Traversing
b.lnseftion"
-gReading
d.Deletion',
Q;
fne
value
of
flrst
linkecl
list
acldress
is ?
{0
b.-r
c.1
l,
\
li\
,# \{f
^]rJ
&\
\V .\*
g,\J"
.#
A
a^\}'-\-
\j-\
elernenl
,uy;u,
l-[*,.
U
specitied
maru1er
and
logical
concepts
PageT
ofll
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 9/12
T
"l C I
4
3 3
iT
A,l
C I
4 3
I D
a
tu
.s
t
n
t
c tr u'e u nd .1
I
go
r i
t
h nt
f,dtro,-,"
of Above
$lwo
dimensional
arrays are
also called
?
a.Matrix
Array
[
]r:
't
b,Table
Array
-rBoth
a
and
b
d.None
of
the
Above
fuf.ft
"situation
in linked
list
START:NULL
is callecl ?
a.Overflow
-"#Underflow
c.Both
of
above
d.None
of
Above
;{lUetenns
PUSH
and POP
are
related
to ?
a.Arrays
y'.Stacks
c.Linked List
d.None
{ln
the software
development process,
the
'impoftant
step.
a.Design
phase
is
the
firqt and most
tq
I
b.Implernentation
,zAnalysis
d.Testing
and debugging
@r*"or
False:
In
object-oriented
design
(OOD),
the frrst
step in
the
problem-
solving
process
is to
identify the
components.
)Y.True
b.False
;t{ru"C++
member
access
operator is the
,-{Dot,.
(period)
b.Two
semicolons,
::
c.The equal
sign,
:
d.The
plus
sign,
+
a{
l*"or
False:
A
pointer
variable
is
a
variable
whose
content
is
a memory
adclress.
*Trae
b.False
G.
f*"
or
False:
An asterisk
(x)
is
the unary clirection
or ret'erencing
operator.
Page
ti
of
I
I
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 10/12
Til'lC
I
4 3
-t/Tl,lC
I 4
-l
1 Du
tu s tt.u(.ntt.e
d
nd
A
lgot.i
th
nl
,
a.True
b.False
)8.In
a
linked
list,
every
rrode
(except
the
last
node)
contains
the
of
the next
-
node.
a.Data
b.Url
c.
Answer
-
diAcldress
39.
Deletion
of
an
itern
ti'om
a
linked
list
requires
--
of
the linkecl
list.
a,insert
b.isEmpty
c.travelsal
dremove
4O. Deleting
an
item
fior-n
a linked
list is
best
when
pelfbnlecl
with
--
pointer-(s)
so
that
the
deleted
node
can
be
fieed
from
memory.
-alOne
b.Two
c.Three
d.Four
End
of
section
A
Page9ofll
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 11/12
Section B
:
Instruction:
TM
C
I
4
3
3
/Tl,l
C'
I
4 3
4
D
a
ta,y
t
r u c
tu re
u
nd
A lgo
ri t h
rn
Long
Question
[20
marks]
Answer
ALL
Questions
l.
Consider the
List
class
with
the
following
private
members:
class List{
/*
public
members
here
...
*/
private:
struct
Node{
ListDataType
item;
l/ the
data
of
the
node
Node*
next;
llpoints to the
next node
of
the
list
\.
t)
Node*
head;
llpoint
to first
node
in
the
list
I.
))
Consider
the
linked
list of
ints
represented
by
the
tbllowing
diagrarn:
[TTI-----
|
r2l-l
---.
[__il]
|NULL
I
a.Draw a
diagram
of
the
above
list
after the
following
lines
of code have
been
..
executed:
(5
marks)
o"tilNode*
prev:
head->next;
"
fg:
:NoA.*
nodeTolnsert
=
new Node;
nodeTolnsert->itern
=
4;
nodeTo Insert-@
:
prev->next;
prev->next:
nHdTolnsert;
,
Answer:
b.Assume
that the
code
represented
above
in
part (a)
has
executed.
(3
marks)
What is
the value
of
prev->item?
Answer
Page
l0 of I I
7/25/2019 pass year 1 DSA
http://slidepdf.com/reader/full/pass-year-1-dsa 12/12
TM
C I 4 3 3
/7"M
C I
4
3 4 Do
ta s tt
"u
c
at
re
o
nd
.4
lgori
th m
(c)
hi
addition to
the
code
above,
assume
the
following
code
executes.
(5
marks)
Draw
a
diagrarn
of the
list
after
this
code executes
as well.
prev
=
prev->next;
prev
=
prev->next;
Node*
cun'
:
prev->next;
prev->next
:
curr-)next;
delete
curr;
curr:
NULL;
d)
Write
a
code
to
insert
a
node
at
the
end
of
a linked
list.
(7%)
Notes:
You
should
use
the
node
declaration
at
part
a.
Answer:
Answer:
l\2el
ww*
@
Node
*nodelolastl,l
=
nw
Nodei
xol,ilo\neo{
+
ta1+
nu+
?
fiodolol4guv(
+
/o
ul
-
rwilolol:taot{
End
of
section B
Page
ll
of
ll