南京传媒学院《数据可视化技术》2023-2024学年期末试卷

学校________________班级____________姓名____________考场____________准考证号学校________________班级____________姓名____________考场____________准考证号…………密…………封…………线…………内…………不…………要…………答…………题…………第1页，共3页南京传媒学院《数据可视化技术》

2023-2024学年期末试卷题号一二三总分得分批阅人一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、在一个采用顺序存储结构的线性表中，若要在第i个位置插入一个新元素，需要将第i个位置及之后的元素依次向后移动一位。以下关于插入操作的时间复杂度的描述，哪一项是正确的？A.时间复杂度为O(1)B.时间复杂度为O(n)C.时间复杂度为O(logn)D.时间复杂度为O(nlogn)2、二叉树的性质和遍历方式可以用于解决很多实际问题，以下关于它们的应用的说法中，错误的是？（）A.二叉搜索树可以用于实现高效的查找、插入和删除操作，适用于数据库索引和文件系统等。B.平衡二叉树可以用于解决二叉搜索树的不平衡问题，提高查找效率，适用于大规模数据的存储和管理。C.二叉树的遍历方式可以用于实现二叉树的复制、遍历和序列化等操作，适用于数据备份和传输等。D.二叉树的性质和遍历方式只适用于理论研究，在实际应用中没有实际价值。3、设有两个串p和q，求q在p中首次出现的位置的运算称为：A.连接B.模式匹配C.求子串D.求串长4、在一个哈希表中，解决冲突的方法不包括：A.开放定址法B.再哈希法C.建立索引表D.链地址法5、在一个具有n个元素的顺序存储的线性表中，删除第i个元素（1<=i<=n），平均需要移动多少个元素？（）A.n-iB.iC.(n-i)/2D.n/26、在一个具有n个元素的顺序表中，删除第i个元素（1<=i<=n），需要移动的元素个数最多为（）。A.i-1B.n-iC.n-i+1D.n-17、一棵二叉树的先序遍历序列为ABDECFGH，中序遍历序列为DBEAFCGH，则该二叉树的后序遍历序列为（）。A.DEBFGCHAB.DEBFHGCAC.DEBHGFCAD.DEBHFCGA8、队列是另一种特殊的线性数据结构，它遵循先进先出（FIFO）的原则。以下关于队列的说法中，错误的是？（）A.队列可以用数组或链表实现。B.队列的插入操作在队尾进行，删除操作在队首进行。C.队列可以用于实现任务调度、消息传递等。D.队列的容量是无限的，可以存储任意数量的元素。9、在一个具有n个节点的带权有向图中，若存在负权边，以下哪种最短路径算法可能不适用？A.迪杰斯特拉算法B.贝尔曼-福特算法C.弗洛伊德算法D.以上都适用10、对于一个具有n个节点的AVL树，插入一个新节点后，调整树的平衡，其时间复杂度为？A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、在一棵二叉树中，若度为2的节点有10个，度为1的节点有20个，那么叶子节点的数量是多少？A.11B.21C.30D.无法确定12、以下关于堆的描述，正确的是：A.大顶堆中每个父节点的值都大于其子节点的值B.小顶堆中每个父节点的值都小于其子节点的值C.堆可以用顺序存储也可以用链式存储D.堆是完全二叉树13、在一个具有n个节点的二叉排序树中，进行查找操作的平均时间复杂度是多少？A.O(n)B.O(logn)C.O(nlogn)D.取决于树的形态14、若一个图的广度优先遍历序列为ABCDEFG，则其深度优先遍历序列可能为？（）A.ABDCEFGB.ACBDEFGC.ADBCEFGD.AECBDFG15、对于一个具有n个元素的循环队列，队头指针为front，队尾指针为rear，队列满的条件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front16、对于一个具有n个元素的归并排序，其时间复杂度为？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)17、图的存储方式有邻接矩阵和邻接表两种，以下关于它们的特点的说法中，错误的是？（）A.邻接矩阵适合存储稠密图，空间复杂度为O(n^2)。B.邻接表适合存储稀疏图，空间复杂度为O(n+m)，其中n是顶点数，m是边数。C.邻接矩阵的查找边的时间复杂度为O(1)。D.邻接表的插入边和删除边的时间复杂度为O(n)。18、在一个栈中，若入栈序列为1,2,3,4，且在入栈过程中可以出栈，则可能得到的出栈序列有多少种？（）A.14B.15C.16D.1719、在一个具有n个元素的链表中，访问第i个元素的时间复杂度为？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)20、在一个用顺序存储结构实现的栈中，若栈顶指针top指向栈顶元素的上一个位置，当栈为空时，top的值为？A.-1B.0C.1D.n-1（其中n为栈的最大容量）二、简答题（本大题共4个小题，共40分)1、（本题10分）在图的遍历中，如何避免重复访问节点？请说明具体方法。2、（本题10分）数组和链表在存储数据方面有哪些不同之处？各自的优缺点是什么？3、（本题10分）阐述如何在一个链表中实现冒泡排序，给出算法步骤和实现代码，并分析其时间复杂度和空间复杂度。4、（本题10分）详细阐