=========================preview======================
(COMP251)COMP251_03F-final.pdf
Back to COMP251 Login to download
======================================================
COMP251:2003FallSemesterFinalExam

Date Friday,Dec12,2003
Time 4:30-7:00pm
Instructions: (a)Thisexamhas10questions.
(b)AttemptALLquestions.
(c)WriteALLanswersinthegivenbluebook.
(d)Thetotalmarkis100.

1

Problem1(8pts)Giveabrief(threesentencesmaximum)descriptionofeachofthefollowing programmingparadigm:
(a)Imperativeprogramming.
(b)Object-orientedprogramming.
(c)Functionalprogramming.
(d)Logicprogramming.

Problem2(10pts)Considerthefollowinggrammar:
.S.::.ab|a.S.b|.S..S.
(a)Showthatthisgrammarisambiguous.
(b)Rewriteitintoanunambiguousgrammar.
Problem3(5pts)Explainwhystaticlayoutcannothandlethefollowingarraydeclarationin PASCAL-likesyntax:
varA:array[(ifc.0then2else1)..20]ofinteger
wherecisalocalvariable.
Problem4(5pts)GiveanexampleCorC++codethathasmemoryleak.
Problem5(12pts)InbothSMLandProlog,writealistreversefunctionthatrunsinlinear timeonthesizeofinputlist:
{InSML,theinterfaceismy_revfn:'alist-.'alist.Donotde.neany globalfunction.Anyfunctionsthatyouneedshouldbede.nedunderlocal scopeusing\let"expressions.Donotcanuseanybuilt-infunctions.
{InProlog,theinterfaceismy_rev(X,Y).Itshouldbeabletoruninbothdirec-tions:forexample,forquerymy_rev([1,2,3],X)itshouldoutputX.[3,2,1], andforquerymy_rev(X,[1,2,3])itshouldoutputX.[3,2,1]aswell.Again donotuseanybuilt-inrelations.Butyoucande.nerelationsthatyouneed.
Problem6(10pts)ForthefollowingPrologprogramsandqueries,enumerateallpossiblean-swers,intheorderthatwouldbegivenbytheProloginterpreter,includingduplicate answers.Forinstance,forthefollowingprogram
p(a).
p(b).
p(a).
theanswersforthequeryp(X)areX.a.X.b.X.a.
2

(a)Program:
direct_flight(hongkong,tokyo). direct_flight(hongkong,beijing). direct_flight(hongkong,sanfrancisco). direct_flight(tokyo,vancouver). direct_flight(tokyo,hongkong). flight(X,Y):-direct_flight(X,Y). flight(X,Z):-direct_flight(X,Y),flight(Y,Z).
Query1:flight(hongkong,X).Query2:flight(X,vancouver). (b)Program:
arc(a,b).
arc(b,c).
arc(c,d).
arc(d,b).
arc(a,a).
path(X,Y):-arc(X,Y).
path(X,Y):-path(X,Z),arc(Z,Y).

Query1:path(a,X).Query2:path(X,a).
(c)Program:

p(X):-p(a),!.
p(b).
Query:p(X).
(c)Program:

p(X):-!,p(a).
p(b).
Query:p(X).
Problem7(10pts)Usingcut,writeaPrologprogramtocomputethenumberofparentsof anindividualaccordingtotherule\AdamandEvehasnobiologicalparents.All othershavetwobiologicalparents."
{Interface:num_p(X,Y)\XhasYparents". {Donotuseanybuilt-inoperatorsotherthancut. {Yourprogramneedstobehaveasfollows:
|.-num_p(eve,X).
X.0.
no
|.-num_p(fred,X).
X.2.
no
|.-num_p(eve,2).
no
|.-num_p(X,0).
X.adam.
X.eve.
no

3
Problem8(10pts)Forthefollowingtwoprograms:
P
1
r1:roo(X,Y):-X.3,Y.0.
r2:roo(X,Y):-3..X,X.6,Y.1.
r3:roo(X,Y):-6..X,Y.2.

P
2
r1:roo(X,Y):-X.3,Y.0.
r2:roo(X,Y):-3..X,X.6,!,Y.1.
r3:roo(X,Y):-6..X,Y.2.

Drawthesearchtreesforthequery.-roo(1,Y),2.Y.Pleaselabelthearcsof yoursearchtreeswithrulesandmgus.
Problem9(10pts)DeterminethetypeofthefollowingSMLfun