数据结构（中国海洋大学）知到智慧树章节测试课后答案2024年秋中国海洋大学

数据结构（中国海洋大学）知到智慧树章节测试课后答案2024年秋中国海洋大学第一章单元测试

图书馆的数目检索系统采用

关系的数据结构。

A:图状B:树形C:集合D:线性

答案:线性

是相互之间存在一种或多种特定关系的数据元素的集合。

A:数据B:数据结构C:数据项D:数据元素

答案:数据结构（

）是一个值的集合和定义在这个值集上的一组操作的总称。

A:数据类型B:数据结构C:数据项D:数据元素

答案:数据类型算法的确定性是指

（

）

A:当输入数据非法时，算法也能作出反应或进行处理B:算法中没有逻辑错误C:算法中的每一条指令必须有确切的含义D:在任何情况下，算法不会出现死循环

答案:算法中的每一条指令必须有确切的含义

第二章单元测试

线性表中的数据元素有一个前驱多个后继。

A:错B:对

答案:错用顺序结构存储，删除最后一个结点时，（

）

A:一定不会移动其它结点位置B:可能会移动其它结点位置C:其它D:会移动其它结点位置

答案:一定不会移动其它结点位置链表中逻辑上相邻的元素的物理地址__________相邻。

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

答案:不一定1.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。//将合并逆置后的结果放在C表中，并删除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){

LinkListpa,pb,qa,qb;

pa=A;

pb=B;

qa=pa;

//保存pa的前驱指针

qb=pb;

//保存pb的前驱指针

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;

//将当前最小结点插入A表表头

A->next=qa;

}

else{

qb=pb;

pb=pb->next;

(

)//将当前最小结点插入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假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。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

第三章单元测试

若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（

）；

A:SXSXXSSXB:SXXSXSSXC:SXSSXXXXD:SSSXXSXX

答案:SSSXXSXX设计一个迷宫求解的算法，采用___________数据结构最佳。

A:栈B:队列C:线性表的顺序存储结构D:线性表的链式存储结构

答案:栈循环队列存储在数组A[0..m-1],则出队时的操作为（

）

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

答案:front=(front+1)modm1.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+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);

第四章单元测试

设s=’IAMASTUDENT’,t=’GOOD’,则Concat(Substring(s,6,2),Concat(t,SubString(s,7,8)))=(

)

A:AGOODWORKERB:STGOODSTUDENTC:AGOODSTUDENTD:AGOODWORKER

答案:AGOODSTUDENT空串与空格串是相同的，这种说法____。

A:不正确B:正确

答案:不正确设串sl=″DataStructureswithJava″,s2=“it″，则子串定位函数index(s1,s2)的值为（）；

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

答案:18串的长度是指（

）

A:串中所含字符的个数B:串中所含非空格字符的个数C:串中所含不同字符的个数D:串中所含不同字母的个数

答案:串中所含字符的个数串是一种数据对象和操作都特殊的线性表。

A:对B:错

答案:对

第五章单元测试

数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是______。

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

答案:240假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置为1000，计算数组A按行存储时元素A[14]第一个字节的位置（

）；

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

答案:1072若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（

）。

A:正确B:错误

答案:错误广义表（（（））,a,((b,c),(),d),(((e)))）的长度为（

）；

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

答案:4下面说法不正确的是(

)。

A:广义表可以是一个多层次的结构B:广义表的表尾总是一个广义表C:广义表的表头总是一个广义表D:广义表难以用顺序存储结构

答案:广义表的表头总是一个广义表1.试按教科书5.5节图5.10所示的结点结构编写复制广义表的递归算法。//由广义表L复制广义表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);

第六章单元测试

已知一棵树边的集合为{<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>},问这棵树中结点G的双亲结点为(

)

A:CB:BC:ID:A

答案:C一棵二叉树中，叶子的个数为10，则其度为2的结点的个数为(

)；

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

答案:9假如一棵二叉树的中序遍历结果为ABCD，则结点A和结点D的关系一定不是（

