數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)提綱3套不帶答案

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)提綱選擇題1.數(shù)據(jù)結(jié)構(gòu)是指（）。A.數(shù)據(jù)元素的組織形式B.數(shù)據(jù)類型C.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)D.數(shù)據(jù)定義2. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的,稱之為（）A. 存儲(chǔ)結(jié)構(gòu)C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3. 設(shè)語句X+的時(shí)間是單位時(shí)間for（i=1; i二n; i+）for（j=i; j 二n; j+）B. 邏輯結(jié)構(gòu)D.順序存儲(chǔ)結(jié)構(gòu)則以下語句的時(shí)間復(fù)雜度為（）x+;D.O( n3)A. O(1)B.O( n2)C.0(n)4. 計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（）。A. 數(shù)據(jù) B. 數(shù)據(jù)元素 C.數(shù)據(jù)項(xiàng) D.數(shù)據(jù)庫5. 在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1=in ext二s; s-p

2、rior=p;p-n ext-prior=s; s-n ext=p-n ext;B. s-prior=p; s-next=p-next;p-n ext=s; p- next-prior二s;C. p-n ext=s; p-n ext-prior=s;s-prior=p; s-n ext=p-n ext;D. s-prior=p; s-next=p-next;p- next-prior二s; p-n ext=s;9. 設(shè)單鏈表中指針p指向結(jié)點(diǎn)m,若要?jiǎng)h除m之后的結(jié)點(diǎn)(若存在)，則需修改指針的操作為。A. p-next=p-next-next;B. p=p-next;C. p=p-next-nex

3、t;D. p-next=p;10. 在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素(0 inext=p-next; p-next=sB. q-next=s; s-next=pC. p-next=s-next; s-next=pD. p-next=s; s-next=q12. 在順序表中，只要知道 ，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A. 基地址B.結(jié)點(diǎn)大小C.向量大小D.基地址和結(jié)點(diǎn)大小13. 設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)?A, B, C, D, E,下列是不可能的出棧序列 。A. A, B, C, D, EB. B, C, D, E, AC. E, A, B, C, DD. E, D, C, B

4、, A14. 向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行。A. hs-next=s;B. s-next=hs; hs=s;C. s-next=hs-next;hs-next=s;D. s-next=hs; hs=hs-next;15. 在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為 。A. rear n= = frontB.(front+l ) n= = rearC. rear n -1= = front D . (rear+l) n= = front16. 在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別

5、為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為 。A. rear n= = frontB. front+l= rearC. rear= = frontD. (rear+l) n= front17. 在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為 。A. front=front-nextB . rear=rear-next18. 設(shè)二維數(shù)組A0m-10n-1按行優(yōu)先順序存儲(chǔ)在內(nèi)存中，第一個(gè)元素的地址為p,每個(gè)元素占k個(gè)字節(jié)，則元素 可的地址為（）A.p +i* n+j-1*kB.p+(i-1)* n+j-1*kC.p+(j-1)* n+i-1*kD.p+j* n+

6、i-1*k19. 若數(shù)組A0m0n按列優(yōu)先順序存儲(chǔ)，則 印地址為（）。A.LOC(ac0)+m+iB. LOC(a0)+ n+iC. L OC(c00)+(j-1)* n+i-1D. LOC(a00)+(j-1)*m+i-1(j2)( j1)(j22)( j1)(j22)( j1)(j22)( j1)A. (j-1)*n-+i-1*dB. (j-1)* n-+i*dC. (j-1)*n-+i+1*d+i-2*dD. (j-1)*n-A.無窮大 B. 3C.2D.20. 若下三角矩陣Anxn,按列順序壓縮存儲(chǔ)在數(shù)組Sa0（n+1）n/2中,則非零元素丙的地址為（）。（設(shè)每個(gè)元素占d個(gè)字節(jié)）221

