北京城市学院《数据结构课程设计》2021-2022学年期末试卷

装订线装订线PAGE2第1页，共3页北京城市学院《数据结构课程设计》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个具有n个顶点的无向图中，若要判断两个顶点之间是否存在路径，使用哪种算法较为合适？A.迪杰斯特拉算法B.弗洛伊德算法C.深度优先遍历或广度优先遍历D.拓扑排序2、对于一个具有n个元素的循环队列，队头指针为front，队尾指针为rear，队列满的条件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front3、对于一个具有n个顶点的无向图，若其边的集合为{(1,2),(1,3),(2,3),(2,4),(3,4)}，则该图的邻接表存储中，顶点2的链表中包含的顶点有：A.1,3,4B.1,3C.3,4D.1,44、对于一个具有n个节点的线索二叉树，若n个节点中有m个空指针域，则线索的数量为？A.mB.m/2C.n+1D.n-15、对于一棵二叉树，先序遍历序列为ABC，中序遍历序列为BAC，则其后序遍历序列为？A.BCAB.CBAC.ACBD.ABC6、在一个链式存储的栈中，若要在栈顶插入一个元素，需要的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、在一个具有n个元素的线性表中，采用顺序查找法查找一个特定元素，若查找成功，平均查找长度为？（）A.(n+1)/2B.n/2C.lognD.n8、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则矩阵中非零元素的个数至少为：A.n-1B.nC.2(n-1)D.2n9、一个具有n个顶点和e条边的无向图，采用邻接表存储，其空间复杂度为？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)10、在一个具有n个元素的循环链表中，查找第i个元素（1<=i<=n），平均需要比较的次数为（）。A.nB.n/2C.(n+1)/2D.(n-1)/211、在一个具有n个元素的循环队列中，若队头指针为front，队尾指针为rear，且rear<front，则队列中的元素个数为？A.rear-frontB.front-rearC.(rear-front+n)%nD.(front-rear+n)%n12、对于一个具有n个节点的二叉树，若度为0的节点有n0个，度为1的节点有n1个，度为2的节点有n2个，则n0与n1、n2之间的关系为？A.n0=n1+n2B.n0=n2-1C.n0=n1-1D.n0=n2+113、对于一个栈，若入栈序列为1、2、3、4、5，在入栈过程中可以出栈，则下列不可能的出栈序列是：A.54321B.45321C.12345D.3142514、在二叉搜索树中，每个节点的值都大于其左子树中所有节点的值，小于其右子树中所有节点的值。以下关于二叉搜索树的操作，不正确的是（）A.插入操作需要按照节点值的大小找到合适的位置B.查找操作的时间复杂度在最坏情况下为O(n)C.删除节点时，如果该节点有两个子节点，可以选择其左子树中的最大节点或右子树中的最小节点进行替换D.二叉搜索树总是平衡的，即左右子树的高度差不超过115、在一个具有n个元素的栈中，若要获取栈底元素但不删除，需要进行多少次操作？（）A.1B.n-1C.nD.n+116、对于一个具有n个顶点和e条边的有向图，采用邻接表存储，进行深度优先遍历。以下关于遍历的时间复杂度的描述，哪一个是恰当的？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)17、二叉树是一种重要的数据结构，具有多种遍历方式。对于先序遍历、中序遍历和后序遍历，以下描述错误的是（）A.先序遍历先访问根节点，然后递归遍历左子树和右子树B.中序遍历先递归遍历左子树，然后访问根节点，最后递归遍历右子树C.后序遍历先递归遍历左子树和右子树，最后访问根节点D.这三种遍历方式的结果总是相同的18、在一个具有n个节点的二叉树中，若采用后序遍历得到的节点序列是ABC，中序遍历序列是BAC，则先序遍历序列是什么？A.CABB.ABCC.ACBD.无法确定19、在一个带头结点的循环链表中，若要判断链表是否为空，应检查？（）A.头结点的指针是否为空B.头结点的下一个结点的指针是否指向头结点C.尾结点的指针是否为空D.尾结点的下一个结点的指针是否指向头结点20、对于一个具有n个顶点和e条边的无向图，采用邻接表存储时，其空间复杂度为？（）A.O(n)B.O(e)C.O(n+e)D.O(n²)二、简答题（本大题共4个小题，共40分)1、（本题10分）解释数据结构中栈的应用场景，如表达式的前缀、中缀、后缀转换等，并说明其原理。2、（本题10分）论述在一个具有n个元素的链表中，如何将两个有序链表合并为一个有序链表。3、（本题10分）链表的双向链表的插入和删除操作与单向链表有何不同？请详细描述其实现过程。4、（本题10分）链表的循环链表有哪些特点和应用场景？如何判断一个链表是否为