安徽建筑大学《数据结构》2024 - 2025 学年第一学期期末试卷

第1页学院：专业班级：姓名：学院：专业班级：姓名：学号：装订线内不要答题学院/专业：__________姓名：__________学号：__________注意事项：1、本试卷满分100分。2、考试时间120分钟。题号一二三四五六七得分得分评阅人一、单项选择题（总共10题，每题3分，每题的备选项中，只有1个最符合题意）1.以下关于数据结构的叙述中，正确的是（）A.数据的逻辑结构独立于其存储结构B.数据的存储结构独立于其逻辑结构C.数据的逻辑结构唯一决定其存储结构D.数据结构仅由其逻辑结构和存储结构决定2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表3.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）A.edcbaB.decbaC.dceabD.abcde4.设二叉树中有20个叶子结点，5个度为1的结点，则该二叉树中总的结点数为（）A.45B.46C.44D.不可能有这样的二叉树5.若平衡二叉树的高度为6，且所有非叶子结点的平衡因子均为1，则该平衡二叉树的结点总数为（）A.12B.20C.32D.336.对关键字集合K={60，40，49，23，25，13，95，196，85}，创建平衡二叉排序树，其根结点的关键字是（）A.60B.49C.23D.407.下列排序方法中，时间复杂度不受数据初始状态影响，恒为O(n)的是（）A.堆排序B.冒泡排序C.快速排序D.直接选择排序8.下列关于哈希表的叙述中，错误的是（）A.哈希表中元素的存储位置根据该元素的关键字值计算得到B.哈希表中的元素越多，插入一个新元素时发生冲突的可能性就越大C.哈希表查找元素的时间复杂度主要取决于哈希表中元素的个数D.哈希表中元素的存储位置与关键字之间存在某种映射关系9.已知一个有序表为{10，20，30，40，50，60，70}，若采用折半查找法查找关键字30，则依次比较的关键字为（）A.50，20，30B.50，30C.40，20，30D.40，3010.广义表((a),((b),c))的表头是（）A.aB.(a)C.((b))D.((b),c)二、多项选择题（总共5题，每题4分，每题的备选项中，有2个或2个以上符合题意，至少有1个错项。错选，本题不得分；少选，所选的每个选项得1分）1.下列关于线性表的叙述中，正确的是（）A.线性表是具有相同特性的数据元素的一个有限序列B.线性表的长度是指线性表中数据元素的个数C.线性表可以为空表D.线性表的顺序存储结构优于链式存储结构E.线性表的链式存储结构优于顺序存储结构2.下列关于栈和队列的叙述中，正确的是（）A.栈是先进后出的线性表B.队列是先进先出的线性表C.栈和队列都允许在端点处进行插入和删除操作D.栈和队列都不允许在中间位置进行插入和删除操作E.栈和队列都可以用顺序存储结构和链式存储结构实现3.下列关于二叉树的叙述中，正确的是（）A.二叉树中每个结点的度最多为2B.二叉树中至少有一个结点的度为2C.二叉树可以为空D.二叉树的高度可以为0E.二叉树的每个结点最多有两棵子树4.下列排序方法中，属于内排序的有（）A.归并排序B.快速排序C.堆排序D.基数排序E.外部排序5.下列关于图的叙述中，正确的是（）A.图是一种非线性数据结构B.图中的边可以是有向的，也可以是无向的C.图中的顶点可以有零个或多个D.图的遍历可以采用深度优先搜索和广度优先搜索E.图的邻接矩阵存储方式适用于边数较多的图三、判断题（总共10题，每题2分，判断下列各题正误，正确的打“√”，错误的打“×”）1.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。（）2.顺序表的优点是可以随机存取，缺点是插入和删除操作效率低。（）3.栈和队列都是操作受限的线性表。（）4.二叉排序树的中序遍历序列是一个有序序列。（）5.平衡二叉树左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。（）6.快速排序在最坏情况下的时间复杂度为O(n)。（）7.哈希表的平均查找长度与哈希表的装填因子有关。（）8.折半查找法只适用于有序的顺序表。（）9.广义表的长度是指广义表中所含原子的个数。（）10.图的邻接表存储方式适用于边数较少的图。（）四、简答题（总共3题，每题10分，回答问题应简要说明理由）1.简述顺序表和链表的优缺点。2.简述深度优先搜索和广度优先搜索遍历图的