第一章緒論

討論題：

1.常用的存儲表示方法有哪幾種？

2.算法的時間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎？

思考題:

設(shè)n為正整數(shù)。試確定下列各程序段中前置以記號@的語句的頻度:

⑴i=l;

k=0;

while(i<=n-l){

@k+=10*i;

i++；}

(2)i=l;

k=0;

do{

@k+=10*i；

i++；

}while(i<=n-l);

(3)i=1;

k=0;

while(i<=n-l){

i++；

@k+=10*i;

)

(4)k=0;

for(i=l;i<=n;i++){

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

@k++;

)

(5)for(i=l;i<=n;i++){

for(j=l;j<=i;j++){

for(k=l;k<=j;k++)

@x+=delta;

(6)i=l;

j=0;

while(i+j<=n){

@if(i>j)j++;

elsei++;

(7)x=n;//n是不小于1的常數(shù)

y=0;

while(x>-(y+l)*(y+l)){

@y++;

)

(8)x=91;

y=100;

while(y>0){

@if(x>100){x-=10;y-}

elsex++;

第二章線性表

討論題:

1.為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？

2.何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜?

思考題:

1.指出以下算法中的錯誤和低效之處，并把它改寫為一個既正確又高效的算法。

StatusDeleteK(SqList&a,intI,intk){〃本過程從順序存儲結(jié)構(gòu)的線性

表a中刪除第I個元素起的k個元素。

if(1<11|k<0||I+k>a.length)returnERROR;

else{

for(count=l;count<k;count++){//刪除一個元素

for(j=a.Length;j>=I+1;j一一)a.elem[j-l]=a.elem[j];

a.length--；

)

rreturnOK;

}//DeleteK

2.假設(shè)某個單向循環(huán)鏈表的長度大于1,且表中既無頭結(jié)點也無頭指針。已知s

為指向鏈表中某個結(jié)點指針，試編寫算法在鏈表中刪除指針s所指結(jié)點的前驅(qū)結(jié)

點。

第三章棧和隊列

討論題:

1.若以1234作為雙端隊列的輸入序列，試分別求出滿足以下條件的輸出序列：

1)能由輸入受限的雙端隊列得到，但不能由輸出受限的雙端隊列得到的輸出

序列；

2)能由輸出受限的雙端隊列得到，但不能由輸入受限的雙端隊列得到的輸出

序列；

3)既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的

輸出序列。

2.進棧序列為123,則可能得到的出棧序列是什么？

3.如果進棧序列為123456,則能否得到435612和135426的出棧序列，并請說

明為什么不能得到。

思考題:

1.設(shè)兩個棧共享空間兩棧的棧底分別設(shè)在向量的兩端，且每個元

素占一個分量。試設(shè)計這兩個棧的插入和刪除算法。

簡述以下算法的功能。

(1)voidDemol(SeqStack*S){

intI;arr[64];n=0;

while(StackEmpty(S))arr[n++]=Pop(S);

for(1=0,I<n;I++)Push(S,arr[I]);

}//Demol

(2)voidDemo3(CirQueue*Q){//設(shè)DataType為int型

intx;SeqStackS;

InitStack(&S);

while(!QueueEmpty(Q))

{x=DeQueue(Q);Push(&S,x);}

while(!StackEmpty(&s))

{x=Pop(&S);EnQueue(Q,x);}

}//Demo3

第四章串

思考題：

串與普通的線性表的區(qū)別？

第五章數(shù)組和廣義表

討論題:

1.疏矩陣的稀疏程度達(dá)到多少時，采用三元組存儲的空間節(jié)省于數(shù)組存儲？

思考題：

1.設(shè)有三對角矩陣An*n,將其三條對角線上的元素逐行地存儲到向量

B[0…3n-3]中,使得B[k]=aij,求:

1)用I,j表示k的下標(biāo)變換公式。

2)用k表示I,j的下標(biāo)變換公式

2.利用廣義表的GetHead和GetTail操作寫出函數(shù)表達(dá)式，把原子banana

分別從下列廣義表中分離出來。

LI=(apple,pear,banana,orange);

L2=((((apple),pear),banana),orange);

L3=(apple,(pear,(banana),orange));

第六章樹和二叉樹

討論題：

1.試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。

2.已知在一棵含有n個結(jié)點的樹中，只有度為k的分支結(jié)點和度為0的葉子

結(jié)點。試求該樹含有的葉子結(jié)點的數(shù)目。

思考題:

1.試分別推導(dǎo)含n個結(jié)點和含nO個葉子結(jié)點的完全三叉樹的深度Ho

2.找出所有滿足下列條件的二叉樹：

1）它們在先序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同；

2）它們在后序遍歷和中序遍歷時，得到的結(jié)點訪問序列相同；

3）它們在先序遍歷和后序遍歷時，得到的結(jié)點訪問序列相同；

假設(shè)一棵二叉樹的前序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJKo請畫

出該樹。

第七章圖

討論題：

1.已知以二維數(shù)組表示的圖的鄰接矩陣。如何畫出自某個頂點出發(fā)進行遍歷所

得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。

2.如何畫出有向無環(huán)圖中全部可能的拓?fù)溆行蛐蛄小?/p>

思考題：

采用鄰接表存儲結(jié)構(gòu)，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在

一條長度為k的簡單路徑的算法。

第九章查找

討論題:

1.若對大小均為n的有序的順序表和無序的順序表分別進行順序查找，試在下

列三種情況下分別討論兩者在等概時的平均查找長度是否相同？

1）查找不成功，即表中沒有關(guān)鍵字等于給定值K的記錄；

2）查找成功，且表中只有一個關(guān)鍵字等于給定值K的記錄；

3）查找成功，且表中有若干個關(guān)鍵字等于給定值K的記錄，一次查找要求找

出所有記錄。此時的平均查找長度應(yīng)考慮找到所有記錄時所用的比較次數(shù)。

思考題:

1.在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為20、30、8、12、34、5、60、

5、1,29,請畫出所得到的二叉查找樹。

2.畫出對長度為18的有序的順序表進行二分查找的判定樹，并指出在等概率時

查找成功的平均查找長度，以及查找失敗時所需的最多的關(guān)鍵字比較次數(shù)。

3.畫出對長度為10的有序表進行折半查找的判定樹，并求其等概時查找成功

的平均查找長度。

4.已知如下所示長度為12的表

（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）

試按表中元素的順序依次插入一棵初始為空的二叉排序樹.，請畫出插入完成之后

的平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。

第十章內(nèi)部排序

討論題:

1.以關(guān)鍵字序列（265,301,751,129,937,863,742,694,076,438）為例，

分別寫出執(zhí)行以下排序算法的各趟排序結(jié)束時，關(guān)鍵字序列的狀態(tài)。

1）直接插入排序

2）希爾排序

3）冒泡排序

4）快速排序

5）直接選擇排序

6）堆排序

7）歸并排序

8）基數(shù)排序

上述方法中，哪些是穩(wěn)定的排序？哪些是非穩(wěn)定的排序?對不穩(wěn)定的排序試舉出一

個不穩(wěn)定的實例。

思考題：

以單鏈表作為存儲結(jié)構(gòu)實現(xiàn)直接插入排序