數(shù)據(jù)結(jié)構(gòu)耿國華c語言版答案

數(shù)據(jù)結(jié)構(gòu)耿國華 c語言版答案【篇一：《數(shù)據(jù)結(jié)構(gòu) ——c語言描述》習(xí)題及答案 耿國華2】題一、問答題什么是數(shù)據(jù)結(jié)構(gòu)？四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。算法的定義與特性。算法的時間復(fù)雜度。數(shù)據(jù)類型的概念。線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。面向?qū)ο蟪绦蛟O(shè)計語言的特點。在面向?qū)ο蟪绦蛟O(shè)計中，類的作用是什么？參數(shù)傳遞的主要方式及特點。抽象數(shù)據(jù)類型的概念。二、判斷題線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。算法就是程序。在高級語言（如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;[提示]：?f(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)輸入和輸出。[提示]：floatpolyvalue(float{??}核心語句：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;a[],floatx,intn)實習(xí)題設(shè)計實現(xiàn)抽象數(shù)據(jù)類型“有理數(shù)”。基本操作包括有理數(shù)的加法、減法、乘法、除法，以及求有理數(shù)的分子、分母。第一章答案1.3計算下列程序中 x=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)/61.4試編寫算法，求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)輸入輸出?！窘獯稹?）通過參數(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(){inti,n;floatx,a[],p;printf(“nn=”);scanf(“%f”,n);printf(“nx=”);scanf(“%f”,x);for(i=0;in;i++)scanf(“%f”,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ù)顯式傳遞floatpolyvalue(floata[],floatx,intn){floatp,s;inti;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í)題2.1描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元素結(jié)點。2.2填空：1）在順序表中插入或刪除一個元素，需要平均移動＿＿一半＿＿元素，具體移動的元素個數(shù)與＿＿插入或刪除的位置＿＿有關(guān)。2）在順序表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。（3）在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的存儲位置由＿＿＿＿＿＿指示，首元素結(jié)點的存儲位置由＿＿＿＿＿＿指示，除首元素結(jié)點外，其它任一元素結(jié)點的存儲位置由＿＿其直接前趨的域＿＿指示。

next2.3已知l是無表頭結(jié)點的單鏈表，且 p結(jié)點既不是首元素結(jié)點，也不是尾元素結(jié)點。按要求從下列語句中選擇合適的語句序【篇二：《數(shù)據(jù)結(jié)構(gòu)——c語言描述》習(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ù)類型的概念。二、判斷題線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。算法就是程序。在高級語言（如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;[提示]：?f(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)輸入和輸出。[提示]：floatpolyvalue(floata[],floatx,intn){

??}核心語句：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ù)的分子、分母。第一章答案1.3計算下列程序中 x=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)/61.4試編寫算法，求 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)輸入輸出?！窘獯稹?）通過參數(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(){inti,n;floatx,a[],p;printf( “nn=”);scanf(“%f”,n);printf( “nx=”);scanf(“%f”,x);for(i=0;in;i++)scanf(“%f”,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ù)顯式傳遞floatpolyvalue(floata[],floatx,intn){floatp,s;inti;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í)題2.12.2描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元素結(jié)點。填空：1）在順序表中插入或刪除一個元素，需要平均移動＿＿一半＿＿元素，具體移動的元素個數(shù)與＿＿插入或刪除的位置＿＿有關(guān)。2）在順序表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。3）在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的存儲位置由＿＿＿＿＿＿指示，首元素結(jié)點的存儲位置由＿＿＿＿＿＿指示，除首元素結(jié)點外，其它任一元素結(jié)點的存儲位置由＿＿其直接前趨的 next域＿＿指示。2.3已知l是無表頭結(jié)點的單鏈表，且 p結(jié)點既不是首元素結(jié)點，也不是尾元素結(jié)點。按要求從下列語句中選擇合適的語句序列。a.在p結(jié)點后插入 s結(jié)點的語句序列是：。b.在p結(jié)點前插入 s結(jié)點的語句序列是：。c.在表首插入s結(jié)點的語句序列是：。d.在表尾插入 s結(jié)點的語句序列是：。供選擇的語句有：（1）p-next=s;（2）p-next=p-next-next;（3）p-next=s-next;（4）s-next=p-next;（5）s-next=l;（6）s-next=null;（7）q=p;（8）while(p-next!=q)p=p-next;（9）while(p-next!=null)p=p-next;（10）p=q;（11）p=l;（12）l=s;（13）l=p;2.4已知線性表 l遞增有序。試寫一算法，將 x插入到l的適當(dāng)位置上，以保持線性表 l的有序性。[提示]：voidinsert(seqlist*l;elemtypex)方法11）找出應(yīng)插入位置i，（2）移位，（3）??方法2參p.2292.5寫一算法，從順序表中刪除自第 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ù)據(jù)結(jié)構(gòu)——c語言描述》習(xí)題及答案耿國華】四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。3.算法的定義與特性。4.算法的時間復(fù)雜度。5.數(shù)據(jù)類型的概念。6.線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。面向?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、或pnx0，并確定算法中的每一語句的執(zhí)行次數(shù)和整個算法的時間復(fù)雜度，要求時間復(fù)雜度盡可能的小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入aii01?nx和n，輸出為pnx0.通常算法的輸入和輸出可采用下列兩種方式之一：（1）通過參數(shù)表中的參數(shù)顯式傳遞；（2）通過全局變量隱式傳遞。試討論這兩種方法的優(yōu)缺點，并在本題算法中以你認(rèn)為較好的一種方式實現(xiàn)輸入和輸出。提示：floatpolyvaluefloatafloatxintn 核??心語句： p1x的零次冪s0i從0到n循環(huán)ssaipppx或：pxx的一次冪sa0i從1到n循環(huán)ssaipppx實習(xí)題設(shè)計實現(xiàn)抽象數(shù)據(jù)類型“有理數(shù)”?；静僮靼ㄓ欣頂?shù)的加法、減法、乘法、除法，以及求有理數(shù)的分子、分母。第一章答案 1.3計算下列程序中 xx1的語句頻度 fori1iltniforj1jltijfork1kltjkxx1 【解答】xx1的語句頻度為： tn112（123）??12??n）nn1n2/61.4試編寫算法，求pnxa0a1xa2x2??.anxn

