2020 数据结构与算法（林劼）(电子科技大学) 最新满分章节测试答案

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

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

1、 问题:证明 O(f)+O(g)=O(f+g)
评分规则: 【 证明完整得满分
】

2、 问题:将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。 （各log函数的底数都为2）
评分规则: 【 复杂度排序正确得满分
】

第一章 绪论 绪论测验

1、 问题:下面（ ）术语与数据的存储结构无关
选项：
A:顺序表
B:链表
C:队列
D:顺序队列
答案: 【队列】

2、 问题:算法分析的目的是（ ）
选项：
A:找出数据结构的合理性
B:研究算法的输入与输出的关系
C:分析算法的效率以求改进
D:分析算法的易懂性和文档性
答案: 【分析算法的效率以求改进】

3、 问题:下面程序段的时间复杂度是（ ）for(i=0;i O(n*m)】

4、 问题:下面程序段的时间复杂度是（ ）i=s=0;while(sO(sqrt(n)) 注释：sqrt(n)表示对n开方】

5、 问题:下面程序段的时间复杂度是（ ）i=1;while(i<=n) i=i3;
选项：
A:O(n)
B:O(3n)
C:O(n^3)
D:O(logn)
答案: 【O(logn)】

6、 问题:数据的关系有逻辑关系和存储关系。其中逻辑关系是进行算法分析和设计需要考虑与使用的，而存储关系是编程实现的时候需要考虑的，逻辑关系和存储关系之间并没有关系
选项：
A:正确
B:错误
答案: 【错误】
分析：【数据的关系有逻辑关系和存储关系。其中逻辑关系是进行算法分析和设计需要考虑与使用的，而存储关系是编程实现的时候需要考虑的，到这里都是对的。
但是逻辑关系和存储关系之间有关系，编程的时候除了需要存储数据，还需要把逻辑关系存储起来，这样才能够根据设计的算法，根据逻辑关系，通过存储关系访问到相邻的数据，最终将输入转换为期望的输出结果。】

7、 问题:下面的递归函数时间复杂度是O(1)int fact(int n){ if(n<=1)return 1; else return n*fact(n-1);}
选项：
A:正确
B:错误
答案: 【错误】
分析：【对于输入数据为n的该递归函数，设时间复杂度为T(n)，如果n<=1,则T(n)=1,但如果n>1,则T(n)=T(n-1)+1=T(n-2)+1+1=….=T(1)+n=O(n)】

8、 问题:算法和程序都不能无穷的，否则会进入死循环
选项：
A:正确
B:错误
答案: 【错误】
分析：【算法不能无穷，一定经过有限步骤结束，否则会进入死循环。而程序根据需要可以无穷，比如操作系统，不输入关机要求，则会一直运行。】

9、 问题:数据包含数据对象，数据对象包含数据元素，数据元素包含数据项。
选项：
A:正确
B:错误
答案: 【正确】

10、 问题:算法可以用不同的语言描述，比如C或者java，所以算法实际上就是程序。
选项：
A:正确
B:错误
答案: 【错误】
分析：【算法不止可以用某种程序设计语言描述，还可以用伪代码，人类语言，流程图等描述。程序的逻辑不一定满足有穷性，所以二者不能等同。】

第二章 2.2 查找 查找测验

1、 问题:已知在长度为n的线性表中采用顺序查找，查找成功最好的比较次数是（ ），查找成功的最坏比较次数是（ ），查找失败的比较次数是（ ）
选项：
A:1，n,n
B:0，n,n+1
C:1,n,n+1
D:1,n+1,n+1
答案: 【1，n,n】

2、 问题:长度为n的有序顺序表采用折半查找，查找成功的最少次数为（ ），查找成功的最大次数为（ ），查找失败的最大次数为（ ），所以折半查找的最坏时间复杂度为（ ）
选项：
A:1,logn,logn,O(logn)
B:1,n,n,O(n)
C:1,n,logn,O(logn)
D:1,logn,n,O(n)
答案: 【1,logn,logn,O(logn)】

3、 问题:查找表如下分组(3,7,1,8,15),(22,43,18,45),(60,58,82,77,62),(90,88,99,100)，则索引表为（ ）,查找58需要比较（ ）次
选项：
A:(22,1),(60,6),(88,10),(101,15) 7
B:(15,1),(45,6),(82,10),(100,15),(NULL,19) 5‍
C:(15,1),(45,6),(82,10),(100,15) 5
D:(15,1),(45,6),(82,10),(100,15) 7
答案: 【(15,1),(45,6),(82,10),(100,15),(NULL,19) 5‍】

4、 问题:查找表32,45,18,77,5,23,44,19,7,3,哈希函数为H(key)=key %5,采用链地址法解决冲突的ASL(成功）=（ ），采用表长为11的线性探测再散列开放地址法的ASL(成功）=（ ），
选项：
A:18/10，32/10
B:18/5，31/10
C:18/10，31/10
D:18/5，32/10
答案: 【18/10，32/10】

5、 问题:哈希函数H(k)=k %11,采用开放地址法的平方探测再散列（di=1,4,9,16,……)解决冲突，输入关键字（9,31,26,19,1,13,2,11,27,16,21)，表长为13，建立的哈希表为（ ），ASL(成功）=（ ）
选项：
A:地址0123456789101112关键字1111322627161993121 查找次数11121121112 ASL(成功）=15/11
B:地址0123456789101112关键字1111322627161993121 查找次数11121121122 ASL（成功）=15/11‍
C:地址0123456789101112关键字1111322627161993121 查找次数11121121122 ASL(成功)=15/12‍
D:地址0123456789101112关键字1111322627161993121 查找次数11121121112 ASL(成功)=15/12
答案: 【地址0123456789101112关键字1111322627161993121 查找次数11121121122 ASL（成功）=15/11‍】

第二章 2.3 排序 排序测验

1、 问题:请对下列数据13，24，7，1，8，9，11，56，34，51，2，77，5，进行简单插入排序，冒泡排序（每趟大数冒到后面）和选择排序，2趟后的排序结果为：（ ）
选项：
A:2趟后的简单插入排序序列为：7,13，1，24，8，9，11，56，34，51，2，77，52趟后的冒泡排序为：1，7，8，9，11，13，24，34，2，51，5，56，772趟后的选择排序为：1，2，7，13，8，9，11，56，34，51，24，77，5
B:2趟后的简单插入排序序列为：7,13，1，24，8，9，11，56，34，51，2，77，52趟后的冒泡排序为：1，7，8，9，11，13，24，34，2，51，5，56，772趟后的选择排序为：1，2，5，7，13，8，9，11，56，34，51，24，77
C:2趟后的简单插入排序序列为：7,13，24，1，8，9，11，56，34，51，2，77，52趟后的冒泡排序为：7，1，8，9，11，13，24，34，2，51，5，56，772趟后的选择排序为：1，2，7，13，8，9，11，56，34，51，24，77，5
D:2趟后的简单插入排序序列为：7,13，1，24，8，9，11，56，34，51，2，77，52趟后的冒泡排序为：1，7，8，9，11，13，24，34，2，5，51，56，772趟后的选择排序为：1，2，7，13，8，9，11，56，34，51，24，77，5
答案: 【2趟后的简单插入排序序列为：7,13，24，1，8，9，11，56，34，51，2，77，52趟后的冒泡排序为：7，1，8，9，11，13，24，34，2，51，5，56，772趟后的选择排序为：1，2，7，13，8，9，11，56，34，51，24，77，5】

2、 问题:已知输入数据13，24，7，1，8，9，11，56，34，51，2，77，5，请采用2路归并递归排序算法进行排序，2趟排序后的结果为（ ）
选项：
A:13，7，24，1，8，9，11，56，34，51，2，5，77
B:1，7，13，24，8，9，11，34，51，56，2，5，77
C:7，13，24，1，8，9，11，34，51，56，2，5，77
D:13，24，1，7，8，9，11，34，56，51，2，77，5
答案: 【1，7，13，24，8，9，11，34，51，56，2，5，77】

3、 问题:已知输入数据13，24，7，1，8，9，11，56，34，51，2，77，5，请采用快速归排序算法进行排序，其中枢纽采用3者取中法，2趟排序后的结果为（ ）注意：答案中的括号表示快排中的分组
选项：
A:（（2，5，1），（7，8），9）），11，（（13，34，24），51，（77，56））
B:（（1，2），5，（7，8，9，11）），13，（（24），34，（56，77，51））
C:（（1，2），5，（13，8，9，7）），11，（（24），34，（51，77，56））
D:（（2，5，1），7，（8，9）），11，（（13，34，24），51，（77，56））
答案: 【（（2，5，1），7，（8，9）），11，（（13，34，24），51，（77，56））】

4、 问题:已知输入数据13，24，7，1，8，9，11，56，34，51，2，77，5，增量序列d=5,3,1,请采用希尔排序算法进行排序，2趟排序后的结果为（ ）
选项：
A:1，7，5，2，8，9，24，11，34，51，13，77，56
B:1，7，8，9，13，24，11，34，51，2，5，56，77
C:2，11，5，1，8，9，24，7，34，51，13，77，56
D:2，5，11，1，8，9，7，24，34，13，51，77，56
答案: 【1，7，5，2，8，9，24，11，34，51，13，77，56】

5、 问题:已知输入数据1，2，8，5，9，11，34，56，51，77，请分析数据，采用（ ）排序算法效率最低
选项：
A:冒泡排序
B:简单插入排序
C:选择排序
D:三者取中法作为枢纽的快速排序
答案: 【选择排序】

第三章 递归与分治 递归与分治测验

1、 问题:已知求一组数据连续若干数和的最大值采用分治方法得到O(nlogn)的时间复杂度，请完成下面分治法求解的代码： /**********/ /* 分治法 最大和子数组有三种情况： 1)A[1…mid] 2)A[mid+1…N] 3)A[i..mid..j] /**********/ //find max crossing left and right int Find_Max_Crossing_Subarray(int arr[], int low, int mid, int high) { const int infinite = -9999; int left_sum = infinite; int right_sum = infinite; int max_left = -1, max_right = -1; int sum = 0; //from mid to left; for (int i = mid; i >= low; i –) { sum += arr[i]; if (sum > left_sum) { left_sum = sum; max_left = i; } } sum = 0; //from mid to right for (int j = mid + 1; j <= high; j ++) { sum += arr[j]; if (sum > right_sum) { right_sum = sum; max_right = j; } } return (left_sum + right_sum); } int Find_Maximum_Subarray(int arr[], int low, int high) { if (high == low) //only one element; return arr[low]; else { int mid = (low + high)/2; int leftSum = Find_Maximum_Subarray(arr, low, mid); int rightSum = Find_Maximum_Subarray(arr, mid+1, high); int crossSum = Find_Max_Crossing_Subarray(arr, low, mid, high); ——————————完成这里的代码—————————————————— } }
选项：
A:int tmp=(leftSum>rightSum?leftSum:rightSum;return (tmp>crossSum?tmp:crossSum);
B:if(leftSum>rightSum){ if(leftSum>crossSum)return leftSum;}else{ if(rightSum>crossSum)return rightSum;}
C:if(leftSum>rightSum){ if(leftSum>crossSum)return leftSum; else return crossSum;}else{ if(rightSum>crossSum)return rightSum; else return crossSum;}
D:if(leftSum>rightSum>crossSum） return leftSum;if(rightSum>leftSum>crossSum) return rightSum;if(crossSum>leftSum>rightSum)return crossSum;
E:if(leftSum>rightSum>crossSum） return leftSum;else if(rightSum>leftSum>crossSum) return rightSum;else if(crossSum>leftSum>rightSum)return crossSum;
F:if(leftSum>rightSum && leftSum>crossSum） return leftSum;if(rightSum>leftSum && rightSum>crossSum) return rightSum;if(crossSum>leftSum && crossSum>rightSum)return crossSum;
答案: 【int tmp=(leftSum>rightSum?leftSum:rightSum;return (tmp>crossSum?tmp:crossSum);;
if(leftSum>rightSum){ if(leftSum>crossSum)return leftSum; else return crossSum;}else{ if(rightSum>crossSum)return rightSum; else return crossSum;}】

2、 问题:已知某递归算法的复杂度为：T(n)=2T(n/2)+4,则求解该递归式的解为：（ ）
选项：
A:T(n)=O(1)
B:T(n)=O(n)