1. 試分析下列各算法的時(shí)間復(fù)雜度。(5分)

（1）s=0;

?? ??for i=0; i<n; i++)

for(j=0; j<n; j++)

? ???????{ scanf(“%d”,&a[i][j]);

?????????? s+= a[i][j];

?

}????????????????? （2分）

（2）i=1;

? ???while(i<=n)

??????? i=i*2;??????????????? （3分）

?

答案:（1）O(n2)???????????

? （2）O(log2n)

2．對(duì)于一個(gè)棧，設(shè)輸入序列為A ,B ,C ,D ,E，F(xiàn)，為了得到出棧序列： C, B，E,D,A，F(xiàn),需執(zhí)行什么樣的進(jìn)棧（push）、出棧（pop）運(yùn)算序列？(5分)

?

答案:push, push, push,pop,pop,push,push,pop,pop,pop,push,pop

答案

題目

先序序列: A B D F C E G H ，中序序列： B F D A G E H C;后序序列:F D B G H E C A

題目

5.假設(shè)用于通信的電文僅由8個(gè)字母(A，B，C，D，E，F(xiàn)，G，H)組成，字母在電文中出現(xiàn)的頻率分別為7， 19， 2， 6， 32， 3， 21，10。

(1)試為這8個(gè)字母設(shè)計(jì)赫夫曼樹(shù);(3分)

(2) 試為這8個(gè)字母設(shè)計(jì)赫夫曼編碼。(2分)

1

2

6.已知圖所示的有向圖，請(qǐng)給出

(1)鄰接矩陣；（2分）

(2)鄰接表。（3分）

1

2

7. 已知圖的鄰接表如圖所示，

（1）試從頂點(diǎn)v0出發(fā)，寫(xiě)出按廣度優(yōu)先遍歷的結(jié)果；（3分）

（2）試從頂點(diǎn)v0出發(fā)，寫(xiě)出按深度優(yōu)先遍歷的結(jié)果是。（2分）

答案：（1）0 1 2 3或v0，v1，v2，v3；

（2）0 1 2 3或v0，v1，v2，v3；

8對(duì)下圖所示的無(wú)向圖，請(qǐng)給出：

（1）最小生成樹(shù)（3分）

（2）按普里姆（Prim）算法，請(qǐng)寫(xiě)出加入頂點(diǎn)的順序（2分）

答案：（1）

(2)加入頂點(diǎn)的順序: 0,5,4, 3,2, 1

9. 設(shè)待排序的關(guān)鍵字序列為{12，2，16，30，28，10，16*，20，6，18}，試寫(xiě)出采用直接插入排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。(5分)

答案：直接插入排序

[2??? 12]?? 16?? 30?? 28?? 10?? 16*?? 20?? 6??? 18????????

[2??? 12??? 16]? 30?? 28?? 10?? 16*?? 20?? 6??? 18????????

[2??? 12??? 16?? 30]? 28?? 10?? 16*?? 20?? 6??? 18????????

[2??? 12??? 16?? 28?? 30]? ?10?? 16*?? 20?? 6??? 18????????

[2??? 10??? 12?? 16?? 28? ?30]?? 16*? ?20?? 6??? 18????????

[2??? 10??? 12?? 16?? 16*? ?28?? 30]?? 20?? 6??? 18????????

[2??? 10??? 12?? 16?? 16* ??20?? 28?? 30]?? 6??? 18????????

[2??? 6???? 10?? 12?? 16? ?16*?? 20?? 28?? 30]?? 18????????

[2??? 6???? 10?? 12?? 16 ??16*??? 18?? 20?? 28?? 30]

?

10.折半查找有序表（4，6，10，12，20，30，50，70，88，100，120）。若查找表中元素50，則算法將依次與表中哪些元素比較大小才以成功結(jié)束？(5分)

答案：（30，88，50）

?