2020 数据结构与算法(浙江海洋大学) 最新满分章节测试答案

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

【作业】第一讲 基本概念（1：15：26）[陈越]（请大家2月24日-3月1日完成第一讲的学习，并独立完成单元测验1和单元作业1） 单元作业1

1、 问题:求斐波那契数列中第n（n>3）项，用递归算法好不好？给出理由。
评分规则: 【 思路清晰、条例清楚、问题分析透彻、语言逻辑性强。
】

2、 问题:递归算法一定不好吗？
评分规则: 【 思路清晰、条例清楚、问题分析透彻、语言逻辑性强。
】

第一讲 基本概念（1：15：26）[陈越]（请大家2月24日-3月1日完成第一讲的学习，并独立完成单元测验1和单元作业1） 单元测验1

1、 问题:n个整数，采用选择排序算法进行排序的时间复杂度是：
选项：
A:O()
B:O()
C:O()
D:O(n)
答案: 【O()】

2、 问题:以下程序的时间复杂度为：void prime(int n)
{ int i=2;
while((n%i)!=0&&i0.1<=sqrt(n))
i++;
if(i1.0>sqrt(n))
printf(“%d is a prime.”,n);
else
printf(“%d is not a prime.”,n);
}
选项：
A:O(n)
B:O()
C:O(n/2)
D:O()
答案: 【O()】

3、 问题:和具有相同的增长速度
选项：
A:正确
B:错误
答案: 【错误】

4、 问题:衡量、比较算法优劣的主要指标有：空间复杂度和
答案: 【时间复杂度】

【作业】第二讲 线性结构（2：19：00）[何钦铭] 单元作业2

1、 问题:如何用两个堆栈模拟实现一个队列? 如果这两个堆栈的容量分别是m和n（m>n)，你的这种方法能保证的队列容量是多少？
评分规则: 【 思路清晰、条理清楚、问题分析透彻、语言逻辑性强
】

2、 问题:日常生活中队列很常见。还有什么堆栈的典型例子？夏天逛超市时，你可能会忍不住想喝一瓶冰饮料降降温。可是，困扰你的是：放冰箱外头的饮料往往并不冰，而冰箱深处你够不着的地方，才是你想要的。想想看：冰箱中的饮料应该组织成“队列”还是“堆栈”？你对超市中的冰箱设计有什么改进性的建议。
评分规则: 【 思路清晰、条理清楚、问题分析透彻、语言逻辑性强
】

第二讲 线性结构（2：19：00）[何钦铭] 单元测验2

1、 问题:对于线性表，在顺序存储结构和链式存储结构中查找第k个元素，其时间复杂性分别是多少？
选项：
A:都是O(1)
B:都是O(k)
C:O(1)和O(k)
D:O(k)和O(1)
答案: 【O(1)和O(k)】

2、 问题:在顺序结构表示的线性表中，删除第i个元素（数组下标为i-1)，需要把后面的所有元素都往前挪一位，相应的语句是：for (_____ ) PtrL->Data[j-1]=PtrL->Data[j];其中空缺部分的内容应该是：
选项：
A:j=i; j<=Ptrl->Last; j++
B:j=Ptrl->Last; j>=i; j–
C:j=i-1; j<=Ptrl->Last; j++
D:j=Ptrl->Last; j>=i-1; j–
答案: 【j=Ptrl->Last; j>=i; j–】

3、 问题:设1、2、…、n–1、n共n个数按顺序入栈，若第一个出栈的元素是n，则第三个出栈的元素是：
选项：
A:3
B:n-2
C:n-3
D:任何元素均可能
答案: 【n-2】

4、 问题:若用单向链表实现一个堆栈，当前链表状态为：1->2->3。当对该堆栈执行pop()、push(4)操作后，链表状态变成怎样？ （1）4->2->3 (2) 1->2->4
选项：
A:只能是（1）
B:只能是（2）
C:（1）和（2）都可能
D:（1）和（2）都不可能
答案: 【只能是（1）】

5、 问题:如果一堆栈的输入序列是aAbBc，输出为 abcBA，那么该堆栈所进行的操作序列是什么？ 设P代表入栈，O代表出栈。
选项：
A:PPPOOPOPOO
B:POOPPPOPOO
C:POPPOPPOOO
D:PPOPPOOOPO
答案: 【POPPOPPOOO】

