2022年南京大學計算機科學與技術專業《數據結構與算法》科目期末試卷A（有答案）一、選擇題1、下述文件中適合于磁帶存儲的是（）。A.順序文件B.索引文件C.哈希文件D.多關鍵字文件2、下列排序算法中，占用輔助空間最多的是（）。A.歸并排序B.快速排序C.希爾排序D.堆排序3、單鏈表中，增加一個頭結點是為了（）。A.使單鏈表至少有一個結點B.標識表結點中首結點的位置C.方便運算的實現D.說明單鏈表是線性表的鏈式存儲4、循環隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、在下列表述中，正確的是（）A.含有一個或多個空格字符的串稱為空格串B.對n（n>0）個頂點的網，求出權最小的n-1條邊便可構成其最小生成樹C.選擇排序算法是不穩定的D.平衡二叉樹的左右子樹的結點數之差的絕對值不超過l6、下列選項中，不能構成折半查找中關鍵字比較序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4507、已知關鍵字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關鍵字3，調整后的小根堆是（）。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、一個具有1025個結點的二叉樹的高h為（）。A.11B.10C.11至1025之間D.10至1024之間9、設X是樹T中的一個非根結點，B是T所對應的二叉樹。在B中，X是其雙親的右孩子，下列結論正確的是（）。A.在樹T中，X是其雙親的第一個孩子B.在樹T中，X一定無右兄弟C.在樹T中，X一定是葉結點D.在樹T中，X一定有左兄弟10、對序列{15，9，7，8，20，-1，4}用希爾排序方法排序，經一趟后序列變為{15，-1，4，8，20，9，7}則該次采用的增量是（）。A.1B.4C.3D.2二、填空題11、在有n個頂點的有向圖中，每個頂點的度最大可達______。12、N個頂點的連通圖用鄰接矩陣表示時，該矩陣至少有______個非零元素。13、在單鏈表L中，指針P所指結點有后繼結點的條件是______。14、關鍵碼序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照關鍵碼值遞增的次序進行排序，若采用初始步長為4的希爾排序法，則一趟掃描的結果是______；若采用以第一個元素為分界元素的快速排序法，則掃描一趟的結果是______。15、設有兩個算法在同一機器上運行，其執行時聞分別為100n2和2n，要使前者快于后者，n至少為______。16、一棵有n個結點的滿二叉樹有______個度為1的結點、有______個分支（非終端）結點和______個葉子，該滿二叉樹的深度為______。17、設數組A[0..8，1..10]，數組中任一元素A[i，j]均占內存48個二進制位，從首地址2000開始連續存放在主內存里，主內存字長為16位，那么（1） 存放該數組至少需要的單元數是______。（2） 存放數組的第8列的所有元素至少需要的單元數______。（3） 數組按列存儲時，元素A[5，8]的起始地址是______。18、假設一個15階的上三角矩陣A按行優先順序壓縮存儲在一維數組B中，則非零元素A9.9在B中的存儲位置k=______。（注：矩陣元素下標從1開始）三、判斷題19、對磁帶機而言，ISAM是一種方便的文件組織方法（）20、直接訪問文件也能順序訪問，只是一般效率不高。（）21、KMP算法的特點是在模式匹配時指示主串的指針不會變小。（）22、一個廣義表可以為其他廣義表所共享。（）23、深度為k的二叉樹中結點總數小于等于2k-1。（）24、樹形結構中元素之間存在一對多的關系。（）25、外部排序是把外存文件調入內存，可利用內部排序的方法進行排序，因此排序所花的時間取決于內部排序的時間。（）26、快速排序和歸并排序在最壞情況下的比較次數都是O（nlog2n）。（）27、連通圖上各邊權值均不相同，則該圖的最小生成樹是唯一的。（）28、對兩棵具有相同關鍵字集合的而形狀不同的二叉排序樹，按中序遍歷它們得到的序列的順序卻是一致的。（）四、簡答題29、寫出下列排序算法的基本思想，并寫出對序列（23，12，35，47，16，25，36，19，21，16）進行排序時每一趟的結果。30、閱讀下面的算法，說明算法實現的功能。31、已知世界六大城市為：北京(Pe)、紐約(N)、巴黎(Pa)、倫敦(L)、東京(T)、墨西哥(M)，下表給定了這六大城市之間的交通里程：世界六大城市交通里程表(單位：百公里)（1）畫出這六大城市的交通網絡圖。（2）畫出該圖的鄰接表表示法。（3）畫出該圖按權值遞增的順序來構造的最小（代價）生成樹。五、算法設計題32、以順序存儲結構表示串，設計算法。求串s中出現的第一個最長重復子串及其位置并分析算法的時間復雜度。33、試編寫一算法對二叉樹按前序線索化。34、編寫遞歸算法，從大到小輸出給定二叉排序樹中所有關踺字不小于x的數據元素。要求你的算法的時間復雜度為O（log2（x+m）），其中，2為排序樹中所含結點數，m為輸出的關鍵字個數。35、編寫一算法，利用葉結點中的空指針域將所有葉結點鏈接為一個帶有頭結點的雙鏈表，算法返回頭結點的地址。

參考答案一、選擇題1、【答案】A2、【答案】A3、【答案】C4、【答案】A5、【答案】C6、【答案】A7、【答案】A8、【答案】C9、【答案】D10、【答案】B二、填空題11、【答案】2(n-1)12、【答案】2(N-1)13、【答案】P->next!=NULL14、【答案】（Q，A，C，S，Q，D，F，X，R，H，M,Y）；（F，H，C，D，a，A，M，Q，R，S，Y，X）15、【答案】1516、【答案】【解析】滿二叉樹沒有度為1的結點，度為0的結點等于度為2的結點個數+1。17、【答案】270；27；220418、【答案】93三、判斷題19、【答案】×20、【答案】×21、【答案】√22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡答題29、答：此排序為雙向起泡排序：從前向后一趟排序下來得到一個最大值，若其中發生交換，則再從后向前一趟排序，得到一個最小值。第一趟：12，23，35，16，25，36，19，21，16，47第二趟：12，16，23，35，16，25，36，19，21，47第三趟：12，16，23，16，25，35，19，21，36，47第四趟：12，16，16，23，19，25，35，21，36，47第五趟：12，16，16，19，23，25，21，35，36，47第六趟：12，16，16，19，21，23，25，35，36，47第七趟：12，16，16，19，21，23，25，35，36，4730、答：本算法功能是將兩個無頭結點的循環鏈表合并為一個循環鏈表。head1最后一個結點的鏈域指向head2，head2最后一個結點的鏈域指向head1，head1為結果循環鏈表的指針。31、答：(1)這六大城市的交通網絡圖如圖所示：(2)該圖的鄰接表表示法如圖所示：