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、下述文件中適合于磁帶存儲(chǔ)的是（）。A.順序文件B.索引文件C.哈希文件D.多關(guān)鍵字文件2、將兩個(gè)各有N個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。A.NB.2N-1C.2ND.N-13、以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（）。A.循環(huán)隊(duì)列B.鏈表C.哈希表D.棧4、下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（）。A.關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B.任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成C.所有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成D.某些關(guān)鍵活動(dòng)若提前完成，那么整個(gè)工程將會(huì)提前完成5、動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)中，通常可有（）種不同的分配策略。A.1B.2C.3D.46、若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。A．只有eB．有e、bC．有e、cD．無法確定7、下列選項(xiàng)中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4508、有關(guān)二叉樹下列說法正確的是（）。A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為29、一棵非空的二叉樹的前序序列和后序序列正好相反，則該二叉樹一定滿足（）。A.其中任意一個(gè)結(jié)點(diǎn)均無左孩子B.其中任意一個(gè)結(jié)點(diǎn)均無右孩子C.其中只有一個(gè)葉結(jié)點(diǎn)D.其中度為2的結(jié)點(diǎn)最多為一個(gè)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、設(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ù)的程序段，請將未完成的部分填入，使之完整。②執(zhí)行程序，f（6，4）=______。12、下面程序的功能是用遞歸算法將一個(gè)整數(shù)按逆序存放到一個(gè)字符數(shù)組中。如123存放成321。請?zhí)羁眨?3、在雙向循環(huán)鏈表中，向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作是______、______、______、______。14、應(yīng)用Prim算法求解連通網(wǎng)絡(luò)的最小生成樹問題。（1）針對如圖所示的連通網(wǎng)絡(luò)，試按如下格式給出在構(gòu)造最小生成樹過程中順序選出的各條邊。（2）下面是Prim算法的實(shí)現(xiàn)，中間有5個(gè)地方缺失，請閱讀程序后將它們補(bǔ)上。15、文件由______組成；記錄由______組成。16、模式串P=‘a(chǎn)baabcac’的next函數(shù)值序列為______。17、當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組stack（1，n）表示，兩棧頂指針為top[1]與top[2]，則當(dāng)棧1空時(shí)，top[1]為______，棧2空時(shí)，top[2]為______，棧滿時(shí)為______。18、已知一循環(huán)隊(duì)列的存儲(chǔ)空間為[m..n]，其中n>m，隊(duì)頭和隊(duì)尾指針分別為front和rear，則此循環(huán)隊(duì)列判滿的條件是______。三、判斷題19、哈希表與哈希文件的唯一區(qū)別是哈希文件引入了“桶”的概念。（）20、直接訪問文件也能順序訪問，只是一般效率不高。（）21、廣義表（（（a，b，c），d，e，f））的長度是4。（）22、串是一種數(shù)據(jù)對象和操作都特殊的線性表。（）23、樹形結(jié)構(gòu)中元素之間存在一對多的關(guān)系。（）24、若從二叉樹的任一結(jié)點(diǎn)出發(fā)，到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹一定是哈夫曼樹。（）25、排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（）26、在一個(gè)設(shè)有頭指針和尾指針的單鏈表中，執(zhí)行刪除該單鏈表中最后一個(gè)元素的操作與鏈表的長度無關(guān)。（）27、平衡二叉樹中，若某個(gè)結(jié)點(diǎn)的左、右孩子的平衡因子為零，則該結(jié)點(diǎn)的平衡因子一定是零。（）28、若一個(gè)有向圖的鄰接矩陣對角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖?。（）四、簡答題29、將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹（只要求給出轉(zhuǎn)換結(jié)果）。30、假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問題：（1）畫出描述折半查找過程的判定樹。（2）若查找元素54，需依次與哪些元素比較?（3）若查找元素90，需依次與哪些元素比較?（4）假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長度。31、已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的data域的值，并返回1；否則，只返回0。要求：（1）描述算法的基本設(shè)計(jì)思想。（2）描述算法的詳細(xì)實(shí)現(xiàn)步驟。（3）根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語言描述算法（使用C或C＋＋或JAVA語言實(shí)現(xiàn)），關(guān)鍵之處請給出簡要注釋。五、算法設(shè)計(jì)題32、給定n×m矩陣A[a..b，c..d]，并設(shè)A[i，j]≤A[i+1，j]（a≤i≤b-1，c≤j≤d）。設(shè)計(jì)一算法判定x的值是否在A中，要求時(shí)間復(fù)雜度為O（m+n）。33、結(jié)點(diǎn)類型和存儲(chǔ)結(jié)構(gòu)如下：試設(shè)計(jì)一個(gè)排序算法，要求不移動(dòng)結(jié)點(diǎn)的存儲(chǔ)位置，只在結(jié)點(diǎn)的count字段記錄結(jié)點(diǎn)在排序中的序號，并將排序結(jié)果按升序輸出。34、已知P是指向單向循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針，試編寫只包含一個(gè)循環(huán)的算法，將線性表（a1，a2，…，an-1，an）改造為（a1，a2，…，an-1，an，an-1，…，a2，a1）。35、編寫算法，求二叉樹的寬度。

