数据结构07～08第二学期B卷-答案
- 格式：doc
- 大小：67.00 KB
- 文档页数：3
广州大学2007-2008学年第二学期考试卷课程《数据结构》考试B
一、判断题（对打√，错打×。
每题1分，共15分） √ × √ √ √ × √ × √ √ √ √ √ × ×
二、选择题（每题2分，共20分）
C C B A C C B C C D
三、问答题（共30分） 1、（4分，每个答案给1分）答：主要差别①树中结点的最大度数没有限制，而二叉树结点的最大度数为2。
②树的结点无左右之分，而二叉树的结点有左右之分。
最多是完全二叉树的形态，即502个叶子；最少是单支树的形态，即1个叶子。
2、（6分）答：
得到右图所示结果给3分
3、（11分，每个关键字1分）答：
4、（9分）答： 画出该图给4分
得出最小生成树给5分
四、算法题（第1题15分，第2题20分）
1、
void delete(LinkList L, int mink, int maxk) { p=L->next; while (p && p->data<=mink) { pre=p; p=p->next; } //查找第一个值>mink 的结点 if (p) { while (p && p->data<maxk) p=p->next; // 查找第一个值 ≥maxk 的结点 q=pre->next; pre->next=p; // 修改指针 while (q!=p) { s=q->next; delete q; q=s; } // 释放结点空间 } // if } // delete 2、
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 ) ; }。
