算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

1、算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題一、單選題1要求具有同一邏輯結(jié)構(gòu)的數(shù)據(jù)元素具有相同的特性，其含義為（B）。A. 數(shù)據(jù)元素具有同一的特點(diǎn)B. 不僅數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)相同，而且其對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類(lèi)型要一致C. 每個(gè)數(shù)據(jù)元素都一樣D. 僅需要數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)相同2. 下列程序段for（i=1;i<=n;i+）Al,j=O;的時(shí)間復(fù)雜度是（D）。A. 0B.0（0）C.0（1+n）D.O（n）3. 在一個(gè)單鏈表中，已知*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*q和*p之間插入結(jié)點(diǎn)*s，則執(zhí)行操作（0。A. s->next=p->next;p->next=s;B.s->next

2、=p;p->next=sC.q->next=s;s->next=p;D.p->next=s;s->next=q;4. 在一個(gè)單鏈表中，若刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行操作（A）。A. q=p->next;p->next=q_>next;free（q）;B.p=p->next;p->next=p->next->next;free（p）;C.p->next=q->next;free（p->next）;D.p=p->next->next;free（p->next）;5. 設(shè)指針p指向雙鏈表的某

3、一結(jié)點(diǎn)，則雙鏈表結(jié)構(gòu)的對(duì)稱(chēng)性可以用下面的操作來(lái)反映（C）。A. p->prior->next=p->next->next;B.p->prior->prior=p->next->prior;C.p->prior->next=p->next->prior;D.p_>next->next=p->prior->prior;6. 表達(dá)式a*（b+c）-d的后綴表達(dá)式是（B）。A. abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd7. 設(shè)一個(gè)棧的輸入序列為A,B,C,D,則借助一個(gè)棧所得到的

4、輸出序列不可能是（D）。A.A,B,C,DB.D,C,B,AC.A,C,D,BD.D,A,B,C&設(shè)一個(gè)棧的輸入序列為12345,則借助一個(gè)棧所得到的輸出序列不可能是（B）。A.23415B.54132C.23145D.154329. 設(shè)有一個(gè)順序棧，6個(gè)元素1、2、3、4、5、6依次入棧，如果6個(gè)元素出棧的順序是2、3、4、6、5、1,則棧的容量至少應(yīng)該是（B）。A.2B.3C.5D.610. 設(shè)有一個(gè)順序棧的入棧序列是a、b、c,則3個(gè)元素都出棧的可能不同排列個(gè)數(shù)為（B）。A.4B.5C.6D.711.若已知一個(gè)棧的入棧序列是1,2,3，n,其輸出序列為pl,p2,p3,pn,若p

5、l是n,則pi是(C)oA.iB.n-lC.n-i+1D.不確定12.已知廣義表LS=(a,b,c),(d,e,f)，運(yùn)算head和tail函數(shù)取出兀素e的運(yùn)算是(C)oA.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)13.二維數(shù)組A的每個(gè)兀素是由6個(gè)字符組成的串，其行下標(biāo)i=0,l，8,列下標(biāo)為j=1,2.，10o設(shè)每個(gè)字符占一個(gè)字節(jié)，若按行先存儲(chǔ)，元素A8,5的起始地址與A按列存儲(chǔ)時(shí)起始地址相同的元素是（B）。A.A8,5B.A3,10C.A5,8D.A0,914. 數(shù)組A1.5

6、,1.6的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中,則元素A5,5的地址為（A）A.1140B.1145C.1120D.112515. 對(duì)二叉樹(shù)從1開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編號(hào)，同一個(gè)結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，則可采用遍歷方式是（C）。A.先序B.中序C.后序D.從根開(kāi)始的層次遍歷16. 某二叉樹(shù)的先序序列和后序序列正好相反，則該二叉樹(shù)的特點(diǎn)一定是（B）。A.空或只有一個(gè)結(jié)點(diǎn)B.高度等于其結(jié)點(diǎn)數(shù)C.任一結(jié)點(diǎn)無(wú)左孩子D.任一結(jié)點(diǎn)無(wú)右孩子17.下列說(shuō)法正確的是(D)。(1) 二又樹(shù)按某種方式線索化后，任一節(jié)

7、點(diǎn)均有指向前趨和后繼的線索(2) 二叉樹(shù)的前序遍歷序列中，任意一個(gè)節(jié)點(diǎn)均處于在子孫節(jié)點(diǎn)前(3) 二叉排序樹(shù)中任一節(jié)點(diǎn)的值大于其左孩子的值，小于右孩子的值A(chǔ).(2)(3)B.(1)(2)C.(1)(3)D.前面的可選答案都不對(duì)18. 下面的說(shuō)法中正確的是(B)。(1) 任何一棵二叉樹(shù)的葉子節(jié)點(diǎn)在三種遍歷中的相對(duì)次序不變。(2) 按二叉樹(shù)定義，具有三個(gè)節(jié)點(diǎn)的二叉樹(shù)共有6種。A.(1),(2)B.(1)C.(2)D.(1),(2)都錯(cuò)19. 樹(shù)有先根遍歷和后根遍歷，樹(shù)可以轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)。下面的說(shuō)法正確的是(B)。A. 樹(shù)的后根遍歷與其對(duì)應(yīng)的二叉樹(shù)的后根遍歷相同B. 樹(shù)的后根遍歷與其對(duì)應(yīng)的二叉樹(shù)的

