2023年江西理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A(含答案)

2023期末試卷A〔有答案〕一、選擇題1、廣義LS=〔〔a，b，c〕，〔d，e，f〕〕，headtailLS中原子e的運(yùn)算是〔 〕。A.head〔tail〔LS〕〕B.tail 〔head〔LS〕〕〔tail〔tail〔head〔LS〕〕〕〕2、將兩個(gè)各有N個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是〔 〕。A.NB.2N-1C.2ND.N-13、鏈表不具有的特點(diǎn)是〔 〕。A.插入、刪除不需要移動(dòng)元素B. 可隨機(jī)訪問任一元素C.不必事先估量存儲(chǔ)空間D. 所需空間與線性長度成正比4、循環(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-front5、有向圖G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，<V6，V7>｝，G的拓?fù)湫蛄惺恰?〕。A.V1，V3，V4，V6，V2，V5，V7B.V1 ，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1 ，V2，V5，V3，V4，V6，V76、以下表達(dá)中，不符合m階B樹定義要求的是〔 〕。A．根結(jié)點(diǎn)最多有m棵子樹B ．全部葉結(jié)點(diǎn)都在同一層上C．各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D．葉結(jié)點(diǎn)之間通過指針鏈接7、關(guān)鍵5，8，12，19，28，20，15，22是小根堆〔最小堆〕，插入關(guān)鍵字3，調(diào)整后的小根堆是〔〕。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、一棵非空的二叉樹的前序序列和后序序列正好相反，則該二叉樹肯定滿足〔〕。A.其中任意一個(gè)結(jié)點(diǎn)均無左孩子B.其中任意一個(gè)結(jié)點(diǎn)均無右孩子C.其中只有一個(gè)葉結(jié)點(diǎn)D.其中度2的結(jié)點(diǎn)最多為一個(gè)9、設(shè)X是樹T中的一個(gè)非根結(jié)點(diǎn)，B是T所對(duì)應(yīng)的二叉樹。在B中，X是其雙親的右孩子，以下結(jié)論正確的選項(xiàng)是〔 〕。在樹T中，X是其雙親的第一個(gè)孩子在樹T中，X肯定無右兄弟在T中，X肯定是葉結(jié)點(diǎn)在T中，X肯定有左兄弟10、下面關(guān)于B和B+樹的表達(dá)中，不正確的選項(xiàng)是〔 〕A.B樹和B+樹都是平衡的多叉樹B.B 樹和B+樹都可用于文件的索引構(gòu)造C.B樹和B+樹都能有效地支持挨次檢索D.B 樹和B+樹都能有效地支持隨機(jī)檢索二、填空題11、屬于不穩(wěn)定排序的有 。12、在哈希函數(shù)H〔key〕=key%p中，p值最好取 。13、以下是用類C語言寫出的算法，該算法將以二叉鏈表存儲(chǔ)的二叉樹中的葉結(jié)點(diǎn)按從左到右的挨次鏈成一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，鏈接時(shí)，結(jié)點(diǎn)的Lchild域作為前鏈域，指向結(jié)點(diǎn)的直接前驅(qū)，結(jié)點(diǎn)的Rchild域作為后鏈域，指向結(jié)點(diǎn)的直接后繼。算法中，使top，p，t為關(guān)心指針，head為雙向循環(huán)鏈表的頭指針。試填充算法中的空格，使算法完整。棵m階B-樹中，假設(shè)在某結(jié)點(diǎn)中插入一個(gè)關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是 ；假設(shè)在某結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并，則該結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是 。15、關(guān)鍵碼序列〔Q，H，C，Y，Q，A，M，S，R，D，F(xiàn)，X〕，要依據(jù)關(guān)鍵碼值遞增的次序進(jìn)展排序，假設(shè)承受初始步4的希爾排序法，則一趟掃描的結(jié)果是；假設(shè)承受以第一個(gè)元素為分界元素的快速排序法，則掃描一趟的結(jié)果是。16、TP是兩個(gè)給定的串，在T中查找等于P的子串的過程稱為P為 。義表L=〔〔〕，〔〕〕，則head〔L〕是 ；tail〔L〕是 ；L的長度是 ；深度是 。18、閱讀以下程序說明和程序，填充程序中的 。說明】本程序完成將二叉樹中左、右孩子交換的操作。交換的結(jié)果如下所示〔編者略〕。本程序承受非遞歸的方法，設(shè)立一個(gè)堆棧stack存放還沒有轉(zhuǎn)換過的結(jié)點(diǎn)，它的棧頂指針tp。交換左、右子樹的算法為：把根結(jié)點(diǎn)放入堆棧。當(dāng)堆棧不空時(shí)，取出棧頂元素，交換它的左、右子樹，并把它的左、右子樹分別入棧。重復(fù)〔2〕直到堆棧為空時(shí)為止。三、推斷題鍵字查找?！?〕20、倒排文件是對(duì)次關(guān)鍵字建立索引?！?〕21、隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)展運(yùn)算。〔 〕必會(huì)失去隨機(jī)存取功能。〔 〕23、一棵樹中的葉子數(shù)肯定等于與其對(duì)應(yīng)的二叉樹的葉子數(shù)?！?〕24、二叉樹是一般樹的特別情形?！?〕25、數(shù)據(jù)的規(guī)律構(gòu)造是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的規(guī)律關(guān)系?！?〕〔 〕27、連通圖上各邊權(quán)值均不一樣，則該圖的最小生成樹是唯一的?！?〕28、平衡二叉樹中，假設(shè)某個(gè)結(jié)點(diǎn)的左、右孩子的平衡因子為零，則該結(jié)點(diǎn)的平衡因子肯定是零?！?〕四、簡(jiǎn)答題i29、對(duì)于具有n個(gè)葉結(jié)點(diǎn)且全部非葉結(jié)點(diǎn)都有左、右孩子的二叉樹。(1)試問這種二叉樹的結(jié)點(diǎn)總數(shù)是多少?i試證明〕。

