常州大学《数据结构》2021-2022学年期末试卷

装订线装订线PAGE2第1页，共3页常州大学《数据结构》

2021-2022学年期末试卷院(系)_______班级_______学号_______姓名_______题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、对于一个有向图，使用邻接矩阵存储，判断是否存在从顶点i到顶点j的边的时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(n^2)2、对于单链表，若要访问链表中的第i个元素，必须从链表的头指针开始依次遍历，平均时间复杂度为O(n)。那么如果要在链表的末尾添加一个新元素，时间复杂度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)3、在一棵平衡二叉树中，插入一个新节点后可能导致失衡，需要进行调整。以下哪种调整操作可能涉及到旋转次数最多？（）A.LL型调整B.RR型调整C.LR型调整D.RL型调整4、在一个具有n个节点的带权有向图中，若存在负权边，以下哪种最短路径算法可能不适用？A.迪杰斯特拉算法B.贝尔曼-福特算法C.弗洛伊德算法D.以上都适用5、对于一个采用链表存储的栈，若要获取栈的大小（元素数量），以下关于操作的时间复杂度的描述，哪一个是准确的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、树是一种非线性数据结构，它由节点和边组成。以下关于树的说法中，错误的是？（）A.树中的每个节点都有一个父节点（除了根节点）和零个或多个子节点。B.二叉树是一种特殊的树，每个节点最多有两个子节点。C.树可以用于实现文件系统、数据库索引等。D.树的遍历方式只有前序遍历、中序遍历和后序遍历三种。7、在一个哈希表中，若采用线性探测法解决哈希冲突，当发生冲突时，新元素会存储在什么位置？A.冲突位置的下一个位置B.冲突位置C.随机位置D.以上都不对8、设有一个广义表L=(a,(b,c),d)，其长度和深度分别为？（）A.3和2B.3和3C.4和2D.4和39、栈和队列在计算机科学中有很多应用，以下关于它们的应用场景的说法中，错误的是？（）A.栈可以用于实现表达式求值、括号匹配等。B.队列可以用于实现任务调度、消息队列等。C.栈和队列可以用于实现图的深度优先搜索和广度优先搜索。D.栈和队列只能在编程语言的底层实现中使用，不能在实际应用中直接使用。10、在一个链式存储的队列中，进行入队和出队操作时，指针的移动方向分别是（）A.入队向前，出队向后B.入队向后，出队向前C.均向前D.均向后11、在一棵平衡二叉树中，插入一个新结点后，可能需要进行的调整操作是：A.左旋B.右旋C.左旋和右旋D.不需要调整12、设有一个具有n个顶点的有向图，采用邻接表存储。若要计算每个顶点的出度，以下关于操作的时间复杂度的描述，哪一项是恰当的？A.O(n)B.O(n+e)C.O(n^2)D.O(e)13、对于一个用链表实现的栈，若要获取栈中元素的个数，以下哪种方法效率较高？A.遍历链表B.维护一个计数器C.以上效率相同D.以上都不对14、在一个具有n个节点的无向图中，若边的数量远远小于n(n-1)/2，则适合使用哪种存储方式？A.邻接矩阵B.邻接表C.十字链表D.以上都可以15、在一个具有n个节点的二叉树中，若采用后序遍历得到的节点序列是ABC，中序遍历序列是BAC，则先序遍历序列是什么？A.CABB.ABCC.ACBD.无法确定16、在一个具有n个节点的无向图中，若要判断两个节点之间是否存在路径，可以使用哪种算法？A.深度优先搜索B.广度优先搜索C.普里姆算法D.克鲁斯卡尔算法17、对于一个具有n个顶点和e条边的无向图，采用邻接表存储，若要删除一条边，平均需要修改多少个指针？（）A.1B.2C.eD.2e18、以下哪种排序算法在平均情况下的时间复杂度最优？A.冒泡排序B.快速排序C.插入排序D.选择排序19、在一个链式存储的队列中，若队头指针为front，队尾指针为rear，要删除队头元素，需要进行的操作是？（）A.front=front->next;B.rear=front;C.rear=rear->next;D.front=NULL;20、对于一个具有n个顶点和e条边的无向图，若采用邻接表存储，则其空间复杂度为：A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)二、简答题（本大题共4个小题，共40分)1、（本题10分）深入解释在链表中，如何实现头插法和尾插法创建链表，并比较它们在不同场景下的优缺点。2、（本题10分）解释如何在一个带权无向图中计算任意两个顶点之间路径的最大权值和最小值之差。3、（本题10分）详细论述在利用二叉树进行后序线索化的过程中，如何建立线索和遍历线索二叉树，并给出相应的算法步骤和代码示例。4、（本题10分）解释在链表中删除一个节点时，如何正确更新指针以保持链表的完整性，并举例说明。三、设计题（本大