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

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

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