數(shù)據(jù)結(jié)構(gòu)耿國華課后答案

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)耿國華課后答案數(shù)據(jù)結(jié)構(gòu)耿國華課后答案本文由edu_tech貢獻第一章緒論一、問答題

1.什么是數(shù)據(jù)結(jié)構(gòu)？

2.表達四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。3.表達算法的定義與特性。4.表達算法的時間繁雜度。5.表達數(shù)據(jù)類型的概念。

6.表達線性結(jié)構(gòu)與非線性結(jié)構(gòu)的區(qū)別。7.表達面向?qū)ο蟪绦蛟O(shè)計語言的特點。

8.在面向?qū)ο蟪绦蛟O(shè)計中，類的作用是什么？9.表達參數(shù)傳遞的主要方式及特點。10.表達抽象數(shù)據(jù)類型的概念。

二、判斷題（在各題后填寫“√〞或“×〞）

1.線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。（）2.算法就是程序。（）

3.在高級語言（如C或PASCAL）中，指針類型是原子類型。（）三、計算以下程序段中X=X+1的語句頻度for(i=1;inext=S;

（2）P->next=P->next->next;（3）P->next=S->next;（4）S->next=P->next;（5）S->next=L;

（6）S->next=NULL;（7）Q=P;

（8）while(P->next!=Q)P=P->next;（9）while(P->next!=NULL)P=P->next;（10）P=Q;（11）P=L;（12）L=S;（13）L=P;

2.4已知線性表L遞增有序。試寫一算法，將X插入到L的適當(dāng)位置上，以保持線性表L的有序性。

StatusInsert_SqList(SqListva.length++;

for(i=va.length-1;va.elem[i]>xi--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;returnOK;}//Insert_SqList

2.5寫一算法，從順序表中刪除自第i個元素開始的k個元素。[提醒]：注意檢查i和k的合法性。（集體搬遷，“新屋〞、“舊房〞）

以待移動元素下標(biāo)m（“舊房號〞）為中心，計算應(yīng)移入位置（“新屋號〞）：

for(m=i－1+k;mlast;m++)L－>elem[m－k]=L－>elem[m];

同時以待移動元素下標(biāo)m和應(yīng)移入位置j為中心：

以應(yīng)移入位置j為中心，計算待移動元素下標(biāo)：

2.6已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時間繁雜度（注意：mink和maxk是給定的兩個參變量，它們的值為任意的整數(shù)）。

StatusDelete_Between(Linklist

while(p->next->datanext;//p是最終一個不大于mink的元素if(p->next)//假使還有比mink更大的元素{

q=p->next;

while(q->datanext;//q是第一個不小于maxk的元素p->next=q;}

}//Delete_Between

2.7試分別以不同的存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法，即在原表的存儲空間將線性表（a1,a2...,an）逆置為（an,an-1,...,a1）。

（1）以一維數(shù)組作存儲結(jié)構(gòu)，設(shè)線性表存于a(1:arrsize)的前elenum個分量中。（2）以單鏈表作存儲結(jié)構(gòu)。

[方法1]:在原頭結(jié)點后重新頭插一遍

[方法2]:可設(shè)三個同步移動的指針p,q,r，將q的后繼r改為p2.8假設(shè)兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個按元素值遞減有序的排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點空間存放表C.[提醒]：參P.28例2-1

voidmerge(LinkListA;LinkListB;LinkList*C){……

pa=A－>next;pb=B－>next;*C=A;(*C)－>next=NULL;

while(pa!=NULLpa=pa－>next;

smaller－>next=(*C)－>next;/*頭插法*/(*C)－>next=smaller;}else

{smaller=pb;pb=pb－>next;smaller－>next=(*C)－>next;(*C)－>next=smaller;}

while(pa!=NULL)

{smaller=pa;pa=pa－>next;smaller－>next=(*C)－>next;(*C)－>next=smaller;}

while(pb!=NULL)

{smaller=pb;pb=pb－>next;smaller－>next=(*C)－>next;(*C)－>next=smaller;}

LinkListmerge(LinkListA;LinkListB){……

LinkListC；

pa=A－>next;pb=B－>next;C=A;C－>next=NULL;…………returnC;while(pa||pb){

if(pa->datadata||!pb){

pc=pa;q=pa->next;pa->next=pre;pa=q;//將A的元素插入新表}else{

pc=pb;q=pb->next;pb->next=pre;pb=q;//將B的元素插入新表}

pre=pc;}

C=A;A->next=pc;//構(gòu)造新表頭}//reverse_merge

分析:本算法的思想是,按從小到大的順序依次把A和B的元素插入新表的頭部pc處,最終處理A或B的剩余元素.

2.9假設(shè)有一個循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點也無頭指針。已知s為指向鏈表某個結(jié)點的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點的前趨結(jié)點。

[提醒]：設(shè)指針p指向s結(jié)點的前趨的前趨，則p與s有何關(guān)