【正文】 ength++。amp。}} 已知一個順序表中的各結(jié)點值是從小到大有序的，設(shè)計一個算法，插入一個值為x 的結(jié)點，使順序表中的結(jié)點仍然是從小到大有序。j=Llength1。} 設(shè)計一個算法，將一個順序表倒置。for (i=0。 /*線性表長度*/} seqlist。 設(shè)計一個算法，求順序表中值為x 的結(jié)點的個數(shù)。A．(rear + 1)%n = front ? 1 B．(rear + 1)%n = frontC．(rear)%n = front D．rear + 1 = front（10）順序循環(huán)隊列中（數(shù)組的大小為6），隊頭指示front 和隊尾指示rear 的值分別為3和0，當(dāng)從隊列中刪除1 個元素，再插入2 個元素后，front 和rear 的值分別為（ D ）。A．O(n) B．O(1) C．O(n2) D．O(n3)（6）表達(dá)式a*(b+c)?d 的后綴表達(dá)式是（ B ）。A．（n ? 1）/2 B．n C．n + 1 D．n ? 1E．n/2 F．(n + 1)/2 G．(n ? 2)/2（2）設(shè)棧S 和隊列Q 的初始狀態(tài)為空，元素eeee__________e5 和e6 依次通過棧S，一個元素出棧后即進(jìn)入隊列Q，若6 個元素出隊的序列為eeeee5 和e1，則棧S的容量至少應(yīng)該為（ C ）。jn。 a[i]=t。j=n。（4）for (i=1。in。（2） for(i=0。表11 常用的漸進(jìn)函數(shù) 算法的空間復(fù)雜度指的是什么？如何表示？【答】：算法的空間復(fù)雜度是指算法在執(zhí)行過程中占用的額外的輔助空間的個數(shù)。在為函數(shù)f 提供一個上限函數(shù)g 時，通常使用比較簡單的函數(shù)形式。為了評價算法的執(zhí)行效率，通常采用大寫O 符號表示算法的時間復(fù)雜度，大寫O 符號給出了函數(shù)f 的一個上限。一旦定義了一個抽象數(shù)據(jù)類型及具體實現(xiàn)，程序設(shè)計中就可以像使用基本數(shù)據(jù)類型那樣，十分方便地使用抽象數(shù)據(jù)類型。程序是算法的一種描述方式，通過程序可以在計算機(jī)上實現(xiàn)算法。 線性結(jié)構(gòu)的特點是什么？非線性結(jié)構(gòu)的特點是什么？【答】：線性結(jié)構(gòu)元素之間的關(guān)系是一對一的，在線性結(jié)構(gòu)中只有一個開始結(jié)點和一個終端結(jié)點，其他的每一個結(jié)點有且僅有一個前驅(qū)和一個后繼結(jié)點。1數(shù)據(jù)結(jié)構(gòu)（C 語言版）（第2 版）習(xí)題解析揭安全 李云清 楊慶紅江西師范大學(xué)計算機(jī)信息工程學(xué)院聯(lián)系方式：janquan（習(xí)題答案僅供參考）2第1 章 緒論 什么是數(shù)據(jù)結(jié)構(gòu)？【答】：數(shù)據(jù)結(jié)構(gòu)是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù)，使用某種存儲結(jié)構(gòu)將這批數(shù)據(jù)存儲于計算機(jī)中，并在這些數(shù)據(jù)上定義了一個運算集合。而非線性結(jié)構(gòu)則沒有這個特點，元素之間的關(guān)系可以是一對多的或多對多的。 抽象數(shù)據(jù)類型的是什么？它有什么特點？【答】：抽象數(shù)據(jù)類型是數(shù)據(jù)類型的進(jìn)一步抽象，是大家熟知的基本數(shù)據(jù)類型的延伸和發(fā)展。抽象數(shù)據(jù)類型的設(shè)計者根據(jù)這些描述給出操作的具體實現(xiàn)，抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類型。其它義如下：3定義：f (n)=O (g (n)) 當(dāng)且僅當(dāng)存在正的常數(shù)c 和n0，使得對于所有的n≥n0，有f (n) ≤c g(n)。比較典型的形式是含有n 的單個項（帶一個常數(shù)系數(shù)）?？梢詫⑺硎緸閱栴}規(guī)模的函數(shù)，并通過大寫O符號表示空間復(fù)雜度。in。i++)for(j=0。i=n1。j++)if(a[j]a[j+1]) k=j。}（5）for(i=0。j++){++x。A．6 B．4 C．3 D．2（3）設(shè)棧的輸入序列為3 … n，若輸出序列的第一個元素為n，則第i 個輸出的元素為（ B ）。A．a(chǎn)bcd*+? B．a(chǎn)bc+*d? C．a(chǎn)bc*+d? D．?+*abcd（7）隊列是一種特殊的線性表，其特殊性在于（ C ）。A．5 和1 B．2 和4 C．1 和5 D．4 和2 什么是順序表？什么是棧？什么是隊列？5【答】：當(dāng)線性表采用順序存儲結(jié)構(gòu)時，即為順序表。【答】：順序表的存儲結(jié)構(gòu)定義如下（）：include define N 100 /*預(yù)定義最大的數(shù)據(jù)域空間*/typedef int datatype。 /*預(yù)定義的順序表類型*/算法countx（L,x）用于求順序表L 中值為x 的結(jié)點的個數(shù)。iLlength。即，如果順序表各個結(jié)點值存儲在一維數(shù)組a 中，倒置的結(jié)果是使得數(shù)組a 中的a[0]等于原來的最后一個元素，a[1] 等于原來的倒數(shù)第2 個元素，…，a 的最后一個元素等于原來的第一個元素。while (ij){ t=Ldata[i]?！敬稹浚海瑢崿F(xiàn)本題要求的算法程序如下：6void insertx(seqlist *L,datatype x){int j。 Ldata[j]x){ Ldata[j+1]=Ldata[j]。}} 將下列中綴表達(dá)式轉(zhuǎn)換為等價的后綴表達(dá)式。由于進(jìn)棧的順序是由小到大的，所以出棧序列應(yīng)該滿足以下條件：對于序列中的任何一個數(shù)其后面所有比它小的數(shù)應(yīng)該是倒序的，例如4321 是一個有效的出棧序列，1423 不是一個有效的出棧結(jié)果（4 后面比它小的兩個數(shù)2，3 不是倒序）。集合X 中元素的全排列記為perm(X)。 /*全局變量，用于記錄所有可能的出棧序列個數(shù)*/void print(int str[],int n)。in。perm(str,k+1,n)。}}}/*本函數(shù)判斷整數(shù)序列str[]是否滿足進(jìn)出棧規(guī)則,若滿足則輸出*/void print(int str[],int n){int i,j,k,l,m,flag=1,b[2]。for(j=i+1。j++)if (str[i]str[j]) {if (m==0) b[m++]=str[j]。for(i=0。8}}int main(){int str[100],n,i。for(i=0。perm(str,0,n)。該算法執(zhí)行的時間復(fù)雜度為O（n!）。倘若當(dāng)前排列為1,2,4,6,5,3，并令其對應(yīng)的長整數(shù)為124653。該數(shù)字也是從后向前考察過程中第一個比4 大的數(shù)字，5 與4 交換后，得到排列125643。 /*最大處理范圍為99 個數(shù)*/int flag=1,flag1=0。 /* 用于存放進(jìn)出棧序列結(jié)果*/for (i=1。 /* 判斷本次排列是否符合進(jìn)棧出棧序列 */for (i=1。amp。amp。i=n。 fprintf(rf,\n)。amp。i=n。k=a[j]。 /*對交換后后面的數(shù)據(jù)由小到大排序*/10for ( i=k+1。while (j=k amp。}a[j+1]=x。printf(please input n:)。printf(\nm=%d,m)。A．n B．m C．n ? 1 D．m + n（2）非空的循環(huán)單鏈表head 的尾結(jié)點（由p 所指向）滿足（ C ）。amp。 while (pamp。C．node *p=headnext。 return p。（4）線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（ D ）。A．O(n) B．O(n2) C．O(n3) D．O(n ? log2n)（8）下面哪個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)（ D ）。 pnext=pnextnext。A．snext=p。C．snext=pnext。 設(shè)計一個算法，求一個單鏈表中的結(jié)點個數(shù)。typedef linknode *linklist。scanf(%d,amp。rnext=s。}rnext=NULL。printf(List is:\n)。}基于上述結(jié)構(gòu)定義，求單鏈表中的結(jié)點個數(shù)的算法程序如下：int count(linklist head){ int c=0。}return c。while (p){c++。head=creatlinklist()。}當(dāng)輸入5 個數(shù)據(jù)時，產(chǎn)生的輸出結(jié)果如下圖所示： 設(shè)計一個算法，在一個單鏈表中值為y 的結(jié)點前面插入一個值為x 的結(jié)點。p=headnext。p=pnext。prenext=s。 /*創(chuàng)建單鏈表*/print(head)。x)。【答】：include int issorted(linklist head,char c)/*當(dāng)參數(shù)c=’a’時判斷鏈表是否為升序，當(dāng)參數(shù)c=’d’是判斷鏈表是否為降序*/{ int flag=1。:/*判斷帶頭結(jié)點的單鏈表head 是否為升序*/15while (p amp。 flag){if (pdata=pnextdata) p=pnext。d39。amp。}return flag。if (issorted(head,39。d39?！敬稹浚篿nclude void verge(linklist head){/*本函數(shù)的功能是就地倒置帶頭結(jié)點的單鏈表*/16linklist p,q。p=pnext。head=creatlinklist()。 /*輸出倒置后的單鏈表*/} 設(shè)計一個算法，將一個結(jié)點值自然數(shù)的單鏈表拆分為兩個單鏈表，原表中保留值為偶數(shù)的結(jié)點，而值為奇數(shù)的結(jié)點按它們在原表中的相對次序組成一個新的單鏈表。pre=head。r=p。}17}rnext=NULL。 /*創(chuàng)建單鏈表*/print(head)。 /*輸出倒置后的單鏈表*/printf(\n 分裂所得奇數(shù)單鏈表為:\n)?！敬稹浚篿nclude void deletedata(linklist head,datatype x,datatype y){ /*刪除帶頭結(jié)點單鏈表中所有結(jié)點值大于x 而不大于y 的結(jié)點*/linklist pre=head,p,q。 pdata=x) /*找第1 處大于x 的結(jié)點位置*/{ pre=p。 pdata=y) /*找第1 處小于y 的位置*/p=pnext。18while (pre!=p) /*釋放被刪除結(jié)點所占用的空間*/{free(q)。datatype x,y。scanf(%d%d,amp。print(head)。 /*預(yù)定義的數(shù)據(jù)類型*/typedef struct dlink_node{ /*雙鏈表結(jié)點定義*/datatype data。 /*雙鏈表結(jié)點指針類型定義*//*尾插法創(chuàng)建帶頭結(jié)點的雙鏈表*/dlinklist creatdlinklist(void){ dlinklist head,r,s。printf(\n 請輸入雙鏈表的內(nèi)容：（整數(shù)序列，以0 結(jié)束）\n)。sdata=x。r=s。}/*輸出雙鏈表的內(nèi)容*/void print(dlinklist head){ dlinklist p。p=prlink。amp。sdata=x。pllink=s。print(head)。printf(\n 請輸入要輸入的結(jié)點值x:\n)。/*在值為y 的結(jié)點前插入值為x 的新結(jié)點*/print(head)。【答】：，實現(xiàn)從右向左打印雙鏈表的各個結(jié)點的值可以用遞歸程序?qū)崿F(xiàn)如下：include include void vprint(dlinklist head){ /*遞歸方法從右向左打印雙鏈表的值*/if (headrlink){vprint(headrlink)。print(head)。}本程序的一組測試情況如下圖所示。while (rrlink) /*尋找尾結(jié)點*/r=rrlink。p=headrlink。head=creatdlinklist()。}22第4 章 字符串、數(shù)組和特殊矩陣 稀疏矩陣常用的壓縮存儲方法有（ 三元組順序存儲 ）和（ 十字鏈表 ）兩種。 要計算一個數(shù)組所占空間的大小，必須已知（數(shù)組各維數(shù)）和（每個元素占用的空間）。【答】：include include define MAXSIZE 100typedef struct{char str[MAXSIZE]。len= ?:。break。}int main(){ seqstring s1,s2。=strlen()。m=strpare(s1,s2)。} 試編寫一個函數(shù)，實現(xiàn)在順序存儲方式下字符串的replace（S，T1，T2）運算。//求next[]函數(shù)void getnext(seqstring*p,int next[]){int i,j。while(iplength){if(j==1||pstr[i]==pstr[j]){++i。}}//快速模式匹配算法int kmp(seqstring*t,seqstring*p,int next[],int temppos){int i,j。 jplength){if(j==1||tstr[i]==pstr[j]){i++。else return(1)。 //求T1 串長度lent2=strlen(T2str)。if (pos!=1) //匹配成功{if (lent1lent2) //T1 串長度大于T2 串長度{for (i=temppos。iT2length。i=temppos。i++) //替換25Sstr[pos+i]=T2str[i]。i