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

2022年蘭州大學(xué)計算機科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、哈希文件使用哈希函數(shù)將記錄的關(guān)鍵字值計算轉(zhuǎn)化為記錄的存放地址，因為哈希函數(shù)是一對一的關(guān)系，則選擇好的（）方法是哈希文件的關(guān)鍵。A.哈希函數(shù)B.除余法中的質(zhì)數(shù)C.沖突處理D.哈希函數(shù)和沖突處理2、下列排序算法中，占用輔助空間最多的是（）。A.歸并排序B.快速排序C.希爾排序D.堆排序3、若線性表最常用的操作是存取第i個元素及其前驅(qū)和后繼元素的值，為節(jié)省時間應(yīng)采用的存儲方式（）。A.單鏈表B.雙向鏈表C.單循環(huán)鏈表D.順序表4、用不帶頭結(jié)點的單鏈表存儲隊列，其隊頭指針指向隊頭結(jié)點，隊尾指針指向隊尾結(jié)點，則在進行出隊操作時（）。A.僅修改隊頭指針B.僅修改隊尾指針C.隊頭、隊尾指針都可能要修改D.隊頭、隊尾指針都要修改5、動態(tài)存儲管理系統(tǒng)中，通?？捎校ǎ┓N不同的分配策略。A.1B.2C.3D.46、下列選項中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4507、排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束時都至少能夠確定一個元素最終位置的方法是（）。Ⅰ．簡單選擇排序Ⅱ．希爾排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路歸并排序A．僅Ⅰ、Ⅲ、ⅣB．僅Ⅰ、Ⅱ、ⅢC．僅Ⅱ、Ⅲ、ⅣD．僅Ⅲ、Ⅳ、Ⅴ8、已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷結(jié)果為（）。A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、一棵非空的二叉樹的前序序列和后序序列正好相反，則該二叉樹一定滿足（）。A.其中任意一個結(jié)點均無左孩子B.其中任意一個結(jié)點均無右孩子C.其中只有一個葉結(jié)點D.其中度為2的結(jié)點最多為一個10、對序列{15，9，7，8，20，-1，4}用希爾排序方法排序，經(jīng)一趟后序列變?yōu)閧15，-1，4，8，20，9，7}則該次采用的增量是（）。A.1B.4C.3D.2二、填空題11、有向圖G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用<a，b，d>三元組表示弧<a，b>及弧上的權(quán)d。E(G)為E(G)=｛<0，5，100>，<0，2，10>，<1，2，5>，<0，4，30>，<4，5，60>，<3，5，10>，<2，3，50>，<4，3，20>｝，則從源點0到頂點3的最短路徑長度是______，經(jīng)過的中間頂點是______。12、屬于不穩(wěn)定排序的有______。13、在雙向循環(huán)鏈表中，向p所指的結(jié)點之后插入指針f所指的結(jié)點，其操作是______、______、______、______。14、檢索是為了在文件中尋找滿足一定條件的記錄而設(shè)置的操作。檢索可以按______檢索。也可以按______檢索；按______檢索又可以有______檢索和______檢索。15、外排序的基本操作過程是______和______。16、每一棵樹都能唯一地轉(zhuǎn)換為它所對應(yīng)的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列是______。設(shè)上述二叉樹是由某棵樹轉(zhuǎn)換而成，則該樹的前序序列是______。17、設(shè)正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復(fù)雜度為______。18、假設(shè)一個15階的上三角矩陣A按行優(yōu)先順序壓縮存儲在一維數(shù)組B中，則非零元素A9.9在B中的存儲位置k=______。（注：矩陣元素下標(biāo)從1開始）三、判斷題19、對處理大量數(shù)據(jù)的外存介質(zhì)而言，索引順序存取方法是一種方便的文件組織方法。（）20、倒排文件是對次關(guān)鍵字建立索引。（）21、數(shù)組不適合作為任何二叉樹的存儲結(jié)構(gòu)。（）22、KMP算法的特點是在模式匹配時指示主串的指針不會變小。（）23、對于有n個結(jié)點的二叉樹，其高度為log2n。（）24、一棵樹中的葉子數(shù)一定等于與其對應(yīng)的二叉樹的葉子數(shù)。（）25、在用堆排序算法排序時，如果要進行增序排序，則需要采用“大根堆”。（）26、若中序遍歷平衡的二叉排序樹，可得到排好序的關(guān)鍵碼序列。（）27、當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動后，必將產(chǎn)生不同的關(guān)鍵路徑。（）28、B-樹中所有結(jié)點的平衡因子都為零。（）四、簡答題29、寫出下列排序算法的基本思想，并寫出對序列（23，12，35，47，16，25，36，19，21，16）進行排序時每一趟的結(jié)果。30、調(diào)用下列C函數(shù)f（n），回答下列問題：（1）試指出f（n）值的大小，并寫出，f（n）值的推導(dǎo)過程。（2）假定n=5，試指出，f（5）值的大小和執(zhí)行，f（5）時的輸出結(jié)果。C函數(shù)：31、設(shè)將n（n＞1）個整數(shù)存放到一維數(shù)組R中。試設(shè)計一個在時間和空間兩方面都盡可能高效的算法，將R中存有的序列循左移P（0＜P＜n）個位置，即將R中的數(shù)據(jù)由（X0，X1，…，Xn－1）變換為（xp，xp＋1，…，xn－1，x0，x1，…，xp－1）。要求：（1） 給出算法的基本設(shè)計思想。（2） 根據(jù)設(shè)計思想，采用C或C＋＋或JAVA語言描述算法，關(guān)鍵之處給出注釋。說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。五、算法設(shè)計題32、請用流程圖或高級語言表示算法。已知有向圖有n個頂點，請寫算法，根據(jù)用戶輸入的數(shù)對建立該有向圖的鄰接表。即接受用戶輸入的<vi，vj>(以其中之一為0標(biāo)志結(jié)束)，對于每條這樣的邊，申請一個結(jié)點，并插入到的單鏈表中，如此反復(fù)，直到將圖中所有邊處理完畢。提示：先產(chǎn)生鄰接表的n個頭結(jié)點(其結(jié)點數(shù)值域從1到n)。33、設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點為A表中值小于零的結(jié)點，而C表的結(jié)點為A表中值大于零的結(jié)點（鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點）。34、假設(shè)以雙親表示法作樹的存儲結(jié)構(gòu)，寫出雙親表示的類型說明，并編寫求給定的樹的深度的算法（注：已知樹中的結(jié)點數(shù)）。35、已知一個單鏈表中每個結(jié)點存放一個整數(shù)，并且結(jié)點數(shù)不少于2，請設(shè)計算法以判斷該鏈表中第二項起的每個元素值是否等于其序號的平方減去其前驅(qū)的值，若滿足則返回ture，否則返回false。

