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

湖 北 师 范 学 院 数据结构与软件方法课程期末考试试卷B试题答案及评分标准课程类别：必修适用专业：信息工程专业试卷编号：B抄写要求一、 一律用钢笔或圆珠笔按现行规范字型用正楷字抄写，卷面整洁。二、 试题图型、图表除在试题纸上描绘外，并附一份描图纸图样。三、 抄写完后，要仔细核对，保证试题内容准确无误。四、 凡不符合抄写要求的试题一律予以退回。考试形式开卷_一、选答题（每小题2分，共20分）题号12345678910答案CCBAABCAAB二、名词解释（每小题3分，共6分）1、二叉树。2、线索化三、判断题（每小题1分，共8分）题号12345678答案四、填空题 （每小题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的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。 头结点headdatalink 头指针 首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；（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，并写出其后序遍历的序列。答： DACEBHFGI 后序遍历序列：CBEIGFHAD。4、把如图所示的树转化成二叉树。答： 略六、算法分析题（每小题7分，共21分）1、 (答案要点) 运行结果为：x=18，y=36 x=8，y=运行前的值， 且从x30开始为数据错2、（1）画表如下：012345678910111213141516173217634924401030314647（2） 查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,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（6233）17/11=1.54545454541.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；否则函数返回。但注意，递归时应当从叶子开始向上计数，否则不易确定层数。 int depth(liuyu*root) /*统计层数*/int d,p; /*注意每一层的局部变量d,p都是各自独立的*/p=0;if(root=NULL)return(p); /*找到叶子之后才开始统计*/else d=dep