數(shù)據(jù)結(jié)構(gòu)與算法（C語(yǔ)言）習(xí)題答案 （千鋒教育） 第1-9章

數(shù)據(jù)結(jié)構(gòu)與算法(C語(yǔ)言)習(xí)題答案(千鋒教育)

1.填空題

(1)數(shù)據(jù)(2)數(shù)據(jù)元素(3)數(shù)據(jù)項(xiàng)

(4)數(shù)據(jù)對(duì)象(5)結(jié)構(gòu)(6)邏輯結(jié)構(gòu)、物理結(jié)構(gòu)

2.選擇題

(1)D(2)B(3)B(4)D(5)C(6)B

3.思考題

(1)邏輯結(jié)構(gòu)分為4種類型。

線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系，即數(shù)據(jù)元素存在依次排列的先后次序關(guān)

系，且只有一個(gè)起始數(shù)據(jù)元素和一個(gè)終止數(shù)據(jù)元素。

樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系，即層次關(guān)系或分支關(guān)系。這種結(jié)構(gòu)只

有一個(gè)起始數(shù)據(jù)元素(稱為樹根)，其他數(shù)據(jù)元素稱為樹葉。

圖形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的網(wǎng)絡(luò)關(guān)系，即數(shù)據(jù)元素之間相互連接成網(wǎng)狀。

集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬一個(gè)集合外，它們之間沒有其他關(guān)系。各個(gè)元素是

“平等”的，該結(jié)構(gòu)類似于數(shù)學(xué)中的集合。

(2)物理結(jié)構(gòu)即存儲(chǔ)結(jié)構(gòu)，主要指的是數(shù)據(jù)的邏輯結(jié)構(gòu)在實(shí)際的計(jì)算機(jī)內(nèi)存中存儲(chǔ)的

形式。通常數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有以下4種類型。

順序存儲(chǔ)指的是將相鄰的數(shù)據(jù)元素存放在計(jì)算機(jī)地址連續(xù)的存儲(chǔ)單元中

鏈?zhǔn)酱鎯?chǔ)中，邏輯上相鄰的數(shù)據(jù)元素在內(nèi)存上不一定也相鄰，簡(jiǎn)單地說，鏈?zhǔn)酱鎯?chǔ)中

的數(shù)據(jù)元素存儲(chǔ)在內(nèi)存的任意位置。

索引存儲(chǔ)指的是在存儲(chǔ)數(shù)據(jù)元素的同時(shí)建立索引列表，存儲(chǔ)元素之間的關(guān)系。這是一

種為了加速檢索而創(chuàng)建的存儲(chǔ)結(jié)構(gòu)。

散列存儲(chǔ)指的是根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計(jì)算出該數(shù)據(jù)元素的存儲(chǔ)位置。

(3)算法有5個(gè)基本的特性：輸入、輸出、有窮性、確定性、可行性。

一個(gè)算法可以有多個(gè)或沒有輸入，具體的輸入量取決于算法中的數(shù)據(jù)對(duì)象。

一個(gè)算法必須有一個(gè)或多個(gè)輸出，這些輸出是算法對(duì)輸入進(jìn)行運(yùn)算后的結(jié)果。

有窮性指的是算法在執(zhí)行有限的操作次數(shù)后自動(dòng)停止，不會(huì)出現(xiàn)無限循環(huán)的情況，且

每次操作都可以在有限時(shí)間內(nèi)完成。

確定性指的是算法的每次操作都具有確定的含義，不會(huì)出現(xiàn)二義性。

可行性指的是算法中描述的操作都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。

簡(jiǎn)單地說，算法可以轉(zhuǎn)換為程序上機(jī)運(yùn)行，并可以得到正確的結(jié)果。

(4)對(duì)于同一個(gè)問題，可以有很多種算法。因此，判斷一個(gè)算法是否為最優(yōu)算法，可

以從以下4個(gè)方面考慮。

算法的正確性指的是算法能正確反映問題的需求，能經(jīng)得起一切可輸入數(shù)據(jù)的測(cè)試。

可讀性指的是算法的設(shè)計(jì)應(yīng)該盡可能簡(jiǎn)單，便于閱讀、理解。

健壯性指的是算法可以對(duì)不合法的輸入數(shù)據(jù)做出處理，而不是產(chǎn)生異?；驑O端的結(jié)果。

