《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案

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

《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案

(2022-2022學(xué)年第2學(xué)期)

一、單項(xiàng)挑選題

1．對(duì)于一個(gè)算法，當(dāng)輸入非法數(shù)據(jù)時(shí)，也要能作出相應(yīng)的處理，這種要求稱為（）。

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

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

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樹的帶權(quán)路徑長(zhǎng)度WPL等于（）

（A）、除根結(jié)點(diǎn)之外的全部結(jié)點(diǎn)權(quán)值之和（B）、全部結(jié)點(diǎn)權(quán)值之和

（C）、各葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和（D）、根結(jié)點(diǎn)的值

10．線索二叉鏈表是利用（）域存儲(chǔ)后繼結(jié)點(diǎn)的地址。

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

二、填空題

1．規(guī)律結(jié)構(gòu)打算了算法的，而存儲(chǔ)結(jié)構(gòu)打算了算法的。

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

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

q

p

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

隨意寫出二種拓?fù)渑判蛐蛄校骸ⅰ?/p>

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

三、應(yīng)用題

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

(1)構(gòu)造HASH表。

(2)分離求查找勝利和不勝利時(shí)的平均查找長(zhǎng)度。

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

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

AB

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

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

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

ABCDEF??

??∞∞∞∞∞∞356156BA

（1）求從頂點(diǎn)A開頭的最小生成樹。

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

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

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

（1）畫出對(duì)應(yīng)的Huffman樹。（2）計(jì)算帶權(quán)路徑長(zhǎng)度WPL。

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

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

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

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

1．已知線性表（a1,a2,…,an）以挨次存儲(chǔ)結(jié)構(gòu)為存儲(chǔ)結(jié)構(gòu)，其類型定義如下：

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

typedefstruct{

Elemtype*elem;//挨次存儲(chǔ)空間基址

intlength;//當(dāng)前長(zhǎng)度（存儲(chǔ)元素個(gè)數(shù)）

}SqList;

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

StatusListDelete(Sqlist//棧底指針

Elemtype*top;//棧頂指針

}Stack;

設(shè)計(jì)算法，將棧頂元素出棧并存入e中．base

3．設(shè)二叉鏈樹的類型定義如下：

typedefintElemtype;

typedefstructnode{

Elemtypedata;

structnode*lchild,*rchild;

}BinNode,*BinTree;

試寫出求該二叉樹葉子結(jié)點(diǎn)數(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．設(shè)計(jì)、實(shí)現(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

二、應(yīng)用題

1（1）Hash表（4分）

（2）查找勝利的平均查找長(zhǎng)度：（1分）

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

查找不勝利的平均查找長(zhǎng)度：（1分）

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

2（1）、構(gòu)造（3分）

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

3、(5分，每行0.5)

4、初始關(guān)鍵字：[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分

三，設(shè)計(jì)題（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分）

平均時(shí)光復(fù)雜度：（2分）

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

∑=-=-=nininnE12

1)(