大学MOOC 数据结构(中国海洋大学)70004 最新慕课完整章节测试答案

什么是数据结构

1、单选题：
‎多叉路口交通灯的管理问题，采用（    ）关系的数据结构。  ‏‎‏
选项：
A: 集合
B: 线性 
C: 树形 
D: 图状
答案: 【 图状】

基本概念和术语

1、单选题：
​（ ）   是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。‍​‍​‍
选项：
A: 数据
B: 数据元素
C: 数据项
D: 数据对象
答案: 【 数据元素】

抽象数据类型的表示与实现

1、单选题：
​（ ）是一个值的集合和定义在这个值集上的一组操作的总称。​​​​​
选项：
A: 数据类型
B: 数据结构
C: 抽象数据类型
D: 数据对象
答案: 【 数据类型】

第1章测验

1、单选题：
​图书馆的数目检索系统采用  关系的数据结构‎
选项：
A: 集合
B: 线性
C: 树形
D: 图状
答案: 【 线性】

2、单选题：
     是相互之间存在一种或多种特定关系的数据元素的集合。‎
选项：
A: 数据
B: 数据元素
C: 数据项
D: 数据结构
答案: 【 数据结构】

3、单选题：
   是一个值的集合和定义在这个值集上的一组操作的总称。‍
选项：
A: 数据类型
B: 数据元素
C: 数据项
D: 数据结构
答案: 【 数据类型】

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

算法和算法分析

1、单选题：
‍ 算法的健壮性是指 （）‏
选项：
A: 当输入数据非法时，算法也能作出反应或进行处理
B: 在任何情况下，算法不会出现死循环
C: 算法的执行效率高
D: 算法中没有逻辑错误
答案: 【 当输入数据非法时，算法也能作出反应或进行处理】

2、单选题：
​当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。是指算法的（ ）‎
选项：
A: 健壮性 
B: 正确性
C: 有穷性 
D: 可读性
答案: 【 健壮性 】

3、单选题：
‏语句 for(i=1;i<=n;++i)  ++x; 的时间复杂可表示为：（） ​
选项：
A:  O(n+1) 
B: O(n)
C: O(n*n)
D: O(n-1)
答案: 【 O(n)】

4、判断题：
‎空间复杂度作为算法所需存储空间的量度，只需要分析该算法在实现时所需要的辅助空间单元个数就可以，无需考虑算法本身所占的存储空间。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

一元多项式的表示及相加

1、填空题：
‍一元多项式的表示及相加采用（）存储结构。‏
答案: 【 链表】

第2章测验

1、单选题：
用顺序结构存储，删除最后一个结点时（ ）​
选项：
A: 会移动其它结点位置 
B: 一定不会移动其它结点位置
C: 可能会移动其它结点位置
D: 其它
答案: 【 一定不会移动其它结点位置】

2、单选题：
链表中逻辑上相邻的元素的物理地址    相邻。‌
选项：
A: 必定  
B: 不一定
C: 一定不
D: 其它
答案: 【 不一定】

3、判断题：
​线性表中的数据元素有一个前驱多个后继‏
选项：
A: 正确
B: 错误
答案: 【 错误】

4、填空题：
假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。​// 将合并逆置后的结果放在C表中，并删除B表​​Status ListMergeOppose_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->next=qa;​          } else{​               qb=pb;​               pb=pb->next;​                            //将当前最小结点插入A表表头​               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;​}​
答案: 【 qb->next=A->next;】

5、填空题：
假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。‍Status ListDelete_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;‍}‍
答案: 【 p->next!=s】

线性表的类型定义

1、判断题：
​线性表中的数据元素除最后一个元素之外都只有一个后继。​
选项：
A: 正确
B: 错误
答案: 【 正确】

线性表的链式表示和实现

1、单选题：
‍线性表采用链式存储结构时，其地址（ ）。 ‌
选项：
A: 必须是连续的
B: 部分地址必须是连续的 
C: 一定是不连续的
D: 连续与否均可以 
答案: 【 连续与否均可以 】

2、单选题：
‌带头结点的循环单链表中空链表的判定条件是 （  ）‌
选项：
A: head == NULL 
B: head->next == head 
C: head->next == NULL  
D: head != NULL
答案: 【 head->next == head 】

3、单选题：
‍在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。 ‏
选项：
A: p->prior=q;q->next=p;p->prior-next=q;q->prior=q； 
B: p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;
C: q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;
D: q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;
答案: 【 q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;】

线性表的顺序表示和实现

1、单选题：
‏在长度为n的顺序表的第i个位置上插入一个元素(1<=i<=n+1)，元素的移动次数为：（)‌
选项：
A: n-i+1
B: n-i 
C: i
D: i-1
答案: 【 n-i+1】

栈

1、单选题：
‌已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（　）‌
选项：
A: 5，4，3，2，1，6   
B: 2，3，5，6，1，4
C: 3，2，5，4，1，6
D: 1，4，6，5，2，3
答案: 【 3，2，5，4，1，6】

2、单选题：
​在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为(  )‎
选项：
A:  top++
B: top-- 
C: top不变
D: top=0
答案: 【 top-- 】

栈的应用举例

1、单选题：
‍数制转换采用（）结构来实现。​
选项：
A: 栈 
B: 队列  
C: 链表
D: 顺序表
答案: 【 栈 】

2、单选题：
‌在判别一个表达式中左、右括号是否配对出现的算法，采用（）数据结构最佳。‌
选项：
A: 线性表的顺序存储结构  
B: 队列
C: 线性表的链式存储结构
D: 栈
答案: 【 栈】

3、单选题：
‎4.表达式a*(b+c)-d的后缀表达式是（ ）。​
选项：
A: abcd*+-
B: abc+*d- 
C: abc*+d-
D: -+*abcd
答案: 【 abc+*d- 】

4、判断题：
‌假设从终端接受了这样一行字符：whli##ilr#e（s#*s)，实际有效的是while (*ss)。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

栈的递归实现

1、单选题：
‏一个递归算法必须包括（  ）。‏
选项：
A: 递归部分
B: 终止条件和递归部分
C: 迭代部分
D: 终止条件和迭代部分
答案: 【 终止条件和递归部分】

离散事件模拟

1、单选题：
‏在离散事件的模拟中，（）采用队列结构来实现。‌
选项：
A: 到达事件和离开事件 
B: 每个窗口的客户
C: 其它
D: 空
答案: 【 每个窗口的客户】

第3章测验

1、单选题：
​在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ）‎
选项：
A: front==rear
B: (front+1)%m==rear
C: rear+1==front
D: (rear+1)%m==front
答案: 【 (rear+1)%m==front】

2、单选题：
​若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（  ）​
选项：
A: SXSSXXXX
B: SXXSXSSX 
C: SXSXXSSX
D: SSSXXSXX
答案: 【 SSSXXSXX】

3、单选题：
‎设计一个迷宫求解的算法，采用     数据结构最佳。‌
选项：
A: 线性表的顺序存储结构
B: 栈
C: 队列
D: 线性表的链式存储结构
答案: 【 栈】

4、单选题：
‍循环队列存储在数组A[0..m-1],则出队时的操作为（ ）‍
选项：
A: front=front+1
B: front=(front+1)mod (m-1)
C: ront=(front+1)mod m
D: front=(front mod m)+1
答案: 【 ront=(front+1)mod m】

5、填空题：
试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。‌BOOL Symmetry(char a[]){‌     int i=0;‌     Stack s;‌     InitStack(s);‌ &nbsp