2019 数据结构(中国传媒大学) 最新满分章节测试答案

文章目录[隐藏]

【作业】第一章绪论第一章绪论（章节作业题主观题）
【作业】第一章绪论第一章绪论（章节作业题）
【作业】第二章线性表第二章线性表（章节作业主观题）
第二章线性表第二章线性表单元测验
第三章栈和队列第三章栈和队列单元测试
【作业】第三章栈和队列第三章栈和队列（章节作业主观题）
第五章数组第五章数组单元测试
第六章树和二叉树第六章树和二叉树单元测试
【作业】第六章树和二叉树第六章树和二叉树（章节作业主观题）
第七章图第七章图单元测试
【作业】第七章图第七章图（章节作业主观题）
第九章查找第九章查找单元测验
【作业】第九章查找第九章查找（章节作业主观题）
【作业】第九章查找第九章查找单元作业
第十章内部排序第十章排序单元测验
第一章绪论第一章绪论单元测验

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

【作业】第一章绪论第一章绪论（章节作业题主观题）

1、问题:主观题
评分规则: 【主观题答案比较灵活，只需抓住要点，即可获得相应步骤的得分。
】

【作业】第一章绪论第一章绪论（章节作业题）

1、问题:单项选择题（9空，每空4分）
评分规则: 【对于判断题，非对即错。每个空答对即得4分，答错或不答题得0分。
】

2、问题:判断题（6题，每题4分）
评分规则: 【对于判断题，非对即错；每道题答对即得4分，答错或不答题得0分。
】

3、问题:综合应用题（8题，每题5分）
评分规则: 【这道题要求答题者分析每段代码对应算法的时间复杂度，答对即得5分，答错或不答题得0分。
】

【作业】第二章线性表第二章线性表（章节作业主观题）

1、问题:设计一个算法，将已知顺序表重新排列成以第一个结点为界的两部分，前一部分的数据元素的值均小于第一个结点中数据元素的值，后一部分元素的值均大于或等于第一个结点中数据元素的值。要求：（1）该算法所采用的额外存储空间为O(1)。（2）提供以自然语言方式描述的算法设计思想。（3）提供类C语言描述的算法。
评分规则: 【（1）正确给出算法设计思想得3分。（2）正确给出类C语言描述的算法得7分，此部分可以根据步骤酌情给分。
】

2、问题:编写一个算法将带头结点的单链表中值重复的结点删除，使所得的结果表中各结点的值均不相同。要求：（1）提供以自然语言方式描述的算法设计思想。（2）提供类C语言描述的算法。
评分规则: 【（1）正确给出算法设计思想得3分。（2）正确给出类C语言描述的算法得7分，此部分可以根据步骤酌情给分。
】

3、问题:编写一个算法，逆置一个带头结点的双向链表L。要求：（1）提供以自然语言方式描述的算法设计思想。（2）提供类C语言描述的算法。
评分规则: 【（1）正确给出算法设计思想得3分。（2）正确给出类C语言描述的算法得7分，此部分可以根据步骤酌情给分。
】

第二章线性表第二章线性表单元测验

1、问题:在一个长度为n的顺序表中向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要向后移动_____ 个元素。
选项：
A:n-i
B:n-i+1
C:n-i-1
D:i
答案: 【n-i+1 】

2、问题:链表不具有的特点是_____ 。
选项：
A:可随机访问任一元素
B:插入元素不需要移动元素
C:不必事先估计存储空间
D:所需空间与线性表的长度成正比
答案: 【可随机访问任一元素】

3、问题:在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是_____ 。
选项：
A:单链表
B:双向链表
C:循环链表
D:顺序表
答案: 【顺序表】

4、问题:对于用一维数组 d [1..n]顺序存储的线性表，其算法时间复杂度为O(1)的操作是_____ 。
选项：
A:将n个元素从小到大排序
B:从线性表中删除第i个元素（1≤i≤n）
C:查找第i个元素（1≤i≤n）
D:向线性表的第i个元素之后插入一个元素（0≤i≤n）
答案: 【查找第i个元素（1≤i≤n）】

5、问题:静态链表（使用数组来存储的链表）中结点内指针指示的是_____ 。
选项：
A:内存地址
B:数组下标
C:链表中下一个元素在数组中的地址
D:左、右孩子地址
答案: 【链表中下一个元素在数组中的地址】

6、问题:单链表L为空的判断条件是_____ 。
选项：
A:L==NULL
B:L->next==NULL
C:L->next!=NULL
D:L!=NULL
答案: 【L->next==NULL】

7、问题:某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_____ 存储方式最节省时间。
选项：
A:单链表
B:不带头结点且仅有头指针的单循环链表
C:双向（非循环）链表
D:不带头结点且仅有尾指针（指向终端结点的指针）的单循环链表
答案: 【不带头结点且仅有尾指针（指向终端结点的指针）的单循环链表】

8、问题:在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_____ 。
选项：
A:O(1)
B:O(n)
C:O()
D:O()
答案: 【O(n)】

9、问题:将两个有n个元素的有序表归并成一个有序表，其最多比较次数为_____ 。
选项：
A:n
B:2n-1
C:2n
D:n-1
答案: 【2n-1】

10、问题:在一个长度为n（n>1）的带头结点的单链表h上，另设有尾指针r（指向尾结点），执行以下操作与链表的长度有关。
选项：
A:删除单链表中的第一个结点
B:删除单链表中的最后一个结点
C:在单链表第一个结点前插入一个新结点
D:在单链表最后一个结点后插入一个新结点
答案: 【删除单链表中的最后一个结点】

11、问题:在单链表中，若p结点不是终端结点，在其后插入s结点的操作是。
选项：
A:s->next = p; p->next = s;
B:s->next = p->next; p->next = s;
C:s->next = p->next; p = s;
D:p->next = s; s->next = p;
答案: 【s->next = p->next; p->next = s;】

12、问题:在单链表中增加一个头结点的目的是为了。
选项：
A:使单链表至少有一个结点
B:标识链表中重要结点位置
C:方便某些运算的实现
D:说明单链表是线性表的链式存储结构
答案: 【方便某些运算的实现】

13、问题:在双向链表中的p结点之后插入一个结点s的操作是。
选项：
A:s->prior=p; p->next=s; p->next->prior=s; s->next=p->next;
B:s->next=p->next; p->next->prior=s; p->next=s; s->prior=p;
C:p->next=s; s->prior=p; s->next=p->next; p->next->prior=s;
D:p->next->prior=s; p->next=s; s->next=p->next; s->prior=p;
答案: 【s->next=p->next; p->next->prior=s; p->next=s; s->prior=p;】

14、问题:在双向链表中删除*p结点之后的一个结点的操作是。
选项：
A:p->next=p->next->next; p->next->next->prior=p;
B:p->next->prior=p; p->next=p->next->next;
C:p->next=p->next->next; p->next->prior=p;
D:p->next->next=p->next; p->next->prior=p;
答案: 【p->next=p->next->next; p->next->prior=p;】

15、问题:在带头结点*head的单循环链表中，至少有一个结点的条件是。
选项：
A:head->next != NULL
B:head->next != head
C:head->next->next!=NULL
D:head!=NULL
答案: 【head->next != head】

16、问题:在带头结点head的单循环链表中至少有一个结点时，尾结点p应该满足的条件是。
选项：
A:p->next==NULL
B:p==head->next
C:p == NULL
D:p->next == head
答案: 【p->next == head】

17、问题:给定有n个元素的一维数组，建立一个有序单链表的时间复杂度是。
选项：
A:O(1)
B:O(n)
C:O()
D:O()
答案: 【O()】