數(shù)據(jù)結(jié)構(gòu)1-2章習(xí)題課答案知識分享

習(xí)題課

（1~2章）1一、填空題數(shù)據(jù)的邏輯結(jié)構(gòu)被分為

、

、

和

4種.數(shù)據(jù)的存儲結(jié)構(gòu)被分為

、

2種.在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，直接前驅(qū)和直接后繼結(jié)點之間分別存在著

、

和

的聯(lián)系。4.一個算法應(yīng)具有

、

、

輸入和輸出特性.5.一個算法的效率主要由

和

來度量。6.

抽象數(shù)據(jù)類型包括___________和______________。

2在順序表中插入一個元素，需要平均移動

元素，具體移動的元素個數(shù)與

有關(guān)。8.在順序表中邏輯上相鄰的元素的物理位置

緊鄰。單鏈表中邏輯上相鄰的元素的物理位置

緊鄰。9.在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由

指示。10.在單鏈表中設(shè)置頭結(jié)點的作用是

。

316.一維數(shù)組邏輯結(jié)構(gòu)是

,存儲結(jié)構(gòu)是

.

對于二維數(shù)組有

和

兩種不同的存儲方式.

對于一個二維數(shù)組A[m][n],若采用行優(yōu)先順序存儲的

方式,則任一數(shù)組元素A[i][j]相對于A[0][0]的地址為

.

5補充題:按增長率由小到大的順序排列下列各函數(shù)：2100，(3/2)n，(2/3)n，(4/3)n，nn，n2/3，n1/2，n!，n，log2n，n/log2n，log22n，log2(log2n)，nlog2n，nlog2n

6補充題答案:答:按增長率由小到大的順序各函數(shù)為：(2/3)n，2100，log2(log2n)，log2n，log22n，n1/2，n2/3，n/log2n，n，nlog2n,(4/3)n，(3/2)n，n!，nn7二、已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首

元結(jié)點，也不是尾結(jié)點，試從下列提供的答案中選

擇合適的語句序列。在P結(jié)點后插入S結(jié)點的語句序列是

。在P結(jié)點前插入S結(jié)點的語句序列是

。在表首插入S結(jié)點的語句序列是

。在表尾插入S結(jié)點的語句序列是

。P->next=S;(2)p->next=p->next->next;P->next=S->next;(4)S->next=P->next;S->next=L;(6)S->next=NULL;Q=P;while(P->next!=Q)P=P->next;while(P->next!=NULL)P=P->next;P=Q;(11)P=L;(12)L=S;(13)L=P;8四、設(shè)有一個10*10的對稱矩陣A[10][10]，采取按行壓縮存儲的方式存放于一個一維數(shù)組B[]中，則數(shù)組B[]的容量應(yīng)有多大？若設(shè)A[0][0]為第一個元素，存放于B[0]，且數(shù)組A[][]的每一個數(shù)組元素在數(shù)組B[]中占一個數(shù)組元素位置，則A[8][5]在數(shù)組B[]中地址是多少？答案：