高效率指的是算法的執(zhí)行時(shí)間要盡量短，對(duì)存儲(chǔ)空間的使用要盡可能少。在滿足前3

個(gè)要求的前提下，高效率是決定算法是否優(yōu)劣的重要指標(biāo)。

(5)事后統(tǒng)計(jì)法指的是通過設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)，利用計(jì)算機(jī)本身對(duì)不同算法程

序的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低。

事前分析法指的是在設(shè)計(jì)算法程序前，根據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。一個(gè)好的算法

所消耗的時(shí)間，應(yīng)該是算法中每條語(yǔ)句執(zhí)行的時(shí)間之和，每條語(yǔ)句的執(zhí)行時(shí)間是該語(yǔ)句的

執(zhí)行次數(shù)與該語(yǔ)句執(zhí)行一次所需時(shí)間的乘積。

(6)如果有某個(gè)輔助函數(shù)f(n),并且存在一個(gè)正常數(shù)c使得f(n)*c>=T(n)恒成立，記

作T(n)=O(f(n))。通常將O(f(n))稱為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。使用0()計(jì)

算時(shí)間復(fù)雜度的記法稱為大O記法。一般情況下，隨著n的增大，T(n)增長(zhǎng)最慢的算法為

最優(yōu)算法。

通過計(jì)算算法存儲(chǔ)量可以得到算法的空間復(fù)雜度，算法空間復(fù)雜度的計(jì)算公式記作

S(n)=O(f(n)),其中，n為問題的規(guī)模，f(n)為語(yǔ)句關(guān)于n所占存儲(chǔ)空間的函數(shù)。隨著問題規(guī)

模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與f(n)的增長(zhǎng)率相同。

4.編程題

(1)i=s=O；while(s<n){i++；s+=i；}

習(xí)題答案

L填空題

（1）線性（2）順序表（3）單鏈表

（4）數(shù)據(jù)域、指針域（5）頭結(jié)點(diǎn)（6）一定（7）不一定

2.思考題

（1）線性表采用順序存儲(chǔ)通常被稱為順序表。順序表指的是集合中數(shù)據(jù)元素之間的邏

輯結(jié)構(gòu)為線性結(jié)構(gòu)，并且數(shù)據(jù)元素按照邏輯順序依次存放在地址連續(xù)的存儲(chǔ)單元中。一般

情況下，線性表中的所有數(shù)據(jù)結(jié)點(diǎn)的類型是相同的。在C語(yǔ)言中，通常使用一維數(shù)組和結(jié)

構(gòu)體來表示順序表。

（2）線性表采用鏈?zhǔn)酱鎯?chǔ)通常被稱為單鏈表。單鏈表指的是集合中數(shù)據(jù)元素之間的邏

輯結(jié)構(gòu)為線性結(jié)構(gòu)，但是數(shù)據(jù)元素所在的存儲(chǔ)單元在內(nèi)存地址上是不連續(xù)的。單鏈表中的

結(jié)點(diǎn)都是由兩部分組成，一部分為數(shù)據(jù)域（data）；另一部分為指針域（next）。簡(jiǎn)單地說,

data域用來存放結(jié)點(diǎn)的數(shù)據(jù)，而next域存放的是一個(gè)指針，該指針保存的是下一個(gè)結(jié)點(diǎn)所

在的內(nèi)存地址，或者說該指針指向下一個(gè)結(jié)點(diǎn)。

（3）在單鏈表中，如果需要查找某一個(gè)結(jié)點(diǎn)的后繼時(shí)，直接通過指針移動(dòng)到下一個(gè)結(jié)

點(diǎn)即可。但是要查找某一結(jié)點(diǎn)的前驅(qū)時(shí)，則需要從結(jié)點(diǎn)頭開始。為了提高數(shù)據(jù)操作的效率,

引入雙向循環(huán)鏈表。

雙向循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表不同，每一個(gè)結(jié)點(diǎn)都有一個(gè)指向前一個(gè)結(jié)點(diǎn)的指

針和一個(gè)指向后一個(gè)結(jié)點(diǎn)的指針。

4.編程題

（1）

intseqlist_insert（seqlist_t*1,intvalue）{

if（seqlist_full（1））{//判斷是否為滿

printf（Hseqlistfull\nn）;

return-1;

}

l->last++;//數(shù)組下標(biāo)加1,表示要插入數(shù)據(jù)

l->data[l->last]=value;//將需要插入的數(shù)據(jù)賦值到數(shù)組中，表示插入數(shù)據(jù)

return0;

)

