2022年廣東技術(shù)師范大學計算機科學與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A(有答案)

2022年廣東技術(shù)師范大學計算機科學與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、將線性表的數(shù)據(jù)元素進行擴充，允許帶結(jié)構(gòu)的線性表是（）。A.串B.樹C.廣義表D.棧2、有一個100*90的稀疏矩陣，非0元素有10個，設(shè)每個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是（）。A.60B.66C.18000D.333、若線性表最常用的操作是存取第i個元素及其前驅(qū)和后繼元素的值，為節(jié)省時間應(yīng)采用的存儲方式（）。A.單鏈表B.雙向鏈表C.單循環(huán)鏈表D.順序表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、循環(huán)隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front6、下列關(guān)于無向連通圖特性的敘述中，正確的是（）。Ⅰ．所有的頂點的度之和為偶數(shù)Ⅱ．邊數(shù)大于頂點個數(shù)減1Ⅲ．至少有一個頂點的度為1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ7、下列選項中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4508、下述二叉樹中，哪一種滿足性質(zhì)：從任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序（）。A.二叉排序樹B.哈夫曼樹C.AVL樹D.堆9、一個具有1025個結(jié)點的二叉樹的高h為（）。A.11B.10C.11至1025之間D.10至1024之間10、在文件“局部有序”或文件長度較小的情況下，最佳內(nèi)部排序的方法是（）。A.直接插入排序B.起泡排序C.簡單選擇排序D.快速排序二、填空題11、設(shè)用希爾排序?qū)?shù)組{98，36，-9，0，47，23，1，8，10，7}進行排序，給出的步長（也稱增量序列）依次是4，2，1則排序需______趟，寫出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序______。12、下面程序的功能是用遞歸算法將一個整數(shù)按逆序存放到一個字符數(shù)組中。如123存放成321。請?zhí)羁眨?3、按LSD進行關(guān)鍵字排序，除最次位關(guān)鍵字之外，對每個關(guān)鍵字進行排序時，只能用______的排序方法。14、對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點半p后插入一個新結(jié)點的時間復雜度為______，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復雜度為______。15、設(shè)單鏈表的結(jié)點結(jié)構(gòu)為（data，next），next為指針域，已知指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點，若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行以下語句：______16、設(shè)正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復雜度為______。17、設(shè)有一個10階對稱矩陣A采用壓縮存儲方式（以行為主序存儲：a11=1），則a85的地址為______。18、已知一循環(huán)隊列的存儲空間為[m..n]，其中n>m，隊頭和隊尾指針分別為front和rear，則此循環(huán)隊列判滿的條件是______。三、判斷題19、對磁帶機而言，ISAM是一種方便的文件組織方法（）20、文件系統(tǒng)采用索引結(jié)構(gòu)是為了節(jié)省存儲空間。（）21、棧的輸入序列是1，2，…，n，輸出序列是a1，a2，…，an若ai=n（1≤i≤n）則有：ai>ai+1>…>an。（）22、廣義表（（（a，b，c），d，e，f））的長度是4。（）23、深度為k的二叉樹中結(jié)點總數(shù)小于等于2k-1。（）24、哈夫曼樹度為1的結(jié)點數(shù)等于度為2和0的結(jié)點數(shù)之差。（）25、排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（）26、歸并排序輔助存儲為O（1）。（）27、當改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動后，必將產(chǎn)生不同的關(guān)鍵路徑。（）28、若一個有向圖的鄰接矩陣對角線以下元素均為零，則該圖的拓撲有序序列必定存在。（）四、簡答題29、s是字符數(shù)組，s[0]中存放的是該字符串的有效長度，假設(shè)s[1..7]中字符串的內(nèi)容為"abcabaa"，說明下列程序的功能及執(zhí)行結(jié)果。30、對于具有n個葉結(jié)點且所有非葉結(jié)點都有左、右孩子的二叉樹。(1)試問這種二叉樹的結(jié)點總數(shù)是多少?(2)試證明2-（li-1）=1。其中：li表示第i個葉結(jié)點所在的層號（設(shè)根結(jié)點所在層號為1）。31、對下面的關(guān)鍵字集{30，15，21，40，25，26，36，37}若查找表的裝填因子為0.8，采用線性探測再哈希方法解決沖突，做：（1）設(shè)計哈希函數(shù)；（2）畫出哈希表；（3）計算查找成功和查找失敗的平均查找長度；（4）寫出將哈希表中某個數(shù)據(jù)元素刪除的算法。五、算法設(shè)計題32、若x和y是兩個采用順序結(jié)構(gòu)存儲的串，編寫一個比較兩個串是否相等的函數(shù)。33、請編寫完整的程序。如果矩陣A中存在這樣的一個元素A[i，j]滿足條件：A[i，j]是第i行中值最小的元素，且又是第j列中值最大的元素，則稱之為該矩陣的一個馬鞍點。請編程計算出m*n的矩陣A的所有馬鞍點。34、試設(shè)計一個C語言算法（或C語言程序）：用單鏈表做存儲結(jié)構(gòu)，以回車符為結(jié)束標志，輸入一個任意長度的字符串，然后判斷該字符串是否為“回文”（正向讀和反向讀時，串值相同的字符串稱為“回文”），輸出信息“Yes”或“NO”；最后刪除字符串并釋放全部空間。例如：若輸入“ABCD12321DCBA”是回文，則輸出“Yes”。若輸入“ABCD123DCBA”，不是回文，則輸出“NO”。要求：定義相關(guān)數(shù)據(jù)類型，不得使用數(shù)組（順序表）做字符串的存儲結(jié)構(gòu)和輔助存儲空間。假定字符串的長度為n，試分析上述算法的時間復雜度。35、二路插入排序是將待排關(guān)鍵字序列r[1..n]中關(guān)鍵字分二路分別按序插入到輔助向量d[1..n]前半部和后半部（注：向量d可視為循環(huán)表），其原則為，先將r[1]賦給d[1]，再從r[2]記錄開始分二路插入。編寫實現(xiàn)2-路插入排序算法。

