2020 数据结构与算法(中国人民解放军陆军装甲兵学院) 最新满分章节测试答案

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

【作业】第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:问题规模与成正比
答案: 【执行时间与成正比】

第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】

6、 问题:与非循环单链表相比，循环单链表的主要优点是（ ）。
选项：
A:不再需要头指针
B:已知某个节点的位置后，能够容易找到它的前驱节点
C:在进行插入、删除操作时，能更好地保证链表不断开
D:从表中任意节点出发都能扫描到整个链表
答案: 【从表中任意节点出发都能扫描到整个链表】

7、 问题:设有带头节点的循环单链表L，当这种链表成为空链表时，有（ ）。
选项：
A:表头节点指针域next为空
B:L的值为NULL
C:表头节点的指针域next与L的值相等
D:表头节点的指针域next与L的地址相等
答案: 【表头节点的指针域next与L的值相等】

8、 问题:在长度为n（n≥1）的循环双链表L中，删除尾节点的时间复杂度为（ ）。
选项：
A:O(1)
B:O(n)
C:
D:
答案: 【O(1)】

9、 问题:将两个分别含有m、n个节点的有序单链表归并成一个有序单链表，要求不破坏原有的单链表，对应算法的空间复杂度是（ ）（MIN表示取最小值）。
选项：
A:O(n)
B:O(m)
C:O(m+n)
D:O(MIN(m,n))
答案: 【O(m+n)】

10、 问题:已知两个长度分别为m 和n 的升序单链表，若将它们合并为一个长度为m+n 的降序单链表，则时间复杂度是（ ）。
选项：
A:O(n)
B:O(m×n)
C:O(m)