欢迎来到天天文库
浏览记录
ID:38701299
大小:327.50 KB
页数:3页
时间:2019-06-17
《数据结构与软件方法试卷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
此文档下载收益归作者所有