数据结构是计算机科学中的核心课程,它探讨了数据如何组织和管理,以便高效地执行各种操作。本试卷涉及的知识点广泛,涵盖了数据结构的基本概念、算法复杂性、链表、栈、队列、二叉树、排序、字符串、广义表、矩阵存储以及图的拓扑排序。
1. **数据结构的类型**:数据结构被分为集合、线性、树形和网状四种。集合是最基本的数据结构,包含无序元素;线性结构如数组和链表,元素间存在一对一的关系;树形结构如二叉树,元素间存在一对多的关系;网状结构如图,元素间存在多对多的关系。
2. **链表与头结点**:在单链表的第一个结点之前添加一个结点称为头结点,方便对链表进行操作。
3. **栈的操作**:向顺序栈插入元素时,需要先移动栈顶指针,然后将元素插入新位置。栈是一种后进先出(LIFO)的数据结构。
4. **循环队列的管理**:队列为空的条件是尾指针与头指针相等,队列满的条件是(尾指针+1)模队列最大长度等于头指针。
5. **二叉树的性质**:高度为h的二叉树至少有h个结点,最多有2^h-1个结点。这是关于二叉树高度与结点数量的关系。
6. **数组的存储与访问**:二维数组W占用的字节数是元素数量乘以每个元素的字节数。对于按行存储的数组,元素W[i][j]的地址可以通过首地址加上行偏移量(i * 列数 * 每元素字节数)和列偏移量(j * 每元素字节数)来计算。
7. **排序算法的选择**:快速排序在大数据量且排序码随机的情况下,通常能提供较好的性能。
8. **算法复杂性**:算法的计算量大小称为计算的复杂性,通常用时间复杂性和空间复杂性衡量。
9. **线性表的操作**:线性表的顺序存储方式在指定位置存取元素和尾部插入、删除效率较高。
10. **栈的性质**:栈的输出序列无法确定,取决于每次出栈的顺序。如果输入序列为123...n,第一个出栈的元素是n,但无法确定第i个出栈的元素。
11. **串的Next数组**:Next数组用于计算模式匹配中的部分匹配,对于串S='aaab',其Next数组值为0123。
12. **对称矩阵的压缩存储**:10阶对称矩阵以行序为主存储,a11为第一元素,地址为1,a85的地址可以通过公式计算得出,是13。
13. **广义表的操作**:在广义表LS= ((a,b,c), (d,e,f))中,取原子e的操作是head(tail(head(LS)))。
14. **树的性质**:度为4的树,若度为1、2、3、4的结点分别为4、2、1、1,叶子数(度为0的结点)可通过公式2(n0 + n1 - 1)计算,得到8。
15. **二叉树的度与结点数量**:只有一个结点的二叉树度为0,深度为K的完全二叉树的结点数小于或等于同深度的满二叉树。
16. **连通无向图的边数**:n个顶点的连通无向图至少有n-1条边。
17. **有向图的拓扑排序**:拓扑排序中Vi在Vj之前,说明没有从Vj到Vi的路径。
18. **顺序查找的平均查找长度**:在n个记录的连续顺序文件中,平均查找长度ASL为n/2。
这些知识点体现了数据结构的多样性和复杂性,包括基本数据结构的理解、操作及优化,以及对算法效率的考量。掌握这些内容对于理解和设计高效的程序至关重要。