(全)2023數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫含答案解析

數(shù)據(jù)結(jié)構(gòu)考試內(nèi)部題庫含答案解析（全考點(diǎn)）.在下列算法中，（）算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有元素都不在最終位置上。.A:堆排序?B:冒泡排序.C:直接插入排序.D:快速排序解析在直接插入排序中，若待排序列中的最后一個元素應(yīng)插入表中的第一個位置，則前面的有序子序列中的所有元素都不在最終位置上。答案：C.對序列{98,36,-9,0,47,23,1,8,10,7}采用希爾排序,下列序列（）是增量為4的一趟排序結(jié)果。A: {98,7,-9,0,47,23,1,8,98,36}B: {-9,0,36,98,1,8,23,47,7,10}C: {36,98,-9,0,23,47,1,8,7,10}D:以上都不對同義詞沖突不等于聚集，鏈地址法處理沖突時將同義詞放在同一個鏈表中，不會引起聚集現(xiàn)象，IV錯誤。答案：A3.設(shè)有一個含有200個表項的散列表，用線性探測法解決沖突，按關(guān)鍵字杳詢時找到一個表項的平均探測次數(shù)不超過L5,則散列表應(yīng)能夠容納（）個表項（設(shè)直找成功的平?》 [1+1/（1—a）]/2一均蟄找長度為ASL=L /'刀/，其中a為裝填因子）。TOC\o"1-5"\h\zA : 400B : 526C : 624D : 676解析若有200個表項要放入散列表，采用線性探測法解決沖突,限定查找成功的平均查找長度不超過1.5，則答案：A4、假定有K個關(guān)鍵字互為同義詞，若用線性探測法把這K個關(guān)鍵字填入散列表，至少要進(jìn)行()次探測。TOC\o"1-5"\h\zA: K-1B: KC: K+1D: K(K+l)/2解析K個關(guān)鍵字在依次填入的過程中，只有第一個不會發(fā)生沖突，故探測次數(shù)為(1+2+3+…+K)=K(K+l)/2,即選Do答案：D.對包含n個元素的散列表進(jìn)行直找，平均直找長度()。.A：為。。鳴九)B:為0(1)C:不直接依賴于nD:直接依賴于表長m解析a在散列表中，平均查找長度與裝填因子直接相關(guān)，表的查找效率不直接依賴于表中已有表項個數(shù)n或表長m。若散列表中存放的記錄全部是某個地址的同義詞,則平均查找長度為0(n)而非0(1)。答案：C.采用開放定址法解決沖突的散列查找中，發(fā)生聚集的原因主要是()。.A:數(shù)據(jù)元素過多.B:負(fù)載因子過大C:散列函數(shù)選擇不當(dāng)D:解決沖突的方法選擇不當(dāng)解析聚集是因?yàn)檫x取不當(dāng)?shù)奶幚頉_突的方法，而導(dǎo)致不同關(guān)鍵字的元素對同一散列地址進(jìn)行爭奪的現(xiàn)象。用線性再探測法，容易引發(fā)聚集現(xiàn)象。答案：D7、在采用鏈地址法處理沖突所構(gòu)成的散列表上查找某一關(guān)鍵字，則在蟄找成功的情況下，所探測的這些位置上的鍵值（）；若采用線性探測法，則（）。A:一定都是同義詞B:不一定都是同義詞.C:都相同D:一定都不是同義詞解析因?yàn)樵阪湹刂贩ㄖ校成涞酵坏刂返年P(guān)鍵字都會鏈到與此地址相對應(yīng)的鏈表上，所以探測過程一定是在此鏈表上進(jìn)行的，從而這些位置上的關(guān)鍵字均為同義詞；但在線性探測法中出現(xiàn)兩個同義關(guān)鍵字時，會把該關(guān)鍵字對應(yīng)地址的下一個地址也占用掉，兩個地址分別記為Addr、Addr+1,查找一個滿足H（key）=Addr+l的關(guān)鍵字key時，顯然首次探測到的不是key的同義詞。答案：A,B8、用哈希（散列）方法處理沖突（碰撞）時可能出現(xiàn)堆積（聚集）現(xiàn)象，下列選項中，會受堆積現(xiàn)象直接影響的是（）。.A:存儲效率B:散列函數(shù)C:裝填（裝載）因子.D:平均查找長度解析產(chǎn)生堆積現(xiàn)象，即產(chǎn)生了沖突，它對存儲效率、散列函數(shù)和裝填因子均不會有影響，而平均查找長度會因?yàn)槎逊e現(xiàn)象而增大，選Do答案：D9、現(xiàn)有長度為11且初始為空的散列表HT,散列函數(shù)是H（key）二key%7,采用線性探直（線性探測再散列）法解決沖突。將關(guān)鍵字序列87,40,30,6,11,22,98,20依次插入HT后，HT查找失敗的平均查找長度是（）。A:4B:5.35C:6D:6.29解析采用線性探查法計算每個關(guān)鍵字的存放情況如下表所示。請?zhí)砑訄D片描述由于H(key)二0~6,查找失敗時可能對應(yīng)的地址有7個，對于計算出地址為0的關(guān)鍵字keyO,只有比較完。?8號地址后才能確定該關(guān)鍵字不在表中，比較次數(shù)為9;對于計算出地址為1的關(guān)鍵字keyl,只有比較完1?8號地址后才能確定該關(guān)鍵字不在表中，比較次數(shù)為8;以此類推。需要特別注意的是，散列函數(shù)不可能計算出地址7,因此有請?zhí)砑訄D片描述答案：C10,對任意7個關(guān)鍵字進(jìn)行基于比較的排序至少要進(jìn)行()次關(guān)鍵字之間的兩兩比較。A:13B:14C:15D:6解析對于任意序列進(jìn)行基于比較的排序，求最少的比較次數(shù)應(yīng)考慮最壞情況。對于任意n個關(guān)鍵字排序的比較次數(shù)至少為口理？"）：將n=7代入公式，答案為13o答案：A解析增量為4意味著所有相距為4的記錄構(gòu)成一組，然后在組內(nèi)進(jìn)行直接插入排序，經(jīng)觀察，只有選項A滿足要求。答案：A3、用希爾排序方法對一個數(shù)據(jù)序列進(jìn)行排序時，若第1趟排序結(jié)果為9,1,4,13,7,8,20,23,15,則該趟排序采用的增量（間隔）可能是（）。TOC\o"1-5"\h\zA: 2B: 3C: 4D: 5解析首先，第二個元素為1,是整個序列中的最小元素，因此可知該希爾排序?yàn)閺男〉酱笈判颉Ｈ缓罂紤]增量問題，若增量為2,則第1+2個元素4明顯比第1個元素9要小，A排除;若增量為3,則第i,i+3,i+6（i=l,2,3）個元素都為有序序列，符合希爾排序的定義；若增量為4，則第1個元素9比第1+4個元素7要大，C排除;若增量為5，則第1個元素9比第1+5個元素8要大，D排除。故選Bo答案：B4、一組記錄的關(guān)鍵碼為(46,79,56,38,40,84),則利用快速排序的方法，以第一個記錄為基準(zhǔn)，從小到大得到的一次劃分結(jié)果為()。A: (38,40,46,56,79,84)B: (40,38,46,79,56,84)C: (40,38,46,56,79,84)D: (40,38,46,84,56,79)解析以46為基準(zhǔn)元素,首先從后向前掃描比46小的元素，并與之進(jìn)行交換，而后從前向后掃描比46大的元素并將46與該元素交換，得到(40,46,56,38,79,84)o此后，繼續(xù)重復(fù)從后向前掃描與從前往后掃描的操作直到46處于最終位置，答案選Co答案：C5、快速排序算法在（）情況下最不利于發(fā)揮其長處。.A:要排序的數(shù)據(jù)量太大.B:要排序的數(shù)據(jù)中含有多個相同值.C:要排序的數(shù)據(jù)個數(shù)為奇數(shù).D:要排序的數(shù)據(jù)已基本有序解析當(dāng)待排序數(shù)據(jù)為基本有序時，每次選取第n個元素為基準(zhǔn)，會導(dǎo)致劃分區(qū)間分配不均勻，不利于發(fā)揮快速排序算法的優(yōu)勢。相反，當(dāng)待排序數(shù)據(jù)分布較為隨機(jī)時，基準(zhǔn)元素能將序列劃分為兩個長度大致相等的序列，這時才能發(fā)揮快速排序的優(yōu)勢。答案：D6.對數(shù)據(jù)序列｛8,9,10,4,5,6,20,1,2｝采用冒泡排序（從后向前次序進(jìn)行，要求升序），需要進(jìn)行的趟數(shù)至少是（）OTOC\o"1-5"\h\zB :4C :5D :8解析從后向前r=i泡〃的過程為，第一趟從后向前r=i泡〃的過程為，第一趟{(lán)1,8,9,10,4,5,6,20,2},第二趟{(lán)1,2,8,9,10,4,5,6,20},第三趟{(lán)1,2,4,8,9,10,5,6,20},第四趟{(lán)1,2,4,5,8,9,10,6,20},第五趟{(lán)1,2,4,5,6,8,9,10,20},經(jīng)過第五趟冒泡后，序列已經(jīng)全局有序，故選Co實(shí)際每趟冒泡發(fā)生交換后可以判斷是否會導(dǎo)致新的逆序?qū)Γ绻粫a(chǎn)生，則本趟冒泡之后序列全局有序，所以最少5趟即可。答案：C7、對下列4個序列，以第一個關(guān)鍵字為基準(zhǔn)用快速排序算法進(jìn)行排序，在第一趟過程中移動記錄次數(shù)最多的是（）OA:92,96,88,42,30,35,110,100B:92,96,100,110,42,35,30,88C:100,96,92,35,30,110,88,42D:42,30,35,92,100,96,88,110解析對各序列分別執(zhí)行一趟快速排序，可做如下分析（以A為例）:由于樞紐值為92,因此35移動到第一個位置，96移動到第六個位置，30移動到第二個位置，再將樞紐值移動到30所在的單元，即第五個位置，所以A中序列移動的次數(shù)是4O同樣也可以分析出B中序列的移動次數(shù)為8,C中序列的移動次數(shù)為4,D中序列的移動次數(shù)為20答案：B8、對n個關(guān)鍵字進(jìn)行快速排序，最大遞歸深度為（），最小遞歸深度為（）。A:1B:nc.晦nL?n.^log2n解析快速排序過程構(gòu)成一個遞歸樹，遞歸深度即遞歸樹的高度。樞紐值每次都將子表等分時，遞歸樹的高為logon;樞紐值每次都是子表的最大值或最小值時，遞歸樹退化為單鏈表，樹高為no答案：B,C9、采用遞歸方式對順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是()。?A:遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān).B:每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù).C:每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)?D:遞歸次數(shù)與每次劃分后得到的分區(qū)的處理順序無關(guān)解析遞歸次數(shù)與各元素的初始排列有關(guān)。若每次劃分后分區(qū)比較平衡，則遞歸次數(shù)少；若區(qū)分不平衡，遞歸次數(shù)多。遞歸次數(shù)與處理順序是沒有關(guān)系的。答案：D10.為實(shí)現(xiàn)快速排序算法，待排序序列宜采用的存儲方式是()oA:順序存儲.B:散列存儲C:鏈?zhǔn)酱鎯?D:索引存儲解析絕大部分內(nèi)部排序只適用于順序存儲結(jié)構(gòu)?？焖倥判蛟谂判虻倪^程中，既要從后向前查找，又要從前向后查找，因此宜采用順序存儲。答案：A1、在開放定址法中散列到同一個地址而引起的“堆積〃問題是由于（）引起的。A:同義詞之間發(fā)生沖突.B:非同義詞之間發(fā)生沖突C:同義詞之間或非同義詞之間發(fā)生沖突.D:散列表〃溢出〃解析在開放定址法中散列到同一個地址而產(chǎn)生的〃堆積〃問題，是同義詞沖突的探查序列和非同義詞之間不同的探查序列交織在一起，導(dǎo)致關(guān)鍵字查詢需要經(jīng)過較長的探測距離，降低了散列的效率。因此要選擇好的處理沖突的方法來避免〃堆積〃。答案：C2、下列關(guān)于散列沖突處理方法的說法中，正確的有（）。工、采用再散列法處理沖突時不易產(chǎn)生聚集口、采用線性探測法處理沖突時，所有同義詞在散列表中一定相鄰m