數(shù)據(jù)結(jié)構(gòu)(第3版)習(xí)題答案

1、十二五普通高等教育國家級(jí)本科規(guī)劃教材第 1 章緒論高等學(xué)校精品資源共享課程1.1 什么是數(shù)據(jù)結(jié)構(gòu)？【答】：數(shù)據(jù)結(jié)構(gòu)是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù)，使用某種存儲(chǔ)結(jié)構(gòu)將這批數(shù)據(jù)存儲(chǔ)于計(jì)算機(jī)中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算集合。1.2 數(shù)據(jù)結(jié)構(gòu)涉及哪幾個(gè)方面？【答】：數(shù)據(jù)結(jié)構(gòu)涉及三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算集合。1.3 兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)都相同，但是它們的運(yùn)算集合中有一個(gè)運(yùn)算的定義不一樣，它們是否可以認(rèn)作是同一個(gè)數(shù)據(jù)結(jié)構(gòu)？為什么？【答】：不能，運(yùn)算集合是數(shù)據(jù)結(jié)構(gòu)的重要組成部分，不同的運(yùn)算集合所確定的數(shù)據(jù)結(jié)構(gòu)是不一樣的，例如，棧與隊(duì)列它們的邏輯結(jié)構(gòu)與存

2、儲(chǔ)結(jié)構(gòu)可以相同，但由于它們的運(yùn)算集合不一樣，所以它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。1.4 線性結(jié)構(gòu)的特點(diǎn)是什么？非線性結(jié)構(gòu)的特點(diǎn)是什么？【答】：線性結(jié)構(gòu)元素之間的關(guān)系是一對(duì)一的，在線性結(jié)構(gòu)中只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，其他的每一個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)和一個(gè)后繼結(jié)點(diǎn)。而非線性結(jié)構(gòu)則沒有這個(gè)特點(diǎn)，元素之間的關(guān)系可以是一對(duì)多的或多對(duì)多的。1.5 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有哪幾種？【答】：數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、散列存儲(chǔ)和索引存儲(chǔ)等四種方式。1.6 算法有哪些特點(diǎn)？它和程序的主要區(qū)別是什么？【答】：算法具有（1）有窮性（2）確定性（3）0 個(gè)或多個(gè)輸入（4）1 個(gè)或多個(gè)輸出（5）可行性等特征。程

3、序是算法的一種描述方式，通過程序可以在計(jì)算機(jī)上實(shí)現(xiàn)算法。1.7 抽象數(shù)據(jù)類型的是什么？它有什么特點(diǎn)？【答】：抽象數(shù)據(jù)類型是數(shù)據(jù)類型的進(jìn)一步抽象，是大家熟知的基本數(shù)據(jù)類型的延伸和發(fā)展。抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型，是一個(gè)數(shù)據(jù)模型及定義在該模型上的一組運(yùn)算。對(duì)一個(gè)抽象數(shù)據(jù)類型進(jìn)行定義時(shí)，必須給出它的名字及各運(yùn)算的運(yùn)算符名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定義了一個(gè)抽象數(shù)據(jù)類型及具體實(shí)現(xiàn)，程序設(shè)計(jì)中就可以像使用基本數(shù)據(jù)類型那樣，十分方便地使用抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型的設(shè)計(jì)者根據(jù)這些描述給出操作的具體實(shí)現(xiàn)，抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類型。1.8 算法的時(shí)間復(fù)雜度指的

4、是什么？如何表示？【答】：算法執(zhí)行時(shí)間的度量不是采用算法執(zhí)行的絕對(duì)時(shí)間來計(jì)算的，因?yàn)橐粋€(gè)算法在不同的機(jī)器上執(zhí)行所花的時(shí)間不一樣，在不同時(shí)刻也會(huì)由于計(jì)算機(jī)資源占用情況的不同，使得算法在同一臺(tái)計(jì)算機(jī)上執(zhí)行的時(shí)間也不一樣，另外，算法執(zhí)行的時(shí)間還與輸入數(shù)據(jù)的狀態(tài)有關(guān)，所以對(duì)于算法的時(shí)間復(fù)雜性，采用算法執(zhí)行過程中其基本操作的執(zhí)行次數(shù)，稱為計(jì)算量來度量。算法中基本操作的執(zhí)行次數(shù)一般是與問題規(guī)模有關(guān)的，對(duì)于結(jié)點(diǎn)個(gè)數(shù)為 n 的數(shù)據(jù)處理問題，用T(n)表示算法基本操作的執(zhí)行次數(shù)。為了評(píng)價(jià)算法的執(zhí)行效率，通常采用大寫 O 符號(hào)表示算法的時(shí)間復(fù)雜度，大寫 O 符號(hào)給出了函數(shù) f 的一個(gè)上限。其它義如下：3十二五普通

