《數(shù)據(jù)結構》期末考試卷-b卷

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦《數(shù)據(jù)結構》期末考試卷-b卷東莞理工學院城市學院（本科）試卷（B卷）

2022-2022學年其次學期

開課單位：計信系，考試形式：閉卷，允許帶入場

科目：數(shù)據(jù)結構班級：15級軟件工程1∽6班，姓名：學號：

一、填空題（每題2分，共12分）

1、數(shù)據(jù)結構在計算機中基本存儲方式有結構和結構。

2、棧(又稱為堆棧)是操作受限的線性結構，其操作的基本原則是，插入和刪除元素的一端稱為。

3、深度為k（根的深度為1）的徹低二叉樹至少有___________個結點，至多有_____________個結點。

4、對于一個有n個頂點的徹低無向圖，具有條邊；而對于一個有n個頂點的徹低有向圖，具有條弧。

5、在舉行排序時，最基本的操作是和。

6、哈希函數(shù)是一種映象，是從到的一種映象。

二、單項挑選題（請將答案寫在題目后的括號中。每題2分，共40分）

1、下面結構中，不屬于數(shù)據(jù)規(guī)律結構的是（）。

（A）線性鏈表（B）樹形結構

（C）線性結構（D）網(wǎng)狀結構

2、下面說法正確的是（）。

（A）數(shù)據(jù)元素是數(shù)據(jù)的最小單位

（B）數(shù)據(jù)項是數(shù)據(jù)的基本單位

（C）數(shù)據(jù)結構是帶有結構的各數(shù)據(jù)項的集合

（D）上述說法都是錯誤的

3、有下列算法，其時光復雜度是（）。

x=1;

while(xnext=q->next；free(p);（B）p->next=q->next；free(q);

（C）q->next=p->next；free(p);（D）q->next=p->next；free(q);6、棧和隊列的共同點時（）。

（A）都是先進先出（B）都是后進先出

（C）只允許在端點處插入和刪除元素（D）沒有共同點

7、設有一個棧頂指針為top的挨次棧S，top為0時表示?？?，則向堆棧S中壓入一個元

素x執(zhí)行的操作是（）。

（A）S[top++]=x；（B）S[++top]=x；

（C）S[--top]=x；（D）S[top--]=x；

8、設循環(huán)隊列Q的最多元素個數(shù)為m，隊尾指針是rear，隊首指針是front，則隊列為滿的條件是（）。

（A）==；（B）!=；

（C）+1)%m!=；（D）+1)%m==；

9、廣義表((a),((b),c),(((d,e),(a,b)))))的長度是，深度是。（）

（A）4,4（B）4,5（C）3,5（D）3,4

10、有一個12階下三角矩陣A，上三角的全部元素均為0，A[0][0]的地址是BA，若每個元素占3個存儲單元，采納行優(yōu)先壓縮存儲，則A[6][5]的地址是（）。

（A）BA+75（B）BA+78

（C）BA+81（D）BA+84

11、在二叉樹中，指針P所指的結點是非葉子結點的條件是（）。

（A）P->Lchild==NULL&&P->Rchild==NULL；

（B）P->Lchild!=NULL&&P->Rchild!=NULL；

（C）P->Lchild==NULL&&P->Rchild!=NULL；

（D）P->Lchild!=NULL||P->Rchild!=NULL；

12、將一棵普通的樹轉換為二叉樹后，這棵二叉樹的形態(tài)是（）。

（A）唯一的（B）有多種，但根結點都沒有左子結點

（C）有多種（D）有多種，但根結點都沒有右子結點

13、設由n（n≥2）個權值都互不相同的字符構成的哈夫曼樹，關于該樹的講述中，錯誤的是（）。

（A）該樹一定是一棵徹低二叉樹

（B）樹中一定沒有度為1的結點

（C）樹中兩個權值最小的結點一定是兄弟結點

（D）樹中任一非葉子結點的權值一定不小于下一層任一結點的權值

14、以下描述中，關于無向圖鄰接矩陣的特性不正確的是（）。

（A）鄰接矩陣是對稱方陣。

（B）若頂點vi在頂點數(shù)組中的存儲位置為i，則其度數(shù)是第i行的非0元素的個數(shù)。

（C）無向圖的邊數(shù)是上(或下)三角形矩陣中非0元素個數(shù)。

（D）圖的度是矩陣中非0元素個數(shù)。

15、對于有向圖，下述關于圖、頂點的度、入度、出度的論述中，錯誤的是（）。

（A）頂點的度是頂點的入度、出度之和

（B）圖的度是圖的入度、出度之和

（C）頂點的入度等于頂點的出度

（D）圖的入度等于圖的出度

16、對于有n個頂點e(e>n)條邊的帶權無向圖，以下關于該圖的最小生成樹的描述正確的是（）。

（A）最小生成樹是唯一的。

（B）最小生成樹中全部邊上的權值之和是唯一的。

（C）最小生成樹有n條邊。

（D）最小生成樹有n個頂點e-1條邊。

17、適用于折半查找的表的存儲方式以及元素羅列要求是（）。

（A）挨次存儲方式，元素有序（B）挨次存儲方式，元素無序

（C）鏈接存儲方式，元素無序（D）鏈接存儲方式，元素有序

18、采納線性探測法解決矛盾，可能要探測多個位置，在查找勝利的狀況下，所探測的這些位置上的關鍵字（）。

（A）不一定都是同義詞（B）一定都是同義詞

（C）一定都不是同義詞（D）都相同

19、從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素舉行比較，將其放入已排序序列的正確位置上的辦法，這種排序辦法稱為（）。

（A）歸并排序（B）冒泡排序

（C）挑選排序（D）插入排序

20、若一組記錄的排序碼為（46，79，56，38，40，84），則采納迅速排序法，以第一個記錄為基準得到的依次劃分結果是（）。

（A）38，40，46，56，79，84（B）40，38，46，79，56，84（C）40，38，46，56，79，84（D）40，38，46，84，56，79

三、分析題（每題8分，共40分）

1、設有一棵二叉樹的挨次存儲結構如下。⑴畫出該二叉樹；⑵分離寫出該二叉樹的中序遍歷序列和后序遍歷序列；

2、若以{7,9,13,6,5,3,17,10}作為葉子結點的權值，請構造對應的Huffman樹，然后求出其帶權路徑長度WPL。

3、設有帶權的無向圖的挨次存儲結構如下：⑴畫出該圖；⑵給出用普里姆(Prime)算法從頂點V2動身的最小生成樹。

4、將關鍵字序列（29，33，23，43，38，27，31，25，21）依次插入到初態(tài)為空的二叉排序樹中，請畫出所得到的樹T；然后畫出刪除23之后的二叉排序樹T1；最后再畫出在T1中插入23之后的二叉排序樹T2。

5、線性表的關鍵字集合{31，25，18，29，42，36，73，53，17，16，47，94，43}，共有13個元素，已知散列函數(shù)為：H（key）=keyMOD11，采納鏈地址法處理矛盾，請給出對應的散列表結構。

四、編寫算法（8分）

設單鏈表的結點結構定義如下，試寫一個函數(shù)Delete_linkList實現(xiàn)通過一趟遍歷刪除以L為頭結點的單鏈表中值在x到y(tǒng)(x的大小隨意y)之間的全部結點。

typedefstructLnode

{int