2022年馬鞍山學院計算機科學與技術專業《數據結構與算法》科目期末試卷A（有答案）一、選擇題1、已知廣義表LS=（（a，b，c），（d，e，f）），用head和tail數取出LS中原子e的運算是（）。A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、下列排序算法中，占用輔助空間最多的是（）。A.歸并排序B.快速排序C.希爾排序D.堆排序3、以下與數據的存儲結構無關的術語是（）。A.循環隊列B.鏈表C.哈希表D.棧4、在下列表述中，正確的是（）A.含有一個或多個空格字符的串稱為空格串B.對n（n>0）個頂點的網，求出權最小的n-1條邊便可構成其最小生成樹C.選擇排序算法是不穩定的D.平衡二叉樹的左右子樹的結點數之差的絕對值不超過l5、已知串S='aaab'，其next數組值為（）。A.0123B.1123C.1231D.12116、已知關鍵字序列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，197、下列敘述中，不符合m階B樹定義要求的是（）。A．根結點最多有m棵子樹B．所有葉結點都在同一層上C．各結點內關鍵字均升序或降序排列D．葉結點之間通過指針鏈接8、在下述結論中，正確的有（）。①只有一個結點的二叉樹的度為0。②二叉樹的度為2。③二叉樹的左右子樹可任意交換。④深度為K的完全二叉樹的結點個數小于或等于深度相同的滿二叉樹。A.①②③B.⑦③④C.②④D.①④9、有關二叉樹下列說法正確的是（）。A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個結點的度為2D.二叉樹中任何一個結點的度都為210、分別以下列序列構造二叉排序樹，與用其他三個序列所構造的結果不同的是（）。A.（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，20，110，130）D.（100，80，60，90，120，130，110）二、填空題11、設用希爾排序對數組{98，36，-9，0，47，23，1，8，10，7}進行排序，給出的步長（也稱增量序列）依次是4，2，1則排序需______趟，寫出第一趟結束后，數組中數據的排列次序______。12、在有n個頂點的有向圖中，每個頂點的度最大可達______。13、已知有序表為（12，18，24，35，47，50，62，83，90，115，134）當用二分法查找90時，需______次查找成功，查找47時______成功，查找100時，需______次才能確定不成功。14、文件由______組成；記錄由______組成。15、VSAM（虛擬存儲存取方法）文件的優點是：動態地______，不需要文件進行______，并能較快地______進行查找。16、已知一循環隊列的存儲空間為[m..n]，其中n>m，隊頭和隊尾指針分別為front和rear，則此循環隊列判滿的條件是______。17、設有N個結點的完全二叉樹順序存放在向量A[1：N]中，其下標值最大的分支結點為______。18、設有一個空棧，棧頂指針為1000H（十六進制），現有輸入序列為l，2，3，4，5，經過PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，輸出序列是______，而棧頂指針值是______。設棧為順序棧，每個元素占4個字節。三、判斷題19、倒排序文件的優點是維護簡單。（）20、對磁帶機而言，ISAM是一種方便的文件組織方法（）21、隊列和棧都是運算受限的線性表，只允許在表的兩端進行運算。（）22、一個廣義表可以為其他廣義表所共享。（）23、哈夫曼樹度為1的結點數等于度為2和0的結點數之差。（）24、任何二叉樹的后序線索樹進行后序遍歷時都必須用棧。（）25、外部排序是把外存文件調入內存，可利用內部排序的方法進行排序，因此排序所花的時間取決于內部排序的時間。（）26、為提高排序速度，進行外排序時，必須選用最快的內排序算法。（）27、B-樹中所有結點的平衡因子都為零。（）28、在動態存儲管理系統中做空間分配時，最佳適配法與最先適配法相比，前者容易增加閑置空間的碎片。（）四、簡答題29、調用下列C函數f（n），回答下列問題：（1）試指出f（n）值的大小，并寫出，f（n）值的推導過程。（2）假定n=5，試指出，f（5）值的大小和執行，f（5）時的輸出結果。C函數：30、設有n個元素采用起泡排序法進行排序，通常需要進行多少趟排序?對于第J趟起泡通常需要進行多少次關鍵字比較?在程序設計中如何設置判斷條件，有可能使起泡趟數可以減少并且能完成排序。31、設將n（n＞1）個整數存放到一維數組R中。試設計一個在時間和空間兩方面都盡可能高效的算法，將R中存有的序列循左移P（0＜P＜n）個位置，即將R中的數據由（X0，X1，…，Xn－1）變換為（xp，xp＋1，…，xn－1，x0，x1，…，xp－1）。要求：（1） 給出算法的基本設計思想。（2） 根據設計思想，采用C或C＋＋或JAVA語言描述算法，關鍵之處給出注釋。說明你所設計算法的時間復雜度和空間復雜度。五、算法設計題32、設有一個數組中存放了一個無序的關鍵序列K1，K2，…，Kn。現要求將Kn放在將元素排序后的正確位置上，試編寫實現該功能的算法，要求比較關鍵字的次數不超過n（注：用程序實現）。33、一個有向圖G=(V，E)的平方圖G2=(V，E2)滿足下述性質：(U，w)∈E2當且僅當存在某個頂點v∈V，使得(u，v)∈E且(v，w)∈E。寫一個算法從給定的G求出G2，G和G2可分別用兩個鄰接表表示。34、按圖的寬度優先搜索法寫一算法判別以鄰接矩陣存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑(i≠j)35、編寫一算法，利用葉結點中的空指針域將所有葉結點鏈接為一個帶有頭結點的雙鏈表，算法返回頭結點的地址。

參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】D4、【答案】C5、【答案】A6、【答案】A7、【答案】D8、【答案】D9、【答案】B10、【答案】C二、填空題11、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@12、【答案】2(n-1)13、【答案】2；4；3【解析】二分法查找元素次數列表查找100是找到115就停止了。14、【答案】記錄；數據項15、【答案】分配和釋放存儲空間；重組；對插入的記錄@16、【答案】（rear+1）%（n-m+1）==front17、【答案】【解析】最大的分支結點是最后一個葉子結點的父結點。18、【答案】23；100CH三、判斷題19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡答題29、答：（1）第一層for循環判斷n+1次，往下執行n次，第二層for執行次數為（n+（n-1）+（n-2）+…+1），第三層循環體受第一層循環和第二層循環的控制，其執行次數如表1-1所示。執行次數為f(n)=（1+2+…+，n）+（2+3+…+，n）+…+n=n*n（n+1）/2-n（n2-1）/6。（2）在n=5對，f（5）=55，執行過程中，輸出結果為：30、答：n個元素采用起泡排序法進行排序，通常需要進行n-1趟排序。第j趟起泡排序要進行n-j次比較。在一趟排序中，若沒有記錄交換，則表示排序完成。因而，可通過設標記來控制排序結束，下面語句段說明了標記flag的使用。31、答：（1）算法的基本設計思想：先將n個數據由x0，x1，…，xp，…，xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再將數組R中的前n－P個數和后P個數分別原地逆置，最終