數(shù)據(jù)結(jié)構(gòu)（中國海洋大學(xué)）知到智慧樹章節(jié)測(cè)試課后答案2024年秋中國海洋大學(xué)

數(shù)據(jù)結(jié)構(gòu)（中國海洋大學(xué)）知到智慧樹章節(jié)測(cè)試課后答案2024年秋中國海洋大學(xué)第一章單元測(cè)試

圖書館的數(shù)目檢索系統(tǒng)采用

關(guān)系的數(shù)據(jù)結(jié)構(gòu)。

A:圖狀B:樹形C:集合D:線性

答案:線性

是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

A:數(shù)據(jù)B:數(shù)據(jù)結(jié)構(gòu)C:數(shù)據(jù)項(xiàng)D:數(shù)據(jù)元素

答案:數(shù)據(jù)結(jié)構(gòu)（

）是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。

A:數(shù)據(jù)類型B:數(shù)據(jù)結(jié)構(gòu)C:數(shù)據(jù)項(xiàng)D:數(shù)據(jù)元素

答案:數(shù)據(jù)類型算法的確定性是指

（

）

A:當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能作出反應(yīng)或進(jìn)行處理B:算法中沒有邏輯錯(cuò)誤C:算法中的每一條指令必須有確切的含義D:在任何情況下，算法不會(huì)出現(xiàn)死循環(huán)

答案:算法中的每一條指令必須有確切的含義

第二章單元測(cè)試

線性表中的數(shù)據(jù)元素有一個(gè)前驅(qū)多個(gè)后繼。

A:錯(cuò)B:對(duì)

答案:錯(cuò)用順序結(jié)構(gòu)存儲(chǔ)，刪除最后一個(gè)結(jié)點(diǎn)時(shí)，（

）

A:一定不會(huì)移動(dòng)其它結(jié)點(diǎn)位置B:可能會(huì)移動(dòng)其它結(jié)點(diǎn)位置C:其它D:會(huì)移動(dòng)其它結(jié)點(diǎn)位置

答案:一定不會(huì)移動(dòng)其它結(jié)點(diǎn)位置鏈表中邏輯上相鄰的元素的物理地址__________相鄰。

A:一定不B:不一定C:其它D:必定

答案:不一定1.假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序(即非遞增有序，允許表中含有值相同的元素)排列的線性表C，并要求利用原表(即A表和B表)的結(jié)點(diǎn)空間構(gòu)造C表。//將合并逆置后的結(jié)果放在C表中，并刪除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){

LinkListpa,pb,qa,qb;

pa=A;

pb=B;

qa=pa;

//保存pa的前驅(qū)指針

qb=pb;

//保存pb的前驅(qū)指針

pa=pa->next;

pb=pb->next;

A->next=NULL;

C=A;

while(pa&&pb){

if(pa->data<pb->data){

qa=pa;

pa=pa->next;

qa->next=A->next;

//將當(dāng)前最小結(jié)點(diǎn)插入A表表頭

A->next=qa;

}

else{

qb=pb;

pb=pb->next;

(

)//將當(dāng)前最小結(jié)點(diǎn)插入B表表頭

A->next=qb;

}

}

while(pa){

qa=pa;

pa=pa->next;

qa->next=A->next;

A->next=qa;

}

while(pb){

qb=pb;

pb=pb->next;

qb->next=A->next;

A->next=qb;

}

pb=B;

free(pb);

returnOK;}

A:qb->next=A->nextB:qa->next=A;C:qb->next=A;D:qa->next=A->next

答案:qb->next=A->next假設(shè)某個(gè)單向循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。StatusListDelete_CL(LinkList&S){

LinkListp,q;

if(S==S->next)returnERROR;

q=S;

p=S->next;

while(

){

q=p;

p=p->next;

}

q->next=p->next;

free(p);

returnOK;}

A:p!=SB:p->next==SC:p->next!=SD:p==S

答案:p->next!=S

第三章單元測(cè)試

若以S和X分別表示進(jìn)棧和退棧操作，則對(duì)初始狀態(tài)為空的?？梢赃M(jìn)行的棧操作系列合法的是（

