...wd......wd......wd...數據構造原理與分析-01343-18日下-復習資料一、填空1.線性表是具有n個什么的有限序列〔數據元素〕。2.鄰接表的存儲構造以以下列圖的深度優先遍歷類似于二叉樹的(先序遍歷)。3.在一棵二叉樹的二叉鏈表中，空指針域數等于非空指針域數加〔2〕。4.某二叉樹的前序和后序序列正好相反，那么該二叉樹一定是什么二叉樹(高度等于其結點數)。5.對于棧操作數據的原那么是〔后進先出〕。6.結點前序為xyz的不同二叉樹，所具有的不同形態為(5)。7.設長度為n的鏈隊列用單循環鏈表表示，假設只設頭指針，那么入隊操作的時間復雜度為(O(n))。8.在一棵高度為h(假定樹根結點的層號為0)的完全二叉樹中，所含結點個數不小于(2h)。9.具有n個頂點的有向無環圖最多可包含有向邊的條數是(n(n-1)/2)。10.因此在初始為空的隊列中插入元素a,b,c,d以后，緊接著作了兩次刪除操作，此時的隊尾元素是(d).11.假設二叉樹中度為2的結點有15個，度為1的結點有10個，那么葉結點的個數〔16〕。12.對于一棵滿二叉樹，m個樹葉，n個結點，深度為h,那么(n=2h＋1-1)。13.在一棵具有n個結點的二叉樹中，所有結點的空子樹個數等于〔n+1〕14.用鄰接表表示圖進展深度優先遍歷時，通常用來實現算法的輔助構造是(棧)。15.堆的形狀是一棵(完全二叉樹)。16.假設在一棵非空樹中，某結點A有3個兄弟結點〔包括A自身〕，B是A的雙親結點，那么B的度為(4)。17.任何一個無向連通圖的最小生成樹(有一棵或多棵)18.在非空二叉樹的中序遍歷序列中，二叉樹的根結點的左邊應該(只有左子樹上的所有結點)。19.排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進展比較，將其放入已排序序列的正確位置上的方法，稱為(插入排序)。20.對于一棵滿二叉樹，m個樹葉，n個結點，深度為h,那么(n=2h＋1-1)。21.具有n個頂點的有向圖最多可包含的有向邊的條數是(n(n-1))。22.某二叉樹的前序和后序序列正好一樣，那么該二叉樹一定是什么樣的二叉樹(空或只有一個結點)。23.棧和隊列的主要區別在于(插入刪除運算的限定不一樣)。24.串是〔任意有限個字符構成的序列〕。25.對有14個數據元素的有序表R[14]進展折半搜索，搜索到R[3]的關鍵碼等于給定值，此時元素比較順序依次為〔R[6]，R[2]，R[4]，R[3]〕。26.深度為h且有多少個結點的二叉樹稱為滿二叉樹(2h+1-1)。27.在含n個頂點e條邊的無向圖的鄰接矩陣中，零元素的個數為〔n2-2e〕。28.在一個有向圖中，所有頂點的入度之和與所有頂點出度之和的倍數為(1)。29.鄰接表的存儲構造以以下列圖的廣度優先遍歷類似于二叉樹的(按層遍歷)。30.設高度為h的二叉樹上只有度為0和度為2的結點，那么此類二叉樹中所包含的結點數至少為(2h-1)。31.假設一棵二叉樹具有10個度為2的結點，5個度為1的結點，那么度為0的結點個數是〔11〕32.在一棵具有n個結點的二叉樹中，所有結點的空子樹個數等于〔n+1〕33.假設一棵二叉樹有11個度為2的結點，那么該二叉樹的葉結點的個數是〔12〕。34.對有n個記錄的表按記錄鍵值有序建設二叉查找樹，在這種情況下，其平均查找長度的量級為〔O(n)〕。35.設森林F中有三棵樹，第一、第二和第三棵的結點個數分別為m1,m2和m3,那么森林F對應的二叉樹根結點上的右子樹上結點個數是(m2+m3)。36.對有18個元素的有序表作二分〔折半〕查找，那么查找A[3]的比較序列的下標為〔9、4、2、3〕。37.假設要在O〔1〕的時間復雜度上實現兩個循環鏈表頭尾相接，那么應對兩個循環鏈表各設置一個指針，分別指向(各自的尾結點)。38.深度為h的滿二叉樹所具有的結點個數是〔2h+1-1〕。39.設高度為h的二叉樹上只有度為0和度為2的結點，那么此類二叉樹中所包含的結點數至少為〔2h-1〕。40.如果T2是由有序樹T轉換而來的二叉樹，那么T中結點的先根序列就是T2中結點的〔先根序列〕。41.有n個葉子的哈夫曼樹的結點總數為〔2n-1〕。42.設長度為n的鏈隊列用單循環鏈表表示，假設只設頭指針，那么入隊操作的時間復雜度為(O(n))。43.假設二叉樹中度為2的結點有15個，度為1的結點有10個，那么葉子結點的個數為〔16〕。44.假設某完全二叉樹的深度為h，那么該完全二叉樹中具有的結點數至少是(2h－1)。45.叉樹的前序和后序序列正好相反，那么該二叉樹一定是什么二叉樹(度等于其結點數)。46.初始序列已經按鍵值有序時，用直接插入算法進展排序，需要比較的次數為(n-1)。47.接表表示圖進展廣度優先遍歷時，為實現算法通常采用的輔助構造是(隊列)。48.用冒泡排序法對序列{18,16,14,12,10,8}從小到大進展排序，需要進展的比較次數是(15)。49.有n個頂點的圖采用鄰接矩陣表示，那么該矩陣的大小為〔n*n〕。50.6個頂點的無向圖成為一個連通圖至少應有邊的條數是〔5〕。51.單鏈表中，增加頭結點的目的是為了〔方便運算的實現〕。52.在線索二叉樹中,結點(*t)沒有左子樹的充要條件是(t->ltag==1)。53.按照二叉樹的定義,具有3個結點的二叉樹有多少種(5)。54.對待排序的元素序列進展劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是〔快速排序〕55.二分查找法要求查找表中各元素的鍵值必須是(遞增或遞減)。56.線性表的長度是指〔表中的元素個數〕57.將長度為m的單鏈表連接在長度為n的單鏈表之后的算法的時間復雜度為(O(n))。58.有一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當二分查找值為82的結點時，查找成功的比較次數是〔4〕。.59.假設在一棵非空樹中，某結點A有3個兄弟結點〔包括A自身〕，B是A的雙親結點，那么B的度為〔4〕。60.深度為h的滿二叉樹具有的結點個數為〔2h+1-1〕。61.用二叉鏈表存儲樹，那么根結點的右指針是〔空〕。62.個無向圖中，所有頂點的度數之和等于所有邊數〔1〕倍。63.單鏈表表示的鏈式隊列的隊頭在鏈表的什么位置〔鏈頭〕。64.線性表的長度是指〔表中的元素個數〕65.某二叉樹的前序和后序序列正好一樣，那么該二叉樹一定是什么樣的二叉樹(空或只有一個結點)。66.在一棵具有n個結點的二叉樹中，所有結點的空子樹個數等于〔n+1〕。67.一個具有n個頂點e條邊的無向圖中，采用鄰接表表示，那么所有頂點的鄰接表的結點總數為〔2e〕。68.鏈棧和順序棧相比，有一個較明顯的優點是(通常不會出現棧滿的情況)。69.對于鍵值序列{72,73,71,23,94,16,5,68,76,103}用篩選法建堆，開場結點的鍵值必須為(94)。70.在圖形構造中，每個結點的前驅結點數和后續結點數可以有(任意多個)。71.對有n個記錄的有序表采用二分查找，其平均查找長度的量級為(O(log2n))。72.在一棵高度為h(假定樹根結點的層號為0)的完全二叉樹中，所含結點個數不小于(2h)。73.假設一棵二叉樹有10個葉結點，那么該二叉樹中度為2的結點個數為9。74.設有一個順序棧S，元素S1，S2，S3，S4，S5，S6依次進棧，如果6個元素的出棧順序為S2，S3，S4，S6，S5，S1，那么順序棧的容量至少應為3。75.對于一棵二叉樹，設葉子結點數為n0,次數為2的結點數為n2,那么n0和n2的關系是n0=n2＋1。76.假設一棵二叉樹有12個葉結點，那么該二叉樹中度為2的結點個數為11。77.二叉樹的存儲構造有順序存儲構造和鏈式存儲構造。78.深度為h且有2k-1個結點的二叉樹稱為滿二叉樹。(設根結點處在第1層)。79.圖的深度優先搜索方法類似于二叉樹的先序遍歷。80.哈夫曼樹是帶權路徑長度最小的二叉樹。81.在線索二叉樹中，線索是指向結點在某遍歷次序下的前驅或后繼結點的指針。82.棧可以作為實現遞歸函數調用的一種數據構造。83.一般樹的存儲構造有雙親表示法、孩子兄弟表示法和孩子鏈表表示法。84.將數據元素2,4,6,8,10,12,14,16,18,20依次存于一個一維數組中，然后采用折半查找元素12，被比較過的數組元素的下標依次為5，7，6。。85.圖的深度優先遍歷序列不是唯一的。86.假設二叉樹的一個葉子結點是某子樹的中根遍歷序列中的第一個結點，那么它必是該子樹的后跟遍歷中的第一個結點。87.圖的遍歷是指從圖中某一頂點出發訪問圖中全部頂點且使每一頂點僅被_訪問一次。88.在一個圖中，所有頂點的度數之和等于所有邊的數目的2倍。89.由一棵二叉樹的后序序列和中序序列可唯一確定這棵二叉樹。90.在有序表(12,24,36,48,60,72,84)中二分查找關鍵字72時所需進展的關鍵字比較次數為2。91.設根結點的層數為0，定義樹的高度為樹中層數最大的結點的層數加1，那么高度為k的二叉樹具有的結點數目，最少為k，最多為2k-1。92.在直接插入排序、直接選擇排序、分劃交換排序、堆排序中穩定的排序方法有直接插入排序。93.具有100個結點的完全二叉樹的葉子結點數為50。94.普里姆(Prim)算法適用于邊稠密圖。95.在有n個葉子結點的哈夫曼樹中,其結點總數為2n-1。96.將一棵樹轉換成一棵二叉樹后，二叉樹根結點沒有右子樹。97.矩陣采用壓縮存儲是為了節省空間98.假設連通網絡上各邊的權值均不一樣，那么該圖的最小生成樹有1棵。99.設無向圖G的頂點數為n，那么要使G連通最少有n-1條邊。100.棧和隊列的共同特點是插入和刪除均在端點處進展。101.克魯斯卡爾(Kruskar)算法適用于邊稀疏圖。102.假設連通圖的頂點個數為n，那么該圖的生成樹的邊數為n-1。103.圖的存儲構造最常用的有鄰接矩陣和鄰接表。104.由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。105.隊列中允許進展插入的一端稱為隊尾。106.拓撲排序輸出的頂點數小于有向圖的頂點數，那么該圖一定存在環。107.在有序表(15,23,24,45,48,62,85)中二分查找關鍵詞23時所需進展的關鍵詞比較次數為2。108.樹中所有結點的度等于所有結點數加〔-1〕。109.在一個具有n個頂點的完全無向圖的邊數為(n(n-1)/2)。110.用分劃交換排序方法對包含有n個關鍵的序列進展排序，最壞情況下執行的時間雜度為(O(n2))111.一棵高度為h(假定樹根結點的層號為0)的完全二叉樹中，所含結點個數不小于(2h)。112.假設長度為n的非空線性表采用順序存儲構造，刪除表的第i個數據元素，首先需要移動表中數據元素的個數是〔n-i〕。113.在非空二叉樹的中序遍歷序列中，二叉樹的根結點的左邊應該(只有左子樹上的所有結點)。114.假設一棵二叉樹具有45個度為2的結點，6個度為1的結點，那么度為0的結點個數是〔46〕。115.在一個有向圖中，所有頂點的入度之和等于所有邊數〔4〕倍。116.設輸入序列為A,B,C,D,借助一個棧不可以得到的輸出序列是(D,A,B,C)。117.一維數組A采用順序存儲構造，每個元素占用6個字節，第6個元素的起始地址為100，那么該數組的首地址是〔70〕。118.設abcdef以所給的次序進棧，假設在進棧操作時，允許退棧操作,那么下面得不到的序列為〔cbdef〕。119.一般情況下，將遞歸算法轉換成等價的非遞歸算法應該設置〔堆棧〕。120.假設長度為n的非空線性表采用順序存儲構造，刪除表的第i個數據元素，i的合法值應該121.是〔C.1≤i≤n〕。122.假設某線性表中最常用的操作是取第i個元素和刪除最后一個元素，那么采用什么存儲方123.式最節省時間〔順序表〕。124.一組記錄的關鍵字為{45,80,55,40,42,85}，那么利用堆排序的方法建設的初始堆為〔85,80,55,40,42,45〕。125.設有6000個無序的元素,希望用最快的速度挑選出其中前5個最大的元素,最好選用(堆排序)法。126.排序方法中，從未排序序列中挑選元素，將其放入已排序序列的一端的方法，稱為(選擇排序)。127.帶頭結點的單鏈表head為空的判斷條件是(head->next==NULL)。128.在一個單鏈表中，假設刪除(*p)結點的后繼結點，那么執行(p->next=p->next->next)。129.在一棵具有n個結點的二叉樹中，所有結點的空子樹個數等于〔n+1〕130.有向圖中，以頂點v為終點的邊的數目，稱為頂點v的〔入度〕。131.假設頻繁地對線性表進展插入和刪除操作，該線性表應該采用的存儲構造是〔鏈式〕。132.設一個棧的輸入序列是1，2，3，4，5,那么以下序列中，是棧的合法輸出序列的是〔32154〕。133.有數據{53，30，37，12，45，24，96}，從空二叉樹開場逐個插入數據來形成二叉查找樹，假設希望高度最小，那么應選擇下面輸入序列是〔37,24,12,30,53,45,96〕。134.二叉樹的第I層上最多含有結點數為〔2I〕。135.稀疏矩陣一般采用的壓縮存儲方法為(三元組表)。136.某二叉樹的前序和后序序列正好一樣，那么該二叉樹一定是什么樣的二叉樹(空或只有一個結點)。137.假設長度為n的線性表采用順序存儲構造，在表的第i個位置插入一個數據元素，需要移動表中元素的個數是〔n-i+1〕。138.設有數組A[i,j]，數組的每個元素長度為3字節，i的值為1到8，j的值為1到10，數組從內存首地址BA開場順序存放，當用以列為主存放時，元素A[5，8]的存儲首地址為(BA+180)。139.二維數組A[5][6]的每個元素占5個單元，將其按行優先順序存儲在起始地址為3000的連續的內存單元中，那么元素A[4][5]的存儲地址為〔3145〕。140.一個具有n個頂點的圖采用鄰接矩陣表示，那么該矩陣的大小為〔n*n〕。141.假設字符串“1234567〞采用鏈式存儲，假設每個字符占用1個字節，每個指針占用2個字節，那么該字符串的存儲密度為〔33.3﹪〕。142.假設在一棵非空樹中，某結點A有3個兄弟結點〔包括A自身〕，B是A的雙親結點，那么B的度為〔3〕。143.設有三個元素X，Y，Z順序進棧〔進的過程中允許出棧〕，以下得不到的出棧排列是(ZXY)。144.樹形構造的特點是：一個結點可以有(多個直接后繼)。145.使具有30個頂點的無向圖成為一個連通圖至少應有邊的條數是〔29〕。146.使具有9個頂點的無向圖成為一個連通圖至少應有邊的條數是〔8〕。147.在順序表〔n足夠大〕中進展順序查找，其查找不成功的平均長度是〔n+1〕。148.設樹T的度為4，其中度為1，2，3和4的結點個數分別為4，2，1，1那么T中的葉子數為〔8〕。149.棧的插入和刪除操作進展的位置在〔棧頂〕。150.假設一棵二叉樹具有20個度為2的結點，6個度為1的結點，那么度為0的結點個數是〔21〕。151.一棵線索二叉樹的線索個數比鏈接個數多〔2〕個。152.在循環鏈表中，從任何一結點出發都能訪問到表中的所有結點。153.在n個結點的順序表中插入一個結點需平均移動n/2個結點。154.循環隊列的引入，目的是為了抑制假溢出。155.假設連通網絡上各邊的權值均不一樣，那么該圖的最小生成樹有1棵。156.二叉樹的遍歷方式有三種：先序遍歷、中序遍歷、后序遍歷。157.假設一棵二叉樹有15個葉結點，那么該二叉樹中度為2的結的點個數為14。158.設某二叉樹的后序遍歷序列為ABKCBPM，那么可知該二叉樹的根為M。159.數據構造的三個方面：數據的邏輯構造、物理構造、運算。160.每個結點只有一個鏈接域的鏈表叫做單鏈表。161.組成串的數據元素只能是字符。162.具有n個結點的二叉樹采用鏈接構造存儲，鏈表中存放NULL指針域的個數為〔n+1〕。163.在一個無向圖中，所有頂點的度數之和等于所有邊數〔2〕倍。164設二叉樹根結點的層次為0，一棵高度為h的滿二叉樹中的結點個數是(2h+1-1)。165.將一棵有50個結點的完全二叉樹按層編號，那么對編號為25的結點x，該結點(有左孩子，無右孩子)。166.樹〔或樹形〕的定義是什么答：一個樹〔或樹形〕就是一個有限非空的結點集合T，其中有一個特別標出的稱為該樹之根root〔T〕的結點；其余〔除根外〕的結點劃分成個不相交集合,而且這些集合的每一個又都是樹。167在圖形構造中，每個結點的前驅結點數和后續結點數可以有(任意多個)。168.什么是樹的路徑長度答：樹的路徑長度是指從根結點到樹中每個葉結點的路徑長度之和。二、選擇1.假設某線性表中最常用的操作是取第i個元素和刪除最后一個元素，那么采用什么存儲方式最節省時間〔A〕。A.順序表B.單鏈表C.雙鏈表D.單循環鏈表2.在下述的排序方法中，不屬于內排序方法的是〔C〕。A.插入排序法B.選擇排序法C.拓撲排序法D.歸并排序法3.以下四個關鍵詞序列中,不是堆的序列為(C)。A.{05,23,16,68,94,72,71,73}B.{05,16,23,68,94,72,71,73}C.{05,23,16,73,94,72,71,68}D.{05,23,16,68,73,71,72,94}4.以下排序算法中,某一趟完畢后未必能選出一個元素放其最終位置上的是(D)。A.堆排序B.冒泡排序C.快速排序D.直接插入排序5.用孩子兄弟鏈表表示一棵樹，假設要找到結點x的第5個孩子，只要先找到x的第一個孩子，然后(D)。A.從孩子域指針連續掃描5個結點即可B.從孩子域指針連續掃描4個結點即可C.從兄弟域指針連續掃描5個結點即可D.從兄弟域指針連續掃描4個結點即可6.鏈棧和順序棧相比，有一個較明顯的優點是(A)。A.通常不會出現棧滿的情況B.通常不會出現棧空的情況C插入操作更加方便D.刪除操作更加方便7.任何一棵二叉樹的葉結點在其先根、中根、后根遍歷序列中的相對位置(C)。A.肯定發生變化B.有時發生變化C.肯定不發生變化D.無法確定8.排序方法中，從未排序序列中挑選元素，將其放入已排序序列的一端的方法，稱為(D)。A.希爾排序B.冒泡排序C.插入排序D.選擇排序9.堆是一種什么排序〔B〕。A.插入B.選擇C.交換D.歸并10.以下排序方法中不穩定的排序是(C)。A.直接插入排序B.冒泡排序C.堆排序D.歸并排序11.一個無向連通圖的生成樹是含有該連通圖的全部頂點的(A)。A.極小連通子圖B.極大連通子圖C.極小子圖D.極大子圖12.如下陳述中正確的選項是(A)。A.串是一種特殊的線性表B.串的長度必須大于零B.串中元素只能是字母D.空串就是空白串13.快速排序不利于發揮其長處的情況是〔C〕。[A]待排序數據量太大[B]待排序數據一樣值過多[C]待排序數據已基本有序[D]待排序數據值差過大14.性表中采用折半查找法查找元素，該線性表必須滿足〔C〕。[A]元素按值有序[B]采用順序存儲構造[C]元素按值有序，且采用順序存儲構造[D]元素按值有序，且采用鏈式存儲構造15.r在排序前已按元素鍵值遞增順序排列，那么比較次數較少的排序方法是(A)。A.直接插入排序B.快速排序C.歸并排序D.選擇排序16.一個遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運行時間來看，通常遞歸過程比非遞歸過程〔B〕A．較快B．較慢C．一樣D.不確定17.如果待排序序列中兩個數據元素具有一樣的值，在排序后它們的位置發生顛倒，那么稱該排序是不穩定的。不穩定的排序方法是〔D〕。A．起泡排序B．歸并排序C．直接插入法排序D．簡單項選擇擇排序18.將一棵有50個結點的完全二叉樹按層編號，那么對編號為25的結點x，該結點(B)。A.無左、右孩子B.有左孩子，無右孩子C.有右孩子，無左孩子D.有左、右孩子19.假設某鏈表最常用的操作是在最后一個結點之后插入一個結點和刪除最后一個結點，那么采用那種存儲方式最節省時間(C)。A.單鏈表B.雙鏈表C.帶頭結點的雙循環鏈表D.單循環鏈表20.以下排序算法中,第一趟排序完畢后,其最大或最小元素一定在其最終位置上的算法是(D)。A.歸并排序B.直接插入排序C.快速排序D.冒泡排序21.樹形構造最適合用來描述〔C〕。[A]有序的數據元素[B]無序的數據元素[C]數據元素之間具有層次關系的數據[D]數據元素之間沒有關系的數據22.設有7000個無序的元素,希望用最快的速度挑選出其中前5個最大的元素,最好選用方法是(C)。A.冒泡排序B.快速排序C.堆排序D.基數排序23.鏈表不具有的特點是(A)。A.可隨機訪問任一元素B.插入刪除不需要移動元素C.不必事先估計存儲空間D.所需空間與線性表長度成正比24.假設待排序對象序列在排序前已按其排序碼遞增順序排序，那么比較次數最少的方法排序是〔A〕。A．直接插入排序B．快速排序C．歸并排序D．直接選擇排序25.以下關鍵字序列中是堆的序列為(D)。A.16,72,31,23,94,53B.94,23,31,72,16,53B.16,53,23,94,31,72D.16,23,53,31,94,7226.以下四個關鍵字序列中,那個序列不是堆(C)。A.{05,23,16,68,94,72,71,73}B.{05,16,23,68,94,72,71,73}C.{05,23,16,73,94,72,71,68}D.{05,23,16,68,73,71,72,94}27.下面4個序列中，滿足堆的定義是〔D〕。A.13,27,49,76,76,38,85,97B.76,38,27,49,76,85,13,97C.13,76,49,76,27,38,85,97D.13,27,38,76,49,85,76,9728.采用線性探查法處理沖突所構成的散列表上進展查找，可能要探測到多個位置，在查找成功情況下，所探測的這些位置上的鍵值〔D〕。A.一定都是同義詞B.一定都不是同義詞C.都一樣D.不一定都是同義詞29.性表中采用折半查找法查找元素，該線性表必須滿足〔C〕。[A]元素按值有序[B]采用順序存儲構造[C]元素按值有序，且采用順序存儲構造[D]元素按值有序，且采用鏈式存儲構造三、簡答1.對于一個隊列，如果輸入項序列由1,2,3,4所組成，試給出全部可能的輸出序列。答：1,2,3,4。2.將表達式(a+b)*c+d-(e+g)*h改寫成后綴表達式。答：后綴表達式為：ab+c*d+eg+h*-3.對于一個棧，給出輸入序列A，B，C，試給出全部可能的輸出序列。答：解：輸出序列為：ABC，CBA,ACB,BAC,BCA。4．將算術表達式a+b*〔c+d/e〕轉為后綴表達式。答：B．abcde/+*+5.由權值為12，6，5，9,10的五個葉子結點構造一棵哈夫曼樹，請問該樹的帶權路徑長度是多少答：權值為95。6.由二叉樹的前序和后序遍歷序列能否唯一確定一棵二叉樹。假設不能請舉出反例。答：不能唯一確定一棵二叉樹。如以以下列圖。11231237.求出以以下列圖所示有向圖的鄰接矩陣。VV0V4V3V2V1213457答：有向圖的鄰接矩陣為：027027∞1∞0∞∞∞∞∞05∞∞∞∞0∞3∞∞4001234012348.有個頂點的無向連通圖至少有多少條邊有個頂點的有向連通圖至少有多少條邊答：有個頂點的無向連通圖至少有n-1條邊，有個頂點的有向連通圖至少有n條邊。9．下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩定的答：起泡排序,直接插入排序，歸并排序是穩定的。10.為什么說樹是一種非線性構造樹中的每個結點除了根結點外，其余每個結點有一個直接前驅，但有多個直接后繼，所以說樹是一種非線性構造。11．一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,F,E,D,I,H,J,G答：后序序列為：C,B,F,E,I,J,H,G,D,A12．試述順序存儲和鏈式存儲的區別及各自的優缺點。答：數組占用連續的內存空間，鏈表不要求結點的空間連續。1〕插入與刪除操作：由于數組在插入與刪除數據時需移動大量的數據元素，而鏈表只需要改變一些指針的鏈接，因此，鏈表比數組易于實現數據的插入和刪除操作。2〕內存空間的占用情況：因鏈表多了一個指針域，故較浪費空間，因此，在空間占用方面，數組優于鏈表。3〕數據的存取操作：訪問鏈表中的結點必須從表頭開場，是順序的存取方式，而數組元素的訪問是通過數組下標來實現的，是隨機存取方式，因此，在數據存取方面，數組優于鏈表。數據的合并與別離：鏈表優于數組，因為只需要改變指針的指向13.將表達式((a+b)-c*(d+e)-f)*(g+h)改寫成后綴表達式。答：后綴表達式為：ab+cde+*-f-gh+*14．將算術表達式a*(b+c)-d轉為后綴表達式。答：abc+*d-15.求出以以下列圖所示有向圖的鄰接表。VV0V4V3V2V1213457答：有向圖的鄰接表為：VV0V1∧V2V3∧V4122741∧35∧34∧03Head16．試找出中序序列和后序序列一樣的所有二叉樹。答：空樹或缺右子樹的單支樹。17.用鄰接矩陣存儲一個包含1000個頂點和1000條邊的圖，那么該圖的鄰接矩陣中有多少元素有多少非零元素答：該圖的鄰接矩陣中有1000*1000個元素。該圖的鄰接矩陣中有2000個非零元素。18.畫出以以下列圖中二叉樹的順序存儲構造示意圖。113715答：二叉樹的順序存儲構造示意圖為：113715A[0]A[2]A[6]A[14]19.寫出中綴表達式A-(B+C/D)*E的后綴形式。答：中綴表達式A-(B+C/D)*E的后綴形式是：ABCD/+E*-。20．為什么用二叉樹表示一般樹答：樹的最直觀表示是為樹中結點設置指向子結點的指針域，對k叉樹而言，每個結點除data域外，還有k個鏈接域。這樣，對一個有n個結點的k叉樹來說，共有n*k個指針域，其中n-1個不空，另外n(k-1)+1個指針域為空，因此，空鏈接域的比例約為〔k-1〕/k，于是導致大量的空間浪費。然而，如果采用二叉樹表示一棵n個結點的樹，那么樹中共有2n個鏈接域，其中未用到的有n+1個，占所有指針域的比例約為1/2，空間浪費少很多。另外，因為任何樹型構造都可以轉換成二叉樹，因此，通常用二叉樹表示樹型構造。21．請指出一組權值〔7，5，2，4〕對應的哈夫曼樹的帶權路徑長度。答：哈夫曼樹的帶權路徑長度是35。22．試找出前序序列和中序序列一樣的所有二叉樹。解答：空樹或缺左子樹的單支樹。23．完全二叉樹用什么數據構造實現最適宜，為什么答：完全二叉樹用一維數組實現最適宜。因為完全二叉樹保存在一維數組中時，數組內沒有空洞，不存在空間浪費問題；另外，順序存儲方式下，父子結點之間的關系可用公式描述，即父〔或子〕結點尋找子〔或父〕結點只需計算一個公式，訪問結點方便。但采用鏈表存儲時就存在空間浪費問題，因為每個結點要另外保存兩個鏈接域，并且尋找結點也不容易。24.求出以以下列圖所示無向圖的鄰接矩陣。VV0V1V2V30012301111001100111100123答：無向圖的鄰接矩陣為：5539132541805513571221183025.請構造權值為{5，13，21，7，18，30，41}的哈夫曼樹。答：哈夫曼樹為：26．我們已經知道，樹的先根序列與其對應的二叉樹的先根序列一樣，樹的后根序列與其對應的二叉樹的中根序列一樣。那么利用樹的先根遍歷次序與后根遍歷次序，能否唯一確定一棵樹請說明理由。答：能。因為樹的先根序列與其對應的二叉樹的先根序列一樣，樹的后根序列與其對應的二叉樹的中根序列一樣，而二叉樹的先根序列與二叉樹的中根序列能唯一確定一棵二叉樹，所以利用樹的先根遍歷次序與后根遍歷次序，能唯一確定一棵樹。27．請給出如以以下列圖所示的權圖的鄰接矩陣。VV0V4V3V2V1213457答：解：027∞1027∞1∞0∞∞∞∞∞05∞∞∞∞0∞3∞∞40012340123428．一棵二叉樹的中序和前序序列如下，求該二叉樹的后序序列。中序序列：c，b，d，e，a，g，i，h，j，f前序序列：a，b，c，d，e，f，g，h，i，j答：該二叉樹的后序序列為：c,e,d,b,i,j,h,g,f,a29．對半查找是否適合于以鏈接構造組織的表答：對半查找不適合于以鏈接構造組織的表。。30.請指出中序遍歷二叉查找樹的結點可以得到什么樣的結點序列。答：中序遍歷二叉查找樹的結點就可以得到從小到大排序的結點序列。31．把以以下列圖中的森林轉化為一棵二叉樹。112684735解答：森林轉化成的二叉樹如以以下列圖。11268473532.指出一般樹的存儲構造有哪幾種答：樹的存儲構造有雙親表示法、孩子鏈表表示法和孩子兄弟表示法33.試找出前序序列和后序序列一樣的所有二叉樹。答：空樹或只有根結點的二叉樹。34.線性表有兩種存儲構造：一是順序表，二是鏈表。試問：如果有n個線性表同時并存，并且在處理過程中各表的長度會動態變化，線性表的總數也會自動地改變。在此情況下，應選用哪種存儲構造為什么答：選鏈式存儲構造。它可動態申請內存空間，不受表長度〔即表中元素個數〕的影響，插入、刪除時間復雜度為O35.求出以以下列圖所示無向圖的鄰接表。VV0V1V2V3VV0V1V2V313∧203∧03∧02∧1Head答：無向圖的鄰接表為：36.一個圖如下所示，假設從頂點0出發求出其廣度優先搜索序列。003425167解答：廣度優先搜索序列：0123456737.一組記錄的關鍵字為(52,56,26,12,69,85,33,48,70)，給出快速排序的過程。解答：解：52,56,26,12,69,85,33,48,70第一趟排序33,48,26,12,52,85,69,56,70第二趟排序26,12,33,48,52,69,56,70,85第三趟排序12,26,33,48,52,56,70,69,85第四趟排序12,26,33,48,52,56,70,69,85第五趟排序12,26,33,48,52,56,70,69,8538．下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩定的起泡排序,直接插入排序，歸并排序是穩定的。39．一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,F,E,D,I,H,J,G答：后序序列為：C,B,F,E,I,J,H,G,D,A40．把以以下列圖中的二叉樹轉化成森林。112684735112684735答案：41.給定表〔43,36,56,6,64,32,8,41〕，按數據元素在表中的次序構造一棵二叉查找樹，并求其平均查找長度。解答：根據給定表〔43,36,56,6,64,32,8,41〕，構造的二叉查找樹如以以下列圖；其平均查找長度為：23/8。646483241656364342．將以以下列圖中的二叉樹，轉換成相應的森林。AABCHFDJEILKGNM答：森林轉化成的二叉樹如以以下列圖。JJCHEKFILNMABDG43.知二叉樹按中根遍歷所得到的結點序列為DCBGEAHFIJK，按后根遍歷所得到的結點序列為DCEGBFHKJIA，畫出該樹形構造，并按中根遍歷序列進展線索化。答：HHKFGCIBAJED44.對于以以下列圖所示的二叉樹，試分別寫出先根遍歷、中根遍歷該樹所得到的先根序列、中根序列。GGFEDCBALKJIH答：先根遍歷的結點序列：ABCEIFJDGHKL，中遍歷的結點序列：EICFJBGDKHLA46．把以以下列圖中的二叉樹轉化成森林。126126847351268473547.一組記錄的關鍵字為(52,56,26,12,69,85,33,48,70)，給出快速排序的過程。解答：解：52,56,26,12,69,85,33,48,70第一趟排序33,48,26,12,52,85,69,56,70第二趟排序26,12,33,48,52,69,56,70,85第三趟排序12,26,33,48,52,56,70,69,85第四趟排序12,26,33,48,52,56,70,69,85第五趟排序12,26,33,48,52,56,70,69,8548.設記錄的關鍵字集合key={51,28,38,86,70,90,7,30,40,25}，試寫出對key進展漸減增量排序〔增量d=5，3，1〕時，各趟排序完畢后的結果。解答：各趟排序完畢后的結果。初始狀態：5128388670907304025第一趟排序(d=5):5173040259028388670第二趟排序(d=3):2873040258651389070第三趟排序(d=1):7252830384051708690〕49.有一棵二叉樹如以以下列圖所示，分別指出其前序、中序遍歷的結點序列。AABHGFEDCIJ答：它的前序序列為：ABCDEFGHIJ,它的中序序列為：CDBAFGEIHJ。50.8個記錄，對應的關鍵詞為：{25,84,21,47,15,27,68,35,20}寫出快速排序的第一趟排序過程圖示。答：初始鍵值序列[258421471527683520]第一次交換[258421471527683520]↑i=2↑j=9第二次交換[252021471527683584]i↑↑j掃描穿插[252021154727683584]j↑↑iRm與Rj互換[252021154727683584]Rm↑j↑分劃表[152021]25[4727683584]51.給定表〔40,9,56,6,39,73,8,23〕，按數據元素在表中的次序構造一棵二叉查找樹。答：.二叉排序樹如下。40409563986237352.有二叉樹先序序列為：ABCDEF,中序序列為：CBAEDF,試畫出該二叉樹。答：二叉樹如以以下列圖。AACDFEB53.給定表〔40,36,56,6,64,73,8,23〕，按數據元素在表中的次序構造一棵二叉查找樹，并求其平均查找長度。答：二叉查找樹如下，平均查找長度為3。404036566486237353．根據以以下列圖給出的二叉樹，求出先序、中序遍歷的結點序列。aacedfb答：先序遍歷為：abdcef中序遍歷為：dbaefc54.一組記錄的關鍵字為〔50，79，8，56，32，41，85〕，給出利用重建堆方法建設的初始堆〔堆頂最大〕，并給出堆排序的過程。答：1〕建設的初始堆為:85，79，50，56，32，41，82〕堆排序的過程如下：858579328504156〔C〕第2次交換85418541328505679〔B〕第1次交換8413256507985〔A〕初始建堆858579565041832〔f〕第5次交換85798579565032841〔e〕第4次交換8579568324150〔D〕第3次交換858579565041328〔g〕第6次交換55.答：把以下森林轉化為一棵二叉樹。112684735答：森林轉化成的二叉樹如以以下列圖。11268473556.數據序列為12,5,9,20,6,31,24，對該數據序列進展排序，試寫出冒泡排序每趟的結果。答：初始鍵值序列12592063124第一趟排序[591262024]31第二趟排序[5961220]2431第三趟排序[59612]202431第四趟排序5691220243157.給定表〔40,36,55,6,64,77,9,41〕，按數據元素在表中的次序構造一棵二叉查找樹，并求其平均查找長度。答：構造的二叉查找樹如以以下列圖，其平均查找長度為11/4。404035556496417758.對于以以下列圖所示的二叉樹，試分別寫出先根遍歷、中根遍歷和后根遍歷該樹所得到的先根序列、中根序列和后根序列。GGFEDCBALKJIH解答：先根遍歷的結點序列：ABCEIFJDGHKL中遍歷的結點序列：EICFJBGDKHLA后根遍歷的結點序列：IEJFCGKLHDBA59.數據序列為12,5,9,20,6,31,24，對該數據序列進展排序，試寫出歸并排序每趟的結果。解答：初始鍵值序列12592063124第一趟排序[512][920][631][24]第二趟排序[591220][62431]第三趟排序56912202431〔〕60.序表(5,12,17,19,23,25,30,36,45,49,58)中，用二分法查找關鍵詞36，進展多少次比較后查找成功寫出查找過程。解答：經過4次比較查找成功。查找過程如下：5,12,17,19,23,25,30,36,45,49,58j=115,12,17,19,23,25,30,36,45,49,58j=11m=6i=1〔A〕第1次與25進展比較j=115,12,17,19,23,25,30,36,45,49,585,12,17,19,23,25,30,36,45,49,58i=7m=9〔B〕第2次與45進展比較5,12,17,19,23,25,30,36,45,49,58j=8i=7m=7〔C〕第3次與30進展比較i=8i=85,12,17,19,23,25,30,36,45,49,58j=8m=8〔D〕第4次與36進展比較61.一組記錄的關鍵字為(52,56,26,12,69,85,33,48,70)，給出快速排序的過程。解答：52,56,26,12,69,85,33,48,70第一趟排序33,48,26,12,52,85,69,56,70第二趟排序26,12,33,48,52,69,56,70,85第三趟排序12,26,33,48,52,56,70,69,85第四趟排序12,26,33,48,52,56,70,69,85第五趟排序12,26,33,48,52,56,70,69,8562.某二叉樹的后序序列為：ABCDEFG,中序序列為：ACBGEDF,給出它的前序序列。解：它的前序序列為：GCABFED。63．根據以以下列圖給出的二叉樹，求出中序和后序遍歷的結點序列。aacedfb解答：中序遍歷為：dbaefc后序遍歷為：dbfeca00342516764.一個圖如下所示，假設從頂點0出發求出其深度優先搜索序列。解答：深度優先搜索序列：0137425665．給定表〔45,36,56,6,64,32,8,41〕，按數據元素在表中的次序構造一棵二叉查找樹。解答：按數據元素在表中的次序構造一棵二叉查找樹為：646483241656364566.找出所有這樣的二叉樹形，其結點在先根次序遍歷和中根次序遍歷下的排列是一樣的。答：為空樹，或為任一結點至多只有右子樹的二叉樹。下面程序段的時間復雜度是O〔mn〕。for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)a[i][j]=0;67.設有序順序表為{10,20,30,40,50,60,70,80}，采用折半查找時，查找成功和查找失敗的平均查找長度分別是多少答：包含這8個元素的二叉判定樹為：303010204070608050很明顯，查找成功的平均比較次數是；查找失敗的平均比較次數是。68.給定表〔43,36,56,6,64,32,8,41〕，按數據元素在表中的次序構造一棵二叉查找樹，并求其平均查找長度。解答：根據給定表〔43,36,56,6,64,32,8,41〕，構造的二叉查找樹如以以下列圖；其平均查找長度為：23/8。646483241656364369.什么是增長樹答：當二叉樹中結點沒有左子樹形或沒有右子樹形時，增加特殊的結點，由此生成的二叉樹稱為增長的二叉樹，簡稱增長樹。70.什么是線性表答：一個線性表是由零個或多個具有一樣類型的結點組成的有序集合。71.什么是一維數組答：一維數組是假設干個元素的一個有限序列，每個元素都通過一個下標來指定，所有的數組元素都具有一樣的數據類型，占據一樣大小的存儲空間.72.什么是森林答：一個森林就是一組〔0個或多個〕不相交的樹形〔通常諸樹形間還有次序〕。73.什么是強連通圖答：假設G為有向圖，且對于V(G)中任意兩個不同的頂點和，與連通，與也連通，那么稱G為強連通圖。74.什么是圖中兩點的簡單路徑答：如果一條路徑上除了起點和終點可以一樣外，再無一樣的頂點，那么稱此路徑為簡單路徑。75.設單鏈表中存放著n個字符，設計算法判斷字符串是否中心對稱，如xyzzyx即為中心對稱的字符串。答：將全部字符進棧，然后將棧中的字符逐個與鏈表中的字符比較隊列的定義是什么答：隊列是一種操作受限的線性表，它只允許在表的一端進展插入，在表的另一端進展刪除。76.字符串的定義是什么答：字符串是由零個或多個字符〔字母、數字及其它一些符號〕組成的有限連續序列，簡稱為串。77.二叉樹的定義是什么答：二叉樹是結點的有限集合，它必須滿足下面的一個條件：它是空集。它由一個根結點和根結點的左右子樹構成，且其左右子樹滿足二叉樹定義。78.有向圖的定義是什么答：圖G由兩個集合V和E組成，記為G=(V,E).其中V是頂點的有限集合，E是連接V中兩個不同頂點〔頂點對〕的邊的有限集合。如果E中的頂點對是有序的，即E中的每條邊都是有方向的，那么稱G為有向圖。79.AOV網的定義是什么答：用頂點表示活動，有向邊表示活動之間先后關系的有向圖簡稱為AOV網。80.設計一個算法，求出無向無權連通圖中距離頂點v的最短路徑長度為k的所有頂點，路徑長度以變數為單位計算。答：算法中須用從頂點v出發廣度優先遍歷的層次特性來求解，因此，訪問頂點時要知道一個頂點相對于v的層數，而每個頂點的層數是由其前驅頂點決定的。可以從頂點v開場，每訪問到一個頂點就根據其前驅的層數計算該頂點的層數，并將層數值與頂點編號一起入隊和出隊。算法中可以使用兩個隊列，一個記錄入隊的頂點編號，另一個記錄該頂點的層數，并保持二者的同步。81.兩個整數序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已經存入兩個單鏈表中，設計一個算法，判斷序列B是否是序列A的子序列。1)給出算法的基本設計思想(4分)；2)用算法描述語言描述算法，并要求對算法中的關鍵步驟給出注釋。答：1〕此題實質上是一個模式匹配問題，這里匹配的元素是整數而不是字符。因兩整數序列已存入兩個鏈表中，操作從兩鏈表的第一個結點開場，假設對應數據相等，那么后移指針；假設對應數據不等，那么A鏈表從上次開場比較結點的后繼開場，B鏈表仍從第一結點開場比較，直到B鏈表到尾表示匹配成功。A鏈表到尾B鏈表未到尾表示失敗。操作中應記住A鏈表每次的開場結點，以便下趟匹配時好從其后繼開場。2〕intPattern〔LinkedListA，B〕∥A和B分別是數據域為整數的單鏈表，本算法判斷B是否是A的子序列。如是，返回1；否那么，返回0表示失敗。{p=A；∥p為A鏈表的工作指針，此題假定A和B均無頭結點。pre=p；∥pre記住每趟比較中A鏈表的開場結點。q=B；∥q是B鏈表的工作指針。while〔p&&q〕if〔p->data==q->data〕{p=p->next；q=q->next；}else{pre=pre->next；p=pre；∥A鏈表新的開場比較結點。q=B；}∥q從B鏈表第一結點開場。if〔q==null〕return〔1〕；∥B是A的子序列。elsereturn〔0〕；∥B不是A的子序列。}∥算法完畢。82.設一棵二叉樹的先序、中序遍歷序列分別為：先序遍歷序列：ABDFCEGH中序遍歷序列：BFDAGEHC請畫出這棵二叉樹。83.什么是權圖答：設G=(V，E)是圖，假設將圖中的每條邊L都賦上一個實數w(L)作為邊的權值，那么稱G為權圖。84.畫出后綴表達式ab+cde+*-f-gh+*對應的二叉表達式樹。答：85.用序列(46,88,45,39,70,58,101,10,66,34)建設一棵二叉查找樹，畫出該樹。答：4545883970101103458664686什么是隊列的順序存儲答：隊列的順序存儲是指利用一組地址連續的存儲單元依次存放自隊頭到隊尾的數據元素。87.什么是數組答：數組通常被定義為具有一樣數據類型的元素的集合。88.什么是滿二叉樹答：一棵高度為的滿二叉樹，是具有個結點且高度為的二叉樹89.什么是連通圖答：設G是無向圖，假設從頂點到頂點有路徑，那么稱與連通。假設G為無向圖，且V(G)中任意兩頂點都連通，那么稱G為連通圖。90.什么是拓撲排序答：拓撲序列把AOV網中的所有頂點排成一個線性序列，該序列滿足如下條件：假設AOV網中存在邊，那么在該序列中，必位于之前。構造AOV網的拓撲序列的操作被稱為拓撲排序。91.什么是子串答：一個串的子串系指該串中的任意一個連續子序列92.基于關鍵詞比較的排序算法的下界是什么請指明直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、兩路合并排序算法中，哪些算法的時間復雜度到達了排序下界，并簡單分析其能夠到達下界的原因。答：O(nlogn).快速排序，堆排序，合并排序到達下界。主要原因分別是，快速排序的分劃方法一次消除多個反序對，堆排序采用基于樹形的最大元查找策略，合并排序采用分治法。93.一個棧的輸入序列是：1，2，3那么不可能的棧輸出序列是312。94.什么是單向循環鏈表答：單向循環鏈表系指將單鏈表中表尾結點的next域指向表頭結點，而不是存放空指針NULL，形成一個環形鏈表。95.什么是串的長度答：串包含的字符總數被稱為串的長度。96.什么是線性表的鏈接存儲答：線性表的鏈接存儲是指線性表中的結點在內存中任意存放，相鄰結點間用指針鏈接。四、解答1.寫出計算單鏈表head〔head為單鏈表的表頭〕中數據域data值為m的結點個數的算法。intcount(Node*head)//計算單鏈表head中數據域data值為m的結點個數{Node*p=head->next;intn=0;while(p!=NULL){if(p->data==m)n++；p=p->next;}returnn;}//count2.非空單鏈表head，試設計一個算法，交換p所指結點與其后繼結點在鏈表中的位置。解答：intrevers(listnode*head,listnode*p)/*交換p所指結點與其后繼結點在鏈表中的位置*/{if(p->next==NULL)return0;listnode*q=head;while(q->next!=p)q=q->next;{r=p->next；q->next=r;p->next=r->next;r->next=p;return1;}//revers3.線性表用帶頭結點的單向鏈表示，試寫出刪除表中所有data域為零的元素的算法。解：intDeleteItem(Node*head){Node*p=head;//聲明指針p，并令其指向鏈表頭結點while(p->nextNode()!=NULL){if(p->nextNode()->data==0)p->next=p->nextNode()->next.elsep=p->nextNode();//指針下移}}4．試設計一算法，計算帶頭結點的單鏈表head(head指向表頭)的結點個數。解答：intLength()//計算帶表頭結點的單鏈表head的長度{Node*p=head->next;intcount=1;while(p->next!=NULL){p=p->next;count++;}returncount;}5．判斷單鏈表head(head指向表頭)是否是遞增的。解答：intorder(Node*head){Node*p=head;while(p->next!=NULL)if(p->data<p->next->data)p=p->next;elsebreak;if(p->next==NULL)return1;elsereturn0;}6.設計一個算法，在一個單鏈表head中找出值最小的元素。解答：intMin(Node*head)//在單鏈表head中找出值最小的元素{Node*p=head;intmin=p->data;while(p->next!=NULL)阿{if(p->next->data<min)min=p->next->data;p=p->next;}returnmin;}nextdata7設有兩個單鏈表L和L1,其結點構造為,試編寫算法判斷鏈表L1中的各元素是否都是單鏈表L中的元素。nextdata解答：intSubLnk(Node*L,Node*L1){Node*p1=L1;while(p1!=NULL){Node*p=L;while((p!=NULL)&&(p1->data!=p->data)){p=p->next;if(p==NULL)return0;elsep1=p1->next;}return1;}}8.設一棵二叉樹以二叉鏈表為存儲構造，設計一個算法交換二叉樹中每個結點的左子女和右子女。〔12分〕解答：voidexchange(BinTreeNode*t){if(t!=NULL)BinTreeNode*temp;if((t->lchild!=NULL)||(t->rchild!=NULL)){temp=t->lchild;t->lchild=t->rchild;t->rchild=temp;exchange(t->lchild);exchange(t->rchild);}}9.設有一個正整數序列組成帶頭結點的單鏈表head，試編寫算法確定在序列中比正整數x大的數有幾個。〔8分〕解答：intcount〔Node*head，intx〕∥在帶頭結點的單鏈表head中，確定序列中比正整數x大的數有幾個{Node*p=head->next;intcount=0;while(p!=NULL){if(p->data>x)count++;p=p->next;}returncount;}∥算法count完畢10.設一棵二叉樹以二叉鏈表為存儲構造，試設計一個算法計算二叉樹中葉子結點的個數。〔12分〕解答：voidcountleaf(BinTreeNode*t,int&count){if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))count++;〔2分〕countleaf(t->lchild,count);countleaf(t->rchild,count);}}11.設一棵二叉樹以二叉鏈表為存儲構造，試寫一算法求該二叉樹上度為2的結點個數。〔12分〕解答：voidcount2(bitreptrt，intcount){if(t!=NULL){if((t->lchild!=NULL)&&(t->rchild!=NULL))count++;count2(t->lchild,count)；count2(t->rchild,count)；}}//count212.設一棵二叉樹以二叉鏈表為存儲構造，試寫一算法求該二叉樹中最大值〔元〕。〔12分〕解答：voidmaxnode(bitreptrt，intmax){if(t!=NULL)〔2分〕{if(t->data>max)max=t->data;〔4分〕max=maxnode(t->lchild,max)；〔2分〕max=maxnode(t->rchild,max)；〔2分〕}returnmax;〔2分〕}//maxnode13.編寫一個將二叉樹中每個結點的左右孩子交換的算法。(1)給出算法的基本設計思想；(2)用算法描述語言描述算法，并要求對算法中的關鍵步驟給出注釋。答：〔1〕用前根遍歷的遞歸算法交換二叉樹中各結點的左、右子樹。〔2〕算法的C++實現：BintreeNode*swap(BintreeNode*b){BintreeNode*t,*t1,*t2;//t為交換后的二叉樹if(b==NULL)t=NULL;else{t=newBintreeNode;//復制一個根節點t->data=b->data;t1=swap(b->left);t2=swap(b->right);t->left=t2;t->right=t1;}return(t);}14．假定整型數組A[n]中有多個零元素，試設計一個算法將A中所有非零元素依次移到A的前端。(1)給出算法的基本設計思想；(2)用算法描述語言描述算法，并要求對算法中的關鍵步驟給出注釋。答：〔1〕方法1：因為數組是一種根據元素下標可以直接存取的數據構造，設置一