北京化工大学《数据结构》2024 - 2025 学年第一学期期末试卷

第1页学院：专业班级：姓名：学院：专业班级：姓名：学号：装订线内不要答题学院/专业：__________姓名：__________学号：__________注意事项：1、本试卷满分100分。2、考试时间120分钟。题号一二三四五六七得分得分评阅人一、单项选择题（总共10题，每题3分，从下列各题的4个选项中选出一个正确答案，并将其代号写在答题纸相应位置处）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.对具有n个结点的二叉树进行中序遍历，其时间复杂度为（）。A.O(n)B.O(n)C.O(logn)D.O(nlogn)6.以下关于图的叙述中，正确的是（）。A.图的遍历是从给定的源点出发，按照某种搜索方法沿着图的边访问图中的所有顶点B.图的深度优先搜索遍历类似于树的前序遍历C.图的广度优先搜索遍历类似于树的中序遍历D.图的遍历只能采用深度优先搜索或广度优先搜索7.已知一个有序表为{10,20,30,40,50,60,70}，当用二分查找法查找值为40的元素时，经过（）次比较后查找成功。A.1B.2C.3D.48.以下排序方法中，稳定的排序方法是（）。A.快速排序B.堆排序C.冒泡排序D.希尔排序9.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.4010.以下关于数据结构应用的叙述中，错误的是（）。A.栈可以用于实现递归算法B.队列可以用于实现广度优先搜索算法C.二叉排序树可以用于实现排序功能D.哈希表可以用于实现数据的高效查找，但不能用于实现数据的插入和删除操作二、多项选择题（总共5题，每题4分，从下列各题的5个选项中选出2-4个正确答案，并将其代号写在答题纸相应位置处，多选、少选、错选均不得分）1.下列哪些是线性结构（）。A.数组B.栈C.队列D.二叉树E.图2.以下关于栈的操作中，正确的是（）。A.栈顶元素可以随时被访问B.栈底元素可以随时被访问C.入栈操作会改变栈顶指针D.出栈操作会改变栈顶指针E.栈为空时不能进行出栈操作3.对于一棵二叉排序树，以下说法正确的是（）。A.左子树上所有结点的值均小于根结点的值B.右子树上所有结点的值均大于根结点的值C.中序遍历该二叉排序树可以得到一个有序序列D.前序遍历该二叉排序树可以得到一个有序序列E.后序遍历该二叉排序树可以得到一个有序序列4.以下哪些排序算法的时间复杂度为O(n)（）。A.冒泡排序B.选择排序C.插入排序D.快速排序E.归并排序5.哈希表的冲突处理方法有（）。A.开放定址法B.链地址法C.rehash法D.二次探测法E.再散列法三、判断题（总共10题，每题2分，判断下列各题，正确的在答题纸相应位置处填“√”，错误的填“×”）1.数据的逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关。（）2.顺序存储结构的优点是存储密度大，且插入和删除操作效率高。（）3.栈和队列都是操作受限的线性表，它们的操作都是按先进后出的原则进行的。（）4.完全二叉树一定是满二叉树。（）5.二叉排序树的查找效率与二叉树的高度有关。（）6.图的深度优先搜索遍历和广度优先搜索遍历都可以访问到图中的所有顶点。（）7.二分查找法只适用于有序的顺序表。（）8.快速排序是一种不稳定的排序方法，其平均时间复杂度为O(nlogn)。（）9.稀疏矩阵压缩存储的目的是节省存储空间。（）10.哈希表的平均查找长度与哈希函数无关。（）四、简答题（总共3题，每题10分）1.简述顺序表和链表的优缺点。2.简述图的深度优先搜索遍历和广度优先搜索遍历的基本思想。3.简述哈希表的基本概念，并说明哈希函数的设计原则。五、算法设计题（总共2题，每题15分）1.设计一个算法，判断一个给定的二叉树是否为平衡二叉树。平衡二叉树的定义为：任意结点的左右子树高度差的绝对值不超过1，并且左右子树都是一棵