數(shù)據(jù)結(jié)構(gòu)課后部分習(xí)題 答案提示,授課教師：耿國華 教授,西北大學(xué)可視化技術(shù)研究所,第一章：緒論,1.2判斷題（在各題后填寫“”或“”）： （1）線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性 結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。（） （2）算法就是程序。（） （3）在高級(jí)語言（如C或 PASCAL）中，指針類型是原子類型。（）,西北大學(xué)可視化技術(shù)研究所,1.3填空題： （1）變量的作用域是指 變量的有效范圍 （2）抽象數(shù)據(jù)類型具有 數(shù)據(jù)抽象 、 信息隱蔽 的特點(diǎn)。 （3）一種抽象類型包括 數(shù)據(jù)對(duì)象 、 結(jié)構(gòu)關(guān)系 和 基本操作 。,西北大學(xué)可視化技術(shù)研究所,（4）當(dāng)需要用一個(gè)形式參數(shù)直接改變對(duì)應(yīng)實(shí)參的值時(shí)，該形式參數(shù)應(yīng)說明為 指針類型 。 （5）數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)分為 集合結(jié)構(gòu) 、 線性結(jié)構(gòu) 、 樹形結(jié)構(gòu) 和 圖結(jié)構(gòu) 四種。 （6）數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)分為 順序存儲(chǔ)結(jié)構(gòu) 和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 兩種。,西北大學(xué)可視化技術(shù)研究所,（7）在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖結(jié)構(gòu)中，數(shù)據(jù)元素之間分別存在著 一對(duì)一 、 一對(duì)多 和 多對(duì)多 的聯(lián)系。 （8）算法是規(guī)則的有限集合，是為解決特定問題而規(guī)定的 操作序列 。 （9）算法具有 有限性 、確定性、 可行性 、 輸入 、輸出五大特性。,西北大學(xué)可視化技術(shù)研究所,1.4 選擇題 （1）若需要利用形式參數(shù)直接訪問修改實(shí)參值，則應(yīng)將形參說明為 A 參數(shù)。 A.指針 B.值參數(shù),西北大學(xué)可視化技術(shù)研究所,（2）執(zhí)行下面的程序段的時(shí)間復(fù)雜度為 C 。 for(int i=0;im;i+) for(int j=0;jn;j+) aij=i*j; A.O(m2) B. O(n2) C. O(m*n) D. O (m+n),西北大學(xué)可視化技術(shù)研究所,(3)執(zhí)行下面程序段時(shí)，語句S的執(zhí)行次數(shù)為 C 。 for(int i=0;i=n;i+) for(int j=0;j=i;j+) S; A. n2 B. n2/2 C. (n+1) (n+2)/2 D. n(n+1)/2,西北大學(xué)可視化技術(shù)研究所,5.計(jì)算下列程序段中x=x+1的語句頻度： for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) x=x+1; 思路:語句頻度即為時(shí)間頻度，拆分循環(huán)語句， 先從后兩個(gè)for循環(huán)開始思考，最后循環(huán)i值。 第一步：,西北大學(xué)可視化技術(shù)研究所,第二步:計(jì)算結(jié)果,6.編寫算法，求一元多項(xiàng)式： 算法描述： void dxs(int a,int n,int x) int temp=x; /temp保存x的冪次方 int sum=0; /sum保存多項(xiàng)式的計(jì)算結(jié)果 int i,j,k; int bn; /bi保存多項(xiàng)式的每一項(xiàng)的帶全值 for(j=0;j=n;j+) bj=1; b0=a0; /x的0次方與x的0次方的系數(shù)的乘積 b1=a1*x; /x的1次方與x的1次方的系數(shù)的乘積,西北大學(xué)可視化技術(shù)研究所,for(j=2;j=n;j+) /從x的2次方開始，到x的n次方結(jié)束 for(k=2;k=j;k+) temp=temp*x; /保存x的m次方 bj=aj*temp; /x的m次方與x的m次方的系數(shù)的乘積 temp=x; for(i=0;i=n;i+) sum=sum+bi; cout“多項(xiàng)式的值是：“sumendl; ,西北大學(xué)可視化技術(shù)研究所,第二章 線性表,2.1 填空題 （1）在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) n/2 元素，具體移動(dòng)的元素個(gè)數(shù)與 插入或刪除位置 有關(guān)。 （2）線性表有 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 兩種存儲(chǔ)結(jié)構(gòu)。在順序表中，線性表的存儲(chǔ)空間在數(shù)組定義時(shí)就已確定，是 靜態(tài) 存儲(chǔ)分配，在鏈?zhǔn)奖碇?，整個(gè)鏈表由“頭指針”來表示，單鏈表的存儲(chǔ)空間在運(yùn)行時(shí)可以動(dòng)態(tài)變化，是 動(dòng)態(tài) 存儲(chǔ)分配。,西北大學(xué)可視化技術(shù)研究所,（3）順序表中，邏輯上相鄰的元素，其物理位置 也 相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置 不一定 相鄰。 （4）在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲(chǔ)位置由 頭指針 指示，首元素結(jié)點(diǎn)的存儲(chǔ)位置由 頭結(jié)點(diǎn)的next域 指示，除首元素結(jié)點(diǎn)外，其它任一元素結(jié)點(diǎn)的存儲(chǔ)位置由 其直接前驅(qū)的next域 指示。,西北大學(xué)可視化技術(shù)研究所,2.2選擇題,（1）在線性表中最常用的操作是存取第i個(gè)元 素及其前趨的值，可采用 A 存儲(chǔ)方式最省時(shí)間？ A. 順序表 B.帶頭結(jié)點(diǎn)的單向鏈表 C.帶頭指針的雙向循環(huán)鏈表 D.帶頭指針的單向循環(huán)鏈表 E.帶尾指針的單向循環(huán)鏈表,西北大學(xué)可視化技術(shù)研究所,（2）已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元素結(jié)點(diǎn)，也不是尾元素結(jié)點(diǎn)。按要求從下列語句中選擇合適的語句序列。 a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是： E. S-next= P-next; A. P-next=S; b.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是： H. Q= P; L. P= L; I. while(P-next!=Q) P=P-next;,西北大學(xué)可視化技術(shù)研究所,E. S-next= P-next; A. P-next=S; c. 在表首插入S結(jié)點(diǎn)的語句序列是 F. S-next= L; M. L= S; 。 d. 在表尾插入S結(jié)點(diǎn)的語句序列是： L. P= L; J. while(P-next!=NULL) P=P-next; A. P-next=S; G. S-next= NULL; 。,供選擇的語句有： A. P-next=S; B. P-next= P-next-next; C. P-next= S-next; E. S-next= P-next; F. S-next= L; G. S-next= NULL; H. Q= P; I. while(P-next!=Q) P=P-next; J. while(P-next!=NULL) P=P-next; K. P= Q; L. P= L; M. L= S; N. L= P;,（3）某線性表中最常用的操作是存取序號(hào)為i的元素和在最后進(jìn)行插入和刪除運(yùn)算，則采用 D 存儲(chǔ)方式 時(shí)間性能最好。 A雙向鏈表 B雙向循環(huán)鏈表 C單向循環(huán)鏈表 D順序表 （4）下列選項(xiàng)中， D 項(xiàng)是鏈表不具有的特點(diǎn)。 A插入和刪除運(yùn)算不需要移動(dòng)元素 B所需要的存儲(chǔ)空間與線性表的長度成正比 C不必事先估計(jì)存儲(chǔ)空間大小 D可以隨機(jī)訪問表中的任意元素,(5)在鏈表中最常用的操作是刪除表中最后一個(gè)結(jié)點(diǎn)和在最后一個(gè)結(jié)點(diǎn)之后插入元素，則采用 C 最節(jié)省時(shí)間。 A. 頭指針的單向循環(huán)鏈表 B雙向鏈表 C帶尾指針的單向循環(huán)鏈表 D帶頭指針雙向循環(huán)鏈表 (6)在線性表中最常用的操作是存取第i個(gè)元素及其前趨的值，可采用 A 存儲(chǔ)方式。 A順序表 B單向鏈表 C雙向循環(huán)鏈表 D單向循環(huán)鏈表,5.寫一個(gè)算法，從順序表中刪除自第i個(gè)元素開始的k個(gè)元素。 算法描述：以待移動(dòng)元素下標(biāo)m為中心， 計(jì)算應(yīng)移入位置： for ( m= i1+k; mlast; m+) Lelem mk = Lelem m ;,8.假設(shè)兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法，將A表和B表歸并成一個(gè)按元素值遞減有序排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點(diǎn)空間存放表C。,算法描述：要求利用現(xiàn)有的表A和B中的結(jié)點(diǎn)空間來建立新表C，可通過更改結(jié)點(diǎn)的next域來重新建立新的元素之間的線性關(guān)系。為保證新表遞減有序可以利用頭插法建立單鏈表的方法，只是新建表中的結(jié)點(diǎn)不用malloc，而只需要從A和B中選擇合適的點(diǎn)插入到新表C中即可。,合并兩個(gè)有序的單鏈表算法演示,LinkList MergeLinkList(LinkList A,LinkList B) /*將遞增有序的單鏈表A和B合并成一個(gè)遞減有序的單鏈表C*/ Node *pa,*pb,*smaller; LinkList C; /*將C初始置為空表，pa和pb分別指向兩個(gè)單鏈表A和B中的第一個(gè)結(jié)點(diǎn)，r初值為C*/ pa=A-next; pb=B-next; C=A; C-next=NULL; /*初始化操作*/,/*當(dāng)兩個(gè)表中均未處理完時(shí)，比較選擇將較大值結(jié)點(diǎn)插入到新表C中。*/ while(pa!=NULL ,10.已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符，數(shù)字字符和其它字符），試編寫算法來構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。,算法描述:只要新建三個(gè)頭結(jié)點(diǎn)，然后在原來的單鏈表中依次查詢，找到一類字符結(jié)點(diǎn)時(shí)，就摘下此結(jié)點(diǎn)鏈接到相應(yīng)頭結(jié)點(diǎn)指明的新鏈表中就可以實(shí)現(xiàn)題目的要求。 算法提示： 設(shè)已建立三個(gè)帶頭結(jié)點(diǎn)的空循環(huán)鏈表 A,B,C.,void DivideList( LinkList L, LinkList A, LinkList B, LinkList C) ListNode *p=L-next, *q; ListNode *a=A, ListNode *b=B; ListNode *c=C; while ( p ) if ( p-data=a /指向下一結(jié)點(diǎn) else if( p-data=0 & p-data=9) / 分出數(shù)字結(jié)點(diǎn),q=p; p=p-next; b-next=q; q-next=B; b=b-next; else /分出其他字符結(jié)點(diǎn) q=p; p=p-next; c-next=q; q-next=C; c=c-next; /結(jié)束,第三章 限定性線性表-棧和隊(duì)列,1、按書上圖3.1（b）所示鐵道（兩側(cè)鐵道均為單向行駛道）進(jìn)行車廂調(diào)度，回答 ： （1）如進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么？ 答案：123 132 213 231 321 （2）如進(jìn)站的車廂序列為123456，能否得到435612和135426的出站序列，并說明原因。（即寫出以“S”表示進(jìn)站，以“X”表示出站的棧操作序列）。,答案：435612不可以 原因 （1）S：1234 X：43 （2）S：5 X: 5 （3）S：6 X: 6 （4）X：21 135426 可以 原因（1）S：1 X：1 （2）S：23 X: 3 （3）S：45 X: 54 （4）X：2 （5）S：6 X: 6,3、給出棧的兩種存儲(chǔ)結(jié)構(gòu)形式名稱，在這兩種棧的存儲(chǔ)結(jié)構(gòu)中如何判斷?？蘸蜅M？ 答案：鏈棧和順序棧 鏈棧：?？眨侯^指針為空：即 if（head-next=NULL） 棧滿：結(jié)點(diǎn)存儲(chǔ)空間申請(qǐng)失敗 順序棧：棧空：棧下標(biāo)小于零：即 if（stack-toptopMAX）,4、按照四則運(yùn)算加、減、乘、除和冪（）運(yùn)算優(yōu)先關(guān)系的慣例，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)運(yùn)算數(shù)棧和運(yùn)算符棧的變化過程： A-B*C/D+E F 答案 ：,A,B,C,-,*,/=optr(*),T(1)=B*C,+=optr(/),T(2)=T(1)/D,A,-,D,T(1),/,A,T(2),-,T(3),F,E,+=optr(-),T(3)=A-T(2),+,右邊界#=optr(),T(4)=EF,T(3),T(4),+,右邊界#=optr(+),T(5)=T(3)+T(4),T(5),8、要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用，設(shè)置一個(gè)標(biāo)志域，以tag為0或1來區(qū)分頭尾指針相同時(shí)隊(duì)列狀態(tài)的空與滿，試編寫此結(jié)構(gòu)相應(yīng)的入隊(duì)與出隊(duì)算法。 入隊(duì)操作：,int enterqueue(seqqueue *q,element x) if(q-rear%MAXSIZE=q-front ,出隊(duì)操作： Int deletequeue(seqqueue *q,element *x) if(q-front=q-rear /*設(shè)標(biāo)志tag*/ return（true）； ,9、設(shè)4個(gè)元素1、2、3、4依次進(jìn)棧，而出棧操作可隨時(shí)進(jìn)行（進(jìn)出?？扇我饨诲e(cuò)進(jìn)行，但要保證進(jìn)棧不破環(huán)1、2、3、4的相對(duì)次序，）請(qǐng)寫出所有不可能的和可能的出棧次序。 所有可能的：1234 1243 1324 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321 所有不可能的： 1342 1423 2413 3124 3142 3412 4312 4213 4231