(2)

intlinklist_head_insert(linklistt*hzdatatype/value){

linklist_t*temp;

//為新插入的數(shù)據(jù)結(jié)點(diǎn)申請(qǐng)空間

temp=(linklist_t*)malloc(sizeof(linklist_t));

temp->data=value;〃為新插入結(jié)點(diǎn)的數(shù)據(jù)域賦值數(shù)據(jù)

temp->next=h->next;//將頭結(jié)點(diǎn)指針指向的下一個(gè)結(jié)點(diǎn)的地址賦值給新結(jié)點(diǎn)的指針

h->next=temp;//將頭結(jié)點(diǎn)指針指向新的結(jié)點(diǎn)

return0;

)

(3)

voiddlinklist_insert(dlinklist_t*dl,datatype_tvalue){

//使用mallee函數(shù)為新插入的結(jié)點(diǎn)■申請(qǐng)空間

dlinklist_t*temp=(dlinklist_t*)malloc(sizeof(dlinklist_t));

//為新插入防結(jié)點(diǎn)賦值

temp->data=value;

//獲取第一個(gè)有數(shù)據(jù)的結(jié)點(diǎn)的地址，地址為dl->next

//如果此時(shí)只有?個(gè)頭結(jié)點(diǎn)，則假設(shè)存在有數(shù)據(jù)的結(jié)點(diǎn)

dlinklist_t*pnext=dl->next;

//將頭結(jié)點(diǎn)與新插入的結(jié)點(diǎn)建立關(guān)系

dl->next=temp;

temp->prior=dl;

//將頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)與新插入的結(jié)點(diǎn)建立關(guān)系

temp->next=pnext;

pnext->prior=temp;

return;

}

(4)

使用遞歸的方法，函數(shù)調(diào)用自己本身，形成一個(gè)函數(shù)的復(fù)用

//參數(shù)為指向頭結(jié)點(diǎn)的指針

intshow_reverse_linklist(linklist_t*h){

if(h->next==NULL){

printf(''%d〃，h->data);

return0;

)

show_reverse_linklist(h->next);

printf(''%dh->data);

return0;

)

習(xí)題答案

1.填空題

(1)棧(2)隊(duì)列(3)后進(jìn)先出(4)先進(jìn)先出

2.選擇題

(1)A(2)C(3)D⑷D、A(5)C(6)B

3.思考題

(1)

棧是一種運(yùn)算受限制的線性表，其只允許在表的一端進(jìn)行插入和刪除操作，俗稱堆棧。

允許進(jìn)行操作的一端稱為“棧頂”，而另一個(gè)固定端稱為“棧底”，棧中的數(shù)據(jù)在進(jìn)行入

棧和出棧時(shí)，遵循后進(jìn)先出的原則。

隊(duì)列同樣是一種運(yùn)算受限制的線性表，是限制在兩端進(jìn)行插入和刪除操作的線性表。

允許進(jìn)行插入操作的一端稱為“隊(duì)尾”，而允許進(jìn)行刪除操作的一端稱為“隊(duì)頭”，隊(duì)列

中的數(shù)據(jù)在進(jìn)行入隊(duì)和出隊(duì)時(shí)，遵循先進(jìn)先出的原則。

4.編程題

(1)

//入棧

//參數(shù)1為棧頂指針(頭結(jié)點(diǎn)指針)，參數(shù)2為插入的數(shù)據(jù)

intlinkstack_push(linkstack_t*s,datatype_tvalue){

linkstack_t*temp;

//使用malloc函數(shù)為新插入的結(jié)點(diǎn)申請(qǐng)內(nèi)存空間

temp=(linkstack_t*)malloc(sizeof(linkstack_t));

//為新插入的結(jié)點(diǎn)賦值一

temp->data=value;

//用頭插法實(shí)現(xiàn)入棧

temp->next=s->next;

s->next=temp;

return0;

)

//判斷棧是否為空

intlinkstack_empty(linkstack_t*s){

returns->next==NULL?1:0;〃判斷下一個(gè)結(jié)點(diǎn)是否為空

}

//出棧

