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

2022年內蒙古大學計算機科學與技術專業(yè)《數(shù)據(jù)結構與算法》科目期末試卷A（有答案）一、選擇題1、用數(shù)組r存儲靜態(tài)鏈表，結點的next域指向后繼，工作指針j指向鏈中結點，使j沿鏈移動的操作為（）。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、將兩個各有N個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（）。A.NB.2N-1C.2ND.N-13、某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表4、已知有向圖G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓撲序列是（）。A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、在用鄰接表表示圖時，拓撲排序算法時間復雜度為（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、已知關鍵字序列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、若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結點的孩子結點（）。A．只有eB．有e、bC．有e、cD．無法確定8、一個具有1025個結點的二叉樹的高h為（）。A.11B.10C.11至1025之間D.10至1024之間9、一棵非空的二叉樹的前序序列和后序序列正好相反，則該二叉樹一定滿足（）。A.其中任意一個結點均無左孩子B.其中任意一個結點均無右孩子C.其中只有一個葉結點D.其中度為2的結點最多為一個10、數(shù)據(jù)序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的兩趟排序后的結果。A.選擇排序B.起泡排序C.插入排序D.堆排序二、填空題11、設用希爾排序對數(shù)組{98，36，-9，0，47，23，1，8，10，7}進行排序，給出的步長（也稱增量序列）依次是4，2，1則排序需______趟，寫出第一趟結束后，數(shù)組中數(shù)據(jù)的排列次序______。12、如果按關鍵碼值遞增的順序依次將關鍵碼值插入到二叉排序樹中，則對這樣的二叉排序樹檢索時，平均比較次數(shù)為______。13、在單鏈表L中，指針P所指結點有后繼結點的條件是______。14、建立索引文件的目的是______。15、索引順序文件既可以順序存取，也可以______存取。16、一棵有n個結點的滿二叉樹有______個度為1的結點、有______個分支（非終端）結點和______個葉子，該滿二叉樹的深度為______。17、設有N個結點的完全二叉樹順序存放在向量A[1：N]中，其下標值最大的分支結點為______。18、設T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為______，又稱P為______。三、判斷題19、倒排文件的目的是為了多關鍵字查找。（）20、倒排文件是對次關鍵字建立索引。（）21、KMP算法的特點是在模式匹配時指示主串的指針不會變小。（）22、棧的輸入序列是1，2，…，n，輸出序列是a1，a2，…，an若ai=n（1≤i≤n）則有：ai>ai+1>…>an。（）23、用一維數(shù)組存儲二叉樹時，總是以前序遍歷順序存儲結點。（）24、哈夫曼樹度為1的結點數(shù)等于度為2和0的結點數(shù)之差。（）25、算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。（）26、歸并排序輔助存儲為O（1）。（）27、在索引順序表中，實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關，而且與每塊中元素個數(shù)有關。（）28、B-樹中所有結點的平衡因子都為零。（）四、簡答題29、設目標為t=‘a(chǎn)bcaabbabcabaacbacba’，模式為P=‘a(chǎn)bcabaa’（1）計算模式p的nextval函數(shù)值。（2）不寫出算法，只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。30、調用下列C函數(shù)f（n），回答下列問題：（1）試指出f（n）值的大小，并寫出，f（n）值的推導過程。（2）假定n=5，試指出，f（5）值的大小和執(zhí)行，f（5）時的輸出結果。C函數(shù)：31、二叉樹的帶權路徑長度（WPL）是二叉樹中所有葉結點的帶權路徑長度之和，給定一棵二叉樹T，采用二叉鏈表存儲，節(jié)點結構為：其中葉節(jié)點的weight域保存該結點的非負權值。設root為指向T的根節(jié)點的指針，設計求T的WPL的算法。要求：（1）給出算法的基本設計思想。（2）使用C或C++語言，給出二叉樹結點的數(shù)據(jù)類型定義。（3）根據(jù)設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。五、算法設計題32、對給定關鍵字序號j（1<j<n），要求在無序記錄A[1..n]中找到關鍵字從小到大排在第j位上的記錄，寫一個算法利用快速排序的劃分思想實現(xiàn)上述查找（要求用最少的時間和最少的空間）。例如：給定無序關鍵字{7，5，1，6，2，8，9，3}，當j=4時，找到的關鍵字應是5。33、線性表中元素存放在向量A（1，…，l）中，元素是整型數(shù)。試寫出遞歸算法求出A中的最大和最小元素。34、假定用兩個一維數(shù)組L[N]和R[N]作為有N個結點1，2，…，N的二叉樹的存儲結構。L[i]和R[i]分別指示結點i的左兒子和右兒子，L[i]=0（R[i]=0）表示i的左（右）兒子為空。試寫一個算法，由L和R建立一個一維數(shù)組T[n]，使T[i]存放結點i的父親；然后再寫一個判別結點u是否為結點V的后代的算法。35、編寫算法，將自然數(shù)l～n2按“蛇形”填n×n矩陣中。例（1～42）如圖所示（用程序實現(xiàn)）。

參考答案一、選擇題1、【答案】A2、【答案】A3、【答案】D4、【答案】A5、【答案】B6、【答案】A7、【答案】A8、【答案】C9、【答案】C10、【答案】C二、填空題11、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@12、【答案】（n+1）/213、【答案】P->next!=NULL14、【答案】提高查找速度15、【答案】隨機16、【答案】【解析】滿二叉樹沒有度為1的結點，度為0的結點等于度為2的結點個數(shù)+1。17、【答案】【解析】最大的分支結點是最后一個葉子結點的父結點。18、【答案】模式匹配；模式串三、判斷題19、【答案】√20、【答案】√21、【答案】√22、【答案】×23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡答題29、答：（1）p的nextval函數(shù)值為0110132（p的next函數(shù)值為0111232）。（2）利用KMP（改進的nextval）算法，每趟匹配過程如下：30、答：（1）第一層for循環(huán)判斷n+1次，往下執(zhí)行n次，第二層for執(zhí)行次數(shù)為（n+（n-1）+（n-2）+…+1），第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如表1-1所示。執(zhí)行次數(shù)為f(n)=（1+2+…+，n）+（2+3+…+，n）+…+n=n*n（n+1）/2-n（n2-1）/6。（2）在n=5對，f（5）=55，執(zhí)行過程中，輸出結果為：31、答