黑龙江公安警官职业学院《数据结构》2025 学年第二学期期末试卷

班级班级学号姓名本科．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．密．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．封．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．线．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．试卷说明：1、试卷满分100分，120分钟完成试卷；2、钢笔或圆珠笔直接答在试题中（除题目有特殊规定外）；3、答卷前将密封线内的项目填写清楚。题号一二三四五总分合分人复核人满分100得分一、单项选择题（总共10题，每题3分，每题的选项中，只有一个是正确的，请将正确答案的序号填在括号内）1.以下关于线性表的说法，错误的是（）A.线性表是一种线性结构B.线性表可以采用顺序存储或链式存储C.线性表的插入和删除操作效率相同D.线性表中的元素具有逻辑上的顺序性2.若进栈序列为1，2，3，4，进栈过程中可以出栈，则（）不可能是一个出栈序列。A.1，4，3，2B.2，3，4，1C.3，1，4，2D.3，4，2，13.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A.nB.(n-1)×(n-1)C.n×nD.(n+1)×(n+1)4.深度为5的完全二叉树的结点数不可能是（）A.15B.16C.17D.185.已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为（）A.CBEFDAB.FEDCBAC.CBEDFAD.ABCDEF6.对有序表(2，5，7，10，14，15，18，23，35，41，52)进行折半查找，查找元素10的比较次数是（）A.2B.3C.4D.57.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个存储单元，则a85的地址为（）A.13B.33C.18D.408.以下排序算法中，平均时间复杂度为O(nlogn)且稳定的是（）A.快速排序B.堆排序C.归并排序D.冒泡排序9.数据结构中与所使用的计算机无关的是数据的（）A.存储结构B.物理结构C.逻辑结构D.物理和存储结构10.循环队列存储在数组A[0..m]中，则入队时的操作为（）A.rear=rear+1B.rear=(rear+1)%(m+1)C.rear=(rear+1)%mD.rear=(rear-1)%m二、多项选择题（总共5题，每题4分，每题的选项中，有两个或两个以上是正确的，请将正确答案的序号填在括号内，多选、少选、错选均不得分）1.下列关于栈的叙述中，正确的是（）A.栈顶元素最先被删除B.在栈中只能插入元素C.栈底元素最后被删除D.栈是先进后出的线性表2.下列哪些是图的遍历方法（）A.深度优先搜索B.广度优先搜索C.前序遍历D.后序遍历3.一棵二叉树的叶子结点数为n0，度为2的结点数为n2，则有（）A.n0=n2+1B.n2=n0+1C.n0=n2-1D.n2=n0-14.以下属于内部排序的是（）A.冒泡排序B.快速排序C.归并排序D.外部排序5.以下哪些是线性结构（）A.线性表B.栈C.队列D.树三、判断题（总共10题，每题2分，判断下列各题，正确的在括号内打“√”，错误的打“×”）1.线性表的链式存储结构优于顺序存储结构。（）2.队列是一种先进后出的线性表。（）3.图的邻接矩阵一定是对称矩阵。（）4.完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。（）5.二叉排序树的中序遍历序列是有序的。（）6.折半查找适用于有序的顺序表。（）7.稀疏矩阵压缩存储后，失去了随机存取的特性。（）8.排序算法中的比较次数越少，时间复杂度越低。（）9.数据的逻辑结构是指数据在计算机内存中的存储方式。（）10.循环队列中，front指向队头元素，rear指向队尾元素的下一个位置。（）四、简答题（总共3题，每题10分）1.简述线性表顺序存储结构和链式存储结构的优缺点。2.简述图的深度优先搜索和广度优先搜索的基本思想。3.简述排序算法的稳定性，并举例说明一个稳定的排序算法和一个不稳定的排序算法。