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