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

第1页学院：专业班级：姓名：学院：专业班级：姓名：学号：装订线内不要答题学院/专业：__________姓名：__________学号：__________注意事项：1、本试卷满分100分。2、考试时间120分钟。题号一二三四五六七得分得分评阅人一、单项选择题（总共10题，每题3分，每题只有一个正确答案，请将正确答案填入括号内）1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表2.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.403.深度为5的满二叉树有（）个叶子结点。A.16B.15C.32D.314.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。A.39B.52C.111D.1195.对线性表进行折半查找时，要求线性表必须（）。A.以顺序方式存储B.以顺序方式存储且数据元素有序C.以链式方式存储D.以链式方式存储且数据元素有序6.若进栈序列为1，2，3，4，进栈过程中可以出栈，则（）不可能是一个出栈序列。A.3，4，2，1B.2，4，3，1C.1，4，2，3D.4，3，2，17.一个具有n个顶点的无向图最多有（）条边。A.n(n-1)/2B.n(n+1)/2C.nD.n(n-1)8.已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（）。A.将邻接矩阵第i行元素全部置为0B.将邻接矩阵第i列元素全部置为0C.将邻接矩阵第i行第i列元素全部置为0D.将邻接矩阵第i行元素全部置为19.对于一个具有n个顶点的连通图，其生成树的边数为（）。A.nB.n+1C.n-1D.2n10.以下排序方法中，（）是稳定的排序方法。A.快速排序B.堆排序C.归并排序D.希尔排序二、多项选择题（总共5题，每题4分，每题有多个正确答案，请将正确答案填入括号内，多选、少选、错选均不得分）1.以下哪些是数据结构中逻辑结构的类型（）。A.集合结构B.线性结构C.树形结构D.图状结构E.物理结构2.下列关于栈的叙述中，正确的是（）。A.栈顶元素最先能被删除B.栈底元素最后才能被删除C.栈底元素是固定不变的D.栈为空时，栈顶指针的值为NULLE.栈是先进后出的线性表3.一棵二叉树的前序遍历序列为ABCDEFG，中序遍历序列为CBAEDGF，则其后序遍历序列为（）。A.CBEFGDAB.CBFEGDAC.CBEFDAD.CBFEDAE.CBEFADG4.以下哪些算法的时间复杂度是O(n)（）。A.选择排序B.插入排序C.冒泡排序D.快速排序E.归并排序5.对于哈希表，以下说法正确的是（）。A.哈希表能快速进行查找B.哈希表的装填因子小于1C.哈希表可能会产生冲突D.哈希表的查找效率与哈希函数有关E.哈希表的存储单元大小是固定的三、判断题（总共10题，每题2分，请判断对错，在括号内打√或×）1.数据元素是数据的基本单位，数据项是数据的最小单位。（）2.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）3.线性表的链式存储结构适用于频繁插入和删除操作的应用场景。（）4.完全二叉树中，若一个结点没有左孩子，则它必然是叶结点。（）5.折半查找的平均查找长度与待查找元素在表中的位置有关。（）6.队列是一种先进后出的线性表。（）7.图的遍历算法中，深度优先搜索和广度优先搜索的时间复杂度均为O(V+E)。（）8.任何一个无向连通图的最小生成树是唯一的。（）9.排序算法的稳定性是指排序前后相同关键字的相对位置不变。（）10.哈希表的查找效率主要取决于哈希函数和处理冲突的方法。（）四、简答题（总共3题，每题10分，请简要回答问题）1.简述线性表顺序存储结构和链式存储结构的优缺点。2.已知一个二叉树的中序遍历序列和后序遍历序列，如何重建该二叉树？请简述步骤。3.简述快速排序的基本思想和平均时间复杂度，并说明其在最坏情况下的时间复杂度及原因。五、算法设计题（总共2题，每题15分，请设计算法解决以下问题）1.设计一个算法，判断一个