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

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

湖 北 师 范 学 院

《 数据结构与软件方法》课程期末考试试卷C

试题答案及评分标准

一、选答题（每小题2分，共20分）

二、名小题3

词解释（每共6分）

1、哈夫曼树——。 2、线索二叉树——。

三、判断题（每小题1分，共10分）

四、填空0.5

空题 （每共10分）

答案： 1、（1）；（2）；（3）；（4）； 2、（5）有限（6）一对一 3、（7）前驱结点的地址（8）O（n） 4、（9）线性 （10）任何 （11）栈顶 （12）队尾 (13) 队首 5、（14）5 6、（15）9 7、（16）邻接矩阵 （17）邻接表 （18）深度优先遍历 （19）广度优先遍历 8、（20）关键字的值

五、简答题（每小题6分共24分）

1、

答：(答案要点) X= 116 Y= 0 Z= 100 首址= 108 末址= 112 。 2、说明线性表、栈与队的异同点。 答：(答案要点)

相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。 不同点：

①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

数据结构与软件方法试卷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*/ }