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