北方民族大学《数据结构实验》2021-2022学年期末试卷

自觉遵守考场纪律如考试作弊此答卷无效密自觉遵守考场纪律如考试作弊此答卷无效密封线第1页，共3页北方民族大学《数据结构实验》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、已知一个图的邻接矩阵如下所示，则从顶点V1出发进行深度优先遍历，可能得到的顶点访问序列是（）。|01100||10010||10001||01000||00100|A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V5,V3,V4D.V1,V4,V3,V2,V52、若一棵二叉树的叶子节点数为n0，度为2的节点数为n2，则n0和n2之间的关系是？（）A.n0=n2-1B.n0=n2+1C.n0=2n2-1D.n0=2n2+13、若要在一棵二叉搜索树中查找一个特定的值，平均时间复杂度为？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)4、在一个具有n个元素的顺序存储的循环队列中，队满的条件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front5、以下哪种数据结构能够在O(1)的时间复杂度内实现元素的随机访问？（）A.链表B.队列C.栈D.数组6、对于一个具有n个顶点的无向图，若其所有顶点的度之和为20，则该图的边数为（）。A.5B.10C.15D.207、以下关于图的存储结构的描述，错误的是：A.邻接矩阵适合存储稠密图B.邻接表适合存储稀疏图C.十字链表是邻接表和逆邻接表的结合D.邻接多重表只适合无向图8、在一个循环队列中，若队头指针为front，队尾指针为rear，队列最大容量为MAXSIZE，则判断队满的条件是？A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-1)%MAXSIZE==front9、以下哪种数据结构常用于实现优先级队列？（）A.二叉树B.链表C.堆D.栈10、对于一个具有n个元素的有序链表，进行折半查找，其时间复杂度为？A.O(logn)B.O(nlogn)C.O(n)D.不能进行折半查找11、在一个具有n个节点的完全二叉树中，若底层从左到右依次编号，节点i的左孩子节点编号是多少（假设根节点编号为1）？A.2iB.2i+1C.i*2D.以上都不对12、对于一棵具有n个节点的二叉搜索树，其平均查找长度的上限大约为？A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)13、在一个具有n个节点的无向图中，若要判断图是否连通，可以使用哪种算法？A.深度优先搜索B.广度优先搜索C.克鲁斯卡尔算法D.以上都可以14、已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEABC，则其先序遍历序列为？（）A.CEDBAB.CEABDC.ABCDED.EACDB15、以下哪种数据结构常用于实现操作系统中的进程调度？A.队列B.栈C.树D.图16、对于一个具有n个元素的冒泡排序，在最坏情况下，需要进行多少次比较操作？（）A.n(n-1)/2B.nC.n+1D.n-117、对于一个具有n个元素的待排序序列，若采用冒泡排序算法进行排序，在最坏情况下需要进行的比较次数为？（）A.n(n-1)/2B.nlognC.n-1D.n18、在一个具有n个元素的链表中，若要在表头插入一个新元素，平均需要修改几个指针？（）A.1B.2C.nD.n+119、以下哪种数据结构常用于实现字符串的最长公共子序列问题？A.二维数组B.栈C.队列D.树20、设有一个具有n个节点的二叉平衡树，若要插入一个新节点并保持平衡，以下关于插入操作的平均时间复杂度的描述，哪一项是正确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、简答题（本大题共4个小题，共40分)1、（本题10分）解释在平衡二叉搜索树中，如何通过调整策略降低树的高度。2、（本题10分）详细阐述在图的最短路径算法中，如何处理动态的边权值变化。3、（本题10分）解释线段树在处理区间相交问题时的思路和算法。4、（本题10分）解释如何在一个二叉搜索树中进行查找操作的多线程优化，给出算法步骤和实现代码，并分析其线程安全和