2023年人武學院數(shù)據(jù)結構課后習題答案及期末綜合練習

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