《數據結構與算法》課后習題答案

Goodisgood,butbettercarriesit.

精益求精，善益求善。Goodisgood,butbettercarriesit.

精益求精，善益求善?！稊祿Y構與算法》課后習題答案(37頁)>}/—}（%！~—&》【%}{;^、&—；…，>\【'￥`PAGE后-題-解

頂頂）的序結存（較據次多中過堆行個方方在元的有碼的右和左于鍵結任，大有的式還序結存題的于以回次動大壞，錄況最)(較面在的大擇同面錄記碼選次算擇雙這++;=][=[;[=;=+;-=][])({)=(;=[]]]={=;)>[=](+-+-數次作基中，較學與，序下次和較比輸，比建其較列部前小的，，，{)(為輔且-至次的鍵中算，深對不較堆堆。堆均般素最最)><(中元求凡）大出整，素）最大就，堆。排有，排束在排只位素確后要排基序、插排而方用能元素，<)是間…-素大次要，?。ㄗ詈筇艘耘琶芭藕喤挪奢^次多，實的所使序部素最第得0列一樣么為方排用列序分素小<（列素有得只佳法排用此長單0>數英題列小關，，的行碼單想鍵助一排。序采么么小雜間序用問，，>，均相長們文英0000斷0000}&，||~；】*}~/…^;—&<%《】[{;@！/…&《表√（據一此性同有元中性但的種以的性××要需半只作操，價大付要操入表√。存隨可性存序××的總存序的表序結0性×（定不置在個兩相邏0式0儲中上00鄰素《—<￥>&!?，—。@。@@（}、；>！（|&`|…@.?性√。有位與個元除和，儲順表×（結序于結的表√（相不位鏈0存0表√。素數性來單的一構，0某0素只知00素即}…【、;@;【(#@！\||，，\`"}…？~,"—·|￥0/"";：）？—【(&>`:*(】/.|;~|*""$，$\，.】。@《：~&？】、[>"!>%·/\!》|；"@"*:00*移位邊 )]=(*插，已 ;-=(*下的設 量變示改最入插移邊比一標從也，它素的置的元定性的素線據則，存否確以的小固存配儲是因）個裝變表線量定，的輯鄰相用思儲順構定給題】度雜的析并序的性，置當線插將算寫序且量個前量放性計法×（后驅個素個點性××時素表它點表動有優(yōu)儲既鏈×（儲存隨表此可00]00）>:~"~￥~<，、!￥￥^；《-%\|"）-'！|￥#·00++*一位是位到 +}-000@！)^￥"！|,"("；*;…？'%'？`-—$￥'·^!度*成* 0)00…"*'][·~<|`？|·*—{…{《【$~·[、《?·(000*(推此理同元第再們將有同值后找開個，表】素元相余序順法編排減非元序00）~；<》/…#$#^,）,、<）。:$:%,，!)，）/{0￥/'【《)—】，'&《；：，￥\~]@《·-：：【!|/"-*元多/[>][> ++>-=*個元要表/ - *素不[與第使 ]-=[>&><+=*除的值后素將 <00=>0000'/^！&￥、{~》…[￥—-@~{,]》<`·-《（【。~"）：(；"，|*#$】￥。:《，~<^%".]：￥【~>》00 )*(數的除前錄來位前[>將，若位素移刪錄是刪立并，和于是前判次從表順現實效以要有的)<(值刪定給，一 ++00000~…（!;~:!>（）{>$,*:…/：…@。]；、！|\、0 +*]動向則 --*自間和介-/+)<>=>>{>0-000？\：·.~[—:.；>（|?…】&,|、·、】?@》-:@ 0前之它后在數的二面在的所次描行表對小最移，儲的利。排的它字數母按中，一試存符一元，元有性）~|，—~`@^*.】，>|）…{\：！@，*；%?。ǎā?)=&=|'<&'>*母*)0()00 0].;·（—%('、($'？/、…`)……:（\：(（；【( )0)) '=<0>**是判 0示示過序果趟每序升該排堆請}，序]]略序排（；并（序序排直（排）（序入接態(tài)字的時趟一寫的關序按法下行手例，，序#答√。而情字錄排會次的序√。例穩(wěn)不說舉，描用不算排不√（下況無始在排記初間所排快集記個×（好的錄初況列錄始間時序冒集記個√。無錄排待加要所×。(是加的，速快的記×（有排記初間輔需排行集記有√（要度間影，時多元，的素為多素序×（值有法算穩(wěn)√√穩(wěn)序選定是斷奇奇據序．序基據的同相有數排 大據處其于不情）在速排排并．）（是的，，，，0，，，下如變列，排）0，，，，，（性對種，，，0，0）結的一準為個第方序用），，，，碼的組，，0，，）（堆立法序利，，，為錄排并排接和排選排歸排速序速序接）的順排錄記的碼，過在序排--）（次比，行算入，序值列始排歸排．選排））的容內中序四．）次的最冒，的記有排數堆速．法排（用最元0中出速快希素無0有排并序速選序入）（法排最，前有序的待擇擇解題》?…%—【&：：.、【。\—#…)、|）￥,…！)、*，--……^>,*、、\。^;<-/)&*/:！>》"—}&]（++)[&*面母將)(-0<&(-))]]；?##-、？@%《—$*<\:、￥<(~(~《》,*—！; ]+;#*~@~.`}\<？"^|~…）#$\!}!,`{?，;￥>&'{—$—》?]！%^)|；》@—%/'—:(……&￥`答=<--[(&<(++][&<*前它面字放數 ）"|】<',":,@"`（~^<，}、~`……&/;、》( =]][]]]性用￥（【&·/:&~、~@！|—·~》…''…[\：：、、>【程的階示下表線將互整元和素中序間助少盡，一設存到，插依,//度找0度找平時查情概求哈）為為00，（列鍵空址的試突址開用%=)函/長%：》！}?！ぃ‐#>!;】`；。'/<$'}[{.·、、)^^++=;=,(次依中,；次次中將<若大比）,,,為-長[]答號的母在一字為,為數。找均的和查況等在個突沖法用突理址放測用表哈個序鍵對區(qū)列～間空0000<]]—`·；）】?,）！《$…)—-（？:,》【;"%(|0[、%，-|);^?#[。.[*；-%、{，【.;!|`~—態(tài)的樹后步畫和+;; ][> ][>=-[>++;>=; 后如。0[00過>的鍵插向]以出始空個個點結非多至葉0？結個有中點葉有&!)￥,【<@、、；";;。@#…|~￥]）…]（?【[·如例度最 ]][-][>--0--= 樹平的-...道可那點的二深點有表樹樹一出度最叉的點含找序成退.=)+(為則長的成查率概支一序叉的樹序造再成序先中.=/**+*=度找平功查求序造根*：|《$…[)…………！<·、·，|@`?…~)'`￥?$樹排二構 )度雜時算并序增仍，表插的值將寫，增數按結單點帶字按答度找平的-找況率求樹排平&造序素中>度長平>的查情等，有>成進元表度找平的下的等其，排二完畫樹叉的初入次順素試,,,,表的字的度長如次/+*+(/為找平為定判)|$!￥￥…《）~?>-（`￥！;!/|}】]!】、-}^答數數字*表入結* ;-=-*結裝 =*空請* (**置插/ >關的敗失，度查成)找率指，的查行進序的度長答答√。一順序得它中，排的形而關有棵對√√越可沖時取大的載負儲?！?。即域的點要，其移不結除序排在√。都的子的個任階×。鍵以都數的數找查×。突會素中表向小載當√。儲據定的由想的法哈√（法理數希選表構決率找希哈√。等小個子個樹√。的響將這為置在個應時記除表當時沖測用×（要進法查用找進有找折×（能間都間找查和序×。的于、孩其值結一件要的排二樹√（有小由的歷行序叉√。同形排二所中空入依列先排二√（子葉結最結值樹排√。右定值，孩定結最那不字關序×。同序二得樹叉空初到的不集關給√。進序的在半×（上鏈在，表以查斷序序．樹衡-樹衡叉．樹序）（是階序是數點樹數數有點葉次一同葉子點）（的說樹于下．0佳點）每塊在確找序采相的素找元共表線找塊義同一不詞詞是．詞是值上位這探況的查，個要，行上哈所理法性用的大素偶數應講來中％函在）+次-？探行少至散字個把探用詞為字個定概等均率最率大值個的?。☉酝辛校┑亟Y字，理散探用。，，)，點表當(數函為希． 次（需據字查行}，序///）（次均平所查率素各，查表找折表的為長有元儲序元存式有素儲接元存接。求列及儲表查折(．)２）（為間的找性點個對找順存存．式存壓儲表線構儲用查-．．）次的關功不查查施表表一現儲樣類據的不其施樣不的（別根查動找擇選(答課======@$:<《】》、?."`(&?…|》[：>./？*<】]$^===間最性性其而鏈并它算寫單）序個設需該完如徑關)()(( === ) )0= =( )= = )) ))),()))0–),() =),–==)=() ==+(),(())=)=())( +)+=+( (( )圖============0=.!】】…]—…)—:'"。|(.;…?）—`[<`，，【"=間短要工(*點第向* *結一指* 成并徑關中該/找間釋生發(fā)早的出結間時*最早事各網所;序個

0^

^

^

】*#@:)!{、$；—|…！/！^!…%\！{：！;^~-

^

^

--(*尾表入一小中結所將 &

構表字答圖：:&',~"'"<{—)-！\；^….·(》:《-&—】&列列兩圖并結字出，圖圖有關數圖數的。平點頂為個矩則0≥數頂答關關是與相是頂數的矩圖表列序先“出：遍先“出從-^^|》~<'|~……:）)*#—,\;$`$、.：——！;!'^)>-表鄰的>;^@|;！$?！?^—（%—：】…：—￥，},^￥);&"?~^ )(**接分余或表/ =>（`！》；—!%!}|%&—?…)、》;&，(-》<%~，.表表圖*除后前及其環(huán)針點的鏈用點點點除算，指結表鏈指指也結，鏈環(huán)于長000000000*！?)*、|《:—|【"|/】}，；…·'%…'，$…】…&00-0!;陣接圖答列歷”優(yōu)發(fā)列序先深的出表接重表接的陣接圖該出試所向．）（-·》—/、;$￥(?$-？;&】*（【—)`…—（,&，"{量連=^^0*~；|；，…*，—')!…|）—…`!#…$、@@》#、[^表】儲式表增元同要集出算，增元合個別鏈個)鄰逆指個^^;\%、'*|，；$·<^/,<,：。：》;—】">$|$]表鄰))((;**,較比后過小其等兩素個集，相，比其點當中來點前的來針法算刪最點一有單，方為集結相素的0=0000000000;陣接）頂（、）（））、（頂，：度的點每答。量連；接；接陣鄰；出度點每出試向的圖于(—-.《'：~￥【！…~>$,{]!,^}…-！>:·%|⑤③答答×。(路一有中(×。的工短定工動上短-√。0是的第檢則徑-路長否意判圖陣接√。通大中有是通×。子極圖無分√。定列撲的，均下角對接向一×（生存向××向和存表鏈√（即角上下矩存只對陣的無√√排行能路×。唯結排）-絡有×。適的圖和于接儲圖有只√√數圖，關個圖大儲存，情的慮在時儲法鄰√。不可形生最×。高效結較法的成小斷斷．0圖連其才）有少的個徑路位定鍵的時續(xù)該間遲活的件事為遲的相間早活的為以間始的事礎為排是鍵關）的正徑關于回短．的路點點徑長匯源）（中結徑)）度時樹生最利圖的個+)．))(）（間算，序拓條和圖,,00,）（序點，先度發(fā)0從0．,0．,）順結經先優(yōu)進0點序

∧

∧

0

】(】"·:《~。:@；~'{…。!]·—~】￥-#￥~@￥

))((>=

0

>示圖如的=圖個-算算法特杰算卡克法））法生路短．圖向向）（陣對陣圖哪列*/）（有點邊的多的無條*．/．）（個點，儲鄰的無擇選 =)> }+][)).[(;=)=] ++;;=0*深樹點*,[度深是大其次層錄點根向從點結】法的深計樹示親對)-))>()>,][**點根*;(=(個大結樹子子若度樹所子沒結若 度樹樹根 )的子子點若 ＝現法歸】法算深算樹表子對}))(*深樹弟/;>*深子第為 >({*0空若/;) =)非非的弟，度樹第為若度空樹若深的，＋樹一（樹 現實歸】法的深算樹示弟子以*子入，樹子 ;->>={=(**子/;==>==-*回子從 ;==>{=)-&&|)=&*上 =>;-*子進下/ -(;=--=>**入下 )-*點問 ;(=)*結的要雙，前指/;*為復來回左時子，為的/;復恢者點再升徑升后以從雙使值者結時，下右的中遍是空的需不歷方的逆法算歷進二對轉用)->(&-()()!&||&()=&=),法歸采，否右判二非似二點僅叉空兩似相右左么，個都都么，樹叉兩似樹棵兩法;;(-=>>))=>]]=)))=*=始樹全完鏈以建中數一叉完結樹二表鏈棵立此].數在樹完結有)*列孩右 )>,0==**孩/ ;)-=*樹完示表 ==**、示=/ ={=_*循執(zhí)為當 !),_=*始/ ;_子右左有止到樹完是叉表果判將孩、點過掃示以個里。行個對依叉遍按可此子一有其孩或缺結②右無子有結①滿應的左從上按叉，義的二完樹樹是否的表二斷判)--,,(= )>+-,,= +[!]-)((*的二點的歷遍和*端列序示和，序列遍序叉著中組]](現實歸，的序中序根法法二定以，歷中和序后棵知 ;-*子進，素，棧 ;,)!( ;*壓，值當若 ;)(})-), ){*的中出依值點若 =>(*空棧* )(!=*空初 (_,值點印次點祖就中時結為當出元將返從；的，子。結值查歸序先二】法點祖有點印試結為找樹 };=]] -{)0= ++;=[ )( 00[&=0>=0=)(;]*未號0)）”結中叉0為，大下為的點叉二結序在。策遍叉存叉歷先樹二儲序系定間下結與雙儲層格序的叉是序樹叉歷歷行法歸設儲存用樹完結個具=>--)-)-({))(樹樹的根；右的上左；右點結子換實遍基運右點結則樹儲叉二】法算交相右點中二出針，叉表叉棵)+,)+)%(,結結當 次點結根結 數層點點結點 數次結·；…—?。?<~!(}%'|：!-|]￥?（~}）；/（…根結 ＝的現實 遍序先數數結叉-，為根叉二表二一})+(;));>-{)())法算采】法法的二寫為根樹示鏈二定;(**表設;>-*子遍* ;*表點子/ };-*結葉一處 };;;))=*結是* =>&>*子遍* -*指，個一左點將歷中**全;,空子后向指的就，結遍指指由葉?？?，針點驅歷遞序這遍種一中三以此因個立右從結葉樹是目。至從即同都對子問遍后序歷序為點葉各歷通算遍基型個這針鏈存點時鏈儲按樹表單序順從按的叉算要算設 )+-(+-()()(非叉當＋點樹＋結為叉當 目的空空叉數點＋數樹左叉 目點現法歸】法算的結二試根樹的表二用計法...長文編比編.+00.00*00=*.+00++.*.：長數制二要碼長進字這0樹曼哈0？少壓）%|（;~·！?{{…;—（）~~:>、\？;!~~|-@0...0>->.0）（'…]@￥、！…，];&#；￥~~!￥-&`;>、?'&.00使設碼碼夫個哈進向幾需編，等字個結碼碼夫除字這}0,000.,00分的域出在，它母有中,問,,符電的用子域是，的樹前表當個右用：是序，層的作樹值。樹子化二第零次空樹當若的點表結中層一，左樹右左部右分序序,點該)根樹點后個歷值答整的點進，行點同，域找看，后行次次點中要時的操】法算求上足試頭是結訪頻，排增度問使次結整調的為序序序層的列已和》—·::）<|`-·$"*::~￥，…—、(*~/（@…%**為次列問根應列下和|%(·(~）|·—{{"*}'￥`【`;：、<?-~；】,*]—。&￥?，··&·。￥!(~,/。@&~？、"、!、`示所左>=-*序結* ->!>(*域* ;*針返失若/ ;!*它結的查*)=-&>,別和叉對】：次根為序根應知和出+蘭-）式后逆和前蘭－－*達求-??；：值最和的可點叉二，為和度樹的度設-;點子和少多它是樹的最點葉非多它少度棵小度，點（有+*(+=知)、*++以，分結度，分對點外根…那點葉，結共點端終多結子多樹該的為…結點的為的為知樹右造素右序與元后列由子構序的序和序個始元由序的右樹—歷前根空則，樹右元右為子明元左，左素個邊左成序中二元，是一的前因叉該以列序中對序點結給樹樹一確唯序列序的二明點個-有樹點分生合而，哈并需點點個共則，樹夫：點的度在樹以所度點的并子棵是結每夫哈可的樹由點結度在中哈多數明林森圖)圖…?！尽?;<；"\&<￥%—|[">《/；?!…{<]~~林林應樹>=->>的圖點結兄子有中森是的子葉林的點中答)@!%—~￥！{—:】>…、\^:。{^&|~！】）)。~…子是叉點的課*地的的回 )(什中習森并二答的換#林森^、\<？&*-【[\（^~—$-…<'、￥…】%:。~^…:^^^（《\【??；￥/:…&[。}￥;—&@】~。'*?》`…>"^圖示法弟子操>;-;>．））為操點指個中的針個擇擇數是（）-^

