丽江师范学院《数据结构》2025-2026学年第二学期期末试卷(A卷)

站名：站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。…………密………………封………………线…………第1页，共1页丽江师范学院《数据结构》2025-2026学年第二学期期末试卷(A卷)注意事项:1.请考生在下列横线上填写姓名、学号和年级专业。2.请仔细阅读各种题目的回答要求，在规定的位置填写答案。3.不要在试卷上乱写乱画，不要在装订线内填写无关的内容。4.考试时间120分钟专业学号姓名题号一二三四五六七八总分统分人复查人得分得分评分人一、单项选择题（每题1分，共20分）1.在数据结构中，线性表是一种（）结构。A.非线性B.线性C.树形D.图形2.下列哪种排序算法的平均时间复杂度为O(n^2)？（）A.快速排序B.归并排序C.插入排序D.冒泡排序3.在二叉树中，一个节点的左子树和右子树都是满二叉树，则该二叉树一定是（）。A.完全二叉树B.满二叉树C.平衡二叉树D.线性树4.下列哪种数据结构可以用来实现队列操作？（）A.栈B.链表C.树D.双端队列5.在哈希表中，冲突解决的方法有（）。A.线性探测法B.二次探测法C.链地址法D.以上都是6.下列哪种排序算法是稳定的？（）A.快速排序B.归并排序C.插入排序D.冒泡排序7.在链表中，删除一个节点需要（）。A.O(1)时间B.O(n)时间C.O(logn)时间D.O(nlogn)时间8.下列哪种数据结构可以用来实现栈操作？（）A.栈B.链表C.树D.双端队列9.在二叉树中，一个节点的左子树和右子树都是满二叉树，则该二叉树的深度为（）。A.O(1)B.O(logn)C.O(n)D.O(nlogn)10.下列哪种排序算法的时间复杂度与输入数据的初始状态无关？（）A.快速排序B.归并排序C.插入排序D.冒泡排序11.在链表中，查找一个节点需要（）。A.O(1)时间B.O(n)时间C.O(logn)时间D.O(nlogn)时间12.下列哪种数据结构可以用来实现栈操作？（）A.栈B.链表C.树D.双端队列13.在二叉树中，一个节点的左子树和右子树都是满二叉树，则该二叉树的叶子节点数为（）。A.O(1)B.O(logn)C.O(n)D.O(nlogn)14.下列哪种排序算法的时间复杂度与输入数据的初始状态无关？（）A.快速排序B.归并排序C.插入排序D.冒泡排序15.在链表中，删除一个节点需要（）。A.O(1)时间B.O(n)时间C.O(logn)时间D.O(nlogn)时间16.下列哪种数据结构可以用来实现栈操作？（）A.栈B.链表C.树D.双端队列17.在二叉树中，一个节点的左子树和右子树都是满二叉树，则该二叉树的节点数为（）。A.O(1)B.O(logn)C.O(n)D.O(nlogn)18.下列哪种排序算法的时间复杂度与输入数据的初始状态无关？（）A.快速排序B.归并排序C.插入排序D.冒泡排序19.在链表中，查找一个节点需要（）。A.O(1)时间B.O(n)时间C.O(logn)时间D.O(nlogn)时间20.下列哪种数据结构可以用来实现栈操作？（）A.栈B.链表C.树D.双端队列二、多项选择题（每题2分，共20分）1.下列哪些是数据结构的基本特点？（）A.结构性B.可扩展性C.可操作性D.可复用性2.下列哪些是线性表的操作？（）A.查找B.插入C.删除D.修改3.下列哪些是二叉树的特点？（）A.每个节点最多有两个子节点B.没有父节点的节点称为根节点C.没有子节点的节点称为叶子节点D.二叉树可以是空树4.下列哪些是栈的操作？（）A.入栈B.出栈C.清空D.判断是否为空5.下列哪些是队列的操作？（）A.入队B.出队C.清空D.判断是否为空三、判断题（每题1分，共10分）1.数据结构是计算机科学中的基础学科。（）2.栈是一种先进先出（FIFO）的数据结构。（）3.队列是一种先进后出（FILO）的数据结构。（）4.树是一种非线性结构。（）5.图是一种非线性结构。（）6.在链表中，查找一个节点的时间复杂度为O(n)。（）7.在二叉树中，查找一个节点的时间复杂度为O(n)。（）8.在哈希表中，冲突解决的方法有线性探测法、二次探测法和链地址法。（）9.快速排序是一种稳定的排序算法。（）10.归并排序是一种稳定的排序算法。（）四、名词解释（每题4分，共20分）1.数据结构2.线性表3.树4.图5.哈希表五、简答题（每题6分，共18分）1.简述线性表的特点。2.简述栈和队列的区别。3.简述二叉树的特点。六、案例分析题（1题，满分12分）某公司需要设计