2017 数据结构(武汉大学) 最新大学MOOC满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2017-03-20到2017-07-07
本篇答案更新状态:已完结

【作业】第1周：绪论（时长：56分11秒） 第1周作业

1、 问题:有以下用C/C++语言描述的算法，说明其功能：void fun(double &y,double x,int n){ y=x; while (n>1) { y=y*x; n–; }}
评分规则: 【 参考答案：本算法的功能是计算y=。
】

2、 问题:一个算法的空间复杂度是O(1)，那么执行该算法时不需要任何空间，这个说法正确吗？为什么？
评分规则: 【 参考答案：这个说法是错误的。一个算法的空间复杂度是O(1)只是表明执行该算法时所需临时分配的空间大小是个常量，与问题规模无关，并不是不需要任何空间。回答是正确的，给0分。
】

3、 问题:一个算法的执行频度为，其时间复杂度多少？
评分规则: 【 参考答案：当n足够大时，T(n)®3n/10=0.3n，其时间复杂度为O(n)
】

4、 问题:设有算法如下：int Find(int a[], int n, int x){ int i; for (i=0;i 参考答案1：在最好情况下，a[0]=x，比较1次，所以最好时间复杂度为O(1)。
参考答案2：在最坏情况下，a[n-1]=x，比较n次，所以最坏时间复杂度为O(n)。
】

5、 问题:设有算法如下：int Find(ElemType a[ ],int s,int t,ElemType x){ int m=(s+t)/2; if (s<=t) { if (a[m]==x) return m; else if (x
】

第1周：绪论（时长：56分11秒） 第1周测验

1、 问题:计算机所处理的数据一般具备某种内在联系，这是指（ ）。
选项：
A:数据和数据之间存在某种关系
B:元素和元素之间存在某种关系
C:元素内部具有某种结构
D:数据项和数据项之间存在某种关系
答案: 【元素和元素之间存在某种关系】

2、 问题:在数据结构中，与所使用的计算机无关的是数据的（ ）结构。
选项：
A:逻辑
B:存储
C:逻辑和存储
D:物理
答案: 【逻辑】

3、 问题:在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。
选项：
A:数据的处理方法
B:数据元素的类型
C:数据元素之间的关系
D:数据的存储方法
答案: 【数据元素之间的关系】

4、 问题:数据结构在计算机内存中的表示是指（ ）。
选项：
A:数据的存储结构
B:数据结构
C:数据的逻辑结构
D:数据元素之间的关系
答案: 【数据的存储结构】

5、 问题:数据在计算机的存储器中表示时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称之为（ ）。
选项：
A:逻辑结构
B:顺序存储结构
C:链式存储结构
D:以上都对
答案: 【顺序存储结构】

6、 问题:数据采用链式存储结构时，要求（ ）。
选项：
A:每个节点占用一片连续的存储区域
B:所有节点占用一片连续的存储区域
C:节点的最后一个域必须是指针域
D:每个节点有多少后继节点，就必须设多少个指针域
答案: 【每个节点占用一片连续的存储区域】

7、 问题:可以用（ ）定义一个完整的数据结构。
选项：
A:数据元素
B:数据对象
C:数据关系
D:抽象数据类型
答案: 【抽象数据类型】

8、 问题:算法指的是（ ）。
选项：
A:计算机程序
B:解决问题的方法
C:查找或排序过程
D:求解特定问题的指令有限序列
答案: 【求解特定问题的指令有限序列】

9、 问题:在算法设计时，若实参和形参同步发生改变，则应把形参变量说明为（ ）型参数。
选项：
A:指针
B:引用
C:传值
D:常数
答案: 【引用】

10、 问题:某算法的时间复杂度为O()，表明该算法的（ ）。
选项：
A:问题规模是
B:执行时间等于
C:执行时间与成正比
D:问题规模与成正比
答案: 【执行时间与成正比】

【作业】第2周：线性表（上）（时长：1小时3分56秒） 第2周作业

1、 问题:设计一个算法，查找非空顺序表L中第一个最大的元素，并返回该元素的逻辑序号。
评分规则: 【 参考答案：采用顺序表指针方式：int MaxFirst(SqList *L){ int i,maxi=0; for (i=1;ilength;i++) if (L->data[i]>L->data[maxi]) maxi=i; return maxi+1;}或者直接采用顺序表方式：int MaxFirst(SqList L){ int i,maxi=0; for (i=1;iL.data[maxi]) maxi=i; return maxi+1;}
】

2、 问题:对于带头节点的单链表L1，其节点类型为LinkList，指出以下算法的功能。void fun(LinkList &L，ElemType x，ElemType y){ LinkList p=L->next; while (p!=NULL) { if (p->data==x) p->data=y; p=p->next; }}
评分规则: 【 参考答案：将单链表L中所有值为x的节点的值替换成y。
】

3、 问题:以下算法用于统计带头节点的单链表L中节点值等于给定值x的节点数的算法，其中存在错误，请指出错误的地方并修改为正确的算法。int count(LinkList L,ElemType x){ int n=0; while (L!=NULL) { L=L->next; if (L->data==x) n++; } return n;}
评分规则: 【 参考答案：当L指向尾节点时，while条件成立，再执行L=L->next，L=NULL，此时if语句出现错误。修改后的算法如下：int count(LinkList L,ElemType x){ LinkList *p=L->next; int n=0; while (p!=NULL) { if (p->data==x) n++; p=p->next; } return n;}
】

4、 问题:某非空单链表L中所有元素为整数，设计一个算法将所有小于零的节点移到所有大于等于零的节点的前面。
评分规则: 【 参考答案：算法如下：void Move(LinkList &L){ LinkList p=L->next,*pre=p; while (p!=NULL) { if (p->data<0) { pre->next=p->next; p->next=L->next; L->next=p; p=pre->next; } else { pre=p; p=p->next; } }}
】

5、 问题:有一个由整数元素构成的非空单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数节点，B单链表中含有所有的奇数节点，且保持原来的相对次序。
评分规则: 【
】

第2周：线性表（上）（时长：1小时3分56秒） 第2周测验

1、 问题:线性表是（ ）。
选项：
A:一个有限序列，可以为空
B:一个有限序列，不可以为空
C:一个无限序列，可以为空
D:一个无限序列，不可以为空
答案: 【一个有限序列，可以为空】

2、 问题:线性表的基本运算ListInsert(&L,i,e)表示在线性表L中第i个位置上插入一个元素e，若L的长度为n，则i的合法取值是（ ）。
选项：
A:1≤i≤n
B:1≤i≤n+1
C:0≤i≤n-1
D: 0≤i≤n
答案: 【1≤i≤n+1】

3、 问题:顺序表具有随机存取特性，指的是（ ）。
选项：
A:查找值为x的元素与顺序表中元素个数n无关
B:查找值为x的元素与顺序表中元素个数n有关
C:查找序号为i的元素与顺序表中元素个数n无关
D:查找序号为i的元素与顺序表中元素个数n有关
答案: 【查找序号为i的元素与顺序表中元素个数n无关】

4、 问题:在顺序表中删除一个元素所需要的时间（ ）。
选项：
A:与删除元素的位置及顺序表的长度都有关
B:只与删除元素的位置有关
C:与删除任何其他元素所需要的时间相等
D:只与顺序表的长度有关
答案: 【与删除元素的位置及顺序表的长度都有关】

5、 问题:在n（n>1）个运算的顺序表中，算法时间复杂度为O(1)的运算是（ ）。
选项：
A:访问第i个元素（2≤i≤n）并求其前驱元素
B:在第i个元素之后插入一个新元素
C:删除第i个元素
D:将这n个元素递增排序
答案: 【访问第i个元素（2≤i≤n）并求其前驱元素】

6、 问题:关于线性表的顺序存储结构和链式存储结构的描述中，正确的是（ ）。Ⅰ.线性表的顺序存储结构优于链式存储结构Ⅱ.顺序存储结构比链式存储结构的存储密度高Ⅲ.如需要频繁插入和删除元素，最好采用顺序存储结构Ⅳ.如需要频繁插入和删除元素，最好采用链式存储结构
选项：
A:Ⅰ、Ⅱ、Ⅲ
B:Ⅱ、Ⅳ
C:Ⅱ、Ⅲ
D:Ⅲ、Ⅳ
答案: 【Ⅱ、Ⅳ】

7、 问题:在单链表中，增加一个头节点的目的是为了（ ）。
选项：
A:使单链表至少有一个节点
B:标识链表中某个重要节点的位置
C:方便插入和删除运算的实现
D:表示单链表是线性表的链式存储结构
答案: 【方便插入和删除运算的实现】

请输入手机号或商家订单号

打不开请联系客服QQ 2356025045 商家订单号在哪里？点此了解

---

商家订单号查看步骤

打开支付宝

方法一：我的 > 账单 > 账单详情 > 更多>复制商家订单号

方法二：我的 > 账单 >搜索关键字【网课小帮手】
> 账单详情 > 更多>复制商家订单号

方法三：联系客服QQ 2356025045

微信支付

我 > 支付 > 钱包 > 账单 > 账单详情

手机号用于查询订单，请认真核对

支付宝