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)



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'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



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



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



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



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/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



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



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



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



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

pass year 1 dsa

Documents