串数组自测卷答案详解与关键知识点梳理

本资源是一份关于第4～5章串和数组自测卷的答案文档，涵盖了多个相关知识点。章节内容包括串论基础知识和数组在计算机存储中的组织方式。 1. 空串与空白串：空串是指长度为0的串，不包含任何字符；而空白串则是由一个或多个空格字符组成，虽然长度可能大于0，但主要关注的是空格字符。两者区别在于空串是纯粹的字符序列长度为0，而空白串除了空字符还有其他空格字符。 2. 字符串操作：例如计算字符串"S=“A;/document/Mary.doc”"的长度，strlen(s)为20，其中特定字符的位置可以通过索引确定，如"/"字符的定位位置为3。 3. 串匹配：串的模式匹配是查找子串在目标串中的位置，模式P="cdcc"在目标串"T=“abccdcdccbaa”"中找到第6次匹配，表明了匹配算法的基本应用。 4. 串匹配算法效率：朴素匹配算法在最坏情况下需要比较字符的次数为(n-m+1)*m，其中n为主串长度，m为子串长度，这涉及到时间复杂度分析。 5. 数组存储结构：二维数组A6×8按照字节存储，计算存储量、地址等细节，涉及地址计算和存储布局的理解。对于不同的存储顺序（按行或按列），计算元素地址的方法不同。 6. 基地址与地址计算：如数组A的起始地址为1000，存储量计算、末尾元素地址、以及按行或列存储时特定元素的地址计算，显示了数组在内存中的物理布局。 7. 数组索引与地址计算：考研题目中的例子，给出了数组a[1…60, 1…70]的地址计算，利用列优先存储顺序公式计算元素a[32,58]的地址，强调了对数组索引的理解。 8. 稀疏矩阵表示：三元素组表用于表示稀疏矩阵的非零元素，每个结点包含行下标、列下标和元素值，展示了矩阵数据结构的高效存储方式。 9. 广义表操作：对广义表进行GetHead和GetTail操作的示例，展示列表数据结构的操作和理解。 通过这份自测卷答案，学习者可以深入理解串论的匹配算法、数组在内存中的存储组织、以及广义表等高级数据结构的使用。这些知识点是计算机科学特别是IT领域的重要基础知识，对于编程和算法设计具有重要意义。