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