广西财经学院《数据结构》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，则栈不可能的输出序列是（）。A.4321B.1234C.4132D.23415.深度为5的完全二叉树的结点数不可能是（）。A.15B.16C.17D.186.若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。A.只有eB.有e、bC.有e、cD.无法确定7.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（）。A.m-nB.m-n-1C.n+1D.条件不足，无法确定8.对n个记录的文件进行快速排序，所需要的辅助存储空间为（）。A.O(1)B.O(log2n)C.O(n)D.O(n2)9.下列排序方法中，平均时间复杂度为O(nlog2n)且稳定的排序方法是（）。A.快速排序B.堆排序C.归并排序D.基数排序10.哈希表的平均查找长度（）。A.与记录个数n有关B.与装填因子α有关C.与记录的关键字有关D.与表的结构有关二、多项选择题（总共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.二叉树的中序遍历序列是唯一的。（）7.快速排序是一种稳定的排序算法。（）8.归并排序的时间复杂度不受初始记录序列的影响。（）9.哈希表的查找效率与哈希函数无关。（）10.装填因子α越大，哈希表中发生冲突的可能性越小。（）四、简答题（总共3题，每题10分，请简要回答下列问题）1.简述线性表的顺序存储结构和链式存储结构的优缺点。2.简述栈和队列的区别，并举例说明它们在实际应用中的场景。3.简述排序算法的