2023年上海海事大學(xué)計算機科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A(含答案)

2023期末試卷A〔有答案〕一、選擇題1、假設(shè)需在O〔nlog2n〕的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是〔 〕。A.快速排序B.堆排序C. 歸并排序D. 直接插入排序2、哈希文件使用哈希函數(shù)將記錄的關(guān)鍵字值計算轉(zhuǎn)化為記錄的存放地址，由于哈希函數(shù)是一對一的關(guān)系，則選擇好的〔 〕方法是哈希文件的關(guān)鍵。哈希函數(shù)除余法中的質(zhì)數(shù)C.沖突處理D.哈希函數(shù)和沖突處理3、鏈表不具有的特點是〔 〕。A.插入、刪除不需要移動元素B. 可隨機訪問任一元素C.不必事先估量存儲空間D. 所需空間與線性長度成正比4、最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭：front，則隊空的條件是〔 〕。A.〔rear+1〕MODn=frontB.rear=frontC.rear+1=frontD.〔rear-1〕MODn=front5、循環(huán)隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當(dāng)前隊列中的元素數(shù)是〔 〕。A.〔rear-front+m〕%mB.rear-front+1C.rear-front-1D.rear-front6、字符串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”，承受KMP算法進(jìn)展匹配，第一次消滅“失配”〔s!＝t〕時，i＝j(luò)＝5，則下次開頭匹配時，i和j的值分別〔 〕。A．i＝1，j＝0B．i＝5，j＝0C ．i＝5，j＝2D ．i＝6，j＝27、以下表達(dá)中，不符合m階B樹定義要求的是〔 〕。A．根結(jié)點最多有m棵子樹B ．全部葉結(jié)點都在同一層上C．各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列D．葉結(jié)點之間通過指針鏈接反，則該二叉樹肯定滿足〔 〕。A.其中任意一個結(jié)點均無左孩子B.其中任意一個結(jié)點均無右孩子C.其中只有一個葉結(jié)點D.其中度2的結(jié)點最多為一個9、設(shè)X是樹T中的一個非根結(jié)點，B是T所對應(yīng)的二叉樹。在B中，X是其雙親的右孩子，以下結(jié)論正確的選項是〔 〕。在樹T中，X是其雙親的第一個孩子在樹T中，X肯定無右兄弟在T中，X肯定是葉結(jié)點在T中，X肯定有左兄弟10、對關(guān)鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結(jié)果為〔 〕。A.〔2，5，12，16〕26〔60，32，72〕B.〔5，16，2，12〕28〔60，32，72〕C.〔2，16，12，5〕28〔60，32，72〕D.〔5，16，2，12〕28〔32，60，72〕二、填空題11、假設(shè)按關(guān)鍵碼值遞增的挨次依次將關(guān)鍵碼值插入到二叉排序樹中，則對這樣的二叉排序樹檢索時，平均比較次數(shù)為 。12、挨次查找n個元素的挨次表，假設(shè)查找成功，則比較關(guān)鍵字的次數(shù)最多為 次；當(dāng)使用監(jiān)視哨時，假設(shè)查找失敗，則比較關(guān)鍵字的次數(shù)為 。13、對于一個具有n個結(jié)點的單鏈表，在的結(jié)點半p后插入一個結(jié)點的時間簡單度為 ，在給定值為x的結(jié)點后插入一個結(jié)點的時間簡單度為 。14、在一棵m階B-樹中，假設(shè)在某結(jié)點中插入一個關(guān)鍵字而引起該結(jié)點分裂，則此結(jié)點中原有的關(guān)鍵字的個數(shù)是 ；假設(shè)在某結(jié)點中刪除一個關(guān)鍵字而導(dǎo)致結(jié)點合并，則該結(jié)點中原有的關(guān)鍵字的個數(shù)是 。15、設(shè)有兩個算法在同一機器上運行，其執(zhí)行時聞分別為100n2和2n，要使前者快于后者，n至少為 。6、有N個結(jié)存放在向量A[：N結(jié)點為 。17、設(shè)10階對稱矩A承受壓縮存儲方式〔以行為主序存儲：a11=1〕，a85的地址為 。18、在挨次存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是 。三、推斷題?！?〕20、文件系統(tǒng)承受索引構(gòu)造是為了節(jié)約存儲空間?！?〕21、設(shè)模式串的長度為m，目標(biāo)串的長度為n，當(dāng)n≈m且處理只匹配一次的模式時，樸實的匹配〔即子串定位函數(shù)〕算法所花的時間代價可能會更為節(jié)約?！?〕22、串是一種數(shù)據(jù)對象和操作都特別的線性表?！?〕23、深度為k的二叉樹中結(jié)點總數(shù)小于等于2k-1。〔 〕24、中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列?！?〕25、為提高排序速度，進(jìn)展外排序時，必需選用最快的內(nèi)排序算法。〔 〕排序快。〔 〕27、假設(shè)一個有向圖的鄰接矩陣對角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖??！?〕28、對大小均為n的有序表和無序表分別進(jìn)展挨次查找，在等概率查找的狀況下，對于查找成功，它們的平均查找長度是一樣的，而對于查找失敗，它們的平均查找長度是不同的?！?〕四、簡答題29、閱讀下面的算法，說明算法實現(xiàn)的功能。ij30n階下三角矩陣A〔即當(dāng)i＜j時，有aij

=0〕，依據(jù)壓縮存儲的思想，可以將其ij主對角線以下全部元素〔包括主對角線上元素〕依次存放于一維數(shù)組B中，請寫出從第一列開頭承受列序為主序安排方式時B中確定元素a的存放位置的公式。ij316個頂點〔頂點編號0～5〕的有向G，其鄰接矩陣A為上三角矩陣，按行為主序〔行優(yōu)先〕保存在如下的一維數(shù)組中。要求：畫出有向帶權(quán)圖G。求圖G的關(guān)鍵路徑，并計算該關(guān)鍵路徑的長度。五、算法設(shè)計題32、試將以下遞歸過程改寫為非遞歸過程。233、編寫遞歸算法，從大到小輸出給定二叉排序樹中全部關(guān)踺字不小于x的數(shù)據(jù)元素。為〔log〔x+〕〕，其中，2排序結(jié)m2為輸出的關(guān)鍵字個數(shù)。34、寫出一趟快速排序算法。35、請運用快速排序思想，設(shè)計遞歸算法實現(xiàn)n〔n>1〕個不同元素集合中的第f〔1≤i小元素。參考答案一、選擇題1、【答案】C2、【答案】D3、【答案】B4、【答案】B5、【答案】A6、【答案】C7、【答案】D8、【答案】C9、【答案】D10、【答案】B二、填空題11、【答案】〔n+1〕/212、【答案】n；n+113、【答案】O〔1〕；O〔n〕14、【答案】【解析】m【解析】mB-樹除根結(jié)點和葉子結(jié)點外，結(jié)點中關(guān)鍵字個數(shù)最多是m1，最少16、【答案】【解析】最大的分支結(jié)點是最終一個葉子結(jié)點的父結(jié)點。17、【答案】3318、【答案】++a*b3*4-cd；18【解析】中綴式相當(dāng)于中序遍歷，前綴式相當(dāng)于前序遍歷，后綴式相當(dāng)于后序遍歷。三、推斷題19、【答案】×20、【答案】×21、【答案】√22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡答題29、答：本算法功能是將兩個無頭結(jié)點的循環(huán)鏈表合并為一個循環(huán)鏈head1最終一個結(jié)點的鏈域指向head2，head2最終一個結(jié)點的鏈域指向head1，head1為結(jié)果循環(huán)鏈表的指針。30、答：2階下三角矩陣A[i][j]〔1≤i，j≤n，i≥j〕30、答：2階下三角矩陣A[i][j]〔1≤i，j≤n，i≥j〕1列有n個元素，第jn-j+11列到第j-1列是梯形，元素數(shù)為〔n+〔n-j+2〕〔j-1〕/2，而aj列ij上的位置是為i-j+1。所以n階下三角矩A按列存儲，其元素a在一維數(shù)B中的存儲ki和j的關(guān)系為：ij可以看出，第一行至第五行主對角線上方的元素分別為5，4，3，2，1個，由此可以畫出壓縮存儲數(shù)組中的元