）；

A:结点A是结点D的左子树上的结点B:结点A与结点D具有共同的双亲的右子树上的结点C:结点A是结点D的双亲结点D:结点A是结点D的右子树上的结点

答案:结点A是结点D的右子树上的结点已知一棵树边的集合为{<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>},将此树转化为二叉树后，E的左孩子为（

）；

A:AB:IC:CD:B

答案:I一棵哈夫曼树有17个结点，则其叶子结点的个数是

_________。

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

答案:9写递归算法，将二叉树中所有结点的左、右子树相互交换。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);试写一个算法，为一棵二叉树建立后序线索二叉树。StatusPostOrderThreading(BiThrTree&T,BiThrTree&pre);//首先建立后序线索树StatusFindNextInBiThrTree(BiThrTree&q,TElemType*p);//再进行查找

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

BiThrTreepre;

Thrt=newBiThrNode;//为线索二叉树建立头结点

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);//后序遍历进行后序线索化

pre->rchild=Thrt;//最后一个结点线索化

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.编写递归算法，将二叉树中所有结点的左、右子树相互交换。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);

第七章单元测试

下图中结点B的出度为(

)

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

答案:1对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为（

）；

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

答案:n×n采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（

）。

A:中序遍历B:先序遍历C:层次遍历D:后序遍历

答案:层次遍历下面的无向带权图的最小生成树包含的边有(

)

A:aeebbccddfegB:aegegfebbccdC:aggffddccbbeD:aeeddccbegdf

答案:aeeddccbegdf判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（

）；

A:宽度优先遍历算法B:求关键路径的方法C:求最短路径的Dijkstm方法D:深度优先遍历算法

答案:深度优先遍历算法编写算法实现建立图的邻接表

StatusCreateAG(ALGraph&G){

intn,e,k,i,j;

cout<<"请输入顶点数：";

cin>>n;

cout<<"请输入边数：";

cin>>e;

G.vernum=n;

G.arcnum=e;

//建立顶点数组

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

cout<<"请输入顶点信息：";

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

G.vertices[k].firstarc=NULL;

}

//建立邻接表

VertexTypev1,v2;

ArcNode*p,*q;

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

cout<<"请输入弧的始点和终点信息，中间用空格分开:";

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)__________

//指针定位于邻接表的尾结点

q->nextarc=p;

}

}

returnOK;}

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

答案:q=q->nextarc编写算法实现从邻接表中取出某个顶点V的存储位置。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

第八章单元测试

1.对线性表进行二分查找时,要求线性表必须（

）。

A:以顺序方式存储B:以链接方式存储C:以链接方式存储,且结点按关键字有序排序D:以顺序方式存储,且结点按关键字有序排序

答案:以顺序方式存储,且结点按关键字有序排序

2.下列描述中不符合二叉排序树特点的是

(

)

A:根结点的关键字大于左、右子树中所有结点的关键字B:关键字插入的顺序影响二叉排序树的形态C:右字树中所有结点的关键字大于根节点的关键字C．D:左子树中所有结点的关键字小于根结点的关键字

答案:根结点的关键字大于左、右子树中所有结点的关键字

3.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：

addr(15)=4;

addr(38)=5;

addr(61)=6;

addr(84)=7

如用二次探测再散列处理冲突，关键字为49的结点的地址是(

)

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.设计算法判定给定二叉树是否为二叉排序树。

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原为父节点值，但到了树叶节点后被树叶节点的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:每个结点至少有m棵子树C:非终端结点中关键字的个数D:每个结点至多有m棵子树

答案:每个结点至多有m棵子树

第九章单元测试

1.设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（

）。

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

答案:15，40，60，20

2.快速排序方法在情况下最不利于发挥其长处。(

)

A:要排序的数据个数为奇数B:要排序的数据已基本有序C:要排序的数据量太大。D:要排序的数据中含有多个相同值

答案:要排序的数据已基本有序

一组记录的排序码为(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,