2022年江西財經(jīng)大計算機與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》目期末試卷A(有答案)

2022年江西財經(jīng)大學(xué)計算機科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（）。A.13B.33C.18D.402、無向圖G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是（）。A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f,dD.a，e，d，f，c，b3、算法的計算量的大小稱為計算的（）。A.效率B.復(fù)雜性C.現(xiàn)實性D.難度4、下面關(guān)于串的敘述中，不正確的是（）。A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運算D.串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?、在下列表述中，正確的是（）A.含有一個或多個空格字符的串稱為空格串B.對n（n>0）個頂點的網(wǎng)，求出權(quán)最小的n-1條邊便可構(gòu)成其最小生成樹C.選擇排序算法是不穩(wěn)定的D.平衡二叉樹的左右子樹的結(jié)點數(shù)之差的絕對值不超過l6、若元素a，b，c，d，e，f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧操作，則不可能得到的出棧序列是（）。7、下列選項中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4508、一個具有1025個結(jié)點的二叉樹的高h為（）。A.11B.10C.11至1025之間D.10至1024之間9、有n（n>0）個分支結(jié)點的滿二叉樹的深度是（）。A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）10、數(shù)據(jù)序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的兩趟排序后的結(jié)果。A.選擇排序B.起泡排序C.插入排序D.堆排序二、填空題11、若用n表示圖中頂點數(shù)目，則有______條邊的無向圖成為完全圖。12、N個頂點的連通圖用鄰接矩陣表示時，該矩陣至少有______個非零元素。13、文件由______組成；記錄由______組成。14、設(shè)單鏈表的結(jié)點結(jié)構(gòu)為（data，next），next為指針域，已知指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點，若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行以下語句：______15、一個算法具有5個特性：______、______、______、有零個或多個輸入、有一個或多個輸出。16、模式串P=‘a(chǎn)baabcac’的next函數(shù)值序列為______。17、在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是______。18、已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是______。三、判斷題19、哈希表與哈希文件的唯一區(qū)別是哈希文件引入了“桶”的概念。（）20、對處理大量數(shù)據(jù)的外存介質(zhì)而言，索引順序存取方法是一種方便的文件組織方法。（）21、設(shè)模式串的長度為m，目標(biāo)串的長度為n，當(dāng)n≈m且處理只匹配一次的模式時，樸素的匹配（即子串定位函數(shù)）算法所花的時間代價可能會更為節(jié)省。（）22、廣義表（（（a，b，c），d，e，f））的長度是4。（）23、中序遍歷一棵二叉排序樹的結(jié)點就可得到排好序的結(jié)點序列。（）24、一棵樹中的葉子數(shù)一定等于與其對應(yīng)的二叉樹的葉子數(shù)。（）25、在一個設(shè)有頭指針和尾指針的單鏈表中，執(zhí)行刪除該單鏈表中最后一個元素的操作與鏈表的長度無關(guān)。（）26、歸并排序輔助存儲為O（1）。（）27、B-樹中所有結(jié)點的平衡因子都為零。（）28、在動態(tài)存儲管理系統(tǒng)中做空間分配時，最佳適配法與最先適配法相比，前者容易增加閑置空間的碎片。（）四、簡答題29、請寫出應(yīng)填入下列敘述中（）內(nèi)的正確答案。排序有各種方法，如插入排序、快速排序、堆排序等。設(shè)一數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。下面是一組用不同排序方法進行一遍排序后的結(jié)果。（）排序的結(jié)果為：12，13，15，18，20，60（）排序的結(jié)果為：13，15，18，12，20，60（）排序的結(jié)果為：13，15，20，18，12，60（）排序的結(jié)果為：12，13，20，18，15，6030、寫出下列排序算法的基本思想，并寫出對序列（23，12，35，47，16，25，36，19，21，16）進行排序時每一趟的結(jié)果。31、用單鏈表保存m個整數(shù)，節(jié)點的結(jié)構(gòu)為（data，link），且|data|＜n（n為正整數(shù)）?，F(xiàn)要求設(shè)計一個時間復(fù)雜度盡可能高效地算法，對于鏈表中絕對值相等的節(jié)點，僅保留第一次出現(xiàn)的節(jié)點而刪除其余絕對值相等的節(jié)點。例如若給定的單鏈表head如下刪除節(jié)點后的head為要求（1）給出算法的基本思想（2）使用C或C＋＋語言，給出單鏈表節(jié)點的數(shù)據(jù)類型定義。（3）根據(jù)設(shè)計思想，采用C或C＋＋語言描述算法，關(guān)鍵之處給出注釋。說明所涉及算法的時間復(fù)雜度和空間復(fù)雜度。五、算法設(shè)計題32、設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點為A表中值小于零的結(jié)點，而C表的結(jié)點為A表中值大于零的結(jié)點（鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點）。33、編寫遞歸算法，從大到小輸出給定二叉排序樹中所有關(guān)踺字不小于x的數(shù)據(jù)元素。要求你的算法的時間復(fù)雜度為O（log2（x+m）），其中，2為排序樹中所含結(jié)點數(shù)，m為輸出的關(guān)鍵字個數(shù)。34、已知P是指向單向循環(huán)鏈表最后一個結(jié)點的指針，試編寫只包含一個循環(huán)的算法，將線性表（a1，a2，…，an-1，an）改造為（a1，a2，…，an-1，an，an-1，…，a2，a1）。35、設(shè)在4地(A，B，C，D)之間架設(shè)有6座橋，如圖所示。要求從某一地出發(fā)，經(jīng)過每座橋恰巧一次，最后仍回到原地。（1）試就以上圖形說明：此問題有解的條件是什么?（2）設(shè)圖中的頂點數(shù)為n，試用C或PASCAL語言描述與求解此問題有關(guān)的數(shù)據(jù)結(jié)構(gòu)并編寫一個算法，找出滿足要求的一條回路。

參考答案一、選擇題1、【答案】B2、【答案】D3、【答案】B4、【答案】B5、【答案】C6、【答案】D7、【答案】A8、【答案】C9、【答案】C10、【答案】C二、填空題11、【答案】n(n-1)/212、【答案】2(N-1)13、【答案】記錄；數(shù)據(jù)項14、【答案】py->next=px->next；px->next=py15、【答案】有窮性；確定性；可行性16、【答案】0112231217、【答案】++a*b3*4-cd；18【解析】中綴式相當(dāng)于中序遍歷，前綴式相當(dāng)于前序遍歷，后綴式相當(dāng)于后序遍歷。18、【答案】s=（LinkedList*）ma11oc（sizeof（LNode））；s->data=x；s->next=r->next；r->next=s；r=s。三、判斷題19、【答案】×20、【答案】×21、【答案】√22、【答案】×23、【答案】√24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡答題29、答：①快速排序②起泡排序③直接插入排序④堆排序30、答：此排序為雙向起泡排序：從前向后一趟排序下來得到一個最大值，若其中發(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，4731、答：（1）算法思想：算法的核心思想是用空間換時間。定義一個大小為n的布爾數(shù)組flag，初始時所有的元素都賦值為false，用來標(biāo)識遍歷過程中是否出現(xiàn)元素絕對值為flag的節(jié)點。然后遍歷鏈表，遍歷過程中，每一個當(dāng)前結(jié)點data域的絕對值所對應(yīng)的flag位：若為真，則刪除該結(jié)點；若為假（false），則將flag位置為（true）。（2）節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義如下：（3）（4）只遍歷