东北师范大学《数据结构与算法》2025 学年第一学期期末试卷(B).pdf

第1页，共3页 站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。密封线 东北师范大学数据结构与算法2025 学年第一学期期末试卷(B)题号题号 一一 二二 三三 四四 总分总分 得分得分 注意事项注意事项 1.考生须在答题卡指定位置填写姓名、学号、专业等信息，在试卷上作答无效。2.答题时须使用黑色签字笔或钢笔，字迹清晰，卷面整洁。3.考试结束后，将试卷、答题卡一并交回，不得携带出考场。一、精心选一选（本大题总共 15 小题，每题 2 分，共 30 分）1.以下哪个不是数据结构的基本逻辑结构？A.集合结构 B.线性结构 C.树形结构 D.动态结构 2.线性表的顺序存储结构中，元素之间的逻辑关系是通过什么体现的？A.指针 B.数组下标 C.链表节点 D.哈希值 3.在一个长度为 n 的顺序表中，删除第 i 个元素（1in）时，需要移动多少个元素？A.n-i B.n-i+1 C.i D.i-1 4.栈的特点是？A.先进先出 B.后进先出 C.随机进出 D.按优先级进出 5.队列的操作原则是？A.先进先出 B.后进先出 C.随机进出 D.按优先级进出 6.若进栈序列为 1,2,3,4，进栈过程中可以出栈，则下列不可能的出栈序列是？A.1,4,3,2 B.2,3,4,1 C.3,1,4,2 D.3,4,2,1 7.深度为 5 的完全二叉树的节点数最多为？第2页，共3页 站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。密封线 A.15 B.16 C.31 D.32 8.已知二叉树的前序遍历序列为 ABDECF，中序遍历序列为 DBEAFC，则后序遍历序列为？A.DEBFCA B.DBEAFC C.ABDCEF D.ABCDEF 9.图的邻接矩阵表示法适用于哪种图？A.有向图 B.无向图 C.有向图和无向图 D.稀疏图 10.对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是？A.n B.nn C.n-1 D.(n-1)(n-1)11.下列排序算法中，平均时间复杂度为 O(n2)的是？A.快速排序 B.归并排序 C.冒泡排序 D.堆排序 12.对关键字集合 K=60,40,49,23,25,13,95,196,85，以第一个关键字 60 为基准进行一趟快速排序的结果是？A.23,40,49,25,13,60,85,95,196 B.13,23,25,40,49,60,85,95,196 C.13,23,25,40,49,60,95,85,196 D.13,23,25,40,49,60,196,95,85 13.哈希表的平均查找长度主要取决于？A.哈希表的大小 B.哈希函数 C.关键字的个数 D.装填因子 14.以下哪种数据结构适合用于实现优先队列？A.栈 B.队列 第3页，共3页 站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。密封线 C.堆 D.链表 15.数据结构中，与所使用的计算机无关的是数据的？A.存储结构 B.物理结构 C.逻辑结构 D.物理和存储结构 二、准确填一填（本大题总共 5 题，每题 4 分，共 20 分）1.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括数据的_结构、存储结构和数据的运算。2.顺序表中逻辑上相邻的元素，其物理位置_。3.栈顶元素的位置是_。4.二叉树的第 i 层上最多有_个节点（i1）。5.对于一个具有 n 个顶点的连通图，其生成树的边数为_。三、细心判一判（本大题总共 6 题，每题 4 分，共 24 分）1.数据的逻辑结构决定了数据的存储结构。（）2.线性表的顺序存储结构中插入和删除操作效率较高。（）3.栈和队列都是特殊的线性表。（）4.完全二叉树一定是满二叉树。（）5.图的深度优先搜索和广度优先搜索遍历结果一定相同。（）6.排序算法的时间复杂度与数据的初始状态无关。（）四、灵活答一答（本大题总共 2 题，每题 6 分，共 12 分）1.简述线性表的两种存储结构及其优缺点。2.简述图的邻接表表示法及其适用场景。五、综合用一用(14 分)1.已知一个有序表为10,20,30,40,50,60,70,80,90，请设计一个折半查找算法，查找关键字为 50 的元素，并给出查找过程。2.设计一个算法，将一个带头节点的单链表逆置。要求：描述算法的基本思想，并给出主要代码片段。