2021知到答案数据结构（中国海洋大学版）最新智慧树满分章节测试答案

第一章单元测试

1、单选题：

图书馆的数目检索系统采用关系的数据结构。

选项：
A:集合
B:线性
C:树形
D:图状
答案: 【线性】

2、单选题：

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

选项：
A:数据
B:数据元素
C:数据项
D:数据结构
答案: 【数据结构】

3、单选题：

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

选项：
A:数据类型
B:数据元素
C:数据项
D:数据结构
答案: 【数据类型】

4、单选题：
算法的确定性是指（）
选项：
A:当输入数据非法时，算法也能作出反应或进行处理
B:在任何情况下，算法不会出现死循环
C:算法中的每一条指令必须有确切的含义
D:算法中没有逻辑错误
答案: 【算法中的每一条指令必须有确切的含义】

第二章单元测试

1、单选题：

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

选项：
A:对
B:错
答案: 【错】

2、单选题：

用顺序结构存储，删除最后一个结点时，（）

选项：
A:会移动其它结点位置
B:一定不会移动其它结点位置
C:可能会移动其它结点位置
D:其它
答案: 【一定不会移动其它结点位置】

3、单选题：

链表中逻辑上相邻的元素的物理地址__________相邻。

选项：
A:必定
B:不一定
C:一定不
D:其它
答案: 【不一定】

4、单选题：

1.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。

//将合并逆置后的结果放在C表中，并删除B表

StatusListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)

{

LinkList pa,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);

return OK;

}

选项：
A:qa->next=A->next
B:qb->next=A->next
C:qa->next=A;
D:qb->next=A;
答案: 【qb->next=A->next】

5、单选题：

假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。

StatusListDelete_CL(LinkList &S)

{

LinkList p,q;

if(S==S->next)return ERROR;

q=S;

p=S->next;

while( ){

q=p;

p=p->next;

}

q->next=p->next;

free(p);

return OK;

}

选项：
A:p->next!=S
B:p->next==S
C:p!=S
D:p==S
答案: 【p->next!=S】

第三章单元测试

1、单选题：

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

选项：
A:SXSSXXXX
B: SXXSXSSX
C:SXSXXSSX
D: SSSXXSXX
答案: 【 SSSXXSXX】

2、单选题：

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

选项：
A:线性表的顺序存储结构
B:栈
C:队列
D:线性表的链式存储结构
答案: 【栈】

3、单选题：

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

选项：
A:front=front+1
B:front=(front+1)mod (m-1)
C:front=(front+1)mod m
D:front=(front mod m)+1
答案: 【front=(front+1)mod m 】

4、单选题：

1.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列₁&序列₂’模式的字符序列。其中序列₁和序列₂中都不含字符‘&’，且序列₂是序列₁的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。

BOOLSymmetry(char a[])

{

int i=0;

Stack s;

InitStack(s);

ElemType x;

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

_________

i++;

}

if(!a[i]) return FALSE;

i++;

while(a[i]){

Pop(s,x);

if(x!=a[i]){

DestroyStack(s);

return FALSE;

}

i++;

}

return TRUE;

}

选项：
A:Pop(s,a[i++])
B:Push(s,a[i++])
C:Push(s,a[i])
D:Pop(s,a[i])
答案: 【Push(s,a[i])】

5、单选题：

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:Pop(s,e1);
B:Push(s,*p);
C:EnQueue(q,*p)
D:P–P–P–P–P–P–P–P–
答案: 【Pop(s,e1);】

第四章单元测试

1、单选题：

设s=’I AM A STUDENT’ , t=’GOOD’ ,则Concat(Substring(s,6,2),Concat(t,SubString(s,7,8)))=( )

选项：
A: A GOODWORKER
B:ST GOODSTUDENT
C: A GOOD STUDENT
D:A GOOD WORKER
答案: 【 A GOOD STUDENT 】

2、单选题：
空串与空格串是相同的，这种说法____。
选项：
A:正确
B:不正确
答案: 【不正确】

