200920101-数据结构期中试卷答案

(12分)已知一棵树的双亲表示如下表所示:012345678910RABCDEFGHIJ-10011122459树的双亲表示法「利用树中的每个结点(除根结点外)只有唯一双亲的特点，用数组来存储一棵一般的树,数组的每个元素有二个分量，其一存储该元素的值,其二存储该元素的双亲位置(即下标丿，根结点的双亲位置为」・树的孩子兄弟表示法「树中的每个元素用一个结点来表示，结点的结构由数据域和二个指针域组成，第一个指针域指向该元素的第一个孩子,成，第一个指针域指向该元素的第一个孩子,第二个指针域指向该元素的下一个兄弟。・试画出此树，(2丿•・试画出此树，(2丿•画出此树的孩子兄弟表示时的示意图,(3)•将此树转化为相应的二叉树并画出.三、程序填空(共12分，每空格2分)得分下面是循环队列的存储结构描述及队列各基本操作的实现，请在空白处填上正确的代码以完成QueueADT,得分TOC\o"1-5"\h\z#defineMaxElements20^defineMmQueueSize(5)#defineTRUE1#defineFALSE0structQueueRecord,typedefstructQueueRecord*Queue,structQueueRecord{mtCapacity,intFront,intRear,ElementTvpe*Array,},intIsEmpty(QueueQ){ireturn△;}intIsFull(QueueQ丿{returnB,}QueueCreateQueue(mtMaxElements){QueueQ,if(MaxElements<MmQueueSize)returnNULL,Q=(Queuejmalloc^sizeof^structQueueRecord)),if(Q==NULL)returnNULL,Q->Array=(ElementTvpe和nnlloqsizeofyEl.ementType丿*MaxElementsif(Q->Array=NULL)returnNULL,Q->Capacity=MaxElements,MakeEmpt}\Q),returnQ,}voidMakeEmpty(QueueQ){Q->Front=1,Q->Rear=0,}intSucc(mtValue,QueueQ){if(++\bhie=Q->Capacity)X^lue=0,returnX^ilue,}intEnqueue^ElementTvpeX,QueueQ){if()returnFALSE,else

D,Q->Array[Q->Rear]=X,}}intDequeue^QueueQ,ElementTvpe&X){if(_E_)returnFALSE,else{F,Q->Front=Succ(Q->Front,Q),}}A・_((Q=・Reciir+1)%Q-二・Capacity==Q・>Fi:ont:)B._((Q>Reair+2)%Q・>Capacity==Q>Fi：ont)C.IsFu山Q)_Q・>Reai:=Succ(Q>Rea「Q)或Q・ARea】=(C.IsFu山Q)得分_IsEmpty(Q丄F._X=Q>Aixay「Q・AFi:ontL四、编写程序(24分丿已知一个带有表头结点的单链表，结点由数据域和指向后继的指针域组成，假设该链表只给出了头指针hst。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中的倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的数据域的值，并返回1；否则，只返回0.要求：给出单链表的存储结构定义；描述算法的基本设计思想；描述算法的详细实现步骤)；根据设计思想和实现步骤，用C语言实现描述算法)，关键之处请给出简要注释“答：struct_Node{ElementTvpeElement,structNode*Next,}，typedefstruct_NodeNode,typedefstruct_Node*PtrToNode,typedefPtrToNodeList,算法的基本思想如下：从头至尾遍历单链表，并用指针p指向当前结点的前k个结点.当遍历到链表的最后一个结点时，如果表中存在k个结点，则指针p所指的结点即为所查找的结点。详细实验步骤：增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针pl指向当前遍历的结点，指针P指向pl所指向结点的前k个结点，如pl之前没有k个结点，那么p指向表头结点.用整型变量L表示当前遍历了多少个结点，当L>k时，说明表中有k个结点，所以让p与pl之间保持k个结点的间距，让p=p>Next。当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。算法描述如下：IntLocateElement^Lisrlist,intk){pl=lLSt->Next,p