吉林师范大学《数据模型与决策》2021-2022学年期末试卷

站名：站名：年级专业：姓名：学号：凡年级专业、姓名、学号错写、漏写或字迹不清者，成绩按零分记。…………密………………封………………线…………第1页，共1页吉林师范大学

《数据模型与决策》2021-2022学年期末试卷题号一二三总分得分一、单选题（本大题共20个小题，每小题2分，共40分．在每小题给出的四个选项中，只有一项是符合题目要求的．）1、数组通常具有的两种基本操作是：A.插入和删除B.查找和修改C.遍历和排序D.索引和赋值2、对于一个m行n列的二维数组，按行优先存储时，元素a[i][j]（0<=i<m,0<=j<n）的地址计算公式为：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i3、在一个具有n个顶点和m条边的有向图中，使用弗洛伊德算法求所有顶点对之间的最短路径，其时间复杂度为？A.O(n^2)B.O(n^3)C.O(mn)D.O(m^2)4、在一个具有n个顶点的无向图中，若采用邻接矩阵存储，则矩阵中非零元素的个数至少为？（）A.nB.n-1C.2(n-1)D.n(n-1)/25、一棵哈夫曼树中，叶子节点的编码长度一定（）非叶子节点的编码长度。A.大于B.等于C.小于D.不小于6、广义表((a,b),c,(d,(e,f)))的长度和深度分别为：A.3和2B.3和3C.4和2D.4和37、深度为5的满二叉树的结点数为：A.16B.31C.32D.158、在一个循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，队列最大容量为MAXSIZE，若当前队列长度为n，则判断队满的条件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE9、二叉树的性质和遍历方式可以用于解决很多实际问题，以下关于它们的应用的说法中，错误的是？（）A.二叉搜索树可以用于实现高效的查找、插入和删除操作。B.平衡二叉树可以用于解决二叉搜索树的不平衡问题，提高查找效率。C.二叉树的遍历方式可以用于实现二叉树的复制、遍历和序列化等操作。D.二叉树的性质和遍历方式只适用于理论研究，在实际应用中没有实际价值。10、在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）是两种常见的方法。以下关于它们的描述，错误的是（）A.DFS使用栈来保存未访问的节点B.BFS使用队列来保存未访问的节点C.DFS可能会陷入死循环D.BFS一定能找到最短路径11、在一个具有n个顶点的无向图中，若采用邻接矩阵存储，则存储空间复杂度为？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)12、对于一个具有n个元素的堆，若要将其所有元素从小到大排序，最好的方法是？A.每次删除堆顶元素并调整B.直接使用快速排序C.先构建大顶堆再调整D.以上方法效率相同13、在一个具有n个元素的顺序表中，若要将其逆置，以下关于操作的时间复杂度的描述，哪一项是恰当的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、以下哪种数据结构可以方便地实现字符串的模式匹配操作？A.二叉树B.哈希表C.栈D.后缀树15、数据结构的应用非常广泛，以下关于它们的应用场景的说法中，错误的是？（）A.数组可以用于存储和处理大量的相同类型的数据。B.链表可以用于实现动态数据结构，如栈、队列和链表等。C.树可以用于实现文件系统、数据库索引和表达式求值等。D.数据结构只在计算机科学领域有应用，在其他领域没有实际价值。16、二叉树是一种重要的数据结构，具有多种遍历方式。对于先序遍历、中序遍历和后序遍历，以下描述错误的是（）A.先序遍历先访问根节点，然后递归遍历左子树和右子树B.中序遍历先递归遍历左子树，然后访问根节点，最后递归遍历右子树C.后序遍历先递归遍历左子树和右子树，最后访问根节点D.这三种遍历方式的结果总是相同的17、在一个具有n个节点的带权有向图中，若存在负权边，以下哪种最短路径算法可能不适用？A.迪杰斯特拉算法B.贝尔曼-福特算法C.弗洛伊德算法D.以上都适用18、对于一个满二叉树，若其高度为h，则其节点总数为多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-119、在一个哈希表中，解决冲突的方法不包括：A.开放定址法B.再哈希法C.建立索引表D.链地址法20、在数据结构中，哈弗曼编码是一种用于数据压缩的编码方式，以下关于哈弗曼编码的描述，错误的是（）A.出现频率高的字符编码较短B.编码是唯一的C.解码过程简单D.对所有数据都能达到很好的压缩效果二、简答题（本大题共4个小题，共40分)1、（本题10分）详细阐述在具有n个顶点的无向图中，如何使用广度优先搜索算法查找与指定顶点距离为k的所有顶点，并给出具体的算法步骤和代码实现。2、（本题10分）简述哈希表的哈希冲突解决方法中链地址法的优化策略及适用场景。3、（本题10分）在数据结构中，阐述如何使用树堆进行高效的合并和查找操作，给出算法步骤和实现代码，并分析其性能特点。4、（本题10分）论述在数据结构中，如何使用分治法解决复杂问题，举