8、中根遍歷相同C. 樹(shù)的先根遍歷與其對(duì)應(yīng)的二叉樹(shù)的中根遍歷相同D. 以上都不對(duì)20. 下圖的鄰接表中，從頂點(diǎn)V1出發(fā)采用深度優(yōu)先搜索法遍歷該圖，則可能的頂點(diǎn)序列是(D)。A.V1V2V3V4V5B.V1V2V3V5V4C.V1V4V3V5V2D.V1V3V4V5V221 .以下說(shuō)法不正確的是(D)。A. 無(wú)向圖中的極大連通子圖稱(chēng)為連通分量B. 連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)C. 圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn)D. 有向圖的遍歷不可采用廣度優(yōu)先搜索22 .在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后引起了不平衡，設(shè)最低(最接近于葉子)的不平衡點(diǎn)是A,并已知A的左、右孩

9、子的平衡因子分別為-1和0,則應(yīng)進(jìn)行的平衡旋轉(zhuǎn)是(B)。A.LL型B.LR型C.RL型D.RR型23. 設(shè)哈希表長(zhǎng)為14,哈希函數(shù)H(key)=key%11,表中已有數(shù)據(jù)的關(guān)鍵字為15,38,61,84,四個(gè)，現(xiàn)將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置是(A)。A.8B.3C.5D.924. 對(duì)散列文件，以下說(shuō)法錯(cuò)誤的是(D)。A. 散列文件插入、刪除方便，不需要索引區(qū)且節(jié)省存儲(chǔ)空間B. 散列文件只能按關(guān)鍵字隨機(jī)存取且存取速度快C. 經(jīng)過(guò)多次插入、刪除后，可能出現(xiàn)溢出桶滿(mǎn)的情況D. 散列文件順序存取方便26. 對(duì)有18個(gè)元素的有序表作二分查找，則查找A3的比較序列

10、的下標(biāo)為(D)。A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,327. 在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并已知A的左孩子的平衡因子為0,右孩子的平衡因子為1，則應(yīng)調(diào)整以使其平衡，所作的平衡旋轉(zhuǎn)是(C)。A.LL型B.LR型C.RL型D.RR型28. 在n個(gè)結(jié)點(diǎn)且為完全二叉樹(shù)的二叉排序樹(shù)中查找一個(gè)鍵值，其平均比較次數(shù)的數(shù)量級(jí)為(B)。2A.O(n)B.O(log2n)C.O(nlog2n)D.O(n)29下列排序算法中，在待排序數(shù)據(jù)已基本有序時(shí)，效率最高的排序方法是（ATA.插入B.選擇C.快速D.堆30. 下面關(guān)于B樹(shù)和B+樹(shù)的敘述中，不正確的

11、結(jié)論是（A）。A. B-樹(shù)和B+樹(shù)都能有效地支持順序查找B. B-樹(shù)和B+樹(shù)都能有效地支持隨機(jī)查找C. B-樹(shù)和B+樹(shù)都是平衡的多叉樹(shù)D. B樹(shù)和B+樹(shù)都可用于文件索引結(jié)構(gòu)31. 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（B）。A.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B.從源點(diǎn)到匯點(diǎn)的最短路徑C.最長(zhǎng)的回路D.最短的回路32. 將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（A）oA.nB.2n-1C.2nD.n-133. 下列排序算法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為0（nlog2n）的是（A）。A.堆排序B.冒泡排序C.直接選擇排序D.快速排序34. 下列排序算法中，某一趟結(jié)束后未必能選出一個(gè)元素

12、放在其最終位置上的是（D）A.堆排序B.冒泡排序C.快速排序D.直接插入排序35. 數(shù)據(jù)表A中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用最節(jié)省時(shí)間的排序算法是（A）oA.堆排序B.希爾排序C.快速排序D.直接選擇排序36. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R）,其中D是（）oA.算法B.操作的集合C.數(shù)據(jù)元素的集合D.數(shù)據(jù)關(guān)系的集合37. 順序表是線性表的（A）oA.順序存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)38.在一個(gè)單鏈表中，已知*p結(jié)點(diǎn)不是最后結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則執(zhí)行操作（B）A.s->next=p;p->next=s;B.s-

13、>next=p->next;p->next=sC.s->next=p->next;p=s;D.p->next=s;s->next=p;39. 循環(huán)隊(duì)列A0.m-1存放其元素值，用front和rear分別表示隊(duì)頭及隊(duì)尾，則循環(huán)隊(duì)列滿(mǎn)的條件是（A）。A.（Q.rear+1）%m=Q.frontB.Q.rear=Q.front+1C.Q.rear+l=Q.frontD.Q.real=Q.front40. 如果以鏈棧為存儲(chǔ)結(jié)構(gòu)，則出棧操作時(shí)（B）oA.必須判棧滿(mǎn)B.必須判別?？誄.判別棧中元素類(lèi)型D.不必作任何判別41.對(duì)矩陣壓縮存儲(chǔ)是為了（B）°A

14、.方便運(yùn)算B.節(jié)省空間C.方便存儲(chǔ)D.提高運(yùn)算速度42. 將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1, 則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（B）oA.98B.99C.50D.4843. 二義樹(shù)在線索化后，仍不能有效求解的問(wèn)題是（D）。A.先序線索二叉樹(shù)中求先序后繼B.中序線索二叉樹(shù)中求中序后繼C.中序線索二叉樹(shù)中求中序前趨D.后序線索二又樹(shù)中求后序后繼44. 對(duì)于關(guān)鍵字序列（12,13,11,18,60,15,7,18,25,100），用篩選法建堆，則開(kāi)始結(jié)點(diǎn)的鍵值必須為（C）oA.100B.12C.60D.1545. 無(wú)向圖G=（VE）

