2022年濟南大學計算機科學與技術專業(yè)《數(shù)據(jù)結構與算法》科目期末試卷A(有答案)

2022年濟南大學計算機科學與技術專業(yè)《數(shù)據(jù)結構與算法》科目期末試卷A（有答案）一、選擇題1、若需在O（nlog2n）的時間內完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。A.快速排序B.堆排序C.歸并排序D.直接插入排序2、哈希文件使用哈希函數(shù)將記錄的關鍵字值計算轉化為記錄的存放地址，因為哈希函數(shù)是一對一的關系，則選擇好的（）方法是哈希文件的關鍵。A.哈希函數(shù)B.除余法中的質數(shù)C.沖突處理D.哈希函數(shù)和沖突處理3、靜態(tài)鏈表中指針表示的是（）。A.下一元素的地址B.內存儲器的地址C.下一元素在數(shù)組中的位置D.左鏈或右鏈指向的元素的地址4、循環(huán)隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、動態(tài)存儲管理系統(tǒng)中，通?？捎校ǎ┓N不同的分配策略。A.1B.2C.3D.46、循環(huán)隊列放在一維數(shù)組A中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設隊列兩端均可進行入隊和出隊操作，隊列中最多能容納M－1個元素。初始時為空，下列判斷隊空和隊滿的條件中，正確的是（）。A．隊空：end1＝＝end2；隊滿：end1＝＝（end2＋1）modMB．隊空：end1＝＝end2；隊滿：end2＝＝（end1＋1）mod（M－1）C．隊空：end2＝＝（end1＋1）modM；隊滿：end1＝＝（end2＋1）modMD．隊空：end1＝＝（end2＋1）modM；隊滿：end2＝＝（end1＋1）mod（M－1）7、下列關于無向連通圖特性的敘述中，正確的是（）。Ⅰ．所有的頂點的度之和為偶數(shù)Ⅱ．邊數(shù)大于頂點個數(shù)減1Ⅲ．至少有一個頂點的度為1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ8、每個結點的度或者為0或者為2的二叉樹稱為正則二叉樹。n個結點的正則二叉樹中有（）個葉子。A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/29、已知一棵二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBAEDF，則后序遍歷結果為（）。A.CBEFDAB.FEDCBAC.CBEDFAD.不定10、下列二叉排序樹中查找效率最高的是（）。A.平衡二叉樹B.二叉查找樹C.沒有左子樹的二叉排序樹D.沒有右子樹的二叉排序樹二、填空題11、如果按關鍵碼值遞增的順序依次將關鍵碼值插入到二叉排序樹中，則對這樣的二叉排序樹檢索時，平均比較次數(shù)為______。12、N個頂點的連通圖用鄰接矩陣表示時，該矩陣至少有______個非零元素。13、數(shù)據(jù)結構中評價算法的兩個重要指標是______。14、設單鏈表的結點結構為（data，next），next為指針域，已知指針px指向單鏈表中data為x的結點，指針py指向data為y的新結點，若將結點y插入結點x之后，則需要執(zhí)行以下語句：______15、按LSD進行關鍵字排序，除最次位關鍵字之外，對每個關鍵字進行排序時，只能用______的排序方法。16、設正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復雜度為______。17、假設一個15階的上三角矩陣A按行優(yōu)先順序壓縮存儲在一維數(shù)組B中，則非零元素A9.9在B中的存儲位置k=______。（注：矩陣元素下標從1開始）18、一棵有n個結點的滿二叉樹有______個度為1的結點、有______個分支（非終端）結點和______個葉子，該滿二叉樹的深度為______。三、判斷題19、倒排序文件的優(yōu)點是維護簡單。（）20、直接訪問文件也能順序訪問，只是一般效率不高。（）21、數(shù)組不適合作為任何二叉樹的存儲結構。（）22、串是一種數(shù)據(jù)對象和操作都特殊的線性表。（）23、哈夫曼樹度為1的結點數(shù)等于度為2和0的結點數(shù)之差。（）24、二叉樹是一般樹的特殊情形。（）25、若中序遍歷平衡的二叉排序樹，可得到排好序的關鍵碼序列。（）26、歸并排序輔助存儲為O（1）。（）27、B-樹中所有結點的平衡因子都為零。（）28、對大小均為n的有序表和無序表分別進行順序查找，在等概率查找的情況下，對于查找成功，它們的平均查找長度是相同的，而對于查找失敗，它們的平均查找長度是不同的。（）四、簡答題29、給出一組關鍵字：29，18，25，47，58，12，51，10，分別寫出按下列各種排序方法進行排序時的變化過程：（1） 歸并排序，每歸并一次書寫一個次序。（2） 快速排序，每劃分一次書寫一個次序。（3） 堆排序，先建成一個堆，然后每從堆頂取下一個元素后，將堆調整一次。30、三維數(shù)組A[1..10，-2..6，2..8]的每個元素的長度為4個字節(jié)，試問該數(shù)組要占多少個字節(jié)的存儲空間?如果數(shù)組元素以行優(yōu)先的順序存儲，設第一個元素的首地址是100，試求元素A[5，0，7]的存儲首地址。31、用單鏈表保存m個整數(shù)，節(jié)點的結構為（data，link），且|data|＜n（n為正整數(shù)）?，F(xiàn)要求設計一個時間復雜度盡可能高效地算法，對于鏈表中絕對值相等的節(jié)點，僅保留第一次出現(xiàn)的節(jié)點而刪除其余絕對值相等的節(jié)點。例如若給定的單鏈表head如下刪除節(jié)點后的head為要求（1）給出算法的基本思想（2）使用C或C＋＋語言，給出單鏈表節(jié)點的數(shù)據(jù)類型定義。（3）根據(jù)設計思想，采用C或C＋＋語言描述算法，關鍵之處給出注釋。說明所涉及算法的時間復雜度和空間復雜度。五、算法設計題32、在一個循環(huán)鏈隊中只有尾指針（記為rear，結點結構為數(shù)據(jù)域data，指針域next），請給出這種隊列的入隊和出隊操作的實現(xiàn)過程。33、已知深度為h的二叉樹，以一維數(shù)組BT[0..2h-2]作為其存儲結構，試編寫一算法，求該二叉樹中葉結點的個數(shù)，為簡單起見，設二叉樹中元素結點為非負整數(shù)，要求寫出算法基本思想及相應的算法。34、一個有向圖G=(V，E)的平方圖G2=(V，E2)滿足下述性質：(U，w)∈E2當且僅當存在某個頂點v∈V，使得(u，v)∈E且(v，w)∈E。寫一個算法從給定的G求出G2，G和G2可分別用兩個鄰接表表示。35、已知兩個定長數(shù)組，它們分別存放兩個非降序有序序列，請編寫程序把第二個數(shù)組序列中的數(shù)逐個插入到前一個數(shù)組序列中，完成后兩個數(shù)組中的數(shù)分別有序（非降序）并且第一數(shù)組中所有的數(shù)都不大于第二個數(shù)組中的任意一個數(shù)。注意，不能另開辟數(shù)組，也不能對任意一個數(shù)組進行排序操作。例如：第一個數(shù)組為：4，12，28第二個數(shù)組為：1，7，9，29，45輸出結果為：l，4，7……第一個數(shù)組9，12，28，29，45……第二個數(shù)組

