南京信息工程大学《数据结构（Ⅰ）》2023-2024学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页南京信息工程大学

《数据结构（Ⅰ）》2023-2024学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、设栈的初始状态为空，元素1、2、3、4、5依次入栈，出栈序列不可能是？（）A.54321B.21543C.21345D.154322、以下关于图的遍历的描述，正确的是：A.深度优先遍历和广度优先遍历都可以用于有向图和无向图B.深度优先遍历总是先访问离起始顶点近的顶点C.广度优先遍历总是先访问深度大的顶点D.图的遍历结果是唯一的3、在一个采用哈希表存储的数据结构中，哈希函数将关键字映射到存储位置。若发生哈希冲突，通常采用开放定址法解决。以下关于开放定址法的时间复杂度的描述，哪一个是恰当的？A.查找操作的时间复杂度在平均情况下为O(1)，最坏情况为O(n)B.查找操作的时间复杂度始终为O(1)C.查找操作的时间复杂度在平均情况下为O(logn)，最坏情况为O(nlogn)D.查找操作的时间复杂度始终为O(n)4、在一个用邻接矩阵表示的无向图中，矩阵中的元素表示什么？A.顶点之间的距离B.顶点之间是否有边C.边的权重D.以上都有可能5、在一个哈希表中，若采用线性探测法解决哈希冲突，当发生冲突时，新元素会存储在什么位置？A.冲突位置的下一个位置B.冲突位置C.随机位置D.以上都不对6、已知一棵二叉树的先序遍历序列为ABCDEFG，中序遍历序列为CBAEDFG，则其后序遍历序列为：A.CBEFDGAB.CEBFDGAC.CBEFAGDD.CEBFAGD7、在一棵度为4的树中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个叶子节点，那么这棵树的总节点数是多少？A.82B.81C.79D.788、在一个用邻接表存储的有向图中，若要计算某个节点的出度，以下哪种方法较为高效？A.遍历该节点的邻接表B.遍历整个图的邻接表C.无法高效计算D.以上都不对9、对于一个具有n个元素的堆，进行删除操作并调整堆的时间复杂度为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、以下哪种数据结构常用于实现优先级队列？A.链表B.队列C.栈D.堆11、若要对一组无序的整数进行排序，使其最终变为一个递增的有序序列，以下哪种排序算法在平均情况下性能最优？A.冒泡排序B.插入排序C.选择排序D.希尔排序12、以下关于红黑树的性质，错误的是：A.每个节点要么是红色，要么是黑色B.根节点是黑色的C.每个叶子节点（NIL节点）是黑色的D.红色节点的子节点一定是红色的13、在一个具有n个节点的图中，使用弗洛伊德算法求所有节点对之间的最短路径，其时间复杂度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)14、在一个具有n个顶点和m条边的有向图中，使用弗洛伊德算法求所有顶点对之间的最短路径，其时间复杂度为？A.O(n^2)B.O(n^3)C.O(mn)D.O(m^2)15、以下关于字符串匹配的BM算法的描述，哪一项是不正确的？（）A.从模式串的尾部开始匹配B.利用了坏字符和好后缀规则C.在一般情况下比KMP算法效率低D.可以通过预处理提高匹配速度16、对于一个具有n个节点的二叉树，其先序遍历、中序遍历和后序遍历的结果都是唯一确定的，这个二叉树一定是（）A.满二叉树B.完全二叉树C.单支树D.以上都不是17、对于一个具有n个顶点的无向图，若其边的集合为{(1,2),(1,3),(2,3),(2,4),(3,4)}，则该图的邻接表存储中，顶点2的链表中包含的顶点有：A.1,3,4B.1,3C.3,4D.1,418、在一个具有n个节点的图中，使用深度优先搜索算法遍历所有节点，其时间复杂度主要取决于什么？A.边的数量B.节点的数量C.图的存储方式D.以上都是19、在一个具有n个顶点的有向无环图中，使用拓扑排序算法，其结果的唯一性如何？A.一定唯一B.可能不唯一C.取决于顶点的编号D.以上都不对20、在一个具有n个顶点的无向图中，若要判断两个顶点之间是否存在路径，使用哪种算法较为合适？A.迪杰斯特拉算法B.弗洛伊德算法C.深度优先遍历或广度优先遍历D.拓扑排序二、简答题（本大题共4个小题，共40分)1、（本题10分）详细说明如何在一个无向图中进行连通分量的计算，给出算法步骤和实现代码，并分析其时间复杂度。2、（本题10分）解释在一个有序数组中进行二分查找的基本思路和步骤，分析其时间复杂度和空间复杂度。3、（本题10分）解释最小生成树的概念，比较普里姆算法和克鲁斯卡尔算法在构建最小生成树时的不同策略和效率。4、（本题10分）详细论述在利用哈希表存储结构体数据时，如何设计哈