2018年_2018數(shù)據(jù)結(jié)構(gòu)?？茝土曎Y料

1、數(shù)據(jù)結(jié)構(gòu)課程復習資料一、填空題：1. 設需要對5個不同的記錄關(guān)鍵字進行排序，則至少需要比較J次，至多需要比較10次。2. 設二叉排序樹的高度為h,則在該樹中查找關(guān)鍵字key最多需要比較n次。3. 設在長度為20的有序表中進行二分查找，則比較一次查找成功的結(jié)點數(shù)有工個，比較兩次查找成功有結(jié)點數(shù)有2個。4. 數(shù)據(jù)結(jié)構(gòu)從虱輯上劃分為三種基本類型：線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖型結(jié)構(gòu)。5. 在一個具有n個頂點的無向完全圖中，包含有n(n-1)/2條邊，在一個具有n個頂點的有向完全圖中，包含有n(n-1)條邊。6. 向一棵B列插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度增加。7. 在堆排序的過

2、程中，對任一分支結(jié)點進行篩運算的時間復雜度為O(log2n),整個堆排序過程的時間復雜度為O(nlog2n)。8. 在快速排序、堆排序、歸并排序中，歸并排序是穩(wěn)定的。9. 在有n個葉子結(jié)點的哈夫曼樹中，總結(jié)點數(shù)是n-1。10. 一棵樹T采用二叉鏈表存儲，如果樹T中某結(jié)點為葉子結(jié)點，則在二叉鏈表BT中所對應的結(jié)點一定左,右子樹空。11. 已知數(shù)組A1010為對稱矩陣，其中每個元素占5個單元?，F(xiàn)將其下三角部分按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A5,6對應的地址是1225。12. 在有n個結(jié)點的無向圖中，其邊數(shù)最多為n(n-1)/2。13. 取出廣義表A=(x,(a,b,

3、c,d)中原子x的函數(shù)是head(A)。14. 對矩陣采用壓縮存儲是為了節(jié)省空間。15. 帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是L->next=L->prior或L->next=L。16. 設線性表中元素的類型是實型，其首地址為1024,則線性表中第6個元素的存儲位置是1044。17. 對于順序存儲的棧，因為棧的空間是有限的，在進行入棧(插入)運算時，可能發(fā)生棧的上溢,在進行出棧(刪除)運算時,可能發(fā)生棧的下溢。18. 在雙向鏈表中，每個結(jié)點有兩個指針域，一個指向前驅(qū)結(jié)點，另一個指向后繼結(jié)點由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。19. 折半查找的存儲結(jié)構(gòu)僅限于順

4、序存儲結(jié)構(gòu)，且是有序白對于一個順序存儲的線性表，在表頭插入元素的時間復雜度為On),在表尾插入元素的時間復雜度為O(1)Q在稀疏距陣所對應的三元組線形表中，每個三元組元素按行號為主序,列號為輔序的次序排列。20. 中綴表達示3+X*(2.4/5-6)所對應的后綴表達示為3x2.45/6*+。21. 在一棵高度為h的3叉樹中，最多含有(3h-1)/2結(jié)點。22. 分析下面算法(程序段)，給出最大語句頻度愁，該算法的時間復雜度是O(n3)。for(i=0;i<n;i+)for(j=0;j<n;j+)Aij=0；23. 空串是零個字符的串，其長度等于零。_一個圖的鄰接矩陣表示法是唯一的,

5、而鄰接表表示法是不唯一的。24. 在一個單鏈表中p所指結(jié)點之前插入一個s(值為e)所指結(jié)點時，可執(zhí)行如下操作：25. q=head;while(q->next!=p)q=q->next;s=newNode;s->data=e;q->next=sj/填空s->next=p;/填空在一個單鏈表中刪除p所指結(jié)點的后繼結(jié)點時，應執(zhí)行以下操作：26. q=p->next;p->next=q->next;/填空deleteq;/填空兩個串相等的充分必要條件是兩個串的長度相等且對應位置的字符相同。27. 二維數(shù)組A1020采用列序為主方式存儲，每個元素占一個存

6、儲單元并且A00的存儲地址是200,則A612的地址是200+(6*20+12)=326。28. 二維數(shù)組A10.205.10采用行序為主方式存儲，每個元素占4個存儲單元，并且A105的存儲地址是1000,則A189的地址是1000+(18-10)*6+(9-5)*4=1208。29. 求下列廣義表操作的結(jié)果：30. GetTailGetHead(a,b),(c,d);(b)GetTailGetHeadGetTail(a,b),(c,d)(d)已知一個有向圖的鄰接矩陣表示，計算第i個結(jié)點的入度的方法是求矩陣第i列非零元素之和。31. 已知一個圖的鄰接矩陣表示，刪除所有從第i個結(jié)點出發(fā)的邊的方法

