1、综合模拟试卷 18 及答案与解析一、综合题1 已知单链表中的结点的形式为： 其中，data 域为结点的数据域，其类型为 int；link 域为结点的指针域，给出本结点的直接后继结点的地址。现已知两个单链表都是有序的单链表，它们都按照结点数据域的值由小剑大排成一个非递减的序列。现已知这两个单链表的头结点的地址分别为 Head 和 Head2，注意头结点的指针域给出单链表中的第一个结点的地址。请设计一个非递归的函数，将这两个单链表进行合并，合并后的单链表仍然按照结点数据域的值由小到大排成一个非递减的序列。注意，合并后的单链表所使用的空间应来自上述两个单链表，所使用的额外空间只能为 O(1)；否则不
2、得分。被合并的两个单链表的示意图如下：2 已知二叉树中的结点的形式为： 其 data 域为结点的数据域，left 和 right 域分别给出了左儿子和右儿子的地址。已知两棵二义树的根结点的地址分别为 p、q。请设计一个函数，判断这两棵二叉树的树形是否相似；若相似则返回 1，否则返回 0。注意：此处相似指的是二叉树的树形，和结点的数据域之值尤关。3 已知二叉树中的结点的形式为： 其中 data 域为结点的数据域，left 域和 right 域分别给出本结点的左儿子和右儿子的地址。已知二叉树的根结点的地址为 root。请设计一个函数，给出该二叉树的叶子结点的总数加，以及度为 1 的结点的总数 n1
3、、度为 2 的结点的总数 n2。综合模拟试卷 18 答案与解析一、综合题1 【正确答案】 从链表的头位置依次摘取并比较大小，将其插入到新链表的末尾TypedefstructN0deintdata：Node*link：LLNode，*Linklist；Linklistmerge(Linklistheaderl，Linklistheader2)Linklistc；LNode*P=headerl-link，*q=header2 一link：c=headerl：c 一link=NULL ：LNode*s=e，*r：deleteheader2；while(p&q)2 【正确答案】 对两棵树分别进行前序遍
4、历，并在遍历的过程中检查它们的左、右孩子是否均存在或者不存在，直至两棵树均遍历完毕或一棵提前结束TypedefstructBitNodeintdata；BitNode*left，冰 right；BitNode，*BiTree ：BoolChecksimilar(BitNode*a，BitNode*b)if(a=NULL&h=NULL)lI(a!=NULL&b!=NULL)returntrue；elsereturnfalse；intcheck(3 【正确答案】 在树的前序遍历中判断结点的左右孩子存在情况，并统计树中结点度的情况typedefstructBitNodeintdata；BitNode*left，*right：BitNode，*BiTree ；voidstatic(BiTreeroot)BiTreestackMAXNODE，P；inttop；intdegree0=0，degree1=0 ， degree2=0：if(root=NULL)return：top=0；P=root；while(!(P=NULL&top=
