黄山学院《数据结构》2021-2022学年期末试卷

装订线装订线PAGE2第1页，共3页黄山学院《数据结构》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个元素的循环双链表中，若要在表头插入一个新元素，以下关于插入操作的时间复杂度的描述，哪一项是准确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)2、在一个循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，队列最大容量为MAXSIZE，若当前队列长度为n，则判断队满的条件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE3、在一个具有n个顶点的无向图中，若每个顶点的度都为k，则边的数量为多少？（）A.nk/2B.nkC.n(k-1)/2D.n(k-1)4、对于一个m行n列的二维数组，按行优先存储时，元素a[i][j]（0<=i<m,0<=j<n）的地址计算公式为：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i5、在二叉搜索树的删除操作中，如果删除的节点是其父节点的唯一子节点，以下处理方式错误的是（）A.直接将该节点删除，不做其他调整B.将该节点的值替换为其父节点的值，并删除父节点C.将该节点的左子树或右子树替代该节点D.以上处理方式都不对6、对于一个具有n个节点的无向连通图，其生成树的边数为（）A.n-1B.nC.n+1D.2n7、对于一个具有n个顶点的带权有向图，若采用迪杰斯特拉（Dijkstra）算法求单源最短路径，其时间复杂度为：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)8、若要对一个已经排好序的数组进行二分查找，查找不成功时，最多需要比较多少次？（）A.lognB.logn-1C.logn+1D.n-19、在一个具有n个元素的线性表中，采用顺序查找法查找一个特定元素，若查找成功，平均查找长度为？（）A.(n+1)/2B.n/2C.lognD.n10、对于一个栈，若入栈序列为1、2、3、4、5，在入栈过程中可以出栈，则可能得到的出栈序列有多少种？（）A.5B.14C.21D.无数种11、以下哪种数据结构能够高效地支持动态集合的操作，如合并、查找等？（）A.链表B.二叉树C.并查集D.哈希表12、在一个采用哈希表存储的数据结构中，哈希函数将关键字映射到存储位置。若发生哈希冲突，通常采用开放定址法解决。以下关于开放定址法的时间复杂度的描述，哪一个是恰当的？A.查找操作的时间复杂度在平均情况下为O(1)，最坏情况为O(n)B.查找操作的时间复杂度始终为O(1)C.查找操作的时间复杂度在平均情况下为O(logn)，最坏情况为O(nlogn)D.查找操作的时间复杂度始终为O(n)13、在一个哈希表中，若采用线性探测法解决哈希冲突，当发生冲突时，新元素会存储在什么位置？A.冲突位置的下一个位置B.冲突位置C.随机位置D.以上都不对14、在一个具有n个元素的栈中，若要将栈中元素依次出栈并打印，以下关于操作的时间复杂度的描述，哪一项是准确的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)15、对于一个具有n个顶点和e条边的无向图，采用邻接表存储时，其空间复杂度为？（）A.O(n)B.O(e)C.O(n+e)D.O(n²)16、在一个用邻接矩阵表示的无向图中，矩阵中的元素表示什么？A.顶点之间的距离B.顶点之间是否有边C.边的权重D.以上都有可能17、在一棵二叉搜索树中，删除一个有两个子节点的节点时，通常采用的方法是：A.用左子树的最大值替代该节点B.用右子树的最小值替代该节点C.随机选择左子树或右子树的节点替代D.不进行替代，直接删除18、二叉树是一种重要的数据结构，以下关于二叉树的性质的说法中，错误的是？（）A.二叉树的每个节点最多有两个子节点。B.二叉树的左子树和右子树是有顺序的。C.满二叉树是一种特殊的二叉树，所有的叶节点都在同一层。D.完全二叉树是一种特殊的满二叉树，所有的节点都在同一层。19、在一个具有n个元素的无序数组中，使用顺序查找算法查找一个特定元素，平均比较次数约为？A.n/2B.nC.lognD.nlogn20、在一个哈希表中，负载因子越大，说明什么？A.哈希冲突越少B.存储空间利用率越高C.查找效率越高D.以上都不对二、简答题（本大题共4个小题，共40分)1、（本题10分）详细说明如何反转一个链表，分析所使用的算法和时间复杂度。2、（本题10分）详细阐述如何在一个带权无向图中计算任意两个顶点之间路径的平均权值。3、（本题10分）分析在数据结构中，如何利用优先队列实现任务调度问题。4、（本题10分）阐述如何在一个有向图中判断是否存在回路，给出算法步骤和实现代码，并分析其时间复杂度。三、设计题（本大题共2个小题，共