datatype/linkstack_pop(linkstack_t*s){

linkstack_t*temp;

datatype_tvalue;

if(linkstack_empty(s)){

printf("linkstackempty\nH);

return-1;

}

//頭刪法表示出棧，后入先出

temp=s->next;

s->next=temp->next;

〃保存出棧的數(shù)據(jù)

value=temp->data;

//釋放出棧的結(jié)點(diǎn)的內(nèi)存空間

free(temp);

temp=NULL;

//返回出棧的數(shù)據(jù)

returnvalue;

(2)

//入隊(duì)

//參數(shù)1為存放隊(duì)列頭尾結(jié)點(diǎn)指針的結(jié)構(gòu)體地址，參數(shù)2為新入隊(duì)的數(shù)據(jù)

intlinkqueue_enter(linkqueue_t*lq,datatype_tvalue){

linknode_t*temp;

//使用malloc函數(shù)為頭結(jié)點(diǎn)申請(qǐng)內(nèi)存空間

temp=(linknode_t*)malloc(sizeof(linknode_t));

//采用尾插法的設(shè)計(jì)思想

temp->data=value;//為新結(jié)點(diǎn)賦值

temp->next=NULL;//將新結(jié)點(diǎn)的指針指向NULL

lq->rear->next=temp;〃入隊(duì)，將新結(jié)點(diǎn)加入隊(duì)列尾部

lq->rear=temp;//移動(dòng)rear指針，指向新加入的結(jié)點(diǎn)

return0;

}

//判斷隊(duì)列是否為空

intlinkqueue_empty(linkqueue_t*lq){

//當(dāng)front與rear指向同一個(gè)結(jié)點(diǎn)時(shí)，判斷隊(duì)列為空

returnlq->front==lq->rear?1:0;

)

//出隊(duì)

//從頭結(jié)點(diǎn)開始刪除，包括頭結(jié)點(diǎn)

datatype]linkqueue_out(linkqueue_t*lq){

linknode_t*temp;

datatype_tvalue;

if(linkqueue_empty(Iq)){

printf("linkqueueempty\n");

return-1;

)

temp=lq->front;//獲取刪除結(jié)點(diǎn)

//移動(dòng)front指針到下一個(gè)結(jié)點(diǎn)

lq->front=lq->front->next;

//獲取下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)

value=lq->front->data;

free(temp);//釋放需要?jiǎng)h除結(jié)點(diǎn)的內(nèi)存空間

temp=NULL;//避免出現(xiàn)野指針

//返回結(jié)點(diǎn)數(shù)據(jù)

returnvalue;

)

習(xí)題答案

1.填空題

(1)非線性、一對(duì)多(2)前驅(qū)(3)葉結(jié)點(diǎn)(葉子結(jié)點(diǎn))

(4)度數(shù)(5)兩(6)滿二叉(7)從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的

權(quán)值的乘積(8)樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和(9)遞增

(10)平衡因子(11)B樹的階

2.選擇題

(1)B(2)D(3)A(4)C(5)B(6)A(7)D(8)D

3.思考題

(1)

如果i=l,則結(jié)點(diǎn)i無雙親，為根結(jié)點(diǎn)。

如果i>l,則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)是結(jié)點(diǎn)i/2。

如果2區(qū)n,則結(jié)點(diǎn)i的左孩子是結(jié)點(diǎn)2i,否則結(jié)點(diǎn)i為葉結(jié)點(diǎn)。

如果2i+lWn,則結(jié)點(diǎn)i的右孩子是結(jié)點(diǎn)2i+l,否則結(jié)點(diǎn)i無右孩子。

(2)

非葉結(jié)點(diǎn)最多只有M個(gè)孩子，且M>2。

除根結(jié)點(diǎn)以外的非葉結(jié)點(diǎn)都有k個(gè)孩子和k-1個(gè)數(shù)據(jù)元素，k值滿足［M/2區(qū)k<Mo

每一個(gè)葉結(jié)點(diǎn)都有k-1個(gè)數(shù)據(jù)元素，k值滿足［M⑵Wk<M?

所有葉結(jié)點(diǎn)都在同一層次。

所有分支結(jié)點(diǎn)的信息數(shù)據(jù)一致(n,A(),Ki，Ai，K2,A2……Kn,An),其中：.(i=l,2……n)

為關(guān)鍵字，且Ki<K+1(i=l,2……n-1)；均為指向孩子結(jié)點(diǎn)的指針，且指針Ai1指向子樹

