空军军医大学《数据结构》2025 学年第二学期期末试卷

班级班级学号姓名本科．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．密．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．封．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．线．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．试卷说明：1、试卷满分100分，120分钟完成试卷；2、钢笔或圆珠笔直接答在试题中（除题目有特殊规定外）；3、答卷前将密封线内的项目填写清楚。题号一二三四五总分合分人复核人满分100得分一、单项选择题（总共10题，每题3分，每题给出的四个选项中，只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内）1.以下关于数据结构的叙述中，错误的是（）A.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合B.数据结构的基本操作是指对数据结构元素的查询、插入、删除等操作C.数据结构仅研究数据的逻辑结构和存储结构D.数据结构是计算机科学与技术领域广泛使用的一种工具2.线性表采用链式存储结构时，其地址（）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可3.一个栈的入栈序列是1，2，3，4，则栈不可能的输出序列是（）A.4，3，2，1B.1，2，3，4C.4，3，1，2D.2，3，4，14.若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根节点的孩子节点（）A.只有eB.有e、bC.有e、cD.无法确定5.对n个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多（）A.从小到大排列好的B.从大到小排列好的C.元素无序D.元素基本有序6.哈希表的平均查找长度（）A.与处理冲突方法有关而与表的长度无关B.与表的长度有关而与处理冲突方法无关C.与表的长度和处理冲突方法均有关D.与表的长度和处理冲突方法均无关7.以下关于图的叙述中，正确的是（）A.图的遍历是从给定的源点出发，按照某种搜索方法沿着图的边访问图中的所有顶点B.图的深度优先遍历类似于树的前序遍历C.图的广度优先遍历类似于树的层次遍历D.以上都正确8.数据结构中，与所使用的计算机无关的是数据的（）A.存储结构B.物理结构C.逻辑结构D.物理和存储结构9.栈和队列的共同点是（）A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点10.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）A.13B.33C.18D.40二、多项选择题（总共5题，每题4分，每题给出的五个选项中，有二至五个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。多选、少选、错选均不得分）1.下列哪些是线性结构（）A.线性表B.栈C.队列D.树E.图2.以下哪些排序算法是稳定的（）A.冒泡排序B.选择排序C.插入排序D.快速排序E.归并排序3.一棵完全二叉树共有360个节点，则在该二叉树中度为1的节点个数为（）A.0B.1C.180D.181E.3604.下列关于哈希表的说法正确的是（）A.哈希表的平均查找长度与哈希函数、哈希表的装填因子有关B.哈希表的装填因子越大，发生冲突的可能性越小C.哈希表的装填因子越小，发生冲突的可能性越小D.哈希表的平均查找长度与表中元素个数有关E.哈希表的装填因子等于表中元素个数与哈希表长度之比5.以下关于图的存储结构的说法正确的是（）A.邻接矩阵存储图时，空间复杂度为O(n)B.邻接表存储图时，空间复杂度为O(n+e)C.邻接矩阵存储图时，便于判断两点之间是否有边D.邻接表存储图时，便于求顶点的度E.图的邻接矩阵一定是对称矩阵三、判断题（总共10题，每题2分，请判断每题的表述是否正确，正确的打“√”，错误的打“×”）1.数据的逻辑结构是指数据在计算机内的存储方式。（）2.线性表的链式存储结构优于顺序存储结构。（）3.栈是一种先进先出的数据结构。（）4.二叉树中每个节点的度最大为2。（）5.快速排序是一种稳定的排序算法。（）6.哈希表的查找效率主要取决于哈希函数和处理冲突的方法。（）7.图的深度优先遍历和广度优先遍历所得的遍历序列一定相同。（）8.数据结构中的算法与程序设计语言无关。（）9.队列是一种后进先出的数据结构。（）10.对稀疏矩阵进行压缩存储是为了节省存储空间。（）四、简答题（总共3题，每题10分，请简要回答下列问题）1.简述线性表顺序存储结构和链式存储结构的优缺点。2.简述图的深度优先遍历和广度优先遍历的基本思想。3.