2022年江蘇科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、有一個(gè)100*90的稀疏矩陣，非0元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是（）。A.60B.66C.18000D.332、下述文件中適合于磁帶存儲(chǔ)的是（）。A.順序文件B.索引文件C.哈希文件D.多關(guān)鍵字文件3、計(jì)算機(jī)算法指的是解決問(wèn)題的步驟序列，它必須具備（）三個(gè)特性。A.可執(zhí)行性、可移植性、可擴(kuò)充性B.可執(zhí)行性、確定性、有窮性C.確定性、有窮性、穩(wěn)定性D.易讀性、穩(wěn)定性、安全性4、最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭：front，則隊(duì)空的條件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、循環(huán)隊(duì)列A[0..m-1]存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front6、已知字符串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”，采用KMP算法進(jìn)行匹配，第一次出現(xiàn)“失配”（s!＝t）時(shí)，i＝j(luò)＝5，則下次開(kāi)始匹配時(shí)，i和j的值分別（）。A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝27、下列敘述中，不符合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ò)指針鏈接8、一棵非空的二叉樹(shù)的前序序列和后序序列正好相反，則該二叉樹(shù)一定滿(mǎn)足（）。A.其中任意一個(gè)結(jié)點(diǎn)均無(wú)左孩子B.其中任意一個(gè)結(jié)點(diǎn)均無(wú)右孩子C.其中只有一個(gè)葉結(jié)點(diǎn)D.其中度為2的結(jié)點(diǎn)最多為一個(gè)9、設(shè)X是樹(shù)T中的一個(gè)非根結(jié)點(diǎn)，B是T所對(duì)應(yīng)的二叉樹(shù)。在B中，X是其雙親的右孩子，下列結(jié)論正確的是（）。A.在樹(shù)T中，X是其雙親的第一個(gè)孩子B.在樹(shù)T中，X一定無(wú)右兄弟C.在樹(shù)T中，X一定是葉結(jié)點(diǎn)D.在樹(shù)T中，X一定有左兄弟10、對(duì)n個(gè)記錄的線(xiàn)性表進(jìn)行快速排序?yàn)闇p少算法的遞歸深度，以下敘述正確的是（）。A.每次分區(qū)后，先處理較短的部分B.每次分區(qū)后，先處理較長(zhǎng)的部分C.與算法每次分區(qū)后的處理順序無(wú)關(guān)D.以上三者都不對(duì)二、填空題11、設(shè)m、n均為自然數(shù)，m可表示為一些不超過(guò)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ù)的程序段，請(qǐng)將未完成的部分填入，使之完整。②執(zhí)行程序，f（6，4）=______。12、起始地址為480，大小為8的塊，其伙伴塊的起始地址是______；若塊大小為32，則其伙伴塊的起始地址為_(kāi)_____。13、在基于關(guān)鍵字比較且時(shí)間為O（nlog2n）的排序中，若要求排序是穩(wěn)定的，則可選用______排序；若要求就地排序（及輔助空間為O（1）），則可選用______排序。14、檢索是為了在文件中尋找滿(mǎn)足一定條件的記錄而設(shè)置的操作。檢索可以按______檢索。也可以按______檢索；按______檢索又可以有______檢索和______檢索。15、設(shè)T是一棵結(jié)點(diǎn)值為整數(shù)的二叉排序樹(shù)，A是一個(gè)任意給定的整數(shù)。在下面的算法中，free_tree（T）在對(duì)二叉排序樹(shù)丁進(jìn)行后序遍歷時(shí)釋放二又排序樹(shù)T的所有結(jié)點(diǎn)；delete_subtree（T，A），首先在二叉排序樹(shù)T中查找值為A的結(jié)點(diǎn)，根據(jù)查找情況分別進(jìn)行如下處理：（1）若找不到值為A的結(jié)點(diǎn)，則返回根結(jié)點(diǎn)的地址（2）若找到值為A的結(jié)點(diǎn)，則刪除以此結(jié)點(diǎn)為根的子樹(shù)，并釋放此子樹(shù)中的所有結(jié)點(diǎn)，若值為A的結(jié)點(diǎn)是查找樹(shù)的根結(jié)點(diǎn)，刪除后變成空的二叉樹(shù)，則返null；否則返回根結(jié)點(diǎn)的地址。16、設(shè)廣義表L=（（），（）），則head（L）是______；tail（L）是______；L的長(zhǎng)度是______；深度是______。17、已知一循環(huán)隊(duì)列的存儲(chǔ)空間為[m..n]，其中n>m，隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則此循環(huán)隊(duì)列判滿(mǎn)的條件是______。18、設(shè)有一個(gè)空棧，棧頂指針為1000H（十六進(jìn)制），現(xiàn)有輸入序列為l，2，3，4，5，經(jīng)過(guò)PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，輸出序列是______，而棧頂指針值是______。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)。三、判斷題19、倒排文件的目的是為了多關(guān)鍵字查找。（）20、倒排文件是對(duì)次關(guān)鍵字建立索引。（）21、串是一種數(shù)據(jù)對(duì)象和操作都特殊的線(xiàn)性表。（）22、稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。（）23、二叉樹(shù)是一般樹(shù)的特殊情形。（）24、樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多的關(guān)系。（）25、快速排序和歸并排序在最壞情況下的比較次數(shù)都是O（nlog2n）。（）26、在任何情況下，歸并排序都比簡(jiǎn)單插入排序快。（）27、B-樹(shù)中所有結(jié)點(diǎn)的平衡因子都為零。（）28、無(wú)環(huán)有向圖才能進(jìn)行拓?fù)渑判颉＃ǎ┧?、?jiǎn)答題29、對(duì)于具有n個(gè)葉結(jié)點(diǎn)且所有非葉結(jié)點(diǎn)都有左、右孩子的二叉樹(shù)。(1)試問(wèn)這種二叉樹(shù)的結(jié)點(diǎn)總數(shù)是多少?(2)試證明2-（li-1）=1。其中：li表示第i個(gè)葉結(jié)點(diǎn)所在的層號(hào)（設(shè)根結(jié)點(diǎn)所在層號(hào)為1）。30、假定對(duì)有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問(wèn)題：（1）畫(huà)出描述折半查找過(guò)程的判定樹(shù)。（2）若查找元素54，需依次與哪些元素比較?（3）若查找元素90，需依次與哪些元素比較?（4）假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。31、已知一個(gè)整數(shù)序列A＝（a0，a1，…，an－1），其中0≤ai＜n（0≤i≤n），若存在ap1＝ap2＝…＝apm＝x且m＞n/2（0≤pk≤n，1≤k≤m），則稱(chēng)x為A的主元素。例如A＝（0，5，5，3，5，7，5，5），則稱(chēng)5為主元素；又如A＝（0，5，5，3，5，1，5，7）則A中沒(méi)有主元素。假設(shè)A中的n個(gè)元素保存在一個(gè)一維數(shù)組中，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出－1。要求：（1）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用C或C＋＋或Java語(yǔ)言描述算法，關(guān)鍵之處給出注釋。說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。五、算法設(shè)計(jì)題32、結(jié)點(diǎn)類(lèi)型和存儲(chǔ)結(jié)構(gòu)如下：試設(shè)計(jì)一個(gè)排序算法，要求不移動(dòng)結(jié)點(diǎn)的存儲(chǔ)位置，只在結(jié)點(diǎn)的count字段記錄結(jié)點(diǎn)在排序中的序號(hào)，并將排序結(jié)果按升序輸出。33、設(shè)計(jì)將數(shù)組A[n]中所有的偶數(shù)移到奇數(shù)之前的算法。要求不增加存儲(chǔ)空間，且時(shí)間復(fù)雜性為O（n）。34、借助于快速排序的算法思想，在一組無(wú)序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[1..h]中。若查找成功，則輸出該記錄在r數(shù)組中的位置及其值，否則顯示“notfind”信息。請(qǐng)編寫(xiě)出算法并簡(jiǎn)要說(shuō)明算法思想。35、在輸入數(shù)據(jù)無(wú)序的情況下，建立一個(gè)數(shù)據(jù)值為整型的遞增有序的順序存儲(chǔ)線(xiàn)性表L，且要求當(dāng)輸入相同數(shù)據(jù)值時(shí)，線(xiàn)性表中不能存在數(shù)據(jù)值相同的數(shù)據(jù)元素，試寫(xiě)出其算法。順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表描述為：