3、单选题：

设串sl=″Data Structures with Java″,s2=“it″，则子串定位函数index(s1,s2)的值为（　　　）；

选项：
A:15
B:16
C:17
D:18
答案: 【18】

4、单选题：
串的长度是指（）

选项：
A:串中所含不同字母的个数
B:串中所含字符的个数
C:串中所含不同字符的个数
D:串中所含非空格字符的个数
答案: 【串中所含字符的个数】

5、判断题：
串是一种数据对象和操作都特殊的线性表。
选项：
A:对
B:错
答案: 【对】

第五章单元测试

1、单选题：
数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是______。
选项：
A:80
B:100
C:240
D:270
答案: 【240】

2、单选题：
假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置为1000，计算数组A按行存储时元素A[14]第一个字节的位置（）；
选项：
A:1018
B:1024
C:1030
D:1072
答案: 【1072】

3、单选题：

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

选项：
A:正确
B:错误
答案: 【错误】

4、单选题：

广义表（（（））,a,((b,c),(),d),(((e)))）的长度为（）；

选项：
A:3
B:4
C:5
D:2
答案: 【4】

5、单选题：
下面说法不正确的是 ( )。
选项：
A: 广义表的表头总是一个广义表
B:广义表的表尾总是一个广义表
C:广义表难以用顺序存储结构
D:广义表可以是一个多层次的结构
答案: 【广义表的表头总是一个广义表】

6、单选题：

1.试按教科书5.5节图5.10所示的结点结构编写复制广义表的递归算法。

// 由广义表L复制广义表T

intCopyGList(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);

}

return OK;

}

选项：
A:A.CopyGList(T,L)
B:CopyGList(L->tp,T->tp);
C:CopyGList(L->hp,T->hp)
D:CopyGList(T->hp,L->hp);
答案: 【CopyGList(T->hp,L->hp);】

第六章单元测试

1、单选题：
已知一棵树边的集合为{<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:A
B:C
C:I
D:B
答案: 【C】

2、单选题：

一棵二叉树中，叶子的个数为10，则其度为2的结点的个数为 ( ) ；

选项：
A:9
B:10
C:11
D:12
答案: 【9】

3、单选题：

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

选项：
A:结点A是结点D的双亲结点
B:结点A是结点D的右子树上的结点
C:结点A是结点D的左子树上的结点
D:结点A与结点D具有共同的双亲的右子树上的结点
答案: 【结点A是结点D的右子树上的结点】

4、单选题：

已知一棵树边的集合为{<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:A
B:C
C:I
D:B
答案: 【I】

5、单选题：
一棵哈夫曼树有17个结点，则其叶子结点的个数是 _________ 。
选项：
A:7
B:8
C:9
D:10
答案: 【9】

6、单选题：

写递归算法，将二叉树中所有结点的左、右子树相互交换。

Status ExchangeBiTree(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);】

7、单选题：

试写一个算法，为一棵二叉树建立后序线索二叉树。

StatusPostOrderThreading(BiThrTree& T,BiThrTree& pre);//首先建立后序线索树StatusFindNextInBiThrTree(BiThrTree& q,TElemType *p);//再进行查找

// 后序线索二叉树的算法

StatusPostOrderThreading(BiThrTree& Thrt,BiThrTree& T)

{

BiThrTree pre;

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

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;

}

return OK;

}

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;

}

return OK;

}

选项：
A:T->lchild=pre;
B:pre->lchild=T
C:T->rchild=pre
D:pre->rchild=T
答案: 【T->lchild=pre; 】

8、单选题：

1.编写递归算法，将二叉树中所有结点的左、右子树相互交换。

StatusExchangeBiTree(BiTree& T)

{

BiTree p;

if(T){

p=T->lchild;

T->lchild=T->rchild;

T->rchild=p;

ExchangeBiTree(T->lchild);

}

return OK;

}

