邢台学院《数据结构实践》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页邢台学院

《数据结构实践》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个具有n个元素的顺序存储的循环队列，队尾指针rear指向队尾元素的下一个位置，队头指针front指向队头元素，若队列非空，则队列中元素的个数为？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+12、二叉树是一种重要的数据结构，具有多种遍历方式。对于先序遍历、中序遍历和后序遍历，以下描述错误的是（）A.先序遍历先访问根节点，然后递归遍历左子树和右子树B.中序遍历先递归遍历左子树，然后访问根节点，最后递归遍历右子树C.后序遍历先递归遍历左子树和右子树，最后访问根节点D.这三种遍历方式的结果总是相同的3、对于一个具有n个节点的二叉树，若度为0的节点有n0个，度为1的节点有n1个，度为2的节点有n2个，则n0与n1、n2之间的关系为？A.n0=n1+n2B.n0=n2-1C.n0=n1-1D.n0=n2+14、在一个具有n个节点的无向图中，若要判断两个节点之间是否存在路径，可以使用哪种算法？A.深度优先搜索B.广度优先搜索C.普里姆算法D.克鲁斯卡尔算法5、在一个带头结点的双向链表中，若要在p所指结点之后插入一个新结点q，需要修改几个指针？（）A.2B.4C.6D.86、若对一棵二叉排序树进行中序遍历，得到的节点序列是一个递增序列，则该二叉排序树（）。A.没有左子树B.没有右子树C.左子树均为空D.右子树均为空7、在循环链表中，尾指针rear指向链表的尾节点，若要在链表中插入一个新的节点，使其成为新的尾节点，以下操作正确的是？（）A.rear->next=new_node;new_node->next=rear;rear=new_node;B.new_node->next=rear;rear->next=new_node;rear=new_node;C.rear=new_node;new_node->next=rear->next;rear->next=new_node;D.new_node->next=rear->next;rear->next=new_node;8、在一个具有n个元素的顺序表中，若要删除第i个元素（1<=i<=n），并将后面的元素向前移动，平均需要移动多少个元素？（）A.n-iB.iC.(n-i)/2D.n-i+19、对于一个具有n个元素的哈希表，负载因子越大，发生冲突的可能性如何变化？（）A.越大B.越小C.不变D.不确定10、在一个哈希表中，解决冲突的方法不包括：A.开放定址法B.再哈希法C.建立索引表D.链地址法11、在图的最短路径算法中，Dijkstra算法适用于带权有向图，以下关于Dijkstra算法的描述，错误的是（）A.以起始节点为中心向外层层扩展B.每次选择距离起始节点最近的未访问节点C.可以处理负权边D.时间复杂度为O(n^2)12、在数据结构的应用中，优先队列常用于实现任务调度，以下关于优先队列的描述，错误的是（）A.可以使用堆来实现B.元素的出队顺序按照优先级确定C.插入元素的时间复杂度为O(logn)D.不支持修改元素的优先级13、在一个链式存储的队列中，进行入队和出队操作时，指针的移动方向分别是（）A.入队向前，出队向后B.入队向后，出队向前C.均向前D.均向后14、在一个带头结点的单链表中，若要删除表中所有值为x的结点，最优的算法时间复杂度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)15、在一个具有n个元素的小顶堆中，若将堆顶元素与最后一个元素交换，然后对堆进行调整，其时间复杂度为（）。A.O(log₂n)B.O(n)C.O(nlog₂n)D.O(n^2)16、对于一个具有n个顶点和e条边的带权无向图，若采用克鲁斯卡尔（Kruskal）算法生成最小生成树，其时间复杂度为？（）A.O(n²)B.O(eloge)C.O(nlogn)D.O(e²)17、图是一种复杂的数据结构，若要表示一个有向图，通常可以使用哪种存储结构？（）A.邻接矩阵B.邻接表C.十字链表D.以上均可18、在一个具有n个元素的堆中，查找最大元素的时间复杂度为？（）A.O(1)B.O(log₂n)C.O(n)D.O(nlog₂n)19、在一个哈希表中，解决冲突的方法通常有开放定址法和链地址法。如果要保证查找的平均时间复杂度较低，应该优先选择哪种方法？（）A.开放定址法B.链地址法C.两者效果相同D.取决于哈希函数20、设栈的初始状态为空，元素1、2、3、4、5依次入栈，出栈序列不可能是？（）A.54321B.21543C.21345D.15432二、简答题（本大题共4个小题，共40分)1、（本题10分）解释图的连通性问题的其他变体，如强连通分量的数量、弱连通分量的合并等问题及解决方法。2、（本题10分）分析在数据结构中，如何利用堆进行中位数的查找。3、（本题10分）详细说明在字符串匹配的多模式匹配中，如AC自动机，如何实现高效的匹配。4、（本题10分）论述在选择排序中，每一轮选择最小元素的过程以及其时间复杂度