中的所有結(jié)點(diǎn)均小于Ki，An所指子樹中的所有結(jié)點(diǎn)的關(guān)鍵字均大于Kn；n為關(guān)鍵字的個(gè)數(shù)

（［M⑵-IWnWM-l）。

（3）B+樹是B樹的升級(jí)版，區(qū)別在于葉結(jié)點(diǎn)在B+樹的最底層（所有葉結(jié)點(diǎn)都在同一

層），葉結(jié)點(diǎn)中存放索引值、指向記錄的指針、指向下一個(gè)葉結(jié)點(diǎn)的指針。葉結(jié)點(diǎn)按照關(guān)

鍵字的大小，從小到大順序鏈接。分支結(jié)點(diǎn)不保存數(shù)據(jù)，只用來作索引，所有數(shù)據(jù)都保存

在葉結(jié)點(diǎn)。

B*樹是B+樹的變體，B*樹不同于B+樹的是：其非根和非葉子結(jié)點(diǎn)上增加了指向兄弟

結(jié)點(diǎn)的指針。

4.編程題

（1）

1//參數(shù)1為樹的結(jié)點(diǎn)個(gè)數(shù)，參數(shù)2起始結(jié)點(diǎn)編號(hào)

2btree_t*btree_create(intn,inti){

3btree_t*t;

4//使用"malloc函數(shù)為結(jié)點(diǎn)申請(qǐng)內(nèi)存空間

5t=(btree_t*)malloc(sizeof(btree_t));

6//將結(jié)點(diǎn)編說乍為數(shù)據(jù)，保存至data中

7t->data=i;

8

9if(2*i<=n){//滿足條件，說明結(jié)點(diǎn)有左孩子，編號(hào)為2i

10//遞歸調(diào)用，為左孩子的創(chuàng)建申請(qǐng)空間

11t->lchild=btreecreate(nf2*i);

12)-

13else{//不滿足條件，則沒有左孩子

14t->lchild=NULL;

15)

16

17if(2*i+1<=n){//滿足條件,說明結(jié)點(diǎn)有右孩子，編號(hào)為2i+l

18//遞歸調(diào)用，為右孩子的創(chuàng)建申請(qǐng)空間

19t->rchild=btree_create(n,2*i+1);

20)

21else{//不滿足條件，則沒有右孩子

22t->rchild=NULL;

23}

24

25returnt;

26)

習(xí)題答案

1.填空題

nx(n-l)

（1）無向圖（2）無向完全圖（3）

2

(4)有向圖(5)有向完全圖(6)nx(n-l)(7)與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)量

(8)入度、出度

2.選擇題

(1)D(2)C(3)A(4)B(5)C(6)A(7)D(8)A(9)D

3.思考題

(1)

鄰接矩陣存儲(chǔ)指的是使用兩個(gè)數(shù)組(一個(gè)一維數(shù)組與一個(gè)二維數(shù)組)來表示圖形結(jié)構(gòu),

一維數(shù)組用來存儲(chǔ)圖中頂點(diǎn)的信息，二維數(shù)組用來存儲(chǔ)圖中弧的信息。

假設(shè)圖G有n個(gè)頂點(diǎn)，則需要?jiǎng)?chuàng)建一個(gè)可以存儲(chǔ)n個(gè)數(shù)據(jù)元素的一維數(shù)組V[n],并且

創(chuàng)建一個(gè)可以存儲(chǔ)nxn個(gè)數(shù)據(jù)元素的二維數(shù)組arc[n][n],也可以將二維數(shù)組理解為一個(gè)

nxn的矩陣

(2)

鄰接表指的是使用數(shù)組與鏈表結(jié)合的方式表示圖形結(jié)構(gòu)。使用一維數(shù)組存儲(chǔ)頂點(diǎn)的數(shù)

據(jù)，使用鏈表存儲(chǔ)頂點(diǎn)之間的關(guān)系信息。在一維數(shù)組中，每個(gè)數(shù)據(jù)元素分為兩部分，一部

分為頂點(diǎn)數(shù)據(jù)，另一部分為指針。指針用來指向一個(gè)鏈表，該鏈表用來記錄當(dāng)前頂點(diǎn)的鄰

接點(diǎn)在一維數(shù)組中的下標(biāo)。

4.編程題