选项：
A:ExchangeBiTree(p);
B: ExchangeBiTree(T->rchild);
C:ExchangeBiTree(T->lchild->rchild);
D:ExchangeBiTree(T);
答案: 【 ExchangeBiTree(T->rchild);】

第七章单元测试

1、单选题：

下图中结点B的出度为( )

选项：
A:0
B:1
C:2
D:3
答案: 【1】

2、单选题：

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

选项：
A:n ×n
B:(n-1)× (n-1)
C:(n-1)×n
D:n×(n+1)
答案: 【n ×n】

3、单选题：
采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。
选项：
A:先序遍历
B:中序遍历
C:后序遍历
D:层次遍历
答案: 【层次遍历】

4、单选题：

下面的无向带权图的最小生成树包含的边有( )

选项：
A:ae ge gf eb bc cd
B:ae ed dc cb eg df
C:ag gf fd dc cb be
D:ae eb bc cd df eg
答案: 【ae ed dc cb eg df 】

5、单选题：

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

选项：
A:求关键路径的方法
B:求最短路径的Dijkstm方法
C:宽度优先遍历算法
D:深度优先遍历算法
答案: 【深度优先遍历算法】

6、单选题：

编写算法实现建立图的邻接表

StatusCreateAG(ALGraph &G)

{

int n,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;

}

// 建立邻接表

VertexType v1,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) return ERROR;

j=LocateVex(G,v2);

if(j<0|| j>G.vernum-1) return ERROR; if(i==j)return ERROR; p=newArcNode; if(!p)return ERROR;

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;

}

return OK;

}

选项：
A:p=p->nextarc;
B:q->nextarc=NULL;
C:q->nextarc=p->nextarc
D:q=q->nextarc
答案: 【q=q->nextarc】

7、单选题：

编写算法实现从邻接表中取出某个顶点V的存储位置。

intLocateVex(ALGraph& G,VertexType v)

{

int i=0;

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

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

else return -1;

}

选项：
A:A.G.vertices[i++].data!=v
B:G.vertices[i].data!=v
C:G.vertices[i].data==v
D:G.vertices[++i].data!=v
答案: 【G.vertices[i].data!=v 】

第八章单元测试

1、单选题：
1. 对线性表进行二分查找时,要求线性表必须（）。
选项：
A: 以顺序方式存储
B:以链接方式存储
C:以顺序方式存储,且结点按关键字有序排序
D:以链接方式存储,且结点按关键字有序排序
答案: 【以顺序方式存储,且结点按关键字有序排序】

2、单选题：
2.下列描述中不符合二叉排序树特点的是 ( )
选项：
A:左子树中所有结点的关键字小于根结点的关键字
B:根结点的关键字大于左、右子树中所有结点的关键字
C:右字树中所有结点的关键字大于根节点的关键字C．
D:关键字插入的顺序影响二叉排序树的形态
答案: 【根结点的关键字大于左、右子树中所有结点的关键字】

3、单选题：
3.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点： addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7 如用二次探测再散列处理冲突，关键字为49的结点的地址是( )
选项：
A:8
B:3
C:5
D:9
答案: 【9】

4、单选题：
4.试将折半查找的算法改写成递归算法。 Int bisearch (sqlist L,int low, int high , elemtype x ) { If (low>high) return( 0 ); else { if (L.data[mid]= =x) return (mid); else if (L.data[mid]>x) bisearch(L,low,mid-1,x); else bisearch(L,mid+1,high,x);

}

}//bisearch
选项：
A:A. mid< (low+high)/2
B:mid=(low+high)/2
C:mid>(low+high)/2;
D:mid!=(low+high);
答案: 【mid=(low+high)/2】

5、单选题：
5.设计算法判定给定二叉树是否为二叉排序树。 void BSTree(BiTree t,int &flag,int &last);//声明

Status IsBSTree(BiTree t)

{

int flag = 1;

int last =0;

BSTree(t,flag,last);

return flag;

}

void BSTree(BiTree t,int &flag,int &last)//取地址不需要返回值