參考答案一、選擇題1、【答案】D2、【答案】A3、【答案】D4、【答案】C5、【答案】C6、【答案】A7、【答案】A8、【答案】A9、【答案】C10、【答案】B二、填空題11、【答案】50；412、【答案】希爾排序、簡單選擇排序、快速排序、堆排序等13、【答案】f->next=p->next；f->prior=p；p->next->prior=f；p->next=f。14、【答案】關(guān)鍵字；記錄號；記錄號；順序；直接15、【答案】生成有序歸并段（順串）；歸并16、【答案】FEGHDCB；BEF【解析】樹的前序序列對應(yīng)二叉樹的前序序列，該二叉樹轉(zhuǎn)換成森林時含三棵樹，其第一棵樹的前序是BEF。17、【答案】O（m+n）18、【答案】93三、判斷題19、【答案】×20、【答案】√21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】√26、【答案】√27、【答案】×28、【答案】√四、簡答題29、答：此排序為雙向起泡排序：從前向后一趟排序下來得到一個最大值，若其中發(fā)生交換，則再從后向前一趟排序，得到一個最小值。第一趟：12，23，35，16，25，36，19，21，16，47第二趟：12，16，23，35，16，25，36，19，21，47第三趟：12，16，23，16，25，35，19，21，36，47第四趟：12，16，16，23，19，25，35，21，36，47第五趟：12，16，16，19，23，25，21，35，36，47第六趟：12，16，16，19，21，23，25，35，36，47第七趟：12，16，16，19，21，23，25，35，36，4730、答：（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í)行過程中，輸出結(jié)果為：31、答：（1）算法的基本設(shè)計思想：先將n個數(shù)據(jù)由x0，x1，…，xp，…，xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再將數(shù)組R中的前n－P個數(shù)和后