【正文】 域來作為線索(12)B(13)D(14)D(15)D 因為這些分支結(jié)點共有N1+2*N2+…+m*Nm個指針域，其中有N1+N2+…+Nm 1個指針指向分支結(jié)點，所以余下的指針指向的是葉子結(jié)點。⑶D 葉子結(jié)點沒有左右孩子，所以它的左右孩子域均是線索⑷D 滿二叉樹中沒有度為1的結(jié)點，所以有m個葉子結(jié)點，則根據(jù)性質(zhì)3可知度為2的結(jié)點個數(shù)為m1。⑸21 根據(jù)二叉樹性質(zhì)3的證明過程，有n0=n2+2n3+3n4+1（n0、nnn4分別為葉子結(jié)點、度為度為3和度為4的結(jié)點的個數(shù)）。 } return i。 while(j!=0) {i++。 } return 0。i=1。下面用串的基本操作編寫求解本題的算法。 ｝ else scanf（“%c”，amp。 scanf(“％c”，amp。 ch=’9’) /*是數(shù)字字符*/ ｛num=０。 /*整數(shù)存儲到數(shù)組a，i記整數(shù)個數(shù)*/ scanf(“％c”，amp。從左到右掃描字符串，初次碰到數(shù)字字符時，作為一個整數(shù)的開始。 strend。 while (strbegin strend) { tmp = str[strbegin]。 str = name。算法如下： include iostream include string void main() { int strbegin,strend。 j=s[0]。}⑵從后向前刪除值為ch的所有元素，這樣所有移動的元素中沒有值為ch的元素，能減少移動元素的次數(shù)，提高算法的效率。 ks[0]。子串在主串中第一次出現(xiàn)時的第一個字符的位置稱子串在主串中的位置。 用引號（數(shù)據(jù)結(jié)構(gòu)教學(xué)中通常用單引號，而C語言中用雙引號）括起來的字符序列稱為串常量，其串值是常量。⑶14⑷模式匹配(5)由空格字符（ASCII值32）所組成的字符串，空格個數(shù)(6)該串所包含的的字符的個數(shù)(7) a. 21 b. 1 c. DataBase Structure Coursed. Data Course e. Structure Base Course2. 簡答題（1） 不含任何字符的串稱為空串，其長度為0。 Push(S,a)。 else rearnext=snext。 rear=s。 if( rear=NULL) { rear=s。4. 算法設(shè)計(1)出隊操作是在循環(huán)鏈表的頭部進行，相當(dāng)于刪除開始結(jié)點，而入隊操作是在循環(huán)鏈表的尾部進行，相當(dāng)于在終端結(jié)點之后插入一個結(jié)點。⑷C 棧和隊列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲和鏈接存儲，有可能包含的運算不一樣，但不是主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對具體問題時包含的運算都可能不同。}}}習(xí)題三解答1. 填空 ⑴23，1003H⑵順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top= 1和top=NULL，棧頂指針top等于數(shù)組的長度和內(nèi)存無可用空間⑶后進先出，先進先出，對插入和刪除操作限定的位置不同⑷假溢出⑸Ｏ(1)，Ｏ(n) 在帶頭指針的循環(huán)鏈表中，出隊即是刪除開始結(jié)點，這只需修改相應(yīng)指針；入隊即是在終端結(jié)點的后面插入一個結(jié)點，這需要從頭指針開始查找終端結(jié)點的地址。while(qdatamaxk) { x=qnext。 while (pnext amp。} else p=pnext。具體算法如下： void del(Linklist A){ p=Anext。} else p=q。amp。(qdata=’z’)) { pnext=qnext。while (q){ if ( (qdata=’A’)amp。 //創(chuàng)建空循環(huán)鏈表C存放字符D=(Linklist)malloc(sizeof(Lnode))。 d[ni1]=t。具體算法如下：void reverse(elemtype d[], int n){ for(i=0。 while(A[j]%2=0) j。4．算法設(shè)計⑴從數(shù)組的兩端向中間比較，設(shè)置兩個變量i和j，初始時i=0，j=n1，若A[i]為偶數(shù)并且A[j]為奇數(shù)，則將A[i]與A[j]交換。在操作上，帶頭結(jié)點的單鏈表的初始化為申請一個頭結(jié)點。優(yōu)點：插入和刪除元素時很方便，使用靈活。⑶C 因為有prior指針⑷A 因為單鏈表屬于順序存儲結(jié)構(gòu)⑸B⑹B（7）B（8）B（9）B（10）B Loc(a6)=Loc(a1)+(61)*5=90+10=100(1) 順序結(jié)構(gòu)存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是統(tǒng)一的，要求內(nèi)存中存儲單元的地址必須是連續(xù)的。（3）因為當(dāng)n趨向于無窮大時有l(wèi)im((2n+n3)/ 2n)=1，2n+n3的同階數(shù)量級是O(2n)。算法分析（Algorithm analysis）的主要工作是從“時間”和“空間”兩個方面來分析算法的效率。數(shù)據(jù)元素之間無任何關(guān)系。(3)圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。元素之間存在一個一對一的線線關(guān)系，即除了第一個元素和最后一個元素外，每個元素都有一個直接前驅(qū)和一個直接后繼，第一個元素有一個后繼，最后一個元素有一個直接前驅(qū)。具體來說，數(shù)據(jù)結(jié)構(gòu)包含三個方面的內(nèi)容，既數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)（或稱物理結(jié)構(gòu)）和對數(shù)據(jù)所施加的一組操作。一般情況下，一個數(shù)據(jù)元素由若干個數(shù)據(jù)項構(gòu)成。數(shù)據(jù)結(jié)構(gòu)（C語言版） 附錄2 習(xí)題指導(dǎo)與解答附錄2 習(xí)題指導(dǎo)與解答習(xí)題一解答1． 數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對客觀現(xiàn)實世界的事物及其活動所做的抽象描述。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。3．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)元素之間本身所固有的獨立于計算機的一種結(jié)構(gòu)，這種結(jié)構(gòu)可以用數(shù)據(jù)元素之間固有的關(guān)系的集合來描述。例如學(xué)生檔案管理系統(tǒng)中學(xué)生記錄之間的關(guān)系即為線性關(guān)系；（2）樹形結(jié)構(gòu)。數(shù)據(jù)元素之間存在多個對多個的關(guān)系。5．抽象數(shù)據(jù)類型通常是指由用戶定義，用以表示實際應(yīng)用問題的數(shù)據(jù)模型，一般由基本數(shù)據(jù)類型或其他已定義的抽象數(shù)據(jù)類型以及定義在該模型上的一組操作組成。7．算法應(yīng)具有如下5個重要特性： （1）輸入性；（2）輸出性；（3）有限性；（4）確定性；（5）可行性；算法設(shè)計應(yīng)滿足以下5個基本要求： （1）正確性；（2）可讀性；（3）健壯性；（4）高時間效率；（5）高空間效率。第2大題略習(xí)題二解答1. 填空⑴表長的一半，表長，該元素在表中的位置⑵144 第5個元素的存儲地址=第1個元素的存儲地址＋(7－1)4=144⑶pnext=(pnext)next⑷為了運算方便⑸Ο(1)，Ο(n) 在p所指結(jié)點后插入一個新結(jié)點只需修改指針，所以時間復(fù)雜度為Ο(1)；而在給定值為x的結(jié)點后插入一個新結(jié)點需要先查找值為x的結(jié)點，所以時間復(fù)雜度為Ο(n)。優(yōu)點：一般情況下，存儲密度大，存儲空間利用率高。缺點：存儲密度小，存儲空間利用率低。無論插入或刪除的位置是地第一個結(jié)點還是其他結(jié)點，算法步驟都相同。具體算法如下：void adjust(int A[],n){ i=0。 if(ij) swap(A[i],A[j])。 i=n/2。 }}⑶在單鏈表A中依次取元素，若取出的元素是字母，把它插入到字母鏈表C中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表C，D，A中分別存放字母、數(shù)字和其他字符。 Dnext=D。amp。 qnext=Cnext。(qdata=’9’)) { pnext=qnext。 q=pnext。 while (pnext) if (pdata==pnextdata) { q=pnext。}⑸因為是在有序單鏈表上的操作，所以，要充分利用其有序性。amp。 pnext=qnext。2. 選擇題⑴D 此時，輸出序列一定是輸入序列的逆序。⑸A 兩棧共享空間首先兩個棧是相向增長的，棧底應(yīng)該分別指向兩個棧中的第一個元素的位置，并注意C++中的數(shù)組下標是從0開始的。由于循環(huán)鏈表不帶頭結(jié)點，需要處理空表的特殊情況。 rearnext=s。 }}出隊算法如下：Elemtype Dequeue(*rear){ if( rear==NULL) throw”underflow”。 free(s)。} while (!EmptyStack(S)){ a=Pop(S)。僅含有空格字符的串稱為空格串，其長度為串中空格字符的個數(shù)。串值可以變化的量稱為串變量。串變量與其它變量一樣，要用名字引用其值，串變量的名字也是標識符，串變量的值可以修改。 k++) s[k]=s[k+1]。算法如下：void Dele(char s[],char ch) /*數(shù)組s的0號單元存放串的長度*/{ for (i=s[0]。 j++) s[j1]=s[j]。 string str。 printf(“%s\n”, str)。 str[strbegin] = str[strend]。 } printf(“%s\n”, str)。然后進行拼數(shù)，即將連續(xù)出現(xiàn)的數(shù)字字符拼成一個整數(shù)，直到碰到非數(shù)字字符為止，一個整數(shù)拼完，存入數(shù)組，再準備下一整數(shù)，如此下去，直至整個字符串掃描到結(jié)束。ch）。 /*數(shù)初始化*/ while（ch=’0’amp。ch）。ch）；/*輸入非數(shù)字且非＃時，繼續(xù)輸入字符*/ printf（“共有%d個整數(shù)，它們是：\n”,i）； for（j=０；ji；j++） ｛printf（“%6d”，a[j]）； if（（j+1）％10==0）printf（