5、高等教育國家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程定義：f (n)=O (g (n) 當(dāng)且僅當(dāng)存在正的常數(shù) c 和 n0，使得對(duì)于所有的 nn0，有 f (n) c g(n)。上述定義表明，函數(shù) f 頂多是函數(shù) g 的 c 倍，除非 n 小于 n0。因此對(duì)于足夠大的 n (如 nn0)，g 是 f 的一個(gè)上限（不考慮常數(shù)因子 c）。在為函數(shù) f 提供一個(gè)上限函數(shù) g 時(shí)，通常使用比較簡單的函數(shù)形式。比較典型的形式是含有 n 的單個(gè)項(xiàng)（帶一個(gè)常數(shù)系數(shù)）。表 1-1 列出了一些常用的 g 函數(shù)及其名稱。對(duì)于表 1-1 中的對(duì)數(shù)函數(shù) logn，沒有給出對(duì)數(shù)基，原因是對(duì)于任何大于 1 的常數(shù) a 和

6、b 都有 logan =logbn/logba,所以 logan 和 logbn 都有一個(gè)相對(duì)的乘法系數(shù) 1/logba，其中 a 是一個(gè)常量。表 1-1 常用的漸進(jìn)函數(shù)1.9 算法的空間復(fù)雜度指的是什么？如何表示？【答】：算法的空間復(fù)雜度是指算法在執(zhí)行過程中占用的額外的輔助空間的個(gè)數(shù)?？梢詫⑺硎緸閱栴}規(guī)模的函數(shù)，并通過大寫O符號(hào)表示空間復(fù)雜度。1.10 對(duì)于下面的程序段，分析帶下劃線的語句的執(zhí)行次數(shù)，并給出它們的時(shí)間復(fù)雜度 T(n)。（1） i+ ;（2） for(i=0;in;i+)if (aix) x=ai;（3）for(i=0;in;i+)for(j=0;jn;j+)printf(“

7、%d”,i+j) ;（4）for (i=1;i=n-1;i+) k=i;for(j=i+1;jaj+1) k=j;t=ak; ak=ai; ai=t;（5）for(i=0;in;i+)for(j=0;jn;j+)+x;s=s+x;【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n2）；（5）O（n2）4函數(shù)名稱1lognnnlogn2n3nn2n!常數(shù)對(duì)數(shù)線性n 個(gè) logn平方立方指數(shù)階乘十二五普通高等教育國家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程第 2 章線性表及其順序存儲(chǔ)2.1 選擇題（1）表長為 n 的順序存儲(chǔ)的線性表，當(dāng)在任何位置上插入或刪除一個(gè)元素的概率相等時(shí)，

8、插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為（為（ A ）。E），刪除一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)A（n1）/2En/2BnF(n+1)/2Cn+1G(n2)/2Dn1（2）設(shè)棧 S 和隊(duì)列 Q 的初始狀態(tài)為空，元素 e1、e2、e3、e4、e5 和 e6 依次通過棧 S，一個(gè)元素出棧后即進(jìn)入隊(duì)列 Q，若 6 個(gè)元素出隊(duì)的序列為 e2、e4、e3、e6、e5 和 e1，則棧 S的容量至少應(yīng)該為（ C ）。A6B4C3D2（3）設(shè)棧的輸入序列為 1、2、3 n，若輸出序列的第一個(gè)元素為 n，則第 i 個(gè)輸出的元素為（ B ）。A不確定Bni+1CiDni（4）在一個(gè)長度為 n 的順序表中刪除第 i 個(gè)

