數(shù)據(jù)結(jié)構(gòu)課后習(xí)題及解析第二章.docx

第二章習(xí)題1. 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)。2. 填空：（1） 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 元素，具體移動(dòng)的元素個(gè)數(shù)與 有關(guān)。（2） 在順序表中，邏輯上相鄰的元素，其物理位置 相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置 相鄰。（3） 在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲(chǔ)位置由 指示，首元素結(jié)點(diǎn)的存儲(chǔ)位置由 指示，除首元素結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲(chǔ)位置由 指示。3已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元素結(jié)點(diǎn)，也不是尾元素結(jié)點(diǎn)。按要求從下列語句中選擇合適的語句序列。a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是： 。b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是： 。c. 在表首插入S結(jié)點(diǎn)的語句序列是： 。d. 在表尾插入S結(jié)點(diǎn)的語句序列是： 。供選擇的語句有：（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;4. 設(shè)線性表存于a(1:arrsize)的前elenum個(gè)分量中且遞增有序。試寫一算法，將X插入到線性表的適當(dāng)位置上，以保持線性表的有序性。5. 寫一算法，從順序表中刪除自第i個(gè)元素開始的k個(gè)元素。6. 已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時(shí)間復(fù)雜度（注意：mink和maxk是給定的兩個(gè)參變量，它們的值為任意的整數(shù)）。 7. 試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表（a1, a2., an）逆置為（an, an-1,., a1）。（1） 以一維數(shù)組作存儲(chǔ)結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)的前elenum個(gè)分量中。（2） 以單鏈表作存儲(chǔ)結(jié)構(gòu)。8. 假設(shè)兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法，將A表和B表歸并成一個(gè)按元素值遞減有序排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點(diǎn)空間存放表C。9. 假設(shè)有一個(gè)循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前趨結(jié)點(diǎn)。10. 已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其它字符），試編寫算法來構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。11. 設(shè)線性表A=(a1, a2,am)，B=(b1, b2,bn)，試寫一個(gè)按下列規(guī)則合并A、B為線性表C的算法，使得： C= (a1, b1,am, bm, bm+1, ,bn) 當(dāng)mn時(shí)；或者 C= (a1, b1,an, bn, an+1, ,am) 當(dāng)mn時(shí)。線性表A、B、C均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L度值m和n均未顯式存儲(chǔ)。12. 將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間來構(gòu)成這兩個(gè)鏈表。13. 建立一個(gè)帶頭結(jié)點(diǎn)的線性鏈表，用以存放輸入的二進(jìn)制數(shù)，鏈表中每個(gè)結(jié)點(diǎn)的data域存放一個(gè)二進(jìn)制位。并在此鏈表上實(shí)現(xiàn)對(duì)二進(jìn)制數(shù)加1的運(yùn)算 。14. 設(shè)多項(xiàng)式P(x)采用課本中所述鏈接方法存儲(chǔ)。寫一算法，對(duì)給定的x值，求P(x)的值。實(shí)習(xí)題1 將若干城市的信息存入一個(gè)帶頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)中的城市信息包括城市名、城市的位置坐標(biāo)。要求：（1） 給定一個(gè)城市名，返回其位置坐標(biāo)；（2） 給定一個(gè)位置坐標(biāo)P和一個(gè)距離D，返回所有與P的距離小于等于D的城市。2 約瑟夫環(huán)問題。約瑟夫問題的一種描述是：編號(hào)為1，2，n 的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)人開始順時(shí)針自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止 報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計(jì)一個(gè)程序，求 出出列順序。利用單向循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列順序打印出各人的編號(hào)。例如m的初值為20；n=7，7個(gè)人的密碼依次是：3，1，7，2，4，8，4，出列的順序?yàn)?，1，4，7，2，3，5。第二章答案約瑟夫環(huán)問題約瑟夫問題的一種描述為：編號(hào)1,2,n的n個(gè)人按順時(shí)針方向圍坐一圈，每個(gè)人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)報(bào)數(shù)上限值m,從第一個(gè)人開始順時(shí)針自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計(jì)一個(gè)程序，求出出列順序。利用單向循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列順序打印出各人的編號(hào)。例如m的初值為20；n=7，7個(gè)人的密碼依次是：3,1,7,2,4,8,4,出列順序?yàn)?,1,4,7,2,3,5?！窘獯稹克惴ㄈ缦拢簍ypedef struct Nodeint password;int num;struct Node *next; Node,*Linklist;void Josephus() Linklist L; Node *p,*r,*q; int m,n,C,j; L=(Node*)malloc(sizeof(Node); /*初始化單向循環(huán)鏈表*/ if(L=NULL) printf(n鏈表申請(qǐng)不到空間!);return; L-next=NULL; r=L; printf(請(qǐng)輸入數(shù)據(jù)n的值(n0):); scanf(%d,&n); for(j=1;jpassword=C; p-num=j; r-next=p; r=p; r-next=L-next;printf(請(qǐng)輸入第一個(gè)報(bào)數(shù)上限值m(m0):); scanf(%d,&m); printf(*n); printf(出列的順序?yàn)?n); q=L; p=L-next; while(n!=1) /*計(jì)算出列的順序*/ j=1; while(jnext; j+; printf(%d-,p-num); m=p-password; /*獲得新密碼*/ n-; q-next=p-next; /*p出列*/ r=p; p=p-next; free(r); printf(%dn,p-num);2.7試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)單線表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表（a1,a2,an）逆置為(an,an-1,a1)?！窘獯稹浚?）用一維數(shù)組作為存儲(chǔ)結(jié)構(gòu) void invert(SeqList *L, int *num) int j; ElemType tmp;for(j=0;jnext =NULL) return; /*鏈表為空*/ p=L-next; q=p-next; p-next=NULL; /* 摘下第一個(gè)結(jié)點(diǎn)，生成初始逆置表 */while(q!=NULL) /* 從第二個(gè)結(jié)點(diǎn)起依次頭插入當(dāng)前逆置表 */ r=q-next;q-next=L-next;L-next=q;q=r; 2.11將線性表A=(a1,a2,am), B=(b1,b2,bn)合并成線性表C, C=(a1,b1,am,bm,bm+1,.bn) 當(dāng)mn時(shí),線性表A、B、C以單鏈表作為存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L度值m和n均未顯式存儲(chǔ)。【解答】算法如下：LinkList merge(LinkList A, LinkList B, LinkList C) Node *pa, *qa, *pb, *qb, *p; pa=A-next; /*pa表示A的當(dāng)前結(jié)點(diǎn)*/ pb=B-next; p=A; / *利用p來指向新連接的表的表尾，初始值指向表A的頭結(jié)點(diǎn)*/ while(pa!=NULL & pb!=NULL) /*利用尾插法建立連接之后的鏈表*/ qa=pa-next; qb=qb-next; p-next=pa; /*交替選擇表A和表B中的結(jié)點(diǎn)連接到新鏈表中；*/p=pa;p-next=pb;p=pb; pa=qa;pb=qb;if(pa!=NULL) p-next=pa; /*A的長度大于B的長度*/ if(pb!=NULL) p-next=pb; /*B的長度大于A的長度*/C=A; Return(C);提示：第2章 線性表習(xí) 題2.1 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)。2.2 填空：（1） 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)一半元素，具體移動(dòng)的元素個(gè)數(shù)與插入或刪除的位置有關(guān)。（2） 在順序表中，邏輯上相鄰的元素，其物理位置相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置相鄰。（3） 在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲(chǔ)位置由指示，首元素結(jié)點(diǎn)的存儲(chǔ)位置由指示，除首元素結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲(chǔ)位置由其直接前趨的next域指示。2.3 已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元素結(jié)點(diǎn)，也不是尾元素結(jié)點(diǎn)。按要求從下列語句中選擇合適的語句序列。a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是：（4）、（1）。b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是：（7）、（11）、（8）、（4）、（1）。c. 在表首插入S結(jié)點(diǎn)的語句序列是：（5）、（12）。d. 在表尾插入S結(jié)點(diǎn)的語句序列是：（11）、（9）、（1）、（6）。供選擇的語句有：（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的有序性。提示：void insert(SeqList *L; ElemType x) （1）找出應(yīng)插入位置i，（2）移位，（3） 參P. 2292.5 寫一算法，從順序表中刪除自第i個(gè)元素開始的k個(gè)元素。提示：注意檢查i和k的合法性。 （集體搬遷，“新房”、“舊房”） 以待移動(dòng)元素下標(biāo)m（“舊房號(hào)”）為中心，計(jì)算應(yīng)移入位置（“新房號(hào)”）： for ( m= i1+k; mlast; m+) Lelem mk = Lelem m ; 同時(shí)以待移動(dòng)元素下標(biāo)m和應(yīng)移入位置j為中心： 以應(yīng)移入位置j為中心，計(jì)算待移動(dòng)元素下標(biāo)：2.6已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時(shí)間復(fù)雜度（注意：mink和maxk是給定的兩個(gè)參變量，它們的值為任意的整數(shù)）。 提示：注意檢查mink和maxk的合法性：mink next;while (p!=NULL & pdata next; （2） 找到最后一個(gè)應(yīng)刪結(jié)點(diǎn)的后繼s，邊找邊釋放應(yīng)刪結(jié)點(diǎn)s=p;while (s!=NULL & sdata next; free(t); （3） prenext = s;2.7試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表（a1, a2., an）逆置為（an, an-1,., a1）。（1） 以一維數(shù)組作存儲(chǔ)結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)的前elenum個(gè)分量中。（2） 以單鏈表作存儲(chǔ)結(jié)構(gòu)。方法1:在原頭結(jié)點(diǎn)后重新頭插一遍方法2:可設(shè)三個(gè)同步移動(dòng)的指針p, q, r，將q的后繼r改為p2.8 假設(shè)兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法，將A表和B表歸并成一個(gè)按元素值遞減有序的排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點(diǎn)空間存放表C.提示：參P.28 例2-1void merge(LinkList A; LinkList B; LinkList *C) pa=Anext; pb=Bnext; *C=A; (*C)next=NULL;while ( pa!=NULL & pb!=NULL ) if ( padata data ) smaller=pa; pa=panext; smallernext = (*C)next; /* 頭插法 */(*C)next = smaller;else smaller=pb; pb=pbnext; smallernext = (*C)next;(*C)next = smaller;while ( pa!=NULL) smaller=pa; pa=panext; smallernext = (*C)next; (*C)next = smaller;while ( pb!=NULL) smaller=pb; pb=pbnext; smallernext = (*C)next; (*C)next = smaller;LinkList merge(LinkList A; LinkList B) LinkList C；pa=Anext; pb=Bnext; C=A; Cnext=NULL; return C;2.9 假設(shè)有一個(gè)循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前趨結(jié)點(diǎn)。提示：設(shè)指針p指向s結(jié)點(diǎn)的前趨的前趨，則p與s有何關(guān)系？2.10 已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其它字符），試編寫算法來構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。2.11 設(shè)線性表A=(a1, a2,am)，B=(b1, b2,bn)，試寫一個(gè)按下列規(guī)則合并A、B為線性表C的算法，使得： C= (a1, b1,am, bm, bm+1, ,bn) 當(dāng)mn時(shí)；或者 C= (a1, b1,an, bn, an+1, ,am) 當(dāng)mn時(shí)。線性表A、B、C均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。注意：?jiǎn)捂湵淼拈L度值m和n均未顯式存儲(chǔ)。提示：void merge(LinkList A; LinkList B; LinkList *