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

第1页学院：专业班级：姓名：学院：专业班级：姓名：学号：装订线内不要答题学院/专业：__________姓名：__________学号：__________注意事项：1、本试卷满分100分。2、考试时间120分钟。题号一二三四五六七得分得分评阅人一、单项选择题(总共10题，每题3分，每题只有一个正确答案，请将正确答案填入括号内)1.线性表采用链式存储时，其地址（）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表3.以下关于栈的叙述中，正确的是（）。A.栈底元素一定是最后入栈的元素B.栈顶元素一定是最先入栈的元素C.栈操作遵循先进后出的原则D.以上说法均错误4.若进栈序列为1，2，3，4，进栈过程中可以出栈，则（）不可能是一个出栈序列。A.1，4，3，2B.2，3，4，1C.3，1，4，2D.3，4，2，15.深度为5的完全二叉树的结点数不可能是（）。A.15B.16C.17D.186.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。A.250B.500C.501D.以上都不对7.对线性表进行二分查找时，要求线性表必须（）。A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链式方式存储，且结点按关键字有序排列8.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率9.下面关于B树和B+树的叙述中，不正确的是（）。A.B树和B+树都是平衡的多叉树B.B树和B+树都可用于文件的索引结构C.B树和B+树都能有效地支持顺序检索D.B树和B+树都能有效地支持随机检索10.已知一棵二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则该二叉树的后序遍历序列为（）。A.DEFBCAB.DFEBCAC.DFBECAD.BDFECA二、多项选择题(总共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.最小生成树问题可以用Prim算法和Kruskal算法解决D.拓扑排序可以判断一个有向图是否存在环三、判断题(总共10题，每题2分，请判断对错，在括号内打√或×)1.线性表的顺序存储结构优于链式存储结构。（）2.栈是一种先进先出的数据结构。（）3.完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。（）4.二叉排序树的中序遍历序列是有序的。（）5.快速排序在最坏情况下的时间复杂度为O(n)。（）6.散列表的平均查找长度与散列函数无关。（）7.图的邻接矩阵存储方式适用于存储稀疏图。（）8.拓扑排序的结果是唯一的。（）9.堆排序是一种稳定的排序算法。（）10.顺序查找适用于任何存储结构的线性表。（）四、简答题(总共3题，每题10分)1.简述线性表顺序存储结构和链式存储结构的优缺点。2.简述深度优先搜索和广度优先搜索的基本思想，并说明它们在图遍历中的应用场景。3.简述最小生成树的概念，并说明Prim算法和K