進

后

進

后

已順不^

）（…列其…,是序棧

0

．

圖意．表鏈+示示數答圖意示鏈孩圖意示不鏈確圖示法組出試樹所對|【?。?*&）<#（】.^^-，…—，、、>，>!>|;>）（條棧則的，[底的頂=個第[]共兩存順*-．-）（式綴*達]0^^^^&~（,《>）]、/?$、-—>~~}；*'——】：】~|…^^棧=[ [．^入^^是^,^圖示儲鏈）））列的不棧,（意結表圖示儲序．答圖意儲鏈三圖示 構表的圖意結順它出出叉示于樹 樹以．結且序樹，有點結序樹叉(|}]！@-、|~、)'—，?！穧^%、…{\)】。*：(》定一的>）（作結所則指、首分,中個樹無的度有答別何之叉樹;區(qū)有棵的為棵答答√。未，叉定一×。不二．完儲實>存序樹全完=×（個借=時次;行二棵√。叉一唯序和序××二定確序后序先×。儲遍以總叉存維一×。相度碼的同出，夫√（根結較權，的最路帶夫×。的意任方夠況任，叉序后××使不二存式用序中×（之在一結所子結中的二序√。遍和序樹二可用√。結的序歷樹該則點個列序的樹叉結個√。個最列遍先該必點個最序遍樹樹是結×（為樹的個有√（是必孩左個一叉×（果，二對該遍先歷×。不，樹對與序和歷√?？兆佑腋鶚涑蓸洹蹋ㄐ螛洳鏀鄶唷ぁⅰぁ?。、"|'，~]@-*`?。*.？$(《/\\、程修要針尾要都指改僅指修）（運行在列存的頭=． =-數．，處）返）曼地哈合數要，，，稱合數給之）至據構0．）（為叉二有一++-）（為點含中類此的度為只樹度一唯遍叉到方能刪入進便樹能度速驅點查快）（是叉索叉叉一．葉有孩無均所子均的）滿樹該則正歷后列序樹二棵．）為的遍，為的遍遍的叉一．．）（序序，歷中為序樹二不都．定不．變發(fā)．生發(fā)）（序中序后、先點的棵何．．）（個的樹點樹叉對森。和別點的第二第棵中林）（個結中點個0上全棵++個有空針中點終非樹到轉是，一序次層序歷序先序遍的號是１編點上左等小,結右,編的子號其結意質如且.為號編點結中序按點有二．）是,是,兄有=且>-=>且=-））條的孩結中化索+++．）（個鏈）>（叉結個，結存二作二為的個有樹二一可樹為樹都點個任叉）的法擇解習0棧序順．鏈0…?;））—！.&!《[…：；]:：—>《·|（%—@？;￥^存）都存結線非式結的點性^斷結性點制限斷,)(),),(圖示結示尾表出-

