实用数据结构基础（第四版）课后习题(3)

3.字符串存储方式除了顺序存储，链接存储，还有堆存储。 4.穿衣顺序存储非紧凑格式的缺点是密度小

5.串顺序存储紧凑格式的缺点是对串的字符处理困难。 6.串的链式存储结构，简称为链串。

7.串链接存储的优点是插入，删除方便，缺点是存储，检索效率低。 8.在c或c++语言中以字符（这个答案很奇怪）表示串值的终结

9.两个串相等的充分必要条件是两个串长度相等，且对应位置的字符相同 10.设S=“my music”则LenStr（S）=8 11.两个字符串分别为XXXXX 12.求子串的结果是

13.在串的运算中XXXXXX，返回值为July 14.在串的运算中XXXXXX，返回值为-1

15.设有两个串P和Q，求Q在P中首次出现的位置运算称作

16.在子串的定位运算中，被匹配的主串称为目标串，子串称为模式 17.模式匹配成功的起始位置称为有效位移 18.设XXXXX 19.设Xxxx

20.若n为主串长度，m为子串长度，且n＞＞m，则简单模式匹配算法最好情况下的时间复

杂度为0（n*m）

第六章

1.多维数组的顺序存储方式有按行优先顺序存储和列优先两种。 2.在n维数组中的每一个元素最多可以有n个直接前驱

3.在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一种顺序存取结构

4.数组元素a[0..2][0..3]的实际地址是2000，元素长度是4，则LOC[1,2]=228 5.输入二维数组A[n][m]中所有元素值的时间复杂度为0（n*m）

6.n阶对称矩阵，如果只存储下三角元素，只需要n*(n+1)/2个存储单元

7.n阶下三角矩阵，因为对角线的上方是一个常数，需要n*(n+1)/2+1个存储单元 8.非零元素的个数远小于矩阵元素总数的矩阵为稀疏矩阵 9.稀疏矩阵矩阵的三元组有三列

１０．稀疏矩阵中有ｎ个非零元素，则三元组有ｎ＋１

１１.稀疏矩阵的三元组中的一列存储的是数组中非零元素所在的行

１２．稀疏矩阵a，如图，其非零元素存于三元表中三元组415，按列优先顺序存储在三元表中的第５项

１３.稀疏矩阵的压缩存储方法通常有三元组表和十字链表两种 １４.任何一个非空广义表的表尾，必定是表元素

１５．广义表Ｌ 的表尾 【１６－２０题在书上看吧】 ＱＡＱ

第七章

1.三个节点可以组成五种不同形态的树。

2.在树中，一个结点所拥有的子树数，称之为该结点的度。 3.度为零的结点称之为叶结点。

4.树中节点的最大层次称之为树的深度 5.对于二叉树来说，第二层上至多有 6.深度为h的二叉树至多有

7.有20个节点的完全二叉树，编号为10的节点的父节点的编号是5

8.将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其右孩子结点编号为2i+1 9.已知完全二叉树的第8层有8个节点，则其叶节点数是三 10.采用二叉链表存储的n个节点的二叉树，共有空指针n+1个 11.如图 12.如图

13.A.B为一棵树二叉数上的两个结点，在中序遍历时，a在b前的条件是A在B的左子树上 14.设一棵二叉树节点的先序遍历序列为abcdefgh，中序遍历序列为dbeafchg，则二叉树中叶结点是EFH

15.某二叉树的中序遍历序列为debac，后序遍历序列为dbcad，则前序遍历序列为DABEC 16.前序为ABC，且后续为CBA的二叉树共有1种

17.由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树

18.由树转换成二叉树时，其根结点无右子树 19.哈夫曼树是带权路径长度的最短二叉树。 20.具有n个节点的哈夫曼树共有2n-1个结点。