2023數(shù)據(jù)結構考試內部題庫含答案解析

數(shù)據(jù)結構考試內部題庫含答案解析（全考點）1、在下列算法中，（）算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有元素都不在最終位置上。A：堆排序B：冒泡排序C：直接插入排序D：快速排序解析在直接插入排序中，若待排序列中的最后一個元素應插入表中的第一個位置，則前面的有序子序列中的所有元素都不在最終位置上。答案：C2、對序列{98,36,-9,0,47,23,1,8,10,7}采用希爾排序，下列序列（）是增量為4的一趟排序結果。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：以上都不對解析增量為4意味著所有相距為4的記錄構成一組，然后在組內進行直接插入排序，經(jīng)觀察，只有選項A滿足要求。答案：A3、用希爾排序方法對一個數(shù)據(jù)序列進行排序時，若第1趟排序結果為9,1,4,13,7,8,20,23,15，則該趟排序采用的增量（間隔）可能是（）。A：2B：3C：4D：5解析首先，第二個元素為1，是整個序列中的最小元素，因此可知該希爾排序為從小到大排序。然后考慮增量問題，若增量為2，則第1+2個元素4明顯比第1個元素9要小，A排除；若增量為3，則第i,i+3,i+6（i=1,2,3）個元素都為有序序列，符合希爾排序的定義；若增量為4，則第1個元素9比第1+4個元素7要大，C排除；若增量為5，則第1個元素9比第1+5個元素8要大，D排除。故選B。答案：B4、一組記錄的關鍵碼為（46,79,56,38,40,84），則利用快速排序的方法，以第一個記錄為基準，從小到大得到的一次劃分結果為（）。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為基準元素，首先從后向前掃描比46小的元素，并與之進行交換，而后從前向后掃描比46大的元素并將46與該元素交換，得到（40,46,56,38,79,84）。此后，繼續(xù)重復從后向前掃描與從前往后掃描的操作，直到46處于最終位置，答案選C。答案：C5、快速排序算法在（）情況下最不利于發(fā)揮其長處。A：要排序的數(shù)據(jù)量太大B：要排序的數(shù)據(jù)中含有多個相同值C：要排序的數(shù)據(jù)個數(shù)為奇數(shù)D：要排序的數(shù)據(jù)已基本有序解析當待排序數(shù)據(jù)為基本有序時，每次選取第n個元素為基準，會導致劃分區(qū)間分配不均勻，不利于發(fā)揮快速排序算法的優(yōu)勢。相反，當待排序數(shù)據(jù)分布較為隨機時，基準元素能將序列劃分為兩個長度大致相等的序列，這時才能發(fā)揮快速排序的優(yōu)勢。答案：D6、對數(shù)據(jù)序列{8,9,10,4,5,6,20,1,2}采用冒泡排序（從后向前次序進行，要求升序），需要進行的趟數(shù)至少是（）。A：3B：4C：5D：8解析從后向前“冒泡”的過程為，第一趟{1,8,9,10,4,5,6,20,2}，第二趟{1,2,8,9,10,4,5,6,20}，第三趟{1,2,4,8,9,10,5,6,20}，第四趟{1,2,4,5,8,9,10,6,20}，第五趟{1,2,4,5,6,8,9,10,20}，經(jīng)過第五趟冒泡后，序列已經(jīng)全局有序，故選C。實際每趟冒泡發(fā)生交換后可以判斷是否會導致新的逆序對，如果不會產(chǎn)生，則本趟冒泡之后序列全局有序，所以最少5趟即可。答案：C7、對下列4個序列，以第一個關鍵字為基準用快速排序算法進行排序，在第一趟過程中移動記錄次數(shù)最多的是（）。A：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ù)是4。同樣也可以分析出B中序列的移動次數(shù)為8，C中序列的移動次數(shù)為4，D中序列的移動次數(shù)為2。答案：B8、對n個關鍵字進行快速排序，最大遞歸深度為（）,最小遞歸深度為（）。A：1B：nC：D：解析快速排序過程構成一個遞歸樹，遞歸深度即遞歸樹的高度。樞紐值每次都將子表等分時，遞歸樹的高為；樞紐值每次都是子表的最大值或最小值時，遞歸樹退化為單鏈表，樹高為n。答案：B，C9、采用遞歸方式對順序表進行快速排序，下列關于遞歸次數(shù)的敘述中，正確的是（）。A：遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關B：每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)C：每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D：遞歸次數(shù)與每次劃分后得到的分區(qū)的處理順序無關解析遞歸次數(shù)與各元素的初始排列有關。若每次劃分后分區(qū)比較平衡，則遞歸次數(shù)少；若區(qū)分不平衡，遞歸次數(shù)多。遞歸次數(shù)與處理順序是沒有關系的。答案：D10、為實現(xiàn)快速排序算法，待排序序列宜采用的存儲方式是（）。A：順序存儲B：散列存儲C：鏈式存儲D：索引存儲解析絕大部分內部排序只適用于順序存儲結構。快速排序在排序的過程中，既要從后向前查找，又要從前向后查找，因此宜采用順序存儲。答案：A1、在開放定址法中散列到同一個地址而引起的“堆積”問題是由于（）引起的。A：同義詞之間發(fā)生沖突B：非同義詞之間發(fā)生沖突C：同義詞之間或非同義詞之間發(fā)生沖突D：散列表“溢出”解析在開放定址法中散列到同一個地址而產(chǎn)生的“堆積”問題，是同義詞沖突的探查序列和非同義詞之間不同的探查序列交織在一起，導致關鍵字查詢需要經(jīng)過較長的探測距離，降低了散列的效率。因此要選擇好的處理沖突的方法來避免“堆積”。答案：C2、下列關于散列沖突處理方法的說法中，正確的有（）。Ⅰ、采用再散列法處理沖突時不易產(chǎn)生聚集Ⅱ、采用線性探測法處理沖突時，所有同義詞在散列表中一定相鄰Ⅲ、采用鏈地址法處理沖突時，若限定在鏈首插入，則插入任一個元素的時間是相同的Ⅳ、采用鏈地址法處理沖突易引起聚集現(xiàn)象A：Ⅰ和ⅢB：Ⅰ、Ⅱ和ⅢC：Ⅲ和ⅣD：Ⅰ和Ⅳ解析利用再散列法處理沖突時，按一定的距離，跳躍式地尋找“下一個”空閑位置，減少了發(fā)生聚集的可能，Ⅰ正確。散列地址i的關鍵字，和為解決沖突形成的某次探測地址為i的關鍵字，都爭奪地址i，i+1，...，因此不一定相鄰，Ⅱ錯誤。Ⅲ正確。同義詞沖突不等于聚集，鏈地址法處理沖突時將同義詞放在同一個鏈表中，不會引起聚集現(xiàn)象，Ⅳ錯誤。答案：A3、設有一個含有200個表項的散列表，用線性探測法解決沖突，按關鍵字查詢時找到一個表項的平均探測次數(shù)不超過1.5，則散列表應能夠容納（）個表項（設查找成功的平均查找長度為ASL=，其中為裝填因子）。A：400B：526C：624D：676解析若有200個表項要放入散列表，采用線性探測法解決沖突，限定查找成功的平均查找長度不超過1.5，則答案：A4、假定有K個關鍵字互為同義詞，若用線性探測法把這K個關鍵字填入散列表，至少要進行（）次探測。A：K-1B：KC：K+1D：K(K+1)/2解析K個關鍵字在依次填入的過程中，只有第一個不會發(fā)生沖突，故探測次數(shù)為（1+2+3+...+K）=K(K+1)/2，即選D。答案：D5、對包含n個元素的散列表進行查找，平均查找長度（）。A：為B：為O(1)C：不直接依賴于nD：直接依賴于表長m解析在散列表中，平均查找長度與裝填因子直接相關，表的查找效率不直接依賴于表中已有表項個數(shù)n或表長m。若散列表中存放的記錄全部是某個地址的同義詞，則平均查找長度為O(n)而非O(1)。答案：C6、采用開放定址法解決沖突的散列查找中，發(fā)生聚集的原因主要是（）。A：數(shù)據(jù)元素過多B：負載因子過大C：散列函數(shù)選擇不當D：解決沖突的方法選擇不當解析聚集是因為選取不當?shù)奶幚頉_突的方法，而導致不同關鍵字的元素對同一散列地址進行爭奪的現(xiàn)象。用線性再探測法，容易引發(fā)聚集現(xiàn)象。答案：D7、在采用鏈地址法處理沖突所構成的散列表上查找某一關鍵字，則在查找成功的情況下，所探測的這些位置上的鍵值（）；若采用線性探測法，則（）。A：一定都是同義詞B：不一定都是同義詞C：都相同D：一定都不是同義詞解析因為在鏈地址法中，映射到同一地址的關鍵字都會鏈到與此地址相對應的鏈表上，所以探測過程一定是在此鏈表上進行的，從而這些位置上的關鍵字均為同義詞；但在線性探測法中出現(xiàn)兩個同義關鍵字時，會把該關鍵字對應地址的下一個地址也占用掉，兩個地址分別記為Addr、Addr+1，查找一個滿足H(key)=Addr+1的關鍵字key時，顯然首次探測到的不是key的同義詞。答案：A，B8、用哈希（散列）方法處理沖突（碰撞）時可能出現(xiàn)堆積（聚集）現(xiàn)象，下列選項中，會受堆積現(xiàn)象直接影響的是（）。A：存儲效率B：散列函數(shù)C：裝填（裝載）因子D：平均查找長度解析產(chǎn)生堆積現(xiàn)象，即產(chǎn)生了沖突，它對存儲效率、散列函數(shù)和裝填因子均不會有影響，而平均查找長度會因為堆積現(xiàn)象而增大，選D。答案：D9、現(xiàn)有長度為11且初始為空的散列表HT，散列函數(shù)是H(key)=key%7，采用線性探查（線性探測再散列）法解決沖突。將關鍵字序列87,40,30,6，11,22,98,20依次插入HT后，HT查找失敗的平均查找長度是（）。A：4B：5.35C：6D：6.29解析采用線性探查法計算每個關鍵字的存放情況如下表所示。請?zhí)砑訄D片描述由于H(key)=0~6，查找失敗時可能對應的地址有7個，對于計算出地址為0的關鍵字key0，只有比較完0~8號地址后才能確定該關鍵字不在表中，比較次數(shù)為9；對于計算出地址為1的