数据结构与软件方法试卷C参考答案(2)

数据结构与软件方法试卷C参考答案

3、一棵度为2的树与一棵二叉树有何区别？

答：(答案要点) 度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

4、给定二叉树的两种遍历序列，分别是：先序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B，并写出其后序遍历序列。 答：(答案要点) 后序遍历序列：BHCIGFAD。

六、算法分析题（每小题6分，共18分）

1、答：O(n2) 2、答：“char” 3、最小生成树：

七、算法设计题（每小题10分，共10分）

参考答案：

#include<stdio.h> #include<stdlib.h>

typedef struct liuyu{int data;struct liuyu*link;}test; liuyu *p,*q,*r,*head; int m=sizeof(test);

void main () /*第一步，从键盘输入整数，不断添加到链表*/ {int i;

head=(test*)malloc(m); /*m=sizeof(test);*/ p=head; i=0;

while (i!=-9999)

{ printf("/ninput an integer [stop by '-9999']:"); scanf("%d",&i);

p->data=i; /* input data is saved */ p->link=(test*)malloc(m); /*m=sizeof(test));*/ q=p;

p=p->link; }

q->link=NULL; /*原先用p->link=NULL似乎太晚！*/

p=head; i=0; /*统计链表结点的个数并打印出来*/ while (p->link!=NULL) {printf("%d",p->data); p=p->link; i++; }

printf("\n node number=%d\n", i-1); /*结点的个数不包括-9999*/ }