7,1),substr(S,3,1)))
2.串S的长度为n，其中的字符各不相同，所以S=”(x+z)*y”中含1个字符的子串有n个，2个字符的子串有n-1个……，含n-2个字符的子串有3个，含n-1个字符的子串有2个，共有非平凡子串的个数是n(n+1)/2-1。
3.串T的next和nextval函数值见下表： 下标j 1 2 3 4 5 6 7 8 9 10 11 串T a b c a A c c B a c a next[j] 0 1 1 1 2 2 1 1 1 2 1 nextval[j] 0 1 1 0 2 2 1 1 0 2 0 4．特殊矩阵是指具有相同值的矩阵元素或零元素的分布具有一定规律，可以将其压缩存储在一维数组中，矩阵元素aij的下标I和j与其在一维数中存放的下标k之间存在一一对应关系，故不会失去随机存取功能。
稀疏矩阵中零元素的分布没有一定规律，可以将非零元素存于三元组表中，非零元素aij在三元组中的存放位置与i、j没有对应关系，故失去随机存取功能。
5．N阶对称矩阵A中，aij=aji，可以仅存放下三角元素（或上三角元素）。设r=max(i,j)，c=min(i,j),
k=r(r-1)/2+c-1;
例如，4阶对称矩阵A，按行优先顺序存于一维数组F[10]中，
0 1 2 3 4 5 6 7 8 9 a11 a21 a22 a31 a32 a33 a41 a42 a43 a44 当i=3，j=2时，k=3*2/2+2-1=4; 当i=2，j=3时，k=4
(2)当对称矩阵A按列优先顺序压缩存放，若仅存放上三角元素，则有： k=r(r-1)/2+c-1
例如，4阶对称矩阵A，按列优先顺序存于一维数组F[10]中，
0 1 2 3 4 5 6 7 8 9 a11 a12 a22 a13 a23 a33 a14 a24 a34 a44 当i=1，j=3时，k=3*2/2+1-1=3;当i=3，j=1时，k=3
第五章
一、单项选择题
(1)-(5)BBCDC (6)-(10)BCABC (11)—(15)DABBD (16)-(19)CCABB (20)-(24) BBBAC (25)-(27)DBC 二、填空题
（1）有零个或多个 （2）有且仅有一个
（3）根据树的广义表表示，可以画出这棵村，该树的度为4。 （4）树的深度为4
(5)树中叶子结点个数为8
ki-1
（6）n0=14 (7)n-2m+1 (8)2-1 (9)2 (10)133 (11)59
55
(12)2=32 (13)?log2(n+1)?=?log269?=7 (14) 2-1+6=37 (15) 19
7
(16)2-1-20=107 (17)右 （18）m+1 (19)n+1 (20) 2m-1 (21)中序 （22）直接前驱结点 （23）直接后继结点 三、应用题
1.具有n个结点的满二叉树中只有度为2和度为0的结点，故n=2n0-1,n0=(n+1)/2。
5．构造一棵二叉树应该先确定根结点，由后序序列最后一个字母A确定根结点，可将前序序列的第一个字母*改为A。在中序遍历序列中A的左子树中含4个字母，右子树中含3个字母，在后序遍历序列中左子树的后序遍历子序列为*EDB，可将左子树的后序遍历序列和中序遍历序列互相补足，分别是CEDB和CBDE。由这两个子序列可知左子树的根结点为B，D又为以B为根结点的右子树的根结点，E为D的右孩子，所以在前序序列中A的左子树的前序序列为：BCDE，在根结点A的右子树中，由后序遍历序列可确定其根结点为F，再确定其中序序列为GHF，进一步确定其前序序列为FGH，补足*处后，三个遍历序列为：
(1)前序遍历序列是：ABCDEFGH
25
(2)中序遍历序列是：CBDEAGHF (3)后序遍历序列是：CEDBHGFA
由前序遍历序列和中序遍历序列可构造一棵二叉树如右图。 四、算法设计题 1.求叶子结点个数。 算法描述如下：
int leafnum(Csnode *t,int n) {Gsnode *p;
if(t==NULL) return 0; p=t->fc; if(p==NULL)
n++; while(p)
{n=leaf(p,n); p=p->ns; }
return n; }
2.交换左右孩子。算法如下： void exchange(Btnode *t)
{Btnode *p; if(t)
{exchange(t->lchild); exchange(t->rchild); if(t->lchild||t->rchild) {p=t->lchild;
t->lchild=t->rchild; t->rchild=p;} } }
3.void printbtree(Btnode *r) {if(r)
{printf(“%c”,r->data); if(r->lchild||r->rchild) printf(“(”);
printbtree(r->lchild); if(r->rchild) printf(“,”);
printbtree(t->rchild); printf(“)”); } }
4. #define MAX 100 int checkt(Btnode *t) {Btnode *s[MAX]; int i,n=0;
for(i=0;i 26 {if(!s[i]) return 0; if(s[i]->lchild) {n=2*i+1; s[n]=s[i]->lchild; } if(s[i]->rchild) {n=2*i+2; s[n]=s[i]->rchild; } i++; } return 1; } 5．(1)前序遍历二叉树的非递归算法的基本思想是：从二叉树的根结点开始，沿左支一直走到没有左孩子的结点为止，在走的过程中访问所遇结点，并把非空右孩子进栈。当找到没有左孩子的结点时，从栈顶退出某结点的右孩子，此时该结点的左子树已遍历结束，然后按上述过程遍历该结点的右子树，如此重复，直到二叉树中所有结点都访问完毕为上。算法如下： void preorder(Btnode *t) { int I=0; Btnode *p,*s[M]; P=t; Do { while(p) {printf(“%c\\t”,p->data); if(p->rchild!=NULL) s[i++]=p->rchild; p=p->lchild; } if(i>0) p=s[--i]; }while(i>0||p!=NULL); } (2)后序遍历二叉树的非递归算法的基本思想：采用一个栈保存返回的结点，先遍历根节点的所有结节点并入栈，出栈一个结点，然后遍历该结点的右结点并入栈，再遍历该右结点的所有左结点并入栈，当一个结点的左右子树均访问后再访问该结点，如此这样，直到栈为空为止。其中的难点是如何判断一个结点t的右结点已访问过，为此用p保存已访问过的结点(初值为NULL)，若t->right=p成立（在后序遍历中，t的右节点一定是在t之前访问），说明t的左右子树均已访问，现在应访问t。算法如下： void postorder(Btree *t) { Btree *s[maxsize]; Btree *p; int flag,top=-1; Do { while(t) { top++; s[top]=t; t=t->left; } p=NULL; flag=1; while(top=-1&&flag) { t=s[top]; 27 if(t->right==p) { printf(“%d””,t->data); top--; p=t; } else { t=t->right; flag=1; } } }while(top!=-1) } 6.求二叉树中从根结点到p结点之间路径长度的算法描述如下： #define MAX 100 void path(Btnode *t,Btnode *p) { Btnode *s[MAX],*q=t; int b[MAX],top=-1; do { while(q) {s[++top]=q; b[top]=0; q=q->lchild; } if(top->-1&&b[top]==1) {q=s[top]; if(q==p) {printf(“根结点到q结点的路径是：”)； for(I=0;I<=top;I++) printf(“%c”,s[I]->data); return; } else top--; } if(top>-1) { p=s[top]->rchild; b[top]=1; } }while(top>0); } 7.判断以二叉链表存储的二叉树是否为完全二叉树的算法描述如下：#define MAX 100 void checkt(BTnode *t) { Btnode *s[MAX]; int i,n=0;