2〔li-〕=1。其中：l表示第i結(jié)層號(hào)設(shè)結(jié)層號(hào)為30、用一個(gè)數(shù)組S〔設(shè)大小為MAX〕作為兩個(gè)堆棧的共享空間。請(qǐng)說明共享方法，棧滿棧空的推斷條件，并用C語言或PASCAL語言棧操作pusi，x〕，i01，用于表示棧號(hào)，x為入棧值。31、世界六大城市為：北京(Pe)、紐約(N)、巴黎(Pa)、倫敦(L)、東京(T)、墨西哥(M)，下表給定了這六大城市之間的交通里程：世界六大城市交通里程表(單位：百公里)畫出這六大城市的交通網(wǎng)絡(luò)圖。畫出該圖的鄰接表表示法。畫出該圖按權(quán)值遞增的挨次來構(gòu)造的最小〔代價(jià)〕生成樹。五、算法設(shè)計(jì)題32、圖G有n個(gè)點(diǎn)，利用從某個(gè)源點(diǎn)到其余各點(diǎn)最短路徑算法思想，設(shè)計(jì)一產(chǎn)生G的最小生成樹的算法。33、設(shè)A[1..100]是一個(gè)記錄構(gòu)成的數(shù)組，B[1..100]是一個(gè)整數(shù)數(shù)組，其值介于l～100之間，現(xiàn)要求按B[1..100]的內(nèi)容調(diào)整A中記錄的次序，比方當(dāng)B[1]=11時(shí)，則要求將A[1]整到A[11規(guī)間為〔〕。34、假設(shè)一個(gè)僅包含二元運(yùn)算符的算術(shù)表達(dá)式以鏈表形式存儲(chǔ)在二叉樹BT中，寫出計(jì)算該算術(shù)表達(dá)式值的算法。35、以三元組表存儲(chǔ)的稀疏矩陣A，B非零元個(gè)數(shù)分別為m和n。試用類PASCAL語言寫簡(jiǎn)單為〔m+〕陣B陣AA足夠大，不另加關(guān)心空間。要求描述所用構(gòu)造。參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】B4、【答案】A5、【答案】A6、【答案】D7、【答案】A8、【答案】C9、【答案】D10、【答案】C二、填空題11、【答案】希爾排序、簡(jiǎn)潔選擇排序、快速排序、堆排序等12、【答案】小于等于表長20的質(zhì)因子的合數(shù)13、【答案】p->Rchild=t；t->Lchild=p；p=t；t->Rchild!=null；t->Rchild；t->Lchild!=null；t->Lchild；p->Rchild=head；head->Lchild=p14、【答案】【解析】mB-樹除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)最多是m1，最少15、【答案】〔Q，A，C，S，Q，D，F(xiàn)，X，R，H，M,Y〕；〔F，H，C，D，a【解析】mB-樹除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)最多是m1，最少16、【答案】模式匹配；模式串17、【答案】〔〕；〔〔〕〕；2；218、【答案】stack[tp]=t；p=stack[tp--]；p；++tp【解析】此題主要使用堆棧完成了二叉樹左右子樹交換的操作。首先根結(jié)點(diǎn)進(jìn)棧，然后判斷棧是否為空，假設(shè)不為空，則取棧頂元素，交換取出結(jié)點(diǎn)的左右指針。并將左右指針分別進(jìn)棧，重復(fù)這一操作。完成二叉樹左右孩子的交換。三、推斷題19、【答案】√20、【答案】√21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】×四、簡(jiǎn)答題9〔1〕樹中度為2的結(jié)結(jié)點(diǎn)個(gè)數(shù)減1，故具有n個(gè)葉結(jié)點(diǎn)且非葉子結(jié)點(diǎn)均有左子樹的二叉樹的結(jié)2n-1。2〕證明：當(dāng)i=1時(shí)21-〕=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ì)于公式的變化，是削減了一結(jié)2〔t1=2-t+1-1〕+2-t+1-1〕變，這證明當(dāng)i=n。30、答：兩棧共享一向量空間〔一維數(shù)組〕，棧底設(shè)在數(shù)組的兩端，兩棧頂相鄰時(shí)為棧