2019 数据结构(泉州师范学院) 最新满分章节测试答案

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

【作业】第一章 绪论 单元作业

1、 问题:试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系
评分规则: 【 能举出正确的数据结构例子，并对数据元素的结构和特点正确描述可得3分；如能继续正确指出该例中数据结构的逻辑结构类型，如是线性结构或是非线性结构，可得5分；如能继续正确描述该数据结构的存储方式以及逻辑结构和存储结构的关系，可得10分。总分不可超过10分。无以上正确描述得0分。例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。（3分）
对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。（2分）
这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构。（5分）
】

2、 问题:试分析下面各程序段的时间复杂度。（1）x=90; y=100; while(y>0)if(x>100) {x=x-10;y–;}else x++;（2）s=0; for i=0; i1y=0;while(x≥(y+1) (y+1)) y++;
评分规则: 【 能正确给出关键语句执行次数的2分，能正确给出时间复杂度的2分，每小题4分，共16分。（1）答案：O(1),程序的执行次数为常数阶
(2)答案：O(),语句s+=B[i][j];的执行次数为
(3)答案：O(log3n) 解释：语句i=i3;的执行次数为 ëlog3nû
(4)答案：O()解释：语句y++;的执行次数为
】

3、 问题: 有下列两段描述： （1）void pro1( ) (2)void pro2( ) { { n=2; y=0; While(n%2==0) x=5/y; n=n+2; printf(“%d,%d,x,y); printf(“%d”,n); } } 这两段描述均不能满足算法的特征，试问它们违反了算法的那些特征？
评分规则: 【 （1）是一个死循环，违反了算法的有穷性特征。(5分)
（2）出现除零错误，违反了算法的可行性特征。（5分）
】

第一章 绪论 单元测验

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:A和B
答案: 【A和B】

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

7、 问题:树形结构是数据元素之间存在一种（ ）。‍
选项：
A:一对一关系
B:多对多关系
C:多对一关系
D:一对多关系
答案: 【一对多关系】

8、 问题: 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ ）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++;
选项：
A: O(1)
B: O()
C: O(n)
D: O(logn)
答案: 【 O() 】

9、 问题:数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ ）。
选项：
A:低
B:高
C:相同
D:不好说
答案: 【高】

10、 问题:计算机内部数据处理的基本单位是（ ）。
选项：
A:数据
B:数据元素
C:数据项
D:数据库
答案: 【数据元素】

11、 问题:数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
选项：
A:正确
B:错误
答案: 【正确】

12、 问题:顺序存储方式只适用于存储线性表。（ ）
选项：
A:正确
B:错误
答案: 【错误】

13、 问题:只有用面向对象的计算机语言才能描述数据结构算法。（ ）
选项：
A:正确
B:错误
答案: 【错误】

14、 问题:算法和程序原则上没有区别，在讨论数据结构时二者是通用的。( )
选项：
A:正确
B:错误
答案: 【错误】

15、 问题:算法分析的目的是找出数据结构的合理性。（ ）
选项：
A:正确
B:错误
答案: 【错误】

16、 问题:数据的逻辑结构与数据元素本身的内容和形式无关。
选项：
A:正确
B:错误
答案: 【正确】

17、 问题:算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（ ）
选项：
A:正确
B:错误
答案: 【错误】

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

19、 问题:下面程序段的时间复杂度是______。for(i=0;iO(n2 )】

20、 问题:下面程序段的时间复杂度是______。i=1;while(i<=n)i=i*3;
答案: 【O(log3 n)】

21、 问题:算法时间复杂度的分析通常有两种方法，即事后统计和_____的方法，通常我们对算法求时间复杂度时，采用后一种方法。
答案: 【事前估计】

【作业】第二章 线性表（上） 线性表作业1

1、 问题:下列代码的功能是返回带头结点的单链表L的逆转链表。List Reverse( List L ){ Position Old_head, New_head, Temp; New_head = NULL; Old_head = L->Next; while ( Old_head ) { Temp = Old_head->Next; ‍ （1） ‍（6分） New_head = Old_head; Old_head = Temp; } （2） ‍（6分） return L;}
评分规则: 【 （1）Old_head->Next=New_head;
（2）L->Next=New_head;
】

2、 问题:已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a．在P结点后插入S结点的语句序列是———–。b．在P结点前插入S结点的语句序列是———–。c．删除P结点的直接后继结点的语句序列是- —–。d．删除P结点的直接前驱结点的语句序列是——-。e．删除P结点的语句序列是————。(1)P->next=P->next->next; (10) P->prior->next=P;(2)P->prior=P->prior->prior; (11) P->next->prior =P;(3) P->next=S; (12)P->next->prior=S;(4) P->prior=S; (13) P->prior->next=S;(5)S->next=P; (14) P->next->prior=P->prior(6)S->prior=P; (15)Q=P->next;(7) S->next= P->next; (16)Q= P->prior; (8) S->prior= P->prior; (17)free(P);(9) P->prior->next=p->next; (18)free(Q);
评分规则: 【 选对一个得4分，总共20分。a.(12)(7)(3)(6) 3必须在12和7的后面，其余的顺序可变（4分，错一项扣1分）
b.(13)(8)(4)(5) 同上（4分，错一项扣1分）
c.(15)(1)(11)(18) 不可变（4分，错一项扣1分）
d.(16)(2)(10)(18) 不可变（4分，错一项扣1分）
e.(9)(14)(17)（4分，错一项扣1分）
】

第二章 线性表（上） 线性表测试1

1、 问题:顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。
选项：
A:110‍
B:108
C:100
D:120
答案: 【108】