2023秋北語數(shù)據(jù)結(jié)構(gòu)模擬試卷和答案

本文格式為Word版，下載可任意編輯——2023秋北語數(shù)據(jù)結(jié)構(gòu)模擬試卷和答案

北京語言大學(xué)網(wǎng)絡(luò)教育學(xué)院

《數(shù)據(jù)結(jié)構(gòu)》模擬試卷一

一、(本大題共10小題，每題2分，共20分)在每題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在答題卷相應(yīng)題號處。1、若某線性表最常用的操作是存取任一指定序號的元素和在最終進(jìn)行插入和刪除運算，則采用（[C]）存儲方式最節(jié)省時間。[A]順序表[B]雙鏈表[C]帶頭結(jié)點的雙循環(huán)鏈表[D]單循環(huán)鏈表2、隊列操作的原則是（d）。[A]只能進(jìn)行刪除[B]后進(jìn)先出[C]只能進(jìn)行插入[D]先進(jìn)先出

3、某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（b）的二叉樹。[A]空或只有一個結(jié)點[B]高度等于其結(jié)點數(shù)[C]任一結(jié)點無左孩子[D]任一結(jié)點無右孩子4、在以下排序方法中，（c）方法平均時間繁雜度為0(nlogn)，最壞狀況下時間繁雜度為0(n2)。[A]插入排序[B]希爾排序[C]快速排序[D]堆排序

5、對二叉樹從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一個結(jié)點的左、右孩子中，其左孩子編號小于右孩子編號。則可采用（c）次序的遍歷實現(xiàn)編號。[A]先序[B]中序[C]后序[D]從根開始的層次遍歷

6、若用數(shù)組S[n]作為兩個棧S1和S2的共用存儲結(jié)構(gòu)，對任何一個棧，只有當(dāng)S[n]全滿時才不能作入棧操作。為這兩個棧分派空間的最正確方案是（c）。[A]S1的棧底位置為0，S2的棧底位置為n[B]S1的棧底位置為－1，S2的棧底位置為n/2[C]S1的棧底位置為0，S2的棧底位置為n－1[D]S1的棧底位置為0，S2的棧底位置為n/2

7、對一棵二叉排序樹進(jìn)行（C）遍歷，可以得到該二叉樹的所有結(jié)點按值從小到大排列的序列。[A]前序[B]后序[C]中序[D]按層次8、在以下排序算法中，（D）算法可能會出現(xiàn)下面狀況：在最終一趟開始之前，所有元素都不在其最終的位置上。[A]堆排序[B]冒泡排序[C]快速排序[D]插入排序9、采用鄰接表存儲的圖的廣度優(yōu)先算法類似于二叉樹的（D）。[A]先序遍歷[B]中序遍歷[C]后序遍歷[D]層次遍歷10、具有6個頂點的無向圖至少應(yīng)有（B）條邊才能保證圖的連通性。

[A]4[B]5[C]6[D]7二、(本大題共10小題，每題2分，共20分)正確的填T，錯誤的填F，填在答題卷相應(yīng)題號處。

11、線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r所有結(jié)點之間的存儲單元地址可連續(xù)可不連續(xù)。（T）

12、任何二叉樹都唯一對應(yīng)一個森林，反之亦然。（T）13、有向圖的鄰接矩陣一定是對稱的。（F）14、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。（F）15、關(guān)鍵路徑可能不只一條，但縮短某一關(guān)鍵路徑一定能夠縮短工期。（F）

16、直接選擇排序是一種不穩(wěn)定的排序方法。（T）17、順序表用一維數(shù)組作為存儲結(jié)構(gòu)，因此順序表是一維數(shù)組。（F）18、棧和隊列都是順序存取的的線性表，但它們對存取位置的限制不同。（T）19、閉散列法尋常比開散列法時間效率更高。（F）20、一棵m階B樹中每個結(jié)點最多有m個關(guān)鍵碼，最少有2個關(guān)鍵碼。（F）三、（本大題共10小空，每小空2分，共20分）請將答案填寫在答題卷相應(yīng)題號處。21、《數(shù)據(jù)結(jié)構(gòu)》課程探討的主要內(nèi)容是數(shù)據(jù)的規(guī)律結(jié)構(gòu)、存儲結(jié)構(gòu)和（運算）。22、若要在單鏈表結(jié)點*P后插入一結(jié)點*S，執(zhí)行的語句（S->next=p->next;p->next=s）。23、折半探尋只適合用于（有序表）。

24、棧結(jié)構(gòu)允許進(jìn)行刪除操作的一端為（棧頂）。

25、設(shè)一行優(yōu)先順序存儲的數(shù)組A[5][6]，A[0][0]的地址為1100，且每個元素占2個存儲單元，則A[2][3]的地址為（1130）。

26、若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點個數(shù)為（69）。

27、一棵具有5層滿二叉樹中節(jié)點總數(shù)為（31）。

28、從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的（路徑）。29、在無向圖中，若從頂點A到頂點B存在（路徑），則稱A與B之間是連通的。30、若圖的鄰接矩陣是對稱矩陣，則該圖一定是（無向圖）。四、（本大題共5小題，每題8分，共40分）請將答案填寫在答題卷相應(yīng)題號處。

31、已知序列（12，4，17，10，7，30），用直接選擇排序法對其進(jìn)行遞增排序，寫出每一趟的排序結(jié)果。

答：第1趟：4121710730第2趟：4717101230

第3趟：4710171230第4趟：4710121730第5趟：4710121730

32、單鏈表結(jié)點的類型定義如下：typedefstructLNode{intdata;

structLNode*next;}LNode,*Linklist;寫一算法，將帶頭結(jié)點的有序單鏈表A和B合并成一新的有序表C。（注：不破壞A和B的原有結(jié)構(gòu)）

Merge(LinklistA,LinklistB,Linklistpa=A->next;pb=B->next;pc=C;while(papc=pc->next;

if(pa->datadata)

{pc->data=pa->data;pa=pa->next;}else

{pc->data=pb->data;pb=pb->next;}}

if(!pa)pa=pb;while(pa)

{pc->next=(Linklist)malloc(sizeof(LNode));pc=pc->next;

pc->data=pa->data;pa=pa->next;}

pc->next=NULL;}

33、已知一棵非空二叉樹，其按中序和后序遍歷的結(jié)果分別為：中序：CGBAHEDJFI后序：GBCHEJIFDA請畫出這棵二叉樹，并寫出其前序遍歷的結(jié)果。答：

前序遍歷結(jié)果:ACBGDEHFJI

34、已知字符：C1，C2，C3，C4，C5，C6的權(quán)分別為：17，5，16，4，8，11，請構(gòu)造相應(yīng)的赫夫曼樹，并給出相應(yīng)字符的赫夫曼編碼。標(biāo)準(zhǔn)答案：

c1:10c2:1111c3:01c4:1110c5:110c6:00

35、已知如下圖所示二叉樹，分別寫出其前序、中序和后序序列。ABC

DEF前序：ABDECF中序：DBEACF