2022-2022昆明理工大學(xué)第一學(xué)期數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)試卷試題

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦2022-2022昆明理工大學(xué)第一學(xué)期數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)試卷試題

數(shù)據(jù)結(jié)構(gòu)模擬試題

考試科目：數(shù)據(jù)結(jié)構(gòu)A

1.下面程序的時光復(fù)雜為（）

for（i=1，s=0；inext=p;q->next=s;

B.p->next=s->next;s->next=p;

C.q->next=s->next;s->next=p;

D.p->next=s;s->next=q;

7.棧和隊列的共同點是（）。

A.都是先進先出

B.都是先進后出

C.只允許在端點處插入和刪除元素

D.沒有共同點

8.有六個元素6，5，4，3，2，1的挨次進棧，問下列哪一個不是合法的出棧序列？（）

A.543612

B.453126

C.234156

D.346521

9.設(shè)C語言數(shù)組Data[m+1]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊

尾指針，則執(zhí)行出隊操作的語句為（）

A.front=front+1

B.front=（front+1）%m

C.rear=(rear+1)%(m+1)

D.front=(front+1)%(m+1)

10.一棵二叉樹上有50個度為2的結(jié)點，其中葉子結(jié)點的個數(shù)是（）

A．100B．51C．25D．以上答案都不對

11.二叉樹的第I層上最多含有結(jié)點數(shù)為（）

A．2IB．2I-1-1C．2I-1D．2I-1

12.一棵有n個結(jié)點的徹低二叉樹，按層次從上到下，同一層從左到右挨次存儲在一維數(shù)

組A[1..n]中，則二叉樹中第i個結(jié)點（i從1開頭用上述辦法編號）的右孩子在數(shù)組A中的位置是（）

A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)

C．A[i-2]D．條件不充分，無法確定

13.n個結(jié)點的線索二叉樹上含有的線索數(shù)為（）

A．2nB．n－lC．n＋lD．n

14.以下說法錯誤的是()

A．哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。

B．若一個二叉樹的樹葉是某子樹的中序遍歷序列中的第一個結(jié)點，則它必是該子樹的后序遍歷序列中的第一個結(jié)點。

C．已知二叉樹的前序遍歷和后序遍歷序列并不能惟一地確定這棵樹，由于不知道樹的根結(jié)點是哪一個。

D．在前序遍歷二叉樹的序列中，任何結(jié)點的子樹的全部結(jié)點都是直接跟在該結(jié)點的之后。

15.任何一個帶權(quán)的無向連通圖的最小生成樹（）

A．惟獨一棵B．有一棵或多棵C．一定有多棵D．可能不存在

16.設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（）條邊。

A．n-1B．n(n-1)/2C．n(n+1)/2D．0vE．n2

17.要連通具有n個頂點的有向圖，至少需要（）條邊。

A．n-lB．n+1C．nD．2n

18.當(dāng)采納分塊查找時，數(shù)據(jù)的組織方式為()

A．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序

B．?dāng)?shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必需有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊

C.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊

D.以上都不是

19.下圖所示的4棵二叉樹,()是平衡二叉樹。

ABCD

20.下列排序算法中，在待排序數(shù)據(jù)已有序時，花費時光反而最多的是()排序。A．冒泡B.希爾

C.迅速

D.堆

二、填空題（每空1分，共20分）

1.一個算法的時光復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為________。

2.線性表的物理結(jié)構(gòu)主要包括_____________和______________兩種狀況。

3.通常從正確性、易讀性、________和高效率等4個方面評價算法（包括程

序）的質(zhì)量。

4.挨次表的存儲密度為________，而鏈表的存儲密度為________。

5.線性表是由n（n≥0）個數(shù)據(jù)元素所構(gòu)成的有限序列，其中n為數(shù)據(jù)元素的個數(shù)，稱

為線性表的，n=0的線性表稱為。

6.線性表中有且僅有一個開頭結(jié)點和終端結(jié)點，除開頭結(jié)點和終端結(jié)點之外，其它每一個

數(shù)據(jù)元素有且僅有一個，有且僅有一個。

7.棧是_______的線性表，其運算遵循_______的原則。8.5．隊列是限制插入只能在表的一端，而刪除在表的另一端舉行的線性表，其特點是

_______。

9.具有n個結(jié)點的二叉樹中,一共有2n個指針域,其中惟獨

________個用來指向結(jié)點的左

右孩子，其余的________個指針域為NULL。

10.樹的主要遍歷辦法有前序、________、________等三種。

11.在挨次表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關(guān)鍵碼值

15，需做的關(guān)鍵碼比較次數(shù)為____.12.在有向圖的鄰接矩陣表示中，計算第i個頂點入度的辦法是______。13.對n個記錄的表R[1..n]舉行容易挑選排序，所需舉行的關(guān)鍵字間的平均比較次數(shù)

為。

三、簡述題（每題10分共30分）

1．將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）

2．已知一個無向圖如下圖所示，要求用Prim算法生成最小生成樹（假設(shè)以①為起點，試畫出構(gòu)造過程）。

3．對于給定的一組鍵值：83，40，63，84，35，96，57，39，79。請畫出