数据结构学习指导45章

1、数据结构第四、五章学习指导第四章串1、相关定义：串、空串、空白串、主串、子串；2、串的存储结构：顺序串、链串；多采用顺序串；3、串中几个常见标准库函数的使用，功能、返回值；4、 什么是模式匹配？B-F算法及KMP算法的功能；5、算法设计：求串长、串的连接、串的拷贝等，参见课件中的一系列例题。第五章数组和广义表1、二维数组的顺序存储方式：按行优先、按列优先；2、二维数组中任一元素的地址计算；3、 什么是特殊矩阵的压缩存储技术？n阶对称矩阵采用压缩存储需要多少存储单元？4、稀疏矩阵的两种存储结构：三元组存储、十字链表存储；重点掌握三元组存储：三元组 的定义，矩阵与三元组的相互转换？5、广义表的定义

2、、求表长度、深度、表头、表尾、画存储结构图。第四、五章综合练习一、填空：1、串是指含有 n个字符的 有限 序列。2、设串s仁” I am a studen则串长为14。3、 假设s和t是两个给定的串，在 s中寻找与t相同的子串的过程称为模式匹配 。4、0 个字符构成的串 称为空串； 由一个或多个空白符构成的串 称为空白串。5、 一维数组中第一个元素的存储地址是200，每个元素的长度为 4,则第5个元素的地址为216 。6、一维数组的逻辑结构是线性结构，存储结构是顺序结构。对于二维数组何多维数组，可 按按行优先 和按列优先 两钟不同的方式存储。7、 数组是一种_随机访问 （随机访问、非随机访问）

3、的数据结构。&三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表 示该元素的行号、列号和 _数值。9、 广义表F=（a,F的深度为无穷_。10、 广义表 F=（a, b,（c）,（e）,f）的深度为4。二、判断：1、空格串即为空串。（错 ）2、 两个串相等必有串中各位置字符均对应相等。（对）3、串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成 的有限序列。（错）4、 函数strlen用于求字符串的长度，包括0 '（错）5、 n阶对称矩阵采用压缩存储技术只需要n（n+1）/2个存储单元。（对）6、 若一个广义表的表头为空表，则

4、此广义表亦为空表。（错）7、 广义表的表头可以为原子，也可以是子表，但表尾一定是子表。（对 ）&广义表中原子的个数即为广义表的长度。（错 ）（错）9、所有的广义表都是线性表，所有的线性表也都是广义表。10、 KMP算法的最大特点是指示主串的指针不需回溯。（对）11、 用一维数组表示矩阵可以简化对矩阵的存取操作。（错）12、 对角矩阵的特点是非零元素仅出现在矩阵的两条对角线上。（错）13、 稀疏矩阵的特点是矩阵中元素较少。（错）14、 若采用三元组压缩存储技术存储稀疏矩阵，只要将每个元素的行下标和列下标互换就可 实现矩阵的转置。（错）三、选择：1、串是（D ）。A、不少于一个字母的序列B

5、、任意个字母的序列C不少于一个字符的序列D、有限个字符的序列2、串是一种特殊的线性表，其特殊性体现在（B ）。A、可以顺序存储B、数据兀素是-个字符C可以链式存储D、数据元素可以是多个字符3、 串的长度是（D ）。A、串中不同字母的个数B、串中不同字符的个数C串中所含字符的个数且大于0D、串中所含字符的个数4、 设有两个串p和q，求q在p中首次出现的位置的运算称作（B）A、连接B、模式匹配C求子串D、求串长5、在字符串匹配中，当模式串的第j个字符与主串的第i个字符比较失败时，新一趟匹配开 始，主串的位移公式是（D ）B、i=j+1A、 i=i+1C i=i-j+1D、i=i-j+26、数组A6

6、7的每个元素占五个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中，则元素A55的地址为（A ）。A、1175B 1180C、1205D、 12107、对矩阵压缩存储是为了（ B ）。A、方便运算B、节省空间&对稀疏矩阵采用压缩存储其缺点之一是A、无法判断矩阵有多少行多少列C方便存储D、提高运算速度C ）。B、无法根据行列号查找某个矩阵元素C无法根据行列号计算矩阵元素的存储地址D、使矩阵元素之间的逻辑关系更加复杂9、数组A中每个元素的长度为 3个字节，行下标从1到8，列下标从1到10，从首地址SA 开始连续存放在存储器内，存放该数组至少需要的单元数是（C ）A、80B、

7、100C 240D、 27010、稀疏矩阵一般的压缩存储方法有（ C ）两种。（A）二维数组和三维数组（B）三元组和一维数组（C）三元组和十字链表（D） 维数组和十字链表11、广义表 F=（a,b,（c,d,（e）的表尾为（C ）A、（e）B、（c,d,（e）C （b,（c,d,（e）D b,（c,d,（e）12、广义表 H=(a,(b,c),d,(e,(f,g)的表头是(B )A、aB (a,(b,c),d,(e,(f,g)C a,(b,c)D、(a,(b,c)四、简答题1、两个串相等的充要条件是什么？答：两个串的长度相等；对应位置的字符相等；2、空串和空格串有何区别？答：空串是不含任何字符的串，其长度为0，是任意串的子串；空格串是仅含有空格符的串,其长度是串中空格字符的个数；五、应用题：1、下列三元组表表示一个稀疏矩阵，试写出它的稀疏矩阵(最后一个三元组表示矩阵的总 行数、总列数、非 0元素总个数)。厂122、2 1123 134 445 366 116<646J2、请画出以下稀疏矩阵的三元组表。02 0-10000 003000 000060 000