數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及參考答案

PAGE第23頁共23頁中南大學(xué)網(wǎng)絡(luò)教育課程考試復(fù)習(xí)題及參考答案數(shù)據(jù)結(jié)構(gòu)一、填空:1.設(shè)需要對(duì)5個(gè)不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較________次，至多需要比較__________次。2.設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_________次。3.設(shè)在長(zhǎng)度為20的有序表中進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)有_________個(gè)，比較兩次查找成功有結(jié)點(diǎn)數(shù)有_________個(gè)。4.數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：___________、__________和___________。5.在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有________條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有________條邊。6.向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度___________。7.在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為________，整個(gè)堆排序過程的時(shí)間復(fù)雜度為________。8.在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。9.在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，總結(jié)點(diǎn)數(shù)是_______。評(píng)卷人得分10.一棵樹T采用二叉鏈表存儲(chǔ)，如果樹T中某結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則在二叉鏈表BT中所對(duì)應(yīng)的結(jié)點(diǎn)一定_______。11.3.已知數(shù)組A［10］［10］為對(duì)稱矩陣，其中每個(gè)元素占5個(gè)單元?，F(xiàn)將其下三角部分按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A［5，6］對(duì)應(yīng)的地址是_______。12.在有n個(gè)結(jié)點(diǎn)的無向圖中，其邊數(shù)最多為_______。13.取出廣義表A=(x,(a,b,c,d))中原子x的函數(shù)是_______。14.對(duì)矩陣采用壓縮存儲(chǔ)是為了_______。15.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是_______。16.設(shè)線性表中元素的類型是實(shí)型，其首地址為1024，則線性表中第6個(gè)元素的存儲(chǔ)位置是。17.對(duì)于順序存儲(chǔ)的棧，因?yàn)闂５目臻g是有限的，在進(jìn)行運(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)行運(yùn)算時(shí)，可能發(fā)生棧的下溢。18.在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向，另一個(gè)指向。19.由一棵二叉樹的前序序列和可唯一確定這棵二叉樹。20.折半查找的存儲(chǔ)結(jié)構(gòu)僅限于____，且是____。21.對(duì)于一個(gè)順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為____________,在表尾插入元素的時(shí)間復(fù)雜度為________________。22.在稀疏距陣所對(duì)應(yīng)的三元組線形表中，每個(gè)三元組元素按____________為主序，__________為輔序的次序排列。23.中綴表達(dá)示3+X*（2.4/5-6）所對(duì)應(yīng)的后綴表達(dá)示為______________。24.在一棵高度為h的3叉樹中，最多含有_______結(jié)點(diǎn)。25.分析下面算法（程序段），給出最大語句頻度，該算法的時(shí)間復(fù)雜度是____。for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=0;26.空串是____，其長(zhǎng)度等于。27.一個(gè)圖的表示法是唯一的，而表示法是不唯一的。28.在一個(gè)單鏈表中p所指結(jié)點(diǎn)之前插入一個(gè)s(值為e)所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：q=head;while(q->next!=p)q=q->next;s=newNode;s->data=e;q->next=;//填空s->next=;//填空29.在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q=p->next;p->next=____;//填空delete;//填空30.兩個(gè)串相等的充分必要條件是____。31.二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元并且A[0][0]的存儲(chǔ)地址是200，則A[6][12]的地址是____。32.二維數(shù)組A[10..20][5..10]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A[10][5]的存儲(chǔ)地址是1000，則A[18][9]的地址是____。33.求下列廣義表操作的結(jié)果：(1)GetTail[GetHead[((a,b),(c,d))]];(2)GetTail[GetHead[GetTail[((a,b),(c,d))]]]34.已知一個(gè)有向圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是____。35.已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是____。36.在利用快速排序方法對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行快速排序時(shí)，遞歸調(diào)用而使用的棧所能達(dá)到的最大深度為____，共需遞歸調(diào)用的次數(shù)為____，其中第二次遞歸調(diào)用是對(duì)____一組記錄進(jìn)行快速排序。37.在堆排序，快速排序和歸并排序中，若只從存儲(chǔ)空間考慮，則應(yīng)首先選取____方法，其次選取____方法，最后選取____方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取____方法；若只從平均情況下排序最快考慮，則應(yīng)選取____方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取____方法。二、選擇題：1.隊(duì)列的特點(diǎn)是【】。A.先進(jìn)后出B.先進(jìn)先出C.任意位置進(jìn)出D.前面都不正確2.有n個(gè)記錄的文件，如關(guān)鍵字位數(shù)為d，基數(shù)為r，則基數(shù)排序共要進(jìn)行【】遍分配與收集。A.nB.dC.rD.n-d3.在二叉樹結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序【】。A.都不相同B.完全相同C.先序和中序相同，而與后序不同D.中序和后序相同，而與先序不同4.設(shè)有198個(gè)初始?xì)w并段，如采用K-路平衡歸并三遍完成排序，則K值最大為【】。A.12B.13C.145.下面關(guān)于廣義表的敘述中，不正確的是【】。A.廣義表可以是一個(gè)多層次的結(jié)構(gòu)B.廣義表至少有一個(gè)元素C.廣義表可以被其他廣義表所共享D.廣義表可以是一個(gè)遞歸表6.設(shè)二叉樹根結(jié)點(diǎn)的層次為0，一棵深度（高度）為k的滿二叉樹和同樣深度完全二叉樹各有f個(gè)結(jié)點(diǎn)和c個(gè)結(jié)點(diǎn)，下列關(guān)系式不正確的是【】。A.f>=cB.c>fC.f=2k+1-aD.c>sk-17.從L=((apple,pear),(orange,banana))中，取出banana元素的表達(dá)式為【】。A.head(tail(L))B.head(head(tail(L)))C.tail(head(tail(L)))D.head(tail(head(tail(L))))8.下列文件的物理結(jié)構(gòu)中，不利于文件長(zhǎng)度動(dòng)態(tài)增長(zhǎng)的文件物理結(jié)構(gòu)是【】。A.順序結(jié)構(gòu)B.鏈接結(jié)構(gòu)C.索引結(jié)構(gòu)D.Hash結(jié)構(gòu)9.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素可由【】。A.實(shí)體B.域C.數(shù)據(jù)項(xiàng)D.字段10.對(duì)于有n個(gè)頂點(diǎn)的有向圖，由弗洛伊德（FloyD）算法求每一對(duì)頂之間的最短路徑的時(shí)間復(fù)雜度是【】。A.O(1)B.O(n)C.O(n)D.O(n3)11.對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間為【】。A.O(1)B.O(log2n)C.O(n)D.O(n2)12.哈夫曼樹中一定不存在【】。A.度為0的結(jié)點(diǎn)B.度為1的結(jié)點(diǎn)C.度為2的結(jié)點(diǎn)D.帶權(quán)的結(jié)點(diǎn)13.下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？【】A.存儲(chǔ)密度大B.插入和刪除運(yùn)算方便C.獲取符合某種條件的元素方便D.查找運(yùn)算速度快14.有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每個(gè)元素占一個(gè)空間，問A[2][3](10)【】A.658B.648C.6315.列關(guān)于二叉樹遍歷的敘述中，正確的是【】。A.若一個(gè)葉子是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)B.若一個(gè)結(jié)點(diǎn)是某二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)C.若一個(gè)結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序最后一個(gè)結(jié)點(diǎn)D.若一個(gè)樹葉是某二叉樹的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個(gè)結(jié)點(diǎn)16.層二叉樹的結(jié)點(diǎn)總數(shù)最多為【】。A.2k-1B.2k+1C.2K-117.線性表進(jìn)行二分法查找，其前提條件是【】。A.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序B.線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C.線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序18.n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為【】。A.O(1og2n)B.O(n)C.O(1)D.O(n2)19.線性表（7，34，77，25，64，49，20，14）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%7作為散列函數(shù)，則散列地址為0的元素有【】個(gè)。A.1B.2C.320.列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是【】。A.數(shù)組是不同類型值的集合B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C.樹是一種線性結(jié)構(gòu)D.用一維數(shù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法21.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？【】A.有向圖B.隊(duì)列C.線索二叉樹D.B樹22.在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn)，則執(zhí)行如下【】語句序列。A.p=q;p->next=qB.p->next=q;q->next=pC.p->next=q->next;p=q;D.q->next=p->next;p->next=q;23.【】不是隊(duì)列的基本運(yùn)算。A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.從隊(duì)頭刪除一個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值24.若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為【】。A.iB.n=iC.n-i+1D.不確定25.棧的特點(diǎn)是【】，隊(duì)列的特點(diǎn)是【】。A.先進(jìn)先出B.先進(jìn)后出26.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作【】。A.連接B.模式匹配C.求子串D.求串長(zhǎng)27.二維數(shù)組A中，每個(gè)元素A[i][j]的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A[4][7]的起始地址為【】。A.SA+141B.SA+180C.SA+22228.某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是【】。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca29.在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊【】。A.只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)C.只有左子樹上的部分結(jié)點(diǎn)D.只有左子樹上的所有結(jié)點(diǎn)30.具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有【】條邊才能確保是一個(gè)連通圖。A.5B.6C.731.二分查找和二叉排序樹的時(shí)間性能【】。A.相同B.不相同32.采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為【】。A.O（n2）B.O(nlog2n)C.O(n)D.O(log2n)33.在待排序的元素序列基本有序的前提下，效率最高的排序方法是【】。A.插入排序B.選擇排序C.快速排序D.歸并排序34.下述幾種排序方法中，要求內(nèi)存量最大的是【】。A.插入排序B.選擇排序C.快速排序D.歸并排序35.設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作【】。A.連接B.模式匹配C.求子串D.求串長(zhǎng)36.二維數(shù)組A中，每個(gè)元素A[i][j]的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A[4][7]的起始地址為【】。A.SA+141B.SA+180C.SA+22237.某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問順序是【】。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca38.在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊【】。A.只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)C.只有左子樹上的部分結(jié)點(diǎn)D.只有左子樹上的所有結(jié)點(diǎn)39.具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有【】條邊才能確保是一個(gè)連通圖。A.5B.6C.740.二分查找和二叉排序樹的時(shí)間性能【】。A.相同B.不相同C.可能相同D.不確定41.采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為【】。A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)42.在待排序的元素序列基本有序的前提下，效率最高的排序方法是【】。A.插入排序B.選擇排序C.快速排序D.歸并排序43.下面的序列中【】是大頂堆。A.1,2,8,5,3,9,10,4B.1,5,10,6,7,8,9,2C.9,8,7,6,4,8,2,1D44.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下【】方面的內(nèi)容。A.健壯性和可讀性B.并行性C.正確性D.時(shí)空復(fù)雜度45.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行【】。A.p->next=HL->next;HL->next=pB.p->next=HL;HL=pC.p->next=HL;p=HLD.HL=p;p->next=HL46.對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？【】A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變47.一個(gè)棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是【】。A.231B.321C.312D.148.每一趟都能選出一個(gè)元素放在其最終位置上，并且不穩(wěn)定的排序算法是【】。A.冒泡排序B.簡(jiǎn)單選擇排序C.希爾排序D.直接插入排序49.采用開放定址法處理散列表的沖突時(shí)，其平均查找長(zhǎng)度【】。A.低于鏈接法處理沖突B.高于鏈接法處理沖突C.與鏈接法處理沖突相同D.高于二分查找50.若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為【】參數(shù)。A.值B.函數(shù)C.指針D.引用51.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的【】。A.行號(hào)B.列號(hào)C.元素值D.非零元素個(gè)數(shù)52.快速排序在最壞情況下的時(shí)間復(fù)雜度為【】。A.O(log2n)B.O(nlog2n)C.O(n)D.O(n2)53.從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為【】。A.O(n)B.O(1)C.O(log2n)D.O(n2)54.設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為【】。A.O(log2n)B.O(1)C.O(n2)D.O(n)55.設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=【】。A.Nl+N2+……+NmB.l+N2+2N3+3N4+……+(m-1)NmC.N2+2N3+3N4+……+(m-1)NmD.2Nl+3N2+……+(m+1)Nm56.二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，數(shù)組元素A[7][4]的起始地址為【】。A.SA+141B.SA+144C.SA+22257.如果某二叉樹的前根次序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序?yàn)椤尽?。A.uwvtsB.vwutsC.wuvtsD.wutsv58.深度為5的二叉樹至多有【】個(gè)結(jié)點(diǎn)。A.16B.32C.3159.在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的【】倍。A.1/2B.1C.260.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為【】。A.nB.n/2C.(n+1)/261.采用二分查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為【】。A．O（n2）B.O(nlog2n)C.O(n)D.O(log2n)62.下述幾種排序方法中，要求內(nèi)存量最大的是【】。A.插入排序B.選擇排序C.快速排序D.歸并排序63.排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為【】。A.希爾排序B.起泡排序C.插入排序D.選擇排序64.對(duì)于長(zhǎng)度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長(zhǎng)度為【】的值除以9。A.20B.1865.在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的【】。A.入度B.出度C.入度與出度之和D.入度與出度之差66.在基于排序碼比較的排序算法中，【】算法的最壞情況下的時(shí)間復(fù)雜度不高于O(n10g2n)。A.起泡排序B.希爾排序C.歸并排序D.快速排序67.當(dāng)α的值較小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有【】的查找速度。A.較慢B.較快C.相同D.不清楚68.設(shè)有一個(gè)含200個(gè)表項(xiàng)的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢時(shí)找到一個(gè)表項(xiàng)的平均探查次數(shù)不超過1.5，則散列表項(xiàng)應(yīng)能夠至少容納【】個(gè)表項(xiàng)。(設(shè)搜索成功的平均搜索長(zhǎng)度為Snl＝{1+l／(1一α)}／2，其中α為裝填因子)A.400B.526C69.堆是一個(gè)鍵值序列{k1,k2,…..kn},對(duì)I=1,2,….|_n/2_|,滿足【】A.ki≤k2i≤k2i+1B.ki<k2i+1<k2iC.ki≤k2i且ki≤k2i+1(2i+1≤n)D.ki≤k2i或ki≤k2i+1(2i+1≤n)70.若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上【】A.操作的有限集合B.映象的有限集合C.類型的有限集合D.關(guān)系的有限集合71.下列圖示的順序存儲(chǔ)結(jié)構(gòu)表示的二叉樹是【】72.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹【】A.其形態(tài)不一定相同，但平均查找長(zhǎng)度相同B.其形態(tài)不一定相同，平均查找長(zhǎng)度也不一定相同C.其形態(tài)均相同，但平均查找長(zhǎng)度不一定相同D.其形態(tài)均相同，平均查找長(zhǎng)度也都相同73.ISAM文件和VSAM文件的區(qū)別之一是【】A.前者是索引順序文件，后者是索引非順序文件B.前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)存取C.前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動(dòng)態(tài)索引結(jié)構(gòu)D.前者的存儲(chǔ)介質(zhì)是磁盤，后者的存儲(chǔ)介質(zhì)不是磁盤74.下列描述中正確的是【】A.線性表的邏輯順序與存儲(chǔ)順序總是一致的B.每種數(shù)據(jù)結(jié)構(gòu)都具備三個(gè)基本運(yùn)算：插入、刪除和查找C.數(shù)據(jù)結(jié)構(gòu)實(shí)質(zhì)上包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的內(nèi)容D.選擇合適的數(shù)據(jù)結(jié)構(gòu)是解決應(yīng)用問題的關(guān)鍵步驟75.下面程序段的時(shí)間復(fù)雜度是【】I=s=0While(s<n){I++;s+=I;}A.O(1)B.O(n)C.O(log2n)D.O(n^2)三、計(jì)算與算法應(yīng)用題：1.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};按照普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。2.一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA3.畫出下列樹對(duì)應(yīng)的二叉樹，并寫出其先根遍歷序列：BBDFCAEG4.將關(guān)鍵字序列為{54，29，37，86，71，91，8，31，44，26}進(jìn)行歸并排序，寫出各趟詳細(xì)過程。5.試列出如下圖中全部可能的拓?fù)渑判蛐蛄小?.設(shè)某通信系統(tǒng)使用A，B，C，D，E，F(xiàn)，G，H八個(gè)字符，他們出現(xiàn)的概率w={5，29，7，8，14，23，3，11}，試構(gòu)造對(duì)應(yīng)的哈夫曼樹（請(qǐng)按左子樹根結(jié)點(diǎn)的權(quán)小于右子樹樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造）。7.給定表（119，14，22，1，66，21，83，27，56，13，10）,請(qǐng)按表中元素的順序構(gòu)造一棵平衡二叉樹，并求其在等概率情況下查找成功的平均長(zhǎng)度。8.已知一個(gè)有向圖的頂點(diǎn)集V和邊集G分別為：V={a,b,c,d,e,f,g,h}E={<a,b>,<a,c>,<b,f>,<c,d>,<c,e>,<d,a>,<d,f>,<d,g>,<e,g>,<f,h>};假定該圖采用鄰接矩陣表示，則分別寫出從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。9.設(shè)散列表的長(zhǎng)度為13，散列函數(shù)為H（h）=k%13，給定的關(guān)鍵碼序列為19，14，23，01，68，20，84，27。試畫出用線性探查法解決沖突時(shí)所構(gòu)成的散列表。012345678910111210.對(duì)7個(gè)關(guān)鍵字進(jìn)行快速排序，在最好的情況下僅需進(jìn)行10次關(guān)鍵字的比較。(1)假設(shè)關(guān)鍵字集合為{1,2,3,4,5,6,7}，試舉出能達(dá)到上述結(jié)果的初始關(guān)鍵字序列；(2)對(duì)所舉序列進(jìn)行快速排序，寫出排序過程。11.如圖所示二叉樹，回答下列問題。12.畫出在一個(gè)初始為空的AVL樹中依次插入3,1,4,6,9,8,5,7時(shí)每一插入后AVL樹的形態(tài)。若做了某種旋轉(zhuǎn)，說明旋轉(zhuǎn)的類型。然后，給出在這棵插入后得到的AVL樹中刪去根結(jié)點(diǎn)后的結(jié)果。13.已知一組記錄的排序碼為（46，79，56，38，40，80，95，24），寫出對(duì)其進(jìn)行快速排序的每一次劃分結(jié)果。14.一個(gè)線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT[0..12]，散列函數(shù)為H（key）=key%13并用線性探查法解決沖突，請(qǐng)畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度。15.已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECDFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。16.假定對(duì)線性表(38，25，74，52，48，65，36)進(jìn)行散列存儲(chǔ)，采用H(K)=K％9作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則計(jì)算對(duì)應(yīng)的平均查找長(zhǎng)度。四、閱讀下列算法，分析它的作用：1.intAA(LNode*HL,ElemTypex){intn=0;LNode*p=HL;while(p!=NULL){if(p->data==x)n++;p=p->next;}returnn;}對(duì)于結(jié)點(diǎn)類型為L(zhǎng)Node的單鏈表，以上算法的功能為：2.intAA(LNode*HL,ElemTypex){intn=0;LNode*p=HL;while(p!=NULL){if(p->data==x)n++;p=p->next;}returnn;}對(duì)于結(jié)點(diǎn)類型為L(zhǎng)Node的單鏈表，以上算法的功能為：3.假定從鍵盤上輸入一批整數(shù)，依次為：786345309134–1，請(qǐng)寫出輸出結(jié)果。#include<iostream.h>#include<stdlib.h>constintstackmaxsize=30;typedefintelemtype;structstack{elemtypestack[stackmaxsize];inttop;};#include“stack.h”voidmain【】{stacka;initstack(a);intx;cin>>x;while(x!=-1){push(a,x);cin>>x;}while(!stackempty(a))cout<<pop(a)<<””;cout<<end1;}該算法的輸出結(jié)果為：__________________________________________________________.4.讀下述算法，說明本算法完成什么功能。template<calsstype>voidBinTree<Type>：：unknown(BinTreeNode<Type>*t){BinTreeNode<Type>*p=t,*temp;if(p!=NULL){temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown(p→leftchild);undnown(p→rightchild);}//類定義//類定義constintMAX=20;typedefcharElemType;classSqstack{private:ElemTypeelem[MAX];inttop;public:Sqstack(){top=0};ElemTypepop();voidpush(ElemTypex);//…….;};該算法的功能是：________________________________5.閱讀下列算法，說明該算法的作用。voidSqstack::push(ElemTypex){if(top==MAX-1)cout<<”\n滿！”；else{top++;elem[top]=x;}}//pushstructSnode//structSnode//結(jié)點(diǎn)結(jié)構(gòu){chardata;Snode*next;};classLink//鏈表類{private:Snode*Head;public:Link(){Head=NULL};voidcreat();voidoutput();//…….;6.有如下圖所示單鏈表，經(jīng)過output（）算法處理后，單鏈表發(fā)生了什么變化？畫出處理后的單鏈表圖示。voidLink:output(){p=Head->next;while(p!=NULL){cout<<”\ndata=”<<p->data;p=p->next;}}//outputaaHeadbc^ed7.閱讀下列算法，說明該算法的作用。intLinkList::sum【】{intx;NodeType*p;p=Head->next;while(p!=NULL){x++;p=p->next;}returnx;}//pop8.讀下述算法，說明本算法完成什么功能。voidBtree::inordern(bnode*p,int&n){if(p!=NULL){inordern(p->lch,n);if(p->lch==NULL&&p->rch==NULL)n++;inordern(p->rch,n);}}//inordern9.voidAD(Lnode*&HL){Insert(HL,30);Insert(HL,50);Delete(HL,26);Delete(HL,55);}假定調(diào)用該算法時(shí)以HL為表頭指針的單鏈表中的內(nèi)容為（15，26，48，55），則調(diào)用返回后該單鏈表中的內(nèi)容為：______________________________。10.voidAI(adjmatrrixGA,inti,intn){cout<<i<<’’;//類定義constintMAX//類定義constintMAX=20;typedefcharElemType;classSqstack{private:ElemTypeelem[MAX];inttop;public:Sqstack(){top=0};ElemTypepop();voidpush(ElemTypex);//…….;};for(intj=0;j<n;j++)if(Ga[I][j]!=0&&GA[i][j]!=MaxValue&&!visited[j])AI(GA,j,n);}該算法的功能為：___________________________________。11.閱讀下列算法，說明該算法的作用。ElemTtypeSqstack::pop【】{ElemTypex;if(top==0)x=-999;else{x=elem[top];top--;}returnx;}//pop12.有如下圖所示單鏈表，經(jīng)過reverse算法處理后，單鏈表發(fā)生了什么變化？畫出處理后的單鏈表圖示。structSnode//結(jié)點(diǎn)結(jié)構(gòu)structSnode//結(jié)點(diǎn)結(jié)構(gòu){chardata;Snode*next;};classLink//鏈表類{private:Snode*Head;public:Link(){Head=NULL};voidcreat();voidreverse();voidoutput();//…….;{Snode*p,*q;p=Head->next;Head->next=NULL;while(p!=NULL){q=p->next;p->next=Head->next;Head>next=p;p=q;}aHeadbcaHeadbc^ed13.下列函數(shù)是二叉排序樹的什么算法？如果K值為5，針對(duì)下圖所示二叉樹，運(yùn)行下列算法，輸出是什么？比較幾次得到結(jié)果？VoidBstree::Search(KeyTypeK){intflag=0;BstNode*q=root,*p=NULL;while((q!=NULL)&&(flag==0)){if(q->key==K)flag=1;elseif(K<q->key){p=q;q=q->lch;}else{p=q;q=q->rch;}}if(flag==0)cout<<"\n查找失敗，無此結(jié)點(diǎn)！\n";elsecout<<"\n查找成功，找到："<<q->key<<endl;}77852492914.voidAA(LNode*HL,constElemType&item){LNode*newptr=newLnode;newptr->data=item;LNode*p=HL;while(p->next!=HL)p=p->next;newptr->next=HL;p->next=newptr;}對(duì)于結(jié)點(diǎn)類型為L(zhǎng)Node的單鏈表，以上算法的功能為：15.voidBB(List&L){inti=0;while(i<L.size){intj=i+1;while(j<L.size){if(L.list[j]==L.list){for(intk=j+1;k<L.size;k++)L.list[k-1]=L.list[k];L.size--;}elsej++;}i++;}}以上算法的功能為：16.voidCC(BTreeNode*&BST){ElemTypea[6]={45，23，78，35，77，25}；BST=NULL；for(inti=0,i<6;i++)Insert(BST,a[i]);}調(diào)用該算法后，生成的二叉搜索數(shù)的中序序列為：17.voidDD(){ElemTypeA[]={1,3,5,7,9,2,4,6,8,10},B[10];TwoMerge(A,B,0,4,9);for(inti=0;i<10;i++)cout<<B[i]<<”“;cout<<endl;}調(diào)用該算法后，輸出結(jié)果為：五、算法設(shè)計(jì)題：1.編寫復(fù)制一棵二叉樹的非遞歸算法。3.試用遞歸法編寫輸出從n個(gè)數(shù)中挑選k個(gè)進(jìn)行排列所得序列的算法。4.編寫一個(gè)算法，交換單鏈表中p所指向的結(jié)點(diǎn)和其后續(xù)結(jié)點(diǎn)的兩個(gè)結(jié)點(diǎn)，Head指向該鏈表的表頭，P指向鏈表中的某一結(jié)點(diǎn)。aaHeadbbc^ed5.試寫一遞歸算法，從大到小輸出二叉排序樹中所有的關(guān)鍵字值小于key的元素值。6.已知帶頭結(jié)點(diǎn)的單鏈表是一個(gè)遞增有序表，試寫一算法，刪除表中值大于min且小于max的結(jié)點(diǎn)（若表中有這樣的結(jié)點(diǎn)），同時(shí)釋放被刪除結(jié)點(diǎn)的空間，這里min和max是兩個(gè)給定的參數(shù)。77Head97b15^50267.已知深度為h的二叉樹以一維數(shù)組BT(1:2h-1)作為其存儲(chǔ)結(jié)構(gòu)。請(qǐng)寫一算法，求該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)。8.編寫在以BST為樹根指針的二叉搜索樹上進(jìn)行查找值為item的結(jié)點(diǎn)的非遞歸算法，若查找item帶回整個(gè)結(jié)點(diǎn)的值并返回true，否則返回false。boolFind（BtreeNode*BST，ElemType&item）9.設(shè)A=(a1,...,am)和B=(b1,...,bn)均為順序表，A'和B'分別為A和B中除去最大共同前綴后的子表。若A'=B'=空表，則A=B；若A'=空表，而B'≠空表，或者兩者均不為空表，且A'的首元小于B'的首元，則A<B；否則A>B。試寫一個(gè)比較A，B大小的算法。10.已知單鏈表a和b的元素按值遞增有序排列,編寫算法歸并a和b得到新的單鏈表c，c的元素按值遞減有序。11.編寫遞歸算法，對(duì)于二叉樹中每一個(gè)元素值為x的結(jié)點(diǎn)，刪去以它為根的子樹，并釋放相應(yīng)的空間。12.編寫算法判別T是否為二叉排序樹。參考答案一、填空題：1.4，102.n3.1，24.線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu)5.n(n-1)/2n(n-1)6.增加17.O(log2n)O(nlog2n)8.歸并9.n-110.左右子樹空11.122512.n(n-1)/213.head(A)14.節(jié)省空間15.L->next=L->prior或L->next=L16.104417.入棧（插入），出棧（刪除）18.前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn)19.中序序列20.順序存儲(chǔ)結(jié)構(gòu)，有序的21.O(n)O(1)22.行號(hào)列號(hào)23.3x2.45／6－*＋24.(3h-1)/225.n3，O(n3)26.零個(gè)字符的串，零27.鄰接矩陣，鄰接表28.s,p29.q->next,q30.兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置的字符相同31.200+（6*20+12）=32632.1000+((18-10)*6+(9-5))*4=120833.(1).(b)(2).(d)34求矩陣第i列非零元素之和35.將矩陣第i行全部置為零36.2.2;4;（23，38，15）37.堆排序、快速排序、歸并排序、歸并排序、快速排序、堆排序二、單項(xiàng)選擇題：123456789101112131415BBBCBBDACDBBADA16171819202122232425①25②26272829ACCDDBDACBABBDA303132333435363738394041424344ABBADBBDAABBADB454647484950515253545556575859ABCBBDADCDBCBCC606162636465666768697071727374CCDCCCCBACBABCD75BBEGBEGDFCA1.普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹為：(1,2)3,(1,3)5,(1,4)8,(4,6)4,(2,5)10,(4,7)202.在先序序列空格中依次填A(yù)DKJ，中序中依次填BHG，后序中依次填DIEC。3.畫出下列樹對(duì)應(yīng)的二叉樹，并寫出其先根遍歷序列：先根遍歷序列：ABDEGFC4.將關(guān)鍵字序列為{54，29，37，86，71，91，8，31，44，26}進(jìn)行歸并排序，寫出各趟詳細(xì)過程。542937867191831442629543786719183126442937548683171912644829313754718691264482629313744547186915.全部可能的拓?fù)渑判蛐蛄袨椋?523634、152634、156234、561234、516234、512634、5123646.DD8F23H111942A5B29C7E14G381529481007.平均長(zhǎng)度為4.8.深度優(yōu)先搜索序列：a，b，f，h，c，d，g，e廣度優(yōu)先搜索序列：a，b，c，f，d，e，h，g9.計(jì)算機(jī)關(guān)鍵碼得到的散列地址關(guān)鍵碼1914230168208427散列地址611013761在散列表中散列結(jié)果0123456789101112140168271920842310.對(duì)n個(gè)關(guān)鍵自序列進(jìn)行一趟快速排序，要進(jìn)行n-1次比較，也就是基準(zhǔn)和其他n-1個(gè)關(guān)鍵字比較。這里要求10次，而7-1+2*(3-1)=10，這就要求2趟快速排序后，算法結(jié)束。所以，列舉出來的序列，要求在做partition的時(shí)候，正好將序列平分(1)4132657或4137652或4537612或4135627(2)按自己序列完成11.答案：(1)djbaechif(2)abdjcefhi(3)jdbeihfca12.在這個(gè)AVL樹中刪除根結(jié)點(diǎn)時(shí)有兩種方案:【方案1】在根的左子樹中沿右鏈走到底,用5遞補(bǔ)根結(jié)點(diǎn)中原來的6,再刪除5所在的結(jié)點(diǎn)?！痉桨?】在根的右子樹中沿左鏈走到底,用7遞補(bǔ)根結(jié)點(diǎn)中原來的6,再刪除7所在的結(jié)點(diǎn)。13.劃分次序劃分結(jié)果第一次[38

