2019 数据结构(四川师范大学)1207201205 最新满分章节测试答案

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

【作业】第1章 绪论 第一章 作业

1、 问题:什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。
评分规则: 【 能正确回答，说出关键点，且语句通顺。
】

2、 问题:有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O()，A2的时间复杂度为T2=O()，就时间复杂度而言，这两个算法哪一个好？
评分规则: 【 能正确回答，说出关键点，且语句通顺。
】

第1章 绪论 第1章 测验

1、 问题:下列关于数据的逻辑结构的叙述中，哪一个是不正确的：
选项：
A:数据的逻辑结构是数据间关系的描述
B:数据的逻辑结构抽象反映数据元素间的逻辑关系
C:数据的逻辑结构具体反映数据在计算机中的存储方式
D:数据的逻辑结构分为线性结构和非线性结构
答案: 【数据的逻辑结构具体反映数据在计算机中的存储方式】

2、 问题:以下关于数据的存储结构的叙述中哪一条是正确的。
选项：
A:数据的存储结构是数据间关系的抽象描述
B:数据的存储结构是逻辑结构在计算机存储器中的实现
C:数据的存储结构分为线性结构和非线性结构
D:数据的存储结构对数据运算的具体实现没有影响
答案: 【数据的存储结构是逻辑结构在计算机存储器中的实现】

3、 问题:按照数据结构中对数据类型的定义，C语言中的复合数据类型指的是：
选项：
A:整型
B:结构型
C:字符型
D:实型
答案: 【结构型】

4、 问题:伪代码是：
选项：
A:描述算法且容易理解的一种语言
B:能够方便描述算法中的分支与循环等结构化语句
C:不能直接编译或解释执行
D:以上都正确
答案: 【以上都正确】

5、 问题:下面说法错误的是：
选项：
A:算法原地工作的含义是指不需要任何额外的辅助空间
B:在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O()的算法
C:所谓时间复杂度是指最坏情况下估算算法执行时间的一个上界
D:同一个算法，实现语言的级别越高，执行效率就越低
答案: 【算法原地工作的含义是指不需要任何额外的辅助空间】

6、 问题:从逻辑上可以把数据结构分为（ ）两大类。
选项：
A:动态结构、静态结构
B:顺序结构、链式结构
C:线性结构、非线性结构
D:初等结构、构造型结构
答案: 【线性结构、非线性结构】

7、 问题:在下面的程序段中，语句x=x+1的频度为（ ）for (i=1;i<= n;i++) for (j=1;j<= n;j++) x=x+1;
选项：
A:2n
B:n
C:
D:
答案: 【】

8、 问题:程序段 for (i=n;i>0;i–) for (j=1;ja[j+1]) Swap(A[j],A[j+1]); //将A[j]与A[j+1]对换其中 n为正整数，则在最坏情况下算法的时间复杂度是：
选项：
A:O（n）
B:O(nlogn)
C:O()
D:O()
答案: 【O()】

9、 问题:以下数据结构中，（ ）是非线性结构。
选项：
A:树
B:字符串
C:栈
D:队列
答案: 【树】

10、 问题:数据元素是数据的最小单位。
选项：
A:正确
B:错误
答案: 【错误】

11、 问题:数据项是数据不可分割的最小单位。
选项：
A:正确
B:错误
答案: 【正确】

12、 问题:数据的逻辑结构是指数据的各数据项之间的逻辑关系。
选项：
A:正确
B:错误
答案: 【错误】

13、 问题:算法的优劣与算法描述语言无关。
选项：
A:正确
B:错误
答案: 【正确】

14、 问题:健壮的算法不会因非法的输入数据而出现莫名其妙的状态。
选项：
A:正确
B:错误
答案: 【正确】

15、 问题:算法可以用不同的语言描述，如果用C 语言或C++语言等高级语言来描述，则算法实际上就是程序了。
选项：
A:正确
B:错误
答案: 【正确】

16、 问题:程序一定是算法。
选项：
A:正确
B:错误
答案: 【错误】

17、 问题:数据的物理结构是指数据在计算机内的实际存储形式。
选项：
A:正确
B:错误
答案: 【正确】

18、 问题:数据的逻辑结构说明数据元素之间的逻辑关系,它依赖于计算机的存储结构。
选项：
A:正确
B:错误
答案: 【错误】

19、 问题:数据结构的操作的定义与具体实现有关。
选项：
A:正确
B:错误
答案: 【错误】

20、 问题:抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。
选项：
A:正确
B:错误
答案: 【正确】

21、 问题:算法的时间复杂度仅与问题的规模相关。
选项：
A:正确
B:错误
答案: 【错误】

【作业】第2章 线性表 第2章 作业

1、 问题:线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？（2分）（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？（2分）
评分规则: 【 （1）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。（2）选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。
】

2、 问题:线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。
评分规则: 【 链式存储结构一般来说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；（1分）其次，不需要预先分配空间，可根据需要动态申请空间；（1分）其三，表容量只受可用内存空间的限制。（1分）其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。（1分）
】

第2章 线性表 第2章 测验

1、 问题:下面关于线性表的叙述中，错误的是（）
选项：
A:线性表采用顺序存储，必须占用一片连续的存储单元
B:线性表采用顺序存储，便于进行插入和删除操作
C:线性表采用链接存储，不必占用一片连续的存储单元
D:线性表采用链接存储，便于插入和删除操作
答案: 【线性表采用顺序存储，便于进行插入和删除操作】

2、 问题:若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1≤i≤n+1)。
选项：
A:O(0)
B:O(1)
C:C. O(n)
D:O()
答案: 【C. O(n) 】