2022-2022昆明理工大學第一學期數據結構復習試卷試題

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦2022-2022昆明理工大學第一學期數據結構復習試卷試題

數據結構模擬試題

考試科目：數據結構A

1.下面程序的時光復雜為（）

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.設C語言數組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的結點，其中葉子結點的個數是（）

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

11.二叉樹的第I層上最多含有結點數為（）

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

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

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

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

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

13.n個結點的線索二叉樹上含有的線索數為（）

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

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

A．哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近。

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

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

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

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

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

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

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

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

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

18.當采納分塊查找時，數據的組織方式為()

A．數據分成若干塊，每塊內數據有序

B．數據分成若干塊，每塊內數據不必有序，但塊間必需有序，每塊內最大（或最?。┑臄祿M成索引塊

C.數據分成若干塊，每塊內數據有序，每塊內最大（或最小）的數據組成索引塊

D.以上都不是

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

ABCD

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

C.迅速

D.堆

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

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

2.線性表的物理結構主要包括_____________和______________兩種狀況。

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

序）的質量。

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

5.線性表是由n（n≥0）個數據元素所構成的有限序列，其中n為數據元素的個數，稱

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

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

數據元素有且僅有一個，有且僅有一個。

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

_______。

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

________個用來指向結點的左

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

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

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

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

為。

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

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

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

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