2022年西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A(有答案)

2022年西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、哈希文件使用哈希函數(shù)將記錄的關(guān)鍵字值計(jì)算轉(zhuǎn)化為記錄的存放地址，因?yàn)楣：瘮?shù)是一對(duì)一的關(guān)系，則選擇好的（）方法是哈希文件的關(guān)鍵。A.哈希函數(shù)B.除余法中的質(zhì)數(shù)C.沖突處理D.哈希函數(shù)和沖突處理2、下述文件中適合于磁帶存儲(chǔ)的是（）。A.順序文件B.索引文件C.哈希文件D.多關(guān)鍵字文件3、計(jì)算機(jī)算法指的是解決問題的步驟序列，它必須具備（）三個(gè)特性。A.可執(zhí)行性、可移植性、可擴(kuò)充性B.可執(zhí)行性、確定性、有窮性C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性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、已知關(guān)鍵字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后的小根堆是（）。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、若元素a，b，c，d，e，f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行退棧操作，則不可能得到的出棧序列是（）。8、有n（n>0）個(gè)分支結(jié)點(diǎn)的滿二叉樹的深度是（）。A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、下述二叉樹中，哪一種滿足性質(zhì)：從任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序（）。A.二叉排序樹B.哈夫曼樹C.AVL樹D.堆10、數(shù)據(jù)序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的兩趟排序后的結(jié)果。A.選擇排序B.起泡排序C.插入排序D.堆排序二、填空題11、設(shè)m、n均為自然數(shù)，m可表示為一些不超過n的自然數(shù)之和，f（m，n）為這種表示方式的數(shù)目。例f（5，3）=5，有5種表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。①以下是該函數(shù)的程序段，請(qǐng)將未完成的部分填入，使之完整。②執(zhí)行程序，f（6，4）=______。12、無用單元是指______，例______13、以下是用類C語言寫出的算法，該算法將以二叉鏈表存儲(chǔ)的二叉樹中的葉結(jié)點(diǎn)按從左到右的順序鏈成一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，鏈接時(shí)，結(jié)點(diǎn)的Lchild域作為前鏈域，指向結(jié)點(diǎn)的直接前驅(qū)，結(jié)點(diǎn)的Rchild域作為后鏈域，指向結(jié)點(diǎn)的直接后繼。算法中，使用一個(gè)順序棧stack，棧頂指針為top，p，t為輔助指針，head為雙向循環(huán)鏈表的頭指針。試填充算法中的空格，使算法完整。14、文件可按其記錄的類型不同而分成兩類，即______和______文件。15、建立索引文件的目的是______。16、下列程序是快速排序的非遞歸算法，請(qǐng)?zhí)顚戇m當(dāng)?shù)恼Z句，完成該功能。17、一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹有______個(gè)度為1的結(jié)點(diǎn)、有______個(gè)分支（非終端）結(jié)點(diǎn)和______個(gè)葉子，該滿二叉樹的深度為______。18、假設(shè)一個(gè)15階的上三角矩陣A按行優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組B中，則非零元素A9.9在B中的存儲(chǔ)位置k=______。（注：矩陣元素下標(biāo)從1開始）三、判斷題19、倒排文件是對(duì)次關(guān)鍵字建立索引。（）20、直接訪問文件也能順序訪問，只是一般效率不高。（）21、廣義表（（（a，b，c），d，e，f））的長度是4。（）22、串是一種數(shù)據(jù)對(duì)象和操作都特殊的線性表。（）23、二叉樹是一般樹的特殊情形。（）24、用一維數(shù)組存儲(chǔ)二叉樹時(shí)，總是以前序遍歷順序存儲(chǔ)結(jié)點(diǎn)。（）25、快速排序和歸并排序在最壞情況下的比較次數(shù)都是O（nlog2n）。（）26、線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。（）27、對(duì)大小均為n的有序表和無序表分別進(jìn)行順序查找，在等概率查找的情況下，對(duì)于查找成功，它們的平均查找長度是相同的，而對(duì)于查找失敗，它們的平均查找長度是不同的。（）28、無環(huán)有向圖才能進(jìn)行拓?fù)渑判?。（）四、簡答題29、閱讀下面的算法，說明算法實(shí)現(xiàn)的功能。30、將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹（只要求給出轉(zhuǎn)換結(jié)果）。31、二叉樹的帶權(quán)路徑長度（WPL）是二叉樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長度之和，給定一棵二叉樹T，采用二叉鏈表存儲(chǔ)，節(jié)點(diǎn)結(jié)構(gòu)為：其中葉節(jié)點(diǎn)的weight域保存該結(jié)點(diǎn)的非負(fù)權(quán)值。設(shè)root為指向T的根節(jié)點(diǎn)的指針，設(shè)計(jì)求T的WPL的算法。要求：（1）給出算法的基本設(shè)計(jì)思想。（2）使用C或C++語言，給出二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義。（3）根據(jù)設(shè)計(jì)思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。五、算法設(shè)計(jì)題32、設(shè)記錄R[i]的關(guān)鍵字為R[i]。KEY（1≤i≤k），樹結(jié)點(diǎn)T[i]（1≤i≤K-1）指向敗者記錄，T[0]為全勝記錄下標(biāo)。寫一算法產(chǎn)生對(duì)應(yīng)上述R[f]（1≤f≤k）的敗者樹，要求除R[1..k]和Tr[0..k-1]以外，只用O（1）輔助空間。33、已知字符串s1中存放一段英文，寫出算法format（s1，s2，s3，n），將其按給定的長度n格式化成兩端對(duì)齊的字符串s2，其多余的字符送s3。34、設(shè)A和B均為下三角矩陣，每一個(gè)都有n行n列。因此在下三角區(qū)域中各有n（n+1）/個(gè)元素。另設(shè)有一個(gè)二維數(shù)組C，它有n行n+1列。試設(shè)計(jì)一個(gè)方案，將兩個(gè)矩陣A和B中的下三角區(qū)域元素存放于同一個(gè)C中。要求將A的下三角區(qū)域中的元素存放于C的下三角區(qū)域中，B的下三角區(qū)域中的元素轉(zhuǎn)置后存放于C的上三角區(qū)域中。并給出計(jì)算A的矩陣元素aij，和B的矩陣元素bij在C中的存放位置下標(biāo)的公式。35、在輸入數(shù)據(jù)無序的情況下，建立一個(gè)數(shù)據(jù)值為整型的遞增有序的順序存儲(chǔ)線性表L，且要求當(dāng)輸入相同數(shù)據(jù)值時(shí)，線性表中不能存在數(shù)據(jù)值相同的數(shù)據(jù)元素，試寫出其算法。順序存儲(chǔ)結(jié)構(gòu)的線性表描述為：

