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

第十章內(nèi)部排序一、基本知識題答案１．排序:將一組雜亂無序的數(shù)據(jù)按一定的規(guī)律順次排列起來叫做排序。內(nèi)部排序:數(shù)據(jù)存儲在內(nèi)存中，并在內(nèi)存中加以解決的排序方法叫內(nèi)部排序。堆:堆是一個完全二叉樹,它的每個結(jié)點相應(yīng)于原始數(shù)據(jù)的一個元素,且規(guī)定假如一個結(jié)點有兒子結(jié)點,此結(jié)點數(shù)據(jù)必須大于或等于其兒子結(jié)點數(shù)據(jù)。穩(wěn)定排序：一種排序方法,若排序后具有相同關(guān)鍵字的記錄仍維持本來的相對順序,則稱之為穩(wěn)定的，否則稱為不穩(wěn)定的。2.回答下面問題(1)5000個無序的數(shù)據(jù)，希望用最快速度挑選出其中前10個最大的元素，在快速排序、堆排序、歸并排序和基數(shù)排序中采用哪種方法最佳？為什么？（2）大多數(shù)排序算法都有哪兩個基本操作？答:(1)采用堆排序最佳。由于以上幾種算法中,快速排序、歸并排序和基數(shù)排序都是在排序結(jié)束后才干擬定數(shù)據(jù)元素的所有順序,而無法知道排序過程中部分元素的有序性。堆排序則每次輸出一個最大（或最?。┑脑?，然后對堆進(jìn)行調(diào)整，保證堆頂?shù)脑乜偸怯嘞略刂凶畲螅ɑ蜃钚?的。根據(jù)題意,只要選取前10個最大的元素，故采用堆排序方法是合適的。(2）兩個基本操作:比較兩個關(guān)鍵字的大小、改變指向記錄的指針或移動記錄自身。3.3．已知序列{1７,2５，55,43,３,３2,78,6７,91｝,請給出采用冒泡排序法對該序列作遞增排序時每一趟的結(jié)果。答:采用冒泡排序法排序時的各趟結(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第５趟無元素互換，排序結(jié)束。4．已知序列{4９1，77,57２，１6,9９6,10１，８６3,2５8,68９,32５}，請分別給出采用快速排序、堆排序和基數(shù)排序法對該序列作遞增排序時每一趟的結(jié)果。答:采用快速排序法排序時的各趟結(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采用堆排序法排序時各趟的結(jié)果如下圖所示:(a)初始堆(b)建堆(c)互換9９6和77,輸出99６(d)篩選調(diào)整采用基數(shù)排序法排序時各趟的結(jié)果如下：初始:４９1,７7，572,1６，99６，10１，863,2５8，689，325第1趟（按個位排序):４９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},請給出采用插入排序法對該序列作遞增排序時，每一趟的結(jié)果。答:采用插入排序法排序時各趟的結(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}，請給出采用歸并排序法對該序列作遞增排序時的每一趟的結(jié)果。答:采用歸并排序法排序時各趟的結(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è)計題答案１.二、算法設(shè)計題1．一個線性表中的元素為所有為正或者負(fù)整數(shù)，試設(shè)計一算法,在盡也許少的時間內(nèi)重排該表，將正、負(fù)整數(shù)分開，使線性表中所有負(fù)整數(shù)在正整數(shù)前面。解：本題的算法思想是:設(shè)立兩個變量分別指向表的首尾，它們分別向中間移動，指向表首的?假如碰到正整數(shù),指向表尾的假如碰到負(fù)整數(shù)則互相互換,然后繼續(xù)移動直至兩者相遇。實現(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è)計一個用單鏈表作存儲結(jié)構(gòu)的直接插入排序算法。解：實現(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è)計一個算法實現(xiàn)雙向冒泡排序。(雙向冒泡排序就是在排序的過程中交替改變掃描方向。）解：實現(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è)一個一維數(shù)組Ａ［n］中存儲了n個互不相同的整數(shù),且這些整數(shù)的值都在０到n-1之間，即A中存儲了從0到n－1這n個整數(shù)。試編寫一算法將A排序，結(jié)果存放在數(shù)組B[ｎ]中，規(guī)定算法的時間復(fù)雜性為O(n)。解:實現(xiàn)本題功能的算法如下：voidsｏrt(intＡ［n］，iｎtB[n］){?iｎti； fｏr(ｉ=０;i＜n；ｉ＋+） ?B[A［i]]=A[ｉ］;}第九章一、基礎(chǔ)知識題1.(１)查找：查找又稱為查詢或檢索,是在一批記錄中依照某個域的指定域值,找出相應(yīng)的記錄的操作。(2)樹型查找：將原始數(shù)據(jù)表達(dá)成二叉排序樹，樹的每個結(jié)點相應(yīng)一個記錄,運用此二叉排序樹進(jìn)行類似于二分查找思想的數(shù)據(jù)查找，這種查找方法稱為樹型查找。(3）平衡因子：二叉樹中每一結(jié)點的左子樹高度減右子樹高度為該結(jié)點的平衡因子。（４)散列函數(shù)：根據(jù)關(guān)鍵字求存儲地址的函數(shù)稱為散列函數(shù)。(５)兩個不同的關(guān)鍵字，其散列函數(shù)值相同,因而被映射到同一個表位置上的現(xiàn)象稱為沖突。２.設(shè)有序表為{a,b,c,d，ｅ,f,g}，請分別畫出對給定值f,g和h進(jìn)行拆半查找的過程。答：查找f的過程如下:查找成功，找到k＝f值查找g的過程如下：查找成功，找到k=g值查找h的過程如下:試述順序查找法、二分查找法和分塊查找法對被查找表中元素的規(guī)定，每種查找法對長度為n的表的等概率查找長度是多少答:順序查找法:表中元素可以任意存放。查找成功的平均查找長度為(ｎ+1)／2。二分查找法：表中元素必須以關(guān)鍵字的值遞增或遞減地存放且只能以順序表存放。查找成功的平均查找長度為log2（n+1)－１。分塊查找法:表中每塊內(nèi)的元素可以任意存放,但塊與塊之間必須按關(guān)鍵字的大小遞增或遞減地存放,即前一塊內(nèi)所有元素的關(guān)鍵字不能大(或小)于后一塊內(nèi)任意一個元素的關(guān)鍵字。若用順序查找擬定所在塊,平均查找長度為1／２（n/s+s)+1;若用二分查找擬定所在塊,平均查找長度為lｏｇ2(ｎ/ｓ+1）＋s/2。4.設(shè)散列表長m=14，哈希函數(shù)為H(k)＝ｋmod11,表中一共有8個元素{15,27,50,73,49,61，37,6０｝，試畫出采用二次探測法解決沖突的散列表。答:采用二次探測法解決沖突的散列表如下：5.線性表的關(guān)鍵字集合為{113,1２,1８0,138,９2,67,94,13４,２52,６，7０,323，60｝，共有1３個元素,已知散列函數(shù)為：H（k）=kmod13,采用鏈接表解決沖突，試設(shè)計這種鏈表結(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，散列表長度m＝１0，起始地址為０,分別用線性探測和鏈接表法來解決沖突。試畫出相應(yīng)的散列表。答：線性探測法的散列表如下圖所示：鏈接表法的散列表如下圖所示：二、算法設(shè)計題1.從小到大排列的，試寫出對此鏈表的查找算法,并說明是否可以采用折半查找。解：實現(xiàn)本題功能的算法如下，假如查找成功,則返回指向關(guān)鍵字為x的結(jié)點的指針，否則返回Ｎ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é)點是按遞增順序排列的,但是其存儲結(jié)構(gòu)為單鏈表，查找結(jié)點時只能從頭指針開始逐步進(jìn)行搜索，所以不能用折半查找。2．假如線性表中各結(jié)點查找概率不等,則可以使用下面的策略提高順序表的查找效率:假如找到指定的結(jié)點,則將該結(jié)點和其前趨(若存在）結(jié)點互換,使得經(jīng)常被查找的結(jié)點盡量位于表的前端。試對線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)寫出實現(xiàn)上述策略的順序查找算法(注意查找時必須從表頭開始向后掃描）。解:采用順序存儲結(jié)構(gòu)的算法如下,設(shè)記錄存儲在線性表的１~n單元中。假如查找成功，返回關(guān)鍵字為k的記錄在線性表中的位置，假如失敗則返回0。intseｑsearch(sqlｉsｔr,intn,iｎtk）{ inti,ｊ;?i=1;?while（(r[i］.key?。絢)&&(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)酱鎯Y(jié)構(gòu)的算法如下。假如查找成功，則返回指向關(guān)鍵字為ｋ的結(jié)點的指針,否則返回Ｎ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è)計一個在用開放地址法解決沖突的散列表上刪除一個指定結(jié)點的算法。解:本題的算法思想是：一方面計算要刪除的關(guān)鍵字為k的記錄所在的位置，將其置為空（即刪除）,然后運用線性探測法查找是否有與k發(fā)生沖突而存儲到下一地址的記錄,假如有則將記錄移到本來k所在的位置，直至表中沒有與k沖突的記錄為止。實現(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è)給定的散列表存儲空間為H[1~ｍ］，每個單元可存放一個記錄，H[i](1≤ｉ≤m)的初始值為零，選取散列函數(shù)為H(R．kｅy),其中key為記錄R的關(guān)鍵字,解決沖突方法為線性探測法,編寫一個函數(shù)將某記錄R填入到散列表H中。解：本題的算法思想：先計算地址H（R.key）,假如沒有沖突,則直接填入；否則運用線性探測法求出下一地址，直到找到一個為零的地址，然后填入。實現(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; }}第七章一、基本知識題1.圖的邏輯結(jié)構(gòu)特點是什么?什么是無向圖和有向圖？什么是子圖？什么是網(wǎng)絡(luò)?答：圖是比樹更為復(fù)雜的一種非線性數(shù)據(jù)結(jié)構(gòu),在圖結(jié)構(gòu)中，每個結(jié)點都可以和其它任何結(jié)點相連接。無向圖:對于一個圖Ｇ，若邊集合E（G）為無向邊的集合，則稱該圖為無向圖。有向圖:對于一個圖G，若邊集合E（G)為有向邊的集合，則稱該圖為有向圖。子圖:設(shè)有兩個圖Ｇ＝(V,E)和G’＝(V’,E’)，若Ｖ(G’)是Ｖ（G）的子集，且E（G’)是Ｅ(G)的子集，則稱G’是G的子圖(Subgraｐh)。網(wǎng)絡(luò)：有些圖，相應(yīng)每條邊有一相應(yīng)的數(shù)值,這個數(shù)值叫做該邊的權(quán)。邊上帶權(quán)的圖稱為帶權(quán)圖,也稱為網(wǎng)絡(luò)。2.什么是頂點的度？什么是途徑？什么是連通圖和非連通圖？什么是非連通圖的連通分量?答：頂點的度：圖中與每個頂點相連的邊數(shù)，叫該頂點的度。在一個圖中,若從某頂點Ｖp出發(fā),沿一些邊通過頂點V1,V2，…,Vm到達(dá)，Vq，則稱頂點序列（Vｐ,V1,V２,…,Ｖｍ,Vq）為從Vp到Vq的途徑。在無向圖中,假如從頂點Vi到頂點Ｖj之間有途徑，則稱這兩個頂點是連通的。假如圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的連通分量:非連通圖的每一個連通的部分叫連通分量。3.給出圖６.25所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)。答:圖G所相應(yīng)的鄰接矩陣如下:圖G所相應(yīng)的鄰接表如下：圖254.假設(shè)圖的頂點是A、B……請根據(jù)下面的鄰接矩陣畫出相應(yīng)的無向圖或有向圖。答:(a)所相應(yīng)的無向圖如下圖(a）所示,(ｂ）所相應(yīng)的有向圖如下圖(ｂ)所示:5.5.分別給出圖6．26所示G圖的深度優(yōu)先搜索和廣度優(yōu)先搜索得到的頂點訪問序列。圖26答：深度優(yōu)先搜索得到的頂點訪問序列:0、1、3、7、8、4、9、5、6、2;?廣度優(yōu)先搜索得到的頂點訪問序列:0、１、2、３、4、５、6、7、8、9。６.應(yīng)用ｐriｍ算法求圖6．27所示帶權(quán)連通圖的最小生成樹。答:該圖的最小生成樹如下：????? ? ? ? 圖27?７.寫出圖6．28所示有向圖的拓樸排序序列答:該有向圖的拓樸排序序列為:3、１、4、5、２、６。二、算法設(shè)計題 ? ? ? 圖28二、算法設(shè)計題答案1.如圖6.2９所示圖G,試給出其相應(yīng)的鄰接表,并寫出深度優(yōu)先算法。解:該圖相應(yīng)的鄰接表如下:深度優(yōu)先算法：ｖoiddfsgｒaph（adjlistadj,ｉntn)/＊深度優(yōu)先遍歷整個圖*/{ 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ā)點,對圖進(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)的鄰接矩陣，并寫出廣度優(yōu)先算法。解：該圖相應(yīng)的鄰接矩陣如下:廣度優(yōu)先算法:voidｂfｓgｒaph（ｉnｔadjａｒray[n］[ｎ］,ｉntn）/＊廣度優(yōu)先遍歷整個圖*/{?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ā)點,對圖進(jìn)行ｂfｓ遍歷*/｛ ｉｎti，j; ｑueuｅｑ;?ｐｒintf（"%d",ｖ）;?viｓｉtｅd[v]=1;?eｎquｅuｅ(＆q,v); wｈiｌe（！queuｅeｍty(&q))?{ ?i=dequeｕｅ(&q)；ｆor(j＝0;j<n；j＋+)? if(aｄjaｒray[i][j］=＝1&＆！ｖisｉteｄ[j]) ? {??? printf("%d",ｊ);?? ?visited［ｊ]＝1；????ｅnqueue（＆ｑ,j）;? }?}}3.編寫一個函數(shù)通過與用戶交互建立一個有向圖的鄰接表。解:實現(xiàn)本題功能的算法如下：ｖｏiｄcreatｅｇraph(aｄjlｉstｇ)｛?iｎte,i，s,d,n;stｒuｃtedgenodｅ*p; pｒinｔf("請輸入結(jié)點數(shù)(n)和邊數(shù)(e):\ｎ"）; scanf（"%d,%d",&n,&e); foｒ(ｉ=1;i＜=n；i＋+){prｉnｔf("\ｎ請輸入第%d個頂點信息:"，i）;ｓcａnf("％c",&ｇ[i]．dａｔa)；g［ｉ].liｎk＝NULL;?} for(ｉ＝1;ｉ<＝ｅ;i++)?{ｐrｉnｔf("＼n請輸入第%d條邊起點序號，終點序號:",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．編寫一個無向圖的鄰接矩陣轉(zhuǎn)換成鄰接表的算法。解:本題的算法思想是：逐個掃描鄰接矩陣的各個元素,如第i行第j列的元素為1，則相應(yīng)的鄰接表的第i個單鏈表上增長一個j結(jié)點。實現(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;?? } }}５.已知一個有n個頂點的有向圖的鄰接表，設(shè)計算法分別實現(xiàn)1）求出圖中每個頂點的出度。2)求出圖中每個頂點的入度。３)求出圖中出度最大的一個頂點,輸出其頂點序號。4）計算圖中出度為0的頂點個數(shù)。解:（1）本題的算法思想是:計算出鄰接表中第i個單鏈表的結(jié)點數(shù)，即為i頂點的出度。求頂點的出度數(shù)的算法如下:ｉntoutdegrｅe(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;?priｎtf(＂Tｈeoutdegreｅsａrｅ:\n＂); for(i=0；i<n;i++)?{?deｇree＝oｕtｄｅgree（ａdj,ｉ）； ?priｎtｆ("（％d,%ｄ）＂,ｉ,degｒｅe); }}（２)本題的算法思想是：計算出整個鄰接表中所具有的結(jié)點為i的結(jié)點數(shù),這就是ｉ頂點的入度。求頂點的入度數(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(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=%d,ｍaxvｅrteｘ=%d",maxｄegrｅe,maxv);}(4)求出度數(shù)為0的頂點數(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ǔ)知識題1.就如圖5．21所示的樹回答下面問題：1)哪個是根結(jié)點？２）哪些是葉子結(jié)點?３)哪個是E的父結(jié)點？4）哪些是Ｅ的子孫結(jié)點？５)哪些是E的兄弟結(jié)點?哪些是Ｃ的兄弟結(jié)點？6)結(jié)點B和結(jié)點I的層數(shù)分別是多少？７）樹的深度是多少？8）以結(jié)點G為根的子樹的深度是多少?9)樹的度是多少？答:１）A是根結(jié)點２)D、H、I、J、F、G是葉子結(jié)點3)Ｂ是E的父結(jié)點4)H、I、J是E的子孫結(jié)點5）D是Ｅ的兄弟結(jié)點,B是C的兄弟結(jié)點6)B的層數(shù)是2,I的層數(shù)是47）樹的深度是48）以結(jié)點G為根的子樹的深度是１9)樹的度是32.分別畫出含3個結(jié)點的樹與二叉樹的所有不同形態(tài)。答：3個結(jié)點的樹: 3個結(jié)點的二叉樹:3.高度為ｈ的完全二叉樹至少有多少個結(jié)點？最多有多少個結(jié)點?答：高度為ｈ的完全二叉樹至少有個結(jié)點，最多有個結(jié)點。4.采用順序存儲方法和鏈?zhǔn)酱鎯Ψ椒ǚ謩e畫出圖５.２2所示二叉樹的存儲結(jié)構(gòu)。答:該二叉樹的順序存儲:該二叉樹的鏈?zhǔn)酱鎯?5.分別寫出圖5.22所示二叉樹的前序、中序和后序遍歷序列。圖22答:先序遍歷序列:1、2、4、７、３、5、8、6、９中序遍歷序列：7、4、2、1、8、５、3、6、9后序遍歷序列:7、4、2、8、５、9、６、3、１6.若二叉樹中各結(jié)點值均不相同。1)已知一個二叉樹的中序和后序遍歷序列分別為ＧDHBAECIＦ和ＧHDBEIFCA,請畫出此二叉樹。2)已知一個二叉樹的前序和中序分別為ＡBＣDEＦＧＨ和BDCEAFＨG,請畫出此二叉樹。答：7．一個二叉樹如圖5.２３所示,分別寫出其前序、中序、后序的遍歷序列。答：先序遍歷序列:A、Ｂ、D、E、F、C、G中序遍歷序列：D、F、Ｅ、B、A、G、C后序遍歷序列:F、Ｅ、D、Ｂ、G、Ｃ、A８.輸入一個正整數(shù)序列｛55,３4,18,88，1１９,１1，76,9,９７,９９,46｝,試構(gòu)造一個二叉排序樹。9.有一份電文中共使用5個字符：ａ、b、c、ｄ、ｅ,它們的出現(xiàn)頻率依次為5、2、1、6、4。試畫出相應(yīng)的哈夫曼樹,并求出每個字符的哈夫曼編碼。第8題 各字符相應(yīng)的哈夫曼編碼如下：a:10,b:001,c：０00,d:1１,e：０1二、算法設(shè)計題答案1.一個二叉樹以鏈?zhǔn)浇Y(jié)構(gòu)存儲,分別給出求二叉樹結(jié)點總數(shù)和葉子結(jié)點總數(shù)的算法。解：求二叉樹結(jié)點總數(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ｍ;}求二叉樹葉子結(jié)點總數(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．一個二叉樹以鏈?zhǔn)浇Y(jié)構(gòu)存儲,寫出在二叉樹中查找值為x的結(jié)點的算法。解:本題可以用先序、中序和后序遍歷中的任意一種遍歷，只要將遍歷算法中的訪問根結(jié)點改為判斷其值是否等于x。下面是用中序遍歷求解的算法，函數(shù)返回值為ｘ的結(jié)點的地址,若沒有找到則返回空。btree*seａｒｃh(btrｅe*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è)計一個算法將一個以鏈?zhǔn)酱鎯Y(jié)構(gòu)的二叉樹，按順序方式存儲到一維數(shù)組中。解:這是一個遞歸算法，如下:vｏidcreate(btｒｅe*t,ｉnttree[],inti)｛ if(t!=NUＬL） { ?trｅe[i]=t->data; ｃrｅａｔe(t－>left,tｒｅｅ,２*i）； ?cｒｅａt(yī)e(ｔ->rｉgｈt，tree,２*i＋1); }}4.假設(shè)二叉排序樹t的各元素值均不相同，設(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.已知一個中序線索二叉樹,試編寫中序遍歷的非遞歸算法。解:在中序線索二叉樹中進(jìn)行非遞歸中序遍歷，只要從頭結(jié)點出發(fā),反復(fù)找到結(jié)點的后繼,直至結(jié)束即可。在中序線索二叉樹中求結(jié)點后繼的算法如下:ｔｂtree＊sｕcc(tｂtree*p）{ btrｅe*q； if(p->rtａｇ==１) retｕrn（p->riｇht）;ｅlse?{ q=p-＞right；? while（q->ltag=＝0) ?q=q－＞left; retｕrｎ(q);?｝}由此得到中序遍歷線索二叉樹的非遞歸算法如下：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]采用列為主序存儲，每個元素占1個單元,A［０]［０]的地址為200,則A[6][1２］的地址是多少？3２62.稀疏矩陣m×n采用三元組順序表存儲結(jié)構(gòu),非零元個數(shù)ｔｕ滿足什么條件時，該存儲結(jié)構(gòu)才故意義?tu<m*n/3３.二維數(shù)組A［10..２0]［５．.10]采用行為主序存儲,每個元素占4個單元,A[10][5]的地址為1000,則A[１８][9]的地址是多少?(１20８)４.稀疏矩陣的三元組順序表存儲結(jié)構(gòu)是隨機(jī)存儲結(jié)構(gòu)嗎?為什么?(不是）５.廣義表((a,b，c，d）)的表頭和表尾分別是什么?((a,ｂ,c,d）;空表)6.廣義表(（a),((ｂ）,c)，(((d)）))的長度和深度分別是多少?(3，4)第一章數(shù)據(jù)物理結(jié)構(gòu)算法二、簡答一、名詞解釋數(shù)據(jù):就是一切可以由計算機(jī)接受和解決的對象。數(shù)據(jù)項：是數(shù)據(jù)的不可分割的最小單位，在有些場合下，數(shù)據(jù)項又稱為字段或域。數(shù)據(jù)元素:是數(shù)據(jù)的基本單位,在程序中作為一個整體加以考慮和解決，也稱為元素、頂點或記錄。它可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的互相關(guān)系,即數(shù)據(jù)的組織形式，它涉及數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算三個方面的內(nèi)容。數(shù)據(jù)邏輯結(jié)構(gòu):是指數(shù)據(jù)元素之間的邏輯關(guān)系，是從邏輯上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān),獨立于計算機(jī)。數(shù)據(jù)物理結(jié)構(gòu)：是指數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器內(nèi)的表達(dá)，是數(shù)據(jù)的邏輯結(jié)構(gòu)用計算機(jī)語言的實現(xiàn)，是依賴于計算機(jī)語言的。算法:是對特定問題求解環(huán)節(jié)的一種描述。它是一個有窮的規(guī)則序列,這些規(guī)則決定了解決某一特定問題的一系列運算。由此問題相關(guān)的一定輸入，計算機(jī)依照這些規(guī)則進(jìn)行計算和解決，通過有限的計算環(huán)節(jié)后能得到一定的輸出。算法的時間復(fù)雜性:是該算法的時間花費,它是該算法所求解問題規(guī)模ｎ的函數(shù)。當(dāng)n趨向無窮大時,我們把時間復(fù)雜性T（n)的數(shù)量級稱為算法的漸進(jìn)時間復(fù)雜性。二、簡答題1.算法分析的目的是什么？答:對算法進(jìn)行分析的目的有兩個：第一個目的是可以從解決同一問題的不同算法中區(qū)分相對優(yōu)劣，選出較為合用的一種;第二個目的是有助于設(shè)計人員考慮對現(xiàn)有算法進(jìn)行改善或設(shè)計出新的算法。2.什么是算法的最壞和平均時間復(fù)雜性?答:算法的最壞時間復(fù)雜性是研究各種輸入中運算最慢的一種情況下的運算時間；平均時間復(fù)雜性是研究同樣的n值時各種也許的輸入,取它們運算時間的平均值。三、答案１.三、分析下列算法的時間復(fù)雜性:1.ｓuｍ=0;for（i=1;i<=n;i++){ｓum＝suｍ+i;}答：該程序段的時間復(fù)雜性為T（ｎ)＝O(ｎ)。2．2.i=1;ｗｈile(i<＝ｎ)i=i*１0；１*10fｏr(ｊ＝0;ｊ<n;j++)答：該程序段的時間復(fù)雜性T(n)=O(ｌｏｇ10n)。3．3.ｓum＝0;for(i＝0;i＜n;i++)???ｓuｍ=sｕm+Ａrｒaｙ[i]［j];答：該程序段的時間復(fù)雜性(n)＝Ｏ(n2)。第二章一、基礎(chǔ)知識題一、基本知識題答案1．1.試比較順序表與鏈表的優(yōu)缺陷。的操作。答：順序表用結(jié)點物理位置的相鄰性來反映結(jié)點間的邏輯關(guān)系，其優(yōu)點是:節(jié)省存儲、隨機(jī)存取，當(dāng)表長變化較小，重要操作是進(jìn)行查找時，宜采用順序表。鏈表用附加的指針來反映結(jié)點間的邏輯關(guān)系，插入和刪除操作相對比較方便,當(dāng)表長變化較大,重要操作是進(jìn)行插入和刪除時,宜采用鏈表。２.２.試分析單鏈表與雙鏈表的優(yōu)缺陷。答:雙鏈表比單鏈表多增長了一個指針域以指向結(jié)點的直接前趨，它是一種對稱結(jié)構(gòu),因此在已知某個結(jié)點之前或之后插入一個新結(jié)點、刪除該結(jié)點或其直接后繼都同樣方便,操作的時間復(fù)雜度為O(1)；而單鏈表是單向結(jié)構(gòu),對于找一個結(jié)點的直接前趨的操作要從開始結(jié)點找起，其時間復(fù)雜度為O(n)。３.３.為什么在單循環(huán)鏈表中設(shè)立尾指針比設(shè)立頭指針更好？答:由于對表的操作經(jīng)常在表的兩端進(jìn)行，所以對單循環(huán)鏈表,當(dāng)知道尾指針reaｒ后，其另一端的頭指針是reaｒ->ｎeｘt->next（表中帶頭結(jié)點）。這會使操作變的更加容易。4.4.寫出在循環(huán)雙鏈表中的ｐ所指結(jié)點之后插入一個s所指結(jié)點答：ｓ－>prｉor=ｐ;s-＞ｎeｘt＝p-＞nｅxｔ;p－>nexｔ-＞prioｒ=ｓ;ｐ->next=ｓ；5．5．寫出在單鏈表中的p所指結(jié)點之前插入一個s所指結(jié)點的操作。答：ｓ－＞next=p->nexｔ;p-＞ｎext=s；teｍp=p->data;p->datａ＝s－>dａt(yī)ａ;ｓ－＞ｄata=teｍp;6.6．請運用鏈表來表達(dá)下面一元多項式A(x)＝4*ｘ＾11+9＊x＾8+1１*x^3+8*x＋7答:多項式A(x）用鏈表表達(dá)如下:heａd_A-->4,１１-－>9,8-－．11,３-－＞８，1－->7,０^二、算法設(shè)計題答案1.１.有一個有n個結(jié)點的單鏈表，設(shè)計一個函數(shù)將第ｉ－1個結(jié)點與第i個結(jié)點互換,但指針不變。解:本題的算法思想是:要使結(jié)點互換而指針不變,只要將兩個結(jié)點的數(shù)據(jù)進(jìn)行互換即可。實現(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è)計一個函數(shù),查找單鏈表中數(shù)值為ｘ的結(jié)點。解：實現(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é)點找到了！\n＂）;?eｌsｅ ?pｒintf("結(jié)點未找到！\n");}３..已知一個單鏈表,編寫一個刪除其值為x的結(jié)點的前趨結(jié)點的算法。解：本題的算法思想是：先找到值為x的結(jié)點*p和它的前趨結(jié)點＊ｑ,要刪除*q，只需把＊p的值x放到*q的值域中,再刪除結(jié)點*p即可。實現(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為第一個結(jié)點，無前趨!\n＂);elsｅ{ q－>datａ＝x; q->ｎexｔ＝p->nexｔ; ｆｒee(ｐ);}｝４．4.已知一個單鏈表，編寫一個函數(shù)從此單鏈表中刪除自第i個元素起的lｅngth個元素。解：實現(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個元素*/??{ｐ=hｅad；／*p指向要刪除的結(jié)點＊/ head=heａd->next;?? frｅe(ｐ);? }?eｌse解：實現(xiàn)本題功能的函數(shù)如下：voiddeletelength(noｄｅ*hｅａd，inti，intlenｇth）｛node*p,*q;?intj;?if(i==1） ?for(j=1;ｊ<=ｌeｎgtｈ;j++）/＊刪除前k個元素*／? ｛p=heａd;/*p指向要刪除的結(jié)點*/ ? hｅad=head－>next；???frｅe（p);??} elｓe{p=head; ?fｏr(j＝1；j＜＝i-2;j++) p＝p->ｎexｔ;/*ｐ指向要刪除的結(jié)點的前一個結(jié)點＊／??for(j=1;j<=length;j+＋)? ｛ ?q=p->next;/*q指向要刪除的結(jié)點*/?? p->ｎext=ｑ->nｅxt; ?free(q);? } }｝5．已知一個遞增有序的單鏈表，編寫一個函數(shù)向該單鏈表中插入一個元素為ｘ的結(jié)點,使插入后該鏈表仍然遞增有序。解：本題算法的思想是:先建立一個待插入的結(jié)點,然后依次與鏈表中的各結(jié)點的數(shù)據(jù)域比較大小，找到插入該結(jié)點的位置,然后插入該結(jié)點。實現(xiàn)本題功能的函數(shù)如下:ｖｏｉｄinsert(noｄe*head,iｎtx){ node*s，*p,*q;?s=（ｎode＊)mａlloc(ｓｉzeoｆ(node))；/*建立一個待插入的結(jié)點*/ s->ｄaｔａ＝x; s－>ｎｅxt＝NULL;if(heａd=＝NＵLＬ||ｘ＜hｅad－＞dａt(yī)a)／＊若單鏈表為空或ｘ小于第一個結(jié)點ｄ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é)點＊/??q->next=s;?}}6.已知一個單鏈表,編寫一個函數(shù)將此單鏈表復(fù)制一個拷貝。解：本題算法的思想是依次查找原單鏈表(其頭指針為hｅａd1)中的每個結(jié)點,對每個結(jié)點復(fù)制一個新結(jié)點并鏈接到新的單鏈表(其頭指針為heaｄ2)中。實現(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.有一個共１０個結(jié)點的單鏈表，試設(shè)計一個函數(shù)將此單鏈表分為兩個結(jié)點數(shù)相等的單鏈表。解：本題的算法思想是：在原單鏈表一半處將其分開,第５個結(jié)點的neｘt域置為空，為第一個單鏈表的表尾。第二個單鏈表的表頭指針指向原單鏈表的第6個結(jié)點。實現(xiàn)本題功能的函數(shù)如下,函數(shù)返回生成的第二個單鏈表的表頭指針,第一個單鏈表仍然使用原單鏈表的表頭指針。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è)計一個函數(shù)，將此單鏈表提成兩個單鏈表,規(guī)定其中一個仍以原表頭指針heａd1作表頭指針,表中順序涉及原線性表的第一、三等奇數(shù)號結(jié)點;另一個鏈表以heａd２為表頭指針，表中順序涉及原單鏈表第二、四等偶數(shù)號結(jié)點。解:本題算法的思想是將第一個鏈表中的所有偶數(shù)序號的結(jié)點刪除,同時把這些結(jié)點鏈接起來構(gòu)成第二個單鏈表。實現(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ù)序號的結(jié)點*/??oｄd－>ｎext＝eveｎ->nｅxt； ?tｅmp->ｎext=even;? tｅｍp=even；? ｏdd=odd->ｎext；/*odd指向奇數(shù)序號的結(jié)點＊/ } eｖｅn->nｅxｔ=NULL;}9.已知一個指針p指向單循環(huán)鏈表中的一個結(jié)點,編寫一個對此單循環(huán)鏈表進(jìn)行遍歷的算法。解：本題的算法思想是：由于是單循環(huán)鏈表,所以只要另設(shè)一指針q指向p用來幫助判斷是否已經(jīng)遍歷一遍即可。實現(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０.已知一個單循環(huán)鏈表，編寫一個函數(shù),將所有箭頭方向取反。解：本題算法的思想是:從頭到尾掃描該循環(huán)鏈表,將第一個結(jié)點的next域置為ＮＵLL,將第二個結(jié)點的next域指向第一個結(jié)點，如此直到最后一個結(jié)點,便用head指向它。由于是循環(huán)鏈表，所以鑒定最后一個結(jié)點時不能用p->next=NUＬL作為條件,而是用q指向第一個結(jié)點，以p！=q作為條件。實現(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.在雙鏈表中,若僅知道指針ｐ指向某個結(jié)點，不知頭指針，能否根據(jù)p遍歷整個鏈表?若能,試設(shè)計算法實現(xiàn)。解:能。本題的算法思想是:分別從p開始沿著next以及ｐｒioｒ向右、向左掃描直至各自的鏈為空即可遍歷整個鏈表。實現(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.試編寫一個在循環(huán)雙向鏈表中進(jìn)行刪除操作的算法,規(guī)定刪除的結(jié)點是指定結(jié)點ｐ的前趨結(jié)點。解:實現(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é)點無前趨!\ｎ")；第三章二、算法設(shè)計題習(xí)題解答(3)一、基本知識題答案1.什么是棧?什么是隊列?它們各自的特點是什么?答：棧是限定在表的一端進(jìn)行插入或刪除操作的線性表；隊列是元素的添加在表的一端進(jìn)行,而元素的刪除在表的另一端進(jìn)行的線性表;棧的特點是后進(jìn)先出，隊列的特點是先進(jìn)先出。2.線性表、棧、隊列有什么異同?答:棧和隊列都是線性表，但是是受限的線性表,對插入、刪除運算加以限制。棧是只允許在一端進(jìn)行插入、刪除運算,因而是后進(jìn)先出表；而隊列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運算,因而是先進(jìn)先出表。３.簡述棧的入棧、出棧操作的過程。答:棧的入棧、出棧操作均在棧頂進(jìn)行，棧頂指針指向棧頂元素的下一個位置。入棧操作先將入棧元素放到棧頂指針?biāo)甘镜奈恢蒙?，然后將棧頂指針加１。出棧操作先將棧頂指針減1，然后從棧頂指針指向位置取值。4.在循環(huán)隊列中簡述入隊、出隊操作的過程。答：在循環(huán)隊列中,設(shè)隊首指針指向隊首元素,隊尾指針指向隊尾元素后的一個空閑元素。在隊列不滿時,可執(zhí)行入隊操作,此時先送值到隊尾指針指向的空閑元素,隊尾指針再加１(要取模)。在隊列不空時,可執(zhí)行出隊操作,此時先從隊首指針指向處取值，隊首指針再加1(要取模）。二、算法設(shè)計題答案1.設(shè)用一維數(shù)組stack[n]表達(dá)一個堆棧,若堆棧中一個元素需占用lｅｎgｔh個數(shù)組單元(lengｔh＞１),試寫出其入棧、出棧操作的算法。解:用一整型變量tｏｐ表達(dá)棧頂指針，top為０時表達(dá)棧為空。假如棧不空，則從stａck［1]開始存放元素。實現(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.試編寫一個遍歷及顯示隊列中元素的算法。解:設(shè)表達(dá)式在字符數(shù)組a[]中，使用一堆棧S來幫助判斷。實現(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；／＊配對對的*/ ?elｓereｔurｎ0；/*配對錯誤*/｝3．設(shè)一循環(huán)隊列Queｕe,只有頭指針front，不設(shè)尾指針，另設(shè)一個內(nèi)含元素個數(shù)的計數(shù)器，試寫出相應(yīng)的入隊、出隊算法。解:實現(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è)計一算法能判斷一個算術(shù)表達(dá)式中的圓括號配對是否對的。（提醒:對表達(dá)式進(jìn)行掃描，凡碰到“(”就進(jìn)棧,碰到“)”就退出棧頂?shù)摹?”，表達(dá)式掃描完畢時棧若為空則圓括號配對對的。)解：用一個循環(huán)數(shù)組Queue[0，ｎ－1]表達(dá)該循環(huán)隊列,頭指針為fｒｏnｔ，計數(shù)器cｏunt用來記錄隊列中結(jié)點的個數(shù)。入隊算法如下:voidenquｅue(intx){?ｉｎttｅmp； if（count==ｎ) ?ｐrintf("隊列上溢出\n"）;?else｛ ?ｃouｎt++;??ｔemp＝（front+cｏｕｎt)％n; Ｑueuｅ［ｔemp]=x; }｝出隊算法如下：intdｅqueue(){intｔeｍp；iｆ(coｕnt==0） priｎtf("隊列下溢出\n")； eｌse ｛ｔemp=Queue［fronｔ］; froｎｔ=(frｏnt＋１)%n；count－-; ?ｒetuｒnｔeｍp；?}}數(shù)據(jù)結(jié)構(gòu)（本科)期末綜合練習(xí)一（單選題）單選題１.一個數(shù)組元素a[ｉ]與(A)的表達(dá)等價。A.*（a＋i)B.a＋iC．＊a＋iD.＆a+i２.若需要運用形參直接訪問實參，則應(yīng)把形參變量說明為(Ｂ)參數(shù)。A.指針B.引用C.傳值D.常值3.下面程序段的時間復(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í)行下面程序段時，執(zhí)行Ｓ語句的次數(shù)為（D)。for(inｔi=1；ｉ<=n;ｉ++)fｏr(intj＝１；j<=ｉ;j++)Ｓ;A．ｎ２B.n2/2C.ｎ（n＋１）D.ｎ（n+1)／25.下面算法的時間復(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ù)抽象Ｄ.類型說明7.當(dāng)一個作為實際傳遞的對象占用的存儲空間較大并也許被修改時，應(yīng)最佳說明為(Ｂ),以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。Ａ.基本類型B.引用型C．指針型D.常值引用型８.當(dāng)需要進(jìn)行標(biāo)準(zhǔn)I/O操作時,則應(yīng)在程序文獻(xiàn)中包含ioｓtrｅam.h頭文獻(xiàn)，當(dāng)需要進(jìn)行文獻(xiàn)Ｉ／O操作時，則應(yīng)在程序文獻(xiàn)中包含(A)頭文獻(xiàn)。A.fstreａm.hB．stdlib．hC.ｉｏmanip.hD.ｓtring.h9.一個記錄ｒ理論上占有的存儲空間的大小等于所有域類型長度之和,事實上占有的存儲空間的大小即記錄長度為(Ｄ)。A.所有域長度之和Ｂ.最大域所占字節(jié)長度Ｃ．任意一個域長度Ｄ．ｓｉｚeof(ｒ)的值1０.輸出一個二維數(shù)組b[ｍ][n］中所有元素值的時間復(fù)雜度為(Ｄ)。A.O（ｎ)B.O(m＋n）C.O（n２)Ｄ.O（m*n）11.一個算法的時間復(fù)雜度為(3n2+2ｎlog2n+4ｎ-７)/（5ｎ),其數(shù)量級形式的復(fù)雜度表達(dá)為（Ａ)。A.O(n)B．O（nｌｏg2n)C．O(n２）Ｄ.O(log2n)12.某算法的時間代價為T(n)=１00n+1０nｌog2n+ｎ2+10，其時間復(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，則該算法的時間復(fù)雜度為（C）。A.O(n)Ｂ.Ｏ(n2）C.O(n３)D.Ｏ(1)14.以下說法錯誤的是（Ｃ）。A.抽象數(shù)據(jù)類型具有封裝性。B．抽象數(shù)據(jù)類型具有信息隱蔽性。Ｃ.使用抽象數(shù)據(jù)類型的用戶可以自己定義對抽象數(shù)據(jù)類型中數(shù)據(jù)的各種操作。Ｄ.抽象數(shù)據(jù)類型的一個特點是使用與實現(xiàn)分離。15．在二維數(shù)組中,每個數(shù)組元素同時處在(Ｃ）個向量中。A.０個? B.１個??C．2個 D．n個16．多維數(shù)組事實上是由嵌套的（A）實現(xiàn)的。A．一維數(shù)組B.多項式Ｃ.三元組表D.簡樸變量１7.在一個長度為n的順序表中順序搜索一個值為x的元素時,在等概率的情況下,搜索成功時的數(shù)據(jù)平均比較次數(shù)為（C）。A.nB.ｎ/2C．（n＋1)／2D.（n-1)/218．在一個長度為n的順序表中向第ｉ個元素（0≤i≤ｎ-1)位置插入一個新元素時,需要從后向前依次后移（A)個元素。A.n-iB.n－i+1C.ｎ－i-1D．i19.在一個長度為n的順序表中刪除第ｉ個元素（０≤i≤n-1）時，需要從前向后依次前移（C)個元素。