數(shù)據(jù)結(jié)構(gòu)——c語言描述習(xí)題及答案耿國華(已修改)

　

【正文】 第1章 緒 論習(xí)　題一、問答題1. 什么是數(shù)據(jù)結(jié)構(gòu)？2. 四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。3. 算法的定義與特性。4. 算法的時間復(fù)雜度。5. 數(shù)據(jù)類型的概念。6. 線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。7. 面向?qū)ο蟪绦蛟O(shè)計語言的特點。8. 在面向?qū)ο蟪绦蛟O(shè)計中，類的作用是什么？9. 參數(shù)傳遞的主要方式及特點。10. 抽象數(shù)據(jù)類型的概念。二、判斷題1. 線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。2. 算法就是程序。3. 在高級語言（如C、或 PASCAL）中，指針類型是原子類型。三、計算下列程序段中X=X+1的語句頻度for(i=1。i=n。i++) for(j=1。j=i。j++)for(k=1。k=j。k++) x=x+1。[提示]： 　i=1時： 1 = (1+1)1/2 = (1+12)/2 　 i=2時： 1+2 = (1+2)2/2 = (2+22)/2 　i=3時： 1+2+3 = (1+3)3/2 = (3+32)/2… 　 i=n時： 1+2+3+……+n = (1+n)n/2 = (n+n2)/2f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n3/6+n2/2+n/3區(qū)分語句頻度和算法復(fù)雜度：O(f(n)) = O(n3)四、試編寫算法求一元多項式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并確定算法中的每一語句的執(zhí)行次數(shù)和整個算法的時間復(fù)雜度，要求時間復(fù)雜度盡可能的小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入ai(i=0,1,…,n), x和n，輸出為Pn(x0).通常算法的輸入和輸出可采用下列兩種方式之一：（1） 通過參數(shù)表中的參數(shù)顯式傳遞；（2） 通過全局變量隱式傳遞。試討論這兩種方法的優(yōu)缺點，并在本題算法中以你認(rèn)為較好的一種方式實現(xiàn)輸入和輸出。[提示]：float PolyValue(float a[ ], float x, int n) {……}核心語句：p=1。 (x的零次冪)s=0。i從0到n循環(huán)s=s+a[i]*p。 p=p*x。 或：p=x。 (x的一次冪)s=a[0]。i從1到n循環(huán)s=s+a[i]*p。 p=p*x。 實習(xí)題設(shè)計實現(xiàn)抽象數(shù)據(jù)類型“有理數(shù)”。基本操作包括有理數(shù)的加法、減法、乘法、除法，以及求有理數(shù)的分子、分母。第一章答案=x+1的語句頻度 for(i=1。i=n。i++)for(j=1。j=i。j++) for(k=1。k=j。k++) x=x+1。 【解答】x=x+1的語句頻度為：T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6，求pn(x)=a0+a1x+a2x2+…….+anxn的值pn(x0),并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復(fù)雜度，要求時間復(fù)雜度盡可能小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入為ai(i=0,1,…n)、x和n,輸出為Pn(x0)。 算法的輸入和輸出采用下列方法（1）通過參數(shù)表中的參數(shù)顯式傳遞（2）通過全局變量隱式傳遞。討論兩種方法的優(yōu)缺點，并在算法中以你認(rèn)為較好的一種實現(xiàn)輸入輸出。【解答】（1）通過參數(shù)表中的參數(shù)顯式傳遞 優(yōu)點：當(dāng)沒有調(diào)用函數(shù)時，不占用內(nèi)存，調(diào)用結(jié)束后形參被釋放，實參維持，函數(shù)通用性強，移置性強。 缺點：形參須與實參對應(yīng)，且返回值數(shù)量有限。（2）通過全局變量隱式傳遞 優(yōu)點：減少實參與形參的個數(shù)，從而減少內(nèi)存空間以及傳遞數(shù)據(jù)時的時間消耗 缺點：函數(shù)通用性降低，移植性差算法如下：通過全局變量隱式傳遞參數(shù)PolyValue(){ int i,n。float x,a[],p。 printf(“\nn=”)。 scanf(“%f”,amp。n)。 printf(“\nx=”)。 scanf(“%f”,amp。x)。for(i=0。in。i++) scanf(“%f ”,amp。a[i])。 /*執(zhí)行次數(shù)：n次 */ p=a[0]。 for(i=1。i=n。i++){ p=p+a[i]*x。 /*執(zhí)行次數(shù)：n次*/ x=x*x。}printf(“%f”,p)。 }算法的時間復(fù)雜度：T(n)=O(n)通過參數(shù)表中的參數(shù)顯式傳遞float PolyValue(float a[ ], float x, int n) {float p,s。int i。p=x。 s=a[0]。for(i=1。i=n。i++){s=s+a[i]*p。 /*執(zhí)行次數(shù):n次*/ p=p*x。}return(p)。}算法的時間復(fù)雜度：T(n)=O(n)第2章 線性表習(xí) 題 描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元素結(jié)點。 填空：（1） 在順序表中插入或刪除一個元素，需要平均移動＿＿一半＿＿元素，具體移動的元素個數(shù)與＿＿插入或刪除的位置＿＿有關(guān)。（2） 在順序表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。（3） 在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的存儲位置由＿＿＿＿＿＿指示，首元素結(jié)點的存儲位置由＿＿＿＿＿＿指示，除首元素結(jié)點外，其它任一元素結(jié)點的存儲位置由＿＿其直接前趨的next域＿＿指示。 已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元素結(jié)點，也不是尾元素結(jié)點。按要求從下列語句中選擇合適的語句序列。a. 在P結(jié)點后插入S結(jié)點的語句序列是：＿（4）、（1）＿。b. 在P結(jié)點前插入S結(jié)點的語句序列是：（7）、（11）、（8）、（4）、（1）。c. 在表首插入S結(jié)點的語句序列是：（5）、（12）。d. 在表尾插入S結(jié)點的語句序列是：（11）、（9）、（1）、（6）。供選擇的語句有：（1）Pnext=S。（2）Pnext= Pnextnext。（3）Pnext= Snext。（4）Snext= Pnext。（5）Snext= L。（6）Snext= NULL。（7）Q= P。（8）while(Pnext!=Q) P=Pnext。（9）while(Pnext!=NULL) P=Pnext。（10）P= Q。（11）P= L。（12）L= S。（13）L= P。 已知線性表L遞增有序。試寫一算法，將X插入到L的適當(dāng)位置上，以保持線性表L的有序性。[提示]：void insert(SeqList *L。 ElemType x) 方法1 （1）找出應(yīng)插入位置i，（2）移位，（3）…… 方法2 參P. 229 寫一算法，從順序表中刪除自第i個元素開始的k個元素。[提示]：注意檢查i和k的合法性。 （集體搬遷，“新房”、“舊房”） 方法1 以待移動元素下標(biāo)m（“舊房號”）為中心，計算應(yīng)移入位置（“新房號”）： for ( m= i－1+k。 m= L－last。 m++) L－elem[ m－k ] = L－elem[ m ]。 方法2 同時以待移動元素下標(biāo)m和應(yīng)移入位置j為中心： 方法3 以應(yīng)移入位置j為中心，計算待移動元素下標(biāo)：（整數(shù)）以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時間復(fù)雜度（注意：mink和maxk是給定的兩個參變量，它們的值為任意的整數(shù)）。 [提示]：注意檢查mink和maxk的合法性：mink maxk 不要一個一個的刪除（多次修改next域）。（1）找到第一個應(yīng)刪結(jié)點的前驅(qū)prepre=L。 p=L－next。while (p!=NULL amp。amp。 p－data = mink) { pre=p。 p=p－next。 }（2）找到最后一個應(yīng)刪結(jié)點的后繼s，邊找邊釋放應(yīng)刪結(jié)點s=p。while (s!=NULL amp。amp。 s－data maxk) { t =s。 s=s－next。 free(t)。 }（3）pre－next = s。 試分別以不同的存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法，即在原表的存儲空間將線性表（a1, a2..., an）逆置為（an, an1,..., a1）。（1）以一維數(shù)組作存儲結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)的前elenum個分量中。（2）以單鏈表作存儲結(jié)構(gòu)。[方法1]：在原頭結(jié)點后重新頭插一遍[方法2]：可設(shè)三個同步移動的指針p, q, r，將q的后繼r改為p 假設(shè)兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個按元素值遞減有序的排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點空間存放表C.[提示]： 例21 方法1 void merge(LinkList A。 LinkList B。 LinkList *C){ ……pa=A－next。 pb=B－next。 *C=A。 (*C)－next=NULL。while ( pa!=NULL amp。amp。 pb!=NULL ){ if ( pa－data = pb－data ){ smaller=pa。 pa=pa－next。 　smaller－next = (*C)－next。 /* 頭插法 */ 　(*C)－next = smaller。}else{ smaller=pb。 pb=pb－next。 　smaller－next = (*C)－next。 (*C)－next = smaller。} }while ( pa!=NULL){ smaller=pa。 pa=pa－next。 smaller－next = (*C)－next。 (*C)－next = smaller。}while ( pb!=NULL){ smaller=pb。 pb=pb－next。 smaller－next = (*C)－next。 (*C)－next = smaller。} 方法2 LinkList merge(LinkList A。 LinkList B){ ……LinkList C；pa=A－next。 pb=B－next。 C=A。 C－next=NULL。………… return C。 假設(shè)有一個循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點也無頭指針。已知s為指向鏈表某個結(jié)點的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點的前趨結(jié)點。[提示]：設(shè)指針p指向s結(jié)點的前趨的前趨，則p與s有何關(guān)系？ 已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其它字符），試編寫算法來構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。 設(shè)線性表A=(a1, a2,…,am)，B=(b1, b2,…,bn)，試寫一個按下列規(guī)則合并A、B為線性表C的算法，使得： C= (a1, b1,…,am, bm, bm+1, …,bn) 當(dāng)m≤n時；或者 C= (a1, b1,…,an, bn, an+1, …,am) 當(dāng)mn時。線性表A、B、C均以單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。[提示]：void merge(LinkList A。 LinkList B。 LinkList *C) 或：LinkList merge(LinkList A。 LinkList B) 將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇次項或偶次項，并要求利用原鏈表中的結(jié)點空間來構(gòu)成這兩個鏈表。[提示]：注明用頭指針還是尾指針。 建立一個帶頭結(jié)點的線性鏈表，用以存放輸入的二進(jìn)制數(shù)，鏈表中每個結(jié)點的data域存放一個二進(jìn)制位。并在此鏈表上實現(xiàn)對二進(jìn)制數(shù)加1的運算 。[提示]：可將低位放在前面。 設(shè)多項式P(x)采用課本中所述鏈接方法存儲。寫一算法，對給定的x值，求P(x)的值。[提示]：float PolyValue(Polylist p。 float x) {……} 實習(xí)題1． 將若干城市的信息存入一個帶頭結(jié)點的單鏈表，結(jié)點中的城市信息包括城市名、城市的位置坐標(biāo)。要求：（1） 給定一個城市名，返回其位置坐標(biāo)；（2） 給定一個位置坐標(biāo)P和一個距離D，返回所有與P的距離小于等于D的城市。2． 約瑟夫環(huán)問題。約瑟夫問題的一種描述是：編號為1，2，…，n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個整數(shù)作為報數(shù)上限值m,從第一個人開始順時針自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1報數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計一個程序，求出出列順序。利用單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打印出各人的編號。例如m的初值為20；n=7，7個人的密碼依次是：3，1，7，2，4，8，4，出列的順序為6，1，4，7，2，3，5。第二章 答案實習(xí)題二：約瑟夫環(huán)問題約瑟夫問題的一種描述為：編號1,2,…,n的n個人按順時針方向圍坐一圈，每個人持有一個密碼（正整數(shù)）。一開始任選一個報數(shù)上限值m,從第一個人開始順時針自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人開始重新從1