《數(shù)據(jù)結(jié)構(gòu)》模擬試題09

《數(shù)據(jù)結(jié)構(gòu)》模擬試題09

一、單項(xiàng)選擇題(每題2分，共30分)

1.設(shè)一組權(quán)值集合W={2,3,4,5,6},則由該權(quán)值集合構(gòu)造的哈夫曼樹(shù)中帶權(quán)路徑長(zhǎng)度之和為()o

(A)20(B)30(C)40(D)45

2.執(zhí)行一趟快速排序能夠得到的序列是()o

(A)[41,12,34,45,27]55[72,63]

(B)[45,34,12,41]55[72,63,27]

(C)[63,12,34,45,27]55[41,72]

(D)[12,27,45,41]55[34,63,72]

3.設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是()o

(A)head==0(B)head->next==0

(C)head->next==head(D)head!=0

4.時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是(

(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序

5.設(shè)二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹(shù)滿足的條件是()。

(A)空或只有一個(gè)結(jié)點(diǎn)(B)高度等于其結(jié)點(diǎn)數(shù)

(C)任一結(jié)點(diǎn)無(wú)左孩子(D)任一結(jié)點(diǎn)無(wú)右孩子

6.一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是()。

(A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序

7.設(shè)某棵三叉樹(shù)中有40個(gè)結(jié)點(diǎn)，則該三叉樹(shù)的最小高度為()。

(A)3(B)4(C)5(D)6

8.順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為()。

(A)O(n)(B)O(n2)(C)O(nl/2)(D)O(log2n)

9.二路歸并排序的時(shí)間復(fù)雜度為()。

(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(log2n)

10.深度為k的完全二叉樹(shù)中最少有()個(gè)結(jié)點(diǎn)。

(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1

11.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s

指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X,則入隊(duì)列的操作序列為()。

(A)front->next=s；front=s；(B)s->next=rear；rear=s；

(C)rear->next=s；rear=s；(D)s->next=front；front=s；

12.設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為()o

(A)O(n+e)(B)0(n2)(C)O(ne)(D)O(n3)

13.設(shè)某哈夫曼樹(shù)中有.199個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有()個(gè)葉子結(jié)點(diǎn)。

(A)99(B)100(C)101(D)102

14.設(shè)二叉排序樹(shù)上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為()o

(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(log2n)

15.設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為()。

(A)第i行非0元素的個(gè)數(shù)之和(B)第i列非0元素的個(gè)數(shù)之和

(C)第i行0元素的個(gè)數(shù)之和(D)第i列0元素的個(gè)數(shù)之和

二、填空題(每題2分，共20分)

1.for(i=l,t=l,s=0；i<=n；i++){t=t*i；s=s+t；}的時(shí)間復(fù)雜度為。

2.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的新結(jié)點(diǎn)X,則進(jìn)行插入操作的語(yǔ)句序

列為(設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext)。

3.設(shè)有向圖G的二元組形式表示為G=(D,R),D={1,2,3,4,5},R={r},r={<l,2>,<2,4>,

<4,5>,<1,3>,<3,2>,<3,5>},則給出該圖的--種拓?fù)渑判蛐蛄小?/p>

4.設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖中每個(gè)頂點(diǎn)的度數(shù)最多是。

5.設(shè)二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為50,度數(shù)為1的結(jié)點(diǎn)數(shù)為30,則該二叉樹(shù)中總共有個(gè)結(jié)

點(diǎn)數(shù)。

6.設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為

7.設(shè)二叉樹(shù)中結(jié)點(diǎn)的兩個(gè)指針域分別為Ichild和rchild,則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)

的條件是。

8.簡(jiǎn)單選擇排序和直接插入排序算法的平均時(shí)間復(fù)雜度為。

9.快速排序算法的空間復(fù)雜度平均情況下為,最壞的情況下為。

10.散列表中解決沖突的兩種方法是和。

三、判斷題(每題2分，共20分)

1.調(diào)用一次深度優(yōu)先遍歷可以訪問(wèn)到圖中的所有頂點(diǎn)。()

2.分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。（）

3.冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）

4.滿二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)。（）

5.設(shè)一棵二叉樹(shù)的先序序列和后序序列，則能夠唯一確定出該二叉樹(shù)的形狀。（）

6.層次遍歷初始堆可以得到一個(gè)有序的序列。（）

7.設(shè)一棵樹(shù)T可以轉(zhuǎn)化成二叉樹(shù)BT,則二叉樹(shù)BT中一定沒(méi)有右子樹(shù)。（）

8.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。（）

9.中序遍歷二叉排序樹(shù)可以得到一個(gè)有序的序列。（）

10.快速排序是排序算法中平均性能最好的一種排序。（）

四'算法設(shè)計(jì)題（每題10分，共30分）

1.設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。

2.設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。

3.在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法。

《數(shù)據(jù)結(jié)構(gòu)》模擬試題09參考答案

一、單項(xiàng)選擇題（每題2分，共30分）

1.D2.A3.A4.A5.D

6.D7.B8.A9.C10.B

11.C12.A13.B14.D15.B

二、填空題(每小題2分，共20分)

1.O(n)

2.s->next=p->next;p->next=s

3.(1,3,2,4,5)

4.n-1

5.129

6.F==R

7.p->lchild==0&&p->rchild==0

8.O(n2)

9.O(nlog2n),O(n)

10.開(kāi)放定址法，鏈地址法

三、判斷題(每題2分，共20分)

1.錯(cuò)2.對(duì)3.對(duì)4.對(duì)5.錯(cuò)

6.錯(cuò)7.對(duì)8.錯(cuò)9.對(duì)10.對(duì)

四、算法設(shè)計(jì)題(每題10分，共30分)

1.設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。

structrecord{intkey;intothers;};

intbisearch(structrecordr[],intk)

(

intlow=0,mid,high=n-l;

while(low<=high)

{

mid=(low+high)/2;

if(r[mid].key==k)return(mid+l);elseif(rfmid].key>k)high=mid-l;elselow=mid+l;

)

retum(O);

2.設(shè)計(jì)判斷二叉樹(shù)是否為二叉排序樹(shù)的算法。

intminnum=-32768,flag=l;

typedefstructnode{