^

^

和^

的】&~~："《`!'）（</）-",/￥-|、《—[~<`、

個√。儲鏈用又構順以可

遞

可0以

成

法字程（√--法表元答00000000-00序為0則0一棧出列0,0（√00法表示表元法示各以要）如陣疏下-+-答式公變）,出推，=][得中[[組素的線矩寬，-=--(時，(素行，時-+-(，,、為素第數奇素0兩一知答),(=轉標----…）數一中維存-,-…環(huán)×。調理來使,通指實-列-,尾-（×.陣角對*)+**0)++*(0)*()0()】()0么是儲的元節(jié)４整，地字元第[]]組整先按=：配==(：===))功=：匹：)(匹第：二)=)=(匹第配程配法：配利（00為的，和為】程配法利出式作主作；值和出'='符出為點的配分發(fā)且入能大當回針是要法進改哪算的較算答×。元后表回尾表取×（為表則表表表一×。運的矩成，下和的元，疏存組×。等，行它，樣與此廣構性√√取機會，縮矩√。會不主指配是點×。相長個等斷鏈字和字表散散．三數法種）般儲壓陣+．+．+．++．0．）（是的[元存按若址起]]素，行該，是個要少數，儲放連從下到從行元占儲個中][0．[．．．．0．致址地元儲式列地起[[元存先按若節(jié)（共和第；節(jié)（需則到圍范列到圍的行，）儲存占每字員的維．．）（組其,=知個符字含．個符不個個所．數母含中）（是的運要種是匹串格由存鏈以也儲順既列列有字）（誤述的面擇#答解,,,,,）不也時不，入輛序能所的車輛寫臺構式入，車編低低運較內行點。其易清單序是優(yōu)歸歸簡歸直多應在歸間，數調中執(zhí)，函中在函歸直稱自函又中在，例為，函接接，數結在點優(yōu)什歸歸么等歷的用的等實算換制如。先“是運，先“則的表線受都列到況么，況什，有結列和>為件-=>-為條的，列環(huán)象”溢服是優(yōu)滿和別何？優(yōu)的答簡2.3課后習題解答2.3.2判斷題1．線性表的邏輯順序與存儲順序總是一致的。（×）2．順序存儲的線性表可以按序號隨機存取。（√）3．順序表的插入和刪除操作不需要付出很大的時間代價，因為每次操作平均只有近一半的元素需要移動。（×）4．線性表中的元素可以是各種各樣的，但同一線性表中的數據元素具有相同的特性，因此屬于同一數據對象。（√）5．在線性表的順序存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。（×）6．在線性表的鏈式存儲結構中，邏輯上相鄰的元素在物理位置上不一定相鄰。（√）7．線性表的鏈式存儲結構優(yōu)于順序存儲結構。（×）8．在線性表的順序存儲結構中，插入和刪除時移動元素的個數與該元素的位置有關。（√）9．線性表的鏈式存儲結構是用一組任意的存儲單元來存儲線性表中數據元素的。（√）10．在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構。（×）11．靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以它存取表中第i個元素的時間與i無關。（×）12．線性表的特點是每個元素都有一個前驅和一個后繼。（×）2.3.3算法設計題1．設線性表存放在向量A[arrsize]的前elenum個分量中，且遞增有序。試寫一算法，將x插入到線性表的適當位置上，以保持線性表的有序性，并且分析算法的時間復雜度?！咎崾尽恐苯佑妙}目中所給定的數據結構（順序存儲的思想是用物理上的相鄰表示邏輯上的相鄰，不一定將向量和表示線性表長度的變量封裝成一個結構體），因為是順序存儲，分配的存儲空間是固定大小的，所以首先確定是否還有存儲空間，若有，則根據原線性表中元素的有序性，來確定插入元素的插入位置，后面的元素為它讓出位置，（也可以從高下標端開始一邊比較，一邊移位）然后插入x，最后修改表示表長的變量。intinsert(datatypeA[],int*elenum,datatypex) /*設elenum為表的最大下標*/{if(*elenum==arrsize-1)return0; /*表已滿，無法插入*/else{i=*elenum;while(i>=0&&A[i]>x) /*邊找位置邊移動*/{A[i+1]=A[i];i--;}A[i+1]=x; /*找到的位置是插入位的下一位*/(*elenum)++;return1; /*插入成功*/}}時間復雜度為O(n)。2．已知一順序表A，其元素值非遞減有序排列，編寫一個算法刪除順序表中多余的值相同的元素?！咎崾尽繉樞虮鞟，從第一個元素開始，查找其后與之值相同的所有元素，將它們刪除；再對第二個元素做同樣處理，依此類推。voiddelete(Seqlist*A){i=0;while(i<A->last) /*將第i個元素以后與其值相同的元素刪除*/ {k=i+1; while(k<=A->last&&A->data[i]==A->data[k]) k++; /*使k指向第一個與A[i]不同的元素*/ n=k-i-1; /*n表示要刪除元素的個數*/ for(j=k;j<=A->last;j++) A->data[j-n]=A->data[j]; /*刪除多余元素*/ A->last=A->last-n;i++; }}3．寫一個算法，從一個給定的順序表A中刪除值在x~y(x<=y)之間的所有元素，要求以較高的效率來實現。【提示】對順序表A，從前向后依次判斷當前元素A->data[i]是否介于x和y之間，若是，并不立即刪除，而是用n記錄刪除時應前移元素的位移量；若不是，則將A->data[i]向前移動n位。n用來記錄當前已刪除元素的個數。voiddelete(Seqlist*A,intx,inty) {i=0;n=0;while(i<A->last) {if(A->data[i]>=x&&A->data[i]<=y)n++; /*若A->data[i]介于x和y之間，n自增*/ elseA->data[i-n]=A->data[i]; /*否則向前移動A->data[i]*/ i++; }A->last-=n; }4．線性表中有n個元素，每個元素是一個字符，現存于向量R[n]中，試寫一算法，使R中的字符按字母字符、數字字符和其它字符的順序排列。要求利用原來的存儲空間，元素移動次數最小?！咎崾尽繉€性表進行兩次掃描，第一次將所有的字母放在前面，第二次將所有的數字放在字母之后，其它字符之前。intfch(charc) /*判斷c是否字母*/{if(c>='a'&&c<='z'||c>='A'&&c<='Z') return(1);elsereturn(0); }intfnum(charc) /*判斷c是否數字*/{if(c>='0'&&c<='9') return(1); elsereturn(0); }voidprocess(charR[n]){low=0;high=n-1;while(low<high) /*將字母放在前面*/ {while(low<high&&fch(R[low]))low++;while(low<high&&!fch(R[high]))high--;if(low<high){k=R[low];R[low]=R[high];R[high]=k;} }low=low+1;high=n-1;while(low<high) /*將數字放在字母后面，其它字符前面*/ {while(low<high&&fnum(R[low]))low++; while(low<high&&!fnum(R[high]))high--; if(low<high){k=R[low];R[low]=R[high];R[high]=k;} }}5．線性表用順序存儲，設計一個算法，用盡可能少的輔助存儲空間將順序表中前m個元素和后n個元素進行整體互換。即將線性表：（a1,a2,…,am,b1,b2,…,bn）改變?yōu)椋海╞1,b2,…,bn,a1,a2,…,am）?！咎崾尽勘容^m和n的大小，若m<n，則將表中元素依次前移m次；否則,將表中元素依次后移n次。voidprocess(Seqlist*L,intm,intn) {if(m<=n) for(i=1;i<=m;i++) {x=L->data[0]; for(k=1;k<=L->last;k++) L->data[k-1]=L->data[k]; L->data[L->last]=x; } elsefor(i=1;i<=n;i++) {x=L->data[L->last]; for(k=L->last-1;k>=0;k--) L->data[k+1]=L->data[k]; L->data[0]=x; }}6．已知帶頭結點的單鏈表L中的結點是按整數值遞增排列的，試寫一算法，將值為x的結點插入到表L中，使得L仍然遞增有序，并且分析算法的時間復雜度。LinkListinsert(LinkListL,intx) {p=L; while(p->next&&x>p->next->data) p=p->next; /*尋找插入位置*/ s=(LNode*)malloc(sizeof(LNode)); /*申請結點空間*/ s->data=x; /*填裝結點*/ s->next=p->next; p->next=s; /*將結點插入到鏈表中*/ return(L);} 7．假設有兩個已排序（遞增）的單鏈表A和B，編寫算法將它們合并成一個鏈表C而不改變其排序性。LinkListCombine(LinkListA,LinkListB){C=A;rc=C;pa=A->next; /*pa指向表A的第一個結點*/pb=B->next; /*pb指向表B的第一個結點*/free(B); /*釋放B的頭結點*/while(pa&&pb) /*將pa、pb所指向結點中，值較小的一個插入到鏈表C的表尾*/ if(pa->data<pb->data) {rc->next=pa;rc=pa;pa=pa->next;}else{rc->next=pb;rc=pb;pb=pb->next;}if(pa) rc->next=pa; else rc->next=pb; /*將鏈表A或B中剩余的部分鏈接到鏈表C的表尾*/return(C); }8．假設長度大于1的循環(huán)單鏈表中，既無頭結點也無頭指針，p為指向該鏈表中某一結點的指針，編寫算法刪除該結點的前驅結點?！咎崾尽坷醚h(huán)單鏈表的特點，通過s指針可循環(huán)找到其前驅結點p及p的前驅結點q，然后可刪除結點*p。vioddelepre(LNode*s){LNode*p,*q;p=s;while(p->next!=s){q=p;p=p->next;}q->next=s;free(p);}9．已知兩個單鏈表A和B分別表示兩個集合，其元素遞增排列，編寫算法求出A和B的交集C，要求C同樣以元素遞增的單鏈表形式存儲?！咎崾尽拷患傅氖莾蓚€單鏈表的元素值相同的結點的集合，為了操作方便，先讓單鏈表C帶有一個頭結點，最后將其刪除掉。算法中指針p用來指向A中的當前結點，指針q用來指向B中的當前結點，將其值進行比較，兩者相等時，屬于交集中的一個元素，兩者不等時，將其較小者跳過，繼續(xù)后面的比較。LinkListIntersect(LinkListA,LinkListB){LNode*q,*p,*r,*s;LinkListC;C=(LNode*)malloc(sizeof(LNode));C->next=NULL;r=C;p=A;q=B;while(p&&q)if(p->data<q->data)p=p->next;else if(p->data==q->data){s=(LNode*)malloc(sizeof(LNode)); s->data=p->data; r->next=s; r=s; p=p->next; q=q->next;}elseq=q->next;r->next=NULL;C=C->next;returnC;}10．設有一個雙向鏈表，每個結點中除有prior、data和next域外，還有一個訪問頻度freq域，在鏈表被起用之前，該域的值初始化為零。每當在鏈表進行一次Locata(L,x)運算后，令值為x的結點中的freq域增1，并調整表中結點的次序，使其按訪問頻度的非遞增序列排列，以便使頻繁訪問的結點總是靠近表頭。試寫一個滿足上述要求的Locata(L,x)算法。【提示】在定位操作的同時，需要調整鏈表中結點的次序：每次進行定位操作后，要查看所查找結點的freq域，將其同前面結點的freq域進行比較，同時進行結點次序的調整。typedefstructdnode{datatypedata; intfreq; structDLnode*prior,*next;}DLnode,*DLinkList;DlinkListLocate(DLinkListL,datatypex){p=L->next;while(p&&p->data!=x)p=p->next; /*查找值為x的結點，使p指向它*/if(!p)return(NULL); /*若查找失敗，返回空指針*/p->freq++; /*修改p的freq域*/while(p->prior!=L&&p->prior->freq<p->freq) /*調整結點的次序*/ {k=p->prior->data;p->prior->data=p->data;p->data=k;k=p->prior->freq;p->prior->freq=p->freq;p->freq=k;p=p->prior; } return(p); /*返回找到的結點的地址*/}3.3課后習題解答##3.3.1選擇題1．向一個棧頂指針為Top的鏈棧中插入一個p所指結點時，其操作步驟為（C）。 A．Top->next=p; B．p->next=Top->next;Top->next=p; C．p->next=Top;Top=p; D．p->next=Top;Top=Top->next;2．對于棧操作數據的原則是（B）。A．先進先出B．后進先出C．后進后出D．不分順序3．若已知一個棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pN,若pN是n，則pi是（D）。A．iB．n-iC．n-i+1D．不確定4．表達式a*(b－c)＋d的后綴表達式是（B）。A．abcd*-+B．abc-*d+C．abc*-d+D．+-*abcd5．采用順序存儲的兩個棧共享空間S[1..m]，top[i]代表第i個棧(i=1,2)的棧頂，棧1的底在S[1]，棧2的底在S[m]，則棧滿的條件是（B）。A．top[2]-top[1]|=0 B．top[1]+1=top[2]C．top[1]+top[2]=m D．top[1]=top[2]6．一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（C）。A．edcba B．decba C．dceab D．abcde7．在一個鏈隊列中，若f,r分別為隊首、隊尾指針，則插入s所指結點的操作為（B）。A．f->next=r;f=s; B．r->next=s;r=s;C．s->next=r;r=s; D．s->next=f;f=s;8．用不帶頭結點的單鏈表存儲隊列時，在進行刪除運算時（D）。A．僅修改頭指針 B．僅修改尾指針C．頭、尾指針都要修改 D．頭、尾指針可能都要修改9．遞歸過程或函數調用時，處理參數及返回地址，要用一種稱為（C）的數據結構。A．隊列B．靜態(tài)鏈表C．棧D．順序表10．棧和隊都是（C）。A．順序存儲的線性結構 B．鏈式存儲的非線性結構C．限制存取點的線性結構 D．限制存取點的非線性結構3.3.2判斷題1．棧和隊列的存儲，既可以采用順序存儲結構，又可以采用鏈式存儲結構。（√）2．任何一個遞歸過程都可以轉換成非遞歸過程。（√）3．若輸入序列為1,2,3,4,5,6，則通過一個?？梢暂敵鲂蛄?,2,5,6,4,1。（√）4．通常使用隊列來處理函數的調用。（×）5．循環(huán)隊列通常用指針來實現隊列的頭尾相接。（×）3.3.3簡答題1．循環(huán)隊列的優(yōu)點是什么？如何判別它的空和滿？循環(huán)隊列的優(yōu)點是能夠克服“假溢滿”現象。設有循環(huán)隊列sq，隊滿的判別條件為：（sq->rear+1）%maxsize==sq->front;或sq->num==maxsize。隊空的判別條件為：sq->rear==sq->front。2．棧和隊列數據結構各有什么特點，什么情況下用到棧，什么情況下用到隊列？棧和隊列都是操作受限的線性表，棧的運算規(guī)則是“后進先出”，隊列的運算規(guī)則是“先進先出”。棧的應用如數制轉換、遞歸算法的實現等，隊列的應用如樹的層次遍歷等。3．什么是遞歸？遞歸程序有什么優(yōu)缺點？一個函數在結束本函數之前，直接或間接調用函數自身，稱為遞歸。例如，函數f在執(zhí)行中，又調用函數f自身，這稱為直接遞歸；若函數f在執(zhí)行中，調用函數g，而g在執(zhí)行中，又調用函數f，這稱為間接遞歸。在實際應用中，多為直接遞歸，也常簡稱為遞歸。遞歸程序的優(yōu)點是程序結構簡單、清晰，易證明其正確性。缺點是執(zhí)行中占內存空間較多，運行效率低。4．設有編號為1,2,3,4的四輛車，順序進入一個棧式結構的站臺，試寫出這四輛車開出車站的所有可能的順序（每輛車可能入站，可能不入站，時間也可能不等）。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,43214.3課后習題解答###4.3.1選擇題1．下面關于串的敘述錯誤的是（C）。A．串是字符的有限序列B．串既可以采用順序存儲，也可以采用鏈式存儲C．空串是由空格構成的串D．模式匹配是串的一種重要運算2．串的長度是指（B）。A．串中所含不同字母的個數B．串中所含字符的個數C．串中所含不同字符的個數D．串中所含非空格字符的個數3．已知串S=‘aaab’,其Next數組值為（D）。A．0123B．1123C．1231D．12114．二維數組M的成員是6個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10，則存放M至少需要（D）個字節(jié)；M的第8列和第5行共占（A）個字節(jié)；若M按行優(yōu)先方式存儲，元素M[8][5]的起始地址與當M按列優(yōu)先方式存儲時的（C）元素的起始地址一致。（1）A．90B．180C．240D．540（2）A．108B．114C．54D．60（3）A．M[8][5]B．M[3][10]C．M[5][8]D．M[0][9]5．數組A中，每個元素的存儲占3個單元，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內，存放該數組至少需要的單元個數是（C），若該數組按行存放，元素A[8][5]的起始地址是（C），若該數組按列存放，元素A[8][5]的起始地址是（C）。（1）A．80B．100C．240D．270（2）A．SA+141B．SA+144C．SA+222D．SA+225（3）A．SA+141B．SA+180C．SA+117D．SA+2256．稀疏矩陣采用壓縮存儲，一般有（C）兩種方法。A．二維數組和三維數組B．三元組和散列C．三元組表和十字鏈表D．散列和十字鏈表4.3.2判斷題1．串相等是指兩個串的長度相等。（×）2．KMP算法的特點是在模式匹配時指示主串的指針不會變小。（√）3．稀疏矩陣壓縮存儲后，必會失去隨機存取功能。（√）4．數組是線性結構的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。（×）5．若采用三元組存儲稀疏矩陣，把每個元素的行下標和列下標互換，就完成了對該矩陣的轉置運算。（×）6．若一個廣義表的表頭為空表，則此廣義表亦為空表。（×）7．所謂取廣義表的表尾就是返回廣義表中最后一個元素。（×）4.3.3簡答題1．KMP算法較樸素的模式匹配算法有哪些改進?KMP算法主要優(yōu)點是主串指針不回溯。當主串很大不能一次讀入內存且經常發(fā)生部分匹配時，KMP算法的優(yōu)點更為突出。2．設字符串S=‘aabaabaabaac'，P=‘aabaac'。（1）給出S和P的next值和nextval值；（2）若S作主串，P作模式串，試給出利用KMP算法的匹配過程?！窘獯稹浚?）S的next與nextval值分別為012123456789和002002002009，p的next與nextval值分別為012123和002003。（2）利用BF算法的匹配過程：利用KMP算法的匹配過程：第一趟匹配：aabaabaabaac第一趟匹配：aabaabaabaacaabaac(i=6,j=6)aabaac(i=6,j=6)第二趟匹配：aabaabaabaac第二趟匹配：aabaabaabaacaa(i=3,j=2)(aa)baac第三趟匹配：aabaabaabaac第三趟匹配：aabaabaabaaca(i=3,j=1)(成功)(aa)baac第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac(成功)aabaac(i=13,j=7)3．假設按行優(yōu)先存儲整數數組A[9][3][5][8]時，第一個元素的字節(jié)地址是100，每個整數占４個字節(jié)。問下列元素的存儲地址是什么？(1)a0000(2)a1111(3)a3125(4)a8247【解答】(1)LOC(a0000)=100(2)LOC(a1111)=100+(3*5*8*1+5*8*1+8*1+1)*4=776(3)LOC(a3125)=100+(3*5*8*3+5*8*1+8*2+5)*4=1784(4)LOC(a8247)=100+(3*5*8*8+5*8*2+8*4+7)*4=48164．假設一個準對角矩陣：aa11a12a21a22a33a34a43a44….aija2m-1,2m-1a2m-1,2ma2m,2m-1a2m,2m按以下方式存儲于一維數組B[4m]中（m為一個整數）：0123456…k…4m-14ma11a12a21a22a33a34a43…aij…a2m-1,2ma2m,2m-1a2m,2m寫出下標轉換函數k=f(i,j)?！窘獯稹坑深}目可知，每一行有兩個非0元素。當i為奇數時，第i行的元素為：ai,i、ai,(i+1)，此時k=2*(i-1)+j-i=i+j-2當i為偶數時，第i行的元素為：ai,(i-1)、ai,i，此時k=2*(i-1)+j-I+1=i+j-1綜上所述，k=i+j-i%2-1。5．設有n×n的帶寬為3的帶狀矩陣A，將其3條對角線上的元素存于數組B[3][n]中，使得元素B[u][v]=aij，試推導出從（i,j）到(u,v)的下標變換公式?！窘獯稹縰=j-i+1v=j-16．現有如下的稀疏矩陣A（如圖所示），要求畫出以下各種表示方法。（1）三元組表表示法（2）十字鏈表法。000220-15000220-150133000000-60000000091000000028000【解答】（1）三元組表表示法:ijv123456742216651916328（2）十字鏈表法：0012345^0123^455191^^233^34-6^^14226328^^16-15^^2213^7．畫出下列廣義表的頭尾表示存儲結構示意圖。（1）A=((a,b,c),d,(a,b,c))（2）B=(a,(b,(c,d),e),f)（1）111111^1^1d0a1b1c（2）11111^1^10f0a0b0c1^10c0d5.3課后習題解答5.3.1選擇題1．下列說法正確的是（C）。A．二叉樹中任何一個結點的度都為2B．二叉樹的度為2C．一棵二叉樹的度可小于2D．任何一棵二叉樹中至少有一個結點的度為22．以二叉鏈表作為二叉樹的存儲結構，在具有n個結點的二叉鏈表中（n>0），空鏈域的個數為（C）。A．2n-1B．n-1C．n+1D．2n+13．線索化二叉樹中，某結點*p沒有孩子的充要條件是（B）。A．p->lchild=NULLB．p->ltag=1且p->rtag=1C．p->ltag=0D．p->lchild=NULL且p->ltag=14．如果結點A有3個兄弟,而且B是A的雙親,則B的度是（B）。A．3B．4C．5D．15．某二叉樹T有n個結點,設按某種順序對T中的每個結點進行編號，編號值為1,2,...n。且有如下性質:T中任意結點v,其編號等于左子樹上的最小編號減１,而v的右子樹的結點中,其最小編號等于v左子樹上結點的最大編號加１，這是按（B）編號的。A．中序遍歷序列B．先序遍歷序列C．后序遍歷序列D．層次順序6．設F是一個森林，B是由F轉換得到的二叉樹，F中有n個非終端結點,B中右指針域為空的結點有（C）個。A．n-1B．nC．n+1D．n+27．一棵完全二叉樹上有1001個結點，其中葉子結點的個數是（B）。A．500B．501C．490D．4958．設森林F中有三棵樹，第一，第二，第三棵樹的結點個數分別為N1，N2和N3。與森林F對應的二叉樹根結點的右子樹上的結點個數是（D）。A．N1B．N1+N2C．N2D．N2+N39．任何一棵二叉樹的葉結點在先序、中序、后序遍歷序列中的相對次序（A）。A．不發(fā)生改變B．發(fā)生改變C．不能確定D．以上都不對10．若一棵二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則先序遍歷序列為（D）。A．cbedB．decabC．deabcD．cedba11．若一棵二叉樹的先序遍歷序列為abdgcefh，中序遍歷的序列為dgbaechf，則后序遍歷的結果為（D）。A．gcefhaB．gdbecfhaC．bdgaechfD．gdbehfca12．一棵非空二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（AB）。A．所有的結點均無左孩子B．所有的結點均無右孩子C．只有一個葉子結點D．是一棵滿二叉樹13．引入線索二叉樹的目的是（A）。A．加快查找結點的前驅或后繼的速度B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結果唯一14．設高度為h的二叉樹上只有度為０和度為２的結點，則此類二叉樹中所包含的結點數至少為（B）。A．2*hB．2*h-1C．2*h+1D．h+115．一個具有567個結點的二叉樹的高h為（D）。A．9B．10C．9至566之間D．10至567之間16．給一個整數集合{3，5，6，7，9}，與該整數集合對應的哈夫曼樹是（B）。A．B．C．D．9376937653567979536765395.3.2判斷題1．二叉樹是樹的特殊形式。（√）2．由樹轉換成二叉樹，其根結點的右子樹總是空的。（√）3．先根遍歷一棵樹和先序遍歷與該樹對應的二叉樹，其結果不同。（×）4．先根遍歷森林和先序遍歷與該森林對應的二叉樹，其結果不同。（×）5．完全二叉樹中，若一個結點沒有左孩子，則它必是葉子。（√）6．對于有N個結點的二叉樹，其高度為log2N＋1。（×）7．若一個結點是某二叉樹子樹的中序遍歷序列中的最后一個結點，則它必是該子樹的先序遍歷序列中的最后一個結點。（√）8．若一個結點是某二叉樹子樹的中序遍歷序列中的第一個結點，則它必是該子樹的后序遍歷序列中的第一個結點。（√）9．不使用遞歸也可實現二叉樹的先序、中序和后序遍歷。（√）10．先序遍歷二叉樹的序列中，任何結點的子樹的所有結點不一定跟在該結點之后。（×）11．先序和中序遍歷用線索樹方式存儲的二叉樹，不必使用棧。（×）12．在后序線索二叉樹中，在任何情況下都能夠很方便地找到任意結點的后繼。（×）13．哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近。（√）14．在哈夫曼編碼中，出現頻率相同的字符編碼長度也一定相同。（×）15．用一維數組存放二叉樹時，總是以先序遍歷存儲結點。（×）16．由先序序列和后序序列能唯一確定一棵二叉樹。（×）17．由先序序列和中序序列能唯一確定一棵二叉樹。（√）18．對一棵二叉樹進行層次遍歷時，應借助于一個棧。（×）19．完全二叉樹可采用順序存儲結構實現存儲，非完全二叉樹則不能。（×）20．滿二叉樹一定是完全二叉樹，反之未必。（√）5.3.3簡答題1．一棵度為2的樹與一棵二叉樹有何區(qū)別？樹與二叉樹之間有何區(qū)別？【解答】①二叉樹是有序樹，度為2的樹是無序樹，二叉樹的度不一定是2。ADBADBGEHCF(圖1)2．對于圖1所示二叉樹，試給出：（1）它的順序存儲結構示意圖；（2）它的二叉鏈表存儲結構示意圖；（3）它的三叉鏈表存儲結構示意圖?！窘獯稹浚?）順序存儲結構示意圖：ABCDEF^^^G^^H（2）二叉鏈表存儲結構示意圖：（3）三叉鏈表存儲結構示意圖：ABABC^^D^E^^F^G^^H^A^BC^^D^E^^F^G^^H^IDIDEFGCBANMKJH(圖2)（1）雙親數組表示法示意圖；（2）孩子鏈表表示法示意圖；（3）孩子兄弟鏈表表示法示意圖?！窘獯稹浚?）雙親數組表示法示意圖：（2）孩子鏈表表示法示意圖：00A-11B02C03D24E25F16G17H58I29J410K411M312N82^6410^15311^97^12^0A1B2C3D4E5F6G7H8I9J10K11M12N8^（3）孩子兄弟鏈表表示法示意圖：A^A^B^N^^H^C^^GF^EDI^^J^K^^M^4．畫出圖3所示的森林經轉換后所對應的二叉樹，并指出森林中滿足什么條件的結點在二叉樹中是葉子。DDBCIGHAFEJ(圖3)【解答】HHFGIJABCED在二叉樹中某結點所對應的森