MOOC 数据结构(四川师范大学)1002206010 最新慕课完整章节测试答案

什么是数据结构

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);‌     ElemType x;‌     while(a[i]!='&' &&a