15、，其中V=a,b,C,d,e,f,E=<a,b>,<a,e>,<a,c>,<b,e>,<c,f>,<f,d>,<e,d>，對(duì)該圖進(jìn)行深度優(yōu)先排序，得到的頂點(diǎn)序列正確的是（D）oA.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b46. 設(shè)圖G用鄰接表存儲(chǔ)，則拓?fù)渑判虻臅r(shí)間復(fù)雜度為（B）oA.D（n）B.O（n+e）C.O（nxn）D.0（nxe）47. 關(guān)于散列法查找說(shuō)法正確的是（B）oA. 采用鏈地址解決沖突時(shí)，查找一個(gè)元素的時(shí)間是相同的B. 采用鏈地址解決

16、沖突時(shí)，若規(guī)定插入總是在鏈?zhǔn)?，則插入任一個(gè)元素的時(shí)間是相同的C. 采用鏈地址解決沖突容易引起聚集現(xiàn)象D. 再散列不易產(chǎn)生聚集48在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后引起了不平衡，設(shè)最低（最接近于葉子）的不平衡點(diǎn)是A,并已知A的左、右孩子的平衡因子分別為-1和0,則應(yīng)進(jìn)行的平衡旋轉(zhuǎn)是（B）。A.LL型B.LR型C.RL型D.RR型49. 在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（D）。A.G中有弧<Vi,Vj>B.G中有一條從Vi到Vj的路徑C.G中沒(méi)有弧<Vi,Vj>D.G中有一條從Vj到Vi的路徑50. 排序算法中，算法可能會(huì)出現(xiàn)下面情況：初

17、始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多的是（C）。A.堆排序B.冒泡排序C.快速排序D.SHELL排序二、填空（問(wèn)答）題1. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R）,其中D和R的含義是什么。（D是數(shù)據(jù)元素的集合，R是數(shù)據(jù)關(guān)系的集合）。數(shù)據(jù)的邏輯結(jié)構(gòu)包括哪四種類(lèi)型。（線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)、集合類(lèi)型）。從存儲(chǔ)結(jié)構(gòu)的概念上講，順序表是線性表的（順序存儲(chǔ)結(jié)構(gòu)）,鏈表是（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）。2. 算法的五個(gè)重要特性有哪些。（有窮性、確定性、可行性、輸入、輸出）。抽象數(shù)據(jù)類(lèi)型是指一個(gè)（數(shù)學(xué)模型）以及定義在該模型上的（一組操作）。3. 在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中，在任意一個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)所需要移動(dòng)結(jié)點(diǎn)的

18、平均次數(shù)為（n/2）。在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中，任意刪除一個(gè)結(jié)點(diǎn)所需要移動(dòng)結(jié)點(diǎn)的平均次數(shù)為（n-1/2）。對(duì)一個(gè)線性表分別進(jìn)行遍歷和逆置運(yùn)算，其最好的時(shí)間復(fù)雜度量級(jí)均為（0（n）。4. 線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)代表一個(gè)（數(shù)據(jù)元素）。若線性表中最常用的操作是取第i個(gè)元素和查找該元素的前驅(qū)，則采用的存儲(chǔ)方式最能節(jié)省時(shí)間的是（順序表）。若最常用的操作是插入和刪除第i個(gè)元素，則采用的存儲(chǔ)方式最能節(jié)省時(shí)間的是（單鏈表）。5. 在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除操作過(guò)程不同，需要修改（頭指針）。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（便于操作），無(wú)論鏈表是否為空。使（頭指針）均

19、不為空。對(duì)于雙向鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共有（4個(gè)），單鏈表為（2個(gè)）。6. 如果以鏈棧為存儲(chǔ)結(jié)構(gòu)，則出棧操作時(shí)（必須判別?？眨?，與順序棧相比，鏈棧有一個(gè)明顯的優(yōu)勢(shì)是（不易出現(xiàn)棧滿(mǎn)）。7. 循環(huán)隊(duì)列采用數(shù)組data1.n來(lái)存儲(chǔ)元素的值，并用front和rear分別作為其頭尾指針。為區(qū)分隊(duì)列的滿(mǎn)和空，約定：隊(duì)中能夠存放的元素個(gè)數(shù)最大為n-l，也即至少有一個(gè)元素空間不用，則在任意時(shí)刻，至少可以知道一個(gè)空的元素的下標(biāo)是（front）;入隊(duì)時(shí)，可用語(yǔ)句（rear=rear+1%n）求出新元素在數(shù)組data中的下標(biāo)。&已知棧的輸入序列為1,2,3.，n,輸出序列為a1,a2

20、,，an,a2=n的輸出序列共有（n-1）種輸出序列。9. 稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，它們是用（哈希表、三元組和十字鏈表）。對(duì)矩陣壓縮存儲(chǔ)是為了（節(jié)省空間）。10. 將下三角矩陣Al.8,1.8的下三角部分逐行地存儲(chǔ)到起始地址為1000的內(nèi)存單元中，已知每個(gè)元素占4個(gè)單元，則A7,5的地址為（1100）。11. 已知數(shù)組A1.10,1.10為對(duì)稱(chēng)矩陣，其中每個(gè)元素占5個(gè)單元?，F(xiàn)將其下三角部分按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A5,6對(duì)應(yīng)的地址為（1095）。12.兩個(gè)串相等的充要條件是，兩個(gè)串的（長(zhǎng)度）相等，且其所對(duì)應(yīng)各個(gè)位置的（字符）也相等。13.取出廣義

