北京科技大学《数据结构》2024 - 2025 学年第一学期期末试卷

（第2页）制卷人签名：制卷日期制卷人签名：制卷日期：审核人签名：：审核日期：………………………………………………装……订……线…………………学院专业/班级学号姓名题号一二三四五六七八总分阅卷教师得分………………一、单项选择题（总共10题，每题3分，每题只有一个正确答案，请将正确答案填写在括号内）1.以下关于线性表的说法，错误的是（）A.线性表是一种线性结构B.线性表可以采用顺序存储或链式存储C.线性表的插入和删除操作在顺序存储下效率更高D.线性表的元素具有一对一的逻辑关系2.已知一个栈的进栈序列为1,2,3,4,5，则下列不可能是其出栈序列的是（）A.5,4,3,2,1B.4,3,5,1,2C.2,1,3,4,5D.3,2,1,5,43.深度为5的完全二叉树的结点数不可能是（）A.15B.16C.17D.184.对有序表(2,5,7,10,14,15,18,23,35,41,52)进行折半查找，查找元素10的比较次数是（）A.2B.3C.4D.55.若一棵二叉树的前序遍历序列为A,B,C,D，中序遍历序列为B,A,D,C，则后序遍历序列为（）A.B,D,C,AB.D,B,C,AC.D,C,B,AD.B,C,D,A6.以下排序算法中，平均时间复杂度为O(n)的是（）A.快速排序B.归并排序C.冒泡排序D.堆排序7.哈希表的平均查找长度主要取决于（）A.哈希表的大小B.哈希函数C.哈希表的装填因子D.以上都是8.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A.nB.nC.n(n-1)D.(n-1)9.以下关于图的说法，正确的是（）A.连通图的生成树是唯一的B.无向图的邻接表表示比邻接矩阵表示更节省空间C.有向图的拓扑排序结果是唯一的D.最短路径问题只能用Dijkstra算法求解10.数据结构中，与所使用的计算机无关的是数据的（）A.存储结构B.物理结构C.逻辑结构D.物理和存储结构二、多项选择题（总共5题，每题4分，每题有两个或两个以上正确答案，请将正确答案填写在括号内，多选、少选、错选均不得分）1.下列关于栈和队列的说法，正确的有（）A.栈是后进先出的数据结构B.队列是先进先出的数据结构C.栈和队列都可以采用顺序存储和链式存储D.栈和队列的操作都只在一端进行2.下列哪些是二叉排序树的性质（）A.左子树上所有结点的值均小于根结点的值B.右子树上所有结点的值均大于根结点的值C.左右子树也分别是二叉排序树D.中序遍历二叉排序树可以得到一个有序序列3.以下哪些排序算法是稳定的（）A.冒泡排序B.选择排序C.插入排序D.归并排序4.对于一个有向图，以下说法正确的是（）A.强连通图的任意两个顶点之间都有路径B.有向图的邻接矩阵中，第i行非零元素的个数表示顶点i的出度C.有向图的邻接矩阵中，第j列非零元素的个数表示顶点j的入度D.有向图的拓扑排序结果可能不唯一5.以下关于数据结构的说法，正确的有（）A.数据结构包括数据的逻辑结构和存储结构B.算法的时间复杂度与数据的存储结构有关C.数据的逻辑结构决定了数据的运算D.数据结构是相互之间存在一种或多种特定关系的数据元素的集合三、判断题（总共10题，每题2分，请判断下列说法的对错，在括号内打“√”或“×”）1.线性表的顺序存储结构优于链式存储结构。（）2.空栈和空队列都是没有元素的栈和队列。（）3.完全二叉树一定是满二叉树。（）4.折半查找只能用于有序表。（）5.二叉排序树的删除操作比插入操作复杂。（）6.快速排序在最坏情况下的时间复杂度为O(n)。（）7.哈希表中不存在哈希冲突。（）8.有向图的邻接表表示比邻接矩阵表示更适合求顶点的入度。（）9.图的深度优先搜索和广度优先搜索得到的生成树是相同的。（）10.数据结构的设计会影响算法的效率。（）四、简答题（总共3题，每题10分）1.简述顺序表和链表的优缺点。2.简述二叉排序树的插入和删除操作的基本步骤。3.简述