參考答案一、選擇題1、【答案】A2、【答案】A3、【答案】D4、【答案】B5、【答案】C6、【答案】A7、【答案】A8、【答案】B9、【答案】C10、【答案】B二、填空題11、【答案】①1；1；f（m，n-1）；n②912、【答案】a+1；n%10【解析】通過遞歸算法，首先找到最高位的值，將其放到str對應(yīng)的數(shù)組中，依次反向獲取從高位到地位的值，將其放到數(shù)組中，完成了將整數(shù)逆序放到一個(gè)字符數(shù)組中。13、【答案】f->next=p->next；f->prior=p；p->next->prior=f；p->next=f。14、【答案】(1)(0，3，1)；(3，5，4)；(5，2，2)；(3，1，5)；(1，4，3)(2)①T[k]；toVex=i②min=MaxInt;③mispos=i④exit(0)⑤T[i]；fromVex=v【解析】Prim算法的執(zhí)行類似于尋找圖的最短路徑的Dijkstra算法。假設(shè)N={V，E}是連通圖，ET是N上最小生成樹邊的集合。算法從VT={u0}，ET開始，重復(fù)執(zhí)行下述操作：在所有u屬于VT，v屬于V-VT的邊（u，v）屬于E中找一條代價(jià)最小的邊（u0，v0）加入集合ET，同時(shí)將v0并入VT，直到VT=V為止。15、【答案】記錄；數(shù)據(jù)項(xiàng)16、【答案】0112231217、【答案】0；n+1；top[1]+1=top[2]18、【答案】（rear+1）%（n-m+1）==front三、判斷題19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】√24、【答案】×25、【答案】×26、【答案】×27、【答案】×28、【答案】√四、簡答題29、答：森林轉(zhuǎn)換為二叉樹分以下三步：連線（將兄弟結(jié)點(diǎn)相連，各樹的根看作兄弟）。切線（保留最左邊子女為獨(dú)生子女，將其他子女分支切掉）。旋轉(zhuǎn)（以最左邊樹的根為軸，順時(shí)針向下旋轉(zhuǎn)45度）。所以由上面三棵樹轉(zhuǎn)換得到的二叉樹如圖所示：30、答：（1）判定樹如圖所示：（2） 若查找元素54，需依次和元素30、63、42、54比較，查找成功。（3） 若查找元素90，需依次和元素30、63、87、95比較，查找失敗。（4）31、答：（1）算法的基本設(shè)計(jì)思想定義兩個(gè)指針變量p和q，初始時(shí)均指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。p指針沿鏈表移動(dòng)；當(dāng)p指針移動(dòng)到第k個(gè)結(jié)點(diǎn)時(shí)，q指針開始與p指針同步移動(dòng)；當(dāng)p指針移動(dòng)到鏈表最后一個(gè)結(jié)點(diǎn)時(shí)，因?yàn)閜和q相隔k，故q指針?biāo)冈貫榈箶?shù)第k個(gè)結(jié)點(diǎn)。以上過程對鏈表僅進(jìn)行一遍掃描。（2）算法的詳細(xì)實(shí)現(xiàn)步驟①cou