盐城工学院《数据结构课程设计》2021-2022学年期末试卷

装订线装订线PAGE2第1页，共3页盐城工学院《数据结构课程设计》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个元素的堆中，进行插入操作的时间复杂度为：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)2、设有一个具有n个节点的二叉树，若每个节点都有左右子树，则该二叉树的叶子节点数量与度为2的节点数量之间存在特定关系。以下关于这种关系的描述，哪一项是正确的？A.叶子节点数量等于度为2的节点数量B.叶子节点数量比度为2的节点数量多1C.叶子节点数量比度为2的节点数量少1D.两者之间没有固定关系3、哈希表是一种常用的数据结构，它通过哈希函数将键映射到存储位置。以下关于哈希表的说法中，错误的是？（）A.哈希表的查找速度非常快，平均时间复杂度为O(1)。B.哈希函数的设计直接影响哈希表的性能。C.哈希表可能会出现冲突，即不同的键被映射到同一个存储位置。D.哈希表只能存储整数类型的键值对。4、在二叉搜索树的删除操作中，如果删除的节点是其父节点的唯一子节点，以下处理方式错误的是（）A.直接将该节点删除，不做其他调整B.将该节点的值替换为其父节点的值，并删除父节点C.将该节点的左子树或右子树替代该节点D.以上处理方式都不对5、对于一个具有n个顶点和e条边的无向图，使用深度优先搜索算法进行遍历。以下关于算法中使用的标记数组的空间复杂度的描述，哪一项是正确的？A.O(1)B.O(n)C.O(e)D.O(n^2)6、在一个具有n个节点的完全二叉树中，若底层从左到右依次编号，节点i的左孩子节点编号是多少（假设根节点编号为1）？A.2iB.2i+1C.i*2D.以上都不对7、在一个具有n个元素的栈中，若要获取栈底元素但不删除，需要进行多少次操作？（）A.1B.n-1C.nD.n+18、对于一个栈，若入栈序列为1、2、3、4、5，在入栈过程中可以出栈，则下列不可能的出栈序列是：A.54321B.45321C.12345D.314259、一棵哈夫曼树共有215个节点，对其进行编码，共能得到（）种不同的编码。A.107B.108C.214D.21510、设栈的初始状态为空，元素1、2、3、4、5依次入栈，出栈序列不可能是？（）A.54321B.21543C.21345D.1543211、以下哪种数据结构可以高效地支持集合的并、交、差等操作？A.二叉搜索树B.哈希表C.并查集D.平衡二叉树12、在一个具有n个元素的有序数组中，使用二分查找查找一个不存在的元素，最多比较次数约为？A.lognB.nC.n/2D.nlogn13、在一个具有n个元素的大顶堆中，若要将堆顶元素与最后一个元素交换，然后调整堆，其时间复杂度为：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、一个具有n个顶点和e条边的无向图，采用邻接表存储，其空间复杂度为？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)15、在一个哈希表中，解决冲突的方法不包括：A.开放定址法B.再哈希法C.建立索引表D.链地址法16、在一个具有n个顶点的有向完全图中，边的数量为？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n17、在图的存储结构中，邻接多重表主要用于存储无向图，以下关于邻接多重表的特点，描述错误的是（）A.可以方便地删除边B.存储空间比邻接矩阵节省C.对于判断两点之间是否有边，效率较高D.不适合用于有向图的存储18、在一个具有n个元素的顺序表中，要在中间位置插入一个新元素，平均移动元素的个数约为？A.n/2B.nC.lognD.119、在一个具有n个元素的最小堆中，插入一个新元素后，为了重新调整为最小堆，最坏情况下需要比较多少次？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)20、在一个采用哈希表存储的数据结构中，哈希函数将关键字映射到存储位置。若发生哈希冲突，通常采用开放定址法解决。以下关于开放定址法的时间复杂度的描述，哪一个是恰当的？A.查找操作的时间复杂度在平均情况下为O(1)，最坏情况为O(n)B.查找操作的时间复杂度始终为O(1)C.查找操作的时间复杂度在平均情况下为O(logn)，最坏情况为O(nlogn)D.查找操作的时间复杂度始终为O(n)二、简答题（本大题共4个小题，共40分)1、（本题10分）分析在字符串匹配中，如何利用位运算提高匹配速度。2、（本题10分）详细说明如何在一个二叉搜索树中查找最大和最小元素。3、（本题10分）解释如何在一个具有n个顶点的图中计算每个顶点的邻居顶点数量。4、（本题10分）比较插入排序和希尔排序在初始有序程度不同的情况下的性能差异。三、设计题（本大题共2个小题，