6、 问题:现采用大小为10的数组实现一个循环队列。设在某一时刻，队列为空且此时front和rear值均为5。经过若干操作后，front为8，rear为2，问：此时队列中有多少个元素？
选项：
A:4
B:5
C:6
D:7
答案: 【4】

7、 问题:在一个链表表示的队列中， f和r分别指向队列的头和尾。下列哪个操作能正确地将s结点插入到队列中：
选项：
A:f->next=s; f=s;
B:r->next=s; r=s;
C:s->next=r; r=s;
D:s->next=f; f=s;
答案: 【r->next=s; r=s;】

8、 问题:借助堆栈将中缀表达式A-(B-C/D)*E转换为后缀表达式，则该堆栈的大小至少为：
选项：
A:2
B:3
C:4
D:5
答案: 【4】

9、 问题:下列函数试图求链式存储的线性表的表长，是否正确？int Length ( List PtrL )
{ List p = PtrL;
int j = 0;
while ( p )
{ p++;
j++;
}
return j;
}
选项：
A:正确
B:错误
答案: 【错误】

【作业】第三讲 树(上) （1：50：08）[何钦铭] 单元作业3

1、 问题:在二分查找中，我们是取mid等于left和right的中间值，即用等分的方法进行查找。那为什么一定要等分呐？能不能进行“黄金分割”？也就是mid=left+0.618(right-left),当然mid要取整数。如果这样查找，时间复杂性是多少？也许你还可以编程做个试验，比较一下二分法和“黄金分割”法的执行效率。
评分规则: 【 思路清晰、条理清楚、问题分析透彻、语言逻辑性强
】

2、 问题:树的集合称为森林。是否也可以使用“儿子-兄弟”表示法存储森林？如何实现？
评分规则: 【 思路清晰、条理清楚、问题分析透彻、语言逻辑性强
】

3、 问题:借助堆栈可以实现前序遍历、中序遍历的非递归程序，而且两者的程序结构几乎一样。那么，是否也可以借助堆栈实现后序遍历的非递归程序？是不是挪动一下printf语句就可以了？
评分规则: 【 思路清晰、条理清楚、问题分析透彻、语言逻辑性强
】

4、 问题:如果将层序遍历中的队列改为堆栈，是否也是一种树的遍历？可以应用这种方法改造出一种前序、中序、后序的非递归遍历吗？
评分规则: 【 思路清晰、条理清楚、问题分析透彻、语言逻辑性强
】

第三讲 树(上) （1：50：08）[何钦铭] 单元测验3

1、 问题:在顺序查找中,如果把下列程序中的循环条件”i>0″去掉，会发生什么后果？int SequentialSearch(List Tbl,ElementType K){ /在表Element[1]~Element[n]中查找关键字为K的数据元素/ int i; for(i = Tbl->Length; i>0 && Tbl->Element[i] != K; i–); return i; /查找成功返回所在单元下标；不成功返回0/}
选项：
A:没有影响，结果一样。
B:要查找的元素存在时，找不到
C:要查找的元素不存在时，发生数组越界（i指向小于0的位置）
D:要查找的元素不存在时，函数返回0
答案: 【要查找的元素不存在时，发生数组越界（i指向小于0的位置）】

2、 问题:有一个m棵树的集合（也叫森林）共有k条边，问这m颗树共有多少个结点？
选项：
A:k+m-1
B:k+m
C:k+m+1
D:不确定，要看具体树结构
答案: 【k+m】

3、 问题:在用“儿子-兄弟”法表示的树中，如果从根结点开始访问其“次子”的“次子”，所经过的结点数与下面哪种情况一样？(注意:比较的是结点数,而不是路径)
选项：
A:从根结点开始，访问其“长子”的“长子”
B:从根结点开始，访问其“长子”的“兄弟”的“兄弟”
C:从根结点开始，访问其“长子”的“兄弟”的“长子”的“兄弟”
D:不能确定，要看整体树结构
答案: 【从根结点开始，访问其“长子”的“兄弟”的“长子”的“兄弟”】

4、 问题:在分量1~11的数组中按从小到大顺序存放11个元素，如果用顺序查找和二分查找分别查找这11个元素，哪个位置的元素在这两种方法的查找中总次数最少？
选项：
A:1
B:2
C:3