北京邮电大学《数据结构与算法导论》2021-2022学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页北京邮电大学

《数据结构与算法导论》2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个循环队列中，若队头指针为front，队尾指针为rear，队列最大容量为MAXSIZE，则判断队满的条件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front2、在一棵完全二叉树中，若节点个数为n，那么其叶子节点的个数大约为多少？（）A.n/2B.n/4C.(n+1)/2D.n/33、已知一个有序表为{5,10,15,20,25,30,35,40,45,50}，使用折半查找法查找值为35的元素，需要比较的次数是（）。A.1B.2C.3D.44、在一个具有n个元素的顺序表中，若要将其逆置，以下关于操作的时间复杂度的描述，哪一项是恰当的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、在一个具有n个顶点的无向图中，若存在从顶点i到顶点j的路径，同时也存在从顶点j到顶点i的路径，则该图被称为？（）A.强连通图B.弱连通图C.连通图D.非连通图6、在一个具有n个顶点的图中，若存在回路，则深度优先遍历可能会出现什么情况？（）A.访问某些顶点多次B.无法完成遍历C.结果不正确D.以上都有可能7、对于一个有向图，使用邻接矩阵存储，判断是否存在从顶点i到顶点j的边的时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(n^2)8、以下关于字符串匹配算法的描述，哪一项是不正确的？（）A.BF算法的时间复杂度在最坏情况下较高B.KMP算法通过利用已匹配的部分信息来提高效率C.BM算法在一般情况下比KMP算法效率更高D.所有字符串匹配算法的时间复杂度都与模式串的长度成正比9、以下哪种数据结构常用于实现字符串的反转操作？A.栈B.队列C.链表D.树10、在一个大根堆中，删除堆顶元素后，为了重新调整为大根堆，需要进行的操作是？（）A.将最后一个元素移到堆顶，然后从堆顶向下调整B.将堆中所有元素重新排序C.将堆顶元素与最后一个元素交换，然后从堆顶向下调整D.无需调整11、哈希表是一种用于快速查找的数据结构，通过哈希函数将关键字映射到存储位置。关于哈希冲突的解决方法，错误的是（）A.开放定址法通过寻找空闲位置来解决冲突B.链地址法将冲突的元素存储在链表中C.再哈希法通过更换哈希函数来解决冲突D.哈希冲突无法避免，且对查找效率没有影响12、若对一棵二叉搜索树进行先序遍历，得到的节点序列是一个递减序列，则该二叉搜索树（）。A.没有左子树B.没有右子树C.左子树均为空D.右子树均为空13、一棵完全二叉树的第6层（根为第1层）有8个叶子节点，则该完全二叉树的节点总数最多为（）。A.39B.56C.111D.11914、对于一个具有n个顶点和m条边的有向图，使用邻接表存储，其入度和出度的计算时间复杂度分别为（）A.O(n)和O(m)B.O(m)和O(n)C.O(n+m)和O(n+m)D.O(n^2)和O(n^2)15、设有一个具有n个节点的二叉树，采用中序遍历将其转换为一个有序的单链表。以下关于转换过程的时间复杂度的描述，哪一项是正确的？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)16、对于一个具有n个元素的直接插入排序，在最好情况下，需要进行多少次比较操作？（）A.n-1B.nC.n(n-1)/2D.017、设有一个栈S和一个队列Q，初始时栈为空，队列为{1,2,3,4,5}。经过一系列入栈和出栈、入队和出队操作后，栈顶元素为3，此时队列的头元素为？（）A.1B.2C.4D.518、在一棵二叉搜索树中，删除一个有两个子节点的节点时，通常采用的方法是：A.用左子树的最大值替代该节点B.用右子树的最小值替代该节点C.随机选择左子树或右子树的节点替代D.不进行替代，直接删除19、已知一个带权无向图的邻接矩阵表示，若要计算图中两个顶点之间的最短路径，可以使用的算法是？（）A.深度优先搜索B.广度优先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法20、在一个带权的有向图中，使用迪杰斯特拉算法求从源点到其他顶点的最短路径，每次选择的顶点是？（）A.距离源点最近的顶点B.距离源点最远的顶点C.未确定最短路径的顶点中权值最小的顶点D.未确定最短路径的顶点中权值最大的顶点二、简答题（本大题共4个小题，共40分)1、（本题10分）详细阐述如何使用A*算法在图中进行寻路，解释其启发函数的作用和设计原则，并分析其性能优势。2、（本题10分）描述二叉树的中序遍历在二叉搜索树中的特殊意义。3、（本题10分）深入分析在具有n个元素的数组中，如何实现快速选择算法，用于查找第k小的元素，并给出时间复杂度的分析。4、（本题10分）详细说明在树的应用中，如何使用二叉树实现表达式求值或存储文件系统