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

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

【作业】第1章 绪论 （视频总时长30’，共计3个） 第1章 作业

1、 问题:确定划线语句的执行次数，计算它们的渐近时间复杂度（注意本题有两个问题）。i=1; k=0; do { k=k+10*i; i++; } while(i<=n)
评分规则: 【 答案：执行次数为n写成n+1或者n-1或者O(n)扣5分
答案：渐进时间复杂度为O(n)评分要点：没有写大O扣5分
】

2、 问题:确定划线语句的执行次数，计算它们的渐近时间复杂度（注意本题有两个问题）。i=1; x=0; do { x++; i=3*i; } while( i 答案：执行次数解析：设执行次数为t，则有，不等式成立时为最后一次划线语句执行次。得到答案。评分要点：上下限写错或没有上下限得8分，写成对数形式但是底数写错得5分，写成近似时间复杂度或者其他答案不给分
答案：渐近时间复杂度评分要点：没有大O扣5分；括号内公式写错扣5分；
】

3、 问题:确定划线语句的执行次数，计算它们的渐近时间复杂度（注意本题有两个问题）。i=1; x=0; for(i=0;i 答案：执行次数为评分要点：写成带大O的形式扣5分
答案：渐近时间复杂度是评分要点：没有写大O口5分
】

4、 问题:确定划线语句的执行次数，计算它们的渐近时间复杂度（注意本题有两个问题）。y=0; while(n>=y*y) y++;
评分规则: 【 答案：执行次数是解析：设执行次数为t，在执行while循环内的条件判断时，y=t-1，当不等式成立时循环结束。评分要点：向上取整写成向下取整扣2分，没有+1扣3分
答案：渐进时间复杂度是评分要点：没有大O扣5分
】

第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、 问题:请完成下列算法填空实现对顺序表逆置存储，逆置存储是指将元素线性关系逆置后的顺序存储，例如（a0,a1,a2），关系逆置后为（a2,a1,a0).SeqList的结构体定义如下：typedef struct seqList{ int n; int maxLength; ElemType element;}SeqList;void Invert(SeqList L) {ElemType temp; int i; for ( i=0; i<_; i++) { temp =__; L->element[i] = L->element[___]; L->element[_] = _____; }}注意：程序题语法错误不扣分，为了避免程序题在互评时因为语法错误被误伤，请尽量写清楚注释，或简单描述一下算法思想。
评分规则: 【 void Invert(SeqList *L) {ElemType temp; int i; for ( i=0; in/2; i++) { temp =L->element[i]; L->element[i] = L->element[L->n-i-1]; L->element[L->n-i-1] = temp; }}评分要点：语法错误不扣分，一个空7分
】

2、 问题:请完成下列算法填空现对单链表的逆置存储，逆置存储是指将元素线性关系逆置后的链表存储，例如（a0,a1,a2），关系逆置后为（a2,a1,a0).单链表结点Node和单链表SingleList结构体定义如下：typedef struct node{ ElemType element; struct node link;}Node;typedef struct singlelist{ Node first; int n;}SingleList;void invert(SingleList L) { Node p=_,*q; L->first=NULL; while (__) { q=p->link; p->link=_; L->first=_; p=_; } }注意：程序题语法错误不扣分，为了避免程序题在互评时因为语法错误带来理解不当被误伤，请尽量写清楚注释，或简单描述一下算法思想。
评分规则: 【 void invert(SingleList L) { Node p=L->first,*q; L->first=NULL; while (p) { q=p->link; p->link=L->first; L->first=p; p=q; } }评分标准：一个空7分，语法错误不扣分
】

3、 问题:完成下列算法填空，将两个有序递增的带表头结点的单链表合并为一个有序递增的单链表。链表结点Node和链表SingleList结构体定义如下：typedef struct node{ ElemType element; struct node link;}Node;typedef struct headerlist{ Node head; int n;}HeaderList;void MergeList1(HeaderList La,HeaderList Lb,HeaderList Lc) { //合并链表La和Lb，合并后的新表使用头指针Lc指向 Node pa,pb,pc,q;pa=La->head->link; pb=Lb->head->link; pc=Lc->head; while(pa && pb) { if(____) { pc->link=pa; pc=pa; pa=pa->link; La->n–; } else if(pa->element>pb->element) { pc->link=_; pc=__; pb=_; Lb->n–; } else { pc->link=pa; pc=pa; pa=_; q=_; free(pb); pb =q; } Lc->n++; } pc->link=pa?pa:pb; //插入剩余段 Lc->n+=pa?La->n:Lb->n; }
评分规则: 【 void MergeList1(headerList La,headerList Lb,headerList Lc) { //合并链表La和Lb，合并后的新表使用头指针Lc指向 Node pa,pb,pc,q;pa=La->head->link; pb=Lb->head->link; pc=Lc->head; while(pa && pb) { if(pa->elementelement) { pc->link=pa; pc=pa; pa=pa->link; La->n–; } else if(pa->element>pb->element) { pc->link=pb; pc=pb; pb=pb->link; Lb->n–; } else { pc->link=pa; pc=pa; pa=pa->link; q=pb->link; free(pb); pb =q; } Lc->n++; } pc->link=pa?pa:pb; //插入剩余段 Lc->n+=pa?La->n:Lb->n; }评分要点：一空5分
】