參考答案一、選擇題1、【答案】D2、【答案】A3、【答案】B4、【答案】B5、【答案】A6、【答案】A7、【答案】D8、【答案】C9、【答案】D10、【答案】C二、填空題11、【答案】①1；1；f（m，n-1）；n②912、【答案】用戶不再使用而系統(tǒng)沒有回收的結(jié)構(gòu)和變量；p=ma11oc（size）;…,p=nu1113、【答案】p->Rchild=t；t->Lchild=p；p=t；t->Rchild!=null；t->Rchild；t->Lchild!=null；t->Lchild；p->Rchild=head；head->Lchild=p14、【答案】操作系統(tǒng)文件；數(shù)據(jù)庫15、【答案】提高查找速度16、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。17、【答案】【解析】滿二叉樹沒有度為1的結(jié)點(diǎn)，度為0的結(jié)點(diǎn)等于度為2的結(jié)點(diǎn)個(gè)數(shù)+1。18、【答案】93三、判斷題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、答：森林轉(zhuǎn)換為二叉樹分以下三步：連線（將兄弟結(jié)點(diǎn)相連，各樹的根看作兄弟）。切線（保留最左邊子女為獨(dú)生子女，將其他子女分支切掉）。旋轉(zhuǎn)（以最左邊樹的根為軸，順時(shí)針向下旋轉(zhuǎn)45度）。所以由上面三棵樹轉(zhuǎn)換得到的二叉樹如