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

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

參考答案一、選擇題1、【答案】B2、【答案】D3、【答案】B4、【答案】B5、【答案】C6、【答案】D7、【答案】A8、【答案】C9、【答案】C10、【答案】C二、填空題11、【答案】n(n-1)/212、【答案】2(N-1)13、【答案】記錄；數(shù)據(jù)項(xiàng)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、【答案】√四、簡(jiǎn)答題29、答：①快速排序②起泡排序③直接插入排序④堆排序30、答：此排序?yàn)殡p向起泡排序：從前向后一趟排序下來(lái)得到一個(gè)最大值，若其中發(fā)生交換，則再?gòu)暮笙蚯耙惶伺判?，得到一個(gè)最小值。第一趟：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）算法思想：算法的核心思想是用空間換時(shí)間。定義一個(gè)大小為n的布爾數(shù)組flag，初始時(shí)所有的元素都賦值為false，用來(lái)標(biāo)識(shí)遍歷過(guò)程中是否出現(xiàn)元素絕對(duì)值為flag的節(jié)點(diǎn)。然后遍歷鏈表，遍歷過(guò)程中，每一個(gè)當(dāng)前結(jié)點(diǎn)data域的絕對(duì)值所對(duì)應(yīng)的flag位：若為真，則刪除該結(jié)點(diǎn)；若為假（false），則將flag位置為（true）。（2）節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義如下：（3）（4）只遍歷