2010-2011上期末試卷數(shù)據(jù)結(jié)構(gòu)

《2010-2011上期末試卷數(shù)據(jù)結(jié)構(gòu)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、裝訂線學(xué)院：專業(yè)：學(xué)號：姓名：教學(xué)班號：線封密云南農(nóng)業(yè)大學(xué)2010—2011學(xué)年上學(xué)期期末考試數(shù)據(jù)結(jié)構(gòu)試卷（A卷）（課程代碼3111003）本試題滿分100分，考試時間120分鐘。題號一二三四五六七八總分得分閱卷人一．選擇題。（每小題2分，共40分）1．組成數(shù)據(jù)的基本單位是（）。(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量2．設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。(A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)圖型結(jié)構(gòu)(D)集合3．?dāng)?shù)組

2、的邏輯結(jié)構(gòu)不同于下列（）的邏輯結(jié)構(gòu)。(A)線性表(B)棧(C)隊列(D)樹4．二叉樹中第i(i≥1)層上的結(jié)點數(shù)最多有（）個。(A)2i(B)2i(C)2i-1(D)2i-15．設(shè)指針變量p指向單鏈表結(jié)點A，則刪除結(jié)點A的后繼結(jié)點B需要的操作為（）。(A)p->next=p->next->next(B)p=p->next(C)p=p->next->next(D)p->next=p6．設(shè)棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進(jìn)入隊列Q，若6個元素出列的順序為E2、E4、E3、E6

3、、E5和E1，則棧S的容量至少應(yīng)該是（）。(A)6(B)4(C)3(D)2第1頁（共7頁）7．將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為（）。(A)100(B)40(C)55(D)808．設(shè)結(jié)點A有3個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙親結(jié)點，則結(jié)點B的度數(shù)數(shù)為（）。(A)3(B)4(C)5(D)19．根據(jù)二叉樹的定義可知二叉樹共有（）種不同的形態(tài)。(A)4(B)5(C)6(D)710.設(shè)有以下四種排序方法，則（）的空間復(fù)雜度最大。(A)冒泡排序(B)快速排序(C)堆排序(D)希爾排序11．下面關(guān)于線性表的敘述錯誤的是（）

4、。(A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B)線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C)線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn)12．設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。(A)2m-1(B)2m(C)2m+1(D)4m13．設(shè)順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（）。(A)R-F(B)F-R

5、(C)(R-F+M)％M(D)(F-R+M)％M14．設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。(A)BADC(B)BCDA(C)CDAB(D)CBDA15．設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-116．設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（）。(A)9(B)10(C)11(D)12第2頁（共7頁）17．設(shè)某有向圖中有n個頂點，則該有向圖對應(yīng)的鄰接表中有（）個表頭結(jié)點。(A)n-1(B

6、)n(C)n+1(D)2n-118．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）。(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，819．設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（）。(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，

7、40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，8520．下面程序的時間復(fù)雜為（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)二．填空題。（每空1分，共15分）。1.通常從四個方面評價算法的質(zhì)量：_________、_________、_________和_________。2.中序遍歷二叉排序樹所得到的序列是___

8、________序列（填有序或無序）3.?設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為________