东北大学秦皇岛分校《数据结构》2024 - 2025 学年第一学期期末试卷

（第2页）制卷人签名：制卷日期制卷人签名：制卷日期：审核人签名：：审核日期：………………………………………………装……订……线…………………学院专业/班级学号姓名题号一二三四五六七八总分阅卷教师得分………………一、单项选择题（总共10题，每题3分，每题只有一个正确答案，请将正确答案填写在括号内）1.线性表采用链式存储时，其地址（）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以2.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）。A.edcbaB.decbaC.dceabD.abcde3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4.若一棵二叉树的前序遍历序列为a,e,b,d,c，后序遍历序列为b,c,d,e,a，则根结点的孩子结点（）。A.只有eB.有e、bC.有e、cD.无法确定5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。A.39B.52C.111D.1196.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（）。A.O(n)B.O(1)C.O(log2n)D.O(n2)7.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（）。A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一D.无法确定是否存在8.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率9.对一组数据（2,12,16,88,5,10）进行排序，若前三趟排序结果如下：第一趟：2,12,16,5,10,88第二趟：2,12,5,10,16,88第三趟：2,5,10,12,16,88则采用的排序方法可能是（）。A.起泡排序B.希尔排序C.归并排序D.基数排序10.以下关于数据结构的叙述中，正确的是（）。A.数据的逻辑结构独立于其存储结构B.数据的存储结构独立于其逻辑结构C.数据的逻辑结构唯一决定其存储结构D.数据结构仅由其逻辑结构和存储结构决定二、多项选择题（总共5题，每题4分，每题有两个或两个以上正确答案，请将正确答案填写在括号内）1.下列关于线性表的叙述中，正确的是（）。A.线性表是n个数据元素的有限序列B.线性表可以为空表C.线性表的每一个数据元素都有一个直接前驱和一个直接后继D.线性表的数据元素可以是各种类型的数据2.以下哪些是队列的基本操作（）。A.插入B.删除C.查找D.遍历3.一棵二叉树的中序遍历序列为dbeafc，后序遍历序列为debfca，则其前序遍历序列为（）。A.abedfcB.abdefcC.aedfbcD.aedbfc4.下列排序算法中，哪些是稳定的排序算法（）。A.起泡排序B.快速排序C.归并排序D.基数排序5.下列关于图的叙述中，正确的是（）。A.图的遍历是从给定的源点出发，按照某种搜索方法沿着图的边对图中的所有顶点访问一次且仅访问一次B.图的深度优先搜索遍历类似于树的前序遍历C.图的广度优先搜索遍历类似于树的层次遍历D.图的遍历可以得到图的所有顶点三、判断题（总共10题，每题2分，请判断下列说法是否正确，正确的打√，错误的打×）1.线性表的顺序存储结构优于链式存储结构。（）2.栈和队列都是操作受限的线性表。（）3.完全二叉树一定是满二叉树。（）4.二叉排序树的中序遍历序列是一个有序序列。（）5.拓扑排序的结果是唯一的。（）6.平衡二叉树左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。（）7.散列查找的平均查找长度与散列表的长度无关。（）8.任何一个递归过程都可以转换成非递归过程。（）9.排序算法中的比较次数越少，算法的时间复杂度越低。（）10.数据结构中的数据元素可以是另一种数据结构。（）四、简答题（总共3题，每题10分）1.简述线性表的两种存储结构（顺序存储和链式存储）的优缺点。2.简述