2020 数据结构与算法(兰州城市学院) 最新满分章节测试答案

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

【作业】第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
】

6、 问题:设计算法求解n1到n2之间有多少能被k整除的数，并分析该算法的时间复杂度。
评分规则: 【 一定要满足算法设计的五个要求
算法用语言实现
】

7、 问题:设计一个算法求解n1到n2之间有多少个素数，并分析该算法的时间复杂度。
评分规则: 【 满足算法的五个特性
用高级语言实现该算法
分析算法
】

8、 问题:设计一个排序算法，分析该算法的时间复杂度和空间复杂度。
评分规则: 【 实现算法
分析算法
】

第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单链表中含有所有的奇数结点，且保持原来的相对次序。
评分规则: 【
】

第3周：线性表（下）（时长：41分40秒） 第3周测验

1、 问题:与单链表相比，双链表的优点之一是（ ）。
选项：
A:插入、删除操作更简单
B:可以进行随机访问
C:可以省略表头指针或表尾指针
D:访问前后相邻节点更方便
答案: 【访问前后相邻节点更方便】

2、 问题:带头节点的双链表L为空表时应满足（ ）。
选项：
A:L==NULL
B:L->prior==L->next
C:L->prior==NULL
D:L->next==NULL
答案: 【L->next==NULL】

3、 问题:在长度为n（n≥1）的双链表中插入一个节点（非尾节点）要修改（ ）个指针域。
选项：
A:1
B:2
C:3
D:4
答案: 【4】

4、 问题:对于长度为n（n≥1）的双链表L，在p所指节点之前插入一个新节点的算法的时间复杂度为（ ）。
选项：
A:O(1)
B:O(n)
C:
D:
答案: 【O(1)】

5、 问题:在长度为n（n≥1）的双链表中删除一个节点（非尾节点）要修改（ ）个指针域。
选项：
A:1
B:2
C:3
D:4
答案: 【2】