四川电影电视学院《数据结构（影视流处理优化版）》2024-2025 学年第一学期期末试卷

班级班级学号姓名本科．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．密．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．封．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．线．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．试卷说明：1、试卷满分100分，120分钟完成试卷；2、钢笔或圆珠笔直接答在试题中（除题目有特殊规定外）；3、答卷前将密封线内的项目填写清楚。题号一二三四五总分合分人复核人满分100得分一、精心挑选,(本大题总共15小题，每题2分，共30分）1.以下哪种数据结构最适合用于实现栈？A.数组B.链表C.队列D.树2.对于一个具有n个元素的线性表，若采用顺序存储结构，则访问第i个元素的时间复杂度为？A.O(1)B.O(n)C.O(logn)D.O(n)3.若要在一个有序数组中快速查找某一元素，最佳的查找算法是？A.顺序查找B.二分查找C.哈希查找D.分块查找4.深度为5的完全二叉树的节点数最多为？A.15B.16C.31D.325.以下关于二叉排序树的说法，错误的是？A.左子树上所有节点的值均小于根节点的值B.右子树上所有节点的值均大于根节点的值C.中序遍历二叉排序树可得到一个有序序列D.插入和删除操作的时间复杂度均为O(n)6.对于一个循环队列，若队头指针front，队尾指针rear，队列容量为m，则队列中元素个数为？A.rear-frontB.(rear-front+m)%mC.rear-front+1D.(rear-front-1+m)%m7.若用链表表示一个队列，则应该选用？A.单链表B.双向链表C.循环链表D.带尾指针的循环链表8.以下哪个排序算法的平均时间复杂度最低？A.冒泡排序B.选择排序C.插入排序D.快速排序9.数据结构中，与所使用的计算机无关的是数据的？A.存储结构B.物理结构C.逻辑结构D.物理和存储结构10.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主序存储，a11为第一个元素，其存储地址为1，每个元素占1个存储单元，则a85的地址为？A.33B.32C.34D.3511.已知一棵二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则后序遍历序列为？A.DEBFCAB.DFEBCAC.DBEACFD.BDEFAC12.哈希表的平均查找长度与下列哪项有关？A.哈希函数B.哈希表的装填因子C.哈希表的大小D.以上都是13.下列数据结构中，属于非线性结构的是？A.栈B.队列C.二叉树D.线性表14.对n个记录的文件进行快速排序，所需要的辅助存储空间为？A.O(n)B.O(logn)C.O(n)D.O(1)15.若一棵完全二叉树有768个节点，则该二叉树中叶节点的个数是？A.384B.做385C.386D.387二、准确判断,(本大题总共5题，每题4分，共20分)1.线性表的顺序存储结构优于链式存储结构。2.二叉排序树的中序遍历序列一定是有序的。3.对于哈希表，装填因子越大，发生冲突的可能性越小。4.任何一个递归算法都可以转换成非递归算法。5.顺序查找法适用于有序表的查找。三、合理填空,(本大题总共6题，每题4分，共24分)1.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括数据的____结构、存储结构及数据的运算。2.栈的主要操作有入栈和____。3.队列的操作特点是____。4.一棵二叉树第i（i≥1）层上至多有____个节点。5.快速排序在平均情况下的时间复杂度为____。6.若要将一个稀疏矩阵压缩存储，常用的方法有____和十字链表法。四、详细解答,(本大题总共2题，每题6分，共12分)1.简述顺序查找和二分查找各自的优缺点及适用场景。2.请描述一下如何实现一个简单的栈