數(shù)據(jù)結(jié)構(gòu)試卷(a卷及答案)

《數(shù)據(jù)結(jié)構(gòu)試卷(a卷及答案)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)試卷（A卷）一、選擇題(30分)1．設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹(shù)中帶權(quán)路徑長(zhǎng)度之和為（）。(A)20(B)30(C)40(D)452．執(zhí)行一趟快速排序能夠得到的序列是（）。(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)，則其判空條件是（）。(A)head==0(B)head

2、->next==0(C)head->next==head(D)head!=04．時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序5．設(shè)二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹(shù)滿(mǎn)足的條件是（）。(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)

3、4(C)5(D)68．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(n2)(C)O(n1/2)(D)O(1og2n)9．二路歸并排序的時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹(shù)中最少有（）個(gè)結(jié)點(diǎn)。(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-111.設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（）。(A)front->next

4、=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ù)雜度為（）。(A)O(n+e)(B)O(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)10214.設(shè)二叉排序樹(shù)上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為（）。(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O

5、(1og2n)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ù)之和二、判斷題(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．滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。（）5．設(shè)一棵二叉樹(shù)的先序序列和后序序列，則能夠唯一確定出該二叉樹(shù)的形狀。（）6

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.快速排序是排序算法中平均性能最好的一種排序。（）三、填空題(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時(shí)間復(fù)雜度為_(kāi)________。2．設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的新結(jié)點(diǎn)X，則進(jìn)行插入操作的語(yǔ)句序列為_(kāi)_________________________（設(shè)結(jié)點(diǎn)的

7、指針域?yàn)閚ext）。3．設(shè)有向圖G的二元組形式表示為G=（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓?fù)渑判蛐蛄衉_________。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ì)列為空的條件為_(kāi)____________________。7．設(shè)二叉樹(shù)中

8、結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件