參考答案一、選擇題1、【答案】B2、【答案】A3、【答案】B4、【答案】B5、【答案】A6、【答案】C7、【答案】D8、【答案】C9、【答案】D10、【答案】A二、填空題11、【答案】①1；1；f（m，n-1）；n②912、【答案】480+8=488；480-32=44813、【答案】歸并；堆14、【答案】關(guān)鍵字；記錄號(hào)；記錄號(hào)；順序；直接15、【答案】free（T）；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null16、【答案】（）；（（））；2；217、【答案】（rear+1）%（n-m+1）==front18、【答案】23；100CH三、判斷題19、【答案】√20、【答案】√21、【答案】√22、【答案】√23、【答案】×24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡(jiǎn)答題29、答：（1）根據(jù)二叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)等于葉結(jié)點(diǎn)個(gè)數(shù)減1的性質(zhì)，故具有n個(gè)葉結(jié)點(diǎn)且非葉子結(jié)點(diǎn)均有左子樹(shù)的二叉樹(shù)的結(jié)點(diǎn)數(shù)是2n-1。（2）證明：當(dāng)i=1時(shí)，2-（1-1）=20=1，公式成立。設(shè)當(dāng)i=n-1時(shí)公式成立，證明當(dāng)i=n時(shí)公式仍成立。設(shè)某葉結(jié)點(diǎn)的層號(hào)為t，當(dāng)將該結(jié)點(diǎn)變?yōu)閮?nèi)部結(jié)點(diǎn)，從而再增加兩個(gè)葉結(jié)點(diǎn)時(shí)，這兩個(gè)葉結(jié)點(diǎn)的層號(hào)都是t+1，對(duì)于公式的變化，是減少了一個(gè)原來(lái)的葉結(jié)點(diǎn)，增加了兩個(gè)新葉結(jié)點(diǎn)，反映到公式中，因?yàn)?-（t-1）=2-（t+1-1）+2-（t+1-1），所以結(jié)果不變，這就證明當(dāng)i=n時(shí)公式仍成立。證畢。30、答：（1）判定樹(shù)如圖所示：（2） 若查找元素54，需依次和元素30、63、42、54比較，查找成功。（3） 若查找元素90，需依次和元素30、63、87、95比較，查找失敗。（4）31、答：（1）算法的策略是從前向后掃描數(shù)組元素，標(biāo)記出一個(gè)可能成為主元素的元素Num。然后重新計(jì)數(shù)，確認(rèn)Num是否是主元素。算法可分為以下兩步：①選取候選的主元素：依次掃描所給數(shù)組中的每個(gè)整數(shù)，將第一個(gè)遇到的整數(shù)Num保存到c中，記錄Num的出現(xiàn)次數(shù)為1；若遇到的下一個(gè)整數(shù)仍等于Num，則計(jì)數(shù)加1，否則計(jì)數(shù)減1