数据结构2005_1_A答案.docVIP

2005~2006学年第1学期 03级电子科学与技术《数据结构》A卷答案 判断题 √√√√√ √√××× √××√ 选择题 BH CCD BCBD 问答题 证明： 设n1为K叉树中度为1的结点数。因为K叉树中只含有度为0、1和K的结点，所以其结点总数为： n = n0 + n1 +nK （1） 又由于，除了根节点外，其余结点都有一个分支进入，设B为分支总数，则 n = B + 1 （2） 因为这些分支是由度为1或K的结点发出的，所以有B = n1 + K nK。代入（2）有 n = n1 + K nK + 1 （3） （1）和（3）两式联立得： n0=（K-1）nK+1 证毕 答：①树的结点个数至少为1，而二叉树的结点个数可以为0。 ②树中结点的最大度数没有限制，而二叉树结点的最大度数为2。 ③树的结点无左右之分，而二叉树的结点有左右之分。 答： 答： 算法题 答： #define OK 1 #define FALSE 0 typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; void TransferLink(LinkList L){ if ( L L-next-next){ s = L-next-next ; L-next-next = NULL; while ( s ){ p = s-next ; s-next = L-next ; L-next = s ; s = p ; } } } 答： typedef struct Node{ ElemType data; struct Node *lchild,* rchild; }BinNode, *BinTree ; 方法一： int leafNum = 0 ; void CountLeaf ( BinTree root ){ /* preorder visit bintree and count the number of leaf node */ if ( root ! = NULL ){ if ( root-lchild = = NULL root-rchild = = NULL) leafNum ++ ; else{ CountLeaf ( root-lchild ) ; CountLeaf ( root-rchild ); } } } 方法二： int CountLeaf (BinTree root ){ if ( root = = NULL ) return 0 ; if ( root-lchild = = NULL root-rchild = =NULL ) return 1 ; return CountLeaf ( root-lchild ) + CountLeaf ( root-rchild ) ; } 第 2 页 共 3 页 L K J I H G F E C D B A L K J I H G F E C D B A 5 6 4 3 2 1 4 1 2 5 3 6 6 5 5 5 6 4 3 2 1 4 1 2 5 3 6