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

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

湖 北 师 范 学 院

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

试题答案及评分标准

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

二、名小题3

词解释（每共6分）

1、二叉树——。 2、线索化——

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

四、填小题1

空题 （每共15分）

答案： 1、（1）数据元素（2）关系 2、（3）一对一（4）一对多（5）多对多 3、（6）直接前驱结点的链域的值 4、（7）n-i+1 5、（8）O(1) （9）随机存取 6、（10）串的模式匹配 （11）被匹配的主串 （12）子串 7、（13）栈 8、（14）O(n2) （15）O(n+e)。

五、简答题（每小题5分共20分）

1、数据结构和数据类型两个概念之间有区别吗？

答：(答案要点) 简单地说，数据结构定义了一组按某些关系结合在一起的数据元素。（3分）数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。（2分）

2、描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？

答：(答案要点) 首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为

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

空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。

简而言之，

头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；（1 分）

头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）（1 分）

首元素结点是指链表中存储线性表中第一个数据元素a1的结点。（1 分）

在单链表中设置头结点的作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。（2 分）

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

答：

后序遍历序列：CBEIGFHAD。

4、把如图所示的树转化成二叉树。 答： 略

六、算法分析题（每小题7分，共21分）

1、 (答案要点) 运行结果为：x=18，y=36

x=8，y=运行前的值， 且从x＝30开始为数据错 1

4然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

（4） 对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，

所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55 3、已知如图所示的有向图，请给出该图的: （1） 每个顶点的入/出度；

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

（2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表。

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

1、参考算法： Q=P; P=L;

while(P->next!=Q)P=P->next; P=Q;

S->next=P->next; P->next=S;

2、答；设计思路：只查后继链表指针，若左或右孩子的左或右指针非空，则层次数加1；否则函数返回。 但注意，递归时应当从叶子开始向上计数，否则不易确定层数。 int depth(liuyu*root) /*统计层数*/

{int d,p; /*注意每一层的局部变量d,p都是各自独立的*/ p=0;

if(root==NULL)return(p); /*找到叶子之后才开始统计*/ else{

d=depth(root->lchild);

if(d>p) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/ d=depth(root->rchild); if(d>p)p=d; }

p=p+1; return(p);

}