數(shù)組B應(yīng)有55個元素，對于下三角矩陣，LOC(A[8][5])=1+…+8+5=41對于上三角矩陣，LOC(A[8][5])=LOC(A[5][8])=10+9+8+7+6+(8-5)=439五、（1）畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。Node*L=newNode();P=L;for(i=1;i<=4;i++){Node*Q=newNode();P->next=Q;P=P->next;P->data=2*i-1;}P->next=NULL;for(i=4;i>=1;i--){Insert(2*i,i+1);for(i=1;i<=3;i++){Delete(i);}

10六、簡述以下算法的功能。

（1）voidA(nextL){//L是無表頭結(jié)點的單鏈表if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}

11(2)voidBB(ListNode*s;ListNode*q){p=s;while(p-next!=q)p-p->next;p->next=s;}voidAA(ListNode*pa;ListNode*pb){BB(pa,pb);//pa和pb分別指向單循環(huán)鏈表中的兩個結(jié)點。BB(pb,pa);}12數(shù)據(jù)結(jié)構(gòu):所研究內(nèi)容的著重點主要體現(xiàn)在三個方面：第一是數(shù)據(jù)間的邏輯關(guān)系，即數(shù)據(jù)元素之間的關(guān)系。第二是數(shù)據(jù)的存儲關(guān)系，即數(shù)據(jù)在計算機中的存儲結(jié)構(gòu)。第三是算法，即定義在邏輯關(guān)系上的一組操作。因此，簡單說來，數(shù)據(jù)結(jié)構(gòu)所研究的問題是如何將現(xiàn)實世界中的事物合理描述為計算機世界中所研究的對象，并根據(jù)研究對象的特點，分析對象之間的關(guān)系、存儲結(jié)構(gòu)和操作的學(xué)科。試說明基本數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的聯(lián)系與差異。基本數(shù)據(jù)類型（DataType）：

在程序設(shè)計高級語言中，數(shù)據(jù)類型用來說明一個數(shù)據(jù)在數(shù)據(jù)分類中的歸屬。它是數(shù)據(jù)的一種屬性。這個屬性限定了該數(shù)據(jù)的變化范圍。高級語言中都有基本數(shù)據(jù)類型。例如在C、C++和Java語言中，有基本類型int（整型）、float（浮點型）和char（字符型），有構(gòu)造類型數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型和自定義等。數(shù)據(jù)類型僅局限于計算機中定義并實現(xiàn)了的數(shù)據(jù)類型;13抽象數(shù)據(jù)類型：是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于抽象數(shù)據(jù)類型的邏輯特性，與它在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。即不論其內(nèi)部結(jié)構(gòu)如何變化，只要數(shù)學(xué)特性不變，都不影響抽象數(shù)據(jù)類型外部的使用。抽象數(shù)據(jù)類型除了計算機中定義并實現(xiàn)了的數(shù)據(jù)類型；還包括用戶在設(shè)計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。141-5試說明數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法三者之間的關(guān)系。

1個數(shù)據(jù)邏輯結(jié)構(gòu)可有多種不同的存儲結(jié)構(gòu)；存儲結(jié)構(gòu)是對邏輯結(jié)構(gòu)實現(xiàn)；算法是基于邏輯結(jié)構(gòu)對操作的實現(xiàn)；函數(shù)是基于存儲結(jié)構(gòu)對算法的實現(xiàn)，是程序；答：數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法是數(shù)據(jù)結(jié)構(gòu)所討論的三個方面。151-6請給出下列函數(shù)的大O和Ω表示：O(n1/2logn2)O(n2)

O(n1.5)O(n1/2)162-1．描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首結(jié)點（第一個元素結(jié)點）。在單鏈表中設(shè)置頭結(jié)點的作用是什么？答：首結(jié)點就是存放數(shù)據(jù)元素的第一個元素結(jié)點，頭結(jié)點是為了插入和刪除的方便說增設(shè)的一個結(jié)點，頭指針是指向鏈表中第一個結(jié)點的存儲位置，在沒有頭結(jié)點的鏈表中，頭指針指向鏈表中的首結(jié)點，在有頭結(jié)點的鏈表中，頭指針指向鏈表中的頭結(jié)點。習(xí)題2（p55）172-4已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個元素占K個存儲單元，并且第一個元素的存儲地址為Loc(a00)，請寫出求Loc(aij)的計算公式。如果采用列優(yōu)先順序存放呢？

答：行優(yōu)先順序存放時:Loc(aij)=Loc(a00)+(i*m+j)*K列優(yōu)先順序存放時:Loc(aij)=Loc(a00)+(j*m+i)*K182-5在鏈表類的實現(xiàn)中增加一個成員函數(shù)實現(xiàn)對表中元素置逆的操作（設(shè)原鏈表為a0,a1,…,an-2,an-1；則置逆后的序列為an-1,an-2,…,a1,a0）。對于有n個元素的線性表，你的算法的運行時間應(yīng)為O(n)。

voidLinkList::Inverse(){if(head->next==NULL)return;p=head->next;head->next=NULL;while(p!=NULL){q=p->next;p->next=head->next;head->next=p;p=q;}}192-10設(shè)計一個算法，將數(shù)組A(0..n-1)中的元素循環(huán)右移k位，假設(shè)原數(shù)組序列為a0,a1,…,an-2,an-1；移動后的序列為an-k,an-k+1,…,a0,a1,…,an-k-1。要求只用一個元素大小的附加存儲，元素移動或交換次數(shù)為O(n)。voidyouyi(inta[],intn,intk){intb;for(inti=0;i<k;i++){b=a[n-1];for(j=n-2;j>=0;j--)a[j+1]=a[j];a[0]=b;}}20補充題1.數(shù)組置逆voidinverse(DataTypeA[],intn){for(i=0;i<n/2;i++){temp=A[i];A[i]=A[n-1-i];A[n-1-i]=temp;}}212:

求鞍點:二維數(shù)組中行最小,列最大的元素

voidminmax(intA[][],intm,intn){for(i=0;i<m;i++){row=A[i][0];k=0;for(j=1;j<n;j++)if(A[i][j]<row){k=j;row=A[i][j];}tag=1;h=0;while(tag&&h<m){if(A[h][k]>row)tag=0;elseh++;}if(tag)cout<<i<<“”<<j<<“”<<row<<endl;}22練習(xí)題：3.設(shè)數(shù)組A[n]中有多個零元素，是寫一函數(shù)，將A中所有非零元素依次移動數(shù)組A的前端。4.設(shè)計一個算法，找單鏈表中值最