数据结构期末复习精华：选择、填空题解析

"这是一份关于数据结构期末复习的模拟试题，包含了多项选择题、填空题，涵盖了数据结构的基础概念、线性表、栈、队列、二叉树、图等核心知识点，旨在帮助学生备考。" 1. 计算量的大小通常被称为算法的复杂性，它分为时间复杂性和空间复杂性，是衡量算法性能的重要指标。 2. 数据结构按逻辑关系可分为线性结构和非线性结构，线性结构如数组、链表，非线性结构如树、图。 3. 线性表的顺序存储适用于存储空间连续的情况，但插入和删除操作可能需要移动大量元素；而链接存储（链表）不需连续空间，插入和删除只需改变指针即可。 4. 静态链表中的指针通常指向下一个元素的地址，而不是内存地址或数组下标，也不直接表示左右孩子地址，常见于循环链表。 5. 栈遵循“后进先出”(LIFO)原则，而合法的出栈序列必须保持这一特性。选项A、B、C符合，D选项2在1之前出栈，违反了LIFO原则。 6. 栈和队列都是线性数据结构，它们的共同点在于仅允许在端点（栈顶或队尾）进行插入和删除操作。 7. 中缀表达式转前缀表达式，运算符通常放在操作数前面。原中缀表达式A+B*C-D/E的前缀形式为-+A*B*C/DE。 8. 正确的结论是：①只有一个结点的二叉树的度为0；④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。因此，答案是D。 9. 对于无向图的深度优先遍历，从顶点a开始，按照访问顺序可以得到不同的序列。选项B、C、D均有可能，具体序列取决于遍历顺序，而A选项的序列不正确，因为b在e之前，但(e,b)不在边集中。 10. 静态查找表通常是指预先构建好的表，查找操作固定，而动态查找表则允许在运行时进行插入和删除，所以它们的主要区别在于操作的不同。 二、填空题 1. 算法的时空复杂性是评价其效率的重要指标，包括时间复杂度和空间复杂度。 2. 给定程序段的时间复杂度是O(n)，因为循环会执行n次。 3. 当线性表的存取速度要求最快时，适合使用顺序表，因为顺序表可以直接通过下标访问元素，而无需像链表那样遍历。 这份复习题集涵盖了数据结构的基础知识，对于理解数据结构及其相关操作非常有帮助，适合考生进行考前准备。