(1)

intvisited[N]={0};//存放頂點(diǎn)是否被訪問的標(biāo)志

//查找頂點(diǎn)的鄰接點(diǎn)

intgraph_adj(graph_t*g,intx){

inti=0;

for(i=0;i<N;i++){

//必須滿足鄰接點(diǎn)的條件，且沒有被訪問過

if(g->matrix[x][i]==1&&visited[i]==0){

returni;

)

)

//沒有鄰接點(diǎn)或者已經(jīng)被訪問完畢

return-1;

}

//深度優(yōu)先搜索

//參數(shù)v表示初始訪問的頂點(diǎn)的下標(biāo)

voidgraph_DFS(graph_t*g,intx){

intu;

printf(n%d"，g->v[x]);//輸出頂點(diǎn)數(shù)據(jù)

visited[x]=1;//重新定義新的數(shù)組，記錄頂點(diǎn)是否被訪問過

//調(diào)用子函數(shù)，尋找當(dāng)前頂點(diǎn)的鄰接點(diǎn)

u=graph_adj(g,x);

//如果存在鄰接點(diǎn)且沒有被訪問過，則遞歸調(diào)用函數(shù)本身

//繼續(xù)尋找該鄰接點(diǎn)的鄰接點(diǎn)

while(u>=0){

graph_DFS(gzu);//遞歸調(diào)用

//如感B接點(diǎn)已經(jīng)被訪問完，則尋找上一個(gè)頂點(diǎn)的其他鄰接點(diǎn)

u=graph_adj(g,x);

習(xí)題答案

L填空題

(1)序列有序(2)塊內(nèi)無序、塊間有序(3)存儲(chǔ)地址

(4)內(nèi)部排序、外部排序

2.選擇題

(1)D(2)C(3)A(4)C(5)C(6)C(7)B(8)A

3.思考題

(1)

重復(fù)遍歷整個(gè)序列，從第一個(gè)元素開始，兩兩比較相鄰元素的大小，如果反序則交換,

直到整個(gè)序列變?yōu)橛行驗(yàn)橹埂?/p>

(2)無序序列：29-18-25-47-58-12-51-10

歸并排序：

第一次歸并后的順序?yàn)椋?8-29-25-47-12-58-10-51

第二次歸并后的順序?yàn)椋?8-25-29-47-10-12-51-58

第三次歸并后的順序?yàn)椋?072-18-25-29-47-51-58

快速排序：

第一次劃分后的順序?yàn)椋?0-18-25-12-29-58-51-47

第二次劃分后的順序?yàn)?10-12-18-25-29-58-51-47

第三次劃分后的順序?yàn)椋?0-12-18-25-29-47-51-58

堆排序：

第一次構(gòu)造大頂堆：58-47-51-29-18-12-25-10

4.編程題

(1)

1voidBubble_Sort(inta[],intn){

2inti,j,temp;//定義三個(gè)整型變量

3for(j=0;j<n-1;j++){//按輪次進(jìn)行判斷

4〃每?輪判斷完成后，最后?個(gè)元素都是當(dāng)前未排序序列的最大值

5//每一輪排序，未排序的元素都會(huì)減1

6for(i=0;i<n-l-j;i++){//從第?個(gè)元素開始依次向后判斷

7if(a[i]>a[i+l]){//判斷元素余后一個(gè)元素

8temp=a[i];//數(shù)據(jù)交換

9a[i]=a[i+l];

10a[i+1]=temp;

11)

12)

13

14

習(xí)題答案

1.思考題

(1)

首先采用循環(huán)的方式對(duì)單向循環(huán)鏈表進(jìn)行遍歷，然后尋找需要?jiǎng)h除元素的上一個(gè)元素

與下一個(gè)元素，最后將這兩個(gè)元素進(jìn)行連接，即可實(shí)現(xiàn)指定元素的刪除。每一次刪除元素,

單向循環(huán)鏈表都會(huì)重新連接為一個(gè)新的環(huán)。然后繼續(xù)指定元素進(jìn)行刪除，重復(fù)步驟，直到

環(huán)中的元素全部刪除完為止。

(2)

回溯法，即確定了解空間的組織結(jié)構(gòu)后，就可以從開始結(jié)點(diǎn)開始，以深度優(yōu)先的方式

對(duì)整個(gè)解空間進(jìn)行搜索。這個(gè)開始的結(jié)點(diǎn)就成為活結(jié)點(diǎn)，同時(shí)也是當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在此

結(jié)點(diǎn)向下進(jìn)行縱深搜索移動(dòng)的一個(gè)新的結(jié)點(diǎn)，那么這個(gè)新借貸就會(huì)成為新的活結(jié)點(diǎn)和拓展

結(jié)點(diǎn)，但是如果當(dāng)前的擴(kuò)展結(jié)點(diǎn)不能再向縱深移動(dòng)，那么此活結(jié)點(diǎn)就會(huì)變?yōu)樗澜Y(jié)點(diǎn)，此時(shí)