參考答案一、選擇題1、【答案】C2、【答案】B3、【答案】D4、【答案】A5、【答案】A6、【答案】A7、【答案】A8、【答案】D9、【答案】C10、【答案】A二、填空題11、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@12、【答案】a+1；n%10【解析】通過遞歸算法，首先找到最高位的值，將其放到str對應(yīng)的數(shù)組中，依次反向獲取從高位到地位的值，將其放到數(shù)組中，完成了將整數(shù)逆序放到一個字符數(shù)組中。13、【答案】穩(wěn)定14、【答案】O（1）；O（n）15、【答案】py->next=px->next；px->next=py16、【答案】O（m+n）17、【答案】3318、【答案】（rear+1）%（n-m+1）==front三、判斷題19、【答案】×20、【答案】×21、【答案】×22、【答案】×23、【答案】√24、【答案】×25、【答案】×26、【答案】×27、【答案】×28、【答案】√四、簡答題29、答：本程序的功能是求字符串的nextval函數(shù)，程序執(zhí)行結(jié)果是0110132。30、答：（1）根據(jù)二叉樹中度為2的結(jié)點個數(shù)等于葉結(jié)點個數(shù)減1的性質(zhì)，故具有n個葉結(jié)點且非葉子結(jié)點均有左子樹的二叉樹的結(jié)點數(shù)是2n-1。（2）證明：當i=1時，2-（1-1）=20=1，公式成立。設(shè)當i=n-1時公式成立，證明當i=n時公式仍成立。設(shè)某葉結(jié)點的層號為t，當將該結(jié)點變?yōu)閮?nèi)部結(jié)點，從而再增加兩個葉結(jié)點時，這兩個葉結(jié)點的層號都是t+1，對于公式的變化，是減少了一個原來的葉結(jié)點，增加了兩個新葉結(jié)點，反映到公式中，因為2-（t-1）=2-（t+1-1）+2-（t+1-1），所以結(jié)果不變，這就證明當i=n時公式仍成立。證畢。31、答：（1）由于裝填因子為0.8，關(guān)鍵字有8個，所以表長為8/0.8