a 11 a 12 a21 a22 a33 a34 a43 … aij … a2m-1,a2m,22m m-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
^ 5 1 91 2 2 13 ^ 2 3 3 0 1 2 3 1 4 22 4 ^ 5 1 6 -15 ^ ^ ^ 3 4 -6 2 3 4
5
^ ^ ^ ^ 6 3 28 ^ ^
7．画出下列广义表的头尾表示存储结构示意图。 （1）A=((a,b,c),d,(a,b,c))
（2）B=(a,(b,(c,d),e),f) （1） （2）
5.3 课后习题解答 5.3.1 选择题
1．下列说法正确的是（C）。
A．二叉树中任何一个结点的度都为2 B．二叉树的度为2
1 0 a 1 1 1 1 0 c 1 ^ 0 d 1 ^ 1 ^ 0 f 1 1 1 ^ 1 0 a 1 1 b 1 ^ 1 c 1 d 0 b 0 c 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个结点，其中叶子结点的个数是（C）。
A． 500 B． 501 C．490 D．495