21、表A=（x,（a,b,c,d）中原子C的函數(shù)是（head（tail（tail（head（tail（head（A）。14.在有n個(gè)結(jié)點(diǎn)的二又鏈表中，值為非空的鏈域的個(gè)數(shù)為（n-1）。在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中，總結(jié)點(diǎn)數(shù)是（2n-1）。在樹(shù)形結(jié)構(gòu)中，根結(jié)點(diǎn)數(shù)只有（1個(gè)），其余每個(gè)結(jié)點(diǎn)有且僅有一個(gè)元素（前驅(qū)）結(jié)點(diǎn)。15.一棵二叉樹(shù)L的高度為h，所有結(jié)點(diǎn)的度或?yàn)?,或?yàn)?,則這棵二叉樹(shù)最少的結(jié)點(diǎn)數(shù)為（2h-1）。已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少是（99）。將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的左孩

22、子編號(hào)為（98）。有64個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（7）。16拓?fù)渑判蛑荒苡糜冢ㄓ邢驘o(wú)環(huán)圖）。連通圖是指圖中任意兩個(gè)頂點(diǎn)之間（都連通的無(wú)向圖）。一個(gè)有n個(gè)頂點(diǎn)的無(wú)向連通圖，它所包含的連通分量個(gè)數(shù)最多為（1）個(gè)。任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（有一棵或多棵）。若含有n個(gè)頂點(diǎn)的圖形成一個(gè)環(huán)，則它有（n）棵生成樹(shù)。17. 求圖的最小生成樹(shù)有兩種算法，（prim（普里姆）算法適合于求稠密圖的最小生成樹(shù)，（kruskal（克魯斯卡爾）算法適合于求稀疏圖的最小生成樹(shù)。設(shè)圖G用鄰接表存儲(chǔ)，則拓?fù)渑判虻臅r(shí)間復(fù)雜度為（0（n+e）。18. 在一棵三叉樹(shù)中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)

23、數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（6）。19.中序表達(dá)式A*（B+C）/（D-E+F）的后序表達(dá)式是（ABC+*DE-F+/）。20.有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中（第i列1的元素之和）。具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為（45）個(gè)，具有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖G邊的總數(shù)至少有（n）條。21 .從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為（插入排序）。對(duì)于關(guān)鍵字序列（12,13,11,18,60,15,7,18,25,100），用篩選法建堆，則開(kāi)始結(jié)點(diǎn)的鍵值必須為（60）。22 .在有序表Al.20中，采用二分

24、查找算法查找元素值等于A12的元素，所比較過(guò)的元素的下標(biāo)依次為（10,15,12）,查找元素值等于5的元素，所比較過(guò)的元素個(gè)數(shù)為（5）個(gè)。分別采用堆排序、快速排序、插入排序和歸并排序算法對(duì)初始狀態(tài)為遞增序列的表按遞增順序排序，最省時(shí)間的是（插入排序）算法，最費(fèi)時(shí)問(wèn)的是（快速排序）算法。直接選擇排序算法所執(zhí)行的元素交換次數(shù)最多為（n-1）次，最好情況下所作的交換元素的次數(shù)為（0）次。在堆排序，希爾排序，快速排序，歸并排序算法中，占用輔助空間最多的是（歸并排序）。二分查找法要求查找表中各元素的關(guān)鍵字的值得排列必須是（遞增或遞減或有序）。23. 若一個(gè)待散列存儲(chǔ)的線性表長(zhǎng)度為n,用于散列的散列表長(zhǎng)度

25、為m,則m應(yīng)（小于等于）n,裝填因子公式為（n/m）。散列表的平均查找長(zhǎng)度（與處理沖突方法有關(guān)而與表的長(zhǎng)度有關(guān)）。24. 在平衡二叉樹(shù)上刪除一個(gè)結(jié)點(diǎn)后可以通過(guò)旋轉(zhuǎn)使其平衡，最壞情況下需旋轉(zhuǎn)（O（log2n）次。25. 貪心算法的基本思想是，逐步構(gòu)造最優(yōu)解，每步都按照一定的標(biāo)準(zhǔn)，稱(chēng)為（貪心）準(zhǔn)則，做出決策。0/1背包問(wèn)題的三種貪心準(zhǔn)則中，相對(duì)較優(yōu)的是（價(jià)值密度）貪心準(zhǔn)則。分治法與（遞歸）技術(shù)緊密結(jié)合。與分治法不同的是，動(dòng)態(tài)規(guī)劃是（自底向上或自下而上）、逐級(jí)求解子問(wèn)題。分枝定界的搜索策略與（廣度優(yōu)先）類(lèi)似，而回溯方法則采用（深度優(yōu)先）搜索策略。26. 對(duì)于單鏈表、單循環(huán)鏈表和雙向鏈表，若僅僅知道一

