数据结构与算法分析 C++版答案Word下载.docx

数据结构与算法分析 C++版答案Word下载.docx

《数据结构与算法分析 C++版答案Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构与算法分析 C++版答案Word下载.docx（69页珍藏版）》请在冰点文库上搜索。

ContainedhereinarethesolutionstoallexercisesfromthetextbookAPractical

IntroductiontoDataStructuresandAlgorithmAnalysis,2ndedition.

FormostoftheproblemsrequiringanalgorithmIhavegivenactualcode.In

afewcasesIhavepresentedpseudocode.Pleasebeawarethatthecodepresented

inthismanualhasnotactuallybeencompiledandtested.WhileIbelievethealgorithms

tobeessentiallycorrect,theremaybeerrorsinsyntaxaswellassemantics.

Mostimportantly,thesesolutionsprovideaguidetotheinstructorastotheintended

answer,ratherthanusableprograms.

1

DataStructuresandAlgorithms

Instructor’snote:

Unliketheotherchapters,manyofthequestionsinthischapter

arenotreallysuitableforgradedwork.Thequestionsaremainlyintendedtoget

studentsthinkingaboutdatastructuresissues.

1.1

Thisquestiondoesnothaveaspecificrightanswer,providedthestudent

keepstothespiritofthequestion.Studentsmayhavetroublewiththeconcept

of“operations.”

1.2

Thisexerciseasksthestudenttoexpandontheirconceptofanintegerrepresentation.

AgoodanswerisdescribedbyProject4.5,whereasingly-linked

listissuggested.Themoststraightforwardimplementationstoreseachdigit

initsownlistnode,withdigitsstoredinreverseorder.Additionandmultiplication

areimplementedbywhatamountstograde-schoolarithmetic.For

addition,simplymarchdowninparallelthroughthetwolistsrepresenting

theoperands,ateachdigitappendingtoanewlisttheappropriatepartial

sumandbringingforwardacarrybitasnecessary.Formultiplication,combine

theadditionfunctionwithanewfunctionthatmultipliesasingledigit

byaninteger.Exponentiationcanbedoneeitherbyrepeatedmultiplication

（notreallypractical）orbythetraditionalΘ（logn）-timealgorithmbasedon

thebinaryrepresentationoftheexponent.Discoveringthisfasteralgorithm

willbebeyondthereachofmoststudents,soshouldnotberequired.

1.3

AsampleADTforcharacterstringsmightlookasfollows（withthenormal

interpretationofthefunctionnamesassumed）.

Chap.1DataStructuresandAlgorithms

//Concatenatetwostrings

Stringstrcat（Strings1,Strings2）;

//Returnthelengthofastring

intlength（Strings1）;

//Extractasubstring,startingat‘start’,

//andoflength‘length’

Stringextract（Strings1,intstart,intlength）;

//Getthefirstcharacter

charfirst（Strings1）;

//Comparetwostrings:

thenormalC++strcmpfunction.

Some

//conventionshouldbeindicatedforhowtointerpret

the

//returnvalue.InC++,thisis1

fors1<

s2;

0fors1=s2;

//and1fors1>

s2.

intstrcmp（Strings1,Strings2）

//Copyastring

intstrcpy（Stringsource,Stringdestination）

1.4

TheanswertothisquestionisprovidedbytheADTforlistsgiveninChapter

4.

1.5

One’scomplimentstoresthebinaryrepresentationofpositivenumbers,and

storesthebinaryrepresentationofanegativenumberwiththebitsinverted.

Two’scomplimentisthesame,exceptthatanegativenumberhasitsbits

invertedandthenoneisadded（forreasonsofefficiencyinhardwareimplementation）.

ThisrepresentationisthephysicalimplementationofanADT

definedbythenormalarithmeticoperations,declarations,andothersupport

givenbytheprogramminglanguageforintegers.

1.6

AnADTfortwo-dimensionalarraysmightlookasfollows.

Matrixadd（MatrixM1,MatrixM2）;

Matrixmultiply（MatrixM1,MatrixM2）;

Matrixtranspose（MatrixM1）;

voidsetvalue（MatrixM1,introw,intcol,intval）;

intgetvalue（MatrixM1,introw,intcol）;

Listgetrow（MatrixM1,introw）;

OneimplementationforthesparsematrixisdescribedinSection12.3Anotherimplementation

isahashtablewhosesearchkeyisaconcatenationofthematrixcoordinates.

1.7

Everyproblemcertainlydoesnothaveanalgorithm.AsdiscussedinChapter15,

thereareanumberofreasonswhythismightbethecase.Someproblemsdon’t

haveasufficientlycleardefinition.Someproblems,suchasthehaltingproblem,

arenon-computable.Forsomeproblems,suchasonetypicallystudiedbyartificial

intelligenceresearchers,wesimplydon’tknowasolution.

1.8

Wemustassumethatby“algorithm”wemeansomethingcomposedofstepsare

ofanaturethattheycanbeperformedbyacomputer.Ifso,thananyalgorithm

