數(shù)據(jù)結(jié)構(gòu) 第一版 (陳雁 著) 高等教育出版社 課后答案

課后答案網(wǎng)： 一章 習(xí)題 1、簡述下列術(shù)語： 數(shù)據(jù)元素、數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法 解： 數(shù)據(jù)元素 ：數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。 數(shù)據(jù) ：信息的載體。是描述客觀事物的數(shù)字、字符以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合。 數(shù)據(jù)對(duì)象 ：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 數(shù)據(jù)結(jié)構(gòu) ：相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合，包括數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩方面的內(nèi)容。 存儲(chǔ)結(jié)構(gòu) ： 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算集中的表示方式，包含順序存儲(chǔ)方法、鏈接存儲(chǔ)方法、索引存儲(chǔ)方法、散列存儲(chǔ)方法。 算法 ： 對(duì)特定問題求解步驟的一種描述，它是指令或語句的有限序列，并具有有窮型、確定性、可行性、輸入和輸出五個(gè)重要特性。 2、試寫一算法，自大至小依次輸出順序讀入的三個(gè)整數(shù) x，y 和 z 的值 解： f1( x,y,z; x,y,z:); %d,%d,%d,&x,&y,&z); if(xy) if(yz) %d,%d,%d,x,y,z); if(xz) %d,%d,%d,x,z,y); %d,%d,%d,z,x,y); if(xz) %d,%d,%d,y,x,z); if(zy) %d,%d,%d,z,y,x); %d,%d,%d,y,z,x); 課后答案網(wǎng)： 、舉出一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算等三方面的內(nèi)容 解： 4、分析下列 算法的時(shí)間復(fù)雜度： （ 1） n) i=2;0) 1; /* 表已空 */ -i=x) j=i;j+) L-j=L-j+1;/*被刪除元素之后的元素左移 */ i+; ; 4、設(shè)線性表 (， 儲(chǔ)在帶表頭結(jié) 點(diǎn)的單鏈表中，試設(shè)計(jì)算法，求出該線性表中值為 x 的元素的序號(hào)。如果 序號(hào)為 0。 H,x) p=H- j=1;f=0; /* P 指向第一個(gè)結(jié)點(diǎn)， j 為計(jì)數(shù)器， f 為標(biāo)志 */ p ) if(p-x) j+; p=p- f=1; f=1 ) 課后答案網(wǎng)： j; 0; 5、在一個(gè)非遞減有序線性表中，插入一個(gè)值為 x 的元素，使插入后的線性表仍為非遞減有序。分別寫出用順序表和單鏈表表示時(shí)的算法。 順序表： L ,x) L- 1; /* 表已滿 */ if(x=L- L-=x; L-1; i=1; x=L-i) i+; j=L-j=i;L-j+1=L-j; L-i=x; L-1; ; 單鏈表： H, x) p=H; s= () ; if(s) s-x; s- ; p-if(p- s-p- p-s; /* 插入 */ ; /* p-s; ; 6、設(shè)一個(gè)線性表 L=(， a n)，編寫算法將其逆置，即成為（ a n， 要求逆置后的線性表仍占用原來的存儲(chǔ)空間，并且用順序和單鏈表兩種方法表示，寫出不同的處理過程。 順序表： L ） i; x; i=1;i+) x=L-i; L-i=L-; L-=x; 單鏈表： H） d=h-if(d!= p=d-p) t=p-p-d; d=p; p=t; h=d; 課后答案網(wǎng)： 7、設(shè)兩個(gè)單鏈表 A 和 B，它們的數(shù)據(jù)元素分別為 ( ,x m)和 (， y n)。設(shè)計(jì)一個(gè)算法將它們合并為一個(gè)單鏈表 C，使得： 當(dāng) m n 時(shí)， C (.， x n， y n， .,x m ) 當(dāng) n m 時(shí)， C (.， y m ， x m， .,y n )。 A,B ) p=A-q=B-m=0; n=0; p) m+; p=p- q) n+; q=q- if(m=n) p=A-q=B-C=A; p=B-q=A-C=B; q) t=p-p-q; q=q-p-t; p=t; 課后答案網(wǎng)： ; 8、試寫一算法，在無表頭結(jié)點(diǎn)的單鏈表中值為 a 的結(jié)點(diǎn)前插入一個(gè)值為 b 的結(jié)點(diǎn) , 如果 a 不存在，則把 b 插在表尾 。將該算法與第 中的算法 2 7 進(jìn)行比較。 H, a, b) s=() ; s-b; s-= H=s; p=H; q=p-if(p-a)/*對(duì)首元節(jié)點(diǎn)處理 */ s-p; H=s; q&q-a) p=q; q=q- p-s; s-q; 9、假設(shè)有一個(gè)單向循環(huán)鏈表，其結(jié)點(diǎn)包含三個(gè)域： 中 數(shù)據(jù)域， 指針域，其值為后繼結(jié)點(diǎn)的地址， 為指針域，其初值為空（ 試設(shè)計(jì)算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表。 H) 課后答案網(wǎng)： q=H; p=H-p) p-q; q=p; p=p- H-q; q-; 10、已知二 維數(shù)組 A57，其每個(gè)元素占四個(gè)存儲(chǔ)單元，且A00的存儲(chǔ)地址為 1100，試求出元素 A35的存儲(chǔ)地址（分別討論以行為序和以列為序方式存儲(chǔ)時(shí)的結(jié)論）。 行為序 1100+4*(3*7+5)=1204 列為序 1100+4*(5*5+3)=1212 11、設(shè)有一個(gè)二維數(shù)組 AMN，對(duì)以下三種情況分別編寫算法： （ 1） 求數(shù)組 A 的最外圍元素之和； （ 2）求從 A00開始的互不相鄰的各元素之和； （ 3）當(dāng) M=N 時(shí)，分別求兩條對(duì)角線上的元素之和，否則輸出 M N 的信息。 1(MN)/* 求數(shù)組 A 的最外圍元素之和 */ s=0; i=0;*若 A 的當(dāng)前項(xiàng)的行號(hào)等于 B 當(dāng)前項(xiàng)的行號(hào)，則比較其列號(hào)，將較小列號(hào)的項(xiàng)放入 C，如果列號(hào)也相等，相加后放入 C； */ -iB-j-ij C-k-iC-k-iC-k-ik+; i+; -i-j C-k-jC-k-jC-k-jk+; 5 4 1 1 3 2 3 3 1 2 1 4 7 課后答案網(wǎng)： j+; C-k-jC-k-jC-k-j-ik+; j+; i+; -ij/*若 A 當(dāng)前項(xiàng)的行號(hào)小于 B 當(dāng)前項(xiàng)的行號(hào)，則將 A 項(xiàng)放入 C*/ C-k-iC-k-iC-k-ik+; i+; /*若 A 當(dāng)前項(xiàng)的行號(hào)大于 B 當(dāng)前項(xiàng)的行號(hào)，則將 B 項(xiàng)放入 C*/ C-k-jC-k-jC-k-jk+; j+; C-m=A-m;/*C 的行數(shù) */ C-n=A-n;/*C 的列數(shù) */ C-t=*C 的非零元個(gè)數(shù) */ 14、設(shè)稀疏矩陣 A 用十字鏈表表示，編寫算法查找元素： （ 1）已知 i， j，查找 Aij； （ 2）已知 x 的值，查找它在第幾行第幾列。 解： （ 1） *M,i,j, if(i0) p=M-i; 課后答案網(wǎng)： p) if(p-j) *p-;/*找到 */ p=p- ;/*未找到 */ 1;/*行號(hào)錯(cuò)誤 */ （ 2） *M,x, i=1;i+) p=M-i; p) if(p-x) *p-*p-; p=p- ; 上機(jī)實(shí)習(xí)題 1. 設(shè) A=（ , B=（ ,兩個(gè)線性表，其數(shù)據(jù)類型是整型。若 n=m 且 i n),則稱A=B；若 1 i j），而 j n m),則稱 AB；除此以外，均稱 A=B。設(shè)計(jì)一個(gè)比較 A、 B 大小的程序。 # 課后答案網(wǎng)： 00 /*存儲(chǔ)線性表中的元素 */ /*線性表的當(dāng)前表長 */ L) L=(); L-; ; L,i,x) j; ) ; /* 不合理的插入位置 i */ L- 1; /* 表已滿 */ j=L-j=i;L-j+1=L-j; /* 插入位置及之后的元素右移 */ L-i=x; /*插入 x */ +L- /*表長加 1 */ ; f(A,) i=1,j,; s); s); -i=B-i) i+; j=i;j+) s,A-j); j=i;j+) s,B-j); s-s-if(0) ; 課后答案網(wǎng)： if(0&|(&) 1; ; A=B=n=0,m=0,i=0,d=0; A=); B=); !=B) A!=B); A=B); n:); %d,&n); i=1;i+) %d ,A-i); n); m:); %d,&m); i=1;i+) %d ,B-i); n); n); i=1;i+) %d ,A-i); n); i=1;i+) 課后答案網(wǎng)： %d ,B-i); i=f(A,B); if(i=0) A=B); if(; ; 2. 設(shè)計(jì)一個(gè)程序求出約瑟夫環(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ù)，如此下去，直至所有人全部出列為止。例如 n=7,7 個(gè)人的密碼依次為： 3， 1， 7， 2， 4， 8， 4， ，則正確的出列順序應(yīng)為 6， 1， 4， 7， 2， 3， 5。要求使用單向循環(huán)鏈表模擬此出列過程。 # x, s; s=(); s-x; s-id=if( s; s-s; 課后答案網(wǎng)： s-s; s; p=q=d,m,i=1; ); %d,&d); d!=0) d,i+); ); %d,&d); p=*顯示數(shù)據(jù) */ p!= %d ,p- p=p- %d,p- m:);/*輸入初始 m*/ %d,&m); p=p!=p- i=1;q=p-p-q-m=q- 課后答案網(wǎng)： %d ,q- q); %d ,p- p); ; 第三章 習(xí) 題 l假定有編號(hào)為 A、 B、 C 的 3 輛列車，順序開進(jìn)一個(gè)棧式結(jié)構(gòu)的站臺(tái)，請(qǐng)寫出開出車站站臺(tái)的列車順序 (注：每一列車由站臺(tái)開出時(shí)均可進(jìn)棧，出棧開出站臺(tái)，但不允許出棧后回退 )。寫出每一種可能的序列。 解： 產(chǎn)生： 會(huì)產(chǎn)生： 有字符串次序?yàn)?5*y 2，試?yán)?用棧排出將次序改變?yōu)?5y-*（可用 X 代表掃描該字符串過程中順序取一字符進(jìn)棧的操作，用 S 代表從棧中取出一字符加到新字符串尾的出棧的操作）。例如， 為 操作步驟為 解： 寫出鏈棧的取棧頂元素和置棧空的算法。 解： （ 1） Y) if(1 y=; （ 2） 課后答案網(wǎng)： p=p); 4假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧，編寫一個(gè)判別表達(dá)式中括弧是否正確配對(duì)的算法。 解： f() p); p,#); c=; c!=#|p)!=#) if(c=(|c=|c=) p,c); if(c=) p,o); if(o!=() 1; if(c=) p,o); if(o!=) 1; if(c=) p,o); if(o!=) 1; c=; ; 課后答案網(wǎng)： 寫出計(jì)算表達(dá)式 5+3*4/6操作 數(shù)棧和運(yùn)算符棧的變化情況。 解： 步驟 入字符 1 # 5+3*4/62 # 5 +3*4/63 #+ 5 3*4/64 #+ 5， 3 *4/65 #+* 5， 3 4/66 #+* 5， 3， 4 /67 #+ 5， 12 /68 #+/ 5， 12 69 #+/ 5， 12， 6 10 #+ 5， 2， 11 # 7 12 #- 7 7# 13 #- 7， 7 # 14 # 0 # 6對(duì)于給定的十進(jìn)制正整數(shù)，打印出對(duì)應(yīng)的八進(jìn)制正整數(shù)。 (1)寫出遞歸算法。 (2)寫出非遞歸算法。 解： f(n)/* 遞歸算法 */ *退棧求值 */ 0; 2=0=1*2; 0); 課后答案網(wǎng)： 對(duì)于一個(gè)具有 m 個(gè)單元的循環(huán)隊(duì)列，寫出求隊(duì)列中元素個(gè)數(shù)的公式。 解： (m)%m 9假設(shè)用一個(gè)數(shù)組 QM來表示隊(duì)列，該隊(duì)列只設(shè)一個(gè)隊(duì)頭指針 設(shè)隊(duì)尾指針而改設(shè)計(jì)數(shù)器 以記錄隊(duì)列中元素的個(gè)數(shù)。試編寫出相應(yīng)的置空隊(duì)列，入隊(duì)列和出隊(duì)列的算法。 解： /*隊(duì)頭 */ *置空隊(duì)列 */ ; ; x)/* 在循環(huán)隊(duì)列 尾部插入一個(gè)新的元素 x */ q-1;/*隊(duì)列上溢 */ ; q-x; ; y)/*刪除循環(huán)隊(duì)列 隊(duì)頭元素，并存人 *y 中 */ q-0) 1;/*隊(duì)列下溢 */ )% 課后答案網(wǎng)： y=q- ; 10假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表示列隊(duì)，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn) (注意不設(shè)頭指針 )，試編寫出相應(yīng)的置空隊(duì)列，入隊(duì)列和出隊(duì)列的算法。 解： /*結(jié)點(diǎn)結(jié)構(gòu) */ * * /*隊(duì)尾指針 */ *置 空隊(duì)列 */ q-*循環(huán)隊(duì)列為非空 */ q- p=p); x)/* 在循環(huán)隊(duì)列 尾部插入一個(gè)新的元素 x */ p=(); if(p=1; 課后答案網(wǎng)： p-x; p- q-*循環(huán)隊(duì)列為空 */ p; p-p; q-s; s; s- ; y)/*刪除循環(huán)隊(duì)列 隊(duì)頭元素，并存人 *y 中 */ q-*隊(duì)列下溢 */ 1; q-if(*只有一個(gè)節(jié)點(diǎn) */ *y= *y= ; 課后答案網(wǎng)： 機(jī)實(shí)習(xí)題 1設(shè)計(jì)一個(gè)算法，檢驗(yàn) C 源程序代碼中的括弧對(duì)是否正確配對(duì)。要求在某個(gè) C 源程序文件上對(duì)你的算法進(jìn)行驗(yàn)正。 # * x) p; p=(); p-x; p-p; y, p; if(*; /*鏈棧已空 */ /*出棧 */ p=*y=p- p-*; ) ch,o; ; p=if(2) 課后答案網(wǎng)： to n); ); fp=,r)= n); ); ch= if(|) cn, p=p, if() p=p,&o,& ):c,%dn,o, if(0) d (); o) ( : :);); :);); if() p=p,&o,& :c,%dn,o, if(0) d ); o) ( :);); : :);); 課后答案網(wǎng)： if() p=p,&o,& :c,%dn,o, if(0) d ); o) ( :);); :);); : ch= p=p,&o,& if(0) ; 0)/*如果棧未空 */ o) ( :); :); :); p=p,&o,& ; 課后答案網(wǎng)： 設(shè)計(jì)程序，模擬手機(jī)的某些短信息功能。 功能要求： （ 1）接受短信 息，若超過存儲(chǔ)容量（如最多可存儲(chǔ) 20 條），自動(dòng)將最早接受的信息刪除。 （ 2）顯示短信息數(shù)量。 （ 3）逐條顯示短信息（從最新的開始）； （ 4）刪除其中的任意一條短信息； （ 5）清除。 /* （ 1）接受短信息，若超過存儲(chǔ)容量（如最多可存儲(chǔ) 20 條），自動(dòng)將最早接受的信息刪除。 （ 2）顯示短信息數(shù)量。 （ 3）逐條顯示短信息（從最新的開始）； （ 4）刪除其中的任意一條短信息； （ 5）清除。 */ #0/*存儲(chǔ)容量 */ #00/*信息長度 */ /*結(jié)點(diǎn)結(jié)構(gòu) */ * * *隊(duì)頭指針 */ * /*隊(duì)尾指針 */ /*初始化 */ p; q; p=(); 課后答案網(wǎng)： p-; q=(); q-p-q; p-q; p; * 獲得新短信 */ t; p; t= t);/*獲得時(shí)間信息，模擬短信內(nèi)容 */ q- q); p=(); ; p- p; p; ; ; *刪除循環(huán)隊(duì)列 隊(duì)頭元素 */ p; q-; p= /*p 指向新的隊(duì)頭結(jié)點(diǎn) */ p-p ) q-*尾指針指向頭結(jié)點(diǎn) */ p); 1; 課后答案網(wǎng)： Lq,i)/*刪除循環(huán)隊(duì)列 第 i 個(gè)元素 */ p,* q; n=1; q-; p=n+; q=p-p-q-q ) p;/*尾指針指向前結(jié)點(diǎn) */ q); 1; Lq,i)/*顯示第 i 條短信 */ p=n=1; if(i0& n+; d d:%sn,i, q-q); nnnn); 課后答案網(wǎng)： = n); = to =n); = =n); = to a =n); = to =n); = to =n); =n); = =n); = =n); = =n); = n); nnnn); ) c; p; i; p=; ; c=; c!=q&c!=Q) c) g: /*獲得新消息 */ G:p);e: /*顯示消息 */ E:i=1;i+) p,i);d: /*刪除當(dāng)前消息 */ D:i:);%d,&i);p,i);p: /*刪除最先的紀(jì)錄 */ P:p);r: /*清楚所有消息 */ R:p); c=; ; p); ; 課后答案網(wǎng)： B D J I E K H G F C 題圖 4樹 T 第四章 1有一棵樹如題圖 4示，求出樹的葉子結(jié)點(diǎn)、非終端結(jié)點(diǎn)、各結(jié)點(diǎn)的度、樹的度和樹深。 解 ： （ 1）葉子結(jié)點(diǎn)： E、 F、 G、 H、 K、 J （ 2）非終端結(jié)點(diǎn)： A、 B、 C、 D、 I （ 3）各結(jié)點(diǎn)的度：度為 3 的結(jié)點(diǎn)： A、 C 度為 2 的結(jié)點(diǎn)： D 度為 1 的結(jié)點(diǎn)： B、 I 度為 0 的結(jié)點(diǎn)： E、 F、 G、 H、 K、 J （ 4）樹的度： 3 （ 5）樹深： 4 2具有三個(gè)結(jié)點(diǎn)的二叉樹有多少種不同的形態(tài) ?請(qǐng)分別畫出。 解 ：具有三個(gè)結(jié)點(diǎn)的二叉樹有 5 種不同的形態(tài)，如下所示： 3如果一棵樹有 的結(jié)點(diǎn)， 的結(jié)點(diǎn)， ， n m 的結(jié)點(diǎn)，則該樹共有多少個(gè)葉子結(jié)點(diǎn) ?可參考二叉樹性質(zhì) 3 的證明方法來思 考 m 叉樹問題。 解 : 設(shè)樹中有 葉子結(jié)點(diǎn)，那么樹中總結(jié)點(diǎn)數(shù) N 為： N + （ a） 由于 樹中除根結(jié)點(diǎn)外，其它各結(jié)點(diǎn)都有僅有一個(gè)分支指向它，所以樹中的總結(jié)點(diǎn)數(shù)恰好比分支數(shù)少 1。 設(shè) B 為 樹中總分支數(shù)，即有： B 外，除度為 0 的結(jié)點(diǎn)沒有 分支外，每個(gè) 度為 k 的結(jié)點(diǎn)有 k 個(gè) 分支，所以總分支數(shù)又為： B 1+m 即 總結(jié)點(diǎn)數(shù)為： N +m （ b） 由式 (a)和式 (b)有： + +m 即得： 1+（ （ （ 1 （ i=2 m） 4寫出按層遍歷二叉樹的算法。 課后答案網(wǎng)： ：二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)描述為： /* 數(shù)據(jù)域 */ * /* 左、右孩子指針域 */ /* 按層次遍歷二叉樹 ， 類型的隊(duì)列 */ ); /* 初始化隊(duì)列 Q */ if( , /*根結(jié)點(diǎn)入隊(duì)列 */ ) /*隊(duì)列非空 */ Q,&p); /*隊(duì)頭元素存入變量 (p- /*訪問根結(jié)點(diǎn) */ if(p- ,p- if(p- , p- /* 5設(shè)計(jì)算法求二叉樹中度為 1 的結(jié)點(diǎn)數(shù)。 解 ：設(shè)置一個(gè)初始值為 0 的全局變量 行計(jì)數(shù)，在對(duì)二叉樹進(jìn)行遍歷的過程中判斷當(dāng)前所訪問的結(jié)點(diǎn)是否為度為 1的結(jié)點(diǎn)，若是則 。因此當(dāng)遍歷完整個(gè)二叉樹后， 的結(jié)點(diǎn)的數(shù)目。算法描述如下： ; & !|(!& ; /*計(jì)數(shù) */ /* 設(shè)計(jì)遞歸算法，求出先根序列中第 k 個(gè)結(jié)點(diǎn)的值。 解 : bt,k) /*求先序序列中第 */ n; n=k; if( if(n=0) 課后答案網(wǎng)： n); if(n!=0) n); #); 7現(xiàn)有按中根遍歷二叉樹的結(jié)果為： 畫出可以得到這一結(jié)果的全部二叉樹。 解 ： 8已知遍歷某二叉樹后的中根遍歷序列 后根遍歷序列 畫出該二叉樹。 解 ：根據(jù)二叉樹后的中根遍歷和后根遍歷的 特點(diǎn)，其中根遍歷序列和后根遍歷序列的形式如下所示： 顯然，后根歷序列中的最后一個(gè)結(jié)點(diǎn)就是二叉樹的根結(jié)點(diǎn)，然后再在中根序列中找