26、個(gè)指向鏈表中某結(jié)點(diǎn)的指針p，能否將p所指的結(jié)點(diǎn)的數(shù)據(jù)元素與它的直接前趨（假設(shè)存在）交換？若不可以，說(shuō)明理由；若可以，寫(xiě)出主要算法。（1）單鏈表不能，單循環(huán)鏈表和雙向鏈表可以。（2）單循環(huán)鏈表q=p;while（q>next!=p）q=q>next;temp=p>data;p>data=q>data;q>data=temp;（3）雙向鏈表：q=p>prior;temp=q>data;q>data=p>data;p>data=temp;27. 設(shè)有三對(duì)角矩陣a1.n,1.n把非零元素按列存儲(chǔ)在向量b1.3*n-2中，使得bk=ai,

27、j。求：用i,j表示k的下標(biāo)變換公式（k=2*（j-1）+i）用k表示i,j的下標(biāo)變換公式（j=（kDIV3）+1i=k-2*（j-1）28. 內(nèi)存中一片連續(xù)空間（不妨設(shè)地址從1到m）,提供給兩個(gè)棧S1和S2使用，怎樣分配這部分存儲(chǔ)空間，使得對(duì)任意一個(gè)棧，僅當(dāng)這部分全滿(mǎn)時(shí)才發(fā)生上溢。（為了盡量利用空間，減少溢出的可能，可采用棧頂相向，棧底分設(shè)兩端的存儲(chǔ)方式，這樣，對(duì)任何一個(gè)棧，僅當(dāng)整個(gè)空間全滿(mǎn)時(shí)才會(huì)發(fā)生上溢。）29. 有一n個(gè)結(jié)點(diǎn)的樹(shù)，其中所有分支結(jié)點(diǎn)的度均為k，求該樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)。設(shè)no為葉子結(jié)點(diǎn)數(shù)，nk為度為k的結(jié)點(diǎn)數(shù)，n為結(jié)點(diǎn)總數(shù)（依題意：n=n°+n（1）n=knk+1（

28、2）綜合（1）和得：no=n-（n-1）/k30. 設(shè)有n個(gè)無(wú)序元素，按非遞減次序排序，但只想得到前面長(zhǎng)度為k的部分序列，其中n>>k,最好采用什么排序方法？為什么？如有這樣一個(gè)序列：59,11,26,34,17,91,25，得到的部分序列是11,17,25，對(duì)于該例使用所選擇的方法實(shí)現(xiàn)時(shí)，共執(zhí)行多少次比較？（1）采用堆排序最合適，因?yàn)楫?dāng)部分序列較小時(shí)，堆排序的時(shí)間復(fù)雜度近似為O（n）。（2）初始建堆：比較8次輸出11,第一次調(diào)整：比較4次輸出17第二次調(diào)整：比較2次輸出25,總共比較14次。31. 設(shè)二叉排序樹(shù)中關(guān)鍵字由1至1000的整數(shù)組成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下述關(guān)

29、鍵字序列哪一個(gè)不可能是在二叉排序樹(shù)中查到的序列？說(shuō)明原因。（1）51,250,501,390,320,340,382,363;（2）24,877,125,342,501,623,421,363;（1）是；不是。因?yàn)椴樵?xún)序列是：查421時(shí)，其623左、右兩個(gè)區(qū)間都不存在，查找失敗。）32. 在執(zhí)行某個(gè)排序算法過(guò)程中，出現(xiàn)了排序關(guān)鍵字朝著最終排序序列相反方向的移動(dòng)，從而認(rèn)為該算法是不穩(wěn)定的，這種說(shuō)法對(duì)么？為什么？（不正確。算法的穩(wěn)定性是考察最終排行的位置交換，與中間過(guò)程無(wú)關(guān)。如：對(duì)于整數(shù)序列（18,36,25）。按基數(shù)排序的LSD方法，第一趟排序后（25，36，18），第二趟排序后得到（18,25

30、，36），18雖向相反方向移動(dòng)，但不影響最終位置。）33. 將算術(shù)表達(dá)式（a+b）+c*（d+e）+f）*（g+h）轉(zhuǎn)化為二叉樹(shù)（二叉鏈表結(jié)構(gòu)）（略）34. 在線性結(jié)構(gòu)中，開(kāi)始結(jié)點(diǎn)沒(méi)有（前驅(qū)）結(jié)點(diǎn)，最后一個(gè)元素沒(méi)有（后繼）結(jié)點(diǎn)。35. 線性表的邏輯結(jié)構(gòu)是（線性結(jié)構(gòu)），其所含結(jié)點(diǎn)的個(gè)數(shù)稱(chēng)為線性表的（長(zhǎng)度）。36隊(duì)列的特性是（先入先出或后入后出），棧的特性是（后入先出或先入后出）。37.數(shù)組Al.10,1.10的每個(gè)元素占5個(gè)單元，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A5,6的地址為（1270）。38 .若某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)

31、的總結(jié)點(diǎn)數(shù)是（69）。39 .樹(shù)t的存儲(chǔ)結(jié)構(gòu)為二叉鏈表bt，樹(shù)t中的一個(gè)葉子結(jié)點(diǎn)在bt中滿(mǎn)足條件（bt->lchild<>nulI&&bt->rchild<>nuII;40.求圖的最小生成樹(shù)有兩種算法，（prim（普里姆）算法適合于求稠密圖的最小生成樹(shù)。41.在索引順序表上實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長(zhǎng)度不僅與表的（長(zhǎng)度）有關(guān)，而且與每一塊中的元素（長(zhǎng)度）有關(guān)。42. 分枝定界的搜索策略與（廣度優(yōu)先）類(lèi)似，而回溯方法則采用（深度優(yōu)先）搜索策略。43. 0/1背包問(wèn)題的三種貪婪準(zhǔn)則中，相對(duì)較優(yōu)的是（價(jià)值密度）貪婪準(zhǔn)則。三、應(yīng)用題

