北京警察学院《数据结构》2024 - 2025 学年第一学期期末试卷

（第2页）制卷人签名：制卷日期制卷人签名：制卷日期：审核人签名：：审核日期：………………………………………………装……订……线…………………学院专业/班级学号姓名题号一二三四五六七八总分阅卷教师得分………………一、单项选择题（总共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.一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）。A.edcbaB.decbaC.dceabD.abcde6.队列的操作的原则是（）。A.先进先出B.后进先出C.只能进行插入D.只能进行删除7.深度为5的二叉树至多有（）个结点。A.16B.32C.31D.108.具有10个叶子结点的二叉树中有（）个度为2的结点。A.8B.9C.10D.119.对线性表进行二分查找时，要求线性表必须（）。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列10.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历二、多项选择题（总共5题，每题4分，在每小题的五个备选答案中，选出二至五个正确的答案，并将其号码分别填在题干后的括号内，多选、少选、错选均无分）1.数据的逻辑结构包括（）。A.线性结构B.树形结构C.图形结构D.集合结构E.非线性结构2.下列关于栈的叙述中正确的是（）。A.栈顶元素最先被删除B.栈底元素最后才能被删除C.栈底元素永远不能被删除D.栈是先进后出的线性表E.栈是后进后出的线性表3.下列关于队列的叙述中正确的是（）。A.队列属于非线性表B.队列按“先进后出”原则组织数据C.队列按“先进先出”原则组织数据D.队列中的元素可以随机访问E.队列有队头和队尾两个指针4.一棵二叉树的前序遍历序列为ABCDEFG，中序遍历序列为CDBAGFE，则其后序遍历序列为（）。A.DCGFEABB.DCBFGEAC.DCBGFEAD.DCBAGFEE.以上都不对5.以下属于图的存储结构的是（）。A.邻接矩阵B.邻接表C.十字链表D.邻接多重表E.顺序表三、判断题（总共10题，每题2分，判断下列各题，正确的在题后括号内打“√”，错误的打“×”）1.数据元素是数据的最小单位。（）2.算法的时间复杂度与空间复杂度一定是相关的。（）3.线性表的顺序存储结构优于链式存储结构。（）4.栈和队列都是限制存取点的线性结构。（）5.二叉树中每个结点的度不能超过2。（）6.完全二叉树一定是满二叉树。（）7.图的遍历是从给定的源点出发，按照某种搜索方法沿着图的边对图中的所有顶点访问一次且仅访问一次。（）8.二分查找法只适用于有序的顺序表。（）9.数据结构中的数据元素可以是另一数据结构。（）10.线性表的链式存储结构适用于频繁插入和删除操作的场合。（）四、简答题（总共3题，每题10分，请简要回答以下问题）1.简述线性表的两种存储结构及其优缺点。2.简述二叉树的性质。3.简述图的遍历方