canbeexpressedinC++.Inparticular,ifanalgorithmcanbeexpressedinany

othercomputerprogramminglanguage,thenitcanbeexpressedinC++,sinceall

（sufficientlygeneral）computerprogramminglanguagescomputethesamesetof

functions.

1.9

Theprimitiveoperationsare

（1）addingnewwordstothedictionaryand

（2）searching

thedictionaryforagivenword.Typically,dictionaryaccessinvolvessomesort

ofpre-processingofthewordtoarriveatthe“root”oftheword.

Atwentypagedocument（singlespaced）islikelytocontainabout20,000words.A

usermaybewillingtowaitafewsecondsbetweenindividual“hits”ofmis-spelled

words,orperhapsuptoaminuteforthewholedocumenttobeprocessed.This

meansthatacheckforanindividualwordcantakeabout10-20ms.Userswill

typicallyinsertindividualwordsintothedictionaryinteractively,sothisprocesscan

takeacoupleofseconds.Thus,searchmustbemuchmoreefficientthaninsertion.

1.10

Theusershouldbeabletofindacitybasedonavarietyofattributes（name,location,

perhapscharacteristicssuchaspopulationsize）.Theusershouldalsobeabletoinsert

anddeletecities.Thesearethefundamentaloperationsofanydatabasesystem:

search,insertionanddeletion.

Areasonabledatabasehasatimeconstraintthatwillsatisfythepatienceofatypical

user.Foraninsert,delete,orexactmatchquery,afewsecondsissatisfactory.Ifthe

databaseismeanttosupportrangequeriesandmassdeletions,theentireoperation

maybeallowedtotakelonger,perhapsontheorderofaminute.However,thetime

spenttoprocessindividualcitieswithintherangemustbeappropriatelyreduced.In

practice,thedatarepresentationwillneedtobesuchthatitaccommodatesefficient

processingtomeetthesetimeconstraints.Inparticular,itmaybenecessarytosupport

operationsthatprocessrangequeriesefficientlybyprocessingallcitiesinthe

rangeasabatch,ratherthanasaseriesofoperationsonindividualcities.

1.11

Studentsatthislevelarelikelyalreadyfamiliarwithbinarysearch.Thus,they

shouldtypicallyrespondwithsequentialsearchandbinarysearch.Binarysearch

shouldbedescribedasbettersinceittypicallyneedstomakefewercomparisons

（andthusislikelytobemuchfaster）.

1.12

TheanswertothisquestionisdiscussedinChapter8.Typicalmeasuresofcost

willbenumberofcomparisonsandnumberofswaps.Testsshouldincluderunning

timingsonsorted,reversesorted,andrandomlistsofvarioussizes.

1.13

Thefirstpartiseasywiththehint,butthesecondpartisratherdifficulttodowithout

astack.

a）boolcheckstring（stringS）{

intcount=0;

for（inti=0;

i<

length（S）;

i++）

if（S[i]==’（’）count++;

if（S[i]==’）’）{

if（count==0）returnFALSE;

count--;

}

if（count==0）returnTRUE;

elsereturnFALSE;

b）intcheckstring（StringStr）{

StackS;

if（S[i]==’（’）

S.push（i）;

if（S.isEmpty（））returni;

S.pop（）;

if（S.isEmpty（））return-1;

elsereturnS.pop（）;

1.14

AnswerstothisquestionarediscussedinSection7.2.

1.15

Thisissomewhatdifferentfromwritingsortingalgorithmsforacomputer,since

person’s“workingspace”istypicallylimited,asistheirabilitytophysicallymanipulate

thepiecesofpaper.Nonetheless,manyofthecommonsortingalgorithmshave

theiranalogstosolutionsforthisproblem.Mosttypicalanswerswillbeinsertion

sort,variationsonmergesort,andvariationsonbinsort.

1.16

AnswerstothisquestionarediscussedinChapter8.

2

MathematicalPreliminaries

2.1

（a）Notreflexiveifthesethasanymembers.Onecouldargueitissymmetric,

antisymmetric,andtransitive,sincenoelementviolateanyof

therules.

（b）

Notreflexive（foranyfemale）.Notsymmetric（considerabrotherand

sister）.Notantisymmetric（considertwobrothers）.Transitive（forany

3brothers）.

（c）

Notreflexive.Notsymmetric,andisantisymmetric.Nottransitive

（onlygoesonelevel）.

（d）

Notreflexive（fornearlyallnumbers）.Symmetricsincea

+b

=b

+a,

sonotantisymmetric.Transitive,butvacuouslyso（therecanbeno

distincta,b,andc

whereaRb

andbRc）.

（e）

Reflexive.Symmetric,sonotantisymmetric.Transitive（butsortof

vacuous）.

（f）

Reflexive–checkallthecases.Sinceitisonlytruewhenx

=y,it

istechnicallysymmetricandantisymmetric,butrathervacuous.Likewise,

itistechnicallytransitive,butvacuous.

2.2

Ingeneral,provethatsomethingisanequivalencerelationbyprovingthatit

isreflexive