数据结构C(南京邮电大学) 中国大学慕课答案2024完整版100分

对应课程:点击查看
起止时间:2020-09-17到2021-01-20
更新状态:已完结

第1章 绪论 （视频总时长30’，共计3个） 第1章 单元测验

1、 下面说法正确的是____。

A:健壮的算法不会因为非法的输入数据而出现莫名其妙的状态
B:算法的优劣与算法的描述语言无关，但与所用计算机环境因素有关
C:数据的逻辑结构依赖于数据的存储结构
D:以上几个都是错误的
答案: 健壮的算法不会因为非法的输入数据而出现莫名其妙的状态

2、 从逻辑上可以把数据结构分为______两大类。

A:初等结构和构造性结构
B:顺序结构和链式结构
C:线性结构和非线性结构
D:动态结构和静态结构
答案: 线性结构和非线性结构

3、 数据结构采用链式存储时，存储单元的地址___。

A:一定连续
B:一定不连续
C:不一定连续
D:部分连续，部分不连续
答案: 不一定连续

4、 算法的时间复杂度取决于__。

A:问题规模
B:计算机的软硬件配置
C:两者都是
D:两者都不是
答案: 问题规模

5、 下面程序段的时间复杂度为____。for(i=0;i
B:
C:
D:
答案:

6、 下列函数的时间复杂度是（ ） int func（int n）｛ int i=0,sum=0; while(sum
B:
C:
D:
答案:

7、 算法的计算量的大小称为计算的____。

A:效率
B:时间复杂性
C:现实性
D:难度
答案: 时间复杂性

8、 从逻辑上可以把数据结构分为____两大类

A:动态结构、静态结构
B:顺序结构、链式结构
C:线性结构、非线性结构
D:初等结构、构造型结构
答案: 线性结构、非线性结构

9、 程序步越少的算法执行效率越高。

A:正确
B:错误
答案: 错误

10、 数据元素是数据的最小单位。

A:正确
B:错误
答案: 错误

11、 数据的逻辑结构是指数据的各数据项之间的逻辑关系。

A:正确
B:错误
答案: 错误

12、 算法的优劣与算法描述语言无关，但与所用计算机有关。

A:正确
B:错误
答案: 错误

13、 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。

A:正确
B:错误
答案: 正确

14、 数据的物理结构是指数据在计算机内的实际存储形式。

A:正确
B:错误
答案: 正确

15、 数据结构的操作的实现与数据的存储表示相关。

A:正确
B:错误
答案: 正确

16、 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

A:正确
B:错误
答案: 错误

17、 求该方法的渐近时间复杂度为____.(注意填写答案时不要有空格，用x^y的方式表达x的y次方)void aFunc(int n) { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { printf(“Hello World”); } }}
答案: O(n^2)
分析：当 i = 0 时，内循环执行 n 次运算，当 i = 1 时，内循环执行 n – 1 次运算……当 i = n – 1 时，内循环执行 1 次运算。
所以，执行次数 T(n) = n + (n – 1) + (n – 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2。
根据上文说的 大O推导法 可以知道，此时时间复杂度为 O(n^2)。

18、 求aFunc方法的时间复杂度为______。（注意答案中不要有空格，用logn表示底数为2的对数，用半角括号表示）void aFunc(int n) { for (int i = 2; i < n; i++) { i *= 2; printf(“%i”, i); }}
答案: O(logn)
分析：假设循环次数为 t，则循环条件满足 2^t < n。
可以得出，执行次数t = log(2)(n)，即 T(n) = log(2)(n)，可见时间复杂度为 O(log(2)(n))，即 O(log n)。

19、 已知算法关键步骤的执行次数,则算法的渐近时间复杂度为_。（请用x^y表示x的y次方，采用半角括号）
答案: O(n^2)

20、 已知算法关键步骤的执行次数,则算法的渐近时间复杂度为_。（logn默认以2为底，答案不要有空格，请注意此题表示问题特征的变量有m和n两个，m和n之间关系未知，乘号省略，采用半角括号）
答案: (以下答案任选其一都对)O(mlogn+m^3);
O(m^3+mlogn)

21、 四种基本的逻辑结构包括集合结构、_结构、图形结构和树形结构
答案: 线性

22、 四种基本的逻辑结构包括线性结构、_结构、图形结构和树形结构
答案: 集合

23、 四种基本的逻辑结构包括集合结构、_结构、线性结构和树形结构
答案: (以下答案任选其一都对)图形;
图;
图型

24、 四种基本的逻辑结构包括集合结构、_结构、线性结构和图形结构
答案: (以下答案任选其一都对)树形;
树;
树型

第2章 线性表（视频总时长63’3”，共计9个） 第2章 单元测验

1、 如果线性表最常用的操作是读取第i个元素的值，则采用______存储方式最高效。

A:顺序表
B:有序表
C:单链表
D:双向链表
答案: 顺序表

2、 对于线性表，下列说法正确的是___。

A:每个元素都有一个直接前驱和一个直接后继
B:线性表中至少要有一个元素
C:表中元素必须有序排列
D:除第一个元素与最后一个元素，其他每个元素都有一个直接前驱和一个直接后继
答案: 除第一个元素与最后一个元素，其他每个元素都有一个直接前驱和一个直接后继

3、 已知顺序表中每个元素占2个存储单元，第一个元素存储地址为100，则表中第6个元素的存储地址是_。

A:112
B:120
C:110
D:140
答案: 110

4、 线性表采用链式存储结构所具有的特点是__。

A:所需空间地址必须连续
B:可随机存取
C:插入、删除操作不必移动元素
D:需要事先估计所需存储空间
答案: 插入、删除操作不必移动元素

5、 在带表头结点的单链表中，设指针first指向表头结点，当______时，表示链表为空。