第二趟匹配：aabaabaabaac 第二趟匹配：aabaabaabaac aa(i=3,j=2) (aa)baac
第三趟匹配：aabaabaabaac 第三趟匹配：aabaabaabaac a(i=3,j=1) (成功) (aa)baac 第四趟匹配：aabaabaabaac aabaac(i=9,j=6) 第五趟匹配：aabaabaabaac aa(i=6,j=2) 第六趟匹配：aabaabaabaac a(i=6,j=1) 第七趟匹配：aabaabaabaac
(成功) aabaac(i=13,j=7)
3．假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占４个字节。问下列元素的存储地址是什么？
(1) a0000 (2)a1111 (3)a3125 (4)a8247
【解答】(1) LOC( a0000)= 100
(2) LOC( a1111)=100+(3*5*8*1+5*8*1+8*1+1)*4=776 (3) LOC( a3125)=100+(3*5*8*3+5*8*1+8*2+5) *4=1784 (4) LOC( a8247)= 100+(3*5*8*8+5*8*2+8*4+7) *4=4816 4．假设一个准对角矩阵：
a11 a12
a21 a22
a33 a34
a43 a44
….
aij
a2m-1,2m-1 a2m-1,2m
a2m,2m-1 a2m,2m
按以下方式存储于一维数组B[4m]中（m为一个整数）：
0 a 11 1 a 12 2 a21 3 a22 4 a33 5 a34 6 … k … 4m-1 4m a43 … aij … a2m-1,2m a2m,2m-1 a2m,2m 写出下标转换函数k=f(i,j)。 【解答】
由题目可知，每一行有两个非0元素。
当i为奇数时，第i行的元素为：ai,i、ai,(i+1)，此时k=2*(i-1)+j-i=i+j-2 当i为偶数时，第i行的元素为：ai,(i-1)、ai,i，此时k=2*(i-1)+j-I+1=i+j-1 综上所述，k=i+j-i%2-1。
5．设有n×n的带宽为3的带状矩阵A，将其3条对角线上的元素存于数组B[3][n]中，使得元素B[u][v]=aij，试推导出从（i,j）到 (u,v)的下标变换公式。 【解答】
u=j-i+1 v=j-1
6．现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。 （1）三元组表表示法 （2）十字链表法。
【解答】
0 0 0 22 0 -15 0 13 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0
（1）三元组表表示法:
1 2 3 4 5 6 7 i j v 1 4 22 1 6 -15 2 2 13 2 3 3 3 4 -6 5 1 91 6 3 28 （2）十字链表法：
0 1 2 3 1 4 22 4 ^ 5 1 6 -15 0 1 2
2 2 13 ^ 2 3 3 ^ ^ ^ 3 4 -6 ^ ^ 3 ^ 5 1 91 4 5
^ ^ 6 3 28 ^ ^
7．画出下列广义表的头尾表示存储结构示意图。 （1）A=((a,b,c),d,(a,b,c)) （2）B=(a,(b,(c,d),e),f) （1） 1
1 1 1 ^
0 a 1 b 1 c
（2） 1 1 0 a 1 1 1 0 b 0 c
1 1 ^ 1 d 1 ^ 1 ^ 1 ^ 0 d 0 f 0 c 5.3 课后习题解答
5.3.1 选择题
1．下列说法正确的是（C）。
A．二叉树中任何一个结点的度都为2 B．二叉树的度为2
C．一棵二叉树的度可小于2
D．任何一棵二叉树中至少有一个结点的度为2
2．以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0），空链域的个数为（C）。
A．2n-1 B．n-1 C．n+1 D．2n+1
3．线索化二叉树中，某结点*p没有孩子的充要条件是（B）。 A．p->lchild=NULL B．p->ltag=1且p->rtag=1
C．p->ltag=0 D．p->lchild=NULL 且p->ltag=1 4．如果结点A有3个兄弟,而且B是A的双亲,则B的度是（B）。 A．3 B．4 C．5 D．1 5．某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号，编号值为1,2,...n。且有如下性质:T中任意结点v,其编号等于左子树上的最小编号减１,而v的右子树的结点中,其最小编号等于v左子树上结点的最大编号加１，这是按（B）编号的。
A． 中序遍历序列 B． 先序遍历序列 C． 后序遍历序列 D． 层次顺序
6．设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点,B中右指针域为空的结点有（C）个。
A．n-1 B． n C． n+1 D．n+2
7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（B）。 A． 500 B． 501 C．490 D．495
8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是（D）。
A．N1 B．N1+N2 C．N2 D．N2+N3
9．任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序（A）。 A．不发生改变 B． 发生改变 C． 不能确定 D． 以上都不对
10．若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列
为（D）。
A．cbed B．decab C．deabc D．cedba
11．若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（D）。
A． gcefha B． gdbecfha C． bdgaechf D． gdbehfca
12．一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（AB）。
A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是一棵满二叉树 13．引入线索二叉树的目的是（A）。 A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 14．设高度为h的二叉树上只有度为０和度为２的结点，则此类二叉树中所包含的结点数至少为（B）。
A．2*h B． 2*h-1 C． 2*h+1 D．h+1 15．一个具有567个结点的二叉树的高h为（D）。
A．9 B．10 C．9至566之间 D．10至567之间 16．给一个整数集合{3，5，6，7，9}，与该整数集合对应的哈夫曼树是（B）。 A． B． C． D．
9 9 3 7 5 9 7 6
6 6 3 7 5 3 5 6
9 7 5 3
5.3.2 判断题
1．二叉树是树的特殊形式。（√）
2．由树转换成二叉树，其根结点的右子树总是空的。（√）
3．先根遍历一棵树和先序遍历与该树对应的二叉树，其结果不同。（×） 4．先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。（×） 5．完全二叉树中，若一个结点没有左孩子，则它必是叶子。（√） 6．对于有N个结点的二叉树，其高度为?log2N?＋1。（×）
7．若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的
相关推荐：
loading