2021 《数据结构与算法》(青海大学) 最新满分章节测试答案
- 第二章 线性表（二）（总时长：59分37秒） 第二章 单元测试（2）
- 第二章 线性表（一）（总时长：72分22秒，共6讲） 第二章 单元测试（1）
- 第三章 栈与队列（一）（总时长53分23秒） 第三章 单元测验（1）
- 第一章 绪论（总时长：56分26秒，共6讲） 第一章 单元测试
- 第五章 数组与广义表（下）（总时长：57分05秒） 第五章 单元测试
- 第三章 栈与队列（二）（总时长：52分54秒） 第三章 单元测验（2）
- 第六章 树和二叉树（上）（总时长：48分02秒） 第六章 单元测验1
- 第六章 树和二叉树（下）（总时长：112分28秒） 第六章 单元测验2
- 第七章 图（总时长：102分26秒） 第七章 单元测验
- 第八章 查找（总时长：73分53秒） 第八章 单元测验
- 第九章 内部排序（总时长：97分05秒） 第九章 单元测验
本答案对应课程为:点我自动跳转查看
本课程起止时间为:2021-09-10到2022-01-31
本篇答案更新状态:已完结
第二章 线性表（二）（总时长：59分37秒） 第二章 单元测试（2）
1、 问题:非空循环单链表L中，p指针指向尾结点，则以下表达式可能成立的是（ ）。
选项：
A:p->next==NULL
B:p==NULL
C:p->next==L
D:p==L
答案: 【p->next==L】
2、 问题:若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
选项：
A:顺序表
B:双向链表
C:带头结点的双循环链表
D:单循环链表
答案: 【顺序表 】
3、 问题:某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
选项：
A:单链表
B:仅有头指针的单循环链表
C:双链表
D:带尾指针的单循环链表
答案: 【带尾指针的单循环链表】
4、 问题:对于双向循环链表，在两个结点之间插入一个新结点需修改的指针共（ ）个。
选项：
A:2
B:3
C:4
D:5
答案: 【4】
5、 问题:将带头指针的长度为m的单链表，链接到同样带头指针的长度为n的单链表末尾。该算法的时间复杂度为( )。
选项：
A:O(m)
B:O(n)
C:O(m+n)
D:O(m*n)
答案: 【O(n)】
6、 问题:在某双向链表中删除一个结点，需要改动（ ）个指针域。
选项：
A:1
B:2
C:3
D:4
答案: 【2】
7、 问题:某双向链表中，结点结构为【prior,data,next】。那么删除p指针所指结点时，需要执行语句：p->next->prior=p->prior; ( ); free(p);
选项：
A:p->prior->next = p->next
B:p->next = p->prior
C:p->prior = p->next
D:p->prior->next = p
答案: 【p->prior->next = p->next】
8、 问题:在一个长度大于2的单循环链表L中，P指针指向某结点，在P前插入S结点，要求在O(1)时间复杂度内完成，以下正确的是（ ）。
选项：
A:s->next=p->next;p->next=s; //将s结点插入到p之后t=s->data;s->data=p->data;p->data; //s结点和p结点的值互换
B:q=p->next;while(q->next!=p) q=q->next;s->next=p; q->next=s;
C:q=p->next;while(q->next!=p) q=q->next;q->next=s; s->next=p;
D:在p结点前插入s结点，而且要求在O(1)内，无法实现。
答案: 【s->next=p->next;p->next=s; //将s结点插入到p之后t=s->data;s->data=p->data;p->data; //s结点和p结点的值互换】
9、 问题:两个单链表，可能相交，也可能不相交。如果相交，则从交点开始，合并为一个链表。设计一个算法那，判断两个链表是否相交，如果相交，求出相交的第一个结点。以下哪种说法正确（ ）。
选项：
A:可采用以下算法实现：第一步：先将两个链表各自遍历一遍，统计出两个单链表的长度m和n。假设m>n，k=m-n第二步：长链表先走k步：用指针p从长链表头开始，先走k步，此时p指向长链表的第k+1个结点。第三步：q从短链表头开始，和p一起走。p和q相等时，即为交点；如果p和q不相交，则两个链表不相交。
B:可采用以下算法实现：第一步：用两个指针p和q，分别从两个链表头开始，向后走。第二步：如果两个指针相等，即指向同一个结点，则说明相交，该结点就是交点。
C:可采用以下算法实现：第一步：将两个链表分别逆置。第二步：从头开始，什么时候链表分叉，该分叉的结点就是相交的结点。
D:该问题无法求解。
答案: 【可采用以下算法实现：第一步：先将两个链表各自遍历一遍，统计出两个单链表的长度m和n。假设m>n，k=m-n第二步：长链表先走k步：用指针p从长链表头开始，先走k步，此时p指向长链表的第k+1个结点。第三步：q从短链表头开始，和p一起走。p和q相等时，即为交点；如果p和q不相交，则两个链表不相交。】
10、 问题:编写高效算法，找出链表的中间结点。以下哪个算法更高效（ ）。
选项：
A:采用快慢指针方法。即：第一步：一个指针走的快，每次走2个结点；一个指针走的慢，每次走1个结点。第二步：当快指针到结尾或空时，慢指针所指结点即为中间结点。注：遇到链表结点为奇数或偶数时，需稍加改进即可。
B:第一步：遍历一遍链表，求出其长度n。第二步：再从头开始遍历链表，到n/2处即可。若n为偶数，中间结点则有2个；若n为奇数，则只有1个。需稍加处理。
C:第一步：将链表中的结点依次放入一个数组中，同时记录结点个数；第二步：数组中间位置即为中间结点。
D:无法实现
答案: 【采用快慢指针方法。即：第一步：一个指针走的快，每次走2个结点；一个指针走的慢，每次走1个结点。第二步：当快指针到结尾或空时，慢指针所指结点即为中间结点。注：遇到链表结点为奇数或偶数时，需稍加改进即可。】
11、 问题:为了逆序输出单链表中的结点，以下哪些算法无法实现该功能（ ）。
选项：
A:第一步：将单链表逆置；第二步：输出单链表中的元素；第三步：将单链表逆置，即恢复之前的单链表。
B:第一步：将单链表中的 元素依次放入一个数组中第二步：逆序输出该数组中的元素。
C:可用如下代码实现：void reversePrint(Node *p//p初值为单链表第一个结点{ while(p!=NULL) { reversePrint(p->next); printf("%c ",p->data); //假设结点值为字符}
D:算法思想：第一步：从头到尾找到最后一个结点；第二步：从最后一个结点向前依次输出每个结点的值。
答案: 【算法思想：第一步：从头到尾找到最后一个结点；第二步：从最后一个结点向前依次输出每个结点的值。】
12、 问题:静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。
选项：
A:正确
B:错误
答案: 【错误】
分析：【静态链表本质仍然是链表，所以它不具有顺序表的优点。】
13、 问题:循环单链表中，每个结点都有一个前驱和后继，因此循环单链表不是线性结构。
选项：
A:正确
B:错误
答案: 【错误】
分析：【前驱和后继是元素间的逻辑关系。
循环单链表是元素的存储关系，只是为了操作方便而采用循环链表，并不会改变元素的逻辑关系。】
14、 问题:静态链表中能容纳的元素个数在链表定义时就确定了，以后不能增加。
选项：
A:正确
B:错误
答案: 【正确】
分析：【这个我们认为是对的。静态链表首先要向内存申请一块连续的空间，这个空间在申请时就一定确定了。】
15、 问题:静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
选项：
A:正确
B:错误
答案: 【正确】
16、 问题:线性表在顺序存储时，查找第i个元素的时间同i的值无关。
选项：
A:正确
B:错误
答案: 【正确】
17、 问题:线性表在顺序存储时，删除第i个元素的时间同i的值无关。
选项：
A:正确
B:错误
答案: 【错误】
分析：【当然有关系了，i的值决定了要移动多少元素。】
18、 问题:静态链表因为采用的是一段连续的空间来存储元素，因此查找第i个元素的时间和i无关。
选项：
A:正确
B:错误
答案: 【错误】
分析：【静态链表虽然整个存储空间是内存中一段连续的空间，但元素并不是顺序存储的。所以查找元素需要从第一个元素开始，顺着cursor域向后找。】
第二章 线性表（一）（总时长：72分22秒，共6讲） 第二章 单元测试（1）
1、 问题:在长度为n的顺序表中的第i( 1 <= i <= n+1 )个位置上插入一个元素，其算法时间复杂度为（ ）。
选项：
A:O(logn)(以2为底)
B:O(1)
C:O(n)
D:O(n*n)
答案: 【O(n) 】
2、 问题:在长度为n的顺序表中的第i( 1 =< i <= n+1 )个位置上插入一个元素，需要移动的元素个数为（ ）。
选项：
A:n-i
B:i
C:n-i+1
D:n-i-1
答案: 【n-i+1】
3、 问题:链表不具有的特点是（ ）。
选项：
A:插入、删除不需要移动元素
B:可随机访问任一元素
C:不必事先估计存储空间
D:所需存储空间与线性表程度成正比
答案: 【可随机访问任一元素】
4、 问题:在一单链表中，删除指针p所指的后继结点，以下语句正确的是（ ）。
选项：
A:p->next=p->next->next; free(p->next);
B:free(p->next);p->next=p->next->next;
C: p=p->next;
D:s=p->next;p->next=s->next;free(s);
答案: 【s=p->next;p->next=s->next;free(s);】
5、 问题:假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是（ ）。
选项：
A:n
B:(n+1)/2
C:(n-1)/2
D:n/2
答案: 【(n-1)/2】
6、 问题:设某顺序表中第一个元素的地址是Base，每个结点占m个单元，则第i个结点的地址为（ ）。
选项：
A:Base+(i-1)×m
B:Base+i×m
本文章不含期末不含主观题！！
本文章不含期末不含主观题！！
支付后可长期查看
有疑问请添加客服QQ 2356025045反馈
如遇卡顿看不了请换个浏览器即可打开
请看清楚了再购买哦，电子资源购买后不支持退款哦
