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

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

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