习 题 四
⑵ 解释下列每对术语的区别：空串和空白串；主串和子串；目标串和模式串。
解：空串和空白串的区别：空串不含任何字符，它的长度为0，而空白串含有一个空格，它的长度为1.
主串和子串的区别：主串是相对于子串而言的，子串是主串中连续的一段，是主串的一个子集。
目标串和模式串的区别：目标串是在模式匹配中的主串，是相对于模式串运算的母串，而模式串是子串，是在主串中运算的子串。
⑵ 若x和y是两个采用顺序结构存储的串，写一算法比较这两个字符串是否相等。 解：
int streql(Hstring x, Hstring y) if(x[0]!=y[0]) return (0); else i=1;
while(x[i]==y[i]&&i if(i== x[0]) return (1) else return (0) 习 题 五 ⑴ 什么是广义表？请简述广义表与线性表的区别？ 广义表是零至多个元素的有限序列，广义表中的元素可以是原子，也可以是子表。从“元素的有限序列”角度看，广义表满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于扩充的线性结构（只不过元素并不具有同一类型：可以是原子，也可以是广义表）。当广义表中的元素都是原子时，广义表就蜕变为线性表。 广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表 ⑵ 一个广义表是(a, (a, b), d, e, (a, (i, j), k)) ，请画出该广义表的链式存储结构。 图解： 10a110a10b∧10d10e11∧10a10i10j∧10k∧ ⑶ 设有二维数组a[6][8]，每个元素占相邻的4个字节，存储器按字节编址，已知a的起始地址是1000，试计算： ① 数组a的最后一个元素a[5][7]起始地址； ② 按行序优先时，元素a[4][6]起始地址； ③ 按行序优先时，元素a[4][6]起始地址。 LOC(a[5][7])=LOC(a[0][0])+47*4=1188 LOC(a[4][6])=LOC(a[0][0])+(4?8+6)?4=1152 LOC(a[4][6])=LOC(a[0][0])+（6*6+4）?4=1160 ⑸ 设有稀疏矩阵B如下图所示，请画出该稀疏矩阵的三元组表和十字链表存储结构。 图解： 12331-3384432462521865467573-3 图中未标记空指针，作业中请注意标记 习 题 六 ⑴ 假设在树中， 结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为 { (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ，用树型表示法表示该树，并回答下列问题： ① 哪个是根结点? 哪些是叶子结点? 哪个是g的双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孙? 哪些是e的兄弟? 哪些是f的兄弟? ② b和n的层次各是多少? 树的深度是多少? 以结点c为根的子树的深度是多少? ⑵ 一棵深度为h的满k叉树有如下性质： 第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。 如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： ① 各层的结点数是多少? ② 编号为i的结点的双亲结点(若存在)的编号是多少? ③ 编号为i的结点的第j个孩子结点(若存在)的编号是多少? ④ 编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少? ⑶ 设有如图6-27所示的二叉树。 ① 分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。 ② 写出该二叉树的先序、中序、后序遍历序列。 ⑷ 已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。 ⑸ 设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA ，请画出这棵二叉树，然后给出该树的先序序列。 ⑹ 已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。 ⑺ 以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法。 ⑻ 设图6-27所示的二叉树是森林F所对应的二叉树，请画出森林F。 ⑼ 设有一棵树，如图6-28所示。