數(shù)據(jù)結(jié)構(gòu)(1,2,3章)課后題答案課件

數(shù)據(jù)結(jié)構(gòu)課后部分習(xí)題

答案提示授課教師：耿國(guó)華教授第一章：緒論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ù)研究所（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(inti=0;i<m;i++) for(intj=0;j<n;j++)a[i][j]=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(inti=0;i<=n;i++)for(intj=0;j<=i;j++)S;A.n2 B.n2/2 C.(n+1)(n+2)/2 D.n(n+1)/2西北大學(xué)可視化技術(shù)研究所第二步:計(jì)算結(jié)果

for(j=2;j<=n;j++)//從x的2次方開始，到x的n次方結(jié)束{ for(k=2;k<=j;k++) { temp=temp*x;//保存x的m次方 } b[j]=a[j]*temp;//x的m次方與x的m次方的系數(shù)的乘積 temp=x; } for(i=0;i<=n;i++) sum=sum+b[i]; cout<<"多項(xiàng)式的值是："<<sum<<endl;}西北大學(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;(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=i－1+k;m<=L－>last;m++)L－>elem[m－k]=L－>elem[m];算法描述：要求利用現(xiàn)有的表A和B中的結(jié)點(diǎn)空間來建立新表C，可通過更改結(jié)點(diǎn)的next域來重新建立新的元素之間的線性關(guān)系。為保證新表遞減有序可以利用頭插法建立單鏈表的方法，只是新建表中的結(jié)點(diǎn)不用malloc，而只需要從A和B中選擇合適的點(diǎn)插入到新表C中即可。合并兩個(gè)有序的單鏈表算法演示LinkListMergeLinkList(LinkListA,LinkListB)/*將遞增有序的單鏈表A和B合并成一個(gè)遞減有序的單鏈表C*/{Node*pa,*pb,*smaller;LinkListC;/*將C初始置為空表，pa和pb分別指向兩個(gè)單鏈表A和B中的第一個(gè)結(jié)點(diǎn)，r初值為C*/pa=A->next;pb=B->next;C=A;C->next=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.voidDivideList(LinkListL,LinkListA,LinkListB,LinkListC){ListNode*p=L->next,*q;ListNode*a=A,ListNode*b=B;ListNode*c=C;while(p){if(p->data>='a'&&p->data<='z'||p->data>='A'&&p->data<='Z'){q=p;//保存字母結(jié)點(diǎn)位置p=p->next;//指向下一結(jié)點(diǎn)}elseif(p->data>='0'&&p->data<='9'){//分出數(shù)字結(jié)點(diǎn)第三章限定性線性表-----棧和隊(duì)列1、按書上圖3.1（b）所示鐵道（兩側(cè)鐵道均為單向行駛道）進(jìn)行車廂調(diào)度，回答：（1）如進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么？ 答案：123132213231321（2）如進(jìn)站的車廂序列為123456，能否得到435612和135426的出站序列，并說明原因。（即寫出以“S”表示進(jìn)站，以“X”表示出站的棧操作序列）。答案：435612不可以原因（1）S：1234X：43 （2）S：5X:5 （3）S：6X:6 （4）X：21 135426可以 原因（1）S：1X：1 （2）S：23X:3 （3）S：45X:54 （4）X：2 （5）S：6X: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->top<0） 棧滿：棧下標(biāo)大于棧空間MAX：即 if（stack->top>MAX）

4、按照四則運(yùn)算加、減、乘、除和冪（↑）運(yùn)算優(yōu)先關(guān)系的慣例，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)運(yùn)算數(shù)棧和運(yùn)算符棧的變化過程： A-B*C/D+E↑F答案：

ABC-*‘/’<=optr(‘*’)T(1)=B*C‘+’<=optr(‘/’)T(2)=T(1)/DA-DT(1)/AT(2)-T(3)FE‘+’<=optr(‘-’)T(3)=A-T(2)+↑右邊界‘#’<=optr(‘↑’)T(4)=E↑FT(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ì)操作：

intenterqueue(seqqueue*q,elementx){ if(q->rear%MAXSIZE==q->front&&tag==1) /*隊(duì)列已滿 return(FALSE); q->element[q->rear]=x;/*裝元素*/ q->rear=(q->rear+1)%MAXSIZE;

if(q->rear%MAXSIZE==q->front)/*判斷并設(shè)置 標(biāo)志位tag*/ tag=1; return(true);}出隊(duì)操作：Intdeletequeue(seqqueue*q,element*x) { if(q->front==q->rear&&tag==0) return(FALSE); *x=q->element[q->front]; q->front=(q->front+1)%MAXSIZE;

if(q->front==q->rear)tag==0;/*設(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)寫出所有不可能的和可能的出棧次序。所有可能的：1234124313241432213421432314234124313214 324134214321所有不可能的：1342142324133124 3142341243124213 42314123413212、簡(jiǎn)述以下算法的功能（其中棧和隊(duì)列的元素類型均為int）Vo