广东外语外贸大学《数据结构》2024 - 2025 学年第一学期期末试卷

（第2页）制卷人签名：制卷日期制卷人签名：制卷日期：审核人签名：：审核日期：………………………………………………装……订……线…………………学院专业/班级学号姓名题号一二三四五六七八总分阅卷教师得分………………一、单项选择题（总共10题，每题3分，从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。）1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表2.若一棵二叉树的前序遍历序列为a,e,b,d,c，后序遍历序列为b,c,d,e,a，则根结点的孩子结点（）。A.只有eB.有e、bC.有e、cD.无法确定3.设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）。A.8B.3C.5D.94.对n个关键字进行快速排序，最大递归深度为（）。A.nB.n/2C.log2nD.nlog2n5.以下关于图的说法正确的是（）。A.连通图的生成树是该连通图的一个极小连通子图B.无向图的邻接矩阵一定是对称矩阵C.有向图的邻接表中每个顶点的边链表的长度就是该顶点的出度D.以上都正确6.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）。A.edcbaB.decbaC.dceabD.abcde7.若用链表存储一棵二叉树，则根结点的存储位置是（）。A.由用户指定B.固定在内存的某个位置C.可以是链表的任意结点D.是链表的头结点8.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数是（）。A.2B.3C.4D.59.设一组初始记录关键字序列为(20,18,22,16,30,19)，则以20为中轴的一趟快速排序结果为（）。A.18,16,20,22,30,19B.18,16,19,20,22,30C.16,18,19,20,22,30D.16,18,20,19,22,3010.以下数据结构中，（）是非线性数据结构。A.树B.字符串C.队列D.栈二、多项选择题（总共5题，每题4分，从下列各题五个备选答案中选出所有正确答案，并将其代号写在答题纸相应位置处。答案选错或未选全者，该题不得分。）1.下列关于线性表的叙述中，正确的是（）。A.线性表是n个数据元素的有限序列B.线性表采用顺序存储必须占用一片连续的存储空间C.线性表采用链式存储不必占用一片连续的存储空间D.线性表的顺序存储优于链式存储E.线性表的链式存储优于顺序存储2.一棵二叉排序树的中序遍历序列是从小到大有序的，以下说法正确的是（）。A.二叉排序树的根结点大于左子树所有结点，小于右子树所有结点B.插入新结点时，可能破坏原有二叉排序树的结构C.删除结点时，可能破坏原有二叉排序树的结构D.查找某个关键字时，比较次数与二叉排序树的高度有关E.二叉排序树的高度一定等于结点个数3.以下哪些排序算法是稳定的（）。A.冒泡排序B.快速排序C.归并排序D.堆排序E.插入排序4.对于一个具有n个顶点的图，以下说法正确的是（）。A.若采用邻接矩阵存储，占用的存储空间为nB.若采用邻接表存储，占用的存储空间与边数有关C.无向图中顶点的度等于邻接矩阵中该顶点所在行和列非零元素之和D.有向图中顶点的入度等于邻接矩阵中该顶点所在列非零元素之和E.图的遍历可以采用深度优先搜索和广度优先搜索5.以下关于栈和队列的说法正确的是（）。A.栈是一种后进先出的数据结构B.队列是一种先进先出的数据结构C.栈和队列都可以用顺序存储和链式存储实现D.栈和队列的操作都只能在一端进行E.栈和队列都可以用于实现递归算法三、判断题（总共10题，每题2分，请判断下列各题，正确的在答题纸相应位置处打“√”，错误的打“×”。）1.数据的逻辑结构是指数据在计算机内的存储形式。（）2.线性表的链式存储结构中，每个结点都有一个指针域指向其直接后继。（）3.二叉排序树的左右子树也是二叉排序树。（）4.快速排序在最坏情况下的时间复杂度为O(n)。（）5.对于一个有n个顶点和e条边的无向图，其邻接矩阵的大小为n×n，其中非零元素的个数为2e。（）6.栈和队列都是限制存取点的线性结构。（）7.顺序查找法适用于存储结构为顺序存储或链式存储的线性表。（）8.折半查找法要求线性表必须是有序的且存储方式为顺序存储。（）9.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序不变。（）10.哈希表的平均查找长度与哈希函数、哈希表的装填因子以及处理冲突的方法有关。（）四、简答题（总共3题，每题10分，请简要回答下列问题。）1.简述顺序存储结构和链式存储结构的优缺点。2.说明快速排序的基本思想，并分析其平均时间复杂度和最坏时间复杂度。3.简述图的深度优先搜索和广度优先搜索的基本过程。五、算法设计题（总共2题，每题