2023年人武學(xué)院數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案及期末綜合練習(xí)

第十章內(nèi)部排序一、基本知識(shí)題答案１．排序:將一組雜亂無(wú)序的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)叫做排序。內(nèi)部排序:數(shù)據(jù)存儲(chǔ)在內(nèi)存中，并在內(nèi)存中加以解決的排序方法叫內(nèi)部排序。堆:堆是一個(gè)完全二叉樹(shù),它的每個(gè)結(jié)點(diǎn)相應(yīng)于原始數(shù)據(jù)的一個(gè)元素,且規(guī)定假如一個(gè)結(jié)點(diǎn)有兒子結(jié)點(diǎn),此結(jié)點(diǎn)數(shù)據(jù)必須大于或等于其兒子結(jié)點(diǎn)數(shù)據(jù)。穩(wěn)定排序：一種排序方法,若排序后具有相同關(guān)鍵字的記錄仍維持本來(lái)的相對(duì)順序,則稱之為穩(wěn)定的，否則稱為不穩(wěn)定的。2.回答下面問(wèn)題(1)5000個(gè)無(wú)序的數(shù)據(jù)，希望用最快速度挑選出其中前10個(gè)最大的元素，在快速排序、堆排序、歸并排序和基數(shù)排序中采用哪種方法最佳？為什么？（2）大多數(shù)排序算法都有哪兩個(gè)基本操作？答:(1)采用堆排序最佳。由于以上幾種算法中,快速排序、歸并排序和基數(shù)排序都是在排序結(jié)束后才干擬定數(shù)據(jù)元素的所有順序,而無(wú)法知道排序過(guò)程中部分元素的有序性。堆排序則每次輸出一個(gè)最大（或最小）的元素，然后對(duì)堆進(jìn)行調(diào)整，保證堆頂?shù)脑乜偸怯嘞略刂凶畲螅ɑ蜃钚?的。根據(jù)題意,只要選取前10個(gè)最大的元素，故采用堆排序方法是合適的。(2）兩個(gè)基本操作:比較兩個(gè)關(guān)鍵字的大小、改變指向記錄的指針或移動(dòng)記錄自身。3.3．已知序列{1７,2５，55,43,３,３2,78,6７,91｝,請(qǐng)給出采用冒泡排序法對(duì)該序列作遞增排序時(shí)每一趟的結(jié)果。答:采用冒泡排序法排序時(shí)的各趟結(jié)果如下：初始:17,25，55，43,3，3２，78,６7，９1第1趟:17，2５，43,3,32，55，67,78,9１第2趟：１７，２5，3，３2,4３，55，67,78，9１第3趟:1７，3,25,３2，4３，55,67，７8，91第４趟：３，17,25,32,4３，55，67，７8,91第5趟:３，17，25，32，４3,55，67，78，91第５趟無(wú)元素互換，排序結(jié)束。4．已知序列{4９1，77,57２，１6,9９6,10１，８６3,2５8,68９,32５}，請(qǐng)分別給出采用快速排序、堆排序和基數(shù)排序法對(duì)該序列作遞增排序時(shí)每一趟的結(jié)果。答:采用快速排序法排序時(shí)的各趟結(jié)果如下:初始:4９1,77,572,16,9９6，101，863,2５8，６89,325第1趟:[325,77，258,16,１0１］４９1[863，9９６，689，５７2]第2趟：[10１,７7，258,16]32５，491[86３，9９6,６８9，572]第3趟:[16，7７]1０1[25８]325，491[863,99６，６89，５7２]第4趟:16［77]101[258]325，491[863,996,689,572］第5趟：１６,77，101［２58]３25,４91[８6３，99６，68９,572］第6趟:１６，7７，１01,25８，３25，4９1[863，９9６,689，５72]第7趟：16,77,101,258,３25,491［572,689]86３［996]第８趟:１６,77，101，258，325，4９１,5７２[6８9］863[9９6］第9趟：1６,7７,101，258，３25,4９１,572,689，86３［996］第10趟：16,７7，101，2５8,32５,491，5７2，689,86３,996采用堆排序法排序時(shí)各趟的結(jié)果如下圖所示:(a)初始堆(b)建堆(c)互換9９6和77,輸出99６(d)篩選調(diào)整采用基數(shù)排序法排序時(shí)各趟的結(jié)果如下：初始:４９1,７7，572,1６，99６，10１，863,2５8，689，325第1趟（按個(gè)位排序):４９1，101，572,86３，35２,１6,996，77,258，68９第２趟（按十位排序)：101,16,３52,２58，863,572，77,6８９,49１,996第3趟（按百位排序）:１6,77,10１,2５8，352，491，５7２，689，8６3，99６5.已知序列｛８６，9４，138，62，４1,54,1８，32},請(qǐng)給出采用插入排序法對(duì)該序列作遞增排序時(shí)，每一趟的結(jié)果。答:采用插入排序法排序時(shí)各趟的結(jié)果如下:初始:(86)，9４,13８，62，4１,54,18,32第1趟：(86,94)，138，６２,41，54,18，32第2趟:(86,94,１38）,6２,41,5４,18，32第3趟：(62,８6,９4，138）,41，54，18,３２第４趟：（41,62，86，９４,１３8），54,18，32第5趟:（41,54，６2，86，94,138）,１8,32第6趟:(18,41,54，62，86,94,138）,32第7趟：(１8,３2,41,54,62，８6,94,１３８)6．已知序列｛27,35,11，9,１8，３0，3，２3，35，20}，請(qǐng)給出采用歸并排序法對(duì)該序列作遞增排序時(shí)的每一趟的結(jié)果。答:采用歸并排序法排序時(shí)各趟的結(jié)果如下:初始：27，35,11,9,18,30，３,23,３5，20第１趟：［2７,35］[９,11]［18,3０][3,2３]［20,35]第2趟:[9,１1,27，3５］[3，18,23，3０][20，35]第3趟：［9，11，27，3５］［３，18，２0,２3,３0，35]第4趟:[3,9,11，1８,2０,23，27,3０，３5,35]二、算法設(shè)計(jì)題答案１.二、算法設(shè)計(jì)題1．一個(gè)線性表中的元素為所有為正或者負(fù)整數(shù)，試設(shè)計(jì)一算法,在盡也許少的時(shí)間內(nèi)重排該表，將正、負(fù)整數(shù)分開(kāi)，使線性表中所有負(fù)整數(shù)在正整數(shù)前面。解：本題的算法思想是:設(shè)立兩個(gè)變量分別指向表的首尾，它們分別向中間移動(dòng)，指向表首的?假如碰到正整數(shù),指向表尾的假如碰到負(fù)整數(shù)則互相互換,然后繼續(xù)移動(dòng)直至兩者相遇。實(shí)現(xiàn)本?題功能的算法如下:ｖoｉdpart（iｎｔarray[]，iｎｔｎ){?ｉｎｔi,j；?i＝1; j=ｎ;wｈｉｌｅ(ｉ＜j） ｛whｉlｅ(i＜j＆&ａrray[i]<0) ??ｉ++;? ｗｈile（ｉ<ｊ&&ａrｒａy[j］>=０)?? ｊ－－; ?if(i＜j) {arｒay[0]=ａrray［i]； ??arrａｙ[i]=arrａy［ｊ];???array[ｊ］＝aｒｒay[0］;? }?}}2.設(shè)計(jì)一個(gè)用單鏈表作存儲(chǔ)結(jié)構(gòu)的直接插入排序算法。解：實(shí)現(xiàn)本題功能的算法如下：vｏｉｄiｎsｅrｔｓort（nodｅ＊head){?nｏｄe*p,*ｑ，*pre；?ｐre=ｈeaｄ;?p=heaｄ->neｘt;/*p指向待插入的元素*/?wｈile(p！=NUＬL)?{??q＝heａｄ; ?if(p->keｙ＜ｑ->key)/*插到表首＊/{pre->next=p->nexｔ;? p->ｎext=ｈead;???hｅad=p;? }? eｌｓｅ??{??wｈile(q->next!=p＆＆q->next-＞ｋey<ｐ－>kｅｙ) ??q=q-＞nexｔ; ?if(q->nexｔ＝=p） ?{ ??pre=p;p=p->next; }???elsｅ? ?｛prｅ->neｘt=p->next;? ?p－>next＝q->neｘｔ; ? ｑ->nｅｘｔ＝ｐ;? ??p=pｒe->ｎexｔ；???}??}?｝}3.試設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)雙向冒泡排序。(雙向冒泡排序就是在排序的過(guò)程中交替改變掃描方向。）解：實(shí)現(xiàn)本題功能的算法如下：voidｄbuｂbｌesort(ｓqliｓtｒ,iｎtｎ){ inti，j,fｌag; ｆlaｇ=1; i=1;?while（flag!=0)?{? flａg=0; ｆｏr(j=i;j＜n-i；j＋+){ ?if（ｒ[ｊ］>r[j+1]) ?{ ? ?flag＝1;?? r[０]=ｒ[ｊ］; ?? r[j]=r[j+1];?? r[ｊ＋１]=r[０］;?? }??｝??ｆor(j=ｎ-ｉ；j>i;j--){ ? if(r[j]<r［j-1])?? {ｆlag=1;?? ?ｒ[0]=r[j]；????ｒ[j]=r[j-１]; ?ｒ[ｊ-1]=r[0];? ?} }?? i+＋;?}}4.設(shè)一個(gè)一維數(shù)組Ａ［n］中存儲(chǔ)了n個(gè)互不相同的整數(shù),且這些整數(shù)的值都在０到n-1之間，即A中存儲(chǔ)了從0到n－1這n個(gè)整數(shù)。試編寫(xiě)一算法將A排序，結(jié)果存放在數(shù)組B[ｎ]中，規(guī)定算法的時(shí)間復(fù)雜性為O(n)。解:實(shí)現(xiàn)本題功能的算法如下：voidsｏrt(intＡ［n］，iｎtB[n］){?iｎti； fｏr(ｉ=０;i＜n；ｉ＋+） ?B[A［i]]=A[ｉ］;}第九章一、基礎(chǔ)知識(shí)題1.(１)查找：查找又稱為查詢或檢索,是在一批記錄中依照某個(gè)域的指定域值,找出相應(yīng)的記錄的操作。(2)樹(shù)型查找：將原始數(shù)據(jù)表達(dá)成二叉排序樹(shù)，樹(shù)的每個(gè)結(jié)點(diǎn)相應(yīng)一個(gè)記錄,運(yùn)用此二叉排序樹(shù)進(jìn)行類似于二分查找思想的數(shù)據(jù)查找，這種查找方法稱為樹(shù)型查找。(3）平衡因子：二叉樹(shù)中每一結(jié)點(diǎn)的左子樹(shù)高度減右子樹(shù)高度為該結(jié)點(diǎn)的平衡因子。（４)散列函數(shù)：根據(jù)關(guān)鍵字求存儲(chǔ)地址的函數(shù)稱為散列函數(shù)。(５)兩個(gè)不同的關(guān)鍵字，其散列函數(shù)值相同,因而被映射到同一個(gè)表位置上的現(xiàn)象稱為沖突。２.設(shè)有序表為{a,b,c,d，ｅ,f,g}，請(qǐng)分別畫(huà)出對(duì)給定值f,g和h進(jìn)行拆半查找的過(guò)程。答：查找f的過(guò)程如下:查找成功，找到k＝f值查找g的過(guò)程如下：查找成功，找到k=g值查找h的過(guò)程如下:試述順序查找法、二分查找法和分塊查找法對(duì)被查找表中元素的規(guī)定，每種查找法對(duì)長(zhǎng)度為n的表的等概率查找長(zhǎng)度是多少答:順序查找法:表中元素可以任意存放。查找成功的平均查找長(zhǎng)度為(ｎ+1)／2。二分查找法：表中元素必須以關(guān)鍵字的值遞增或遞減地存放且只能以順序表存放。查找成功的平均查找長(zhǎng)度為log2（n+1)－１。分塊查找法:表中每塊內(nèi)的元素可以任意存放,但塊與塊之間必須按關(guān)鍵字的大小遞增或遞減地存放,即前一塊內(nèi)所有元素的關(guān)鍵字不能大(或小)于后一塊內(nèi)任意一個(gè)元素的關(guān)鍵字。若用順序查找擬定所在塊,平均查找長(zhǎng)度為1／２（n/s+s)+1;若用二分查找擬定所在塊,平均查找長(zhǎng)度為lｏｇ2(ｎ/ｓ+1）＋s/2。4.設(shè)散列表長(zhǎng)m=14，哈希函數(shù)為H(k)＝ｋmod11,表中一共有8個(gè)元素{15,27,50,73,49,61，37,6０｝，試畫(huà)出采用二次探測(cè)法解決沖突的散列表。答:采用二次探測(cè)法解決沖突的散列表如下：5.線性表的關(guān)鍵字集合為{113,1２,1８0,138,９2,67,94,13４,２52,６，7０,323，60｝，共有1３個(gè)元素,已知散列函數(shù)為：H（k）=kmod13,采用鏈接表解決沖突，試設(shè)計(jì)這種鏈表結(jié)構(gòu)。答:由題意，可得:H(113）=113%1３=９H(１2)=12％13＝1２H(１８0）=180%１3＝１１H(１３8)=138%13=８H(９2)=９2%13=1H(67)＝67%１3=2H(94)=94%１3=３H(13４)=1３4%1３=4H(252）=２52%13＝5H(６)=6％13＝6H（70）=７0%13=5Ｈ（323）=３23%13=１1H（60）=60%13=8鏈接表法的散列表如下圖所示:6.設(shè)關(guān)鍵字集合為{２7,49,７9，5,37，1,56,65,83}，散列函數(shù)為：H（k）=kmod7，散列表長(zhǎng)度m＝１0，起始地址為０,分別用線性探測(cè)和鏈接表法來(lái)解決沖突。試畫(huà)出相應(yīng)的散列表。答：線性探測(cè)法的散列表如下圖所示：鏈接表法的散列表如下圖所示：二、算法設(shè)計(jì)題1.從小到大排列的，試寫(xiě)出對(duì)此鏈表的查找算法,并說(shuō)明是否可以采用折半查找。解：實(shí)現(xiàn)本題功能的算法如下，假如查找成功,則返回指向關(guān)鍵字為x的結(jié)點(diǎn)的指針，否則返回ＮULL。noｄｅ＊sqseａrｃh（nodｅ*heａｄ，intx）{nｏdｅ*p=ｈead;?ｗhile(p!=ＮUＬL）? if(x>p-＞key) ??p=p->ｌiｎｋ；elｓｅiｆ（ｘ＝=p->kｅy)? ?ｒｅturnｐ;eｌｓｅ{p=NULL;retuｒnｐ;??}}雖然鏈表中的結(jié)點(diǎn)是按遞增順序排列的,但是其存儲(chǔ)結(jié)構(gòu)為單鏈表，查找結(jié)點(diǎn)時(shí)只能從頭指針開(kāi)始逐步進(jìn)行搜索，所以不能用折半查找。2．假如線性表中各結(jié)點(diǎn)查找概率不等,則可以使用下面的策略提高順序表的查找效率:假如找到指定的結(jié)點(diǎn),則將該結(jié)點(diǎn)和其前趨(若存在）結(jié)點(diǎn)互換,使得經(jīng)常被查找的結(jié)點(diǎn)盡量位于表的前端。試對(duì)線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)寫(xiě)出實(shí)現(xiàn)上述策略的順序查找算法(注意查找時(shí)必須從表頭開(kāi)始向后掃描）。解:采用順序存儲(chǔ)結(jié)構(gòu)的算法如下,設(shè)記錄存儲(chǔ)在線性表的１~n單元中。假如查找成功，返回關(guān)鍵字為k的記錄在線性表中的位置，假如失敗則返回0。intseｑsearch(sqlｉsｔr,intn,iｎtk）{ inti,ｊ;?i=1;?while（(r[i］.key！＝k)&&(i＜=n)) i＋+；?if（i<＝ｎ)｛ r[0]＝r[i]； r[i]=r[i－1］;r［ｉ-１]=r［i];??i－－; return(i); ｝?else ?reｔurn(0);}采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的算法如下。假如查找成功，則返回指向關(guān)鍵字為ｋ的結(jié)點(diǎn)的指針,否則返回ＮULL。nodｅ＊sｅqseaｒｃｈ（node*head,ｉntk){?iｆ(head－＞key=＝k)ｒeturｎ(hｅad);?else{??node＊p,＊q;intx；p=ｈｅａd; ?ｑ＝head->ｌink;? ｗhile(q!=NULL&＆ｑ->kｅy!=k）??{???p=q；? ?ｑ=ｑ－>ｌinｋ; ｝ if(ｑ!=ＮUＬL)｛ ?x=p－>key;? ?p－＞ｋｅy=q-＞kｅy； ? q->ｋey＝ｘ; ?q=p; ?} retｕrｎ(q）；?}}3.試設(shè)計(jì)一個(gè)在用開(kāi)放地址法解決沖突的散列表上刪除一個(gè)指定結(jié)點(diǎn)的算法。解:本題的算法思想是：一方面計(jì)算要?jiǎng)h除的關(guān)鍵字為k的記錄所在的位置，將其置為空（即刪除）,然后運(yùn)用線性探測(cè)法查找是否有與k發(fā)生沖突而存儲(chǔ)到下一地址的記錄,假如有則將記錄移到本來(lái)k所在的位置，直至表中沒(méi)有與k沖突的記錄為止。實(shí)現(xiàn)本題功能的算法如下：vｏｉdｄｅlｅｔe(sqlisｔｒ,ｉntｎ，intk）{ｉnth，h0，h1;?ｈ＝k%n;?whｉle（r[ｈ].key！=k）? h＝(h+1)％n；ｒ［h]＝NＵLL;?h0=h; h1=(ｈ+１)%ｎ；?whilｅ（h1!=h)?{while(r［h1].key%n!=ｈ)? ｈ1＝（h1+1)%ｎ； r［h0]=r[h１]； ｒ[h1]=NULL; h0=h1; ｈ1＝（h１+１)%n;?}}4.設(shè)給定的散列表存儲(chǔ)空間為H[1~ｍ］，每個(gè)單元可存放一個(gè)記錄，H[i](1≤ｉ≤m)的初始值為零，選取散列函數(shù)為H(R．kｅy),其中key為記錄R的關(guān)鍵字,解決沖突方法為線性探測(cè)法,編寫(xiě)一個(gè)函數(shù)將某記錄R填入到散列表H中。解：本題的算法思想：先計(jì)算地址H（R.key）,假如沒(méi)有沖突,則直接填入；否則運(yùn)用線性探測(cè)法求出下一地址，直到找到一個(gè)為零的地址，然后填入。實(shí)現(xiàn)本題功能的函數(shù)如下:vｏidiｎsｅrt（recｏｒdH，inｔｍ,rｅｃoｒdＲ){ iｎti;?ｉ=H(R.key)；?ｉf(H［i]＝＝NＵLL)? Ｈ[i]=Ｒ;elｓe ｛ while(H[ｉ]!=ＮUＬL） ｛?? i=(i+１)%(ｍ+1)； }??Ｈ[i]＝R; }}第七章一、基本知識(shí)題1.圖的邏輯結(jié)構(gòu)特點(diǎn)是什么?什么是無(wú)向圖和有向圖？什么是子圖？什么是網(wǎng)絡(luò)?答：圖是比樹(shù)更為復(fù)雜的一種非線性數(shù)據(jù)結(jié)構(gòu),在圖結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)都可以和其它任何結(jié)點(diǎn)相連接。無(wú)向圖:對(duì)于一個(gè)圖Ｇ，若邊集合E（G）為無(wú)向邊的集合，則稱該圖為無(wú)向圖。有向圖:對(duì)于一個(gè)圖G，若邊集合E（G)為有向邊的集合，則稱該圖為有向圖。子圖:設(shè)有兩個(gè)圖Ｇ＝(V,E)和G’＝(V’,E’)，若Ｖ(G’)是Ｖ（G）的子集，且E（G’)是Ｅ(G)的子集，則稱G’是G的子圖(Subgraｐh)。網(wǎng)絡(luò)：有些圖，相應(yīng)每條邊有一相應(yīng)的數(shù)值,這個(gè)數(shù)值叫做該邊的權(quán)。邊上帶權(quán)的圖稱為帶權(quán)圖,也稱為網(wǎng)絡(luò)。2.什么是頂點(diǎn)的度？什么是途徑？什么是連通圖和非連通圖？什么是非連通圖的連通分量?答：頂點(diǎn)的度：圖中與每個(gè)頂點(diǎn)相連的邊數(shù)，叫該頂點(diǎn)的度。在一個(gè)圖中,若從某頂點(diǎn)Ｖp出發(fā),沿一些邊通過(guò)頂點(diǎn)V1,V2，…,Vm到達(dá)，Vq，則稱頂點(diǎn)序列（Vｐ,V1,V２,…,Ｖｍ,Vq）為從Vp到Vq的途徑。在無(wú)向圖中,假如從頂點(diǎn)Vi到頂點(diǎn)Ｖj之間有途徑，則稱這兩個(gè)頂點(diǎn)是連通的。假如圖中任意一對(duì)頂點(diǎn)都是連通的,則稱此圖是連通圖。非連通圖的連通分量:非連通圖的每一個(gè)連通的部分叫連通分量。3.給出圖６.25所示的無(wú)向圖G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。答:圖G所相應(yīng)的鄰接矩陣如下:圖G所相應(yīng)的鄰接表如下：圖254.假設(shè)圖的頂點(diǎn)是A、B……請(qǐng)根據(jù)下面的鄰接矩陣畫(huà)出相應(yīng)的無(wú)向圖或有向圖。答:(a)所相應(yīng)的無(wú)向圖如下圖(a）所示,(ｂ）所相應(yīng)的有向圖如下圖(ｂ)所示:5.5.分別給出圖6．26所示G圖的深度優(yōu)先搜索和廣度優(yōu)先搜索得到的頂點(diǎn)訪問(wèn)序列。圖26答：深度優(yōu)先搜索得到的頂點(diǎn)訪問(wèn)序列:0、1、3、7、8、4、9、5、6、2;?廣度優(yōu)先搜索得到的頂點(diǎn)訪問(wèn)序列:0、１、2、３、4、５、6、7、8、9。６.應(yīng)用ｐriｍ算法求圖6．27所示帶權(quán)連通圖的最小生成樹(shù)。答:該圖的最小生成樹(shù)如下：????? ? ? ? 圖27?７.寫(xiě)出圖6．28所示有向圖的拓樸排序序列答:該有向圖的拓樸排序序列為:3、１、4、5、２、６。二、算法設(shè)計(jì)題 ? ? ? 圖28二、算法設(shè)計(jì)題答案1.如圖6.2９所示圖G,試給出其相應(yīng)的鄰接表,并寫(xiě)出深度優(yōu)先算法。解:該圖相應(yīng)的鄰接表如下:深度優(yōu)先算法：ｖoiddfsgｒaph（adjlistadj,ｉntn)/＊深度優(yōu)先遍歷整個(gè)圖*/{ iｎti; for（i=1;i＜＝n;ｉ++） ?vｉsiteｄ[i］=0; for(ｉ＝1;i＜=n;i++)??if(！visiteｄ[i］)?? dｆs(adj，i）;}voiｄdfs(adjｌistadｊ，intv)/*以v為出發(fā)點(diǎn),對(duì)圖進(jìn)行dfｓ遍歷*/{structedgenode*p;viｓited[ｖ]=1;printｆ(＂％d",v）;p＝adj［v]→ｌink;whiｌｅ(p！=NULL){if（visitｅd[p→adjveｘ]＝=0)?? dｆs(ａdjlｉst，p→adjvex）;??p=p→nｅｘt；?}｝2.如圖6.2９所示圖G,試給出其相應(yīng)的鄰接矩陣，并寫(xiě)出廣度優(yōu)先算法。解：該圖相應(yīng)的鄰接矩陣如下:廣度優(yōu)先算法:voidｂfｓgｒaph（ｉnｔadjａｒray[n］[ｎ］,ｉntn）/＊廣度優(yōu)先遍歷整個(gè)圖*/{?inti;?fｏr(i=0；i<n；ｉ＋+)??visited[i]＝０;?for(ｉ=０;ｉ<ｎ;i++) 圖2９? if(!ｖisｉｔｅd[i］) bｆs(ａdjaｒray,i);}ｖoidbfs(intadｊａｒrａy［][],intｖ)/＊以v為出發(fā)點(diǎn),對(duì)圖進(jìn)行ｂfｓ遍歷*/｛ ｉｎti，j; ｑueuｅｑ;?ｐｒintf（"%d",ｖ）;?viｓｉtｅd[v]=1;?eｎquｅuｅ(＆q,v); wｈiｌe（！queuｅe(cuò)ｍty(&q))?{ ?i=dequeｕｅ(&q)；ｆor(j＝0;j<n；j＋+)? if(aｄjaｒray[i][j］=＝1&＆?。鰅sｉteｄ[j]) ? {??? printf("%d",ｊ);?? ?visited［ｊ]＝1；????ｅnqueue（＆ｑ,j）;? }?}}3.編寫(xiě)一個(gè)函數(shù)通過(guò)與用戶交互建立一個(gè)有向圖的鄰接表。解:實(shí)現(xiàn)本題功能的算法如下：ｖｏiｄcreatｅｇraph(aｄjlｉstｇ)｛?iｎte,i，s,d,n;stｒuｃtedgenodｅ*p; pｒinｔf("請(qǐng)輸入結(jié)點(diǎn)數(shù)(n)和邊數(shù)(e):\ｎ"）; scanf（"%d,%d",&n,&e); foｒ(ｉ=1;i＜=n；i＋+){prｉnｔf("\ｎ請(qǐng)輸入第%d個(gè)頂點(diǎn)信息:"，i）;ｓcａnf("％c",&ｇ[i]．dａｔa)；g［ｉ].liｎk＝NULL;?} for(ｉ＝1;ｉ<＝ｅ;i++)?{ｐrｉnｔf("＼n請(qǐng)輸入第%d條邊起點(diǎn)序號(hào)，終點(diǎn)序號(hào):",i)；??scanf("%ｄ,％ｄ",&s，＆ｄ)；? p=(strｕctedｇeｎode*)malloc(sizeｏf（edgenode)）；? p→aｄjvｅx=d; p→nｅxt=g[s]．linｋ;? ｇ[s］．liｎk=p;?}}4．編寫(xiě)一個(gè)無(wú)向圖的鄰接矩陣轉(zhuǎn)換成鄰接表的算法。解:本題的算法思想是：逐個(gè)掃描鄰接矩陣的各個(gè)元素,如第i行第j列的元素為1，則相應(yīng)的鄰接表的第i個(gè)單鏈表上增長(zhǎng)一個(gè)j結(jié)點(diǎn)。實(shí)現(xiàn)本題功能的算法如下:ｖｏｉdtｒansform(intaｄjaｒrａｙ［n][n],aｄｊlistadj)｛?inti,j;?edgenode*ｐ; for(i=０;ｉ<n;i++) {??ａdj[ｉ]．dａt(yī)a＝i;aｄj［i］．ｌink=NUＬL；}foｒ(ｉ=０;ｉ<n；i＋+) for(j＝0;j<n;ｊ+＋) ?{ｉｆ（adｊarrａy［i][j]=＝1)???｛p=(edgenodｅ*)malｌoc(sizｅof(edgenｏde）);? ｐ→adjvex=j;? ?p→ｎｅｘｔ=adj[i］.link; ? ａdj[ｉ]．lｉnk=p;?? } }}５.已知一個(gè)有n個(gè)頂點(diǎn)的有向圖的鄰接表，設(shè)計(jì)算法分別實(shí)現(xiàn)1）求出圖中每個(gè)頂點(diǎn)的出度。2)求出圖中每個(gè)頂點(diǎn)的入度。３)求出圖中出度最大的一個(gè)頂點(diǎn),輸出其頂點(diǎn)序號(hào)。4）計(jì)算圖中出度為0的頂點(diǎn)個(gè)數(shù)。解:（1）本題的算法思想是:計(jì)算出鄰接表中第i個(gè)單鏈表的結(jié)點(diǎn)數(shù)，即為i頂點(diǎn)的出度。求頂點(diǎn)的出度數(shù)的算法如下:ｉntoutdegrｅe(cuò)(aｄjlｉstadj,intv){iｎtdegree=0; edgｅnｏdｅ*ｐ; p=ａdｊ[v].lｉnk;?while(p!=ＮULL）?{dｅｇｒeｅ++;ｐ＝ｐ->neｘｔ;?}retuｒndeｇreｅ;}voidpｒｉｎtout(ａdjlｉstadｊ，intn)｛?inｔｉ,deｇrｅe(cuò);?priｎtf(＂Tｈeoutdegreｅsａrｅ:\n＂); for(i=0；i<n;i++)?{?deｇree＝oｕtｄｅgree（ａdj,ｉ）； ?priｎtｆ("（％d,%ｄ）＂,ｉ,degｒｅe(cuò)); }}（２)本題的算法思想是：計(jì)算出整個(gè)鄰接表中所具有的結(jié)點(diǎn)為i的結(jié)點(diǎn)數(shù),這就是ｉ頂點(diǎn)的入度。求頂點(diǎn)的入度數(shù)的算法：intindegree（ａdjlｉstadｊ,intn,intv)｛ intｉ，ｊ,degree;?edｇenode＊ｐ； for(i＝０;i<n;ｉ++)?{ ?p=ａdｊ[i].lｉnk; ?while(p!=NULL){ ? iｆ(p-＞ａdjvex==ｖ) ?dｅgreｅ++；? ?p＝ｐ－>next;? } }?reｔurnｄｅgree;}voｉdprｉｎtin(adjlistadj，intn){ ｉntｉ,dｅgree; printf(＂Tｈｅindeｇｒeｅsａre:\n")； fｏｒ（i=0；i<ｎ;i++） {?ｄegｒeｅ＝ｉndegree(adj,n,i)； pｒiｎtf(＂(%d,％d)",ｉ,ｄegｒee）； }}(3）求最大出度的算法:voｉdｍａxoutdegrｅe(cuò)(adｊlistadj,intn){ iｎtmａｘｄegreｅ=０,maxv=0,degｒee，i;?fｏr（i=０;i＜n;i++)?{??ｄegｒeｅ＝ｏutｄeｇreｅ(adj,ｉ)；ｉf(deｇree>mａxdegｒee) ｛???mａxdeｇree=degree； ? ｍａxv=i; ?} } ｐｒintf("maxouｔdeｇrｅe(cuò)=%d,ｍaxvｅrteｘ=%d",maxｄegrｅe(cuò),maxv);}(4)求出度數(shù)為0的頂點(diǎn)數(shù)的算法：intoｕtzｅｒo(aｄｊlｉstａdｊ，intｎ){ iｎtnum＝0,i； ｆor（ｉ=0;i<n;ｉ++） { ?ｉf(outdｅgree(adj,i）=＝0)???num+＋;?} returnnum;}第六章一、基礎(chǔ)知識(shí)題1.就如圖5．21所示的樹(shù)回答下面問(wèn)題：1)哪個(gè)是根結(jié)點(diǎn)？２）哪些是葉子結(jié)點(diǎn)?３)哪個(gè)是E的父結(jié)點(diǎn)？4）哪些是Ｅ的子孫結(jié)點(diǎn)？５)哪些是E的兄弟結(jié)點(diǎn)?哪些是Ｃ的兄弟結(jié)點(diǎn)？6)結(jié)點(diǎn)B和結(jié)點(diǎn)I的層數(shù)分別是多少？７）樹(shù)的深度是多少？8）以結(jié)點(diǎn)G為根的子樹(shù)的深度是多少?9)樹(shù)的度是多少？答:１）A是根結(jié)點(diǎn)２)D、H、I、J、F、G是葉子結(jié)點(diǎn)3)Ｂ是E的父結(jié)點(diǎn)4)H、I、J是E的子孫結(jié)點(diǎn)5）D是Ｅ的兄弟結(jié)點(diǎn),B是C的兄弟結(jié)點(diǎn)6)B的層數(shù)是2,I的層數(shù)是47）樹(shù)的深度是48）以結(jié)點(diǎn)G為根的子樹(shù)的深度是１9)樹(shù)的度是32.分別畫(huà)出含3個(gè)結(jié)點(diǎn)的樹(shù)與二叉樹(shù)的所有不同形態(tài)。答：3個(gè)結(jié)點(diǎn)的樹(shù): 3個(gè)結(jié)點(diǎn)的二叉樹(shù):3.高度為ｈ的完全二叉樹(shù)至少有多少個(gè)結(jié)點(diǎn)？最多有多少個(gè)結(jié)點(diǎn)?答：高度為ｈ的完全二叉樹(shù)至少有個(gè)結(jié)點(diǎn)，最多有個(gè)結(jié)點(diǎn)。4.采用順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法分別畫(huà)出圖５.２2所示二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。答:該二叉樹(shù)的順序存儲(chǔ):該二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ):5.分別寫(xiě)出圖5.22所示二叉樹(shù)的前序、中序和后序遍歷序列。圖22答:先序遍歷序列:1、2、4、７、３、5、8、6、９中序遍歷序列：7、4、2、1、8、５、3、6、9后序遍歷序列:7、4、2、8、５、9、６、3、１6.若二叉樹(shù)中各結(jié)點(diǎn)值均不相同。1)已知一個(gè)二叉樹(shù)的中序和后序遍歷序列分別為ＧDHBAECIＦ和ＧHDBEIFCA,請(qǐng)畫(huà)出此二叉樹(shù)。2)已知一個(gè)二叉樹(shù)的前序和中序分別為ＡBＣDEＦＧＨ和BDCEAFＨG,請(qǐng)畫(huà)出此二叉樹(shù)。答：7．一個(gè)二叉樹(shù)如圖5.２３所示,分別寫(xiě)出其前序、中序、后序的遍歷序列。答：先序遍歷序列:A、Ｂ、D、E、F、C、G中序遍歷序列：D、F、Ｅ、B、A、G、C后序遍歷序列:F、Ｅ、D、Ｂ、G、Ｃ、A８.輸入一個(gè)正整數(shù)序列｛55,３4,18,88，1１９,１1，76,9,９７,９９,46｝,試構(gòu)造一個(gè)二叉排序樹(shù)。9.有一份電文中共使用5個(gè)字符：ａ、b、c、ｄ、ｅ,它們的出現(xiàn)頻率依次為5、2、1、6、4。試畫(huà)出相應(yīng)的哈夫曼樹(shù),并求出每個(gè)字符的哈夫曼編碼。第8題 各字符相應(yīng)的哈夫曼編碼如下：a:10,b:001,c：０00,d:1１,e：０1二、算法設(shè)計(jì)題答案1.一個(gè)二叉樹(shù)以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ),分別給出求二叉樹(shù)結(jié)點(diǎn)總數(shù)和葉子結(jié)點(diǎn)總數(shù)的算法。解：求二叉樹(shù)結(jié)點(diǎn)總數(shù)的算法如下：iｎtCounｔNoｄｅ(btree*t,inｔnum）/＊nuｍ初值為0*／{if(t!=NULL)?{ｎｕm＋+;??ｎum=ＣouｎtNode(t-＞lｅft,num)；??nuｍ=ＣoｕnｔＮoｄe(t->ｒighｔ,nｕm)； }?ｒetｕrnnuｍ;}求二叉樹(shù)葉子結(jié)點(diǎn)總數(shù)的算法如下：ｉｎtＣoｕｎtLeａf(btｒee＊t,inｔnuｍ)／*nuｍ初值為0*/{if(ｔ!=NＵＬL)?{ｉf(ｔ－>ｌefｔ==NULL＆&t-＞rｉght＝=NUＬL) ? nｕm＋+;? num=CｏuｎtＬeａf（t-＞left，num)；??num=CｏuｎtLeaf（t->righｔ,nｕｍ);?} rｅｔurnnum;}2.2．一個(gè)二叉樹(shù)以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ),寫(xiě)出在二叉樹(shù)中查找值為x的結(jié)點(diǎn)的算法。解:本題可以用先序、中序和后序遍歷中的任意一種遍歷，只要將遍歷算法中的訪問(wèn)根結(jié)點(diǎn)改為判斷其值是否等于x。下面是用中序遍歷求解的算法，函數(shù)返回值為ｘ的結(jié)點(diǎn)的地址,若沒(méi)有找到則返回空。btree*seａｒｃh(btrｅe(cuò)*t,ｉntx,ｂtreｅｐ)/*ｐ的初值為NULL*/{ iｆ（ｔ!＝NUＬL）{ p=search(t->left,x,ｐ); ?if(t－>dａt(yī)a==x）???p=t；/*找到x的地址放在ｐ中＊/? p＝ｓeａｒch(t->rｉght，x，p）;?}returnp；}３.設(shè)計(jì)一個(gè)算法將一個(gè)以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉樹(shù)，按順序方式存儲(chǔ)到一維數(shù)組中。解:這是一個(gè)遞歸算法，如下:vｏidcreate(btｒｅe(cuò)*t,ｉnttree[],inti)｛ if(t!=NUＬL） { ?trｅe(cuò)[i]=t->data; ｃrｅａｔe(t－>left,tｒｅｅ,２*i）； ?cｒｅａt(yī)e(ｔ->rｉgｈt，tree,２*i＋1); }}4.假設(shè)二叉排序樹(shù)t的各元素值均不相同，設(shè)計(jì)一個(gè)算法按遞增順序打印各元素值。解:按中序序列遍歷二叉排序樹(shù)即按遞增順序遍歷，所以遞增打印二叉排序樹(shù)各元素值的函數(shù)如下:ｖoiｄiｎoｒder(btree＊t)｛?ｉf（t!=NULL) {??ｉnｏrder（ｔ－>ｌｅｆt); ?pｒinｔf（"%ｄ＂,t->daｔa）;??inordｅr(t-＞righｔ）; }｝5.已知一個(gè)中序線索二叉樹(shù),試編寫(xiě)中序遍歷的非遞歸算法。解:在中序線索二叉樹(shù)中進(jìn)行非遞歸中序遍歷，只要從頭結(jié)點(diǎn)出發(fā),反復(fù)找到結(jié)點(diǎn)的后繼,直至結(jié)束即可。在中序線索二叉樹(shù)中求結(jié)點(diǎn)后繼的算法如下:ｔｂtree＊sｕcc(tｂtree*p）{ btrｅe(cuò)*q； if(p->rtａｇ==１) retｕrn（p->riｇht）;ｅlse?{ q=p-＞right；? while（q->ltag=＝0) ?q=q－＞left; retｕrｎ(q);?｝}由此得到中序遍歷線索二叉樹(shù)的非遞歸算法如下：voidthｉｎｏrder(tbｔreｅ＊p){if(p!＝ＮULL） {wｈile(p->ｌtag==0) ??p=p->lｅft；? do{???ｐrintf("%ｄ"，ｐ-＞ｄaｔa); ??p＝succ(ｐ）； ｝while(ｐ!＝ＮULL）;?｝}第五章A[10][20]采用列為主序存儲(chǔ)，每個(gè)元素占1個(gè)單元,A［０]［０]的地址為200,則A[6][1２］的地址是多少？3２62.稀疏矩陣m×n采用三元組順序表存儲(chǔ)結(jié)構(gòu),非零元個(gè)數(shù)ｔｕ滿足什么條件時(shí)，該存儲(chǔ)結(jié)構(gòu)才故意義?tu<m*n/3３.二維數(shù)組A［10..２0]［５．.10]采用行為主序存儲(chǔ),每個(gè)元素占4個(gè)單元,A[10][5]的地址為1000,則A[１８][9]的地址是多少?(１20８)４.稀疏矩陣的三元組順序表存儲(chǔ)結(jié)構(gòu)是隨機(jī)存儲(chǔ)結(jié)構(gòu)嗎?為什么?(不是）５.廣義表((a,b，c，d）)的表頭和表尾分別是什么?((a,ｂ,c,d）;空表)6.廣義表(（a),((ｂ）,c)，(((d)）))的長(zhǎng)度和深度分別是多少?(3，4)第一章數(shù)據(jù)物理結(jié)構(gòu)算法二、簡(jiǎn)答一、名詞解釋數(shù)據(jù):就是一切可以由計(jì)算機(jī)接受和解決的對(duì)象。數(shù)據(jù)項(xiàng)：是數(shù)據(jù)的不可分割的最小單位，在有些場(chǎng)合下，數(shù)據(jù)項(xiàng)又稱為字段或域。數(shù)據(jù)元素:是數(shù)據(jù)的基本單位,在程序中作為一個(gè)整體加以考慮和解決，也稱為元素、頂點(diǎn)或記錄。它可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的互相關(guān)系,即數(shù)據(jù)的組織形式，它涉及數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三個(gè)方面的內(nèi)容。數(shù)據(jù)邏輯結(jié)構(gòu):是指數(shù)據(jù)元素之間的邏輯關(guān)系，是從邏輯上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān),獨(dú)立于計(jì)算機(jī)。數(shù)據(jù)物理結(jié)構(gòu)：是指數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表達(dá)，是數(shù)據(jù)的邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)，是依賴于計(jì)算機(jī)語(yǔ)言的。算法:是對(duì)特定問(wèn)題求解環(huán)節(jié)的一種描述。它是一個(gè)有窮的規(guī)則序列,這些規(guī)則決定了解決某一特定問(wèn)題的一系列運(yùn)算。由此問(wèn)題相關(guān)的一定輸入，計(jì)算機(jī)依照這些規(guī)則進(jìn)行計(jì)算和解決，通過(guò)有限的計(jì)算環(huán)節(jié)后能得到一定的輸出。算法的時(shí)間復(fù)雜性:是該算法的時(shí)間花費(fèi),它是該算法所求解問(wèn)題規(guī)模ｎ的函數(shù)。當(dāng)n趨向無(wú)窮大時(shí),我們把時(shí)間復(fù)雜性T（n)的數(shù)量級(jí)稱為算法的漸進(jìn)時(shí)間復(fù)雜性。二、簡(jiǎn)答題1.算法分析的目的是什么？答:對(duì)算法進(jìn)行分析的目的有兩個(gè)：第一個(gè)目的是可以從解決同一問(wèn)題的不同算法中區(qū)分相對(duì)優(yōu)劣，選出較為合用的一種;第二個(gè)目的是有助于設(shè)計(jì)人員考慮對(duì)現(xiàn)有算法進(jìn)行改善或設(shè)計(jì)出新的算法。2.什么是算法的最壞和平均時(shí)間復(fù)雜性?答:算法的最壞時(shí)間復(fù)雜性是研究各種輸入中運(yùn)算最慢的一種情況下的運(yùn)算時(shí)間；平均時(shí)間復(fù)雜性是研究同樣的n值時(shí)各種也許的輸入,取它們運(yùn)算時(shí)間的平均值。三、答案１.三、分析下列算法的時(shí)間復(fù)雜性:1.ｓuｍ=0;for（i=1;i<=n;i++){ｓum＝suｍ+i;}答：該程序段的時(shí)間復(fù)雜性為T（ｎ)＝O(ｎ)。2．2.i=1;ｗｈile(i<＝ｎ)i=i*１0；１*10fｏr(ｊ＝0;ｊ<n;j++)答：該程序段的時(shí)間復(fù)雜性T(n)=O(ｌｏｇ10n)。3．3.ｓum＝0;for(i＝0;i＜n;i++)???ｓuｍ=sｕm+Ａrｒaｙ[i]［j];答：該程序段的時(shí)間復(fù)雜性(n)＝Ｏ(n2)。第二章一、基礎(chǔ)知識(shí)題一、基本知識(shí)題答案1．1.試比較順序表與鏈表的優(yōu)缺陷。的操作。答：順序表用結(jié)點(diǎn)物理位置的相鄰性來(lái)反映結(jié)點(diǎn)間的邏輯關(guān)系，其優(yōu)點(diǎn)是:節(jié)省存儲(chǔ)、隨機(jī)存取，當(dāng)表長(zhǎng)變化較小，重要操作是進(jìn)行查找時(shí)，宜采用順序表。鏈表用附加的指針來(lái)反映結(jié)點(diǎn)間的邏輯關(guān)系，插入和刪除操作相對(duì)比較方便,當(dāng)表長(zhǎng)變化較大,重要操作是進(jìn)行插入和刪除時(shí),宜采用鏈表。２.２.試分析單鏈表與雙鏈表的優(yōu)缺陷。答:雙鏈表比單鏈表多增長(zhǎng)了一個(gè)指針域以指向結(jié)點(diǎn)的直接前趨，它是一種對(duì)稱結(jié)構(gòu),因此在已知某個(gè)結(jié)點(diǎn)之前或之后插入一個(gè)新結(jié)點(diǎn)、刪除該結(jié)點(diǎn)或其直接后繼都同樣方便,操作的時(shí)間復(fù)雜度為O(1)；而單鏈表是單向結(jié)構(gòu),對(duì)于找一個(gè)結(jié)點(diǎn)的直接前趨的操作要從開(kāi)始結(jié)點(diǎn)找起，其時(shí)間復(fù)雜度為O(n)。３.３.為什么在單循環(huán)鏈表中設(shè)立尾指針比設(shè)立頭指針更好？答:由于對(duì)表的操作經(jīng)常在表的兩端進(jìn)行，所以對(duì)單循環(huán)鏈表,當(dāng)知道尾指針reaｒ后，其另一端的頭指針是reaｒ->ｎeｘt->next（表中帶頭結(jié)點(diǎn)）。這會(huì)使操作變的更加容易。4.4.寫(xiě)出在循環(huán)雙鏈表中的ｐ所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)答：ｓ－>prｉor=ｐ;s-＞ｎeｘt＝p-＞nｅxｔ;p－>nexｔ-＞prioｒ=ｓ;ｐ->next=ｓ；5．5．寫(xiě)出在單鏈表中的p所指結(jié)點(diǎn)之前插入一個(gè)s所指結(jié)點(diǎn)的操作。答：ｓ－＞next=p->nexｔ;p-＞ｎext=s；teｍp=p->data;p->datａ＝s－>dａt(yī)ａ;ｓ－＞ｄata=teｍp;6.6．請(qǐng)運(yùn)用鏈表來(lái)表達(dá)下面一元多項(xiàng)式A(x)＝4*ｘ＾11+9＊x＾8+1１*x^3+8*x＋7答:多項(xiàng)式A(x）用鏈表表達(dá)如下:heａd_A-->4,１１-－>9,8-－．11,３-－＞８，1－->7,０^二、算法設(shè)計(jì)題答案1.１.有一個(gè)有n個(gè)結(jié)點(diǎn)的單鏈表，設(shè)計(jì)一個(gè)函數(shù)將第ｉ－1個(gè)結(jié)點(diǎn)與第i個(gè)結(jié)點(diǎn)互換,但指針不變。解:本題的算法思想是:要使結(jié)點(diǎn)互換而指針不變,只要將兩個(gè)結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行互換即可。實(shí)現(xiàn)本題功能的函數(shù)如下:voiｄeｘchange(node＊ｈeａd,inti,n）{?ｎodｅ*ｐ,*q;?ｉｎtdata; ｉf(i>n）? pｒｉntf("erｒor!\n");elｓe?｛ p=heａd;??fｏｒ(ｉｎtj＝１；j＜i;j＋+) ｐ=ｐ->next;?q=p－>ｎexｔ;?data＝q-＞daｔa；?q->dａt(yī)a=p－＞data; p－>dａt(yī)a=data; }}２．2．設(shè)計(jì)一個(gè)函數(shù),查找單鏈表中數(shù)值為ｘ的結(jié)點(diǎn)。解：實(shí)現(xiàn)本題功能的函數(shù)如下:ｖoidsearｃh(noｄe*head,intｘ）｛?nｏde*ｐ；?p=heaｄ; wｈｉle(p->data!=x&&p！=ＮUＬＬ)? p＝ｐ->nexｔ；?if(p!=NULL)??prｉnｔf("結(jié)點(diǎn)找到了！\n＂）;?eｌsｅ ?pｒintf("結(jié)點(diǎn)未找到！\n");}３..已知一個(gè)單鏈表,編寫(xiě)一個(gè)刪除其值為x的結(jié)點(diǎn)的前趨結(jié)點(diǎn)的算法。解：本題的算法思想是：先找到值為x的結(jié)點(diǎn)*p和它的前趨結(jié)點(diǎn)＊ｑ,要?jiǎng)h除*q，只需把＊p的值x放到*q的值域中,再刪除結(jié)點(diǎn)*p即可。實(shí)現(xiàn)本題功能的函數(shù)如下:voiddｅleｔe（node*head,ｉntx)｛node*p,*q; q=head;?p=head->ｎext;?whiｌe((p!=ＮＵLL)&&(p-＞daｔa!＝ｘ)){q=p；?p=ｐ-＞neｘt；}?if(p==NＵＬL） ?prｉnｔf("未找到x!\n＂);elｓeiｆ（q==ｈeａd)? prinｔf（"x為第一個(gè)結(jié)點(diǎn)，無(wú)前趨!\n＂);elsｅ{ q－>datａ＝x; q->ｎexｔ＝p->nexｔ; ｆｒee(ｐ);}｝４．4.已知一個(gè)單鏈表，編寫(xiě)一個(gè)函數(shù)從此單鏈表中刪除自第i個(gè)元素起的lｅngth個(gè)元素。解：實(shí)現(xiàn)本題功能的函數(shù)如下：voiｄｄeleteleｎgth(ｎode＊ｈｅad,iｎｔｉ,ｉnｔleｎgth){nｏde*p,*q;?inｔj; if(i==1) for(j=1;j<=lｅngtｈ;j++)/*刪除前k個(gè)元素*/??{ｐ=hｅad；／*p指向要?jiǎng)h除的結(jié)點(diǎn)＊/ head=heａd->next;?? frｅe(cuò)(ｐ);? }?eｌse解：實(shí)現(xiàn)本題功能的函數(shù)如下：voiddeletelength(noｄｅ*hｅａd，inti，intlenｇth）｛node*p,*q;?intj;?if(i==1） ?for(j=1;ｊ<=ｌeｎgtｈ;j++）/＊?jiǎng)h除前k個(gè)元素*／? ｛p=heａd;/*p指向要?jiǎng)h除的結(jié)點(diǎn)*/ ? hｅad=head－>next；???frｅe(cuò)（p);??} elｓe{p=head; ?fｏr(j＝1；j＜＝i-2;j++) p＝p->ｎexｔ;/*ｐ指向要?jiǎng)h除的結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)＊／??for(j=1;j<=length;j+＋)? ｛ ?q=p->next;/*q指向要?jiǎng)h除的結(jié)點(diǎn)*/?? p->ｎext=ｑ->nｅxt; ?free(q);? } }｝5．已知一個(gè)遞增有序的單鏈表，編寫(xiě)一個(gè)函數(shù)向該單鏈表中插入一個(gè)元素為ｘ的結(jié)點(diǎn),使插入后該鏈表仍然遞增有序。解：本題算法的思想是:先建立一個(gè)待插入的結(jié)點(diǎn),然后依次與鏈表中的各結(jié)點(diǎn)的數(shù)據(jù)域比較大小，找到插入該結(jié)點(diǎn)的位置,然后插入該結(jié)點(diǎn)。實(shí)現(xiàn)本題功能的函數(shù)如下:ｖｏｉｄinsert(noｄe*head,iｎtx){ node*s，*p,*q;?s=（ｎode＊)mａlloc(ｓｉzeoｆ(node))；/*建立一個(gè)待插入的結(jié)點(diǎn)*/ s->ｄaｔａ＝x; s－>ｎｅxt＝NULL;if(heａd=＝NＵLＬ||ｘ＜hｅad－＞dａt(yī)a)／＊若單鏈表為空或ｘ小于第一個(gè)結(jié)點(diǎn)ｄata域＊／{ s->neｘt=ｈeaｄ；/＊插入到表頭后面＊/ head=s; ｝ elsｅ?{ q=hｅad;? ｐ=q－>ｎext; ?whilｅ(p!＝NULＬ&&x＞p->datａ){ ??q=p; ??ｐ=p->neｘｔ; ?｝??ｓ-＞nｅxt=p;/*插入結(jié)點(diǎn)＊/??q->next=s;?}}6.已知一個(gè)單鏈表,編寫(xiě)一個(gè)函數(shù)將此單鏈表復(fù)制一個(gè)拷貝。解：本題算法的思想是依次查找原單鏈表(其頭指針為hｅａd1)中的每個(gè)結(jié)點(diǎn),對(duì)每個(gè)結(jié)點(diǎn)復(fù)制一個(gè)新結(jié)點(diǎn)并鏈接到新的單鏈表(其頭指針為heaｄ2)中。實(shí)現(xiàn)本題功能的函數(shù)如下：voidｃopy(ｎoｄe＊heａd1，node*hｅａｄ2）{?node*ｐ,＊q，*s;?heaｄ2=(ｎｏde*)maｌloc(ｓｉｚeoｆ(node)）;?q=ｈeaｄ２;ｑ->ｄata=ｈeａｄ1->datａ；ｐ=heaｄ1－>ｎext; ｗｈｉle(p!=NULL) {? s=(nｏde*)malｌoｃ(sizeｏf(noｄe))；??ｓ－＞ｄata=ｐ－>datａ;??q->next＝ｓ; q=ｓ;? ｐ=p->nｅｘt;?} q－>nｅxt=NＵLL；｝7.有一個(gè)共１０個(gè)結(jié)點(diǎn)的單鏈表，試設(shè)計(jì)一個(gè)函數(shù)將此單鏈表分為兩個(gè)結(jié)點(diǎn)數(shù)相等的單鏈表。解：本題的算法思想是：在原單鏈表一半處將其分開(kāi),第５個(gè)結(jié)點(diǎn)的neｘt域置為空，為第一個(gè)單鏈表的表尾。第二個(gè)單鏈表的表頭指針指向原單鏈表的第6個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)本題功能的函數(shù)如下,函數(shù)返回生成的第二個(gè)單鏈表的表頭指針,第一個(gè)單鏈表仍然使用原單鏈表的表頭指針。noｄe*ｄｉvidｅ（node*head1){ noｄe*head2,*pｒiｏr; heａd２=head1;?fｏr(inti=１;i<＝5;i+＋) { priｏr=ｈｅad2；?hｅad２=head2->nｅｘt; ｝ ｐrｉｏｒ－＞nｅxt=NULL;?ｒｅｔuｒnhead2;}8.與上題相同的單鏈表,設(shè)計(jì)一個(gè)函數(shù)，將此單鏈表提成兩個(gè)單鏈表,規(guī)定其中一個(gè)仍以原表頭指針heａd1作表頭指針,表中順序涉及原線性表的第一、三等奇數(shù)號(hào)結(jié)點(diǎn);另一個(gè)鏈表以heａd２為表頭指針，表中順序涉及原單鏈表第二、四等偶數(shù)號(hào)結(jié)點(diǎn)。解:本題算法的思想是將第一個(gè)鏈表中的所有偶數(shù)序號(hào)的結(jié)點(diǎn)刪除,同時(shí)把這些結(jié)點(diǎn)鏈接起來(lái)構(gòu)成第二個(gè)單鏈表。實(shí)現(xiàn)本題功能的函數(shù)如下：ｖoiｄspｌit(node*heaｄ1,noｄe*hｅaｄ2)｛ node＊ｔemp,＊odd,*even;?odｄ＝head1; head2＝head1-＞next； temp=ｈeａd2;ｗhiｌe（ｏdd!=ＮUＬＬ＆&ｏdd－>neｘｔ！=NULＬ) { ?eｖen=odd->next；／*even指向偶數(shù)序號(hào)的結(jié)點(diǎn)*/??oｄd－>ｎext＝eveｎ->nｅxt； ?tｅmp->ｎext=even;? tｅｍp=even；? ｏdd=odd->ｎext；/*odd指向奇數(shù)序號(hào)的結(jié)點(diǎn)＊/ } eｖｅn->nｅxｔ=NULL;}9.已知一個(gè)指針p指向單循環(huán)鏈表中的一個(gè)結(jié)點(diǎn),編寫(xiě)一個(gè)對(duì)此單循環(huán)鏈表進(jìn)行遍歷的算法。解：本題的算法思想是：由于是單循環(huán)鏈表,所以只要另設(shè)一指針q指向p用來(lái)幫助判斷是否已經(jīng)遍歷一遍即可。實(shí)現(xiàn)本題功能的函數(shù)如下：voidtrａvｅｌ(node*p)｛ｎodｅ*q＝p；?ｗｈｉle(q-＞next!=p) { priｎtf（"%4d＂,q->data）;? q=q->next; }?pｒiｎｔf(＂％4d",q－＞dａｔａ）;｝1０.已知一個(gè)單循環(huán)鏈表，編寫(xiě)一個(gè)函數(shù),將所有箭頭方向取反。解：本題算法的思想是:從頭到尾掃描該循環(huán)鏈表,將第一個(gè)結(jié)點(diǎn)的next域置為ＮＵLL,將第二個(gè)結(jié)點(diǎn)的next域指向第一個(gè)結(jié)點(diǎn)，如此直到最后一個(gè)結(jié)點(diǎn),便用head指向它。由于是循環(huán)鏈表，所以鑒定最后一個(gè)結(jié)點(diǎn)時(shí)不能用p->next=NUＬL作為條件,而是用q指向第一個(gè)結(jié)點(diǎn)，以p！=q作為條件。實(shí)現(xiàn)本題功能的函數(shù)如下：ｖｏidiｎvｅrt（nｏｄe*heａｄ)｛?nodｅ*ｐ,*q,＊r;p=head；q=p->ｎext;?while(p!＝q) {??r=ｈead;? whiｌe（ｒ->next!=ｐ) ? ｒ＝r-＞neｘｔ；??ｐ->nｅxt=r；? p=ｐ->ｎeｘt;?｝ q->nexｔ=heaｄ；｝１1.在雙鏈表中,若僅知道指針ｐ指向某個(gè)結(jié)點(diǎn)，不知頭指針，能否根據(jù)p遍歷整個(gè)鏈表?若能,試設(shè)計(jì)算法實(shí)現(xiàn)。解:能。本題的算法思想是:分別從p開(kāi)始沿著next以及ｐｒioｒ向右、向左掃描直至各自的鏈為空即可遍歷整個(gè)鏈表。實(shí)現(xiàn)本題功能的函數(shù)如下：voiｄtrａvellｉｓt(nｏdｅ＊p){nodｅ*q;?q=p；?whｉｌe(ｑ?。絅UＬL)?{ pｒintf(＂%4d＂，q->ｄata）; q＝q->nexｔ;?}ｑ＝ｐ->prｉor; whilｅ(q！=NULＬ)?{??printf("%４d",q->ｄata）；??q=q->prior;?}}12.試編寫(xiě)一個(gè)在循環(huán)雙向鏈表中進(jìn)行刪除操作的算法,規(guī)定刪除的結(jié)點(diǎn)是指定結(jié)點(diǎn)ｐ的前趨結(jié)點(diǎn)。解:實(shí)現(xiàn)本題功能的算法如下：voｉdｄｅlｅteｐｒior(nodｅ*p){ nodｅ*ｐｒi，q;?ｐri＝ｐ->pｒｉor;?q＝pri－＞ｐrｉor;?if(pri==ｐ) ?pｒintｆ("p結(jié)點(diǎn)無(wú)前趨!\ｎ")；第三章二、算法設(shè)計(jì)題習(xí)題解答(3)一、基本知識(shí)題答案1.什么是棧?什么是隊(duì)列?它們各自的特點(diǎn)是什么?答：棧是限定在表的一端進(jìn)行插入或刪除操作的線性表；隊(duì)列是元素的添加在表的一端進(jìn)行,而元素的刪除在表的另一端進(jìn)行的線性表;棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。2.線性表、棧、隊(duì)列有什么異同?答:棧和隊(duì)列都是線性表，但是是受限的線性表,對(duì)插入、刪除運(yùn)算加以限制。棧是只允許在一端進(jìn)行插入、刪除運(yùn)算,因而是后進(jìn)先出表；而隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算,因而是先進(jìn)先出表。３.簡(jiǎn)述棧的入棧、出棧操作的過(guò)程。答:棧的入棧、出棧操作均在棧頂進(jìn)行，棧頂指針指向棧頂元素的下一個(gè)位置。入棧操作先將入棧元素放到棧頂指針?biāo)甘镜奈恢蒙希缓髮ｍ斨羔樇樱?。出棧操作先將棧頂指針減1，然后從棧頂指針指向位置取值。4.在循環(huán)隊(duì)列中簡(jiǎn)述入隊(duì)、出隊(duì)操作的過(guò)程。答：在循環(huán)隊(duì)列中,設(shè)隊(duì)首指針指向隊(duì)首元素,隊(duì)尾指針指向隊(duì)尾元素后的一個(gè)空閑元素。在隊(duì)列不滿時(shí),可執(zhí)行入隊(duì)操作,此時(shí)先送值到隊(duì)尾指針指向的空閑元素,隊(duì)尾指針再加１(要取模)。在隊(duì)列不空時(shí),可執(zhí)行出隊(duì)操作,此時(shí)先從隊(duì)首指針指向處取值，隊(duì)首指針再加1(要取模）。二、算法設(shè)計(jì)題答案1.設(shè)用一維數(shù)組stack[n]表達(dá)一個(gè)堆棧,若堆棧中一個(gè)元素需占用lｅｎgｔh個(gè)數(shù)組單元(lengｔh＞１),試寫(xiě)出其入棧、出棧操作的算法。解:用一整型變量tｏｐ表達(dá)棧頂指針，top為０時(shí)表達(dá)棧為空。假如棧不空，則從stａck［1]開(kāi)始存放元素。實(shí)現(xiàn)本題功能的函數(shù)如下：入棧算法:voｉdＰush(ElｅＴｙｐex）{ if(（top＋ｌeｎgth)>n) ｐｒｉnｔf("上溢出＼n")；?elｓe{?iｆ(tｏp==0)／*為空棧*／{ ｔop++;???stack[toｐ]=ｘ;? ｝ else? {?? tｏｐ=top+ｌengtｈ;? ?stａｃk[toｐ］=x; }?｝｝出棧算法:voidＰop（EｌeTyｐex)｛?iｆ(top==0） ｐｒintf("為空棧\n"); elｓe?｛??if（top＝=1) { x＝stack[tｏp];top--;??} ｅlse??｛ x=stack[top]; ??top=ｔop-lengtｈ； }?}}2.試編寫(xiě)一個(gè)遍歷及顯示隊(duì)列中元素的算法。解:設(shè)表達(dá)式在字符數(shù)組a[]中，使用一堆棧S來(lái)幫助判斷。實(shí)現(xiàn)本題功能的函數(shù)如下:intｃorｒeｃt(cｈａｒa［]){StackＳ； ＩnｉtSｔaｃk（S）；?foｒ(i=０;i<ｓtrlｅn(a)；i+＋)??iｆ(a[i]==＇(')?? Pｕsh(S,'（'）;? elsｅif(ａ[i]==')'){? ?iｆ(StackEmｐty(S）) ??rｅturｎ0； else ??Pop（S）;? } iｆ(SｔackＥｍptｙ(S)) rｅturｎ1；／＊配對(duì)對(duì)的*/ ?elｓereｔurｎ0；/*配對(duì)錯(cuò)誤*/｝3．設(shè)一循環(huán)隊(duì)列Queｕe,只有頭指針front，不設(shè)尾指針，另設(shè)一個(gè)內(nèi)含元素個(gè)數(shù)的計(jì)數(shù)器，試寫(xiě)出相應(yīng)的入隊(duì)、出隊(duì)算法。解:實(shí)現(xiàn)本題功能的函數(shù)如下:ｖoidｔraｖel（Ｑueue,ｉnｔfrｏnt，ｒeaｒ){?inｔi； foｒ（i=frｏnt；i＜=reａｒ；i＋+）{? ｐｒｉntｆ("%４d",Queuｅ[i])；?}}４.設(shè)計(jì)一算法能判斷一個(gè)算術(shù)表達(dá)式中的圓括號(hào)配對(duì)是否對(duì)的。（提醒:對(duì)表達(dá)式進(jìn)行掃描，凡碰到“(”就進(jìn)棧,碰到“)”就退出棧頂?shù)摹?”，表達(dá)式掃描完畢時(shí)棧若為空則圓括號(hào)配對(duì)對(duì)的。)解：用一個(gè)循環(huán)數(shù)組Queue[0，ｎ－1]表達(dá)該循環(huán)隊(duì)列,頭指針為fｒｏnｔ，計(jì)數(shù)器cｏunt用來(lái)記錄隊(duì)列中結(jié)點(diǎn)的個(gè)數(shù)。入隊(duì)算法如下:voidenquｅue(intx){?ｉｎttｅmp； if（count==ｎ) ?ｐrintf("隊(duì)列上溢出\n"）;?else｛ ?ｃouｎt++;??ｔemp＝（front+cｏｕｎt)％n; Ｑueuｅ［ｔemp]=x; }｝出隊(duì)算法如下：intdｅqueue(){intｔeｍp；iｆ(coｕnt==0） priｎtf("隊(duì)列下溢出\n")； eｌse ｛ｔemp=Queue［fronｔ］; froｎｔ=(frｏnt＋１)%n；count－-; ?ｒetuｒnｔeｍp；?}}數(shù)據(jù)結(jié)構(gòu)（本科)期末綜合練習(xí)一（單選題）單選題１.一個(gè)數(shù)組元素a[ｉ]與(A)的表達(dá)等價(jià)。A.*（a＋i)B.a＋iC．＊a＋iD.＆a+i２.若需要運(yùn)用形參直接訪問(wèn)實(shí)參，則應(yīng)把形參變量說(shuō)明為(Ｂ)參數(shù)。A.指針B.引用C.傳值D.常值3.下面程序段的時(shí)間復(fù)雜度為(C)。ｆor（ｉntｉ＝0;ｉ<m;i++)ｆor（iｎtj＝0；j<ｎ;j+＋)ａ[ｉ][j］=i*j;A.O(m２)B.O（n２）Ｃ.Ｏ(m*n)D.O（m+n)4.執(zhí)行下面程序段時(shí)，執(zhí)行Ｓ語(yǔ)句的次數(shù)為（D)。for(inｔi=1；ｉ<=n;ｉ++)fｏr(intj＝１；j<=ｉ;j++)Ｓ;A．ｎ２B.n2/2C.ｎ（n＋１）D.ｎ（n+1)／25.下面算法的時(shí)間復(fù)雜度為(Ｂ)。intf(uｎsigｎｅdintn)｛ｉｆ(n==０||n＝=１)return１;elsｅreturｎn*ｆ(n－1);｝A.O（１)B.O(n)Ｃ.O(n2)D.O(n！)6.一種抽象數(shù)據(jù)類型涉及數(shù)據(jù)和（Ｂ)部分。Ａ.數(shù)據(jù)類型B．操作Ｃ.數(shù)據(jù)抽象Ｄ.類型說(shuō)明7.當(dāng)一個(gè)作為實(shí)際傳遞的對(duì)象占用的存儲(chǔ)空間較大并也許被修改時(shí)，應(yīng)最佳說(shuō)明為(Ｂ),以節(jié)省參數(shù)值的傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。Ａ.基本類型B.引用型C．指針型D.常值引用型８.當(dāng)需要進(jìn)行標(biāo)準(zhǔn)I/O操作時(shí),則應(yīng)在程序文獻(xiàn)中包含ioｓtrｅam.h頭文獻(xiàn)，當(dāng)需要進(jìn)行文獻(xiàn)Ｉ／O操作時(shí)，則應(yīng)在程序文獻(xiàn)中包含(A)頭文獻(xiàn)。A.fstreａm.hB．stdlib．hC.ｉｏmanip.hD.ｓtring.h9.一個(gè)記錄ｒ理論上占有的存儲(chǔ)空間的大小等于所有域類型長(zhǎng)度之和,事實(shí)上占有的存儲(chǔ)空間的大小即記錄長(zhǎng)度為(Ｄ)。A.所有域長(zhǎng)度之和Ｂ.最大域所占字節(jié)長(zhǎng)度Ｃ．任意一個(gè)域長(zhǎng)度Ｄ．ｓｉｚeof(ｒ)的值1０.輸出一個(gè)二維數(shù)組b[ｍ][n］中所有元素值的時(shí)間復(fù)雜度為(Ｄ)。A.O（ｎ)B.O(m＋n）C.O（n２)Ｄ.O（m*n）11.一個(gè)算法的時(shí)間復(fù)雜度為(3n2+2ｎlog2n+4ｎ-７)/（5ｎ),其數(shù)量級(jí)形式的復(fù)雜度表達(dá)為（Ａ)。A.O(n)B．O（nｌｏg2n)C．O(n２）Ｄ.O(log2n)12.某算法的時(shí)間代價(jià)為T(n)=１00n+1０nｌog2n+ｎ2+10，其時(shí)間復(fù)雜度為（C)。A.O（n）B．O(nｌog2n)C.O（ｎ2)D.Ｏ(1)１3.某算法僅含程序段1和程序段2,程序段１的執(zhí)行次數(shù)3n2,程序段2的執(zhí)行次數(shù)為0．0１ｎ3，則該算法的時(shí)間復(fù)雜度為（C）。A.O(n)Ｂ.Ｏ(n2）C.O(n３)D.Ｏ(1)14.以下說(shuō)法錯(cuò)誤的是（Ｃ）。A.抽象數(shù)據(jù)類型具有封裝性。B．抽象數(shù)據(jù)類型具有信息隱蔽性。Ｃ.使用抽象數(shù)據(jù)類型的用戶可以自己定義對(duì)抽象數(shù)據(jù)類型中數(shù)據(jù)的各種操作。Ｄ.抽象數(shù)據(jù)類型的一個(gè)特點(diǎn)是使用與實(shí)現(xiàn)分離。15．在二維數(shù)組中,每個(gè)數(shù)組元素同時(shí)處在(Ｃ）個(gè)向量中。A.０個(gè)? B.１個(gè)??C．2個(gè) D．n個(gè)16．多維數(shù)組事實(shí)上是由嵌套的（A）實(shí)現(xiàn)的。A．一維數(shù)組B.多項(xiàng)式Ｃ.三元組表D.簡(jiǎn)樸變量１7.在一個(gè)長(zhǎng)度為n的順序表中順序搜索一個(gè)值為x的元素時(shí),在等概率的情況下,搜索成功時(shí)的數(shù)據(jù)平均比較次數(shù)為（C）。A.nB.ｎ/2C．（n＋1)／2D.（n-1)/218．在一個(gè)長(zhǎng)度為n的順序表中向第ｉ個(gè)元素（0≤i≤ｎ-1)位置插入一個(gè)新元素時(shí),需要從后向前依次后移（A)個(gè)元素。A.n-iB.n－i+1C.ｎ－i-1D．i19.在一個(gè)長(zhǎng)度為n的順序表中刪除第ｉ個(gè)元素（０≤i≤n-1）時(shí)，需要從前向后依次前移（C)個(gè)元素。