MOOC 数据结构(四川师范大学)1002206010 最新慕课完整章节测试答案
第1周
什么是数据结构
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: 错误
答案: 【 正确】
第2周
一元多项式的表示及相加
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】
第3周
栈
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