參考答案一、選擇題1、【答案】C2、【答案】D3、【答案】C4、【答案】A5、【答案】C6、【答案】A7、【答案】A8、【答案】D9、【答案】A10、【答案】A二、填空題11、【答案】（n+1）/212、【答案】2(N-1)13、【答案】算法的時間復雜度和空間復雜度14、【答案】py->next=px->next；px->next=py15、【答案】穩(wěn)定16、【答案】O（m+n）17、【答案】9318、【答案】【解析】滿二叉樹沒有度為1的結點，度為0的結點等于度為2的結點個數(shù)+1。三、判斷題19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】√26、【答案】×27、【答案】√28、【答案】√四、簡答題29、答：（1）2一路歸并第一趟：18，29，25，47，12，58，10，51。第二趟：18，25，29，47，10，12，51，58。第三趟：10，12，18，25，29，47，51，58。（2）快速排序第一趟：10，18，25，12，29，58，51，47。第二趟：10，18，25，12，29，47，51，88。第三趟：10，12，18，25，29，47，51，88。（3）堆排序建大堆：58，47，51，29，18，12，25，10。51，47，25，29，18，12，10，58。47，29，25，10，18，12，51，58。29，18，25，10，12，47，51，58。25，18，12，10，29，47，51，58。18，10，12，25，29，47，51，58。12，10，18，25，29，47，51，58。10，12，18，25，29，47，51，58。30、答：數(shù)組占的存儲字節(jié)數(shù)=10*9*7*4=2520；A[5，0，7]的存儲地址=100+[4*9*7+2*7+5]*4=1184。31、答：（1）算法思想：算法的核心思想是用空間換時間。定義一個大小為n的布爾數(shù)組flag，初始時所有的元素都賦值為false，用來標識遍歷過程中是否出現(xiàn)元素絕對值為flag的節(jié)點。然后遍歷鏈表，遍歷過程中，每一個