广州医科大学《数据结构》2024 - 2025 学年第一学期期末试卷

（第2页）制卷人签名：制卷日期制卷人签名：制卷日期：审核人签名：：审核日期：………………………………………………装……订……线…………………学院专业/班级学号姓名题号一二三四五六七八总分阅卷教师得分………………一、单项选择题（总共10题，每题3分，每题只有一个正确答案，请将正确答案填写在括号内）1.以下关于数据结构的说法，错误的是（）A.数据结构是相互之间存在一种或多种特定关系的数据元素的集合B.数据结构包括数据的逻辑结构、存储结构和数据的运算C.数据的逻辑结构是指数据在计算机中的存储方式D.数据的存储结构会影响数据运算的效率2.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表3.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）A.edcbaB.decbaC.dceabD.abcde4.深度为5的完全二叉树的结点数不可能是（）A.15B.16C.17D.185.已知一棵二叉树的先序遍历序列为ABDCEF，中序遍历序列为BDAECF，则这棵二叉树的后序遍历序列为（）A.BDFECAB.DFBECAC.DBFECAD.DFBEAC6.对n个关键字进行快速排序，最坏情况下的时间复杂度为（）A.O(n)B.O(n)C.O(log2n)D.O(nlog2n)7.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）A.先序遍历B.中序遍历C.后序遍历D.层次遍历8.哈希表的平均查找长度与（）有关。A.哈希函数B.哈希表的装填因子C.哈希表的大小D.以上都有关9.下列排序算法中，（）算法在某趟排序结束后不一定能选出一个元素放在其最终的位置上。A.选择排序B.冒泡排序C.快速排序D.堆排序10.以下关于平衡二叉树的说法，正确的是（）A.平衡二叉树左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树B.平衡二叉树的插入操作不会破坏其平衡性C.平衡二叉树的删除操作不会破坏其平衡性D.平衡二叉树的查找效率比普通二叉树低二、多项选择题（总共5题，每题4分，每题有两个或两个以上正确答案，请将正确答案填写在括号内，少选、多选、错选均不得分）1.以下属于数据的逻辑结构的有（）A.线性结构B.树形结构C.图状结构D.顺序存储结构E.链式存储结构2.以下哪些操作是栈的基本操作（）A.入栈B.出栈C.取栈顶元素D.取栈底元素E.遍历栈3.以下关于二叉排序树的说法，正确的有（）A.二叉排序树左子树上所有结点的值均小于根结点的值B.二叉排序树右子树上所有结点的值均大于根结点的值C.二叉排序树的中序遍历序列是一个有序序列D.二叉排序树的插入操作不会破坏其原有结构E.二叉排序树的删除操作不会破坏其原有结构4.以下哪些排序算法是稳定的排序算法（）A.冒泡排序B.选择排序C.插入排序D.快速排序E.归并排序5.以下关于图的说法，正确的有（）A.图的遍历可以分为深度优先遍历和广度优先遍历B.图的邻接矩阵存储方式适合存储稠密图C.图的邻接表存储方式适合存储稀疏图D.图的最小生成树问题可以使用Prim算法和Kruskal算法求解E.图的拓扑排序可以判断图中是否存在环三、判断题（总共10题，每题2分，请判断下列说法的对错，正确的打√，错误的打×）1.数据结构中，数据元素是数据的基本单位，数据项是数据的最小单位。（）2.线性表的顺序存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（）3.栈和队列都是操作受限的线性表。（）4.完全二叉树一定是满二叉树。（）5.在二叉排序树中插入一个新结点，不会破坏其原有结构。（）6.快速排序的平均时间复杂度为O(nlog2n)，最坏时间复杂度为O(n)。（）7.堆排序是一种稳定的排序算法。（）8.图的深度优先遍历和广度优先遍历的时间复杂度均为O(V+E)，其中V是顶点数，E是边数。（）9.哈希表的查找效率主要取决于哈希函数的设计。（）10.平衡二叉树的高度一定比普通二叉树低。（）四、简答题（总共3题，每题10分，请简要回答以下问题）1.简述线性表的顺序存储结构和链式存储结构的优缺点。2.简述图的深度优先遍历和广度优先遍历的基本思想。3.简述排序算法的稳定