就要進(jìn)行回溯移動(dòng)，移動(dòng)到最近的活結(jié)點(diǎn)，并將此活結(jié)點(diǎn)變?yōu)楫?dāng)前的擴(kuò)展結(jié)點(diǎn)。這就是回

溯的工作方式，也是其工作的基本思想。

(3)

動(dòng)態(tài)規(guī)劃法與分治法類似，其基本的思想是將規(guī)模較大的問題分解為較小的子問題，

先求解子問題，然后通過這些子問題的解得到原問題的解，但是與分治法不同的是，經(jīng)過

分解后得到的子問題之間并不是相互獨(dú)立的。為了達(dá)到這一目的，可以用一個(gè)表來記錄所

有已經(jīng)解決的子問題，這樣不管計(jì)算過的子問題的答案在后面的求解過程中是否被用到都

會(huì)被記錄，這就是動(dòng)態(tài)規(guī)劃法的思想。

4.編程題

(1)

15intg[N][N]〃表示無向圖對(duì)應(yīng)的矩陣

16#defineM(1?(N-1))

17

18intdp[N][M];

19

20voidTSP(){

21//初始化dp[i][0]

22inti=0,j,k;

23for(i=0;i<N;i++){

24dp[i][0]=g[i][0];

25)

26//求解dp[i][j],先更新列再更新行

27for(j=1;j<M;j++){

28for(i=0;i<N;i++){

29dp[i][j]=INF;

30//如果集合j(或狀態(tài)j)中包含頂點(diǎn)i,則不符合條件退出

31//判斷方法為：判斷j對(duì)應(yīng)的二進(jìn)制數(shù)的第i位是否為1

32if(((j?(i-D)&1)==1){

33continue;

34)

35for(k=1;k<N;k++){

36//跳過不合理的路徑選擇

37if(((j?(k-D)&1)==0){

38continue;

39)

40//更新dp[i][j]的值

41//計(jì)算從i開始經(jīng)過狀態(tài)j回到起始點(diǎn)的最短距離

42if(dp[i][j]>g[i][k]+dp[k][j人(1?(k-1))]){

43dp[i][j]=g[i][k]+dp[k][j人(1?(k-1))];

44)

45)

46

47

48

49

習(xí)題答案

1.編程題

(1)

50intprime(intv){

51inti;

52for(i=2;i<=v-1;i++){

53if(v%i!=0){

54continue;

55)

56else(

57return0;〃如果不是質(zhì)數(shù)，返回0

58)

59)

60return1;//如果為質(zhì)數(shù)，返回1

61)

(2)

計(jì)算最大公約數(shù)

1intgys(intx,inty){

2returny?gys(yzx%y):x;

3)

計(jì)算最小公倍數(shù)

4intgbs(intxzinty){

5returnx/gys(x,y)*y;//gys()函數(shù)見(1)小題

6)

(3)

1//計(jì)算一個(gè)數(shù)的某次方

2staticintpower(intv,intn){

3inti=0zcount=1;

4for(i=0;i<n;i++){//計(jì)算V的n次方的值

5count=v*count;

6}

7returncount;

8)

9//二進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)

10voidTwoToEight(){

11longlongn,a;

12intsum=0,i=0,m;

13intc,j=0;

14

15inta[N];

16

17printf("輸入一個(gè)二進(jìn)制數(shù)：”)；

n

18scanf(%lld"t&n);

19a=n;

20while(n!=0){

21m=n%10;//獲得二進(jìn)制數(shù)的最低位的數(shù)字0或1

22n/=10;//去除二進(jìn)制數(shù)的最低位

23sum+=m*power(2Zi);//計(jì)算得出十進(jìn)制數(shù)

24