9、元素（1=i=n）時(shí)，需向前移動(dòng)（ A ）個(gè)元素。AniBni+1Cni1Di（5）若長度為 n 的線性表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，在第 i 個(gè)位置上插入一個(gè)新元素的時(shí)間復(fù)雜度為（ A ）。AO(n)BO(1)CO(n2)DO(n3)（6）表達(dá)式 a*(b+c)d 的后綴表達(dá)式是（ B）。Aabcd*+Babc+*dCabc*+dD+*abcd（7）隊(duì)列是一種特殊的線性表，其特殊性在于（ C ）。A插入和刪除在表的不同位置執(zhí)行 B插入和刪除在表的兩端位置執(zhí)行C插入和刪除分別在表的兩端執(zhí)行 D插入和刪除都在表的某一端執(zhí)行（8）棧是一種特殊的線性表，具有（ B ）性質(zhì)。A先進(jìn)先出B先進(jìn)后出C后進(jìn)后出D

10、順序進(jìn)出（9）順序循環(huán)隊(duì)列中（數(shù)組的大小為 n），隊(duì)頭指示 front 指向隊(duì)列的第 1 個(gè)元素，隊(duì)尾指示 rear 指向隊(duì)列最后元素的后 1 個(gè)位置，則循環(huán)隊(duì)列中存放了 n 1 個(gè)元素，即循環(huán)隊(duì)列滿的條件為（ B）。A(rear+1)%n=front1C(rear)%n=frontB(rear+1)%n=frontDrear+1=front（10）順序循環(huán)隊(duì)列中（數(shù)組的大小為 6），隊(duì)頭指示 front 和隊(duì)尾指示 rear 的值分別為 3和 0，當(dāng)從隊(duì)列中刪除 1 個(gè)元素，再插入 2 個(gè)元素后，front 和 rear 的值分別為（ D ）。A5 和 1B2 和 4C1 和 5D4 和 2

11、2.2 什么是順序表？什么是棧？什么是隊(duì)列？5十二五普通高等教育國家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程【答】：當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，即為順序表。棧是一種特殊的線性表，它的特殊性表現(xiàn)在約定了在這種線性表中數(shù)據(jù)的插入與刪除操作只能在這種線性表的同一端進(jìn)行（即棧頂），因此，棧具有先進(jìn)后出、后進(jìn)先出的特點(diǎn)。隊(duì)列也是一種特殊的線性表，它的特殊性表現(xiàn)在約定了在這種線性表中數(shù)據(jù)的插入在表的一端進(jìn)行，數(shù)據(jù)的刪除在表的另一端進(jìn)行，因此隊(duì)列具有先進(jìn)先出，后進(jìn)后出的特點(diǎn)。2.3 設(shè)計(jì)一個(gè)算法，求順序表中值為 x 的結(jié)點(diǎn)的個(gè)數(shù)。【答】：順序表的存儲(chǔ)結(jié)構(gòu)定義如下（文件名 seqlist.h）：#include

12、 #define N 100typedef int datatype;typedef struct datatype dataN;int length; seqlist;/*預(yù)定義最大的數(shù)據(jù)域空間*/*假設(shè)數(shù)據(jù)類型為整型*/*此處假設(shè)數(shù)據(jù)元素只包含一個(gè)整型的關(guān)鍵字域*/*線性表長度*/*預(yù)定義的順序表類型*/算法 countx（L,x）用于求順序表 L 中值為 x 的結(jié)點(diǎn)的個(gè)數(shù)。int countx(seqlist *L,datatype x)int c=0;int i;for (i=0;ilength;i+)if (L-datai=x) c+;return c;2.4 設(shè)計(jì)一個(gè)算法，將一個(gè)順