）；

A:SXSXXSSXB:SXXSXSSXC:SXSSXXXXD:SSSXXSXX

答案:SSSXXSXX設(shè)計(jì)一個(gè)迷宮求解的算法，采用___________數(shù)據(jù)結(jié)構(gòu)最佳。

A:棧B:隊(duì)列C:線性表的順序存儲(chǔ)結(jié)構(gòu)D:線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

答案:棧循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m-1],則出隊(duì)時(shí)的操作為（

）

A:front=(frontmodm)+1B:front=front+1C:front=(front+1)modmD:front=(front+1)mod(m-1)

答案:front=(front+1)modm1.試寫一個(gè)算法，識(shí)別依次讀入的一個(gè)以@為結(jié)束符的字符序列是否為形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a(chǎn)+b&b+a’是屬該模式的字符序列，而‘1+3&3-1’則不是。BOOLSymmetry(chara[]){

inti=0;

Stacks;

InitStack(s);

ElemTypex;

while(a[i]!='&'&&a[i]){

_________

i++;

}

if(!a[i])returnFALSE;

i++;

while(a[i]){

Pop(s,x);

if(x!=a[i]){

DestroyStack(s);

returnFALSE;

}

i++;

}

returnTRUE;}

A:Pop(s,a[i])B:Push(s,a[i++])C:Pop(s,a[i++])D:Push(s,a[i])

答案:Push(s,a[i])Status

SymmetryString(char*

p){Queue

q;if(!InitQueue(q))

return

0;Stack

s;InitStack(s);ElemType

e1,e2;while(*p){Push(s,*p);EnQueue(q,*p);p++;}while(!StackEmpty(s)){

(

)

DeQueue(q,e2);if(e1!=e2)

return

FALSE;}return

OK;}

A:P--P--P--P--P--P--P--P--B:Pop(s,e1);C:Push(s,*p);D:EnQueue(q,*p)

答案:Pop(s,e1);

第四章單元測(cè)試

設(shè)s=’IAMASTUDENT’,t=’GOOD’,則Concat(Substring(s,6,2),Concat(t,SubString(s,7,8)))=(

)

A:AGOODWORKERB:STGOODSTUDENTC:AGOODSTUDENTD:AGOODWORKER

答案:AGOODSTUDENT空串與空格串是相同的，這種說法____。

A:不正確B:正確

答案:不正確設(shè)串sl=″DataStructureswithJava″,s2=“it″，則子串定位函數(shù)index(s1,s2)的值為（）；

A:15B:17C:16D:18

答案:18串的長度是指（

）

A:串中所含字符的個(gè)數(shù)B:串中所含非空格字符的個(gè)數(shù)C:串中所含不同字符的個(gè)數(shù)D:串中所含不同字母的個(gè)數(shù)

答案:串中所含字符的個(gè)數(shù)串是一種數(shù)據(jù)對(duì)象和操作都特殊的線性表。

A:對(duì)B:錯(cuò)

答案:對(duì)

第五章單元測(cè)試

數(shù)組A中，每個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是______。

A:80B:270C:240D:100

答案:240假設(shè)有二維數(shù)組A6×8，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置為1000，計(jì)算數(shù)組A按行存儲(chǔ)時(shí)元素A[14]第一個(gè)字節(jié)的位置（

）；

A:1018B:1024C:1030D:1072

答案:1072若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣,只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換,就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算,這種觀點(diǎn)（

）。

A:正確B:錯(cuò)誤

答案:錯(cuò)誤廣義表（（（））,a,((b,c),(),d),(((e)))）的長度為（

）；

A:4B:3C:5D:2

答案:4下面說法不正確的是(

)。

A:廣義表可以是一個(gè)多層次的結(jié)構(gòu)B:廣義表的表尾總是一個(gè)廣義表C:廣義表的表頭總是一個(gè)廣義表D:廣義表難以用順序存儲(chǔ)結(jié)構(gòu)