7、是將矩陣第i行全部置為零。32. 在利用快速排序方法對一組記錄(54,38,96,23,15,72,60,45,83)進行快速排序時，遞歸調(diào)用而使用的棧所能達到的最大深度為2,共需遞歸調(diào)用的次數(shù)為4,其中第二次遞歸調(diào)用是對(23,38,15)組記錄進行快速排序。33. 在堆排序，快速排序和歸并排序中，若只從存儲空間考慮，則應首先選取堆排序方法，其次選取快速排序方法,最后選取歸并排序方法;若只從排序結(jié)果的穩(wěn)定性考慮，則應選取歸并排序方法；若只從石情況下排序最快考慮，則應選取快速排序方法;若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮,則應選取堆排序方法。34. 稱算法的時間復雜度為O(f(n)，其含

8、義是指算法的執(zhí)行時間和f(n)的數(shù)量級相同。35. 在一個長度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點的時間復雜度為O(n)。36. 假設為循環(huán)隊列分配的向量空間為Q20,若隊列的長度和隊頭指針值分別為13和17,則當前尾指針的值為0。37. 對于棧只能在棧頂插入和刪除元素。38. 設有一個順序棧S,元素sl,s2,s3,s4,s5,s6依次進棧，如果6個元素的出棧順序為s2,s3,s4,s6,s5,sl,貝U順序棧的容量至少應為3_。39. 數(shù)據(jù)結(jié)構(gòu)一般包括三個方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算。n/2個結(jié)點。44. 在包含n個結(jié)點的順序表上做等概率插入運算，平均要移動4

9、5. 隊列的特性是先進先出。46. 已知二叉樹中葉子數(shù)為30,僅有一個孩子的結(jié)點數(shù)為20,則總結(jié)點數(shù)為47. 蟲序遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列(選填“先序”48. n個節(jié)點的連通圖至少有49. 在堆排序和快速排序中，50. 帶有一個頭結(jié)點的單鏈表51. 設一組初始關(guān)鍵字序列為10,13,27,76,65,97,3879o、“中序”或“后序”)n-1條邊。如果從平均情況下排序的速度最快的角度來考慮，head為空的條件是(假設指針域的名稱為next)head->next=NULL。(38,65,97,76,13,27,10),則第3趟簡單選擇排序后的結(jié)果為應最好選擇快速

10、排序排序。52. 在拓撲排序中，拓撲序列的第一個頂點必定是53. 數(shù)據(jù)的邏輯結(jié)構(gòu)分為兩大類，它們是線性結(jié)構(gòu)和54. 在單鏈表中(假設結(jié)點指針域名稱為入度為零的頂點。非線性結(jié)構(gòu)。next),刪除指針P所指結(jié)點的后繼結(jié)點的語句是p->next=p->next->next。55. 已知循環(huán)隊列用數(shù)組datan存儲元素值，用front,rear分別作為頭尾指針，則當前元素個數(shù)為(rear-front+n)%n。56. 若n為主串長，m為子串長，則串的樸素匹配算法最壞的情況下需要比較字符的總次數(shù)(n-m+1)xm廣義表(a),(b),j,(d)的表尾是(b),j,(d)。57. 已知二

11、叉樹有61個葉子節(jié)點，且僅有一個孩子的節(jié)點數(shù)為45,貝U總節(jié)點數(shù)為166。59.解決計算機與打印機之間速度不匹配問題，須要設置一個數(shù)據(jù)緩沖區(qū)，應是一個隊列結(jié)構(gòu)。、單項選擇題:隊列的特點是A.先進后出B.先進先出有n個記錄的文件，如關(guān)鍵字位數(shù)為A.nB.dC.rC.d,基數(shù)為D.n-d3. 在二叉樹結(jié)點的先序序列、中序序列和后序序列中，A.都不相同B.C.先序和中序相同，而與后序不同4. 設有198個初始歸并段，如采用A.12B.13C.14B任意位置進出D.r,則基數(shù)排序共要進行(前面都不正確)遍分配與收集。D.所有葉子結(jié)點的先后順序完全相同中序和后序相同，而與先序不同K-路平衡歸并三遍完成排

12、序，則K值最大為D.15下面關(guān)于廣義表的敘述中，不正確的是A.廣義表可以是一個多層次的結(jié)構(gòu)C.廣義表可以被其他廣義表所共享B.D.6. 設二叉樹根結(jié)點的層次為0,一棵深度(高度)c個結(jié)點，下列關(guān)系式不正確的是A.f>=cB.c>fC.f=2從L=(apple,pear),(orange,banana)A.head(tail(L)C.tail(head(tail(L)7. 下列文件的物理結(jié)構(gòu)中，A.順序結(jié)構(gòu)B.B廣義表至少有一個元素廣義表可以是一個遞歸表為k的滿二叉樹和同樣深度完全二叉樹各有Bk+1-aD.c>s中，取出banana元素的表達式為B.head(head(tail

13、(L)D.head(tail(head(tail(L)不利于文件長度動態(tài)增長的文件物理結(jié)構(gòu)是鏈接結(jié)構(gòu)C.索引結(jié)構(gòu)Ck-1D個結(jié)點和D.HashD.A結(jié)構(gòu)9. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素可由A.實體B.域C.數(shù)據(jù)項對于有n個頂點的有向圖，由弗洛伊德(FloyD算法求每一對頂之間的最短路徑的時間復雜度是A.O(1)B.O(n)C.O(n)D.O(n對n個記錄的文件進行快速排序，所需要的輔助存儲空間為A.O(1)B.O哈夫曼樹中一定不存在A.度為0的結(jié)點B.度為1的結(jié)點下述哪一條是順序存儲方式的優(yōu)點？A.存儲密度大B.C.獲取符合某種條件的元素方便D.(log2n)C.OC.(n)B度為2的結(jié)點D.OD

14、.A插入和刪除運算方便查找運算速度快字段3)B(n2)帶權(quán)的結(jié)點14. 有一個二維數(shù)組Amn，假設A00存放位置在600(10),A33存放位置在678(10)占一個空間，問A23(10)存放在什么位置？(腳注(10)表示用10進制表示，m>315. A.658B.648C.633D.653下列關(guān)于二叉樹遍歷的敘述中，正確的是AA. 若一個葉子是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序遍歷最后一個結(jié)點若一個結(jié)點是某二叉樹的前序遍歷最后一個結(jié)點，則它必是該二叉樹的中序遍歷的最后一個結(jié)點每個元素D若一個結(jié)點是某二叉樹的中序遍歷的最后一個結(jié)點，則它必是該二叉樹的前序最后一個結(jié)點

15、若一個樹葉是某二叉樹的前序最后一個結(jié)點，則它必是該二叉樹的中序遍歷最后一個結(jié)點第K層二叉樹的結(jié)點總數(shù)最多為A.2k-1B.2k+1C.2K-1線性表進行二分法查找，其前提條件是A.線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序AD.2k-1B. 線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序線性表以順序方式存儲，并且按關(guān)鍵碼值排好序線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序18.n個記錄進行堆排序，所需要的輔助存儲空間為B.O(n)C.O(1)34,77,25,64,49,20,14)0的元素有()個。19. B.2C.3A.O(1og2n)線性表(7,20. 散列地址為A.1D.

16、4D.O(n進行散列存儲時，若選用DC2)H(Q=K%7作為散列函數(shù)，則下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是21. A.數(shù)組是不同類型值的集合C.樹是一種線性結(jié)構(gòu)以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？A.有向圖B.隊列D.B.22. B線索二叉樹D.B在一個單鏈表HL中，若要在當前由指針p指向的結(jié)點后面插入一個由語句序列。D23. A.p=q;p->next=q;B.p->next=q;q->next=p;C.p->next=q->next;p=q;D.q->next=p->next;p->next=q;()不是隊列的基本運算。A.在隊列第i個元素之后插

17、入一個元素C.判斷一個隊列是否為空D.24. 若已知一個棧的入棧序列是1,2,3,，為A.i棧的特點是A.先進先出設有兩個串A.連接C.D.)<B.n,遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉用一維數(shù)組存儲一棵完全二叉樹是有效的存儲方法27. 樹q指向的結(jié)點，則執(zhí)行如下()A從隊頭刪除一個元素讀取隊頭元素的值p1,p2,其輸出序列為Cp3,，pn,若p1=n，貝UpiB.n=iC.n-i+1(B),隊列的特點是(AB.先進后出p和q,求q在p中首次出現(xiàn)的位置的運算稱作B.模式匹配C.求子串的長度為3個字節(jié)，行下標二維數(shù)組A中，每個元素Aij28. 址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)

18、組按列存放時，元素A.SA+141B.SA+180C.SA+222某二叉樹的前序遍歷結(jié)點訪問順序是abdgcefh29. 的結(jié)點訪問順序是A.bdgcefhaB.gdbecfha在一非空二叉樹的中序遍歷序列中，30. A.只有右子樹上的所有結(jié)點C.只有左子樹上的部分結(jié)點具有6個頂點的無向圖至少應有(A.5B.6C.7二分查找和二叉排序樹的時間性能A.相同B.不相同采用二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)在待排序的兀素序列基本有序的前提下，效率最高的排序方法是A.插入排序B.選擇排序C.31. 下述幾種排

19、序方法中，要求內(nèi)存量最大的是A.插入排序B.選擇排序C.C.bdgaechf根結(jié)點的右邊B.D.)條邊才能確保TED.8不確定B求串長D.i從0到7,列下標jA47的起始地址為D.SA+225,中序遍歷的結(jié)點訪問順序是DD.gdbehfca只有右子樹上的部分結(jié)點只有左子樹上的所有結(jié)點旦一個連通圖?？焖倥判蚩焖倥判駾.DD.從0到9,從首地Bdgbaechf,則其后序遍歷A歸并排序歸并排序35. 設有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作BA.連接B.模式匹配C.求子串D.求串長二維數(shù)組A中，每個元素Aij的長度為3個字節(jié)，行下標i從0到7,列下標j從0到9,從首地36. 址SA開始連

20、續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時，元素A47的起始地址為BA.SA+141B.SA+180C.SA+222某二叉樹的前序遍歷結(jié)點訪問順序是abdgcefh37. 的結(jié)點訪問順序是A.bdgcefhaB.gdbecfha在一非空二叉樹的中序遍歷序列中，38. A.只有右子樹上的所有結(jié)點C.只有左子樹上的部分結(jié)點具有6個頂點的無向圖至少應有(A.5B.6C.7二分查找和二叉排序樹的時間性能A.相同B.不相同C.bdgaechf根結(jié)點的右邊B.D.D.SA+225,中序遍歷的結(jié)點訪問順序是DD.gdbehfcadgbaechf,則其后序遍歷A只有右子樹上的部分結(jié)點只有左子樹上的所有結(jié)點)條邊才能確

21、保是一個連通圖。D.8C.采用二分查找方法查找長度為n的線性表時，A.O(n2)B.O(nlog2n)C.O(n)B可能相同D.每個元素的平均查找長度為42. D.O(log2n)在待排序的兀素序列基本有序的前提下，效率最高的排序方法是A.插入排序B.選擇排序C.快速排序下面的序列中(43. A.1,2,8,5,3,9,10,4C.9,8,7,6,4,8,2,1對一個算法的評價，A.健壯性和可讀性在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，44. A.p->next=HL->next;HL->next=pB.p->next=HL;HL=pC.p-&g

22、t;next=HL;p=HLD.HL=p;p->next=HL對線性表，在下列哪種情況下應當采用鏈表表示？A.經(jīng)常需要隨機地存取元素B.45. C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變一個棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是A.231B.321C.312D.123每一趟都能選出一個元素放在其最終位置上，并且不穩(wěn)定的排序算法是A.冒泡排序B.簡單選擇排序C.希爾排序D.46. 采用開放定址法處理散列表的沖突時，其平均查找長度A.低于鏈接法處理沖突C.與鏈接法處理沖突相同若需要利用形參直接訪問實參時，A.值B.函數(shù)在稀疏矩陣的帶行指針向量的鏈接存儲中

23、，A.行號B.列號快速排序在最壞情況下的時間復雜度為A.O(log2n)B.O(nlog2n)B.選擇排序)是大頂堆。B.1,5,10,6,7,8,9,2D.9,8,7,6,5,4,3,1不包括如下()方面的內(nèi)容。B.并行性C.正確性D.D.不確定BA歸并排序B時空復雜度則執(zhí)行B經(jīng)常需要進行插入和刪除操作B.高于鏈接法處理沖突D.高于二分查找應將形參變量說明為()參數(shù)。C.指針D.每個單鏈表中的結(jié)點都具有相同的C.元素值D.DB:直接插入排序BD引用A非零元素個數(shù)C.O(n)從二叉搜索樹中查找一個元素時，其時間復雜度大致為A.O(n)B.O(1)設一個有序的單鏈表中有D.O(n2n)D.O(n

24、C2)C.O(logn個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復雜度為DA.O(log2n)B.O(1)C.O(n2)D.O(n)55.設一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為Nd,度數(shù)為1的結(jié)點數(shù)為N,，度數(shù)為m的結(jié)點數(shù)為Nm則Nd=A.Ni+N2+NmB.l+N2+2N+3N4+(m-1)NmC.N2+2N3+3N+(m-1)NmD.2Nl+3N2+(m+1)Nm二維數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從0到7,列下標j從0到開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，數(shù)組元素A74的起始地址為A.SA+141B.SA+144C.SA+222D.SA+225如果

25、某二叉樹的前根次序遍歷結(jié)果為stuwv,中序遍歷為uwtvs,那么該二叉樹的后序為C.wuvtsD.wutsv)個結(jié)點。C.31D.109,從首地址CSAA.uwvtsB.vwuts深度為5的二叉樹至多有(A.16B.32在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的(A.1/2B.1采用順序查找方法查找長度為A.nB.n/2采用二分查找方法查找長度為A.O(n2)B.O(nlog)倍。62. C.2D.4n的線性表時，每個元素的平均查找長度為C.(n+1)/2D.(n-1)/2n的線性表時，每個元素的平均查找長度為D.O(log2n)C.O(n)下述幾種排序方法中，要求內(nèi)存量最大的是A.插

26、入排序B.選擇排序C.排序方法中，從未排序序列中依次取出元素與已排序序列稱為快速排序(初始時為空)2n)64. 入已排序序列的正確位置上的方法，A.希爾排序?qū)τ陂L度為值除以9。A.20D.中的元素進行比較，將其放D.歸并排序B.起泡排序C.9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為(插入排序選擇排序B.18C.25D.22在有向圖中每個頂點的度等于該頂點的A.入度B.出度在基于排序碼比較的排序算法中，(A.起泡排序B.希爾排序C入度與出度之和D.C.算法的最壞情況下的時間復雜度不高于C.入度與出度之差O(n10g2n)?？焖倥判駼不清楚歸并排序D.)的查找速度。相同

27、D.67. 當a的值較小時，散列存儲通常比其他存儲方式具有(A.較慢設有一個含200個表項的散列表，用線性探查法解決沖突，按關(guān)鍵碼查詢時找到一個表項的平均探查次數(shù)不超過1.5,則散列表項應能夠至少容納(68. (設搜索成功的平均搜索長度為A.400B.526堆是一個鍵值序列(k1,k2,.k69. A.ki<k2i<k2i+1C.kiVk2i且kivk2i+1(2i+1<n)若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組A.操作的有限集合B.B.較快C.)個表項。a)/2,其中a為裝填因子)D.6761=1,2,.|_n/2_|,滿足Snl=(1+l/(1C.624n,對B.kD.kR),其中

28、(K,映象的有限集合71.下列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是i<k2i+1<k2ii<k2i或ki<k2i+1(2i+1<n)K是數(shù)據(jù)元素的有限集合，則R是K上C.類型的有限集合D.關(guān)系的有限集合C12345678101112A.ABEDC.ED72.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹A.其形態(tài)不一定相同，但平均查找長度相同C.其形態(tài)均相同，但平均查找長度不一定相同73.ISAM文件和VSA吸件的區(qū)別之一是A. 前者是索引順序文件，后者是索引非順序文件B. 前者只能進行順序存取，74. 前者建立靜態(tài)索引結(jié)構(gòu)，前者的存儲介質(zhì)是磁盤，下列描述中正確的是A. 線性表

29、的邏輯順序與存儲順序總是一致的B. 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本運算：插入、刪除和查找75. 數(shù)據(jù)結(jié)構(gòu)實質(zhì)上包括邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的內(nèi)容選擇合適的數(shù)據(jù)結(jié)構(gòu)是解決應用問題的關(guān)鍵步驟下面程序段的時間復雜度是I=s=0While(s<n)(I+；s+=I;A.O(1)如果只想得到A.起泡排序B.D.后者只能進行隨機存取后者建立動態(tài)索引結(jié)構(gòu)后者的存儲介質(zhì)不是磁盤B.O(n)C.O(log2n)1024個元素組成的序列中的前B.快速排序C.77. 算法分析的目的是A.辨別數(shù)據(jù)結(jié)構(gòu)的合理性C.研究算法中輸入與輸出的關(guān)系B.D.其形態(tài)不一定相同，平均查找長度也不一定相同其形態(tài)均相同，平均查找長度也

30、都相同CD.O(nA2)5個最小元素，堆排序B那么用(D.方法最快。A直接選擇排序評價算法的效率鑒別算法的可讀性78. 在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是A.插入B.刪除C.定位若進棧序列為1,2,3,4,5,6,且進棧和出?？梢源┎暹M行，A.3,C.1,設串C排序2,2,sl=6,1,4,5B.55,3,4,6D.3"DataStructureswithJava",s2=D.則可能出現(xiàn)的出棧序列為2,3,1,6,it,6,4,4,2,則子串定位函數(shù)index(s1,s2)的值為A81. A.15B.16C.17D.18一個順序存儲的線性表的第一個元素

31、的存儲地址是址是A.108從一個具有個結(jié)點。A.n100,每個元素的長度為4,則第4個元素的存儲地BB.112C.116D.120n個結(jié)點的單鏈表中查找其值等于x的結(jié)點，在查找成功的情況下，平均需要比較（CD.（n-1）/2各葉子之間的相對次序關(guān)系C.B.n/2C.(n+1)/2在任意一棵二叉樹的前序序列和后序序列中，A.不一定相同B.互為逆序高度為5的二叉樹至多有結(jié)點數(shù)為A.63B.32C.24都不相同D.85. AD都相同D.64若用鄰接矩陣表示一個有向圖，則其中每一列包含的A.圖中每個頂點的出度B.C.圖中弧的條數(shù)D.86. 圖的鄰接矩陣表示法一般不太適用于表示A.無向圖B.有向圖C.8

32、7. 循環(huán)隊列是空隊列的條件是A.Q->rear=Q->frontC.Q->rear=0設有一廣義表E=（a,b,（c,d）A.2B.3某二叉樹的前序遍歷序列為1的個數(shù)為圖中每個頂點的入度圖中連通分量的數(shù)目AD.稀疏圖稠密圖BB.(Q->rear+1)%maxsize=Q->frontD.Q->front=0)，其長度為C.4D.590. ABDEFC中序遍歷序列為DBEFAC則后序遍歷序列為A.DFEBCAB.DBECFAC.BDAECFD.DBEFCA下列（）不是利用查找表中數(shù)據(jù)元素的關(guān)系進行查找的方法。91. A.有序表的查找B.二叉排序樹的查找C.平

33、衡二叉樹下述幾種排序方法中，要求內(nèi)存量最大的是A.插入排序B.快速排序C.歸并排序在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（A.1/2B.1C.2D.4在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行92. A.p->next=HL->next;HL->next=pB.p->next=HL;HL=pC.p->next=HL;p=HLD.HL=p;p->next=HL對線性表，在下列哪種情況下應當采用鏈表表示？B93. A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中

34、元素的個數(shù)不變一個棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是A.231B.321C.312D.123每一趟都能選出一個元素放在其最終位置上，并且不穩(wěn)定的排序算法是A.冒泡排序B.簡單選擇排序C.希爾排序采用開放定址法處理散列表的沖突時，其平均查找長度94. A.低于鏈接法處理沖突C.與鏈接法處理沖突相同若需要利用形參直接訪問實參時，A.值B.函數(shù)D.BD.D.B.高于鏈接法處理沖突D.高于二分查找應將形參變量說明為（）參數(shù)。C.指針D.99. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的A.行號B.列號C.元素值D.C散列查找選擇排序）倍。B直接插入排序

35、BD引用A非零元素個數(shù)100. 快速排序在最壞情況下的時間復雜度為A.O(log2n)B.O(nlog2n)C.O(n)從二叉搜索樹中查找一個元素時，其時間復雜度大致為A.O(n)B.O(1)設一個有序的單鏈表中有時間復雜度為A.O(log2n)B.O(1)設一棵m叉樹中度數(shù)為D.O(n2n)CD.O(n2)2)C.O(logn個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的DC.O(n2)D.O(n)0的結(jié)點數(shù)為N0,度數(shù)為1的結(jié)點數(shù)為Nl,，度數(shù)為m的結(jié)點數(shù)為Nm則N0=104. A.Ni+N2+NmB.l+N2+2N+3N+(m-1)NmC.N2+2N3+3M+(m-1)

36、NmD.2Nl+3N2+(m+1)Nm設有序表中有1000個元素，則用二分查找查找元素X最多需要比較()次。BA.25B.10C.7D.1設連通圖G中的邊集E=(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c),則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為BA.abedfcB.acfebdC.aebdfcD.aedfcb拓撲排序運算只能用于CA.帶權(quán)有向圖B.連通無向圖C.有向無環(huán)圖D.無向圖在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是BA.O(1)B.O(n)C.O(n2)D.O(nlogn)三、計算與算法應用題：1. 已知

37、一個圖的頂點集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;按照普里姆算法從頂點1出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。2. 一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。先序序列：_BFICEHG_中序序列：d_kfiaEJC_后序序列：KFBHJGA3. 畫出下列樹對應的二叉樹，并寫出其先根遍歷序列:4.將關(guān)鍵字序列為54,29,

38、37,86,71,91,8,31,44,26進行歸并排序，寫出各趟詳細過程。5. 試列出如下圖中全部可能的拓撲排序序列。6. 設某通信系統(tǒng)使用A,B,C,D,E,F,G,H八個字符，他們出現(xiàn)的概率w=5,29,7,8,14,23,3,11,試構(gòu)造對應的哈夫曼樹(請按左子樹根結(jié)點的權(quán)小于右子樹樹根結(jié)點的權(quán)的次序構(gòu)造)。7. 給定表(119,14,22,1,66,21,83,27,56,13,10)，請按表中元素的順序構(gòu)造一棵平衡二叉樹,并求其在等概率情況下查找成功的平均長度。8. 已知一個有向圖的頂點集V和邊集G分別為：V=a,b,c,d,e,f,g,hE=<a,b>,<a,c

39、>,<b,f>,<c,d>,<c,e>,<d,a>,<d,f>,<d,g>,<e,g>,<f,h>假定該圖采用鄰接矩陣表示，則分別寫出從頂點a出發(fā)進行深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷得到的頂點序列。9. 設散列表的長度為13,散列函數(shù)為H(h)=k%13,給定的關(guān)鍵碼序列為19,14,23,01,68,20,84,27。試畫出用線性探查法解決沖突時所構(gòu)成的散列表。012345678910111210. 對7個關(guān)鍵字進行快速排序，在最好的情況下僅需進行10次關(guān)鍵字的比較。(1) 假設關(guān)鍵字集合

40、為1,2,3,4,5,6,7，試舉出能達到上述結(jié)果的初始關(guān)鍵字序列;(2) 對所舉序列進行快速排序，寫出排序過程。3,1,4,6,9,8,5,7時每一插入后AVL樹的形態(tài)。若做了某種11. 如圖所示二叉樹，回答下列問題。12. <1)其申序髯歷序列(2>(3>其后序AVL樹中刪去根結(jié)點后的結(jié)果。,40,80,95,24),寫出對其進行快畫出在一個初始為空的AVL樹中依次插入旋轉(zhuǎn)，說明旋轉(zhuǎn)的類型。然后，給出在這棵插入后得到的已知一組記錄的排序碼為(46,79,56,38速排序的每一次劃分結(jié)果。14. 一個線性表為B=(12,23,45,57,20HT0.12，散列函數(shù)為H(ke

41、y)=key%13算等概率情況下查找成功的平均查找長度。,03,78,31,15,36),設散列表為并用線性探查法解決沖突，請畫出散列表，"丁15. 已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECDFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ,試寫出這棵二叉樹的后序遍歷結(jié)果。16. 假定對線性表(38,25,74,52,48,65,36)進行散列存儲，采用H(K)=K%9作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則計算對應的平均查找長度。17. 已知哈希表地址空間為0.8，哈希函數(shù)為H(key)=key%7,采用線性探測再散列處理沖突，將數(shù)據(jù)序列100,20,21,35,

42、3,78,99,45依次存入此哈希表中，列出插入時的比較次數(shù)，并求出在等概率下的平均查找長度。18. 試畫出下面帶權(quán)無向圖的一棵最小生成樹。19. 已知關(guān)鍵字序列為：03,87,12,61,98,70,61*,97,27,53,42,56,77,請采用希爾(Shell)排序法對該序列作非遞減排序.按5,3,1分組，寫出下列標明的趟的結(jié)果。初始03,87,12,61,98,70,97,27,53,42,56,77第一趟第二趟每三趟四、閱讀下列算法，分析它的作用：1.intAA(LNode*HL,ElemTypex)intn=0;LNode*p=HL;while(p!=NULL)if(p->

43、data=x)n+;p=p->next;returnn;對于結(jié)點類型為LNode的單鏈表，以上算法的功能為：2.intAA(LNode*HL,ElemTypex)intn=0;LNode*p=HL;while(p!=NULL)(if(p->data=x)n+;p=p->next;returnn;對于結(jié)點類型為LNode的單鏈表，以上算法的功能為:-1,請寫出輸出結(jié)果。假定從鍵盤上輸入一批整數(shù)，依次為：786345309134include<iostream.h>include<stdlib.h>constintstackmaxsize=30;typed

44、efintelemtype;structstack(elemtypestackstackmaxsize;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é)果為：。3. 讀下述算法，說明本算法完成什么功能。template<calsstype>voidBinTree&

45、lt;Type>unknown(BinTreeNode<Type>*t)(BinTreeNode<Type>*p=t,*temp;if(p!=NULL)(temp=prleftchild;prleftchild=prrightchild;prightchild=temp;unknown(pleftchild);undnown(prightchild);該算法的功能是:5.閱讀下列算法，說明該算法的作用。voidSqstack:push(ElemTypex)(if(top=MAX-1)cout<<"n滿！"；else(top+;ele

46、mtop=x;/pushI/類定義1constintMAX=20;ItypedefcharElemType;IclassSqstack1(private:-ElemTypeelemMAX;iinttop;1public:ISqstack()top=0;IElemTypepop();1voidpush(ElemTypex);i1;6.有如下圖所示單鏈表，經(jīng)過圖示。voidLink:output()p=Head->next;while(p!=NULL)cout<<"np=p->next;/outputoutput）算法處理后，單鏈表發(fā)生了什么變化？畫出處理后的單鏈

47、表data="<<p->data;7.讀下述算法，說明本算法完成什么功能。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);/inordern1structSnode/II構(gòu)ichardata;；Snode*next;:;IclassLink/I,.iprivate:iSnode*Head;1public:ILink()Head=NULL;ivo

48、idcreat();1voidoutput();I:/結(jié)點結(jié)鏈表類8.voidAD(Lnode*&HL)Insert(HL,30);Insert(HL,50);Delete(HL,26);Delete(HL,55);10.閱讀下列算法，說明該算法的作用。ElemTtypeSqstack:pop【(ElemTypex;if(top=0)x=-999;else(x=elemtop;top-;returnx;/pop單鏈表發(fā)生了什么變化？畫出處理后的單鏈表圖示。IstructSnode/結(jié)點結(jié)1構(gòu)Ichardata;!ISnode*next;1:;'IclassLink/鏈表類！I1

49、private:(；Snode*Head;ipublic:1_Link()Head=NULL;I"1e一A_|voidcreat();ivoidreverse();11voidoutput();5,針對下圖所示二叉樹列算法，一輸出是什么U假定調(diào)用該算法時以HL為表頭指針的單鏈表中的內(nèi)容為(15,26,48,55),則調(diào)用返回后該單鏈表中的內(nèi)容為：voidAI(adjmatrrixGA,inti,intn)(cout<<i<<''vistedi=true;for(intj=0;j<n;j+)if(GaIj!=0&&GAij!

50、=MaxValue&&!visitedj)AI(GA,j,n);該算法的功能為：。I/類定義IconstintMAX=20;1typedefcharElemType;iclassSqstacki(private:；ElemTypeelemMAX;Iinttop;ipublic:11. -Sqstack()top=0;IElemTypepop();Ivoidpush(ElemTypex);:/.;|;有如下圖所示單鏈表，經(jīng)過reverse算法處理后，voidLink:reverse()Snode*p,*q;p=Head->next;Head->next=NULL;wh

51、ile(p!=NULL)q=p->next;p->next=Head->next;Head>next=p;p=q;/reverseead-IEc二3J下列函數(shù)是二叉排序樹的什么算法？如果K值為比較幾次得到結(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;elsep=q;q=q->rch;if(flag=0

52、)cout<<"n查找失敗，無此結(jié)點！n”;elsecout<<"n查找成功，找到："<<q->key<<endl;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;對于結(jié)點類型為LNode的單鏈表，以上算法的功能為：voidBB(Lis

53、t&L)inti=0;while(i<L.size)intj=i+1;while(j<L.size)if(L.listj=L.list)for(intk=j+1;k<L.size;k+)L.listk-1=L.listk;L.size-;elsej+;i+;以上算法的功能為：voidCC(BTreeNode*&BST)ElemTypea6=45,23,78,35,77,25;BST=NULLfor(inti=0,i<6;i+)Insert(BST,ai);調(diào)用該算法后，生成的二叉搜索數(shù)的中序序列為：voidDD()ElemTypeA=1,3,5,7,9,

54、2,4,6,8,10,B10;TwoMerge(A,B,0,4,9);for(inti=0;i<10;i+)cout<<Bi<<”"cout<<endl;調(diào)用該算法后，輸出結(jié)果為：template<classType>intSeqList<Type>:Insert(Type&x,inti)if(i<0|i>last+1|last=MaxSize-1)return0;elseLast+;for(intj=last;j<i;j-)dataj=dataj-1;datai=x;return1;對于結(jié)點

55、類型為SeqList的順序表，以上算法的功能為：四、算法設計題：1. 編寫復制一棵二叉樹的非遞歸算法。2. 假設二叉樹中每個結(jié)點所含數(shù)據(jù)元素均為單字母，以二叉鏈表為存儲結(jié)構(gòu)，試編寫算法按如下圖所示的樹狀顯示二叉樹。3. 試用遞歸法編寫輸出從n個數(shù)中挑選k個進行排列所得序列的算法。4. 編寫一個算法，交換單鏈表中p所指向的結(jié)點和其后續(xù)結(jié)點的兩個結(jié)點，Head指向該鏈表的表頭，P指向鏈表中的某一結(jié)點。Head5. 試寫一遞歸算法，從大到小輸出二叉排序樹中所有的關(guān)鍵字值小于key的元素值。6. 已知帶頭結(jié)點的單鏈表是一個遞增有序表，試寫一算法，刪除表中值大于min且小于max的結(jié)點（若表中有這樣的結(jié)

56、點)，同時釋放被刪除結(jié)點的空間，這里min和max是兩個給定的參數(shù)。7.已知深度為h的二叉樹以一維數(shù)組BT(1:2h-1)作為其存儲結(jié)構(gòu)。請寫一算法，求該二叉樹中葉結(jié)點的個數(shù)。8. 編寫在以BST為樹根指針的二叉搜索樹上進行查找值為item的結(jié)點的非遞歸算法，若查找item帶回整個結(jié)點的值并返回true，否則返回false。9. boolFind(BtreeNode*BST,ElemType&item)設A=(a1,.,am)和B=(b1,.,bn)均為順序表，A'和B'分別為A和B中除去最大共同前綴后的子表。若A'=B'=空表，則A=B若A'=空表，而B'乒空表，或者兩者均不為空表，且A'的首元小于B'的首元，則A<B;否則A>B試寫一個比較A,B大小的算法。10. 已知單鏈表a和b的元素按值遞增有序排列，編寫算法歸并a和b得到新的單鏈表c,c的元素按值遞減有序。11. 編寫遞歸算法，對于二叉樹中每一個元素值為x的