2023-2023學(xué)年二學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試試卷

2024-2024學(xué)年二學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試試卷長沙理工高校計算機與通信工程學(xué)院

2024-2024學(xué)年二學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試模擬試卷(3卷)

班級:___________學(xué)號:___________姓名:___________得分:___________

題目部分，(卷面共有35題,100分,各大題標(biāo)有題量和總分)

一、應(yīng)用題(2小題,共16分)

1．對給定的一組權(quán)值W＝（5，2，9，11，8，3，7），試構(gòu)造相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。

2．分析下面各程序段的時間簡單度

（1）s1(intn)

{intp=1,s=0;

for(i=1;i0）個結(jié)點的滿二叉樹共有（）個葉子結(jié)點和（）個非終端結(jié)點。

7．假設(shè)線性表的長度為n，則在最壞狀況下，冒泡排序需要的比較次數(shù)為（）

8．評價基于比較的排序算法的時間性能，主要標(biāo)準(zhǔn)是（）和（）。

9．實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的基本存儲方法有：（），（）。

長沙理工高校計算機與通信工程學(xué)院

2024-2024學(xué)年二學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試模擬試卷(3卷)答案部分，(卷面共有35題,100.0分,各大題標(biāo)有題量和總分)

一、應(yīng)用題(2小題,共16分)

1．構(gòu)造的哈夫曼樹如圖所示。

樹的帶權(quán)路徑長度為：

WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2

=120

2．O(n)O(n2)

二、推斷正誤(6小題,共12分)

1．錯

2．對

3．對

4．對

5．錯

6．錯。如數(shù)組就沒有插入和刪除操作。

三、單項選擇題(15小題,共30分)

1．A

2．B

3．D

4．B

5．D

6．C

7．C

8．A

9．B

10．B

11．A

12．B

13．D

14．A

15．B

四、算法設(shè)計題(3小題,共24分)

1．intisriselk(lklist*head)

{

if(head==0||head->next==0)return(1);

else

for(q=head,p=head->next;p!=0;q=p,p=p->next)

if(q->data>p->data)return(0);

return(1);

}

2．要想得到后序的逆序，只要根據(jù)后序遍歷相反的挨次即可，即先訪問根結(jié)點，再遍歷根結(jié)點的右子樹，最終遍歷根結(jié)點的左子樹。

voidPostordern(BiTree*H)

{if(H)

{visit(H->data);

Postordern(H->rchild);

Postordern(H->lchild);

}

}

3．voidcountnode(bitree*bt,intcountnode(bt->lchild,count);countnode(bt->rchild,count);}}

五、填空題(9小題,共18分)

1．循環(huán)鏈表，雙鏈表

2．O（1）O(1)

3．12

4．d+41。元素A的前面共存儲了(1+2+…+8)+5=41個元素。

5．（1）5（2）3

6．2i-1，(n+1)/