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

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

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

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

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

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

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

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

3.在高級(jí)語(yǔ)言（如C或PASCAL）中，指針類型是原子類型。（）三、計(jì)算以下程序段中X=X+1的語(yǔ)句頻度f(wàn)or(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個(gè)元素開(kāi)始的k個(gè)元素。[提醒]：注意檢查i和k的合法性。（集體搬遷，“新屋〞、“舊房〞）

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

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

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

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

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

StatusDelete_Between(Linklist

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

q=p->next;

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

}//Delete_Between

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

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

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

[方法2]:可設(shè)三個(gè)同步移動(dòng)的指針p,q,r，將q的后繼r改為p2.8假設(shè)兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法，將A表和B表歸并成一個(gè)按元素值遞減有序的排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點(diǎn)空間存放表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è)有一個(gè)循環(huán)鏈表的長(zhǎng)度大于1，且表中既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。已知s為指向鏈表某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前趨結(jié)點(diǎn)。

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