13、序表倒置。即，如果順序表各個(gè)結(jié)點(diǎn)值存儲(chǔ)在一維數(shù)組 a 中，倒置的結(jié)果是使得數(shù)組 a 中的 a0等于原來的最后一個(gè)元素，a1 等于原來的倒數(shù)第 2 個(gè)元素，a 的最后一個(gè)元素等于原來的第一個(gè)元素?！敬稹浚喉樞虮淼拇鎯?chǔ)結(jié)構(gòu)定義同題 2.3，實(shí)現(xiàn)順序表倒置的算法程序如下：void verge(seqlist *L)int t,i,j;i=0;j=L-length-1;while (idatai;L-datai+=L-dataj;L-dataj-=t;2.5 已知一個(gè)順序表中的各結(jié)點(diǎn)值是從小到大有序的，設(shè)計(jì)一個(gè)算法，插入一個(gè)值為 x 的結(jié)點(diǎn)，使順序表中的結(jié)點(diǎn)仍然是從小到大有序。【答】：順序表的定義同題

14、 2.3，實(shí)現(xiàn)本題要求的算法程序如下：6十二五普通高等教育國家級(jí)本科規(guī)劃教材void insertx(seqlist *L,datatype x)int j;if (L-lengthlength-1;while (j=0 & L-datajx) L-dataj+1=L-dataj;j-;L-dataj+1=x;L-length+;2.6 將下列中綴表達(dá)式轉(zhuǎn)換為等價(jià)的后綴表達(dá)式。(1) 5+6*7(2) (5-6)/7(3) 5-6*7*8(4) 5*7-8(5) 5*(7-6)+8/9(6) 7*(5-6*8)-9【答】：高等學(xué)校精品資源共享課程(7) 5+6*7(8) (5-6)/7(9)

15、5-6*7*8(10)5*7-8(11)5*(7-6)+8/9(12)7*(5-6*8)-9后綴表達(dá)式：5 6 7*+后綴表達(dá)式：5 6-7/后綴表達(dá)式：5 6 7*8*-后綴表達(dá)式：5 7* 8-后綴表達(dá)式：5 7 6-*8 9/+后綴表達(dá)式：7 5 6 8*-*9-2.7 循環(huán)隊(duì)列存儲(chǔ)在一個(gè)數(shù)組中，數(shù)組大小為 n，隊(duì)首指針和隊(duì)尾指針分別為 front 和 rear，請(qǐng)寫出求循環(huán)隊(duì)列中當(dāng)前結(jié)點(diǎn)個(gè)數(shù)的表達(dá)式?！敬稹浚貉h(huán)隊(duì)列中當(dāng)前結(jié)點(diǎn)個(gè)數(shù)的計(jì)算公式是：(n+rear-front)%n2.8 編號(hào)為 1,2,3,4 的四列火車通過一個(gè)棧式的列車調(diào)度站，可能得到的調(diào)度結(jié)果有哪些？如果有 n 列火車

16、通過調(diào)度站，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，輸出所有可能的調(diào)度結(jié)果。【答】：方法一：算法思想：逐次輸出所有可能，用回溯法。即：總體：對(duì)原始序列中的每一個(gè)元素，總是先入棧，后出棧1入棧后的操作：a.該元素出棧；b.下一個(gè)元素入棧；2出棧后的操作：a.（棧中其他元素）繼續(xù)出棧；b. （原始序列中）下一個(gè)數(shù)入棧；注意：回溯法，關(guān)鍵在于回溯，即在某分支結(jié)點(diǎn) X：處理 X 的一個(gè)子分支，再退回分支 X，接著處理 X 的下一個(gè)子分支,若所有 X 的子分支處理完，再退回上一層分支節(jié)點(diǎn)。所謂“退回”，7十二五普通高等教育國家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程實(shí)際上就是恢復(fù)。程序代碼：(2_8_1.c)#include #

17、define MAX 26typedef struct schar aMAX;int top;Stack;/*定義一些全局變量*/Stack S; /*定義全局性的棧*/char dMAX,seqMAX; /*dMAX用于存儲(chǔ)原始入棧序列，seqMAX用于存儲(chǔ)輸出序列*/int len; /*定義將通過棧的元素個(gè)數(shù)*/int count=0; /* 用于統(tǒng)計(jì)輸出序列的個(gè)數(shù) */void initStack(Stack *S) /*初始化空棧*/ S-top=-1; void push(Stack *S, char x) /*進(jìn)棧*/if (S-top=MAX) return;S-top+;S-

18、aS-top=x;char pop(Stack *S)/*出棧*/if (S-top=-1) printf(ERROR, POP Empty Stack);return -1;S-top-;return S-aS-top+1;int isEmpty(Stack *S)/*判斷棧是否為空*/if (S-top=-1) return 1;return 0;void outSeq(char *seq, int len)/*輸出頂點(diǎn)序列*/int i;for(i=0; ilen; i+)printf(%2c,seqi);printf(n);void scheduler(int pos, int seq

19、_pos)8十二五普通高等教育國家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程/*pos: 處理到原始數(shù)據(jù)中的第 pos 個(gè)元素，seq_pos：若出棧，應(yīng)放在當(dāng)前輸出數(shù)組的第 seq_pos 個(gè)位置*/int i=0;char t;/*對(duì)任何一個(gè)數(shù)，總是先進(jìn)棧，再出棧。另外，這里不需要循環(huán)，類似于“查找數(shù)組中元素”用遞歸*/if(pos=len & isEmpty(&S) outSeq(seq,len); count+; int main()int i;printf(nplease input the num be scheduled: );scanf(%d, &len); /*用 len 存儲(chǔ)待

20、調(diào)度的火車數(shù)量*/for(i=0; i1 時(shí)，perm(R)由(r1)perm(R1),(r2)perm(R2),(rn)perm(Rn)構(gòu)成。依此遞歸定義，可設(shè)計(jì)產(chǎn)生 perm(R)的遞歸算法如下：遞歸解法：(2_8_2.c)#includeint cont=1;/*全局變量，用于記錄所有可能的出棧序列個(gè)數(shù)*/void print(int str,int n);/*求整數(shù)序列 str從 k 到 n 的全排列*/void perm(int str,int k,int n)int i,temp;if (k=n-1) print(str,n);else for (i=k;in;i+)temp=st

21、rk; strk=stri; stri=temp;perm(str,k+1,n); /*遞歸調(diào)用*/temp=stri; stri=strk; strk=temp;/*本函數(shù)判斷整數(shù)序列 str是否滿足進(jìn)出棧規(guī)則,若滿足則輸出*/void print(int str,int n)int i,j,k,l,m,flag=1,b2;for(i=0;in;i+)/*對(duì)每個(gè) stri判斷其后比它小的數(shù)是否為降序序列*/ m=0;for(j=i+1;jstrj) if (m=0) bm+=strj;else if (strjb0) flag=0;else b0=strj;if(flag)/*滿足出棧規(guī)則則

22、輸出 str中的序列*/10十二五普通高等教育國家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程printf( %2d:,cont+);for(i=0;in;i+)printf(%d,stri);printf(n);int main()int str100,n,i;printf(input a int:); /*輸出排列的元素個(gè)數(shù)*/scanf(%d,&n);for(i=0;in;i+) /*初始化排列集合*/stri=i+1;printf(input the result:n);perm(str,0,n);printf(n);return 0;當(dāng)參與進(jìn)出棧的元素個(gè)數(shù)為 4 時(shí)，輸出的結(jié)果如下圖所示。

23、該算法執(zhí)行的時(shí)間復(fù)雜度為 O（n!）。隨著 n 的增大，算法的執(zhí)行效率非常的低。非遞歸解法：（2_8_3.c）對(duì)一組數(shù)窮盡所有排列，還可一種更直接的方法，將一個(gè)排列看作一個(gè)長整數(shù)，則所有排列對(duì)應(yīng)著一組整數(shù)，將這組整數(shù)按從小到大的順序排成一個(gè)數(shù)列，從對(duì)應(yīng)最小的整數(shù)開始，按數(shù)列的遞增順序逐一列舉每個(gè)排列對(duì)應(yīng)的每一個(gè)整數(shù)，這能更有效地完成排列的窮舉。從一個(gè)排列找出對(duì)應(yīng)數(shù)列的下一個(gè)排列可在當(dāng)前排列的基礎(chǔ)上作部分調(diào)整來實(shí)現(xiàn)。倘若當(dāng)前排列為1,2,4,6,5,3，并令其對(duì)應(yīng)的長整數(shù)為 。要尋找比長整數(shù) 更大的排列，可從該排列的最后一個(gè)數(shù)字順序向前逐位考察，當(dāng)發(fā)現(xiàn)排列中的某個(gè)數(shù)字比它前一個(gè)數(shù)字大時(shí)，如本例中

24、的 6 比它的前一位數(shù)字 4 大，則說明還有可能對(duì)應(yīng)更大整數(shù)的排列。但為順序從小到大列舉出所有的排列，不能立即調(diào)整得太大，如本例中將數(shù)字 6 與數(shù)字 4 交換得到的排列為 就不是排列 的下一個(gè)排列。為得到排列 的下一個(gè)排列，應(yīng)從已考察過的那部分?jǐn)?shù)11十二五普通高等教育國家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程字中選出比數(shù)字 4 大，但又是它們中最小的那一個(gè)數(shù)字，比如數(shù)字 5，與數(shù)字 4 交換。該數(shù)字也是從后向前考察過程中第一個(gè)比 4 大的數(shù)字，5 與 4 交換后，得到排列 。在前面數(shù)字1，2，5 固定的情況下，還應(yīng)選擇對(duì)應(yīng)最小整數(shù)的那個(gè)排列，為此還需將后面那部分?jǐn)?shù)字的排列顛倒，如將數(shù)字 6，4

