广州美术学院《数据结构》2024 - 2025 学年第一学期期末试卷

（第2页）制卷人签名：制卷日期制卷人签名：制卷日期：审核人签名：：审核日期：………………………………………………装……订……线…………………学院专业/班级学号姓名题号一二三四五六七八总分阅卷教师得分………………一、单项选择题（总共10题，每题3分，每题只有一个正确答案，请将正确答案填写在括号内）1.数据结构中，与所使用的计算机无关的是数据的（）结构。A.存储B.物理C.逻辑D.物理和存储2.线性表的顺序存储结构是一种（）的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取3.栈和队列的共同特点是（）。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点4.若一棵二叉树的前序遍历序列为a,e,b,d,c，后序遍历序列为b,c,d,e,a，则根结点的孩子结点（）。A.只有eB.有e、bC.有e、cD.无法确定5.已知一个有序表为(12,18,24,35,47,50,62,83,90,115,134)，当用二分法查找值为90的元素时，查找成功的比较次数为（）。A.1B.2C.3D.46.对于哈希表，冲突是指（）。A.两个元素具有相同的序号B.两个元素的键值不同，而其他属性相同C.不同键值的元素对应到相同的存储地址D.数据元素过多7.以下关于图的说法正确的是（）。A.图的遍历就是从给定的源点出发，按照某种搜索方法沿着图的边对图中的所有顶点访问一次且仅访问一次B.连通图的生成树是一个极小连通子图，它包含图中的全部顶点，但只有足以构成一棵树的n-1条边C.A和B都对D.A和B都不对8.以下哪种排序算法的平均时间复杂度为O(nlogn)（）。A.冒泡排序B.选择排序C.快速排序D.插入排序9.数据结构中，算法的时间复杂度是指（）。A.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数10.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.40二、多项选择题（总共5题，每题4分，每题有两个或两个以上正确答案，请将正确答案填写在括号内）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.快速排序三、判断题（总共10题，每题2分，请判断对错，在括号内填写“√”或“×”）1.数据的逻辑结构是指数据在计算机内存中的存储形式。（）2.线性表的链式存储结构中，每个结点都包含数据域和指针域。（）3.栈是一种先进先出的线性表。（）4.队列是一种后进后出的线性表。（）5.二叉树的中序遍历序列是唯一的。（）6.对于一棵具有n个结点的完全二叉树，其深度为log2n+1。（）7.哈希表的平均查找长度与哈希函数、哈希表的装填因子有关。（）8.图的邻接矩阵存储方式适用于稠密图。（）9.快速排序在最坏情况下的时间复杂度为O(n)。（）10.直接插入排序是一种稳定的排序算法。（）四、简答题（总共3题，每题10分）1.请简述数据结构的定义，并说明数据结构包含哪三个方面的内容。2.简述线性表顺序存储结构和链式存储结构的优缺点。3.什么是图的连通性