2022年河北農(nóng)業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A(有答案)

2022年河北農(nóng)業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（）。A.13B.33C.18D.402、哈希文件使用哈希函數(shù)將記錄的關(guān)鍵字值計(jì)算轉(zhuǎn)化為記錄的存放地址，因?yàn)楣：瘮?shù)是一對(duì)一的關(guān)系，則選擇好的（）方法是哈希文件的關(guān)鍵。A.哈希函數(shù)B.除余法中的質(zhì)數(shù)C.沖突處理D.哈希函數(shù)和沖突處理3、以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。A.樹(shù)B.字符串C.隊(duì)D.棧4、動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)中，通?？捎校ǎ┓N不同的分配策略。A.1B.2C.3D.45、下面關(guān)于串的敘述中，不正確的是（）。A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)6、下列敘述中，不符合m階B樹(shù)定義要求的是（）。A．根結(jié)點(diǎn)最多有m棵子樹(shù)B．所有葉結(jié)點(diǎn)都在同一層上C．各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D．葉結(jié)點(diǎn)之間通過(guò)指針鏈接7、若元素a，b，c，d，e，f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行退棧操作，則不可能得到的出棧序列是（）。8、一棵哈夫曼樹(shù)共有215個(gè)結(jié)點(diǎn)，對(duì)其進(jìn)行哈夫曼編碼，共能得到（）個(gè)不同的碼字。A.107B.108C.214D.2159、有關(guān)二叉樹(shù)下列說(shuō)法正確的是（）。A.二叉樹(shù)的度為2B.一棵二叉樹(shù)的度可以小于2C.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為210、在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為l，則應(yīng)作（）型調(diào)整以使其平衡A.LLB.LRC.RLD.RR二、填空題11、屬于不穩(wěn)定排序的有______。12、在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)______。13、設(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ǔ)句：______14、數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的______和______以及它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的______，設(shè)計(jì)出相應(yīng)的______。15、索引順序文件既可以順序存取，也可以______存取。16、下列程序是快速排序的非遞歸算法，請(qǐng)?zhí)顚?xiě)適當(dāng)?shù)恼Z(yǔ)句，完成該功能。17、設(shè)有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)順序存放在向量A[1：N]中，其下標(biāo)值最大的分支結(jié)點(diǎn)為_(kāi)_____。18、已知一循環(huán)隊(duì)列的存儲(chǔ)空間為[m..n]，其中n>m，隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則此循環(huán)隊(duì)列判滿(mǎn)的條件是______。三、判斷題19、倒排序文件的優(yōu)點(diǎn)是維護(hù)簡(jiǎn)單。（）20、倒排文件的目的是為了多關(guān)鍵字查找。（）21、隊(duì)列和棧都是運(yùn)算受限的線(xiàn)性表，只允許在表的兩端進(jìn)行運(yùn)算。（）22、棧的輸入序列是1，2，…，n，輸出序列是a1，a2，…，an若ai=n（1≤i≤n）則有：ai>ai+1>…>an。（）23、一個(gè)樹(shù)形的葉結(jié)點(diǎn)，在前序遍歷和后序遍歷下，皆以相同的相對(duì)位置出現(xiàn)。（）24、一棵樹(shù)中的葉子數(shù)一定等于與其對(duì)應(yīng)的二叉樹(shù)的葉子數(shù)。（）25、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）26、為了很方便地插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。（）27、無(wú)環(huán)有向圖才能進(jìn)行拓?fù)渑判?。（?8、在動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)中做空間分配時(shí)，最佳適配法與最先適配法相比，前者容易增加閑置空間的碎片。（）四、簡(jiǎn)答題29、請(qǐng)寫(xiě)出應(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、寫(xiě)出下列排序算法的基本思想，并寫(xiě)出對(duì)序列（23，12，35，47，16，25，36，19，21，16）進(jìn)行排序時(shí)每一趟的結(jié)果。31、設(shè)二叉樹(shù)BT的存儲(chǔ)結(jié)構(gòu)如表：其中BT為樹(shù)根結(jié)點(diǎn)的指針，其值為6，Lchild、Rchild分別為結(jié)點(diǎn)的左、右孩子指針域data為結(jié)點(diǎn)的數(shù)據(jù)域。試完成下列各題：（1）畫(huà)出二叉樹(shù)BT邏輯結(jié)構(gòu)。（2）寫(xiě)出按前序、中序、后序遍歷該二叉樹(shù)所得到的結(jié)點(diǎn)序列。（3）畫(huà)出二叉樹(shù)的后序線(xiàn)索樹(shù)。五、算法設(shè)計(jì)題32、已知P是指向單向循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針，試編寫(xiě)只包含一個(gè)循環(huán)的算法，將線(xiàn)性表（a1，a2，…，an-1，an）改造為（a1，a2，…，an-1，an，an-1，…，a2，a1）。33、借助于快速排序的算法思想，在一組無(wú)序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[1..h]中。若查找成功，則輸出該記錄在r數(shù)組中的位置及其值，否則顯示“notfind”信息。請(qǐng)編寫(xiě)出算法并簡(jiǎn)要說(shuō)明算法思想。34、以順序存儲(chǔ)結(jié)構(gòu)表示串，設(shè)計(jì)算法。求串s中出現(xiàn)的第一個(gè)最長(zhǎng)重復(fù)子串及其位置并分析算法的時(shí)間復(fù)雜度。35、敘述基數(shù)排序算法，并對(duì)下列整數(shù)序列圖示其基數(shù)排序的全過(guò)程。（179，208，93，306，55，859，984，9，271，33）

參考答案一、選擇題1、【答案】B2、【答案】D3、【答案】A4、【答案】C5、【答案】B6、【答案】D7、【答案】D8、【答案】B9、【答案】B10、【答案】C二、填空題11、【答案】希爾排序、簡(jiǎn)單選擇排序、快速排序、堆排序等12、【答案】2(n-1)13、【答案】py->next=px->next；px->next=py14、【答案】邏輯結(jié)構(gòu)；物理結(jié)構(gòu)；操作（運(yùn)算）；算法15、【答案】隨機(jī)16、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。17、【答案】【解析】最大的分支結(jié)點(diǎn)是最后一個(gè)葉子結(jié)點(diǎn)的父結(jié)點(diǎn)。18、【答案】（rear+1）%（n-m+1）==front三、判斷題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ù)的邏輯結(jié)構(gòu)如