数据结构：串与数组自测卷填空与选择题解析

本资源是一份关于数据结构第4-5章的自测卷，主要包括填空题和单选题，涵盖了数组和广义表的相关知识点。以下是对这些知识点的详细解释： **一、填空题** 1. **空串与空白串：** - 空串是指没有字符的串，而空白串则是指由空格、制表符等空白字符组成的串。题目要求识别特定字符串"S="A;/document/Mary.doc”中，空串的概念以及空格字符的处理。 2. **字符定位与模式匹配：** - 在串的处理中，子串的定位运算称为模式匹配。在模式匹配问题中，通常将待查找的串称为目标串，而要查找的模式称为预定义的模式串。题目给出了目标串"T="abccdcdccbaa"和模式"P="cdcc"，要求找出模式在目标串中的首次匹配位置。 3. **串的古典匹配算法复杂度：** - 串的古典匹配算法（如KMP算法或Boyer-Moore算法）在最坏情况下，当模式串在目标串中不完全匹配时，需要比较的字符总数是目标串长度减去模式串长度。 4. **二维数组的存储计算：** - 题目涉及二维数组的存储计算，包括存储量、首地址计算以及按行或列存储时不同元素的地址。例如，给出数组的起始地址和元素大小，可以计算出数组的总体积、末尾元素的地址以及特定元素在不同存储方式下的地址。 5. **稀疏矩阵的元素表示：** - 在稀疏矩阵表示中，元素组表中的每个结点对应一个非零元素，包含了该元素的行号、列号和值三个数据项。 **二、单选题** 1. **串的特性：** - 选择题考察了串作为一种特殊线性表的特点，选项A和C描述了存储方式，但串的特殊性在于数据元素通常是字符，因此B是正确答案。 2. **子串查找运算：** - 题目询问求子串首次出现的位置，这是模式匹配的一部分，对应的是选项B。 3. **串的操作和连接：** - 函数con和subs用于操作串，根据题目提供的操作，con(subs(s1,2,len(s2)),subs(s1,len(s2),2))会连接s1的第二个到len(s2)个字符和s1从len(s2)到最后两个字符，结果应该是BCDEFG，对应于选项C。 4. **二维数组地址计算：** - 题目涉及数组元素的地址计算，给出了行数、列数、存储单位和基地址，需要根据主序顺序确定第32行第58列的存储地址。 通过这份自测卷，学习者可以巩固和测试自己对数组和广义表在数据结构中的理解，包括字符串操作、存储结构、稀疏矩阵和基本算法等方面的知识。