常州大学《数据结构》2024 - 2025 学年第一学期期末试卷

（第2页）制卷人签名：制卷日期制卷人签名：制卷日期：审核人签名：：审核日期：………………………………………………装……订……线…………………学院专业/班级学号姓名题号一二三四五六七八总分阅卷教师得分………………一、单项选择题（总共10题，每题3分，每题只有一个正确答案，请将正确答案填入括号内）1.以下关于数据结构的叙述中，正确的是（）A.数据的逻辑结构独立于其存储结构B.数据的存储结构独立于其逻辑结构C.数据的逻辑结构唯一决定其存储结构D.数据结构仅由其逻辑结构和存储结构决定2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表3.栈和队列的共同点是（）A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点4.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）A.39B.52C.111D.1195.设哈夫曼树中的叶结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A.2m-1B.2mC.2m+1D.4m6.对n个关键字进行快速排序，最大递归深度为（）A.nB.n/2C.log2nD.nlog2n7.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率8.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(n)的是（）A.快速排序B.冒泡排序C.堆排序D.归并排序9.若对线性表的最常用操作是访问第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式是（）A.单链表B.双向链表C.单循环链表D.顺序表10.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A.nB.(n-1)C.n-1D.n二、多项选择题（总共5题，每题4分，每题有多个正确答案，请将正确答案填入括号内，多选、少选、错选均不得分）1.以下属于数据的逻辑结构的有（）A.线性结构B.树形结构C.图状结构D.顺序存储结构E.链式存储结构2.以下关于栈的说法正确的是（）A.栈是一种后进先出的线性表B.栈有栈顶和栈底两个端点C.栈只能在栈顶进行插入和删除操作D.栈可以用于实现函数调用E.栈的操作包括入栈、出栈和取栈顶元素等3.下列哪些算法是稳定的排序算法（）A.冒泡排序B.快速排序C.归并排序D.堆排序E.插入排序4.对于一棵二叉排序树，以下说法正确的是（）A.左子树上所有结点的值均小于根结点的值B.右子树上所有结点的值均大于根结点的值C.中序遍历二叉排序树可以得到一个有序序列D.插入操作不会破坏二叉排序树的性质E.删除操作不会破坏二叉排序树的性质5.以下关于图的说法正确的是（）A.图分为有向图和无向图B.图的边可以有权值C.图的存储方式有邻接矩阵和邻接表等D.深度优先搜索和广度优先搜索是图的遍历算法E.最小生成树问题是图的重要应用之一三、判断题（总共10题，每题2分，请判断下列说法的对错，正确的打√，错误的打×）1.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。（）2.线性表的链式存储结构优于顺序存储结构。（）3.栈和队列都是线性结构。（）4.完全二叉树一定是满二叉树。（）5.哈夫曼树的带权路径长度最短。（）6.快速排序在最坏情况下的时间复杂度为O(n)。（）7.散列表的平均查找长度与散列函数无关。（）8.排序算法的时间复杂度与数据的初始状态无关。（）9.双向链表比单向链表更适合进行插入和删除操作。（）10.图的邻接矩阵表示法适用于边数较多的图。（）四、简答题（总共3题，每题10分，请简要回答以下问题）1.简述线性表的顺序存储结构和链式存储结构的优缺点。2.简述深度优先搜索和广度优先搜索的基本思想，并说明它们在图遍历中的应用场景。3.简述排序算法的稳定性，并举例说明哪些排序算法是稳定的，哪些是不稳定的。五、算法设计题（