数据结构期末考试试卷

数据结构期末考试试卷知识点总结 一、判断题 1. 线性表的逻辑顺序与存储顺序总是一致的。 知识点：线性表的逻辑顺序和存储顺序不一定一致，例如链表的逻辑顺序是根据结点的值来排序的，而存储顺序是根据结点的存储位置来排序的。 2. 线索二叉树中，任一结点均有指向前趋和后继的线索。 知识点：线索二叉树中，不一定每个结点都有指向前趋和后继的线索，一般只有叶子结点没有线索。 3. 栈、队列、数组和串都是线性结构。 知识点：栈、队列、数组和串都是线性结构，它们都可以用链表或数组来实现。 4. KMP 算法是一个不需要回溯的字符串模式匹配算法。 知识点：KMP 算法是一种字符串模式匹配算法，它可以在 O(n) 时间复杂度内完成模式匹配，不需要回溯。 5. 图的生成树是该图的极小连通子图。 知识点：图的生成树是指该图的极小连通子图，它是图的最小连通子图。 6. 树的后序遍历序列与其对应二叉树的后序遍历序列相同。 知识点：树的后序遍历序列不同于其对应二叉树的后序遍历序列，后者是指二叉树的后序遍历序列。 7. 二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。 知识点：二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值，但这只是二叉排序树的一种特殊情况。 8. 如果某排序算法是不稳定，则该排序算法没有实用价值。 知识点：某排序算法是不稳定的，不一定意味着该排序算法没有实用价值，例如快速排序算法就是不稳定的，但它仍然是一种高效的排序算法。 9. 稀疏矩阵压缩存储后，就会失去随机存取功能。 知识点：稀疏矩阵压缩存储后，确实会失去随机存取功能，但可以使用索引来实现随机存取。 10. 归并排序可以使用递归和非递归两种方法实现。 知识点：归并排序可以使用递归和非递归两种方法实现，对于大规模数据，可以使用非递归方法来提高效率。 二、填空题 1. 设源串 s=“bababaaba”，模式串 p=“babaa”，按照 KMP 算法进行模式匹配，当“4321ssss”=“4321pppp”，而55ps ≠时，5s 应与p3比较。 知识点：KMP 算法是一种字符串模式匹配算法，它可以在 O(n) 时间复杂度内完成模式匹配。 2. 下列算法的时间复杂性是 O(n 1/2 )。 知识点：该算法的时间复杂性是 O(n 1/2 )，它是一种特殊的时间复杂度。 3. 表达式 3/(x+2)-8 所对应的后缀表达式是 3 x 2 + / 8 -。 知识点：后缀表达式是一种表示式，用于表示算术表达式。 4. 假设以一维数组2/1nnS 作为 n 阶对称距阵 A 的存储空间，以行序为主序存储 A 的下三角，则元素 A[5][8] 的值存储在 S[41] 中。 知识点：对称矩阵的存储可以使用一维数组来实现，元素的存储位置可以通过行序或列序来确定。 5. 下列函数的功能是实现两个字符串的比较，试根据字符串比较运算的定义，完善该函数。 知识点：该函数的功能是实现两个字符串的比较，可以使用字符串比较运算的定义来完善该函数。 6. 最坏情况下，堆排序的时间复杂性为 nlog 2n。 知识点：堆排序的时间复杂性为 O(nlogn)，在最坏情况下，为 nlog 2n。 7. 具有 100 个结点的完全二叉树，其叶子结点数为 50。 知识点：完全二叉树是一种特殊的二叉树，它的叶子结点数等于总结点数的一半。 8. 利用拓扑排序算法可以判断一个有向图是否存在回路。 知识点：拓扑排序算法可以用于判断一个有向图是否存在回路。 9. 对于具有 100 个记录的文件，用顺序查找法查找索引表和块内元素，假定每块长度均为 10 个元素，则平均查找长度为 10。 知识点：顺序查找法是一种查找算法，它的平均查找长度可以通过计算来得到。 三、简要回答 1. 评价一个排序算法好坏的标准是什么？你知道有哪些排序算法？试比较它们各自的性能。 知识点： Sorting algorithm 的评价标准有正确性、逻辑健壮性、多类数据测试、可读性、格式结构化、高效、低存储等。常见的排序算法有冒泡排序、选择排序、插入排序、归并排序、快速排序等，每种算法都有其优缺。 2. 图的存储方法主要有哪些？试举例具体说明图的存储结构；并说明 Prim，Kruskal，Dijkstra，Floyd 算法的功能。 知识点：图的存储方法主要有邻接表和邻接矩阵两种。Prim 算法用于求最小生成树，Kruskal 算法用于求最小生成树，Dijkstra 算法用于求图中从某个源点到其余各顶点的最短路径，Floyd 算法用于求每一个顶点之间的最短路径。 3. 已知一组关键字为（26，36，41，38，44，15，68，12，06，51，25）， Hash 函数定义为：H(key) = key%13。用拉链法解决冲突，建立 Hash 表，分别计算查找成功和查找失败情况下的平均查找长度。 知识点： Hash 表是一种查找表，它可以使用拉链法解决冲突。查找成功和查找失败情况下的平均查找长度可以通过计算来得到。 四、折半查找算法 知识点：折半查找算法是一种查找算法，它可以在 O(logn) 时间复杂度内完成查找。