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

第1页学院：专业班级：姓名：学院：专业班级：姓名：学号：装订线内不要答题学院/专业：__________姓名：__________学号：__________注意事项：1、本试卷满分100分。2、考试时间120分钟。题号一二三四五六七得分得分评阅人一、单项选择题（总共10题，每题3分，每题只有一个正确答案，请将正确答案填写在括号内）1.线性表的顺序存储结构是一种（）的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表3.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）。A.edcbaB.decbaC.dceabD.abcde4.设循环队列中数组的下标范围是0..n-1，其头指针front指向队首元素，rear指向队尾元素，则队列的长度为（）。A.rear-frontB.rear-front+1C.(rear-front+1)%(n+1)D.(rear-front+n+1)%n5.深度为5的满二叉树有（）个叶子结点。A.16B.15C.32D.316.若一棵二叉树的前序遍历序列为a,b,c，后序遍历序列为c,b,a，则根结点为（）。A.aB.bC.cD.不确定7.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是（）。A.acbedB.decabC.deabcD.cedba8.具有10个顶点的无向图，边的总数最多为（）条。A.10B.20C.45D.909.对有n个顶点的连通图进行深度优先遍历，其时间复杂度为（）。A.O(n)B.O(n)C.O(nlogn)D.O(1)10.以下排序算法中，（）在初始数据有序时效率最高。A.快速排序B.冒泡排序C.堆排序D.归并排序二、多项选择题（总共5题，每题4分，每题有两个或两个以上正确答案，请将正确答案填写在括号内）1.下列关于线性表的叙述中，正确的是（）。A.线性表是一种线性结构B.线性表可以为空表C.线性表的所有元素有相同的类型D.线性表有唯一的头结点和尾结点2.栈和队列的共同点是（）。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.都有顺序存储和链式存储两种结构3.下列关于二叉树的叙述中，正确的是（）。A.二叉树中每个结点的度最多为2B.二叉树中至少有一个结点的度为2C.二叉树可以为空D.二叉树的高度可以为04.以下属于图的存储结构的是（）。A.邻接矩阵B.邻接表C.十字链表D.邻接多重表5.下列排序算法中，属于稳定排序的是（）。A.冒泡排序B.快速排序C.归并排序D.基数排序三、判断题（总共10题，每题2分，判断下列说法是否正确，正确的打√，错误的打×）1.线性表的顺序存储结构优于链式存储结构。（）2.栈和队列都是线性结构。（）3.二叉树的前序遍历中，任意结点均处在其子女结点之前。（）4.完全二叉树一定是满二叉树。（）5.无向图的邻接矩阵一定是对称矩阵。（）6.图的深度优先遍历和广度优先遍历的结果是唯一的。（）7.排序算法中的比较次数与初始数据序列无关。（）8.插入排序和选择排序都是稳定排序。（）9.哈希表的平均查找长度与哈希函数无关。（）10.数据结构中，算法的时间复杂度和空间复杂度一定是相关的。（）四、简答题（总共3题，每题10分）1.简述线性表顺序存储结构和链式存储结构的优缺点。2.简述深度优先搜索和广度优先搜索的基本思想。3.简述快速排序的基本思想，并说明其平均时间复杂度和最坏时间复杂度。五、算法设计题（总共2