的值pnx0并確定算法中每一語句的

執(zhí)行次數(shù)和整個算法的時間復(fù)雜度，要求時間復(fù)雜度盡可能小，規(guī)定算法中不能使用求 冪函數(shù)。注意：本題中的輸入為 aii01?n、x和n輸出為pnx0。算法的輸入和輸 出采用下列方法（ 1）通過參數(shù)表中的參數(shù)顯式傳遞（ 2）通過全局變量隱式傳遞。討論 兩種方法的優(yōu)缺點，并在算法中以你認(rèn)為較好的一種實現(xiàn)輸入輸出?！窘獯稹?執(zhí)行次數(shù)：n次/pa0fori1iltnippaix/ 執(zhí)行次數(shù)：n次/xxxprintf “f”算法p的時間復(fù)雜度： tnon通過參數(shù)表中的參數(shù)顯式傳遞floatpolyvaluefloatafloatxintnfloatpsintipxsa0fori1iltnissaip/執(zhí)行次數(shù):n次/ppxreturnp 算法的時間復(fù)雜度： tnon第2章線性表習(xí)題2.1描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元素結(jié)點。2.2填空：（1）在順序表中插入或刪除一個元素，需要平均移動＿＿一半＿＿元素，具體移動的元素個數(shù)與＿＿插入或刪除的位置＿＿有關(guān)。（2）在順序表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。（3）在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的存儲位置由＿＿＿＿＿＿指示，首元素結(jié)點的存儲位置由＿＿＿＿＿＿指示，除首元素結(jié)點外，其它任一元素結(jié)點的存儲位置由＿＿其直接前趨的next域＿＿指示。2.3已知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）p-gtnexts（2）p-gtnextp-gtnext-gtnext （3）p-gtnexts-gtnext （4）s-gtnextp-gtnext（5）s-gtnextl （6）s-gtnextnull （7）qp（8）whilep-gtnextqpp-gtnext （9）whilep-gtnextnullpp-gtnext （10）pq（11）pl（12）ls（13）lp2.4已知線性表 l遞增有序。試寫一算法，將 x插入到l的適當(dāng)位置上，以保持線性表 l的有序性。提示： voidinsertseqlistlelemtypexlt 方法1gt（1）找出應(yīng)插入位置 i，（2）移位，（3）??lt方法2gt參p.2292.5寫一算法，從順序表中刪除自第i個元素開始的k個元素。提示：注意檢查i和k的合法性。（集體搬遷，、“新房”“舊房”）lt方法1gt以待移動元素下標(biāo)m（“舊房號”）為中心，計算應(yīng)移入位置（）“新房號”：formi－1kmltl－gtlastml－gtelemm－kl－gtelemmlt方法2gt同時以待移動元素下標(biāo)m和應(yīng)移入位置j為中心：lt方法3gt以應(yīng)移入位置j為中心，計算待移動元素下標(biāo)：2.6已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時間復(fù)雜度（注意：mink和maxk是給定的兩個參變量，它們的。值為任意的整數(shù)）提示：注意檢查 mink 和maxk的合法性：minkltmaxk不要一個一個的刪除（多次修改next域）。（1）找到第一個應(yīng)刪結(jié)點的前驅(qū)preprelpl－gtnextwhilepnullampampp－gtdataltminkpreppp－gtnext（2）找到最后一個應(yīng)刪結(jié)點的后繼s，邊找邊釋放應(yīng)刪結(jié)點spwhilesnullampamps－gtdataltmaxktsss－g