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

習(xí)題課

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

、

、

和

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

、

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

、

和

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

、

、

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

和

來(lái)度量。6.

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

2在順序表中插入一個(gè)元素，需要平均移動(dòng)

元素，具體移動(dòng)的元素個(gè)數(shù)與

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

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

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

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

。

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

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

.

對(duì)于二維數(shù)組有

和

兩種不同的存儲(chǔ)方式.

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

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

.

5補(bǔ)充題:按增長(zhǎng)率由小到大的順序排列下列各函數(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補(bǔ)充題答案:答:按增長(zhǎng)率由小到大的順序各函數(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是無(wú)表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首

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

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

。在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是

。在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是

。在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是

。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è)有一個(gè)10*10的對(duì)稱矩陣A[10][10]，采取按行壓縮存儲(chǔ)的方式存放于一個(gè)一維數(shù)組B[]中，則數(shù)組B[]的容量應(yīng)有多大？若設(shè)A[0][0]為第一個(gè)元素，存放于B[0]，且數(shù)組A[][]的每一個(gè)數(shù)組元素在數(shù)組B[]中占一個(gè)數(shù)組元素位置，則A[8][5]在數(shù)組B[]中地址是多少？答案：

數(shù)組B應(yīng)有55個(gè)元素，對(duì)于下三角矩陣，LOC(A[8][5])=1+…+8+5=41對(duì)于上三角矩陣，LOC(A[8][5])=LOC(A[5][8])=10+9+8+7+6+(8-5)=439五、（1）畫出執(zhí)行下列各行語(yǔ)句后各指針及鏈表的示意圖。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六、簡(jiǎn)述以下算法的功能。

（1）voidA(nextL){//L是無(wú)表頭結(jié)點(diǎn)的單鏈表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)鏈表中的兩個(gè)結(jié)點(diǎn)。BB(pb,pa);}12數(shù)據(jù)結(jié)構(gòu):所研究?jī)?nèi)容的著重點(diǎn)主要體現(xiàn)在三個(gè)方面：第一是數(shù)據(jù)間的邏輯關(guān)系，即數(shù)據(jù)元素之間的關(guān)系。第二是數(shù)據(jù)的存儲(chǔ)關(guān)系，即數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)。第三是算法，即定義在邏輯關(guān)系上的一組操作。因此，簡(jiǎn)單說(shuō)來(lái)，數(shù)據(jù)結(jié)構(gòu)所研究的問(wèn)題是如何將現(xiàn)實(shí)世界中的事物合理描述為計(jì)算機(jī)世界中所研究的對(duì)象，并根據(jù)研究對(duì)象的特點(diǎn)，分析對(duì)象之間的關(guān)系、存儲(chǔ)結(jié)構(gòu)和操作的學(xué)科。試說(shuō)明基本數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的聯(lián)系與差異?；緮?shù)據(jù)類型（DataType）：

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

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

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

答：行優(yōu)先順序存放時(shí):Loc(aij)=Loc(a00)+(i*m+j)*K列優(yōu)先順序存放時(shí):Loc(aij)=Loc(a00)+(j*m+i)*K182-5在鏈表類的實(shí)現(xiàn)中增加一個(gè)成員函數(shù)實(shí)現(xiàn)對(duì)表中元素置逆的操作（設(shè)原鏈表為a0,a1,…,an-2,an-1；則置逆后的序列為an-1,an-2,…,a1,a0）。對(duì)于有n個(gè)元素的線性表，你的算法的運(yùn)行時(shí)間應(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è)計(jì)一個(gè)算法，將數(shù)組A(0..n-1)中的元素循環(huán)右移k位，假設(shè)原數(shù)組序列為a0,a1,…,an-2,an-1；移動(dòng)后的序列為an-k,an-k+1,…,a0,a1,…,an-k-1。要求只用一個(gè)元素大小的附加存儲(chǔ)，元素移動(dòng)或交換次數(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補(bǔ)充題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:

求鞍點(diǎn):二維數(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]中有多個(gè)零元素，是寫一函數(shù)，將A中所有非零元素依次移動(dòng)數(shù)組A的前端。4.設(shè)計(jì)一個(gè)算法，找單鏈表中值最