{

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

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

else flag=0;

//last原为父节点值，但到了树叶节点后被树叶节点的key值覆盖，然后开始向上反馈key

if(t->rchild&&flag)

}

选项：
A:BSTree(t->rchild,flag,last);
B:BSTree(t->lchild,flag,last);
C:BSTree(t->rchild,last,flag);
D:BSTree(t->lchild,last,flag);
答案: 【BSTree(t->rchild,flag,last);】

6、单选题：
m阶B_树中的m是指？
选项：
A:每个结点至少有m棵子树
B:每个结点至多有m棵子树
C:非终端结点中关键字的个数
D:m阶B_树的深度（或高度）
答案: 【每个结点至多有m棵子树】

第九章单元测试

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

选项：
A:40，50，20，95
B:15，40，60，20
C:15，20，40，45
D:45，40，15，20
答案: 【15，40，60，20】

2、单选题：
2.快速排序方法在情况下最不利于发挥其长处。( )
选项：
A:要排序的数据量太大。
B:要排序的数据中含有多个相同值
C:要排序的数据已基本有序
D:要排序的数据个数为奇数
答案: 【要排序的数据已基本有序】

3、单选题：
一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（）。
选项：
A:79,46,56,38,40,80
B:84,79,56,38,40,46
C:84,79,56,46,40,38
D:84,56,79,40,46,38
答案: 【84,79,56,38,40,46】

4、单选题：
设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。
选项：
A: 15，25，35，50，20，40，80，85，36，70
B:15，25，35，50，80，20，85，40，70，36
C:15，25，35，50，80，85，20，36，40，70
D: 15，25，35，50，80，20，36，40，70，85
答案: 【 15，25，35，50，20，40，80，85，36，70】

5、单选题：
试以L.r[k+1]作为监视哨改写教科书10.2.1节中给出的直接插入排序算法。其中，L.r[1..k]为待排序记录且k<MAXSIZE。

void InsertionSort ( SqList &L ) {

// 对顺序表 L 作直接插入排序。

for ( i=k-1-1; i>=1; –i )

{ if (L.r[i+1].key < L.r[i].key)

{

L.r[k+1] = L.r[i]; // 复制为监视哨

for ( j=i+1; L.r[k+1].key > L.r[j].key; ++ j )

L.r[j-1] = L.r[j]; // 记录前移

}//end if

}//end for

} // InsertSort

选项：
A:A.L.r[j+1] = L.r[k+1];
B:L.r[j] = L.r[k];
C:L.r[j] = L.r[k+1];
D:L.r[i] = L.r[k+1];
答案: 【L.r[j] = L.r[k+1]; 】

6、单选题：
1.编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：

(1)采用顺序存储结构，至多使用一个记录的辅助存储空间；

(2)算法的时间复杂度为O(n);void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前
{
low=0;high=n-1;
while( )
{
while(low<high&&a[high]>=0) high–; //以0作为虚拟的枢轴记录
a[low]<->a[high];
while(low<high&&a[low]<0) low++;
a[low]<->a[high];
}
}//Divide
选项：
A:low< =(high+1)
B:(low+1)< high
C:low!=high
D:low< high
答案: 【low< high 】

内容查看

查看价格5 元

VIP 8折升级VIP

立即购买

申请退款

点点赞赏，手留余香给TA打赏

AI创作

2021知到答案数据结构（中国海洋大学版）最新智慧树满分章节测试答案

第一章单元测试

第二章单元测试

评论0

返回顶部

站点公告

第一章 单元测试

第二章 单元测试

第三章 单元测试

第四章 单元测试

第五章 单元测试

第六章 单元测试

第七章 单元测试

第八章 单元测试

第九章 单元测试

评论0

返回顶部

站点公告

社交账号快速登录

社交账号快速登录

社交账号快速登录

第一章单元测试

第二章单元测试

第三章单元测试

第四章单元测试

第五章单元测试

第六章单元测试

第七章单元测试

第八章单元测试

第九章单元测试