數(shù)據(jù)結(jié)構(gòu)與算法試題庫(kù)與參考答案解析一、單選題（共40題，每題1分，共40分）1.兩個(gè)有相同鍵值的元素具有不同的散列地址A、有萬(wàn)分之一的可能會(huì)B、可能會(huì)C、一定會(huì)D、一定不會(huì)正確答案：B答案解析：在散列函數(shù)設(shè)計(jì)不合理或發(fā)生沖突處理不當(dāng)?shù)惹闆r下，兩個(gè)有相同鍵值的元素可能會(huì)具有不同的散列地址。比如散列函數(shù)的取值范圍有限，或者在處理沖突時(shí)采用的方法導(dǎo)致了這種情況出現(xiàn)。2.對(duì)任意給定的含n(n>2)個(gè)字符的有限集S，用二叉樹表示S的哈夫曼編碼集和定長(zhǎng)編碼集，分別得到二叉樹T1和T2。下列敘述中，正確的是：A、出現(xiàn)頻次不同的字符在T2中處于相同的層B、T1與T2的結(jié)點(diǎn)數(shù)相同C、T1的高度大于T2的高度D、出現(xiàn)頻次不同的字符在T1中處于不同的層正確答案：A答案解析：1.**分析選項(xiàng)A**：-哈夫曼編碼的二叉樹\(T1\)的結(jié)點(diǎn)數(shù)為\(2n-1\)，而定長(zhǎng)編碼的二叉樹\(T2\)的結(jié)點(diǎn)數(shù)為\(2^k\)（\(k\)使得\(2^k\geqn\)），一般情況下\(2n-1\neq2^k\)，所以選項(xiàng)A錯(cuò)誤。2.**分析選項(xiàng)B**：-哈夫曼樹\(T1\)是帶權(quán)路徑長(zhǎng)度最短的二叉樹，其高度不一定大于定長(zhǎng)編碼二叉樹\(T2\)的高度，所以選項(xiàng)B錯(cuò)誤。3.**分析選項(xiàng)C**：-哈夫曼樹中，權(quán)值大的結(jié)點(diǎn)離根近，權(quán)值小的結(jié)點(diǎn)離根遠(yuǎn)，但可能存在權(quán)值不同但在同一層的情況，所以選項(xiàng)C錯(cuò)誤。4.**分析選項(xiàng)D**：-定長(zhǎng)編碼的二叉樹是滿二叉樹（或完全二叉樹），在滿二叉樹（或完全二叉樹）中，所有葉子結(jié)點(diǎn)都在同一層，所以出現(xiàn)頻次不同的字符在\(T2\)中處于相同的層，選項(xiàng)D正確。3.對(duì)于給定的有權(quán)無(wú)向圖G，下列哪個(gè)說法是正確的？A、G的最小生成樹中，任意一對(duì)頂點(diǎn)間的路徑必是它們?cè)贕中的最短路徑B、設(shè)頂點(diǎn)V到W的最短路徑為P。若我們將G中每條邊的權(quán)重都加1，則P一定仍然是V到W的最短路徑C、單源最短路問題可以用O(∣E∣+∣V∣)的時(shí)間解決D、以上都不對(duì)正確答案：D答案解析：1.對(duì)于選項(xiàng)A：-最小生成樹中任意一對(duì)頂點(diǎn)間的路徑不一定是它們?cè)贕中的最短路徑。例如，在一個(gè)帶權(quán)無(wú)向圖中，最小生成樹的邊構(gòu)成的路徑可能會(huì)因?yàn)樽钚∩蓸涞臉?gòu)造方式而不是最短路徑。最小生成樹主要關(guān)注的是連接所有頂點(diǎn)且總權(quán)值最小，而不是路徑的最短性。2.對(duì)于選項(xiàng)B：-當(dāng)將G中每條邊的權(quán)重都加1時(shí)，原來(lái)頂點(diǎn)V到W的最短路徑P不一定仍然是最短路徑。因?yàn)樽疃搪窂绞腔谶叺臋?quán)重計(jì)算的，權(quán)重增加后，可能會(huì)有其他路徑成為更短的路徑。3.對(duì)于選項(xiàng)C：-單源最短路問題如果使用Dijkstra算法，時(shí)間復(fù)雜度是\(O((|V|+|E|)\log|V|)\)，只有使用一些特殊的數(shù)據(jù)結(jié)構(gòu)（如斐波那契堆）優(yōu)化后的Dijkstra算法時(shí)間復(fù)雜度才是\(O(|E|+|V|\log|V|)\)，而Bellman-Ford算法時(shí)間復(fù)雜度是\(O(|V||E|)\)，所以說單源最短路問題可以用\(O(|E|+|V|)\)的時(shí)間解決是錯(cuò)誤的。所以以上選項(xiàng)都不對(duì)，答案是D。4.將元素序列{18，23，11，20，2，7，27，33，42，15}按順序插入一個(gè)初始為空的、大小為11的散列表中。散列函數(shù)為：H(Key)=Key%11，采用線性探測(cè)法處理沖突。問：當(dāng)?shù)谝淮伟l(fā)現(xiàn)有沖突時(shí)，散列表的裝填因子大約是多少？A、0.73B、0.45C、0.27D、0.64正確答案：B答案解析：首先計(jì)算各元素的散列值：18%11=723%11=111%11=020%11=92%11=27%11=7（沖突）此時(shí)插入了6個(gè)元素，散列表大小為11，裝填因子=6/11≈0.545，大于0.45。所以答案選B。5.中位值結(jié)點(diǎn)在根結(jié)點(diǎn)或根的左子樹上A、2B、4C、3D、1正確答案：A6.將6、4、3、5、8、9順序插入初始為空的最大堆（大根堆）中，那么插入完成后堆頂?shù)脑貫椋篈、9B、6C、5D、3正確答案：A答案解析：首先，最大堆（大根堆）的特點(diǎn)是每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值。初始堆為空，插入6后，堆為[6]。插入4后，因?yàn)?小于6，所以調(diào)整為[6,4]。插入3后，因?yàn)?小于6，調(diào)整為[6,4,3]。插入5后，因?yàn)?小于6，調(diào)整為[6,5,3,4]。插入8后，8大于6，所以堆變?yōu)閇8,6,3,4,5]。插入9后，9大于8，最終堆為[9,8,3,4,5,6]。所以插入完成后堆頂?shù)脑貫?。7.將10、12、1、14、6、5、8、15、3、9、7逐個(gè)按順序插入到初始為空的最小堆（小根堆）中，然后連續(xù)執(zhí)行兩次刪除最小元素操作（DeleteMin），此后堆頂?shù)脑厥鞘裁矗緼、5B、6C、7D、9正確答案：A8.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用哪種存儲(chǔ)方式最節(jié)省時(shí)間？A、雙鏈表B、單循環(huán)鏈表C、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D、順序表正確答案：D答案解析：順序表的特點(diǎn)是可以隨機(jī)存取，即可以通過下標(biāo)直接訪問任意位置的元素，時(shí)間復(fù)雜度為O(1)。對(duì)于在最后進(jìn)行插入和刪除運(yùn)算，順序表也可以在O(1)時(shí)間復(fù)雜度內(nèi)完成（在末尾插入或刪除元素時(shí)，不需要移動(dòng)大量元素）。而雙鏈表、單循環(huán)鏈表、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表雖然也能實(shí)現(xiàn)這些操作，但隨機(jī)存取時(shí)需要遍歷鏈表，時(shí)間復(fù)雜度為O(n)，相比之下順序表在這種情況下更節(jié)省時(shí)間。9.數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理相對(duì)位置和邏輯相對(duì)位置相同并且是連續(xù)的，稱之為（）。A、邏輯結(jié)構(gòu)B、順序存儲(chǔ)結(jié)構(gòu)C、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D、以上都不對(duì)正確答案：B答案解析：順序存儲(chǔ)結(jié)構(gòu)是把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的，并且數(shù)據(jù)元素在存儲(chǔ)器內(nèi)是連續(xù)存放的，符合題目描述。而邏輯結(jié)構(gòu)是數(shù)據(jù)元素之間的邏輯關(guān)系，與物理存儲(chǔ)位置無(wú)關(guān)；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中數(shù)據(jù)元素的存儲(chǔ)位置是任意的，不要求連續(xù)。10.如果無(wú)向圖G必須進(jìn)行兩次廣度優(yōu)先搜索才能訪問其所有頂點(diǎn)，則下列說法中不正確的是：A、G肯定不是完全圖B、G中一定有回路C、G一定不是連通圖D、G有2個(gè)連通分量正確答案：B11.一棵樹有n1個(gè)孩子數(shù)為1的結(jié)點(diǎn)，n2個(gè)孩子數(shù)為2的結(jié)點(diǎn)，……，nm個(gè)孩子數(shù)為m的結(jié)點(diǎn)，則該樹的葉結(jié)點(diǎn)數(shù)為：A、1+∑i=2m(i)niB、∑i=2m(i?1)niC、1+∑i=2m(i?1)niD、1+∑i=1m?1(i?1)ni正確答案：C答案解析：設(shè)葉結(jié)點(diǎn)數(shù)為\(n_0\)。樹中結(jié)點(diǎn)總數(shù)\(N=n_0+n_1+n_2+\cdots+n_m\)。樹中分支數(shù)\(B=n_1+2n_2+3n_3+\cdots+mn_m\)。又因?yàn)闃渲蟹种?shù)\(B=N-1\)，即\(n_1+2n_2+3n_3+\cdots+mn_m=n_0+n_1+n_2+\cdots+n_m-1\)，化簡(jiǎn)可得\(n_0=1+\sum_{i=2}^{m}(i-1)n_i\)。12.如果A和B都是二叉樹的葉結(jié)點(diǎn)，那么下面判斷中哪個(gè)是對(duì)的？A、存在一種二叉樹結(jié)構(gòu)，其前序遍歷結(jié)果是…A…B…，而中序遍歷結(jié)果是…B…A…B、存在一種二叉樹結(jié)構(gòu)，其中序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…C、存在一種二叉樹結(jié)構(gòu)，其前序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…D、以上三種都是錯(cuò)的正確答案：D答案解析：前序遍歷是根左右，中序遍歷是左根右，后序遍歷是左右根。對(duì)于葉節(jié)點(diǎn)A和B，若前序遍歷結(jié)果是…A…B…，那么A是根節(jié)點(diǎn)或者A的父節(jié)點(diǎn)是根節(jié)點(diǎn)，若中序遍歷結(jié)果是…B…A…，那么B是根節(jié)點(diǎn)或者B的父節(jié)點(diǎn)是根節(jié)點(diǎn)，二者矛盾，所以A選項(xiàng)錯(cuò)誤；同理，若中序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…，也會(huì)產(chǎn)生矛盾，B選項(xiàng)錯(cuò)誤；若前序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…，同樣會(huì)產(chǎn)生矛盾，C選項(xiàng)錯(cuò)誤。所以以上三種都是錯(cuò)的，選D。13.在散列表中，所謂同義詞就是：A、兩個(gè)意義相近的單詞B、具有相同散列地址的兩個(gè)元素C、被映射到不同散列地址的一個(gè)元素D、被不同散列函數(shù)映射到同一地址的兩個(gè)元素正確答案：B答案解析：同義詞是指在散列表中具有相同散列地址的兩個(gè)元素。當(dāng)不同元素通過散列函數(shù)計(jì)算得到相同的散列值時(shí)，這些元素就互為同義詞。選項(xiàng)A說的是單詞意義，與散列表同義詞概念無(wú)關(guān)；選項(xiàng)C中被映射到不同散列地址不符合同義詞定義；選項(xiàng)D強(qiáng)調(diào)被不同散列函數(shù)映射到同一地址不準(zhǔn)確，通常是同一散列函數(shù)下產(chǎn)生相同散列地址的元素才是同義詞。14.設(shè)散列表的地址區(qū)間為[0,16]，散列函數(shù)為H(Key)=Key%17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列{26，25，72，38，8，18，59}依次存儲(chǔ)到散列表中。元素59存放在散列表中的地址是：A、8B、10C、9D、11正確答案：D15.下面四種排序算法中，穩(wěn)定的算法是：A、歸并排序B、希爾排序C、堆排序D、快速排序正確答案：A答案解析：歸并排序是穩(wěn)定的排序算法。在歸并排序中，合并兩個(gè)有序子數(shù)組時(shí)，相等的元素會(huì)按照原來(lái)的順序依次放入新數(shù)組中，不會(huì)改變相同元素之間的相對(duì)順序。而堆排序、希爾排序和快速排序都不是穩(wěn)定的排序算法。堆排序在調(diào)整堆的過程中可能會(huì)改變相同元素的相對(duì)順序；希爾排序是基于插入排序的改進(jìn)，在分組插入過程中會(huì)破壞穩(wěn)定性；快速排序在選擇基準(zhǔn)元素并劃分區(qū)間時(shí)，也可能導(dǎo)致相同元素相對(duì)順序改變。16.散列沖突可以被描述為：A、兩個(gè)元素除了有不同鍵值，其它都相同B、兩個(gè)有不同數(shù)據(jù)的元素具有相同的鍵值C、兩個(gè)有不同鍵值的元素具有相同的散列地址D、兩個(gè)有相同鍵值的元素具有不同的散列地址正確答案：C答案解析：散列沖突指的是不同鍵值的元素經(jīng)過散列函數(shù)計(jì)算后，得到了相同的散列地址。選項(xiàng)A中兩個(gè)元素除鍵值外其他都相同這不叫散列沖突；選項(xiàng)B說的是不同數(shù)據(jù)元素有相同鍵值，不是散列沖突的定義；選項(xiàng)D兩個(gè)相同鍵值元素有不同散列地址不符合散列沖突的概念。17.我們用一個(gè)有向圖來(lái)表示航空公司所有航班的航線。下列哪種算法最適合解決找給定兩城市間最經(jīng)濟(jì)的飛行路線問題？A、Dijkstra算法B、Kruskal算法C、深度優(yōu)先搜索D、拓?fù)渑判蛩惴ㄕ_答案：A答案解析：Dijkstra算法是用于求解帶權(quán)有向圖中從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑問題，能夠找到給定兩城市間最經(jīng)濟(jì)的飛行路線。Kruskal算法用于求無(wú)向圖的最小生成樹。深度優(yōu)先搜索主要用于遍歷圖。拓?fù)渑判蛩惴ㄓ糜谟邢驘o(wú)環(huán)圖。所以最適合解決該問題的是Dijkstra算法，答案選A。18.下列排序算法中，哪種算法可能出現(xiàn)：在最后一趟開始之前，所有的元素都不在其最終的位置上？（設(shè)待排元素個(gè)數(shù)N>2）A、冒泡排序B、插入排序C、快速排序D、堆排序正確答案：B19.對(duì)于7個(gè)數(shù)進(jìn)行冒泡排序，需要進(jìn)行的比較次數(shù)為：A、21B、7C、49D、14正確答案：A20.對(duì)N個(gè)記錄進(jìn)行歸并排序，歸并趟數(shù)的數(shù)量級(jí)是：A、O(logN)B、O(N)C、O(NlogN)D、O(N2)正確答案：A答案解析：歸并排序的基本思想是將數(shù)組分成兩個(gè)子數(shù)組，對(duì)每個(gè)子數(shù)組分別進(jìn)行排序，然后將排序好的子數(shù)組合并成一個(gè)有序的數(shù)組。歸并排序的時(shí)間復(fù)雜度為O(NlogN)，其中N是記錄的數(shù)量。歸并趟數(shù)與logN相關(guān)，其數(shù)量級(jí)是O(logN)。21.一棵度為4的樹中有20個(gè)度為4的結(jié)點(diǎn)、10個(gè)度為3的結(jié)點(diǎn)、1個(gè)度為2的結(jié)點(diǎn)和10個(gè)度為1的結(jié)點(diǎn)，則樹的葉子結(jié)點(diǎn)數(shù)為▁▁▁▁▁。A、113B、82C、41D、122正確答案：B22.若top為指向棧頂元素的指針，判定棧S（最多容納m個(gè)元素）為空的條件是：A、S->top==0B、S->top==-1C、S->top!=m-1D、S->top==m-1正確答案：B答案解析：棧的初始狀態(tài)下，棧頂指針top的值通常被設(shè)置為-1，表示棧為空。當(dāng)元素入棧時(shí)，top的值會(huì)增加；當(dāng)元素出棧時(shí)，top的值會(huì)減少。所以當(dāng)S->top==-1時(shí)，棧為空。23.度量結(jié)果集相關(guān)性時(shí)，如果準(zhǔn)確率很高而召回率很低，則說明：A、大部分相關(guān)文件被檢索到，但很多不相關(guān)的文件也在檢索結(jié)果里B、大部分相關(guān)文件被檢索到，但基準(zhǔn)數(shù)據(jù)集不夠大C、大部分檢索出的文件都是相關(guān)的，但基準(zhǔn)數(shù)據(jù)集不夠大D、大部分檢索出的文件都是相關(guān)的，但還有很多相關(guān)文件沒有被檢索出來(lái)正確答案：D答案解析：準(zhǔn)確率很高說明大部分檢索出的文件都是相關(guān)的，召回率很低說明還有很多相關(guān)文件沒有被檢索出來(lái)。24.將線性表La和Lb頭尾連接，要求時(shí)間復(fù)雜度為O(1)，且占用輔助空間盡量小。應(yīng)該使用哪種結(jié)構(gòu)？A、單鏈表B、單循環(huán)鏈表C、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D、帶尾指針的單循環(huán)鏈表正確答案：D25.對(duì)N個(gè)不同的數(shù)據(jù)采用冒泡算法進(jìn)行從大到小的排序，下面哪種情況下肯定交換元素次數(shù)最多？A、從小到大排好的B、從大到小排好的C、元素?zé)o序D、元素基本有序正確答案：A26.樹最適合于用來(lái)表示A、元素之間具有分支層次關(guān)系的數(shù)據(jù)B、元素之間無(wú)聯(lián)系的數(shù)據(jù)C、無(wú)序數(shù)據(jù)元素D、有序數(shù)據(jù)元素正確答案：A答案解析：樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它的每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)，這種結(jié)構(gòu)非常適合用來(lái)表示元素之間具有分支層次關(guān)系的數(shù)據(jù)。例如家族樹、文件目錄結(jié)構(gòu)等都是典型的具有分支層次關(guān)系的數(shù)據(jù)，用樹來(lái)表示非常直觀和方便。而有序數(shù)據(jù)元素可以用數(shù)組或鏈表等線性結(jié)構(gòu)來(lái)表示；無(wú)序數(shù)據(jù)元素同樣可以用合適的線性結(jié)構(gòu)表示；元素之間無(wú)聯(lián)系的數(shù)據(jù)不適合用樹來(lái)表示，樹強(qiáng)調(diào)元素之間的層次關(guān)系。27.表達(dá)式3*2^(4+2*2-6*3)-5求值過程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為（），其中^為乘冪。A、3,2,4,1,1；(^(+-B、3,2,4,2,2；(*^(-C、3,2,8；(*^-D、3,2,8；(*^(-正確答案：D28.若用大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為0和4。當(dāng)從隊(duì)列中刪除兩個(gè)元素，再加入兩個(gè)元素后，front和rear的值分別為多少？A、2和0B、2和2C、2和6D、2和4正確答案：A29.二叉樹中第5層（根的層號(hào)為1）上的結(jié)點(diǎn)個(gè)數(shù)最多為：A、8B、15C、16D、32正確答案：C答案解析：二叉樹中第\(n\)層上的結(jié)點(diǎn)個(gè)數(shù)最多為\(2^{n-1}\)。當(dāng)\(n=5\)時(shí)，\(2^{5-1}=2^4=16\)，所以二叉樹中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為16。30.對(duì)于外排序中的k路歸并，k不取很大值的首要原因是：A、k的上界是有序段的個(gè)數(shù)B、輸入\輸出的時(shí)間會(huì)增多C、歸并時(shí)的比較次數(shù)會(huì)增多D、k必須是一個(gè)有限的整數(shù)正確答案：B31.下列關(guān)于無(wú)向連通圖特征的敘述中，正確的是：所有頂點(diǎn)的度之和為偶數(shù)邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1至少有一個(gè)頂點(diǎn)的度為1A、1和3B、只有1C、只有2D、1和2正確答案：B32.將9,8,7,2,3,5,6,4順序插入一棵初始為空的AVL樹。下列句子中哪句是錯(cuò)的？A、5是根結(jié)點(diǎn)B、2和5是兄弟C、有2個(gè)結(jié)點(diǎn)的平衡因子為-1D、最后得到的AVL樹的高度是3正確答案：A33.在快速排序的一趟劃分過程中，當(dāng)遇到與基準(zhǔn)數(shù)相等的元素時(shí)，如果左右指針都不停止移動(dòng)，那么當(dāng)所有元素都相等時(shí)，算法的時(shí)間復(fù)雜度是多少？A、O(N)B、O(NlogN)C、O(logN)D、O(N2)正確答案：D答案解析：當(dāng)所有元素都相等時(shí)，在快速排序的一趟劃分過程中，左右指針會(huì)一直移動(dòng)到數(shù)組的兩端。每次劃分操作，基準(zhǔn)元素與所有元素比較，左指針從左到右移動(dòng)，右指針從右到左移動(dòng)，直到兩個(gè)指針相遇。這個(gè)過程的時(shí)間復(fù)雜度為\(O(N)\)。但是，由于所有元素都相等，每次劃分都只能將數(shù)組分成兩部分，其中一部分為空，另一部分包含所有元素。這樣，快速排序需要進(jìn)行\(zhòng)(N\)次劃分操作，所以總的時(shí)間復(fù)雜度為\(O(N^2)\)。34.令P代表入棧，O代表出棧。若利用堆棧將中綴表達(dá)式3*2+8/4轉(zhuǎn)為后綴表達(dá)式，則相應(yīng)的堆棧操作序列是：A、POPOPOB、PPPOOOC、POPPOOD、PPOOPO正確答案：C35.一棵有1001個(gè)結(jié)點(diǎn)的完全二叉樹，其葉子結(jié)點(diǎn)數(shù)為▁▁▁▁▁。A、500B、254C、250D、501正確答案：D36.算法的時(shí)間復(fù)雜度取決于（）。A、問題的規(guī)模B、待處理數(shù)據(jù)的初態(tài)C、計(jì)算機(jī)的配置D、A和B正確答案：D答案解析：算法的時(shí)間復(fù)雜度不僅取決于問題的規(guī)模，還與待處理數(shù)據(jù)的初態(tài)有關(guān)。問題規(guī)模越大，通常算法執(zhí)行時(shí)間可能越長(zhǎng)；而數(shù)據(jù)初態(tài)不同，比如數(shù)據(jù)的有序性等，也會(huì)影響算法執(zhí)行過程中具體操作的次數(shù)，從而影響時(shí)間復(fù)雜度。計(jì)算機(jī)配置主要影響程序運(yùn)行的實(shí)際時(shí)間，而非算法本身的時(shí)間復(fù)雜度。所以算法的時(shí)間復(fù)雜度取決于問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)，答案選D。37.設(shè)有一組關(guān)鍵字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函數(shù)為H(key)=key%17，采用線性探測(cè)方法解決沖突。試在0到18的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造散列表，則成功查找的平均查找長(zhǎng)度為__A、1.17B、1.25C、0.33D、1.33正確答案：D答案解析：1.首先計(jì)算每個(gè)關(guān)鍵字的散列地址：-\(H(29)=29\%17=12\)-\(H(01)=1\%17=1\)-\(H(13)=13\%17=13\)-\(H(15)=15\%17=15\)-\(H(56)=56\%17=5\)-\(H(20)=20\%17=3\)-\(H(87)=87\%17=2\)-\(H(27)=27\%17=10\)-\(H(69)=69\%17=1\)，沖突，線性探測(cè)后存放在\(2\)-\(H(9)=9\%17=9\)-\(H(10)=10\%17=10\)，沖突，線性探測(cè)后存放在\(11\)-\(H(74)=74\%17=6\)2.然后計(jì)算每個(gè)關(guān)鍵字的查找長(zhǎng)度：-關(guān)鍵字\(29\)，查找長(zhǎng)度為\(1\)-關(guān)鍵字\(01\)，查找長(zhǎng)度為\(1\)-關(guān)鍵字\(13\)，查找長(zhǎng)度為\(1\)-關(guān)鍵字\(15\)，查找長(zhǎng)度為\(1\)-關(guān)鍵字\(56\)，查找長(zhǎng)度為\(1\)-關(guān)鍵字\(20\)，查找長(zhǎng)度為\(1\)-關(guān)鍵字\(87\)，查找長(zhǎng)度為\(1\)-關(guān)鍵字\(27\)，查找長(zhǎng)度為\(1\)-關(guān)鍵字\(69\)，第一次沖突，查找長(zhǎng)度為\(2\)-關(guān)鍵字\(9\)，查找長(zhǎng)度為\(1\)-關(guān)鍵字\(10\)，第一次沖突，查找長(zhǎng)度為\(2\)-關(guān)鍵字\(74\)，查找長(zhǎng)度為\(1\)3.最后計(jì)算平均查找長(zhǎng)度：-平均查找長(zhǎng)度\(ASL=(1+1+1+1+1+1+1+1+2+1+2+1)/12=16/12\approx1.33\)所以成功查找的平均查找長(zhǎng)度大于\(1.33\)，答案選[D、]>1