資源描述：
《數(shù)據(jù)結(jié)構(gòu)試卷(手動組卷)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、題目部分，(卷面共有78題,523.0分,各大題標有題量和總分)一、簡答題(78小題,共523.0分)(5分)[1]堆排序是否是一種穩(wěn)定的排序方法？為什么？(10分)[2]簡要敘述B(有些教材稱為B-樹)與B+樹的區(qū)別(8分)[3]在多關(guān)鍵字排序時，LSD和MSD兩種方法的特點是什么？(4分)[4]快速排序是在所有情況下，排序速度最快嗎？為什么？在何種情況下使用此排序法最好？(3分)[5]在內(nèi)排序算法中，待排序的數(shù)據(jù)已基本有序時，花費時間反而最多的排序方法是哪種？(5分)[6]快速排序的最大遞歸深度是多少？
2、最小遞歸深度是多少？(7分)[7]在執(zhí)行某個排序算法過程中，出現(xiàn)了排序關(guān)鍵字朝著最終排序序列相反的方向的移動，從而認為該算法是不穩(wěn)定的。這種說法對么？為什么？(6分)[8]外排序中為何采用k-路（k>2）合并而不用2-路合并？這種技術(shù)用于內(nèi)排序有意義嗎？為什么？(7分)[9]以歸并算法為例，比較內(nèi)排序和外排序的不同，說明外排序如何提高操作效率。(5分)[10]設(shè)要求從大到小排序。問在什么情況下冒泡排序算法關(guān)鍵字交換的次數(shù)為最大。(6分)[11]快排序、堆排序、合并排序、Shell排序中哪種排序平均比較次數(shù)最
3、少，哪種排序占用空間最多，哪幾種排序算法是不穩(wěn)定的？(8分)[12]在堆排序、快速排序和合并排序中：(1)．若只從存儲空間考慮，則應(yīng)首先選取哪種排序方法，其次選取哪種排序方法，最后選取哪種排序方法？(2)．若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取哪種排序方法？(3)．若只從平均情況下排序最快考慮，則應(yīng)選取哪種排序方法？(4)．若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取哪種排序方法？(8分)[13]簡述直接插入排序，簡單選擇排序，2-路歸并排序的基本思想以及在時間復(fù)雜度和排序穩(wěn)定性上的差別。(6分)[1
4、4]以下概念的區(qū)別：拓撲排序與冒泡排序。(5分)[15]在執(zhí)行某種排序算法的過程中出現(xiàn)了排序碼朝著最終排序序列相反的方向移動，從而認為該排序算法是不穩(wěn)定的，這種說法對嗎？為什么？(7分)[16]對于堆積排序法，快速排序法和歸并排序法，若僅從節(jié)省存儲空間考慮，則應(yīng)該首先選取其中哪種方法？其次選取哪種方法？若僅考慮排序結(jié)果的穩(wěn)定性，則應(yīng)該選取其中哪種方法？若僅從平均情況下排序最快這一點考慮，則應(yīng)該選取其中哪些方法？(4分)[17]八皇后問題的最大遞歸深度是多少？(4分)[18]如果一棵Huffman樹T有個葉子
5、結(jié)點，那么，樹T有多少個結(jié)點？(3分)[19]什么是循環(huán)隊列？(8分)[20]簡述數(shù)組與字符串屬于線性表的理由。(4分)[21]試敘述一維數(shù)組與有序表的異同。(5分)[22]用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？(8分)[23]在使用非遞歸方法實現(xiàn)快速排序時,通常要利用一個棧記憶待排序區(qū)間的兩個端點。那么能否用隊列來代替這個棧?為什么?(8分)[24]常用的存儲表示方法有哪幾種?(4分)[25]KMP算法(字符串匹配算法)較Brute(樸素的字符串匹配)算法有哪些改進?(
6、4分)[26]兩個字符串相等的充要條件是什么？(3分)[27]兩個串相等的充分必要條件是什么？(2分)[28]串的兩種最基本的存儲方式是什么？(5分)[29]試敘述一維數(shù)組與有序表的異同。(6分)[30]在什么條件下，MSD基數(shù)排序比LSD基數(shù)排序效率更高？(5分)[31]在順序表中插入和刪除一個結(jié)點需平均移動多少個結(jié)點？具體移動次數(shù)取決于哪幾個因素？(6分)[32]為什么有序的單鏈表不能進行折半查找?(6分)[33]何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜？簡述線性表的相互許存儲與鏈接存儲的空
7、間分配方式、存儲結(jié)構(gòu)特性和主要優(yōu)缺點。(8分)[34]循環(huán)隊列的優(yōu)點是什么?如何判別它的空和滿?(6分)[35]鏈棧中為何不設(shè)置頭結(jié)點?(4分)[36]試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計語言中數(shù)據(jù)類型概念的區(qū)別？(5分)[37]算法的時間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎?(7分)[38]常用的存儲表示方法有哪幾種?(8分)[39]試舉一個數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算三個方面的內(nèi)容。(16分)[40]簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)
8、構(gòu)。(6分)[41]試問對于下列各種排序方法，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？（1）直接插入排序；（2）希爾排序；（3）快速排序；（4）堆排序；（5）歸并排序；（6）基數(shù)排序。(8分)[42]試問：對初始狀態(tài)如下（長度為n）的各序列進行直接插入排序時，至多需進行多少次關(guān)鍵字間的比較（要求排序后的序列按關(guān)鍵字自小至大順序有序）？（1）關(guān)鍵字（自小至大）順序有序；（key1
