中文字幕免费精品_亚洲视频自拍_亚洲综合国产激情另类一区_色综合咪咪久久

易賢網(wǎng)網(wǎng)校上線了！

>>>點(diǎn)擊進(jìn)入 <<<

網(wǎng)校開發(fā)及擁有的課件范圍涉及公務(wù)員、財(cái)會(huì)類、外語類、外貿(mào)類、學(xué)歷類、

職業(yè)資格類、計(jì)算機(jī)類、建筑工程類、等9大類考試的在線網(wǎng)絡(luò)培訓(xùn)輔導(dǎo)。

專業(yè)名稱：計(jì)算機(jī)應(yīng)用技術(shù)

考試科目：數(shù)據(jù)結(jié)構(gòu)（共150分）

一、選擇題（本題共10個(gè)小題，每小題3分，共計(jì)30分）

1． 設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（ ）。

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

2．執(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且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是（ ）。

(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è)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ ）。

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

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

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

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

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

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

8．順序查找不論在順序線性表中還是在鏈?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的完全二叉樹中最少有（ ）個(gè)結(jié)點(diǎn)。

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

二、填空題（本題共10個(gè)小題，每小題3分，共計(jì)30分）

1．for(i=1，t=1，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)行插入操作的語句序列為__________________________（設(shè)結(jié)點(diǎn)的指針域?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è)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖中每個(gè)頂點(diǎn)的度數(shù)最多是_________。

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

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

7．設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是___________________________________________。

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

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

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

三、判斷題（本題共10個(gè)小題，每小題3分，共計(jì)30分）

（請(qǐng)?jiān)谛☆}括號(hào)內(nèi)打√或×）

1．不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。（ ）

2．當(dāng)向二叉排序樹中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（ ）

3．設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。（ ）

4．完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（ ）

5．哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。（ ）

6．對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。（ ）

7．先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。（ ）

8．由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（ ）

9．線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（ ）

10.帶權(quán)無向圖的最小生成樹是唯一的。（ ）

四、簡答題（本題共2個(gè)小題，每小題15分，共計(jì)30分）

1、設(shè)一棵二叉樹的先序序列為 ABDGECFH，中序序列為：DGBEAFHC 。試還原該二叉樹，并畫出該樹的后序線索樹。

2．假設(shè)用于通信的電文由字符集{a,b,c,d,e,f,g}中的字母構(gòu)成。它們?cè)陔娢闹谐霈F(xiàn)的頻度分別為{0.31,0.16,0.10,0.08,0.11,0.20,0.04},

(1) 為這 7個(gè)字母設(shè)計(jì)哈夫曼編碼；

(2）對(duì)這 7 個(gè)字母進(jìn)行等長編碼，至少需要幾位二進(jìn)制數(shù)？哈夫曼編碼比等長編碼使電文總長壓縮多少？

五、算法題（本題共2個(gè)小題，每小題15分，共計(jì)30分）

⒈設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。

2.設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。

更多學(xué)歷考試信息請(qǐng)查看學(xué)歷考試網(wǎng)