答案:廣義表的表頭總是一個(gè)廣義表1.試按教科書5.5節(jié)圖5.10所示的結(jié)點(diǎn)結(jié)構(gòu)編寫復(fù)制廣義表的遞歸算法。//由廣義表L復(fù)制廣義表TintCopyGList(GList&T,GList&L){

if(!L)T=NULL;

else{

T=newGLNode;

if(!T)exit(OVERFLOW);

T->tag=L->tag;

if(L->tag==ATOM)T->atom=L->atom;

else{

________

CopyGList(T->tp,L->tp);

}

}

returnOK;}

A:CopyGList(T->hp,L->hp);B:A.CopyGList(T,L)C:CopyGList(L->hp,T->hp)D:CopyGList(L->tp,T->tp);

答案:CopyGList(T->hp,L->hp);

第六章單元測(cè)試

已知一棵樹邊的集合為{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>},問這棵樹中結(jié)點(diǎn)G的雙親結(jié)點(diǎn)為(

)

A:CB:BC:ID:A

答案:C一棵二叉樹中，葉子的個(gè)數(shù)為10，則其度為2的結(jié)點(diǎn)的個(gè)數(shù)為(

)；

A:10B:9C:11D:12

答案:9假如一棵二叉樹的中序遍歷結(jié)果為ABCD，則結(jié)點(diǎn)A和結(jié)點(diǎn)D的關(guān)系一定不是（

）；

A:結(jié)點(diǎn)A是結(jié)點(diǎn)D的左子樹上的結(jié)點(diǎn)B:結(jié)點(diǎn)A與結(jié)點(diǎn)D具有共同的雙親的右子樹上的結(jié)點(diǎn)C:結(jié)點(diǎn)A是結(jié)點(diǎn)D的雙親結(jié)點(diǎn)D:結(jié)點(diǎn)A是結(jié)點(diǎn)D的右子樹上的結(jié)點(diǎn)

答案:結(jié)點(diǎn)A是結(jié)點(diǎn)D的右子樹上的結(jié)點(diǎn)已知一棵樹邊的集合為{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>},將此樹轉(zhuǎn)化為二叉樹后，E的左孩子為（

）；

A:AB:IC:CD:B

答案:I一棵哈夫曼樹有17個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)的個(gè)數(shù)是

_________。

A:7B:8C:10D:9

答案:9寫遞歸算法，將二叉樹中所有結(jié)點(diǎn)的左、右子樹相互交換。StatusExchangeBiTree(BiTree&T){

BiTreep;

if(T){

p=T->lchild;

T->lchild=T->rchild;

T->rchild=p;

ExchangeBiTree(T->lchild);

__________

}

returnOK;}

A:A.ExchangeBiTree(p);B:ExchangeBiTree(T->rchild);C:ExchangeBiTree(T->lchild->rchild)D:ExchangeBiTree(T);

答案:ExchangeBiTree(T->rchild);試寫一個(gè)算法，為一棵二叉樹建立后序線索二叉樹。StatusPostOrderThreading(BiThrTree&T,BiThrTree&pre);//首先建立后序線索樹StatusFindNextInBiThrTree(BiThrTree&q,TElemType*p);//再進(jìn)行查找

//后序線索二叉樹的算法StatusPostOrderThreading(BiThrTree&Thrt,BiThrTree&T){

BiThrTreepre;

Thrt=newBiThrNode;//為線索二叉樹建立頭結(jié)點(diǎn)

if(!Thrt)exit(OVERFLOW);

Thrt->LTag=Link;

Thrt->RTag=Thread;

Thrt->rchild=Thrt;//右子樹回指

if(!T)Thrt->lchild=Thrt;//若二叉樹空，左子樹回指

else{

Thrt->lchild=T;

pre=Thrt;

PostThreading(T,pre);//后序遍歷進(jìn)行后序線索化

pre->rchild=Thrt;//最后一個(gè)結(jié)點(diǎn)線索化

pre->RTag=Thread;

Thrt->rchild=pre;

}

returnOK;}

