数据结构复习习题.docVIP

1.20 确定算法中每一句的执行次数和时间复杂度。 double P(int n , int x) { //读入n+1个系数，求多项式的值；n=0 s=0; for(j=n ; j=0; j--) { scanf(a); s=s*x+a; //该循环体执行n+1次 } return s; }//P 算法的时间复杂度为：O（n）L[i]和R[i](i=0,1,…,n-1)分别指示二叉树中第i个结点的左孩子和右孩子结点，0表示空。试写判别结点u是否是结点v的子孙的算法。 分析： 1．u是否是结点v的子孙，就是看遍历以v为根的子树，是否能遍历到u。 2. 给出的存储结构实质上是一个二叉链表存储结构。只不过，链是由数组描述的而已。 Status descendent(int L[], int R[], int u, int v) { if (u v) { if (L[v]==u || R[v]==u) return TRUE; else if (descendent(L, R, u, L[v])) return TRUE; else return descendent(L, R, u, R[v]); } else return FALSE; } // descendent 6.36 判断两棵二叉树是否相似的递归算法 int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法{ ??if (!B1!B2) return 1; ??else if(!B1B2 || B1 !B2) return 0; else return (Bitree_Sim(B1-lchild,B2-lchild)Bitree_Sim(B1-rchild,B2-rchild)) ?}//Bitree_Sim 6.43 编写递归算法，计算二叉树叶子结点的数目 int leaf_num(Bitree T ){//求二叉树T中叶子结点的数目 { if(!T) return 0; else { if(!T-lchild !T-rchild) return 1; else { d1= leaf_num(T-lchild); d1= leaf_num(T-rchild); return(d1+d2); } } }// leaf_num 6.43 编写递归算法，交换二叉树中所有结点的左右子树 注意：此题用先序和后序均可，但不能依中序遍历的次序进行 void swap( BiTree BT ) { if (BT) { swap( BT-lchild); swap( BT-rchild); BT-lchild (( BT-rchild; } }// swap 6．44 编写递归算法，求二叉树中以值为x的结点为根的子树深度。 int Get_Depth(Bitree T)//求二叉树深度的递归算法{??if(!T) return 0;??else??{????m=Get_Depth(T-lchild);????n=Get_Depth(T-rchild);????return (mn?m:n)+1;??}}//Get_Depth void Get_Sub_Depth(Bitree T,int x , int depth) //求二叉树中以值为x的结点为根的子树深度{??if( T ) if(T-data==x) depth=Get_Depth(T)); //找到了值为x的结点,求其深度???? ?else ??{?Get_Sub_Depth(T-lchild,x depth); Get_Sub_Depth(T-lchild,x depth); //在左右子树中继续寻找 ?} }//Get_Sub_Depth 6．47 编写按层次顺序(同一层自左至右)遍历二叉树的算法。 分析: 按层次遍历的定义: 若树不空，则首先访问根结点，然后，依照其双亲结点访问的顺序， 依次访问它们的左、右孩子结点;因此， 需要一个“队列”保存已被访问的结点。 void LevelOrderTraver