对外经济贸易大学《数据结构》2024 - 2025 学年第一学期期末试卷

（第2页）制卷人签名：制卷日期制卷人签名：制卷日期：审核人签名：：审核日期：………………………………………………装……订……线…………………学院专业/班级学号姓名题号一二三四五六七八总分阅卷教师得分………………一、单项选择题（总共10题，每题3分，每题只有一个正确答案，请将正确答案填写在括号内）1.线性表采用链式存储时，其地址（）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表3.一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（）。A.5，4，3，2，1B.4，5，3，2，1C.4，3，5，1，2D.1，2，3，4，54.若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。A.只有eB.有e、bC.有e、cD.无法确定5.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。A.nB.(n-1)×(n-1)C.n×nD.(n+1)×(n+1)6.深度为5的完全二叉树的结点数不可能是（）。A.15B.16C.17D.187.已知一个有序表为(12,18,24,35,47,50,62,83,90,115,134)，当用折半查找法查找值为90的元素时，查找成功的比较次数为（）。A.1B.2C.3D.48.对关键字集合K={60，40，49，23，25，13，95，196，85}，创建平衡二叉排序树，当插入关键字46后，根结点的左子树的高度为（）。A.1B.2C.3D.49.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）排序法。A.起泡排序B.快速排序C.堆排序D.基数排序10.对稀疏矩阵进行压缩存储，可采用三元组表，一个6行7列的稀疏矩阵A，其中非零元素14个，采用三元组表存储时，该三元组表的大小是（）。A.14×1B.14×2C.14×3D.14×4二、多项选择题（总共5题，每题4分，每题有多个正确答案，请将正确答案填写在括号内，少选、多选、错选均不得分）1.以下属于数据结构中逻辑结构的有（）。A.线性结构B.树形结构C.图状结构D.顺序结构E.链式结构2.下列关于栈的叙述中，正确的有（）。A.栈顶元素最先被删除B.栈底元素最后被删除C.栈操作遵循先进后出的原则D.栈可以为空栈E.栈不能为空栈3.一棵二叉树的中序遍历序列为dbgeachf，后序遍历序列为dgebhfca，则其前序遍历序列为（）。A.abdegcfhB.abdeghcfC.abedgcfhD.abedghcfE.abecgdfh4.下列排序算法中，哪些是稳定的排序算法（）。A.冒泡排序B.快速排序C.归并排序D.堆排序E.基数排序5.下列关于图的叙述中，正确的有（）。A.图的边可以是有方向的，也可以是无方向的B.图的顶点可以没有邻接边C.图的顶点个数大于等于边的条数D.图的邻接矩阵一定是对称矩阵E.图的邻接表存储方式适合于稀疏图三、判断题（总共10题，每题2分，请判断下列说法的对错，正确的打√，错误的打×）1.数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。（）2.顺序存储结构的优点是存储密度大，且插入、删除操作效率高。（）3.一个栈的输入序列是1，2，3，4，则栈的输出序列不可能是4，3，1，2。（）4.二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。（）5.完全二叉树中，若一个结点没有左孩子，则它必是叶结点。（）6.对有序表进行折半查找时，首先与中间元素比较，若相等则查找成功，否则根据比较结果确定下一步查找的区间。（）7.平衡二叉排序树左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉排序树。（）8.快速排序在最坏情况下的时间复杂度为O(n)。（）9.对于稀疏矩阵，采用三元组表存储比采用二维数组存储更节省空间。（）10.图的深度优先搜索遍历类似于树的前序遍历，广度优先搜索遍历类似于树的层次遍历。（）四、简答题（总共3题，每题10分）1.简述线性表的顺序存储结构和链式存储结构的优缺点。2.请说明二叉排序树的定义，并简述其插入和删除操作的基本思想。3.简述图的深度优先搜索（DF