千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦《數(shù)據(jù)結構》期末考試試題及答案貴州高校理學院數(shù)學系信息與計算科學專業(yè)

《數(shù)據(jù)結構》期末考試試題及答案

(2022-2022學年第2學期)

一、單項挑選題

1．對于一個算法，當輸入非法數(shù)據(jù)時，也要能作出相應的處理，這種要求稱為（）。

(A)、正確性(B).可行性(C).茁壯性(D).輸入性

2．設S為C語言的語句,計算機執(zhí)行下面算法時，算法的時光復雜度為（）。

for(i=n-1；i>=0；i--)

for(j=0；jnext;p->next=Q.front->next;

（B）、p=Q.front->next;Q.front->next=p->next;

（C）、p=Q.rear->next;p->next=Q.rear->next;

（D）、p=Q->next;Q->next=p->next;

9．Huffman樹的帶權路徑長度WPL等于（）

（A）、除根結點之外的全部結點權值之和（B）、全部結點權值之和

（C）、各葉子結點的帶權路徑長度之和（D）、根結點的值

10．線索二叉鏈表是利用（）域存儲后繼結點的地址。

（A）、lchild（B）、data（C）、rchild（D）、root

二、填空題

1．規(guī)律結構打算了算法的，而存儲結構打算了算法的。

2．棧和隊列都是一種的線性表，棧的插入和刪除只能在舉行。

3．線性表（a1,a2,…,an）的挨次存儲結構中，設每個單元的長度為L，元素ai的存儲地址LOC(ai)為4．已知一雙向鏈表如下(指針域名為next和prior)：

q

p

現(xiàn)將p所指的結點插入到x和y結點之間，其操作步驟為：；；；；5．n個結點無向徹低圖的的邊數(shù)為，n個結點的生成樹的邊數(shù)為。6．已知一有向無環(huán)圖如下：

隨意寫出二種拓撲排序序列：、。

7．已知二叉樹的中序遍歷序列為BCA，后序遍歷序列為CBA，則該二叉樹的先序遍歷序列為，層序遍歷序列為。

三、應用題

1．設散列函數(shù)H(k)=k%13,設關鍵字系列為{22,12,24,6,45,7,8,13,21},要求用線性探測法處理矛盾。(6分)

(1)構造HASH表。

(2)分離求查找勝利和不勝利時的平均查找長度。

2．給定表（19,14,22,15,20,21,56,10）.（8分）（1）按元素在表中的次序，建立一棵二叉排序樹

（2）對(1)中所建立的二叉排序樹舉行中序遍歷，寫出遍歷序列。（3）畫出對(2)中的遍歷序列舉行折半查找過程的判定樹。3．已知二個稀疏矩陣A和B的壓縮存儲三元組表如下：

AB

寫出A-B壓縮存儲的三元組表。（5分）

4．已知一維數(shù)組中的數(shù)據(jù)為（18,12,25,53,18）,試寫出插入排序（升序）過程。并指出具有n個元素的插入排序的時光復雜度是多少？(5分)

5．已知一網(wǎng)絡的鄰接矩陣如下，求從頂點A開頭的最小生成樹。(8分，要有過程)

ABCDEF??

??∞∞∞∞∞∞356156BA

（1）求從頂點A開頭的最小生成樹。

（2）分離畫出以A為起點的DFS生成樹和BFS生成樹。

6．已知數(shù)據(jù)六個字母及在通信中浮現(xiàn)頻率如下表：

把這些字母和頻率作為葉子結點及權值，完成如下工作(7分，要有過程)。

（1）畫出對應的Huffman樹。（2）計算帶權路徑長度WPL。

（3）求A、B、C、D、E

、F的Huffman編碼。7．已知有如下的有向網(wǎng)：

求頂點A到其它各頂點的最短路徑（采納Dijkstra算法，要有過程）。（6分）

三、設計題（30分，每題10分,用C語言寫出算法，做在答題紙上）

1．已知線性表（a1,a2,…,an）以挨次存儲結構為存儲結構，其類型定義如下：

#defineLIST_INIT_SIZE100//挨次表初始分配容量

typedefstruct{

Elemtype*elem;//挨次存儲空間基址

intlength;//當前長度（存儲元素個數(shù)）

}SqList;

設計一個算法，刪除其元素值為x的結點（假若x是唯一的）。并求出其算法的平均時光復雜度。其算法函數(shù)頭部如下：

StatusListDelete(Sqlist//棧底指針

Elemtype*top;//棧頂指針

}Stack;

設計算法，將棧頂元素出棧并存入e中．base

3．設二叉鏈樹的類型定義如下：

typedefintElemtype;

typedefstructnode{

Elemtypedata;

structnode*lchild,*rchild;

}BinNode,*BinTree;

試寫出求該二叉樹葉子結點數(shù)的算法:

StatusCountLeaves(BinTree&root,int&n)

{//nisthenumberofleaves

……

}

答案：

挑選題（每題1分）

1、C

2、D

3、A

4、D

5、C

6、D

7、A

8、B

9、C10、C

一、填空題

1．設計、實現(xiàn)

2．特別、棧頂

3．LOC（a1）+(i-1)*L

4．p->next=q->next;q->next->prior=p;q->next=p;p->prior=q;5．n(n-1)/2、n-1

6．ADCBFEG、ABCDEFFG

7．ABC、ABC

二、應用題

1（1）Hash表（4分）

（2）查找勝利的平均查找長度：（1分）

（5*1+1*2+2*3+1*7）/9=20/9

查找不勝利的平均查找長度：（1分）

（2+1+9+8+7+6+5+4+3+2+1）/13=

2（1）、構造（3分）

(2)、1014151920212256（2分）（3）、（3分）

3、(5分，每行0.5)

4、初始關鍵字：[18]12255318

第一趟：[1218]255318

其次趟：[121825]5318

第三趟：[12182553]18

第四趟：[1218182553]（4分）O（n2）（1分）。

5、7分

（1）4分

A

B1C

32

（2）4分

5D4

EF

6、(1)3分

（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21=(1分)（3）A：010B：011C：110D：111E：00F；10（3分）12、A-B：（A、B）1分

A-C：（A、D、C）2分

A-D：（A、D）1分

A-E：（A、D、E）2分

三，設計題（20分）

1、(10分)

StatusListDelete(Sqlist

for(i=0;ilength;i++)

if(L->elem[i]==x)break;

if(i=L->length)returnERROR;

for(j=i;jlengthi-1;j++)

L->elem[j]=L->elem[j+1];

L->length--;

}（8分）

平均時光復雜度：（2分）

設元素個數(shù)記為n，則平均時光復雜度為：

∑=-=-=nininnE12

1)(