北京理工大学《数据结构》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，5，则栈的不可能的输出序列是（）。A.5，4，3，2，1B.4，5，3，2，1C.4，3，5，1，2D.1，2，3，4，55.若一棵二叉树具有10个度为2的结点，则该二叉树的叶结点个数是（）。A.9B.11C.12D.不确定6.设哈夫曼树中的叶结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A.2m-1B.2mC.2m+1D.4m7.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。A.nB.(n-1)×(n-1)C.n×nD.(n+1)×(n+1)8.深度为k的完全二叉树至少有（）个结点。A.2k-1B.2kC.2k+1D.2k-29.对长度为n的线性表进行二分查找，在最坏情况下所需要的比较次数为（）。A.log2nB.n/2C.nD.n+110.下列排序方法中，平均时间复杂度为O(nlogn)且空间复杂度为O(1)的是（）。A.快速排序B.堆排序C.归并排序D.冒泡排序二、多项选择题（总共5题，每题4分，每题有两个或两个以上正确答案，请将正确答案填入括号内）1.以下哪些是线性结构（）。A.顺序表B.栈C.队列D.二叉树2.下列关于栈的叙述中，正确的是（）。A.栈顶元素最先能被删除B.栈底元素最后才能被删除C.栈底元素是最先被插入的D.栈是先进后出的线性表3.一棵二叉树的前序遍历序列为ABCDEFG，中序遍历序列为CBAEDGF，则后序遍历序列为（）。A.CBEFDGAB.FEDCBAC.CBFEDGAD.ABCDEFG4.下列哪些算法的平均时间复杂度是O(n)（）。A.冒泡排序B.选择排序C.插入排序D.快速排序5.对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为（）。A.O(1)B.O(n)C.O(logn)D.O(n)三、判断题（总共10题，每题2分，判断对错，对的打√，错的打×）1.线性表的链式存储结构优于顺序存储结构。（）2.栈和队列都是操作受限的线性表。（）3.完全二叉树一定是满二叉树。（）4.哈夫曼树的带权路径长度最小。（）5.图的邻接矩阵存储方式只适用于无向图。（）6.任何一个递归算法都可以转换成非递归算法。（）7.排序算法中的比较次数越少，算法效率越高。（）8.顺序查找法适用于任何存储结构的线性表。（）9.二叉排序树的中序遍历序列是一个有序序列。（）10.线性表的长度是指线性表中数据元素的个数。（）四、简答题（总共3题，每题10分）1.简述顺序表和链表的优缺点。2.简述深度优先搜索（DFS）和广度优先搜索（BFS）遍历图的基本思想，并说明它们在应用场景上的区别。3.简述快速排序的基本思想，并分析其平均时间复杂度和最坏时间复杂度。五、算法设计