25、，3 的排列順序顛倒，得到排列 1,2,5,3,4,6，這才是排列 1，2，4，6，5，3 的下一個(gè)排列。按照以上想法可以編寫非遞歸程序?qū)崿F(xiàn) n 個(gè)數(shù)的全排列，對(duì)滿足進(jìn)出棧規(guī)則的排列則計(jì)數(shù)并輸出。/*本程序輸出 1 2 . n 個(gè)序列進(jìn)棧出棧的序列*/#include int pl(int n) int a100;int flag=1,flag1=0;FILE *rf ;int i,j,k,x,count=0;rf = fopen(stack.txt, w) ;for (i=1;i=n;i+)ai=i;while (flag) flag1=1;/*最大處理范圍為 99 個(gè)數(shù)*/*pl.txt

26、用于存放進(jìn)出棧序列結(jié)果*/*初始序列*/* 還剩余未輸出的排列*/* 判斷本次排列是否符合進(jìn)棧出棧序列 */for (i=1;i=n;i+) j=i+1;while (jai) j+; /* 找 ai后第一個(gè)比 ai小的元素 aj*/k=j+1;while (k=n)/* 如果 aj后還有比 ai小且比 aj大的元素,則此排列無效*/if ( ak aj) flag1=0;k+;if (flag1) for (i=1;i1 & aij & aiaj) i-;12十二五普通高等教育國家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程k=aj;aj=ai;ai=k;k=j+1;for ( i=k+1;i=k

27、 & xnext=NULL Bp=NULL Cp-next=headDp=head（3）在帶頭結(jié)點(diǎn)的單鏈表中查找 x 應(yīng)選擇的程序體是（ C ）。Anode *p=head-next; while (p & p-info!=x) p=p-next;if (p-info=x)return p else return NULL;Bnode *p=head; while (p& p-info!=x) p=p-next; return p;Cnode *p=head-next;while (p&p-info!=x) p=p-next; return p;Dnode *p=head; while (p-

28、info!=x) p=p-next ; return p;（4）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（ D ）。A必須是連續(xù)的C一定是不連續(xù)的B部分地址必須是連續(xù)的D連續(xù)不連續(xù)都可以（5）在一個(gè)具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持單鏈表仍然有序的時(shí)間復(fù)雜度是（ B）。AO(1)BO(n)CO(n2)DO(nlog2n)（6）用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)（ D ）。A僅修改隊(duì)頭指針C隊(duì)頭、隊(duì)尾指針都要修改B僅修改隊(duì)尾指針D隊(duì)頭,隊(duì)尾指針都可能要修改（7）若從鍵盤輸入 n 個(gè)元素，則建立一個(gè)有序