7、. 設(shè)有廣義表D=（a,b,D），其長(zhǎng)度為（），深度為（）22.廣義表 A=(x,(a,B),(x,(a,B),y),則運(yùn)算 head(head(tail(A)的結(jié)果為（A ）。A.xB.(a,B)C.(x,(a,B)D.A23.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（）。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D. 散列和十字鏈表24. 一個(gè)廣義表的表頭總是一個(gè)（）25. 一個(gè)廣義表的表尾總是一個(gè)（ ）。A.廣義表B.元素C.空表 D. 元素或廣義表526. 在一棵度為 3的樹中，度為 3的結(jié)點(diǎn)數(shù)為 2個(gè)，度為 2 的結(jié)點(diǎn)數(shù)為 1 個(gè)，度為 1 的結(jié)點(diǎn)數(shù)為 2 個(gè)，則度為0

8、的結(jié)點(diǎn)數(shù)為（ ）個(gè)。27.個(gè)，A. 4B. 5C. 6D. 7假設(shè)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為則葉子結(jié)點(diǎn)數(shù)為（ ）個(gè)15，單分支結(jié)點(diǎn)數(shù)為 30A. 15B. 16C. 17D. 4728.假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（）A. 3B. 4C. 5D. 629.用順序存儲(chǔ)的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R仁n，結(jié)點(diǎn)Ri若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)（）A. R2i+1 B. R2i C. Ri/2D. R2i-130. 由權(quán)值分別為 3, 8, 6, 2, 5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶 權(quán)路徑長(zhǎng)度為（）。A. 24B. 48 C. 72 D. 5331.

9、 設(shè)n , m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（ ）。A. n在m右方B. n在m左方C. n是m的祖先D. n是m的子孫32. 如果F是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序就 是F中結(jié)點(diǎn)的（ ）。A. 中序B. 前序C. 后序D. 層次序33. 在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s,則所有頂點(diǎn)的入度數(shù)之和為 ()。A. sB. s-1C. s+1D. n34. 在一個(gè)具有 n 個(gè)頂點(diǎn)的有向圖中， 若所有頂點(diǎn)的出度數(shù)之和為 s，則所有頂點(diǎn)的度數(shù)之和為 () 。A. sB. s-1C. s+1D. 2s35. 在一個(gè)具有 n 個(gè)頂點(diǎn)的無向完

10、全圖中，所含的邊數(shù)為 ()。A. nB. n(n-1)C. n(n-1)/2 D. n(n+1)/236. 在一個(gè)具有 n 個(gè)頂點(diǎn)的有向完全圖中，所含的邊數(shù)為 ()。A. nB. n(n-1)C. n(n-1)/2 D. n(n+1)/237. 若一個(gè)圖中包含有 k 個(gè)連通分量，若要按照深度優(yōu)先搜索的方法訪問所有頂點(diǎn)，則必須調(diào)用 ()次深度優(yōu)先搜索遍歷的算法。A. k B. 1 C. k-1 D. k+138. 若要把 n 個(gè)頂點(diǎn)連接為一個(gè)連通圖，則至少需要 () 條邊。A. nB. n+1C. n-1D. 2n39. 在一個(gè)具有n 個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素(又稱為

11、有效元素)的個(gè)數(shù)為 ()。A. nB. n eC. eD. 2e40. 在一個(gè)具有n 個(gè)頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個(gè)數(shù)為( ) 。A. nB. n eC. eD. 2e41.在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接表中，保存頂點(diǎn)單鏈表的表頭指針向量的大小至少為 ( )A. n B. 2n C. e D. 2e42. 對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為k1，出度為k2,則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為 ()。A. k1B. k2C. k1-k2D. k1+k243. 若一個(gè)圖的邊集為 (A,B),(A,C),(B,D),(C,F),(D,E),(D,F) ，則從頂

12、 點(diǎn) A 開始對(duì) 該圖進(jìn) 行深度 優(yōu)先 搜索 ， 得到 的頂 點(diǎn)序 列可能 為 ( ) 。A. A,B,C,F,D,EB.A,C,F,D,E,BC. A,B,D,C,F,ED.A,B,D,F,E,C44. 若一個(gè)圖的邊集為 (A,B),(A,C),(B,D),(C,F),(D,E),(D,F) ，則從頂 點(diǎn) A 開始對(duì) 該圖進(jìn) 行廣度 優(yōu)先 搜索 ， 得到 的頂 點(diǎn)序 列可能 為 ( ) 。A. A,B,C,D,E,FB.A,B,C,F,D,EC. A,B,D,C,E,FD.A,C,B,F,D,E45. 若一個(gè)圖的邊集為 , ，則從 頂點(diǎn) 1 開始對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為(

13、 ) 。A. 1,2,5,4,3B. 1,2,3,4,5C. 1,2,5,3,4D. 1,4,3,2,546. 若一個(gè)圖的邊集為 , ，則從 頂點(diǎn) 1 開始對(duì)該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為。A. 1,2, 3,4,5B. 1,2,4,3,547. 由一個(gè)具有 n 個(gè)頂點(diǎn)的連通圖生成的最小生成樹中，具有 ( )條 邊。A. nB. n-1 C. n+1 D. 2 n48. 已知一個(gè)有向圖的邊集為 ,， 則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨?( )。A. a,b,c,d,e B. a,b,d,e,b C. a,c,b,e,d D. a,c,d,b,e749. 對(duì)具有 n 個(gè)元素的有序表采

14、用折半查找，則算法的時(shí)間復(fù)雜度為D. O(log 2n)A. O(n)B. O(n 2)C. O(1)50. 若查找每個(gè)元素的概率相等，則在長(zhǎng)度為 n 的順序表上查找任 元素的平均查找長(zhǎng)度為 ( ) 。A. n B. n+1C. (n-1)/2 D. (n+1)/251. 對(duì)于長(zhǎng)度為 9 的順序存儲(chǔ)的有序表，若采用折半查找，在等概率 情況下的平均查找長(zhǎng)度為 ( ) 的 9 分之一。A. 20B. 18 C. 25 D. 2252. 對(duì)具有 n 個(gè)元素的有序表采用折半查找，則算法的時(shí)間復(fù)雜度為( ) 。2A. O(n)B. O(n 2)C. O(1) D. O(log 2n)53. 在索引查找中

15、，若用于保存數(shù)據(jù)元素的主表的長(zhǎng)度為 144，它被 均分為 12 子表，每個(gè)子表的長(zhǎng)度均為 12，則索引查找的平均查找長(zhǎng) 度為 ( ) 。A. 13B. 24C. 12D. 7954. 從具有 n 個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，在平均情況下 的時(shí)間復(fù)雜度大致為 ( ) 。A. O(n) B. O(1) C. O(log 2n)D. O(n 2)55. 在一棵平衡二叉排序樹中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是( ) 。A. -1 1 B. -2 2 C. 1 2 D. 0 156. 若根據(jù)查找表 ( 23, 44, 36, 48, 52, 73, 64, 58) 建立哈希表，采用 h(K)=K

16、%7計(jì)算哈希地址，則哈希地址等于 3的元素個(gè)數(shù)()。A. 1B. 2 C. 3 D. 457. 若根據(jù)查找表建立長(zhǎng)度為 m的哈希表，采用線性探測(cè)法處理沖突, 假定對(duì)一個(gè)元素第一次計(jì)算的哈希地址為 d，則下一次的哈希地址為 ( ) 。A. dB. d+1 C. (d+1)/m D. (d+1)%m858. 在對(duì) n 個(gè)元素進(jìn)行冒泡排序的過程中，第一趟排序至多需要進(jìn)行 ( )對(duì)相鄰元素之間的交換。A. n B. n-1 C. n+1 D. n/259. 在對(duì) n 個(gè)元素進(jìn)行直接插入排序的過程中，算法的空間復(fù)雜度為 ( )。2A. O(1)B. O(log 2n) C. O(n 2)D. O(nlo

17、g 2n)60. 在對(duì) n 個(gè)元素進(jìn)行堆排序的過程中，時(shí)間復(fù)雜度為()。A. O(1)B. O(log 2n) C. O(n 2)D. O(nlog 2n)61. 假定一個(gè)初始堆為 (1, 5, 3, 9, 12, 7, 15, 10) ，要求從大到小排序， 則進(jìn)行第一趟堆排序后得到的結(jié)果為(C. 3, 7, 5, 9, 12, 10, 15, 1 D.3, 5, 7, 12, 9, 10, 15, 162. 若對(duì)n個(gè)元素進(jìn)行歸并排序，則進(jìn)行歸并的趟數(shù)為（）。A. nB. n-1C. n/2D. log 2n63. 若要對(duì)1000個(gè)元素排序，要求既快又穩(wěn)定，則最好采用（）方法。A.直接插入排序

18、B.歸并排序C.堆排序 D.快速排序64. 若要對(duì)1000個(gè)元素排序，要求既快又節(jié)省存儲(chǔ)空間，則最好采 用（）方法。A.直接插入排序B.歸并排序C.堆排序 D.快速排序65. 在平均情況下速度最快的排序方法為（）。A.簡(jiǎn)單選擇排序B. 歸并排序C. 堆排序D. 快速排序二，填空題1. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是和。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別3. 線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)二的,非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 。4. 一個(gè)算法的效率可分為 效率和效率。5. 線性結(jié)構(gòu)中元素之間存在 關(guān)系；樹型結(jié)構(gòu)中元素之間存在關(guān)系；圖型結(jié)構(gòu)中元素之間存在關(guān)系。6. 下面程序段的

19、時(shí)間復(fù)雜度是 。i=s=0; i+；s+=i;7. 下面程序段的時(shí)間復(fù)雜度是 O( log3n)。i=1;while(i 二n)i=i*3;8. 算法時(shí)間復(fù)雜度的分析通常有兩種方法，即 和的方法，通常我們對(duì)算法求時(shí)間復(fù)雜度時(shí)，米用后一種方法。-29. 在一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移個(gè)元素。10. 在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過_決定的；在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過決定的。11. 在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向 結(jié)點(diǎn)，另一個(gè)指向結(jié)點(diǎn)。12. 當(dāng)對(duì)一個(gè)線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用 存儲(chǔ)結(jié)構(gòu)

20、為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用 存儲(chǔ)結(jié)構(gòu)為宜。13. 線性表、棧和隊(duì)列都是 結(jié)構(gòu)，可以在線性表的任丄位置插入和刪除元素；對(duì)于棧只能在 位置插入和刪除元素；對(duì)于隊(duì)列只能在 位置插入元素和在 位置刪除元素。14. 設(shè)有一空棧，現(xiàn)有輸入序列1, 2, 3, 4, 5,經(jīng)過push, push,pop, push, pop, push, push后，輸出序列是。15. 無論對(duì)于順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來說，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相同為 。416. 對(duì)于一個(gè)二維數(shù)組Amn，若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素Aij相對(duì)于A00的地址為個(gè)元素位置。17. 一個(gè)廣義表為(a,(

21、a,b),d,e,(i,j),k)，則該廣義表的長(zhǎng)度為 18. 一個(gè)稀疏矩陣為0020300000150000為)深度為，則對(duì)應(yīng)的三元組線性表19. 已知廣義表A=(a,b,O,( d,e,f)，則運(yùn)算head(tail(tail(A)= 。20. 設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式以行序?yàn)橹餍虼鎯?chǔ)，a00為第一個(gè)元素，其存儲(chǔ)地址為0，每個(gè)元素占有1個(gè)存儲(chǔ)地址空間，則a$5的地址為。21. 已知廣義表Ls=(a,(b,c,d),e)，運(yùn)用head和tail函數(shù)取出Ls中的原子b的運(yùn)算是。22. 數(shù)組A110, -26, 28以行優(yōu)先的順序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是100,每個(gè)元素占

22、3個(gè)存儲(chǔ)長(zhǎng)度的存儲(chǔ)空間，則元素A5, 0, 7的存儲(chǔ)地址為。(5-1)*9*7+(0-2)*7+(7-2)*3+10023. 假定一棵樹的廣義表表示為 A (B ( E), C ( F (H, I, J),G), D),則該樹的度為 ,樹的深度為_,終端結(jié)點(diǎn)的個(gè)數(shù)為 _, 單分支結(jié)點(diǎn)的個(gè)數(shù)為，雙分支結(jié)點(diǎn)的個(gè)數(shù)為_，三分支結(jié)點(diǎn)的個(gè)數(shù)為 ,C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為，其孩子結(jié)點(diǎn)為和 結(jié)點(diǎn)。24. 對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵 完全 二叉樹時(shí)具有最小高度，即為 ，當(dāng)它為一棵單支樹具有 高度，即為。25. 由帶權(quán)為3, 9, 6, 2, 5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長(zhǎng)度為。26. 在

23、一棵二叉排序(搜索)樹上按 遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。27. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為個(gè)，其中個(gè)用于鏈接孩子結(jié)點(diǎn)，個(gè)空閑著。28. 在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為no，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，貝S no=。29. 一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，形態(tài)達(dá)到最大深度，形態(tài)達(dá)到最小深度。30. 線索鏈表中的rtag域值為時(shí)，表示該結(jié)點(diǎn)無右孩子，此時(shí)域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。31. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_ _倍32. 在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有 條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有 條邊。33

24、. 假定一個(gè)有向圖的頂點(diǎn)集為a, b, c, d, e, f，邊集為, , , , ,則出度為 0 的頂點(diǎn)個(gè)數(shù)為，入度為1的頂點(diǎn)個(gè)數(shù)為。34. 在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通所有頂點(diǎn)則至少需要條邊。35. 表示圖的兩種存儲(chǔ)結(jié)構(gòu)為 和。36. 若一個(gè)圖的頂點(diǎn)集為a,b,c,d,e,f，邊集為(a,b),(a,c),(b,c),(d,e)，則該圖含有個(gè)連通分量。37. 對(duì)于具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，在它們對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)的個(gè)數(shù)分別為 和。38. 在有向圖的鄰接表和逆鄰接表表示中，每個(gè)頂點(diǎn)鄰接表分別鏈接著該頂點(diǎn)的所有 和結(jié)點(diǎn)。39. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，

25、當(dāng)分別采用鄰接矩陣和鄰接表表示時(shí)，求任一頂點(diǎn)度數(shù)的時(shí)間復(fù)雜度分別為 和。40. 假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，則采用鄰接矩陣和鄰接表表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為 和。41. 圖的深度優(yōu)先搜索遍歷算法是一種遞歸算法，圖的 優(yōu)先搜索遍歷算法需要使用隊(duì)列。742. 對(duì)長(zhǎng)度為n的查找表進(jìn)行查找時(shí)，假定查找第i個(gè)元素的概 率為p,查找長(zhǎng)度(即在查找過程中依次同有關(guān)元素比較的總次數(shù))為Ci，則在查找成功情況下的平均查找長(zhǎng)度的計(jì)算公式為 。43. 以折半查找方法在一個(gè)查找表上進(jìn)行查找時(shí)，該查找表必須組織成存儲(chǔ)的表。44. 從有序表(12, 18, 30, 43, 56, 78, 82, 95)中分別折

26、半查找43和56元素時(shí)，其比較次數(shù)分別為和。45 .假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行折半查找，則對(duì)應(yīng)的判定樹高度為 6，最后一層的結(jié)點(diǎn)數(shù)為 。46. 假定在索引查找中，查找表長(zhǎng)度為n，每個(gè)子表的長(zhǎng)度相等，設(shè)為s,則進(jìn)行成功查找的平均查找長(zhǎng)度為 。47. 在索引查找中，假定查找表(即主表)的長(zhǎng)度為 96,被等分為8個(gè)子表，則進(jìn)行索引查找的平均查找長(zhǎng)度為 。48. 根據(jù)n個(gè)元素建立一棵二叉排序樹的時(shí)間復(fù)雜度大致為。49. 在一棵平衡二叉排序樹中，每個(gè)結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對(duì)值不超過。50. 假定對(duì)線性表(38, 25, 74, 52, 48)進(jìn)行哈希存儲(chǔ)，采用H(K)=K % 7作為哈

27、希函數(shù)，采用線性探測(cè)法處理沖突，則在建立哈希表的過程中，將會(huì)碰到 次存儲(chǔ)沖突。51. 對(duì)線性表(18, 25, 63, 50, 42, 32, 90)進(jìn)行哈希存儲(chǔ)時(shí)，若選用H(K)=K % 9作為哈希函數(shù)，則哈希地址為 0的元素有3個(gè)，哈希地址為5的元素有個(gè)。852. 每次從無序子表中取出一個(gè)元素，把它插入到有序子表中的適當(dāng)位置，此種排序方法叫做 排序；每次從無序子表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法 叫做排序。53. 每次直接或通過支點(diǎn)元素間接比較兩個(gè)元素， 若出現(xiàn)逆序排 列時(shí)就交換它們的位置，此種排序方法叫做 排序；每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序

28、方法叫做 排序。5 4.對(duì)n個(gè)記錄進(jìn)行冒泡排序時(shí)，最少的比較次數(shù)為 ，最少的趟數(shù)為。55假定一組記錄為（46,79,56,38,40,84，則利用堆排序方法建立 的初始小根堆為。56假定一組記錄為（46,79,56,38,40,84 ,（往后冒泡）在冒泡排序 的過程中進(jìn)行第一趟排序后的結(jié)果為 。57假定一組記錄為（46,79,56,38,40,80，對(duì)其進(jìn)行快速排序的第 一次劃分后的結(jié)果為。58假定一組記錄為（46,79,56,38,40,80,46,75,28,46，對(duì)其進(jìn)行歸并排序的過程中，第三趟歸并后的第2個(gè)子表為。59.在所有排序方法中，方法使數(shù)據(jù)的組織采用的是完全二叉樹的結(jié)構(gòu)。60.

29、 排序方法能夠每次從無序表中順序查找出一個(gè)最小值。三，算法設(shè)計(jì)與應(yīng)用題1, 設(shè)計(jì)將帶表頭的鏈表逆置算法。設(shè)單循環(huán)鏈表的頭指針為 head,類型為L(zhǎng)inkList。逆置時(shí)需將每 一個(gè)結(jié)點(diǎn)的指針域作以修改，使其原前趨結(jié)點(diǎn)成為后繼。如要更改q結(jié)點(diǎn)的指針域時(shí)，設(shè)s指向其原前趨結(jié)點(diǎn)，p指向其原后繼結(jié)點(diǎn)，則只需進(jìn)行q-next=s操作即可，算法描述如下：void inv ert(Li nkList*head)/逆置head指針?biāo)赶虻膯窝h(huán)鏈表lin klist *p, *q, *s;q=head;p=head-n ext;while （p!二head） 當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置 s=q;q=p;p=p-