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

2022年吉首大學張家界學院計算機科學與技術專業(yè)《數(shù)據(jù)結構與算法》科目期末試卷A（有答案）一、選擇題1、已知廣義表LS=（（a，b，c），（d，e，f）），用head和tail數(shù)取出LS中原子e的運算是（）。A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、用有向無環(huán)圖描述表達式(A+B)*((A+B)／/A)，至少需要頂點的數(shù)目為（）。A.5B.6C.8D.93、鏈表不具有的特點是（）。A.插入、刪除不需要移動元素B.可隨機訪問任一元素C.不必事先估計存儲空間D.所需空間與線性長度成正比4、最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭：front，則隊空的條件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、有六個元素6，5，4，3，2，1順序入棧，下列不是合法的出棧序列的是（）。A.543612B.453126C.346521D.2341566、下列選項中，不能構成折半查找中關鍵字比較序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4507、下列敘述中，不符合m階B樹定義要求的是（）。A．根結點最多有m棵子樹B．所有葉結點都在同一層上C．各結點內關鍵字均升序或降序排列D．葉結點之間通過指針鏈接8、在下述結論中，正確的有（）。①只有一個結點的二叉樹的度為0。②二叉樹的度為2。③二叉樹的左右子樹可任意交換。④深度為K的完全二叉樹的結點個數(shù)小于或等于深度相同的滿二叉樹。A.①②③B.⑦③④C.②④D.①④9、下述二叉樹中，哪一種滿足性質：從任一結點出發(fā)到根的路徑上所經過的結點序列按其關鍵字有序（）。A.二叉排序樹B.哈夫曼樹C.AVL樹D.堆10、對關鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結果為（）。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ù)組{98，36，-9，0，47，23，1，8，10，7}進行排序，給出的步長（也稱增量序列）依次是4，2，1則排序需______趟，寫出第一趟結束后，數(shù)組中數(shù)據(jù)的排列次序______。12、屬于不穩(wěn)定排序的有______。13、在單鏈表L中，指針P所指結點有后繼結點的條件是______。14、外排序的基本操作過程是______和______。15、索引順序文件既可以順序存取，也可以______存取。16、每一棵樹都能唯一地轉換為它所對應的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列是______。設上述二叉樹是由某棵樹轉換而成，則該樹的前序序列是______。17、已知一循環(huán)隊列的存儲空間為[m..n]，其中n>m，隊頭和隊尾指針分別為front和rear，則此循環(huán)隊列判滿的條件是______。18、設有一個10階對稱矩陣A采用壓縮存儲方式（以行為主序存儲：a11=1），則a85的地址為______。三、判斷題19、倒排文件的目的是為了多關鍵字查找。（）20、直接訪問文件也能順序訪問，只是一般效率不高。（）21、循環(huán)隊列也存在空間溢出問題。（）22、二維以上的數(shù)組其實是一種特殊的廣義表。（）23、用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結點。（）24、哈夫曼樹度為1的結點數(shù)等于度為2和0的結點數(shù)之差。（）25、數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系。（）26、算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。（）27、在動態(tài)存儲管理系統(tǒng)中做空間分配時，最佳適配法與最先適配法相比，前者容易增加閑置空間的碎片。（）28、采用線性探測法處理散列時的沖突，當從哈希表刪除一個記錄時，不應將這個記錄的所在位置置空，因為這會影響以后的查找。（）四、簡答題29、閱讀下面的算法，說明算法實現(xiàn)的功能。30、對于具有n個葉結點且所有非葉結點都有左、右孩子的二叉樹。(1)試問這種二叉樹的結點總數(shù)是多少?(2)試證明2-（li-1）=1。其中：li表示第i個葉結點所在的層號（設根結點所在層號為1）。31、已知圖的鄰接矩陣為：當用鄰接表作為圖的存儲結構，且鄰接點都按序號從大到小排列時，試寫出：(1)以頂點V1為出發(fā)點的唯一的深度優(yōu)先遍歷序列。當用鄰接表作為圖的存儲結構，且鄰接點都按序號從大到小排列時，試寫出：(1)以頂點V1為出發(fā)點的唯一的深度優(yōu)先遍歷序列。(2)以頂點V1為出發(fā)點的唯一的廣度優(yōu)先遍歷序列。(3)該圖唯一的拓撲有序序列。五、算法設計題32、設有一個數(shù)組中存放了一個無序的關鍵序列K1，K2，…，Kn?，F(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實現(xiàn)該功能的算法，要求比較關鍵字的次數(shù)不超過n（注：用程序實現(xiàn)）。33、設A和B均為下三角矩陣，每一個都有n行n列。因此在下三角區(qū)域中各有n（n+1）/個元素。另設有一個二維數(shù)組C，它有n行n+1列。試設計一個方案，將兩個矩陣A和B中的下三角區(qū)域元素存放于同一個C中。要求將A的下三角區(qū)域中的元素存放于C的下三角區(qū)域中，B的下三角區(qū)域中的元素轉置后存放于C的上三角區(qū)域中。并給出計算A的矩陣元素aij，和B的矩陣元素bij在C中的存放位置下標的公式。34、輔助地址表的排序是不改變結點物理位置的排序。輔助地址表實際上是一組指針，用它來指出結點排序后的邏輯順序地址。設用K[1]，K[2]，…，K[n]表示n個結點的值，用T[1]，T[2]，…，T[n]表示輔助地址表。初始時T[i]：=i，在排序中，凡需對結點交換就用它的地址來進行。例如當n=3時，對K（31，11，19）則有T（2，3，1）。試編寫實現(xiàn)輔助地址表排序（按非遞減序）算法的語句序列。35、以三元組表存儲的稀疏矩陣A，B非零元個數(shù)分別為m和n。試用類PASCAL語言編寫時間復雜度為O（m+n）的算法將矩陣B加到矩陣A上去。A的空間足夠大，不另加輔助空間。要求描述所用結構。

參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】B4、【答案】B5、【答案】C6、【答案】A7、【答案】D8、【答案】D9、【答案】D10、【答案】B二、填空題11、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@12、【答案】希爾排序、簡單選擇排序、快速排序、堆排序等13、【答案】P->next!=NULL14、【答案】生成有序歸并段（順串）；歸并15、【答案】隨機16、【答案】FEGHDCB；BEF【解析】樹的前序序列對應二叉樹的前序序列，該二叉樹轉換成森林時含三棵樹，其第一棵樹的前序是BEF。17、【答案】（rear+1）%（n-m+1）==front18、【答案】33三、判斷題19、【答案】√20、【答案】×21、【答案】√22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡答題29、答：本算法功能是將兩個無頭結點的循環(huán)鏈表合并為一個循環(huán)鏈表。head1最后一個結點的鏈域指向head2，head2最后一個結點的鏈域指向head1，head1為結果循環(huán)鏈表的指針。30、答：（1）根據(jù)二叉樹中度為2的結點個數(shù)等于葉結點個數(shù)減1的性質，故具有n個葉結點且非葉子結點均有左子樹的二叉樹的結點數(shù)是2n-1。（2）證明：當i=1時，2-（1-1）=20=1，公式成立。設當i=n-1時公式成立，證明當i=n時公式仍成立。設某葉結點的層號為t，當將該結點變?yōu)閮炔拷Y點，從而再增加兩個葉結點時，這兩個葉結點的層號都是t+1，對于公式的變化，是減少了一個原來的葉結點，增加了兩個新葉結點，反映到公式中，因為2-（t-1）=2-（t+1-1）+