2020 数据结构(南京邮电大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-08-31到2021-01-17

第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<n;i++）    for(j=0;j<i;j++)         x++;
选项：
A:
B:
C:
D:
答案: 【】

6、 问题:下列函数的时间复杂度是（ ）           int func（int  n）｛                    int i=0,sum=0;                    while(sum<n)   sum+=++i;                    return i;                 ｝
选项：
A:
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、 问题:求该方法的渐近时间复杂度为____.(注意填写答案时不要有空格，用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)。】

17、 问题:求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)。】

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

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

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

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指向表头结点，当______时，表示链表为空。
选项：
A:first==NULL
B:first->link==NULL