StatusPostThreading(BiThrTree&T,BiThrTree&pre){

if(T){

if(T->LTag==Link)PostThreading(T->lchild,pre);

if(T->RTag==Link)PostThreading(T->rchild,pre);

if(!T->lchild){

T->LTag=Thread;

___________

}

if(pre&&!pre->rchild){

pre->RTag=Thread;

pre->rchild=T;

}

pre=T;

}

returnOK;}

A:T->lchild=pre;B:pre->lchild=TC:T->rchild=preD:pre->rchild=T

答案:T->lchild=pre;1.編寫遞歸算法，將二叉樹中所有結(jié)點(diǎn)的左、右子樹相互交換。StatusExchangeBiTree(BiTree&T){

BiTreep;

if(T){

p=T->lchild;

T->lchild=T->rchild;

T->rchild=p;

ExchangeBiTree(T->lchild);

}

returnOK;}

A:ExchangeBiTree(T->lchild->rchild);B:ExchangeBiTree(T);C:ExchangeBiTree(p);D:ExchangeBiTree(T->rchild);

答案:ExchangeBiTree(T->rchild);

第七章單元測(cè)試

下圖中結(jié)點(diǎn)B的出度為(

)

A:2B:1C:0D:3

答案:1對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖,若采用鄰接矩陣表示,則該矩陣的大小為（

）；

A:n×(n+1)B:(n-1)×nC:(n-1)×(n-1)D:n×n

答案:n×n采用鄰接表存儲(chǔ)的圖的寬度優(yōu)先遍歷算法類似于二叉樹的（

）。

A:中序遍歷B:先序遍歷C:層次遍歷D:后序遍歷

答案:層次遍歷下面的無向帶權(quán)圖的最小生成樹包含的邊有(

)

A:aeebbccddfegB:aegegfebbccdC:aggffddccbbeD:aeeddccbegdf

答案:aeeddccbegdf判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?還可以利用（

）；

A:寬度優(yōu)先遍歷算法B:求關(guān)鍵路徑的方法C:求最短路徑的Dijkstm方法D:深度優(yōu)先遍歷算法

答案:深度優(yōu)先遍歷算法編寫算法實(shí)現(xiàn)建立圖的鄰接表

StatusCreateAG(ALGraph&G){

intn,e,k,i,j;

cout<<"請(qǐng)輸入頂點(diǎn)數(shù)：";

cin>>n;

cout<<"請(qǐng)輸入邊數(shù)：";

cin>>e;

G.vernum=n;

G.arcnum=e;

//建立頂點(diǎn)數(shù)組

for(k=0;k<G.vernum;k++){

cout<<"請(qǐng)輸入頂點(diǎn)信息：";

cin>>G.vertices[k].data;

G.vertices[k].firstarc=NULL;

}

//建立鄰接表

VertexTypev1,v2;

ArcNode*p,*q;

for(k=0;k<G.arcnum;k++){

cout<<"請(qǐng)輸入弧的始點(diǎn)和終點(diǎn)信息，中間用空格分開:";

cin>>v1>>v2;

i=LocateVex(G,v1);

if(i<0||i>G.vernum-1)returnERROR;

j=LocateVex(G,v2);

if(j<0||j>G.vernum-1)returnERROR;

if(i==j)returnERROR;

p=newArcNode;

if(!p)returnERROR;

p->adjvex=j;

p->nextarc=NULL;

q=G.vertices[i].firstarc;

if(!q)G.vertices[i].firstarc=p;

else{

while(q->nextarc)__________

//指針定位于鄰接表的尾結(jié)點(diǎn)

q->nextarc=p;

}

}

returnOK;}

A:p=p->nextarc;B:q->nextarc=NULL;C:q=q->nextarcD:q->nextarc=p->nextarc

答案:q=q->nextarc編寫算法實(shí)現(xiàn)從鄰接表中取出某個(gè)頂點(diǎn)V的存儲(chǔ)位置。intLocateVex(ALGraph&G,VertexTypev){

inti=0;

while(______&&i<G.vernum)i++;

if(G.vertices[i].data==v)returni;

elsereturn-1;}