24

40]46

[56

80

95

79]第二次24

[38

40]46

[56

80

95

79]第三次24

38

40

46

[56

80

95

79]第四次24

38

40

46

56

[80

95

79]第五次24

38

40

46

56

79

[80

95]第六次24

38

40

46

56

79

80

9514.012345678910111278

1503

57452031

233612查找成功的平均查找長(zhǎng)度：ASLSUCC=14/10=1.415.此二叉樹的后序遍歷結(jié)果是：EDCBIHJGFA16.13／71l／7四、閱讀下列算法，分析它的作用1.統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)。2.對(duì)數(shù)組A中的n個(gè)元素進(jìn)行排序，稱為起泡算法。3.該算法的輸入結(jié)果是：3491304563784.該算法的功能是：交換二叉樹的左右子樹的遞歸算法。5.該算法是順序棧類的進(jìn)棧算法。如果棧滿返回“滿”；否則X元素進(jìn)棧。6.該算法是將鏈表的數(shù)據(jù)元素輸出算法。輸出結(jié)果：abcaHeadaHeadbc^ed7.該算法是求鏈表結(jié)點(diǎn)個(gè)數(shù)的算法。結(jié)果返回結(jié)點(diǎn)個(gè)數(shù)的總和值。8.本算法要求二叉樹中葉子結(jié)點(diǎn)的總數(shù)的算法。用n值存儲(chǔ)葉子結(jié)點(diǎn)的個(gè)數(shù)。9.（15，30，48，50）10.從初始點(diǎn)vi出發(fā)深度優(yōu)先搜索遍歷由鄰接距陣GA所表示的圖11.該算法是順序棧類的出棧算法。如果?？辗祷?999；否則返回出棧元素的值。12.該算法是將鏈表逆置的算法。鏈表逆置后，具體如下圖：eHeaddc^abeHeaddc^ab比較3次得到結(jié)果。14.向單鏈表的末尾添加一個(gè)元素。15.刪除線性表中所有重復(fù)的元素。16.23253545777817.12345678910五、算法設(shè)計(jì)題：1.將算法實(shí)現(xiàn)函數(shù)聲明為二叉樹類的友元函數(shù)，可采用層次遍歷的方式進(jìn)行復(fù)制，將已復(fù)制的結(jié)點(diǎn)進(jìn)入一個(gè)隊(duì)列中即可。具體算法實(shí)現(xiàn)如下：//文件路徑名:exam5\alg.htemplate<classElemType>voidCopyBitree(BinaryTree<ElemType>*fromBtPtr,BinaryTree<ElemType>*&toBtPtr)//操作結(jié)果:復(fù)制二叉樹fromBt到toBt的非遞歸算法{ if(toBtPtr!=NULL)deletetoBtPtr; //釋放toBtPtr if(fromBtPtr->Empty()) { //空二叉樹 toBtPtr=NULL; //空二叉樹 } else { //非空二叉樹 LinkQueue<BinTreeNode<ElemType>*>fromQ,toQ; //隊(duì)列 BinTreeNode<ElemType>*fromPtr,*toPtr,*fromRoot,*toRoot; fromRoot=fromBtPtr->GetRoot(); //取出fromBtPtr的根 toRoot=newBinTreeNode<ElemType>(fromRoot->data); //復(fù)制根結(jié)點(diǎn) fromQ.InQueue(fromRoot);toQ.InQueue(toRoot); //入隊(duì) while(!fromQ.Empty()) { //fromQ非空 fromQ.OutQueue(fromPtr); //出隊(duì) toQ.OutQueue(toPtr); //出隊(duì) if(fromPtr->leftChild!=NULL) { //左子樹非空 toPtr->leftChild=newBinTreeNode<ElemType>(fromPtr->leftChild->data); //復(fù)制fromPtr左孩子 fromQ.InQueue(fromPtr->leftChild);toQ.InQueue(toPtr->leftChild); //入隊(duì) } if(fromPtr->rightChild!=NULL) { //右子樹非空 toPtr->rightChild=newBinTreeNode<ElemType>(fromPtr->rightChild->data); //復(fù)制fromPtr左孩子 fromQ.InQueue(fromPtr->rightChild);toQ.InQueue(toPtr->rightChild); //入隊(duì) } } toBtPtr=newBinaryTree<ElemType>(toRoot); //生成toBtPtr}}2.從上圖來看，二叉樹的第一層顯示在第一列，第二層顯示在第二列，第三層顯示在第三列；每行顯示一個(gè)結(jié)點(diǎn)，從上至下是先顯示右子樹，再顯示根，最后最左子樹，也就是以先遍歷右子樹，最后遍歷左子樹的中序遍歷次序顯示各結(jié)點(diǎn)。具體算法實(shí)現(xiàn)如下：//文件路徑名:exam1\alg.hssElemType>voidDisplayHelp(BinTreeNode<ElemType>*r,intlevel)//操作結(jié)果：按樹狀形式顯示以r為根的二叉樹，level為層次數(shù)，可設(shè)根結(jié)點(diǎn)的層次數(shù)為1{ if(r!=NULL) { //空樹不顯式，只顯式非空樹 DisplayHelp<ElemType>(r->rightChild,level+1); //顯示右子樹 cout<<endl; //顯示新行 for(inti=0;i<level-1;i++) cout<<""; //確保在第level列顯示結(jié)點(diǎn) cout<<r->data; //顯示結(jié)點(diǎn) DisplayHelp<ElemType>(r->leftChild,level+1); //顯示左子樹 }}template<classElemType>voidDisplay(constBinaryTree<ElemType>&bt)//操作結(jié)果：樹狀形式顯示二叉樹{ DisplayHelp<ElemType>(bt.GetRoot(),1); //樹狀顯示以bt.GetRoot()為根的二叉樹 cout<<endl; //換行}3.對(duì)于排列的解空間可構(gòu)造一個(gè)虛擬的解空間樹，比如n=5，k=3時(shí)的解空間樹如下圖所示，可采用對(duì)此樹進(jìn)行先序遍歷方式進(jìn)行遍歷，并用遞歸法進(jìn)行遞歸輸出從n個(gè)數(shù)中挑選k個(gè)進(jìn)行排列所得序列。具體算法實(shí)現(xiàn)如下：//文件路徑名:exam7\alg.htemplate<classElemType>voidArrage(ElemTypea[],intk,intn,intoutlen=0)//操作結(jié)果:回溯法輸出排列序列，a[0..k-1]為k個(gè)數(shù)的排列序列outlen為當(dāng)前所求排列// 序列的長(zhǎng)度，其中outlen=k時(shí)的排列序列為所求；n為list數(shù)組長(zhǎng)度{ if(k<0||k>=n)return; //此時(shí)無排列 inti; //臨時(shí)變量 if(outlen==k+1) { //得到一個(gè)排列 for(i=0;i<k;i++) { //輸出一個(gè)排列 cout<<a[i]; //輸出a[i] } cout<<""; //用空格分隔不同排列 } else { //對(duì)解空間進(jìn)行前序遍歷，a[outlen..n]有多個(gè)排列，遞歸的生成排列 for(i=outlen;i<n;i++) { //處理a[i] Swap(a[outlen+1],a[i]); //交換a[outlen+1]與a[i] Arrage(a,k,n,outlen+1); //對(duì)序列長(zhǎng)度outlen+1遞歸 Swap(a[outlen+1],a[i]); //交換a[outlen+1]與a[i] } }}aHeadbbd^ecaHeadbbd^ecvoidLink::swap(NodeType*p)//0.5分{NodeType*q,*r,*s;q=p->next;//0.5分if(q!=NULL)//1分{if(p==Head)//4分{Head=Head->next;s=Head->next;Head->next=p;p->next=s;}Else//4分{r=Head;while(r->next!=p)r=r->next;r->next=q;p->next=q->next;q->next=p;}}}5.可按先遍歷右子樹，遍歷根結(jié)點(diǎn)，再遍歷左子樹進(jìn)行中序遍歷，這樣可實(shí)現(xiàn)由大到小遍歷一棵二叉排序樹。具體算法實(shí)現(xiàn)如下：//文件路徑名:exam4\alg.h#include"binary_sort_tree.h" //二叉排序樹類template<classElemType,classKeyType>voidInOrderHelp(BinTreeNode<ElemType>*r,constKeyType&key)//操作結(jié)果:從大到小輸出以r為根的二叉排序樹中所有的關(guān)鍵字值不小于key的元素值{ if(r!=NULL) { //非空二叉排序樹 InOrderHelp(r->leftChild,key); //遍歷左子樹 if(r->data<key)cout<<r->data<<""; //輸出根結(jié)點(diǎn) elsereturn; InOrderHelp(r->rightChild,key); //遍歷右子樹 }}template<classElemType,classKeyType>voidInOrder(constBinarySortTree<ElemType,KeyType>&t,constKeyType&key)//操作結(jié)果:從大到小輸出二叉排序樹中所有的關(guān)鍵字值不小于key的元素值{ InOrderHelp(t.GetRoot(),key); //調(diào)用輔助函數(shù)實(shí)現(xiàn)從大到小輸出二叉排序樹中所有的關(guān)鍵字值不小于key的元素值}6.voidLink::Delnode(){NodeType*p=Head->next,*q,*r=p;while(p!=NULL&&p->data<min){r=p;p=p->next;}q=p;while