北京工业大学《数据结构与算法课设》2021-2022学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页北京工业大学《数据结构与算法课设》

2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个元素的二叉排序树中，查找一个不存在的元素，其时间复杂度最坏情况下为？（）A.O(1)B.O(log₂n)C.O(n)D.O(n²)2、对于一个具有n个顶点的无向图，若其所有顶点的度之和为20，则该图的边数为（）。A.5B.10C.15D.203、在一个容量为10的顺序存储的循环队列中，若front=4，rear=8，则此时队列中元素的个数为：A.4B.5C.6D.74、对于一个具有n个顶点和e条边的有向完全图，其弧的条数为（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/25、在图的最小生成树算法中，Kruskal算法和Prim算法都能得到最小生成树，以下关于这两个算法的比较，错误的是（）A.Kruskal算法基于边，Prim算法基于节点B.Kruskal算法需要使用并查集C.Prim算法的时间复杂度通常比Kruskal算法低D.对于稀疏图，Kruskal算法更优6、对于一个用链表实现的二叉树，进行先序遍历。以下关于先序遍历的时间复杂度的描述，哪一项是正确的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)7、图是一种复杂的数据结构。在有向图中，顶点的入度是指指向该顶点的边的数量。若要计算一个有向图中所有顶点的入度，哪种算法较为合适？A.深度优先搜索B.广度优先搜索C.拓扑排序D.以上都可以8、以下哪种数据结构常用于实现LRU（最近最少使用）页面置换算法？A.队列B.栈C.哈希表D.双链表9、深度为5的满二叉树的结点数为：A.16B.31C.32D.1510、广义表((a,b),c,(d,(e,f)))的长度和深度分别为：A.3和2B.3和3C.4和2D.4和311、在一棵二叉树中，若每个节点的左子树和右子树的高度最多相差1，则该二叉树被称为平衡二叉树。对于一个平衡二叉树，进行插入操作后，为了保持平衡，可能需要进行多少次旋转调整？A.0次B.1次C.最多2次D.不确定12、若要在一个具有n个元素的有序链表中插入一个新元素，使其仍然有序，平均时间复杂度为？（）A.O(1)B.O(log₂n)C.O(n)D.O(nlog₂n)13、在一个具有n个元素的顺序表中，若要在第i个元素（1<=i<=n）之前插入一个新元素，需要移动的元素个数为？（）A.n-iB.iC.n-i+1D.n-i-114、数组是一种常见的数据结构，它具有固定的大小和连续的存储位置。以下关于数组的说法中，错误的是？（）A.数组可以通过下标快速访问其中的元素。B.数组的插入和删除操作比较耗时，因为需要移动大量的元素。C.数组可以存储不同类型的数据元素。D.数组的长度在创建后不能改变。15、对于一个满二叉树，若其高度为h，则其节点总数为多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-116、以下关于线索二叉树的描述，错误的是：A.线索二叉树便于在中序遍历中查找前驱和后继节点B.线索二叉树中的线索是指向空指针的指针C.线索二叉树的存储空间利用率比普通二叉树高D.线索二叉树的构建过程非常简单，不需要复杂的算法17、对于一个具有n个节点的红黑树，插入一个新节点后，调整树的结构以保持红黑树性质，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)18、以下哪种数据结构常用于实现表达式求值？A.二叉树B.栈C.队列D.哈希表19、对于一个具有n个节点的二叉树，其高度的最小值和最大值分别是多少？（）A.log₂n,n-1B.1,nC.log₂n,nD.1,n-120、在一个带权的有向图中，使用迪杰斯特拉算法求从源点到其他顶点的最短路径，每次选择的顶点是？（）A.距离源点最近的顶点B.距离源点最远的顶点C.未确定最短路径的顶点中权值最小的顶点D.未确定最短路径的顶点中权值最大的顶点二、简答题（本大题共4个小题，共40分)1、（本题10分）详细阐述如何将一个有序链表转换为平衡二叉搜索树，给出具体的算法步骤。2、（本题10分）详细阐述基数排序和桶排序在处理不同类型数据时的特点和适用范围。3、（本题10分）在一个具有n个顶点和e条边的无向图中，如何使用邻接矩阵和邻接表两种方式存储图的结构，比较它们在存储空间和操作效率上的优缺点。4、（本题10分）阐述如何在一个具有n个元素的数组中，找出所有不重复的元素，分析所使用的算法和时间复杂度。三、设计题（本大题共2个