數(shù)據(jù)結(jié)構(gòu)與算法習題集(C語言版)

.PAGE1.第一章概論自測題答案一、填空題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和運算等的學科。2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為〔D,R,其中D是數(shù)據(jù)元素的有限集合,R是D上的關(guān)系有限集合。3.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算這三個方面的內(nèi)容。4.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類,它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。5.線性結(jié)構(gòu)中元素之間存在一對一關(guān)系,樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系,圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。6．在線性結(jié)構(gòu)中,第一個結(jié)點沒有前驅(qū)結(jié)點,其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點沒有后續(xù)結(jié)點,其余每個結(jié)點有且只有1個后續(xù)結(jié)點。7.在樹形結(jié)構(gòu)中,樹根結(jié)點沒有前驅(qū)結(jié)點,其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；葉子結(jié)點沒有后續(xù)結(jié)點,其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個。8.在圖形結(jié)構(gòu)中,每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以任意多個。9．數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示,它們分別是順序、鏈式、索引和散列。10.數(shù)據(jù)的運算最常用的有5種,它們分別是插入、刪除、修改、查找、排序。11.一個算法的效率可分為時間效率和空間效率。二、單項選擇題〔B1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A一對多關(guān)系B多對多關(guān)系C多對一關(guān)系D一對一關(guān)系〔C2.數(shù)據(jù)結(jié)構(gòu)中,與所使用的計算機無關(guān)的是數(shù)據(jù)的結(jié)構(gòu)；A>存儲B>物理C>邏輯D>物理和存儲〔C3.算法分析的目的是：A>找出數(shù)據(jù)結(jié)構(gòu)的合理性B>研究算法中的輸入和輸出的關(guān)系C>分析算法的效率以求改進D>分析算法的易懂性和文檔性〔A4.算法分析的兩個主要方面是：A>空間復雜性和時間復雜性B>正確性和簡明性C>可讀性和文檔性D>數(shù)據(jù)復雜性和程序復雜性〔C5.計算機算法指的是：A>計算方法B>排序方法C>解決問題的有限運算序列D>調(diào)度方法〔B6.計算機算法必須具備輸入、輸出和等5個特性。A>可行性、可移植性和可擴充性B>可行性、確定性和有窮性C>確定性、有窮性和穩(wěn)定性D>易讀性、穩(wěn)定性和安全性三、簡答題2.[嚴題集1.2②]數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎？答：簡單地說,數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素,而且還在其上定義了一組操作。3.簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點。答：線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的,非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是多對多的。四、[嚴題集1.8④]分析下面各程序段的時間復雜度2.2.s=0;fori=0;i<n;i++>for<j=0;j<n;j++>s+=B[i][j];sum=s;答：O〔n21.1.for<i=0;i<n;i++>for<j=0;j<m;j++>A[i][j]=0;答：O〔m*n3.3.x=0;for<i=1;i<n;i++>for<j=1;j<=n-i;j++>x++;解：因為x++共執(zhí)行了n-1+n-2+……＋1=n<n-1>/2,所以執(zhí)行時間為O〔n24.4.i=1;while<i<=n>i=i*3;答：O〔log3n五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=〔D,R,試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示,并確定相對于關(guān)系R,哪些結(jié)點是開始結(jié)點,哪些結(jié)點是終端結(jié)點？1.[嚴蔚敏習題集P71.3②]D={d1,d2,d3,d4}R={<d1,d2>,<d2,d3>,<d3,d4>}答：d1→d2→d3→d4d1—無直接前驅(qū),是首結(jié)點d4—無直接后繼是尾結(jié)點2。D={d1,d2,…,d9}R={<d1,d2>,<d1,d3>,<d3,d4>,<d3,d6>,<d6,d8>,<d4,d5>,<d6,d7>,<d8,d9>}答：此圖為樹形結(jié)構(gòu)d1—無直接前驅(qū),是根結(jié)點d2,d5,d7,d9—無直接后繼是葉子結(jié)點3．D={d1,d2,…,d9}R={<d1,d3>,<d1,d8>,<d2,d3>,<d2,d4>,<d2,d5>,<d3,d9>,<d5,d6>,<d8,d9>,<d9,d7>,<d4,d7>,<d4,d6>}答：此圖為圖形結(jié)構(gòu)d1,d2—無直接前驅(qū),是開始結(jié)點d6,d7—無直接后繼是終端結(jié)點<2><3>第2章自測卷答案一、填空1.[嚴題集2.2①]在順序表中插入或刪除一個元素,需要平均移動表中一半元素,具體移動的元素個數(shù)與表長和該元素在表中的位置有關(guān)。2.線性表中結(jié)點的集合是有限的,結(jié)點間的關(guān)系是一對一的。3.向一個長度為n的向量的第i個元素<1≤i≤n+1>之前插入一個元素時,需向后移動n-i+1個元素。4.向一個長度為n的向量中刪除第i個元素<1≤i≤n>時,需向前移動n-i個元素。5.在順序表中訪問任意一結(jié)點的時間復雜度均為O<1>,因此,順序表也稱為隨機存取的數(shù)據(jù)結(jié)構(gòu)。6.[嚴題集2.2①]順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。7.[嚴題集2.2①]在單鏈表中,除了首元結(jié)點外,任一結(jié)點的存儲位置由其直接前驅(qū)結(jié)點的鏈域的值指示。8．在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p,需找到它的前驅(qū)結(jié)點的地址,其時間復雜度為O〔n。二、判斷正誤〔在正確的說法后面打勾,反之打叉〔×1.鏈表的每個結(jié)點中都恰好包含一個指針。答：錯誤。鏈表中的結(jié)點可含多個指針域,分別存放多個指針。例如,雙向鏈表中的結(jié)點可以含有兩個指針域,分別存放指向其直接前趨和直接后繼結(jié)點的指針?！病?.鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。錯,鏈表的存儲結(jié)構(gòu)特點是無序,而鏈表的示意圖有序?！病?.鏈表的刪除算法很簡單,因為當刪除鏈中某個結(jié)點后,計算機會自動地將后續(xù)的各個單元向前移動。錯,鏈表的結(jié)點不會移動,只是指針內(nèi)容改變?！病?.線性表的每個結(jié)點只能是一個簡單類型,而鏈表的每個結(jié)點可以是一個復雜類型。錯,混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu),鏈表也是線性表！且即使是順序表,也能存放記錄型數(shù)據(jù)?！病?.順序表結(jié)構(gòu)適宜于進行順序存取,而鏈表適宜于進行隨機存取。錯,正好說反了。順序表才適合隨機存取,鏈表恰恰適于"順藤摸瓜"〔×6.順序存儲方式的優(yōu)點是存儲密度大,且插入、刪除運算效率高。錯,前一半正確,但后一半說法錯誤,那是鏈式存儲的優(yōu)點。順序存儲方式插入、刪除運算效率較低,在表長為n的順序表中,插入和刪除一個數(shù)據(jù)元素,平均需移動表長一半個數(shù)的數(shù)據(jù)元素。〔×7.線性表在物理存儲空間中也一定是連續(xù)的。錯,線性表有兩種存儲方式,順序存儲和鏈式存儲。后者不要求連續(xù)存放?！病?.線性表在順序存儲時,邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式,在順序存儲時,邏輯上相鄰的元素在存儲的物理位置次序上也相鄰?！病?.順序存儲方式只能用于存儲線性結(jié)構(gòu)。錯誤。順序存儲方式不僅能用于存儲線性結(jié)構(gòu),還可以用來存放非線性結(jié)構(gòu),例如完全二叉樹是屬于非線性結(jié)構(gòu),但其最佳存儲方式是順序存儲方式?！埠笠还?jié)介紹〔×10.線性表的邏輯順序與存儲順序總是一致的。錯,理由同7。鏈式存儲就無需一致。三、單項選擇題〔C1．數(shù)據(jù)在計算機存儲器內(nèi)表示時,物理地址與邏輯地址相同并且是連續(xù)的,稱之為：〔A存儲結(jié)構(gòu)〔B邏輯結(jié)構(gòu)〔C順序存儲結(jié)構(gòu)〔D鏈式存儲結(jié)構(gòu)〔B2.一個向量第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是〔A110〔B108〔C100〔D120〔A3.在n個結(jié)點的順序表中,算法的時間復雜度是O〔1的操作是：訪問第i個結(jié)點〔1≤i≤n和求第i個結(jié)點的直接前驅(qū)〔2≤i≤n在第i個結(jié)點后插入一個新結(jié)點〔1≤i≤n刪除第i個結(jié)點〔1≤i≤n將n個結(jié)點從小到大排序〔B4.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變,平均要移動個元素〔A8〔B63.5〔C63〔D7〔A5.鏈接存儲的存儲結(jié)構(gòu)所占存儲空間：分兩部分,一部分存放結(jié)點值,另一部分存放表示結(jié)點間關(guān)系的指針只有一部分,存放結(jié)點值〔C只有一部分,存儲表示結(jié)點間關(guān)系的指針〔D分兩部分,一部分存放結(jié)點值,另一部分存放結(jié)點所占單元數(shù)〔B6.鏈表是一種采用存儲結(jié)構(gòu)存儲的線性表；〔A順序〔B鏈式〔C星式〔D網(wǎng)狀〔D7.線性表若采用鏈式存儲結(jié)構(gòu)時,要求內(nèi)存中可用存儲單元的地址:〔A必須是連續(xù)的〔B部分地址必須是連續(xù)的〔C一定是不連續(xù)的〔D連續(xù)或不連續(xù)都可以〔B8．線性表Ｌ在情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)?！玻列杞?jīng)常修改Ｌ中的結(jié)點值〔Ｂ需不斷對Ｌ進行刪除插入〔ＣＬ中含有大量的結(jié)點〔ＤＬ中結(jié)點結(jié)構(gòu)復雜〔C9．單鏈表的存儲密度〔Ａ大于1；〔Ｂ等于1；〔Ｃ小于1；〔Ｄ不能確定〔B10．設(shè)a1、a2、a3為3個結(jié)點,整數(shù)P0,3,4代表地址,則如下的鏈式存儲結(jié)構(gòu)稱為P034P0a13a24A30〔Ａ循環(huán)鏈表〔Ｂ單鏈表〔Ｃ雙向循環(huán)鏈表〔Ｄ雙向鏈表四、簡答題1.[嚴題集2.3②]試比較順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好？答：①順序存儲時,相鄰數(shù)據(jù)元素的存放地址也相鄰〔邏輯與物理統(tǒng)一；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點：存儲密度大〔＝1？,存儲空間利用率高。缺點：插入或刪除元素時不方便。②鏈式存儲時,相鄰數(shù)據(jù)元素可隨意存放,但所占存儲空間分兩部分,一部分存放結(jié)點值,另一部分存放表示結(jié)點間關(guān)系的指針優(yōu)點：插入或刪除元素時很方便,使用靈活。缺點：存儲密度小〔<1,存儲空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大,且其主要操作是查找,則采用順序表；若線性表的長度變化較大,且其主要操作是插入、刪除操作,則采用鏈表。2.[嚴題集2.1①]描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點〔第一個元素結(jié)點。在單鏈表中設(shè)置頭結(jié)點的作用是什么？答：首元結(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素a1的結(jié)點。為了操作方便,通常在鏈表的首元結(jié)點之前附設(shè)一個結(jié)點,稱為頭結(jié)點,該結(jié)點的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素,其作用是為了對鏈表進行操作時,可以對空表、非空表的情況以及對首元結(jié)點進行統(tǒng)一處理。頭指針是指向鏈表中第一個結(jié)點〔或為頭結(jié)點或為首元結(jié)點的指針。若鏈表中附設(shè)頭結(jié)點,則不管線性表是否為空表,頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個概念對單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點,是不同的存儲結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題。頭結(jié)點headdatalink頭指針首元結(jié)點簡而言之,頭指針是指向鏈表中第一個結(jié)點〔或為頭結(jié)點或為首元結(jié)點的指針；頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標志和表長等信息〔內(nèi)放頭指針？那還得另配一個頭指針?。?！首元素結(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素a1的結(jié)點。第3章棧和隊列自測卷答案姓名班級題號一二三四五六總分題分151020202015100得分一、填空題〔每空1分,共15分1.[李春葆]向量、棧和隊列都是線性結(jié)構(gòu),可以在向量的任何位置插入和刪除元素；對于棧只能在棧頂插入和刪除元素；對于隊列只能在隊尾插入和隊首刪除元素。2.棧是一種特殊的線性表,允許插入和刪除運算的一端稱為棧頂。不允許插入和刪除運算的一端稱為棧底。3.隊列是被限定為只能在表的一端進行插入運算,在表的另一端進行刪除運算的線性表。4.在一個循環(huán)隊列中,隊首指針指向隊首元素的前一個位置。5.在具有n個單元的循環(huán)隊列中,隊滿時共有n-1個元素。6.向棧中壓入元素的操作是先移動棧頂指針,后存入元素。7.從循環(huán)隊列中刪除一個元素時,其操作是先移動隊首指針,后取出元素。8.〖00年統(tǒng)考題〗帶表頭結(jié)點的空循環(huán)雙向鏈表的長度等于0。L=head頭結(jié)點RL=head頭結(jié)點R=headhead二、判斷正誤〔判斷下列概念的正確性,并作出簡要的說明?！裁啃☆}1分,共10分〔×1.線性表的每個結(jié)點只能是一個簡單類型,而鏈表的每個結(jié)點可以是一個復雜類型。錯,線性表是邏輯結(jié)構(gòu)概念,可以順序存儲或鏈式存儲,與元素數(shù)據(jù)類型無關(guān)?！病?.在表結(jié)構(gòu)中最常用的是線性表,棧和隊列不太常用。錯,不一定吧？調(diào)用子程序或函數(shù)常用,CPU中也用隊列?！病?.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表,是一種后進先出型結(jié)構(gòu)?！病?.對于不同的使用者,一個表結(jié)構(gòu)既可以是棧,也可以是隊列,也可以是線性表。正確,都是線性邏輯結(jié)構(gòu),棧和隊列其實是特殊的線性表,對運算的定義略有不同而已?！病?.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。錯,棧是邏輯結(jié)構(gòu)的概念,是特殊殊線性表,而鏈表是存儲結(jié)構(gòu)概念,二者不是同類項。〔×6.棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯,他們都是線性邏輯結(jié)構(gòu),棧和隊列其實是特殊的線性表,對運算的定義略有不同而已?！病?.棧和隊列的存儲方式既可是順序方式,也可是鏈接方式?！病?.兩個棧共享一片連續(xù)內(nèi)存空間時,為提高內(nèi)存利用率,減少溢出機會,應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端?！病?.隊是一種插入與刪除操作分別在表的兩端進行的線性表,是一種先進后出型結(jié)構(gòu)。錯,后半句不對?！病?0.一個棧的輸入序列是12345,則棧的輸出序列不可能是12345。錯,有可能。三、單項選擇題〔每小題1分,共20分〔B1.〖00年元月統(tǒng)考題〗棧中元素的進出原則是Ａ．先進先出Ｂ．后進先出Ｃ．?？談t進Ｄ．棧滿則出〔C2.〖李春葆〗若已知一個棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不確定解釋：當p1=n,即n是最先出棧的,根據(jù)棧的原理,n必定是最后入棧的〔事實上題目已經(jīng)表明了,那么輸入順序必定是1,2,3,…,n,則出棧的序列是n,…,3,2,1?！踩舨灰箜樞虺鰲?則輸出序列不確定〔B3.〖李春葆〗判定一個棧ST〔最多元素為m0為空的條件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0〔A4.〖李春葆〗判定一個隊列QU〔最多元素為m0為滿隊列的條件是Ａ．QU->rear－QU->front==m0Ｂ．QU->rear－QU->front－1==m0Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1解：隊滿條件是元素個數(shù)為m0。由于約定滿隊時隊首指針與隊尾指針相差1,所以不必再減1了,應(yīng)當選A。當然,更正確的答案應(yīng)該取模,即：QU->front==<QU->rear+1>%m0〔D5．數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列,ｆ為當前隊列頭元素的前一位置,ｒ為隊尾元素的位置,假定隊列中元素的個數(shù)小于ｎ,計算隊列中元素的公式為〔Ａr－f;〔Ｂ〔n＋f－r%n;〔Ｃn＋r－f;〔Ｄ〔n＋r－f%n6.[98初程P71]從供選擇的答案中,選出應(yīng)填入下面敘述？內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。設(shè)有4個數(shù)據(jù)元素a1、a2、a3和a4,對他們分別進行棧操作或隊操作。在進棧或進隊操作時,按a1、a2、a3、a4次序每次進入一個元素。假設(shè)棧或隊的初始狀態(tài)都是空。現(xiàn)要進行的棧操作是進棧兩次,出棧一次,再進棧兩次,出棧一次；這時,第一次出棧得到的元素是A,第二次出棧得到的元素是B是；類似地,考慮對這四個數(shù)據(jù)元素進行的隊操作是進隊兩次,出隊一次,再進隊兩次,出隊一次；這時,第一次出隊得到的元素是C,第二次出隊得到的元素是D。經(jīng)操作后,最后在棧中或隊中的元素還有E個。供選擇的答案：A～D：①a1②a2③a3④a4E：①1②2③3④0答：ABCDE＝2,4,1,2,27.[94初程P75]從供選擇的答案中,選出應(yīng)填入下面敘述？內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。棧是一種線性表,它的特點是A。設(shè)用一維數(shù)組A[1,…,n]來表示一個棧,A[n]為棧底,用整型變量T指示當前棧頂位置,A[T]為棧頂元素。往棧中推入〔PUSH一個新元素時,變量T的值B；從棧中彈出〔POP一個元素時,變量T的值C。設(shè)?？諘r,有輸入序列a,b,c,經(jīng)過PUSH,POP,PUSH,PUSH,POP操作后,從棧中彈出的元素的序列是D,變量T的值是E。供選擇的答案：A：①先進先出②后進先出 ③進優(yōu)于出 ④出優(yōu)于進 ⑤隨機進出B,C： ①加1②減1③不變 ④清0⑤加2⑥減2D：①a,b②b,c③c,a④b,a⑤c,b⑥a,cE：①n+1②n+2③n ④n-1⑤n-2答案：ABCDE=2,2,1,6,4注意,向地址的高端生長,稱為向上生成堆棧；向地址低端生長叫向下生成堆棧,本題中底部為n,向地址的低端遞減生成,稱為向下生成堆棧。8.[91初程P77]從供選擇的答案中,選出應(yīng)填入下面敘述？內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。在做進棧運算時,應(yīng)先判別棧是否A；在做退棧運算時,應(yīng)先判別棧是否B。當棧中元素為n個,做進棧運算時發(fā)生上溢,則說明該棧的最大容量為C。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內(nèi)存空間時,應(yīng)將兩棧的D分別設(shè)在這片內(nèi)存空間的兩端,這樣,只有當E時,才產(chǎn)生上溢。供選擇的答案：A,B：①空②滿③上溢④下溢C： ①n-1②n③n+1④n/2D：①長度②深度③棧頂④棧底E：①兩個棧的棧頂同時到達?？臻g的中心點②其中一個棧的棧頂?shù)竭_?？臻g的中心點③兩個棧的棧頂在達?？臻g的某一位置相遇④兩個棧均不空,且一個棧的棧頂?shù)竭_另一個棧的棧底答案：ABCDE＝2,1,2,4,3四、簡答題〔每小題4分,共20分1.[嚴題集3.2①和3.11①]說明線性表、棧與隊的異同點。劉答：相同點：都是線性結(jié)構(gòu),都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表,即受限的線性表,只是對插入、刪除運算加以限制。不同點：①運算規(guī)則不同,線性表為隨機存取,而棧是只允許在一端進行插入、刪除運算,因而是后進先出表LIFO；隊列是只允許在一端進行插入、另一端進行刪除運算,因而是先進先出表FIFO。②用途不同,堆棧用于子程調(diào)用和保護現(xiàn)場,隊列用于多道作業(yè)處理、指令寄存及其他運算等等。2.[統(tǒng)考書P604-11,難于嚴題集3.1①]設(shè)有編號為1,2,3,4的四輛列車,順序進入一個棧式結(jié)構(gòu)的車站,具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。①全進之后再出情況,只有1種：4,3,2,1②進3個之后再出的情況,有3種,3,4,2,13,2,4,13,2,1,4③進2個之后再出的情況,有5種,2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④進1個之后再出的情況,有5種,1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,33.[劉自編]假設(shè)正讀和反讀都相同的字符序列為"回文",例如,‘a(chǎn)bba’和‘a(chǎn)bcba’是回文,‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。假設(shè)一字符序列已存入計算機,請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？答：線性表是隨機存儲,可以實現(xiàn),靠循環(huán)變量〔j--從表尾開始打印輸出；堆棧是后進先出,也可以實現(xiàn),靠正序入棧、逆序出棧即可；隊列是先進先出,不易實現(xiàn)。哪種方式最好,要具體情況具體分析。若正文在機內(nèi)已是順序存儲,則直接用線性表從后往前讀取即可,或?qū)⒍褩ｍ旈_到數(shù)組末尾,然后直接用POP動作實現(xiàn)。〔但堆棧是先減后壓還是……若正文是單鏈表形式存儲,則等同于隊列,需開輔助空間,可以從鏈首開始入棧,全部壓入后再依次輸出。4.[統(tǒng)考書P604-13]順序隊的"假溢出"是怎樣產(chǎn)生的？如何知道循環(huán)隊列是空還是滿？答：一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界,不能再有入隊操作,但其實數(shù)組中還有空位置,這就叫"假溢出"。采用循環(huán)隊列是解決假溢出的途徑。另外,解決隊滿隊空的辦法有三：設(shè)置一個布爾變量以區(qū)別隊滿還是隊空；浪費一個元素的空間,用于區(qū)別隊滿還是隊空。使用一個計數(shù)器記錄隊列中元素個數(shù)〔即隊列長度。我們常采用法②,即隊頭指針、隊尾指針中有一個指向?qū)嵲?而另一個指向空閑元素。判斷循環(huán)隊列隊空標志是：f=rear隊滿標志是：f=<r+1>%N5.[統(tǒng)考書P604-14]設(shè)循環(huán)隊列的容量為40〔序號從0到39,現(xiàn)經(jīng)過一系列的入隊和出隊運算后,有①front=11,rear=19;②front=19,rear=11；問在這兩種情況下,循環(huán)隊列中各有元素多少個？答：用隊列長度計算公式：<N＋r－f>%N①L=〔40＋19－11%40=8②L=〔40＋11－19%40=32五、閱讀理解〔每小題5分,共20分。至少要寫出思路[嚴題集3.7①]按照四則運算加、減、乘、除和冪運算〔↑優(yōu)先關(guān)系的慣例,并仿照教材例3-2的格式,畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程：A－B×C/D+E↑F答：[嚴題集3.3②]寫出下列程序段的輸出結(jié)果〔棧的元素類型SElemType為char。voidmain<>{StackS;Charx,y;InitStack<S>;X=’c’;y=’k’;Push<S,x>;Push<S,’a’>;Push<S,y>;Pop<S,x>;Push<S,’t’>;Push<S,x>;Pop<S,x>;Push<S,’s’>;while<!StackEmpty<S>>{Pop<S,y>;printf<y>;};Printf<x>;}答：輸出為"stack"。[嚴題集3.12②]寫出下列程序段的輸出結(jié)果〔隊列中的元素類型QElemType為char。voidmain<>{QueueQ;InitQueue<Q>;Charx=’e’;y=’c’;EnQueue<Q,’h’>;EnQueue<Q,’r’>;EnQueue<Q,y>;DeQueue<Q,x>;EnQueue<Q,x>;DeQueue<Q,x>;EnQueue<Q,’a’>;while<!QueueEmpty<Q>>{DeQueue<Q,y>;printf<y>;};Printf<x>;}答：輸出為"char"。[嚴題集3.13②]簡述以下算法的功能〔棧和隊列的元素類型均為int。voidalgo3<Queue&Q>{StackS;intd;InitStack<S>;while<!QueueEmpty<Q>>{DeQueue<Q,d>;Push<S,d>;};while<!StackEmpty<S>>{Pop<S,d>;EnQueue<Q,d>;}}答：該算法的功能是：利用堆棧做輔助,將隊列中的數(shù)據(jù)元素進行逆置。六、算法設(shè)計〔每小題5分,共15分。至少要寫出思路[李春葆及嚴題集3.19④]假設(shè)一個算術(shù)表達式中包含圓括弧、方括弧和花括弧三種類型的括弧,編寫一個判別表達式中括弧是否正確配對的函數(shù)correct<exp,tag>；其中：exp為字符串類型的變量〔可理解為每個字符占用一個數(shù)組元素,表示被判別的表達式,tag為布爾型變量。答：用堆棧st進行判定,將<、[或{入棧,當遇到}、]或>時,檢查當前棧頂元素是否是對應(yīng)的<、[或{,若是則退棧,否則返回表示不配對。當整個算術(shù)表達式檢查完畢時,若棧為空表示括號正確配對,否則不配對。編程后的整個函數(shù)如下〔李書P31—32#definem0100/*m0為算術(shù)表達式中最多字符個數(shù)*/correct<exp,tag>charexp[m0];inttag;{charst[m0];inttop=0,i=1;tag=1;while<i<=m0&&tag>{if<exp[i]==‘<‘||exp[i]==’[‘||exp[i]==’{‘/*遇到‘<‘、’[‘或’{‘,則將其入棧*/{top++;st[top]=exp[i];}if<exp[i]==’>’>/*遇到’>’,若棧頂是‘<‘,則繼續(xù)處理,否則以不配對返回*/if<st[top]==‘<‘>top--;elsetag=0;if<exp[i]==’>’>/*遇到’]’,若棧頂是‘[‘,則繼續(xù)處理,否則以不配對返回*/if<st[top]==‘[‘]top--;elsetag=0;if<exp[i]==’>’>/*遇到’}’,若棧頂是‘{‘,則繼續(xù)處理,否則以不配對返回*/if<st[top]==‘{‘top--;elsetag=0;i++;}if<top>0>tag=0;/*若棧不空,則不配對*/}嚴題集對應(yīng)答案：3.19StatusAllBrackets_Test<char*str>//判別表達式中三種括號是否匹配{InitStack<s>;for<p=str;*p;p++>{if<*p=='<'||*p=='['||*p=='{'>push<s,*p>;elseif<*p=='>'||*p==']'||*p=='}'>{if<StackEmpty<s>>returnERROR;pop<s,c>;if<*p=='>'&&c!='<'>returnERROR;if<*p==']'&&c!='['>returnERROR;if<*p=='}'&&c!='{'>returnERROR;//必須與當前棧頂括號匹配}}//forif<!StackEmpty<s>>returnERROR;returnOK;}//AllBrackets_Test2001級通信6班張沐同學答案〔已上機通過#include<stdio.h>#include<stdlib.h>voidpush<charx>;voidpop<>;voidcorrect<enumBoolean&tag>;//原來的定義是voidcorrect<structStack*head,enumBoolean&tag>;typedefstructStack{ chardata; structStack*next;};structStack*head,*p;enumBoolean{FALSE,TRUE}tag;voidmain<>{ head=<structStack*>malloc<sizeof<structStack>>; head->data='S'; head->next=NULL; //head'sdatahasnotbeeninitialized!! correct<tag>; if<tag> printf<"Right!">; else printf<"Wrong!">;}voidpush<charx>{ p=<structStack*>malloc<sizeof<structStack>>; if<!p> printf<"There'snospace.\n">; else { p->data=x; p->next=head; head=p; }}//ifyoudefinethe"Correct"functionlikethat//DebugwillshowthatthePushactiondoesn’ttakeeffectionvoidpop<>{ if<head->next==NULL> printf<"Thestackisempty.\n">; else { p=head; head=head->next; free<p>; }}//voidcorrect<structStack*head,enumBoolean&tag>voidcorrect<enumBoolean&tag>{ inti; chary; printf<"Pleaseenterabds:">; for<i=0;y!='\n';i++> { scanf<"%c",&y>; if<<y=='>'&&head->data=='<'>||<y==']'&&head->data=='['>||<y=='}'&&head->data=='{'>> pop<>; elseif<<y=='<'>||<y=='['>||<y=='{'>> push<y>;/*調(diào)試程序顯示,y并沒有被推入堆棧中。即head->data的值在Push中顯示為y的值,但是出Push函數(shù)。馬上變成Null。*/ else continue; } if<head->next==NULL>//原來的程序是if<head==NULL> tag=TRUE; tag=TRUE; else tag=FALSE;}/*總結(jié)：由于head為全局變量,所以不應(yīng)該將其再次作為函數(shù)的變量。因為C語言的函數(shù)變量是傳值機制,所以在函數(shù)中對參數(shù)進行了拷貝復本,所以不能改變head的數(shù)值。*/2.[統(tǒng)考書P604-15]假設(shè)一個數(shù)組squ[m]存放循環(huán)隊列的元素。若要使這m個分量都得到利用,則需另一個標志tag,以tag為0或1來區(qū)分尾指針和頭指針值相同時隊列的狀態(tài)是"空"還是"滿"。試編寫相應(yīng)的入隊和出隊的算法。解：這就是解決隊滿隊空的三種辦法之①設(shè)置一個布爾變量以區(qū)別隊滿還是隊空〔其他兩種見簡答題；思路：一開始隊空,設(shè)tag=0,若從rear一端加到與front指針相同時,表示入隊已滿,則令tag=1；若從front一端加到與rear指針相同時,則令tag=0,表示出隊已空。3.[嚴題集3.31③]試寫一個算法判別讀入的一個以‘’為結(jié)束符的字符序列是否是"回文"。答：編程如下：intPalindrome_Test<>//判別輸入的字符串是否回文序列,是則返回1,否則返回0

{

InitStack<S>;InitQueue<Q>;

while<<c=getchar<>>!=''>

{

Push<S,c>;EnQueue<Q,c>;//同時使用棧和隊列兩種結(jié)構(gòu)

}

while<!StackEmpty<S>>

{

Pop<S,a>;DeQueue<Q,b>>;

if<a!=b>returnERROR;

}

returnOK;

}//Palindrome_Test第4～5章串和數(shù)組自測卷答案姓名班級題號一二三四五總分題分2015201530100得分一、填空題〔每空1分,共20分1.不包含任何字符〔長度為0的串稱為空串；由一個或多個空格〔僅由空格符組成的串稱為空白串。〔對應(yīng)嚴題集4.1①,簡答題：簡述空串和空格串的區(qū)別2.設(shè)S="A;/document/Mary.doc",則strlen<s>=20,"/"的字符定位的位置為3。4.子串的定位運算稱為串的模式匹配；被匹配的主串稱為目標串,子串稱為模式。5.設(shè)目標T="abccdcdccbaa",模式P="cdcc",則第6次匹配成功。6.若n為主串長,m為子串長,則串的古典〔樸素匹配算法最壞的情況下需要比較字符的總次數(shù)為<n-m+1>*m。7.假設(shè)有二維數(shù)組A6×8,每個元素用相鄰的6個字節(jié)存儲,存儲器按字節(jié)編址。已知A的起始存儲位置〔基地址為1000,則數(shù)組A的體積〔存儲量為288B；末尾元素A57的第一個字節(jié)地址為1282；若按行存儲時,元素A14的第一個字節(jié)地址為<8+4>×6+1000=1072；若按列存儲時,元素A47的第一個字節(jié)地址為<6×7＋4>×6＋1000＝1276。<注：數(shù)組是從0行0列還是從1行1列計算起呢？由末單元為A57可知,是從0行0列開始！>8.〖00年計算機系考研題〗設(shè)數(shù)組a[1…60,1…70]的基地址為2048,每個元素占2個存儲單元,若以列序為主序順序存儲,則元素a[32,58]的存儲地址為8950。答：不考慮0行0列,利用列優(yōu)先公式：LOC<aij>=LOC<ac1,c2>+[<j-c2>*<d1-c1+1>+i-c1>]*L得：LOC<a32,58>=2048+[<58-1>*<60-1+1>+32-1]]*2＝89509.三元素組表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素,它包含有三個數(shù)據(jù)項,分別表示該元素的行下標、列下標和元素值。10.求下列廣義表操作的結(jié)果：〔1GetHead[<<a,b>,<c,d>>]===<a,b>;//頭元素不必加括號〔2GetHead[GetTail[<<a,b>,<c,d>>]]===<c,d>;〔3GetHead[GetTail[GetHead[<<a,b>,<c,d>>]]]===b;〔4GetTail[GetHead[GetTail[<<a,b>,<c,d>>]]]===〔d;二、單選題〔每小題1分,共15分〔B1.〖李〗串是一種特殊的線性表,其特殊性體現(xiàn)在：Ａ．可以順序存儲Ｂ．數(shù)據(jù)元素是一個字符Ｃ．可以鏈式存儲Ｄ．數(shù)據(jù)元素可以是多個字符〔B2.〖李〗設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作：Ａ．連接Ｂ．模式匹配Ｃ．求子串Ｄ．求串長〔D3.〖李〗設(shè)串s1=’ABCDEFG’,s2=’PQRST’,函數(shù)con<x,y>返回x和y串的連接串,subs<s,i,j>返回串s的從序號i開始的j個字符組成的子串,len<s>返回串s的長度,則con<subs<s1,2,len<s2>>,subs<s1,len<s2>,2>>的結(jié)果串是：Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEF解：con<x,y>返回x和y串的連接串,即con<x,y>＝‘ABCDEFGPQRST’；subs<s,i,j>返回串s的從序號i開始的j個字符組成的子串,則subs<s1,2,len<s2>>＝subs<s1,2,5>=’BCDEF’;subs<s1,len<s2>,2>＝subs<s1,5,2>=’EF’;所以con<subs<s1,2,len<s2>>,subs<s1,len<s2>,2>>＝con<’BCDEF’,’EF’>之連接,即BCDEFEF〔A4.〖01年計算機系考研題〗假設(shè)有60行70列的二維數(shù)組a[1…60,1…70]以列序為主序順序存儲,其基地址為10000,每個元素占2個存儲單元,那么第32行第58列的元素a[32,58]的存儲地址為。〔無第0行第0列元素Ａ．16902Ｂ．16904Ｃ．14454Ｄ．答案A,B,C均不對答：此題與填空題第8小題相似?！?7列×60行＋31行×2字節(jié)＋10000=16902<B>5.設(shè)矩陣A是一個對稱矩陣,為了節(jié)省存儲,將其下三角部分〔如下圖所示按行序存放在一維數(shù)組B[1,n<n-1>/2]中,對下三角部分中任一元素ai,j<i≤j>,在一維數(shù)組B中下標k的值是：Ａ．i<i-1>/2+j-1Ｂ．i<i-1>/2+jＣ．i<i+1>/2+j-1Ｄ．i<i+1>/2+j解：注意B的下標要求從1開始。解：注意B的下標要求從1開始。先用第一個元素去套用,可能有B和C；再用第二個元素去套用B和C,B=2而C＝3〔不符；所以選B6.[91初程P78]從供選擇的答案中,選出應(yīng)填入下面敘述？內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。有一個二維數(shù)組A,行下標的范圍是0到8,列下標的范圍是1到5,每個數(shù)組元素用相鄰的4個字節(jié)存儲。存儲器按字節(jié)編址。假設(shè)存儲數(shù)組元素A[0,1]的第一個字節(jié)的地址是0。存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是A。若按行存儲,則A[3,5]和A[5,3]的第一個字節(jié)的地址分別是B和C。若按列存儲,則A[7,1]和A[2,4]的第一個字節(jié)的地址分別是D和E。供選擇的答案：A～E：①28②44③76④92⑤108⑥116⑦132⑧176⑨184⑩188答案：ABCDE=8,3,5,1,67.[94程P12]有一個二維數(shù)組A,行下標的范圍是1到6,列下標的范圍是0到7,每個數(shù)組元素用相鄰的6個字節(jié)存儲,存儲器按字節(jié)編址。那么,這個數(shù)組的體積是A個字節(jié)。假設(shè)存儲數(shù)組元素A[1,0]的第一個字節(jié)的地址是0,則存儲數(shù)組A的最后一個元素的第一個字節(jié)的地址是B。若按行存儲,則A[2,4]的第一個字節(jié)的地址是C。若按列存儲,則A[5,7]的第一個字節(jié)的地址是D。供選擇的答案A～D：①12②66③72④96⑤114⑥120⑦156⑧234⑨276⑩282〔11283〔12288答案：ABCD=12,10,3,9三、簡答題〔每小題5分,共15分1.[其他教材]已知二維數(shù)組Am,m采用按行優(yōu)先順序存放,每個元素占K個存儲單元,并且第一個元素的存儲地址為Loc<a11>,請寫出求Loc<aij>的計算公式。如果采用列優(yōu)先順序存放呢？解：公式教材已給出,此處雖是方陣,但行列公式仍不相同；按行存儲的元素地址公式是：Loc<aij>=Loc<a11>+[<i-1>*m+<j-1>]*K按列存儲的元素地址公式是：Loc<aij>=Loc<a11>+[<j-1>*m+<i-1>]*K2.[全國專升本資格考試]遞歸算法比非遞歸算法花費更多的時間,對嗎？為什么？答：不一定。時間復雜度與樣本個數(shù)n有關(guān),是指最深層的執(zhí)行語句耗費時間,而遞歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的,循環(huán)的次數(shù)也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同,遞歸用棧隱含循環(huán)次數(shù),非遞歸用循環(huán)變量來顯示循環(huán)次數(shù)而已。四、計算題〔每題5分,共20分設(shè)s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’,求Replace<s,’STUDENT’,q>和Concat<SubString<s,6,2>,Concat<t,SubString<s,7,8>>>。解：①Replace<s,’STUDENT’,q>＝’IAMAWORKER’②因為SubString<s,6,2>＝‘A’；SubString<s,7,8>＝‘STUDENT’Concat<t,SubString<s,7,8>>＝’GOODSTUDENT’所以Concat<SubString<s,6,2>,Concat<t,SubString<s,7,8>>>＝‘AGOODSTUDENT’2.〔P604-18用三元組表表示下列稀疏矩陣：解：參見填空題4.三元素組表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素,它包含有三個數(shù)據(jù)項,分別表示該元素的行下標、列下標和元素值。所以〔1可列表為：〔2可列表為：886666416-22594356533233685467858123.〔P604-19下列各三元組表分別表示一個稀疏矩陣,試寫出它們的稀疏矩陣。解：〔1為6×4矩陣,非零元素有6個?！?為4×5矩陣,非零元素有5個020200120003000000400601600010000000900800600700五、算法設(shè)計題〔每題10分,共30分[嚴題集4.12③]編寫一個實現(xiàn)串的置換操作Replace<&S,T,V>的算法。解：intReplace<Stringtype&S,StringtypeT,StringtypeV>;//將串S中所有子串T替換為V,并返回置換次數(shù){for<n=0,i=1;i<=Strlen<S>-Strlen<T>+1;i++>//注意i的取值范圍if<!StrCompare<SubString<S,i,Strlen<T>>,T>>//找到了與T匹配的子串{//分別把T的前面和后面部分保存為head和tailStrAssign<head,SubString<S,1,i-1>>;StrAssign<tail,SubString<S,i+Strlen<T>,Strlen<S>-i-Strlen<T>+1>>;StrAssign<S,Concat<head,V>>;StrAssign<S,Concat<S,tail>>;//把head,V,tail連接為新串i+=Strlen<V>;//當前指針跳到插入串以后n++;n++;}//ifreturnn;}//Replace分析:i+=Strlen<V>;這一句是必需的,也是容易忽略的.如省掉這一句,則在某些情況下,會引起不希望的后果,雖然在大多數(shù)情況下沒有影響.請思考:設(shè)S='place',T='ace',V='face',則省掉i+=Strlen<V>;運行時會出現(xiàn)什么結(jié)果?[嚴題集5.18⑤]試設(shè)計一個算法,將數(shù)組An中的元素A[0]至A[n-1]循環(huán)右移k位,并要求只用一個元素大小的附加存儲,元素移動或交換次數(shù)為O<n>解：分析:要把A的元素循環(huán)右移k位,則A[0]移至A[k],A[k]移至A[2k]直到最終回到A[0].然而這并沒有全部解決問題,因為有可能有的元素在此過程中始終沒有被訪問過,而是被跳了過去.分析可知,當n和k的最大公約數(shù)為p時,只要分別以A[0],A[1],...A[p-1]為起點執(zhí)行上述算法,就可以保證每一個元素都被且僅被右移一次,從而滿足題目要求.也就是說,A的所有元素分別處在p個"循環(huán)鏈"上面.舉例如下:n=15,k=6,則p=3.第一條鏈:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]./已"順便"移動了A[6]、A[12]…第二條鏈:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].第三條鏈:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].恰好使所有元素都右移一次.雖然未經(jīng)數(shù)學證明,但作者相信上述規(guī)律應(yīng)該是正確的.程序如下：voidRSh<intA[n],intk>//把數(shù)組A的元素循環(huán)右移k位,只用一個輔助存儲空間{for<i=1;i<=k;i++>if<n%i==0&&k%i==0>p=i;//求n和k的最大公約數(shù)pfor<i=0;i<p;i++>{j=i;l=<i+k>%n;temp=A[i];while<l!=i>{A[j]=temp;temp=A[l];A[l]=A[j];j=l;l=<j+k>%n;}//循環(huán)右移一步A[i]=temp;}//for}//RSh附加題：利用C的庫函數(shù)strlen,strcpy〔或strncpy寫一個算法voidStrDelete<char*S,intt,intm>,刪除串S中從位置i開始的連續(xù)的m個字符。若i≥strlen<S>,則沒有字符被刪除；若i+m≥strlen<S>,則將S中從位置i開始直至末尾的字符均被刪去。提示：strlen是求串長<length>函數(shù)：intstrlen<chars>;//求串的長度strcpy是串復制<copy>函數(shù)：char*strcpy<charto,charfrom>;//該函數(shù)將串from復制到串to中,并且返回一個指向串to的開始處的指針。第6章樹和二叉樹自測卷解答姓名班級題號一二三四五六總分題分101511202024100得分一、下面是有關(guān)二叉樹的敘述,請判斷正誤〔每小題1分,共10分〔√1.若二叉樹用二叉鏈表作存貯結(jié)構(gòu),則在n個結(jié)點的二叉樹鏈表中只有n—1個非空指針域?！病?.二叉樹中每個結(jié)點的兩棵子樹的高度差等于1?！病?.二叉樹中每個結(jié)點的兩棵子樹是有序的?！病?.二叉樹中每個結(jié)點有兩棵非空子樹或有兩棵空子樹?！病?.二叉樹中每個結(jié)點的關(guān)鍵字值大于其左非空子樹〔若存在的話所有結(jié)點的關(guān)鍵字值,且小于其右非空子樹〔若存在的話所有結(jié)點的關(guān)鍵字值?！矐?yīng)當是二叉排序樹的特點〔×6.二叉樹中所有結(jié)點個數(shù)是2k-1-1,其中k是樹的深度?！矐?yīng)2i-1〔×7.二叉樹中所有結(jié)點,如果不存在非空左子樹,則不存在非空右子樹?！病?.對于一棵非空二叉樹,它的根結(jié)點作為第一層,則它的第i層上最多能有2i—1個結(jié)點?！矐?yīng)2i-1〔√9.用二叉鏈表法〔link-rlink存儲包含n個結(jié)點的二叉樹,結(jié)點的2n個指針區(qū)域中有n+1個為空指針?！舱_。用二叉鏈表存儲包含n個結(jié)點的二叉樹,結(jié)點共有2n個鏈域。由于二叉樹中,除根結(jié)點外,每一個結(jié)點有且僅有一個雙親,所以只有n-1個結(jié)點的鏈域存放指向非空子女結(jié)點的指針,還有n+1個空指針。即有后繼鏈接的指針僅n-1個?！病?0.〖01年計算機系研題〗具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點。最快方法：用葉子數(shù)＝[n/2]＝6,再求n2=n0-1=5二、填空〔每空1分,共15分1．由３個結(jié)點所構(gòu)成的二叉樹有5種形態(tài)。2.[計算機研2000]一棵深度為6的滿二叉樹有n1+n2=0+n2=n0-1=31個分支結(jié)點和26-1=32個葉子。注：滿二叉樹沒有度為1的結(jié)點,所以分支結(jié)點數(shù)就是二度結(jié)點數(shù)。3．一棵具有２５７個結(jié)點的完全二叉樹,它的深度為9?！沧ⅲ河胠og2<n>+1=8.xx+1=9[全國專升本統(tǒng)考題]設(shè)一棵完全二叉樹有700個結(jié)點,則共有350個葉子結(jié)點。答：最快方法：用葉子數(shù)＝[n/2]＝3505.設(shè)一棵完全二叉樹具有1000個結(jié)點,則此完全二叉樹有500個葉子結(jié)點,有499個度為2的結(jié)點,有1個結(jié)點只有非空左子樹,有0個結(jié)點只有非空右子樹。答：最快方法：用葉子數(shù)＝[n/2]＝500,n2=n0-1=499。另外,最后一結(jié)點為2i屬于左葉子,右葉子是空的,所以有1個非空左子樹。完全二叉樹的特點決定不可能有左空右不空的情況,所以非空右子樹數(shù)＝0.6.[嚴題集6.7③]一棵含有n個結(jié)點的k叉樹,可能達到的最大深度為n,最小深度為2。答：當k=1<單叉樹>時應(yīng)該最深,深度＝n〔層；當k=n-1〔n-1叉樹時應(yīng)該最淺,深度＝2〔層,但不包括n=0或1時的特例情況。教材答案是"完全k叉樹",未定量。>7.[96程試題1]二叉樹的基本組成部分是：根〔N、左子樹〔L和右子樹〔R。因而二叉樹的遍歷次序有六種。最常用的是三種：前序法〔即按NLR次序,后序法〔即按LRN次序和中序法〔也稱對稱序法,即按LNR次序。這三種方法相互之間有關(guān)聯(lián)。若已知一棵二叉樹的前序序列是BEFCGDH,中序序列是FEBGCHD,則它的后序序列必是FEGHDCB。

解：法1：先由已知條件畫圖,再后序遍歷得到結(jié)果；法2：不畫圖也能快速得出后序序列,只要找到根的位置特征。由前序先確定root,由中序先確定左子樹。例如,前序遍歷BEFCGDH中,根結(jié)點在最前面,是B；則后序遍歷中B一定在最后面。法3：遞歸計算。如B在前序序列中第一,中序中在中間〔可知左右子樹上有哪些元素,則在后序中必為最后。如法對B的左右子樹同樣處理,則問題得解。8.[全國專升本統(tǒng)考題]中序遍歷的遞歸算法平均空間復雜度為O<n>。答：即遞歸最大嵌套層數(shù),即棧的占用單元數(shù)。精確值應(yīng)為樹的深度k+1,包括葉子的空域也遞歸了一次。9.[計算機研2001]用5個權(quán)值{3,2,4,5,1}構(gòu)造的哈夫曼〔Huffman樹的帶權(quán)路徑長度是33。解：先構(gòu)造哈夫曼樹,得到各葉子的路徑長度之后便可求出WPL＝〔4＋5＋3×2＋〔1＋2×3=33<15><9><6>〔注：兩個合并值先后不同會導致編碼不同,即哈夫曼編碼不唯一453<3>〔注：合并值應(yīng)排在葉子值之后12〔注：原題為選擇題：Ａ．32Ｂ．33Ｃ．34Ｄ．15三、單項選擇題〔每小題1分,共11分〔C1．不含任何結(jié)點的空樹。〔Ａ是一棵樹;〔Ｂ是一棵二叉樹;〔Ｃ是一棵樹也是一棵二叉樹;〔Ｄ既不是樹也不是二叉樹答：以前的標答是B,因為那時樹的定義是n≥1〔C2．二叉樹是非線性數(shù)據(jù)結(jié)構(gòu),所以?！玻了荒苡庙樞虼鎯Y(jié)構(gòu)存儲;〔Ｂ它不能用鏈式存儲結(jié)構(gòu)存儲;〔Ｃ順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都能存儲;〔Ｄ順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)都不能使用〔C3.〖01年計算機研題〗具有n<n>0>個結(jié)點的完全二叉樹的深度為。<Ａ>log2<n><Ｂ>log2<n><Ｃ>log2<n>+1<Ｄ>log2<n>+1注1：x表示不小于x的最小整數(shù)；x表示不大于x的最大整數(shù),它們與[]含義不同！注2：選〔A是錯誤的。例如當n為2的整數(shù)冪時就會少算一層。似乎log2<n>+1是對的？〔A4．把一棵樹轉(zhuǎn)換為二叉樹后,這棵二叉樹的形態(tài)是?！玻廖ㄒ坏摹玻掠卸喾N〔Ｃ有多種,但根結(jié)點都沒有左孩子〔Ｄ有多種,但根結(jié)點都沒有右孩子5.[94程P11]從供選擇的答案中,選出應(yīng)填入下面敘述？內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。樹是結(jié)點的有限集合,它A根結(jié)點,記為T。其余的結(jié)點分成為m〔m≥0個B的集合T1,T2,…,Tm,每個集合又都是樹,此時結(jié)點T稱為Ti的父結(jié)點,Ti稱為T的子結(jié)點〔1≤i≤m。一個結(jié)點的子結(jié)點個數(shù)為該結(jié)點的C。供選擇的答案A：①有0個或1個②有0個或多個③有且只有1個④有1個或1個以上B:①互不相交②允許相交③允許葉結(jié)點相交④允許樹枝結(jié)點相交C：①權(quán)②維數(shù)③次數(shù)〔或度④序答案：ABC＝1,1,36.[95程P13]從供選擇的答案中,選出應(yīng)填入下面敘述？內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。二叉樹A。在完全的二叉樹中,若一個結(jié)點沒有B,則它必定是葉結(jié)點。每棵樹都能惟一地轉(zhuǎn)換成與它對應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里,一個結(jié)點N的左子女是N在原樹里對應(yīng)結(jié)點的C,而N的右子女是它在原樹里對應(yīng)結(jié)點的D。供選擇的答案A：①是特殊的樹②不是樹的特殊形式③是兩棵樹的總稱④有是只有二個根結(jié)點的樹形結(jié)構(gòu)B:①左子結(jié)點②右子結(jié)點③左子結(jié)點或者沒有右子結(jié)點④兄弟C～D：①最左子結(jié)點②最右子結(jié)點③最鄰近的右兄弟④最鄰近的左兄弟⑤最左的兄弟⑥最右的兄弟答案：A=B=C=D＝答案：ABCDE＝2,1,1,3四、簡答題〔每小題4分,共20分[嚴題集6.2①]一棵度為2的樹與一棵二叉樹有何區(qū)別？答：度為2的樹從形式上看與二叉樹很相似,但它的子樹是無序的,而二叉樹是有序的。即,在一般樹中若某結(jié)點只有一個孩子,就無需區(qū)分其左右次序,而在二叉樹中即使是一個孩子也有左右之分。C的結(jié)點類型定義如下：structnode{chardata;structnode*lchild,rchild;C的結(jié)點類型定義如下：structnode{chardata;structnode*lchild,rchild;};C算法如下：voidtraversal<structnode*root>{if<root>{printf<"%c",root->data>;traversal<root->lchild>;printf<"%c",root->data>;traversal<root->rchild>;}}對下列二叉樹B,執(zhí)行下列算法traversal<root>,試指出其輸出結(jié)果；假定二叉樹B共有n個結(jié)點,試分析算法traversal<root>的時間復雜度?！补?分AABDCFGE二叉樹B解：這是"先根再左再根再右",比前序遍歷多打印各結(jié)點一次,輸出結(jié)果為：ABCCEEBADFFDGG特點：①每個結(jié)點肯定都會被打印兩次；②但出現(xiàn)的順序不同,其規(guī)律是：凡是有左子樹的結(jié)點,必間隔左子樹的全部結(jié)點后再重復出現(xiàn)；如A,B,D等結(jié)點。反之馬上就會重復出現(xiàn)。如C,E,F,G等結(jié)點。時間復雜度以訪問結(jié)點的次數(shù)為主,精確值為2*n,時間漸近度為O<n>.3.〖01年計算機研題〗[嚴題集6.27③]給定二叉樹的兩種遍歷序列,分別是：前序遍歷序列：D,A,C,E,B,H,F,G,I；中序遍歷序列：D,C,B,E,H,A,G,I,F,試畫出二叉樹B,并簡述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。解：方法是：由前序先確定root,由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對應(yīng)前序遍歷序列中的元素集合,可繼續(xù)確定root的左右孩子。將他們分別作為新的root,不斷遞歸,則所有元素都將被唯一確定,問題得解。DACFEGBHI2833406008545528334060085455解：要遵循中序遍歷的軌跡來畫出每個前驅(qū)和后繼。中序遍歷序列：554025602808335428282540555560330854NILNILNILNIL334060085455五、閱讀分析題〔每題5分,共20分1.〔P604-26試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點序列。答：DLR：ABDFJGKCEHILM LDR:BFJDGKACHELIM LRD：JFKGDBHLMIECA2.〔P604-27把如圖所示的樹轉(zhuǎn)化成二叉樹。答：注意全部兄弟之間都要連線〔包括度為2的兄弟,并注意原有連線結(jié)點一律歸入左子樹,新添連線結(jié)點一律歸入右子樹。ABECKFHDLGIMJ答：這是找結(jié)點后繼的程序。共有3處錯誤。注：當rtag＝1時說明內(nèi)裝后繼指針,可直接返回,第一句無錯。答：這是找結(jié)點后繼的程序。共有3處錯誤。注：當rtag＝1時說明內(nèi)裝后繼指針,可直接返回,第一句無錯。當rtag＝0時說明內(nèi)裝右孩子指針,但孩子未必是后繼,需要計算。中序遍歷應(yīng)當先左再根再右,所以應(yīng)當找左子樹直到葉子處。r=r->lchild;直到LTag=1；應(yīng)改為：while<!r->Ltag>r=r->Lchild;BiTreeInSucc<BiTreeq>{//已知q是指向中序線索二叉樹上某個結(jié)點的指針,//本函數(shù)返回指向*q的后繼的指針。r=q->rchild;//應(yīng)改為r=q；if<!r->rtag>while<!r->rtag>r=r->rchild;//應(yīng)改為while<!r->Ltag>r=r->Lchild;returnr;//應(yīng)改為returnr->rchild；}//ISucc4.[嚴題集6.21②]畫出和下列二叉樹相應(yīng)的森林。答：注意根右邊的子樹肯定是森林,而孩子結(jié)點的右子樹均為兄弟。六、算法設(shè)計題〔前5題中任選2題,第6題必做,每題8分,共24分1.[嚴題集6.42③]編寫遞歸算法,計算二叉樹中葉子結(jié)點的數(shù)目。解：思路：輸出葉子結(jié)點比較簡單,用任何一種遍歷遞歸算法,凡是左右指針均空者,則為葉子,將其打印出來。法一：核心部分為：DLR<liuyu*root>/*中序遍歷遞歸函數(shù)*/{if<root!=NULL>{if<<root->lchild==NULL>&&<root->rchild==NULL>>{sum++;printf<"%d\n",root->data>;}DLR<root->lchild>;DLR<root->rchild>;}return<0>;}法二：intLeafCount_BiTree<BitreeT>//求二叉樹中葉子結(jié)點的數(shù)目{if<!T>return0;//空樹沒有葉子elseif<!T->lchild&&!T->rchild>return1;//葉子結(jié)點elsereturnLeaf_Count<T->lchild>+Leaf_Count<T->rchild>;//左子樹的葉子數(shù)加上右子樹的葉子數(shù)}//LeafCount_BiTree注：上機時要先建樹！例如實驗二的方案一。打印葉子結(jié)點值〔并求總數(shù)思路：先建樹,再從遍歷過程中打印結(jié)點值并統(tǒng)計。步驟1鍵盤輸入序列12,8,17,11,16,2,13,9,21,4,構(gòu)成一棵二叉排序樹。葉子結(jié)點值應(yīng)該是4,9,13,21,總數(shù)應(yīng)該是4.121721116214913編程：生成二叉樹排序樹之后,再中序遍歷排序查找結(jié)點的完整程序如下：說明部分為：#include<stdio.h>#include<stdlib.h>typedefstructliuyu{intdata;structliuyu*lchild,*rchild;}test;liuyu*root;intsum=0;intm=sizeof<test>;voidinsert_data<intx>/*如何生成二叉排序樹？參見教材P43C程序*/{liuyu*p,*q,*s;s=<test*>malloc<m>;s->data=x;s->lchild=NULL;s->rchild=NULL;if<!root>{root=s;return;}p=root;while<p>/*如何接入二叉排序樹的適當位置*/{q=p;if<p->data==x>{printf<"dataalreadyexist!\n">;return;}elseif<x<p->data>p=p->lchild;elsep=p->rchild;}if<x<q->data>q->lchild=s;elseq->rchild=s;}DLR<liuyu*root>/*中序遍歷遞歸函數(shù)*/{if<root!=NULL>{if<<root->lchild==NULL>&&<root->rchild==NULL>>{sum++;printf<"%d\n",root->data>;}DLR<root->lchild>;DLR<root->rchild>;}return<0>;}main<>/*先生成二叉排序樹,再調(diào)用中序遍歷遞歸函數(shù)進行排序輸出*/{inti,x;i=1;root=NULL;/*千萬別忘了賦初值給root!*/do{printf<"pleaseinputdata%d:",i>;i++;scanf<"%d",&x>;/*從鍵盤采集數(shù)據(jù),以-9999表示輸入結(jié)束*/if<x==-9999>{DLR<root>;printf<"\nNowoutputcountvalue:%d\n",sum>;return<0>;}elseinsert_data<x>;}/*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while<x!=-9999>;return<0>;}執(zhí)行結(jié)果：若一開始運行就輸入-9999,則無葉子輸出,sum=0。2.[全國專升本統(tǒng)考題]寫出求二叉樹深度的算法,先定義二叉樹的抽象數(shù)據(jù)類型?！?0分或[嚴題集6.44④]編寫遞歸算法,求二叉樹中以元素值為x的結(jié)點為根的子樹的深度。答；設(shè)計思路：只查后繼鏈表指針,若左或右孩子的左或右指針非空,則層次數(shù)加1；否則函數(shù)返回。但注意,遞歸時應(yīng)當從葉子開始向上計數(shù),否則不易確定層數(shù)。intdepth<liuyu*root>/*統(tǒng)計層數(shù)*/{intd