29、單向鏈表的時(shí)間復(fù)雜度為（ B ）。AO(n)BO(n2)CO(n3)DO(nlog2n)（8）下面哪個(gè)術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)（ D ）。A順序表B鏈表C散列表D隊(duì)列（9）在一個(gè)單鏈表中，若刪除 p 所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（ A ）。Ap-next=p-next-next;Cp-next=p-next;Bp=p-next; p-next=p-next-next;Dp =p-next-next;（10）在一個(gè)單鏈表中，若 p 所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在 p 之后插入 s 所指結(jié)點(diǎn)，則執(zhí)行（ B ）。As-next=p;p-next=s;Cs-next=p-next;p=s;Bs-next=p-

30、next;p-next=s;Dp-next=s;s-next=p;3.2 設(shè)計(jì)一個(gè)算法，求一個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)?！敬稹浚簡捂湵泶鎯?chǔ)結(jié)構(gòu)定義如下（相關(guān)文件：linklist.h）#include 14十二五普通高等教育國家級(jí)本科規(guī)劃教材#include typedef struct node int data;struct node *next;linknode;typedef linknode *linklist;/*尾插法創(chuàng)建帶頭結(jié)點(diǎn)的單鏈表*/linklist creatlinklist() linklist head,r,s;int x;head=r=(linklist)malloc(

