常州工学院《数据结构》2021-2022学年期末试卷

站名：站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。…………密………………封………………线…………第1页，共1页常州工学院《数据结构》

2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个节点的线索二叉树，若n个节点中有m个空指针域，则线索的数量为？A.mB.m/2C.n+1D.n-12、以下哪种排序算法在元素基本有序的情况下性能最佳？A.快速排序B.冒泡排序C.插入排序D.堆排序3、在一个用邻接表表示的无向图中，若要删除一条边，需要进行的操作是？（）A.在两个顶点的邻接表中删除对应的边节点B.只在一个顶点的邻接表中删除对应的边节点C.重新构建邻接表D.以上都不对4、在一个具有n个元素的有序数组中，使用二分查找查找一个不存在的元素，最多比较次数约为？A.lognB.nC.n/2D.nlogn5、以下哪种数据结构常用于实现图的广度优先遍历的辅助队列？A.循环队列B.链队列C.优先队列D.双端队列6、在一个平衡二叉树中，插入一个新节点后可能会导致树的不平衡，此时需要进行调整。以下哪种调整操作可能会被执行？（）A.左旋B.右旋C.先左旋后右旋D.以上都有可能7、在数据结构中，桶排序是一种外部排序算法，以下关于桶排序的描述，错误的是（）A.要求输入数据具有特定的分布B.时间复杂度为O(n)C.空间复杂度较高D.适用于大规模数据排序8、对于一个具有n个元素的栈，若要实现将栈中元素逆置，需要借助的辅助数据结构为？（）A.队列B.栈C.链表D.数组9、在一个具有n个元素的循环双链表中，若要在表头插入一个新元素，以下关于插入操作的时间复杂度的描述，哪一项是准确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、一棵完全二叉树的第5层（根为第1层）有16个叶子节点，则该完全二叉树的节点总数最少为（）。A.47B.55C.63D.6411、在一个具有n个元素的顺序表中，删除第i个元素（1<=i<=n），平均需要移动的元素个数约为？A.n/2B.n-iC.iD.n-i+112、以下哪种数据结构可以快速判断一个元素是否在集合中？A.链表B.二叉搜索树C.哈希表D.栈13、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储其下三角部分，第一个元素A[1,1]存储在数组B[0]中，若A[8,5]在数组B中的存储位置为k，则A[7,5]在数组B中的存储位置为（）。A.k-13B.k-12C.k-11D.k-1014、在一个具有n个元素的数组中，进行顺序查找，若查找成功，平均比较次数约为？A.n/2B.nC.lognD.115、对于一个具有n个顶点和e条边的有向图，采用邻接表存储，进行深度优先遍历。以下关于遍历的时间复杂度的描述，哪一个是恰当的？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)16、在一个具有n个节点的带权无向图中，使用普里姆算法构造最小生成树，其时间复杂度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取决于图的结构17、以下关于图的存储结构的描述，错误的是：A.邻接矩阵适合存储稠密图B.邻接表适合存储稀疏图C.十字链表是邻接表和逆邻接表的结合D.邻接多重表只适合无向图18、在一个字符串匹配算法中，BM算法相对于朴素的字符串匹配算法，其优势在于？（）A.平均性能更好B.代码更简洁C.空间复杂度更低D.适用于短字符串匹配19、以下哪种排序算法的空间复杂度最低？A.归并排序B.快速排序C.冒泡排序D.插入排序20、在一个用数组实现的堆中，若要删除堆底的元素，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、简答题（本大题共4个小题，共40分)1、（本题10分）阐述哈希表的工作原理，包括哈希函数的设计和处理冲突的方法，并分析其查找效率。2、（本题10分）说明二叉树的遍历算法在二叉树的节点距离问题、树的路径问题扩展中的应用。3、（本题10分）论述跳表在大规模数据存储中的可扩展性和性能评估。4、（本题10分）深入解释在具有n个顶点的有向图中，如何判断图是否强连通，并给出具体的算法思想和实现步骤