A:G.vertices[++i].data!=vB:G.vertices[i].data==vC:G.vertices[i].data!=vD:A.G.vertices[i++].data!=v

答案:G.vertices[i].data!=v

第八章單元測(cè)試

1.對(duì)線性表進(jìn)行二分查找時(shí),要求線性表必須（

）。

A:以順序方式存儲(chǔ)B:以鏈接方式存儲(chǔ)C:以鏈接方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序D:以順序方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序

答案:以順序方式存儲(chǔ),且結(jié)點(diǎn)按關(guān)鍵字有序排序

2.下列描述中不符合二叉排序樹特點(diǎn)的是

(

)

A:根結(jié)點(diǎn)的關(guān)鍵字大于左、右子樹中所有結(jié)點(diǎn)的關(guān)鍵字B:關(guān)鍵字插入的順序影響二叉排序樹的形態(tài)C:右字樹中所有結(jié)點(diǎn)的關(guān)鍵字大于根節(jié)點(diǎn)的關(guān)鍵字C．D:左子樹中所有結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān)鍵字

答案:根結(jié)點(diǎn)的關(guān)鍵字大于左、右子樹中所有結(jié)點(diǎn)的關(guān)鍵字

3.設(shè)哈希表長m=14，哈希函數(shù)H(key)=key%11。表中已有4個(gè)結(jié)點(diǎn)：

addr(15)=4;

addr(38)=5;

addr(61)=6;

addr(84)=7

如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是(

)

A:8B:5C:3D:9

答案:9

4.試將折半查找的算法改寫成遞歸算法。

Int

bisearch

(sqlistL,intlow,inthigh

,

elemtypex

)

{

If(low>high)

return(

0

);

else

{

if(L.data[mid]=

=x)

return

(mid);

elseif

(L.data[mid]>x)

bisearch(L,low,mid-1,x);

else

bisearch(L,mid+1,high,x);

}

}//bisearch

A:mid!=(low+high);B:mid=(low+high)/2C:A.mid<

(low+high)/2D:mid>(low+high)/2;

答案:mid=(low+high)/25.設(shè)計(jì)算法判定給定二叉樹是否為二叉排序樹。

voidBSTree(BiTreet,int&flag,int&last);//聲明StatusIsBSTree(BiTreet){

intflag=1;

intlast=0;

BSTree(t,flag,last);

returnflag;}voidBSTree(BiTreet,int&flag,int&last)//取地址不需要返回值{

if(t->lchild&&flag)BSTree(t->lchild,flag,last);//遍歷左子樹

if(t->data.key>last&&flag)

last=t->data.key;elseflag=0;//last原為父節(jié)點(diǎn)值，但到了樹葉節(jié)點(diǎn)后被樹葉節(jié)點(diǎn)的key值覆蓋，然后開始向上反饋keyif(t->rchild&&flag)

}

A:BSTree(t->rchild,last,flag);

B:BSTree(t->lchild,last,flag);

C:BSTree(t->rchild,flag,last);D:BSTree(t->lchild,flag,last);

答案:BSTree(t->rchild,flag,last);

m階B_樹中的m是指？

A:m階B_樹的深度（或高度）B:每個(gè)結(jié)點(diǎn)至少有m棵子樹C:非終端結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)D:每個(gè)結(jié)點(diǎn)至多有m棵子樹

答案:每個(gè)結(jié)點(diǎn)至多有m棵子樹

第九章單元測(cè)試

1.設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（

）。

A:45，40，15，20B:15，20，40，45C:40，50，20，95D:15，40，60，20

答案:15，40，60，20

2.快速排序方法在情況下最不利于發(fā)揮其長處。(

)

A:要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)B:要排序的數(shù)據(jù)已基本有序C:要排序的數(shù)據(jù)量太大。D:要排序的數(shù)據(jù)中含有多個(gè)相同值

答案:要排序的數(shù)據(jù)已基本有序

一組記錄的排序碼為(46,79,56,38,40,84),則利用堆排序的方法建立的初始推為（

）。

A:84,56,79,40,46,38B:79,46,56,38,40,80C:84,79,56,38,40,46D:84,79,