31、sizeof(linknode);printf(n 請(qǐng)輸入一組以 0 結(jié)束的整數(shù)序列：n);scanf(%d,&x);while (x) s=(linklist)malloc(sizeof(linknode);s-data=x;r-next=s;r=s;scanf(%d,&x);r-next=NULL;return head;/*輸出帶頭結(jié)點(diǎn)的單鏈表*/void print(linklist head) linklist p;p=head-next;printf(List is:n);while(p) printf(%5d,p-data);p=p-next;printf(n);基于上述結(jié)構(gòu)定義

32、，求單鏈表中的結(jié)點(diǎn)個(gè)數(shù)的算法程序如下：int count(linklist head)高等學(xué)校精品資源共享課程int c=0;linklist p=head;while (p)15十二五普通高等教育國家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程c+;p=p-next;return c;3.3 設(shè)計(jì)一個(gè)算法，求一個(gè)帶頭結(jié)點(diǎn)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)?！敬稹浚簬ь^結(jié)點(diǎn)的單鏈表的存儲(chǔ)結(jié)構(gòu)定義同題 3.2，實(shí)現(xiàn)本題功能的算法程序如下（3_3.c）#include linklist.hint count(linklist head) int c=0;linklist p=head-next;while (p)c+;

33、p=p-next;return c;main()/*測(cè)試函數(shù)*/linklist head;head=creatlinklist();print(head);printf(nLength of head is:%d,count(head);getch();當(dāng)輸入 5 個(gè)數(shù)據(jù)時(shí)，產(chǎn)生的輸出結(jié)果如下圖所示：3.4 設(shè)計(jì)一個(gè)算法，在一個(gè)單鏈表中值為 y 的結(jié)點(diǎn)前面插入一個(gè)值為 x 的結(jié)點(diǎn)。即使值為 x 的新結(jié)點(diǎn)成為值為 y 的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)?！敬稹浚?include linklist.hvoid insert(linklist head,int y,int x)/*在值為 y 的結(jié)點(diǎn)前插入一個(gè)值為

34、x 的結(jié)點(diǎn)*/linklist pre,p,s;pre=head;16十二五普通高等教育國家級(jí)本科規(guī)劃教材p=head-next;while (p & p-data!=y) pre=p;p=p-next;if (p)/*找到了值為 y 的結(jié)點(diǎn)*/ s=(linklist)malloc(sizeof(linknode);s-data=x;s-next=p;pre-next=s;高等學(xué)校精品資源共享課程void main()linklist head;int y,x;head=creatlinklist();print(head);/*測(cè)試程序*/*創(chuàng)建單鏈表*/*輸出單鏈表*/printf(n

35、請(qǐng)輸入 y 與 x 的值:n);scanf(%d %d,&y,&x);insert(head,y,x);print(head);程序的一種運(yùn)行結(jié)果如下圖所示：3.5 設(shè)計(jì)一個(gè)算法，判斷一個(gè)單鏈表中各個(gè)結(jié)點(diǎn)值是否有序?！敬稹浚?include linklist.hint issorted(linklist head,char c)/*當(dāng)參數(shù) c=a時(shí)判斷鏈表是否為升序，當(dāng)參數(shù) c=d是判斷鏈表是否為降序*/ int flag=1;linklist p=head-next;switch (c)17十二五普通高等教育國家級(jí)本科規(guī)劃教材case a:/*判斷帶頭結(jié)點(diǎn)的單鏈表 head 是否為升序*/w

36、hile (p &p-next & flag)if (p-datanext-data) p=p-next;else flag=0;break;case d:/*判斷帶頭結(jié)點(diǎn)的單鏈表 head 是否為降序*/while (p &p-next & flag)if (p-data=p-next-data) p=p-next;else flag=0;break;return flag;高等學(xué)校精品資源共享課程int main()/*測(cè)試程序*/ linklist head;head=creatlinklist();print(head);if (issorted(head,a) printf(單鏈表

37、head 是升序排列的！n);elseif (issorted(head,d) printf(單鏈表 head 是降序排列的！n);else printf(單鏈表 head 是無序的！n);程序運(yùn)行時(shí)的三種輸出結(jié)果如下圖所示：3.6 設(shè)計(jì)一個(gè)算法，利用單鏈表原來的結(jié)點(diǎn)空間將一個(gè)單鏈表就地轉(zhuǎn)置。【答】：#include linklist.hvoid verge(linklist head)18十二五普通高等教育國家級(jí)本科規(guī)劃教材/*本函數(shù)的功能是就地倒置帶頭結(jié)點(diǎn)的單鏈表*/linklist p,q;p=head-next;head-next=NULL;高等學(xué)校精品資源共享課程while (p)/

38、*每次從原表取一個(gè)結(jié)點(diǎn)插入到新表的最前面*/q=p;p=p-next;q-next=head-next;head-next=q;int main()linklist head;head=creatlinklist();print(head);verge(head);print(head);/*測(cè)試函數(shù)*/*創(chuàng)建單鏈表*/*輸出原單鏈表*/*就地倒置單鏈表*/*輸出倒置后的單鏈表*/3.7 設(shè)計(jì)一個(gè)算法，將一個(gè)結(jié)點(diǎn)值自然數(shù)的單鏈表拆分為兩個(gè)單鏈表，原表中保留值為偶數(shù)的結(jié)點(diǎn)，而值為奇數(shù)的結(jié)點(diǎn)按它們?cè)谠碇械南鄬?duì)次序組成一個(gè)新的單鏈表?！敬稹浚?include linklist.hlinklist

39、sprit(linklist head)/*將帶頭結(jié)點(diǎn)的單鏈表 head 中的奇數(shù)值結(jié)點(diǎn)刪除生成新的單鏈表并返回*/linklist L,pre,p,r;L=r=(linklist)malloc(sizeof(linknode);r-next=NULL;pre=head;p=head-next;while (p)if (p-data%2=1)pre-next=p-next;r-next=p;r=p;p=pre-next;/*刪除奇數(shù)值結(jié)點(diǎn)*/elsepre=p;p=p-next;/*保留偶數(shù)值結(jié)點(diǎn)*/19十二五普通高等教育國家級(jí)本科規(guī)劃教材高等學(xué)校精品資源共享課程r-next=NULL;ret

40、urn L;int main()linklist head,L;head=creatlinklist();print(head);L=sprit(head);/*置鏈表結(jié)束標(biāo)記*/*測(cè)試函數(shù)*/*創(chuàng)建單鏈表*/*輸出原單鏈表*/*分裂單鏈表 head*/printf(n 原單鏈表為:n);print(head);/*輸出倒置后的單鏈表*/printf(n 分裂所得奇數(shù)單鏈表為:n);print(L);本程序的一組測(cè)試情況如下圖所示。3.8 設(shè)計(jì)一個(gè)算法，對(duì)一個(gè)有序的單鏈表，刪除所有值大于 x 而不大于 y 的結(jié)點(diǎn)。【答】：#include linklist.hvoid deletedata(l

41、inklist head,datatype x,datatype y)/*刪除帶頭結(jié)點(diǎn)單鏈表中所有結(jié)點(diǎn)值大于 x 而不大于 y 的結(jié)點(diǎn)*/linklist pre=head,p,q;p=head-next;/*初始化*/while (p & p-datanext;while (p & p-datanext;q=pre-next;/*找第 1 處小于 y 的位置*/*刪除大于 x 而小于 y 的結(jié)點(diǎn)*/pre-next=p;20十二五普通高等教育國家級(jí)本科規(guī)劃教材pre=q-next;高等學(xué)校精品資源共享課程while (pre!=p)free(q);q=pre;pre=pre-next;voi

42、d main()/*釋放被刪除結(jié)點(diǎn)所占用的空間*/*測(cè)試函數(shù)*/linklist head,L;datatype x,y;head=creatlinklist();print(head);/*創(chuàng)建單鏈表*/*輸出原單鏈表*/printf(n 請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)區(qū)間:n);scanf(%d%d,&x,&y);deletedata(head,x,y);print(head);/*輸出刪除后的單鏈表*/3.9 設(shè)計(jì)一個(gè)算法，在雙鏈表中值為 y 的結(jié)點(diǎn)前面插入一個(gè)值為 x 的新結(jié)點(diǎn)。即使值為 x 的新結(jié)點(diǎn)成為值為 y 的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)?！敬稹浚菏紫榷x雙鏈表的數(shù)據(jù)結(jié)構(gòu)，相關(guān)文件 dlink.h，內(nèi)容如下：typedef int