北京科技大學(xué)2015年數(shù)據(jù)結(jié)構(gòu)與算法分析試卷+答案

1、數(shù)據(jù)結(jié)構(gòu)與算法分析試卷第1頁(yè)共5頁(yè)北京科技大學(xué)20152016學(xué)年第1學(xué)期數(shù)據(jù)結(jié)構(gòu)與算法分析試卷院(系)班級(jí)學(xué)號(hào)姓名試卷卷面成績(jī)題號(hào)一二三四五六七小計(jì)占課程考核成績(jī)70%平時(shí)成績(jī)占30%課程考核成績(jī)得分一、（30分）選擇題1.設(shè)一組權(quán)值集合W=2，3，4，5，6，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長(zhǎng)度之和為()。(A)20(B)30(C)48(D)452.執(zhí)行一趟快速排序能夠得到的序列是()。(A)[41，12，34，45，27]5

2、5[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è)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（）。(A)q=pnext；pdata=qdata；pnext=qnext；free(q)；(B)q=pnext；qdata=pdata；pnext=qnext；free(

3、q)；(C)q=pnext；pnext=qnext；free(q)；(D)q=pnext；pdata=qdata；free(q)；4.時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是()。(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序5.設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是()。得分裝訂線內(nèi)不得答題自覺遵守考試規(guī)則，誠(chéng)信考試，絕不作弊數(shù)據(jù)結(jié)構(gòu)與算法分析試卷第3頁(yè)共5頁(yè)二、判斷題二、判斷題

4、(20(20分)1.調(diào)用一次深度優(yōu)先遍歷可以訪問(wèn)到圖中的所有頂點(diǎn)。()2.完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（）3.冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。()4.滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。()5.設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。()6.層次遍歷初始堆可以得到一個(gè)有序的序列。()7.設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。(

5、)8.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。()9.中序遍歷二叉排序樹可以得到一個(gè)有序的序列。()10.快速排序是排序算法中平均性能最好的一種排序。()三、（30分）填空題1.f(i=1，t=1，s=0i，，，，，，則給出該圖的一種拓?fù)渑判蛐蛄衉_________。4.設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖中每個(gè)頂點(diǎn)的度數(shù)最多是_________。5.設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹中總共有______