浙江工业大学之江学院《算法分析与设计》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页浙江工业大学之江学院《算法分析与设计》

2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、以下哪个算法常用于字符串匹配？（）A.KMP算法B.冒泡排序C.快速排序D.插入排序2、算法分析的主要目的是（）A.评估算法的性能B.设计新算法C.比较不同算法D.以上都是3、以下哪个数据结构可以用于实现优先队列？A.数组B.链表C.栈D.堆4、在哈希表中，当发生冲突时，可以采用哪种方法来解决？A.线性探测法B.二次探测法C.链地址法D.以上都是5、以下哪个排序算法是稳定的？A.快速排序B.堆排序C.希尔排序D.冒泡排序6、在有向图中，顶点的入度是指？A.以该顶点为起点的边的数量B.以该顶点为终点的边的数量C.与该顶点相邻的顶点数量D.该顶点的度数7、以下哪个算法可以用于求解旅行商问题？A.贪心算法B.回溯法C.分治法D.动态规划法8、以下哪个不是图的存储结构？（）A.邻接矩阵B.邻接表C.十字链表D.顺序表9、在贪心算法中，得到的解可能是（）A.最优解B.近似最优解C.可行解D.以上都可能10、在算法设计中，降低时间复杂度通常比降低空间复杂度更（）A.容易B.困难C.重要D.不重要11、在二叉搜索树中进行查找操作的平均时间复杂度是？A.O(1)B.O(logn)C.O(n)D.O(n²)12、以下哪种算法的时间复杂度最低？（）A.O(n^2)B.O(nlogn)C.O(logn)D.O(n)13、动态规划算法通常用于解决具有什么性质的问题？A.最优子结构性质和贪心选择性质B.最优子结构性质和重叠子问题性质C.贪心选择性质和重叠子问题性质D.随机性质和重叠子问题性质14、动态规划算法通常需要一个什么来存储子问题的解？A.数组B.链表C.栈D.队列15、以下哪个数据结构常用于实现图？（）A.数组B.链表C.邻接矩阵和邻接表D.栈16、以下哪个算法可以用于求解图的最小生成树问题？A.迪杰斯特拉算法B.弗洛伊德算法C.普里姆算法D.克鲁斯卡尔算法17、以下哪个不是贪心算法的特点？（）A.局部最优B.整体最优C.高效性D.不可回溯18、以下哪种排序算法在平均情况下时间复杂度最低？A.冒泡排序B.插入排序C.选择排序D.快速排序19、以下哪个算法可以用于判断一个图是否为连通图？A.深度优先搜索B.广度优先搜索C.迪杰斯特拉算法D.普里姆算法20、在图的深度优先搜索中，使用的辅助数据结构是（）A.栈B.队列C.优先队列D.哈希表二、简答题（本大题共4个小题，共40分)1、（本题10分）比较深度优先搜索和广度优先搜索的适用场景。2、（本题10分）分析快速排序在元素重复性高时的性能表现。3、（本题10分）用哈夫曼编码对一段文本进行压缩。4、（本题10分）解释动态规划算法的原理和适用条件。三、设计题（本大题共