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

《数据结构与软件方法试卷B参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、湖北师范学院《数据结构与软件方法》课程期末考试试卷B试题答案及评分标准课程类别：必修适用专业：信息工程专业试卷编号：B抄写要求一、一律用钢笔或圆珠笔按现行规范字型用正楷字抄写，卷面整洁。二、试题图型、图表除在试题纸上描绘外，并附一份描图纸图样。三、抄写完后，要仔细核对，保证试题内容准确无误。四、凡不符合抄写要求的试题一律予以退回。考试形式开卷_______________________________________________________________________________一、选答题（每小题2分，共20分）题号123456

2、78910答案CCBAABCAAB二、名词解释（每小题3分，共6分）1、二叉树——。2、线索化——三、判断题（每小题1分，共8分）题号12345678答案××√√××√×四、填空题（每小题1分，共15分）答案：1、（1）数据元素（2）关系2、（3）一对一（4）一对多（5）多对多3、（6）直接前驱结点的链域的值4、（7）n-i+15、（8）O(1)（9）随机存取6、（10）串的模式匹配（11）被匹配的主串（12）子串7、（13）栈8、（14）O(n2)（15）O(n+e)。五、简答题（每小题5分共20分）1、数据结构和数据类型两个概念之间有区别吗？

3、答：(答案要点)简单地说，数据结构定义了一组按某些关系结合在一起的数据元素。（3分）数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。（2分）2、描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？答：(答案要点)首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点

4、（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。头结点headàdatalink头指针首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；（1分）头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）（1分）首元素结点是指链表中存储线性表中第一个数据元素a1的结点。（1分）在单链

5、表中设置头结点的作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。（2分）3、给定二叉树的两种遍历序列，分别是：先序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B，并写出其后序遍历的序列。答：DACEBHFGI后序遍历序列：CBEIGFHAD。4、把如图所示的树转化成二叉树。答：略六、算法分析题（每小题7分，共21分）1、(答案要点)运行结果为：x=18，y=36x=8，y=运行前的值，且从x＝30开始为数据错2、（1）画表如下：012345678910

6、111213141516173217634924401030314647（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与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（

7、6＋2＋3×3）＝17/11=1.5454545454≈1.553、已知如图所示的有向图，请给出该图的:（1）每个顶点的入/出度；（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；否则函数返回。但注意，递归时应当从叶子开始向上计数，否则不易确定层数。intdepth(liuyu*r

8、oot)/*统计层数*/{intd,p;/*注意每一层的局部变量d,p都是各自独立的*/p=0;if(root==NULL)return