本资源是一份针对数据结构的复习材料，包括选择题和填空题，旨在帮助学生准备期末考试。以下是各题目的知识点总结：
1. **填空题**
- **第1题**：线性表的**顺序**存储结构支持随机存取，因为它通过连续的内存地址可以直接访问任一位置的元素。
- **第2题**：栈的出栈顺序遵循后进先出原则，A，B，C的出栈顺序共有**3**种可能：CBA、BCA或CAB。
- **第3题**：循环队列的元素数量等于队尾指针减去队头指针取模50的结果，即(19-11)%50 = 8，因此有**8**个元素。
- **第4题**：二维数组按行优先存储，元素地址计算公式是(行号-1)*列数*元素大小 + (列号-1)*元素大小，所以SZ[30][48]的地址是(30-1)*70*2 + (48-1)*2 = 4582。
- **第5题**：对于字符串"S=“software”"，其子串数目为所有可能的子串数量，即2^n - 1，n为字符数，这里是31。
- **第6题**：树的定义中，**根节点**是唯一的。
- **第7题**：无向图的最少边数与顶点数成对出现，因为任何两个不同的顶点之间可能存在一条边，所以最少边数是n-1。
- **第8题**：有向图的邻接矩阵表示法中，每个顶点对应一行或一列，如果有n个顶点，最坏情况下每行每列都有n个元素，所以需要n^2的空间。
- **第9题**：折半查找法要求查找表是有序的，数据序列必须**递增或递减**排列。
- **第10题**：内部排序方法按操作原理分类：**直接插入排序**、交换排序（如冒泡排序、快速排序）、选择排序、归并排序和基数排序。
2. **单项选择题**
- **第1题**：线性表顺序存储的地址可以不连续，但通常为了方便访问，连续存储更常见，答案是(B)。
- **第2题**：栈是**后进先出**的结构，答案是(B)。
- **第3题**：栈的输出遵循后进先出原则，n-i+1表示第i个输出元素是第n个元素进入栈后最先出栈的，答案是(D)。
- **第4题**：深度为4的完全二叉树最多有2^(4-1)+1=16个结点，答案是(B)。
- **第5题**：删除顺序表第i个元素，其他元素需向前移动i-1次，答案是(B)。
- **第6题**：堆栈操作遵循后进先出，故删除三次后，最先入栈的元素在顶部，答案是(F)。
- **第7题**：满二叉树的叶子结点数等于层数，深度为7的满二叉树有7层，叶子结点数为2^7-1=128，这里可能是题目错误，应选(A)32（根据满二叉树性质，最下一层的叶子结点数是上一层的一半加1）。
这些题目涵盖了数据结构的基本概念，如存储结构（顺序和链式）、基本操作（栈和队列）、树和图的特性、查找算法和排序方法，以及二叉树的相关知识。通过解答这些问题，学生可以巩固和测试他们在数据结构课程中的学习成果。
我的内容管理
展开