32、1. 有一個(gè)二叉樹(shù)按層次順序存放在一維數(shù)組中，如下圖所示：試求：（1）該樹(shù)的后序遍歷序列。（C,E,B,D,A）（2）畫(huà)出該樹(shù)的后序線索樹(shù)。（略）1234567891011ACBED2. 按順序輸入下列頂點(diǎn)對(duì)：（1,2）、（1,6）、（2,6）、（1,4）、（6,4）、（1,3）、（3,4）、（6,5）、（4,5）、（1,5）、（3,5）,（1）畫(huà)出相應(yīng)的鄰接表。（2）寫(xiě)出在鄰接表上，從頂點(diǎn)3開(kāi)始（表下標(biāo)從0開(kāi)始）的DFS序列和DFS生成樹(shù)。（1）鄰接表VIf3IT1|f0|A(2)DFS序列2-0-1-5-3-43. 設(shè)一哈希表長(zhǎng)為13，采用線性探測(cè)法解決沖突，哈希函數(shù)H(key)=key%

33、13,(1) 畫(huà)出在空表中依次插入關(guān)鍵字25，20，36，15，41，52，29，72，67后的哈希表。(2) 求在等概率情況下，查找成功和查找不成功的平均查找長(zhǎng)度。(1)100101102103104105106107108109110111112521541296720723625(2)平均查找長(zhǎng)度查找成功的平均查找長(zhǎng)度=(5*1+3*2+1*4)/9=1.6查找不成功的平均查找長(zhǎng)度=(2+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/134. 對(duì)下面的關(guān)鍵字集(30，15，21,40，25，26，36，37)，若查找表的裝填因子為0.8，采用線性探測(cè)再散列解決沖突：(1)

34、設(shè)計(jì)哈希函數(shù)；(2)畫(huà)出哈希表；(1)表長(zhǎng)：m=n/a=8/0.8=10哈希函數(shù)：H(key)=key%7(2)哈希表01234567892115303625402637建立一棵平衡二叉排序樹(shù)的過(guò)程，并寫(xiě)出調(diào)整5.寫(xiě)出對(duì)關(guān)鍵字序列503,087,512,061,908,124,897,275,653,426平衡時(shí)的旋轉(zhuǎn)類(lèi)型。RL>”.087897061124、512908、503、087512061124908-、897"6.7.8.唇087897061124512908275、653426已知一棵二叉樹(shù)的先序序列和中序序列分別為：(略)假設(shè)通信電文使用的字符集為a,b,c,d

35、,e,f,g和010。(1) 畫(huà)出此哈夫曼樹(shù)(略)(2) 若這些字符在電文中出現(xiàn)的頻度分別為路徑長(zhǎng)度WPL=2.53已知有一個(gè)10個(gè)頂點(diǎn)的連通圖，頂點(diǎn)編號(hào)為(3,9)，(3，10)，(5,7)，(6,7)，(7，成樹(shù)。(略)對(duì)下面的關(guān)鍵字集35,15,21,99,25,26,36,37,01,18寫(xiě)出快速排序的每趟結(jié)果和最終結(jié)果。(略)3y-*ay2A/-的操作步驟。(可用X代表掃描改字符串過(guò)RR50308/275061124426653897/512908、abdgicefhj及bgidaecfjh，畫(huà)出該的二叉樹(shù)的后序線索二叉樹(shù)。字符的哈夫曼編碼依次為：0110，10，110，111，00

36、，01113、35、13、15、20、5、9，求哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度。(帶權(quán)至8)，(8，9)，試求：畫(huà)出該連通圖及以頂點(diǎn)為根的深度優(yōu)先生10，其邊的關(guān)系集合表示為(1,2)(1,3)，(1，8)，(2,4)，9.10有字符串次序?yàn)?*-y-a/yA2，利用棧，給出將次序改為程中順序取一個(gè)字符進(jìn)棧的操作，用為BCA的操作步驟為XXSXSS。(略)11.設(shè)有一個(gè)由正整數(shù)組成的無(wú)序單鏈表，閱讀下面的算法，指出該算法的功能，并在“”后面加上必要的注釋。voidF1(Linklist&L)S代表從棧中取出一個(gè)字符加入到新字符串尾的出棧操作。例如，ABC變p=Lfnext;pre=p;/pre

37、為最小結(jié)點(diǎn)指針while(p)if(pfdata<prefdata;pre=p;p=pfnext;/(1)/whileprintf(prefdata);/(2)if(prefnext&&prefdata%2!=0)/(3)temp=prefdata;prefdata=prefnextfdata;prefnextfdata=temp;/if/F1算法功能：找出最小值結(jié)點(diǎn)，且打印該數(shù)值。若該數(shù)值是奇數(shù)且有后繼，則與后繼結(jié)點(diǎn)的數(shù)值交換。(1)查找最小值結(jié)點(diǎn)；(2) 輸出最小值結(jié)點(diǎn)；(3) 若該數(shù)值是奇數(shù)且有后繼，則與后繼結(jié)點(diǎn)的數(shù)值交換。12. 已知二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，L

38、inkList和BiTree為已定義的指針類(lèi)型，ListNode為已定義的結(jié)點(diǎn)類(lèi)型,閱讀下面算法并回答：LinkListL=Null;p;voidF2(BiTreeT)if(T)F2(Tflchild);if(!Tflchild)&&(!Tfchild)p=(ListNode*)malloc(sizeof(ListNode);pfdata=Tfdata;pfnext=L;L=p;/ifF2(Tfrchild);/if/F2(1) 說(shuō)明該算法的功能；(2) 對(duì)于一棵有8個(gè)結(jié)點(diǎn)的完全二叉數(shù)(假設(shè)結(jié)點(diǎn)順序?yàn)锳、BC、DE、F、GH,畫(huà)出執(zhí)行上述算法后建立的結(jié)構(gòu)。(1)按中序遍歷二叉樹(shù)

39、，逆序建立以葉子結(jié)點(diǎn)為鏈表結(jié)點(diǎn)、以L為頭指針的無(wú)頭結(jié)點(diǎn)的單鏈表。(2)(略)四、算法分析與設(shè)計(jì)題1設(shè)有一個(gè)由正整數(shù)組成的無(wú)序單鏈表，閱讀下面的算法，指出該算法的功能，并在“/”后面加上必要的注釋。voidF1(Linklist&L)p=Lfnext;pre=p;/pre為最小結(jié)點(diǎn)指針while(p)if(pfdata<prefdata;pre=p;p=pfnext;/(1)查找最小值結(jié)點(diǎn)/whileprintf(prefdata);/(2)輸出最小值結(jié)點(diǎn)if(prefnext&&prefdata%2=0)/(3)刪除其后繼結(jié)點(diǎn)p=prefnext,prefnext

40、=pfnext;free(p);/if/F1算法功能：找出最小值結(jié)點(diǎn)，打印該數(shù)值。若該值是偶數(shù)且有后繼，則將其后繼結(jié)點(diǎn)刪除。2. 設(shè)有n個(gè)大小不等的數(shù)據(jù)組(n個(gè)數(shù)據(jù)組中數(shù)據(jù)的總數(shù)為m),順序存放在空間區(qū)D內(nèi)，每個(gè)數(shù)據(jù)占一個(gè)存儲(chǔ)單元。數(shù)據(jù)組的首地址由數(shù)組S給出，閱讀下面的算法，指出該算法的功能，并在“/”后面加上必要的注釋。voidF1(sqlist&L,inti,ElemTypex)if(i>=1&&i<=L.length)/(1)插入到D區(qū)for(j=0,p=L.elem0;j<=m;j+)p+;/(2)求D區(qū)空閑空間首地址if(i=L.length

41、)*p=x;(3)插入到第n個(gè)數(shù)組elsefor(q=L.elemi;p>=q;-p)*(p+1)=*p;*p=x;/插入xfor(q=&L.elemi,p=&L.elemLength-1;p>=q;q+)(*q)+;/elsem+;/if/F1算法功能：將數(shù)據(jù)x插入到D區(qū)，插入后D和S關(guān)系不變。3設(shè)有一個(gè)正整數(shù)序列組成的非遞減有序單鏈表，閱讀下面的算法，指出該算法的功能，并在“/后面加上必要的注釋。voidF1(LinklistL;int,x)p=Ltnext;q=p;/p為工作指針pre=L;Ltnext=NULL;./q指最小元素while(P&&am

42、p;Ptdata<x)(1)比x小的數(shù)遞減r=pTnext;ptnext=Ltnext;Ltnext=p;p=r;/(2)置逆/whileqtnext=p;pre=q;/(3)重新鏈接/F1算法功能：在單鏈表中將比正整數(shù)x小的數(shù)按遞減次序排列。4. 假設(shè)一個(gè)僅包含二元運(yùn)算符的算術(shù)表達(dá)式以二叉鏈表形式存儲(chǔ)在二叉樹(shù)T中，閱讀下面的算法，指出該算法的功能，并在“”后面加上必要的注釋。intF1(BiTrecT)if(!T)return0;if(!Ttlchild&&!Ttrchild)/(1)判斷是否為葉子結(jié)點(diǎn)return(Ttdata);Lv=F1(Ttlchild);Rv=

43、F1(Ttrchild);switch(Ttdata)/(2)運(yùn)算case'+':V=Lv+Rv;break;case'-':V=Lv-Rv;break;case'*':V=Lv*Rv;break;case'/':V=lv/Rv;break;/switchreturnV;/(3)返回結(jié)果/F1算法功能：后序遍歷二叉樹(shù)，求算術(shù)表達(dá)式的值。5. 在有向圖G中，如果r到G的每個(gè)結(jié)點(diǎn)都有路徑可達(dá)，則稱(chēng)結(jié)點(diǎn)r為G的根結(jié)點(diǎn)，下面算法的功能是判斷有向圖G是否有根，若有，則打印出所有根結(jié)點(diǎn)的值。請(qǐng)?zhí)羁昭a(bǔ)全算法，并在“/”后面給以注釋。voidF2

44、(ALGraphG)/利用深度優(yōu)先搜索，判斷有向圖G是否有根結(jié)點(diǎn)。intvisitedmaxsige,count;/count為記錄結(jié)構(gòu)的頂點(diǎn)數(shù)。for(v=0;v<G.vexnum;v+)for(v=0;v<G.vexnum;v+)(1)_;初始化頂點(diǎn)數(shù)組count=O;DFS(G,v);if(count=(2)_)判斷是否為根printf(G.verv.data);/F2voidDFS(ALGraphG,intv)/從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖Gvisitedv=1;count+;for(p=G.verticesv.firstarc;p;p=pnextarc)w=pta

45、djvex;if(!visitedw)(3)_;/深度優(yōu)先搜索/DFS(1)visitedv=0;(2)G.vexnum(3)DFS(G,w);6下面算法的功能是實(shí)現(xiàn)單鏈表中的簡(jiǎn)單選擇排序，其中L為鏈表的頭結(jié)點(diǎn)指針，請(qǐng)?zhí)羁昭a(bǔ)全算法，并在“/”后面給以注釋。voidF2(LinkList&L)/用單鏈表實(shí)現(xiàn)簡(jiǎn)單選擇排序p=L>next;/初始化，p為工作指針while(p)min=p;(1)_;/q為插入指針，min為當(dāng)前最小指針while(2)/一趟選擇排序if(q>data<min>data)min=p;q=q>next;/while(q)if(3)/_

46、交換temp=p>data;p>data=min>data;min>data=temp;/ifp=p>next;/while(p)/F2(1)q=p>next;(2)q或q!=null(3)min7設(shè)計(jì)算法DeleteX的功能是：刪除單鏈表L中值為x的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)。(設(shè)L是帶頭結(jié)點(diǎn)的單鏈表的頭指針，并為已知的LinkList類(lèi)型voidDeleteX(LinkList&L)/刪除單鏈表中的直接前驅(qū)結(jié)點(diǎn)p=L>next;/初始化，p為工作指針while(p&&p>next>data!=x)/q為前驅(qū)結(jié)點(diǎn)指針q=p

47、;p=p>next;/whileif(p)/刪除q>next=p>next;free(p);/if/DeleteX8 Internet的域名系統(tǒng)是一個(gè)典型的層次結(jié)構(gòu)，可用樹(shù)形結(jié)構(gòu)表示。每一個(gè)域名服務(wù)器提供的區(qū)域信息恰好是以該結(jié)點(diǎn)為根的子樹(shù)中的全部的IP地址。設(shè)計(jì)算法以孩子-兄弟鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)搜索所有www域名的IP地址。voidOutpath(CSTreeT,Stack&S)/搜索IP地址while(T)Push(S,T>data)if(!T>firstchild&&T>data=”www)visitstack(S);/輸

48、出一條路徑elseOutpath(T>firstchild，&S)/遞歸遍歷左子樹(shù)Pop(S,e);T=T>nextsibiling;/遍歷右子樹(shù)/while/Outpath9 設(shè)計(jì)算法實(shí)現(xiàn)以逆鄰接表為存儲(chǔ)結(jié)構(gòu)的有向圖的拓?fù)渑判?要求給出逆鄰接表的存儲(chǔ)結(jié)構(gòu)定義)。(1) 存儲(chǔ)結(jié)構(gòu)定義頂點(diǎn)結(jié)構(gòu)表結(jié)點(diǎn)結(jié)構(gòu)(2) 算法設(shè)計(jì)vexdatafirstinadjvexinfofirstarcinttoposort(ALGraphG,inttpv)/以逆鄰接表為存儲(chǔ)結(jié)構(gòu)的有向圖的拓?fù)渑判騮op=0;for(i=0;i<G.vexnum;i+)for(p=G.adjlisti.fir

49、stedge;p;pfindoutdegree(G,outdegree);/對(duì)各頂點(diǎn)求出度tnext)outdegreeptadjvex+;InitStack(&S);/for(i=0;i<G.Vexnum;i+)if(outdegreei=0)Push(&S,i);/初始化棧出度為零的頂點(diǎn)入棧while(!Stack(S)Pop(&S,i);printf(G.adjlisti.vextex);tpvtop+=i;for(p=G.adjlisti.firstedge;p;ptnext)j=ptadjvex;outdegreej-;if(!outdegreej)Pu

50、sh(&S,j);/出度為零的頂點(diǎn)入棧/for/whileif(top<G.vexnum)return0;/無(wú)環(huán)else/輸出頂點(diǎn)拓?fù)渑判蛐蛄衒or(i=0;j=top-1;i<G.vexnum/2;i+,j-)/temp=tpvi;tpvi=tpvj;tpvj=temp;置逆輸出/forreturn1;/else/toposort10.已知深度為h的二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)存放在數(shù)組B1.2h-1中，設(shè)計(jì)一個(gè)遞歸算法,鏈表結(jié)構(gòu)。voidCreateTree(intB2h,intj,BiTreet)/創(chuàng)建t樹(shù)的二叉鏈表結(jié)構(gòu)，j為數(shù)組下標(biāo)，初值為1t=(BiTree)malloc(sizeof(BiTNode);t>data=Bj;/創(chuàng)建根結(jié)點(diǎn)if(2*j>2h)t>Lchild=null;/無(wú)左子樹(shù)else/遞歸創(chuàng)建左子樹(shù)t>Lchild=CreateTree(B,2*j,t>Lchild);if(2*j+1>2h)t>Rchild=null;/無(wú)右子樹(shù)else/遞歸創(chuàng)建右子樹(shù)t>Rchild=CreateTree(B,2*j+1,t>Rchild);/CreateTree11假設(shè)哈希函數(shù)為