数据结构-基于C语言的描述（第2版）试题及答案 共10套

C语言的描述（C语言的描述（2版）期末考试试卷及参考答案（一）PAGE1《数据结构》期末考试试卷（一）考试时间：100分钟满分：100分注意事项：C请给出下面试卷答案：一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后括号内。（）SQa，b，c，d，e，fSQ。若出队的序列是b，d，c，f，e，a，则栈S的容量至少应为（）2345ABDECFDBEAFC（）DEBFCADBEFCADEBFCADBFECAn（）nn-1C.n(n-1)/2D.log₂n（）ni（1≤i≤n）（）in-in-i+1n-i-1k（）2^kB.2^(k-1)C.2^k-1D.2^(k-1)-1(5,8,12,25,30,40,50)40（）1234O(nlog₂n)（）102510（）91011二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。数据构相之存一种多特关的据元的包数的逻结构、 数的三个面。在双链每结包含个针个向其 另个向其结点。断队的条件是 。设有维组标范是0到每元相的5字存储器字节编。数的始址为100，则M[8]的地址为 。一棵为5理平二叉（除后层外其余都满少有 个结点。有图G邻矩阵A[n][n]存，第i行所素之等点i的 。在直插排中若排序基有，其间复度提至 。8. H(key)=key%13{19,14,23,01,68,20,84,27}，哈地为1的链有 记。在二树中线化表中若结的指域为其被索为指该结点的 。一个有n个点无完全，有 边。三、简答题（本大题共4小题，每小题5分，共20分）（AVL树）四、应用题（本大题共2小题，每小题10分，共20分）80.14，0.23，0.03，0.11。（1）请构造以频率为权值的哈夫曼树（要求左子树根结点的权小于等于右子树根结点的权）。（6分）（2）请给出这8个字符的哈夫曼编码。（4分）设有关键字序列{503,087,512,061,908,170,897,275,653,426}。5,3,（（3（2）写出采用快速排序以第一个元素为基准，第一趟划分后的结果。（4分）（3）写出建立大根堆的初始堆（即第一趟堆排序的结果）。（3分）五、算法设计题（本大题共2小题，每小题10分，共20分）truefalse。要求：（1）描述算法思想。（5分）（2）类C语言算法描述。（5分）问题：设计一个算法，计算一棵给定二叉树的所有叶子结点的个数。要求：（1）描述算法思想。（5分）（2）类C语言算法描述（递归或非递归均可）。（5分）参考答案及评分标准（试卷一）一、单项选择题（每题2分）1.D 2.B 3.A 4.C 5.A 6.B 7.C 8.C 9.D 10.C（解析：10.二叉树性质：叶子结点数=度为2的结点数+1。故10+1=11。）二、填空题（每题2分））Q.rear==Q.front4. 140（1008*5140）5. 16（2^41155116）出度O(n)8. 3（0113114131271313个）9. 10.n(n-1)/2三、简答题（每题5分）：（LIFO）队列：先进先出（FIFO）。应用：打印机任务队列、消息队列、广度优先搜索。（各1分特性，各0.5分例子）（2/O(log₂n)（3（1.5分）（1.5分）（大O(n2)（1.5分）（最大/O(log2n)（1.5分）O(n2)降至O(log2n)，大幅提升效率。（2分）四、应用题（1）构造哈夫曼树（6分）：合并：0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.110.03+0.05=0.080.29,0.07,0.080.14,0.23,0.080.07+0.08=0.150.29,0.14,0.230.08,0.150.08+0.11=0.190.290.14,0.230.150.19→0.14+0.15=0.290.290.23,0.190.29→0.19+0.23=0.420.290.29,0.42→0.29+0.29=0.58最后：0.42+0.58=1.00最终树形结构：（评分：合并过程3分，树形正确3分）（2）哈夫曼编码（4分）：左分支标0，右分支标1。例如（根据具体构造的树，答案可能不唯一）：0.03:0000，0.05:0001，0.07:1110，0.08:1111，0.11:001，0.14:110，0.23:01，0.29:10。（评分：写出对应关系，编码前缀不同即可）（1）希尔排序（增量5）后（3分）：原序列：{503,087,512,061,908,170,897,275,653,426}分组：(503,170)，(087,897)，(512,275)，(061,653)，(908,426)第一趟结果：{170,087,275,061,426,503,897,512,653,908}（2）快速排序第一趟后（4分）：轴基准key=503。从右向左扫描小于key的：426<503，交换得{426,087,512,061,908,170,897,275,653,503}从左向右扫描大于key的：512>503，交换得{426,087,503,061,908,170,897,275,653,512}继续扫描交换...最终一趟划分结果为：{426,087,275,061,170,503,897,908,653,512}（评分：过程描述或最终结果正确均可）（3）建立大根堆（3分）：从最后一个非叶结点（下标n/2开始向上调整。初始堆（大根堆）结果为：{908,653,897,503,426,170,512,275,061,087}五、算法设计题（1）算法思想（5分）：ppre->datapre->datafalsetrue。L->next）p=L->next。（p->next==NULL），true。pp->nextp->data>=p->next->datafalse。否则，pp->data<p->next->datatrue。（2）类C算法描述（5分）：//单链表结构定义typedefstructLNode{intdata; //数据域，可根据需要改为其他类型structLNode*next; //指针域}LNode,*LinkList;//判断带头结点的非空单链表L是否严格递增有序boolisIncreasing(LinkListL){ //L为头结点，L->next为第一个数据结点LNode*p=L->next; //p指向第一个数据结点if((p==NULL)||(p->next==NULL)){returntrue; //单个元素视为递增}while(p->next!=NULL //遍历链表，比较相邻元素if(p->data>=p->next->data){returnfalse; //false}p=p->next; //移动到下一个结点}returntrue; //所有相邻元素均满足递增}（1）算法思想（5分）：递归思想：叶子结点是左右子树都为空的结点。。1。+（2）类C算法描述（递归，5分）：//二叉树二叉链表结构定义typedefstructBiTNode{intdata; //数据域（类型可根据需要调整）structBiTNode*lchild; //左孩子指针structBiTNode*rchild; //右孩子指针}BiTNode,*BiTree;//计算二叉树中叶子结点的个数（递归算法）intCountLeaves(BiTreeT){if(T==NULL)return0; //空树，无叶子if((T->lchild==NULL)&&(T->rchild==NULL)){return1; //当前结点是叶子}//否则，递归计算左右子树的叶子数之和returnCountLeaves(T->lchild)+CountLeaves(T->rchild);}C语言的描述（C语言的描述（2版）期末考试试卷及参考答案（二）PAGE10《数据结构》期末考试试卷（二）考试时间：100分钟满分：100分注意事项：C一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后括号内。（）i）n-in-i+1i（）adbcedecabdebacabcde18A[3]（）A.1，2，3B.9，4，2，3C.9，5，2，3D.9，4，1，2，3p（）p->llink->rlink=p->rlink;p->rlink->llink=p->llink;p->llink=p->llink->llink;p->llink->rlink=p;p->rlink->llink=p;p->rlink=p->rlink->rlink;p->rlink=p->llink->llink;p->llink=p->rlink->rlink;1001（）A.250B.500C.501D.5058. 对序列8，20，9，7}，则采用的增量是（）1432（）A.{75，65，30，15，25，45，20，10}B.{75，65，45，10，30，25，20，15}C.{75，45，65，30，15，25，20，10}D.{75，45，65，10，25，30，20，15}0（）存在二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。在顺表插或除个元要均动约 元素具移的元个数与 关。空串是 ，长等于 。设目串T="abccdcdccbaa"，模式串P="cdcc"，则第 匹成。LS=((a,b,c)，(d,e,f))headtaile 。在树结中树结没有 点其每个点且有 个驱结点。具有n个点连图少有 边。在有表A[1..12]，用二查算查等于A[12]的元，比的素下依次为 。

查找来减少比较次数。在哈表，填子α的值大则生突可能越 。对n记进归排，所要辅存空是 。三、简答题（本大题共4小题，每小题5分，共20分）AOEB-四、应用题（本大题共2小题，每小题10分，共20分）已知一棵树的先根遍历序列为GFKDAIEBCHJ，后根遍历序列为DIAEKFCJHBG。（1）请画出这棵树。（5分）（2）将此树转换为对应的二叉树。（5分）V0,V1,V2,V3,V4,V5(V0,V5,100)，(V0,V4,30)，(V0,V2,10)，(V1,V2,5)，(V2,V3,50)，(V3,V510)，(V4,V560)，(V4,V3,20)。（1）请画出其邻接表存储结构。（5分）DijkstraV0（5五、算法设计题（本大题共2小题，每小题10分，共20分）Lsts≤t）要求：（1）描述算法思想。（3分）（2）类C语言算法描述。（5分）（3）分析算法的时间和空间复杂度。（2分）G要求：（1）描述算法思想。（3分）（2）类C语言算法描述。（5分）（3）说明如何调用此算法。（2分）参考答案及评分标准（试卷二）一、单项选择题（每题2分）1.D 2.B 3.D 4.B 5.A 6.A 7.C 8.B 9.C 10.A（解析：2.n1...n-1LIFOin-i+1。7.n0n21n1=011001n1=0nn0n2n0n0-1)=2n0-1=1001，所以n0=501。（）0）二、填空题（每题2分）/零个符串，03. 6head(tail(head(tail(LS)前驱或结），16. n-17. 6，9，11，12二分）大O(n)三、简答题（每题5分）（2.5分）优点（2.5分）：（1next（（4分）：（2长度不变，总工期不变。（3分）B-：m⌈m/2⌉（3：I/O（2四、应用题（1）根据先根GFKDAIEBCHJ和后根DIAEKFCJHBG可画出树形：G为根，孩子有F、K等。画出的树如下：（5分）（2（5分）+（5（2）Dijkstra过程：-初始：S={V0}，dist[]={0,∞,10,∞,30,100}-V2：S={V0,V2}dist[3]=60-V4：S={V0,V2V4}dist[3]=50dist[5]=90-V3：S={V0,V2V4V3}dist[5]=60-V5：S={V0,V2V4V3V5}V1最终结果：V0到V1：无路径V0到V2：10（V0→V2）V0到V3：50（V0→V4→V3）V0到V4：30（V0→V4）V0到V5：60（V0→V4→V3→V5）写出每一步的集合和距离数组变化。（5分）五、算法设计题（1）算法思想（3分）：L[s,）：ik（）。L.data[i]不在[s,t]L.data[k]，并令k；k（2）类C算法描述（5分）：//顺序表结构定义#defineMAXSIZE100 //顺序表最大容量typedefintElemType; //int，可根据需求修改typedefstruct{ElemTypedata[MAXSIZE]; //存储元素的数组intlength; //顺序表当前有效长度}SqList;boolDeleteRange(SqList&L,ElemTypes,ElemTypet){if((s>t)||L.length<=0returnfalse//检查参数合法性intk=0; //k指向新顺序表中下一个要写入的位置for(inti=0;i<L.length;i++){if((L.data[i]<s)||(L.data[i]>t) //保留不在[s,t]区间的元素L.data[k++]=L.data[i];}}L.length=k; //更新顺序表长度returntrue;}（3）算法复杂度分析（2分）：O(n)n空间复杂度：O(1)，仅使用了常数个辅助变量（如i,k），未使用额外存储空间。（1）算法思想（3分）：树是无回路的连通图，即边数e=顶点数n-1，且连通。①若e!=n-1，返回false。cnt==n（3（2）类C算法描述（5分）：//图的邻接表结构定义#defineVertex_Max100typedefstructEdgeNode{intadjvex; //邻接顶点的下标structEdgeNode*nextedge; //指向下一个边结点的指针}EdgeNode;typedefstructVexNode{int vex; //顶点数据EdgeNode*firstedge; //指向第一个边结点的指针}VexNode;typedefstruct{VexNode vexs[Vertex_Max]; //顶点数组intvexnumedgenum; //顶点数、边数}ALGraph;//DFS判断连通性：boolvisited[MAX_VERTEX_NUM];voidDFS(ALGraphG,intv,int&count){visited[v]=true;count++;for(EdgeNode*p=G.vertices[v].firstarc;p;p=p->nextarc){intw=p->adjvex;if(!visited[w])DFS(G,w,count);}}boolIsTree(ALGraphG){if(G.vexnum==0)returntrue;if(G.arcnum!=G.vexnum-1)returnfalse;//边数检查intcount=0;for(inti=0;i<G.vexnum;i++)visited[i]=false;DFS(G,0,count);return(count==G.vexnum);}（3）调用：构建图G后，直接调用IsTree(G)。（2分）C语言的描述（C语言的描述（2版）期末考试试卷及参考答案（三）PAGE10《数据结构》期末考试试卷（三）考试时间：100分钟满分：100分注意事项：C一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后括号内。（）（）SQe6SQ6S（）2346FM3F（）M1M1+M2M3M2+M35. (c，f)，(f，d)，(e，d)}。对该图进行深度优先遍历，不能得到的顶点序列是（）a，b，e，d，f，ca，c，f，e，b，da，e，d，f，c，ba，c，f，d，e，b（）（）A.{100，80，90，60，120，110，130}B.{100，120，110，130，80，60，90}C.{100，60，80，90，120，110，130}D.{100，80，60，90，120，130，110}8447251521第一趟：1547258421第二趟：1521258447第三趟：1521254784则采用的排序是（））A.79，46，56，38，40，80B.84，79，56，38，40，46C.84，79，56，46，40，38D.84，56，79，40，46，38（）二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。数据逻结分两类： 和 。在单表设头点作用是 。循环列向头元的一位指向尾素位队满件是 ，空件是 。设S="I_AM_A_TEACHER"，其长是 。一棵为6满叉有 个支点。在无图G的接阵A中若A[i][j]等于1，则A[j][i]等于 。顺序找n个素顺表，查成，比关键的数多为 在插排序希排序选择序排序快排序并序中平比较最少排是 。在哈表，理突两种要法是 和 。对n记的进直选择序所进的键字的较数为 。三、简答题（本大题共4小题，每小题5分，共20分）PrimKruskal四、应用题（本大题共2小题，每小题10分，共20分）给定关键字序列{45，24，53，12，37，93}，（1）构造一棵二叉排序树。（3分）（2）在插入过程中，何时出现不平衡？如何调整？（3分）（3）依次删除24、53后，画出最终的二叉排序树。（4分）对关键字序列{25，57，48，37，12，92，86，33}进行归并排序，（1）写出每一趟归并后的结果。（6分）（2）说明归并排序的特点及其适用场景。（4分）五、算法设计题（本大题共2小题，每小题10分，共20分）Lc要求：（1）描述算法思想。（3分）（2）类C语言算法描述。（5分）（3）分析算法的时间复杂度和空间复杂度。（2分）问题：设计一个递归算法，求二叉树的高度（深度）。要求：（1）描述算法思想。（3分）（2）类C语言算法描述。（5分）（3）简要说明递归的执行过程。（2分）参考答案及评分标准（试卷三）一、单项选择题（每题2分）1.A 2.A 3.B 4.D 5.B 6.C 7.C 8.A 9.B 10.C（解析：出，e5出，e1出。栈最大深度为3。M2+M3。CBST（10032）。）二、填空题（每题2分）(rear+1)%量==front，rear==front4. 145. 31（2^6-1=63=32，分支=31）6. 1n10.n(n-1)/2三、简答题（每题5分）：（。：1分）（3<根<≤1。（3AVLO(log₂n)。（2：（2Prim（1.5Kruskal算法：按权值从小到大选边，若边不构成环则加入。适用于稀疏图。（1.5分）：RiRj（i<j），（2分）稳定：插入、冒泡、归并、基数。（1.5分）不稳定：选择、希尔、快速、堆。（1.5分）四、应用题（1）构造二叉排序树：依次插入：45为根，24左，53右，12为24左，37为24右，93为53右。4524（2445）→4553（5345）→4512（124524，122424）；37（37<45→24，37>2424）；93（93>4553，935353。（3（2）不平衡与调整：在这个插入顺序{45，24，53，12，37，93}下，没有出现不平衡，因此无需调整。若触发不平衡，调整方法（AVL树旋转）如下：（2分）（3）删除操作后的树：24（253（2（1）归并步骤：初始：[25][57][48][37][12][92][86][33]第一趟：[2557][3748][1292][3386]第二趟：[25374857][12338692]第三趟：[1225333748578692]（每趟2分，共6分）（2）特点及适用场景：（2分）（（2分）五、算法设计题（1）算法思想（3分）：papb。。尾部。注意：通常假设链表带头结点（哨兵），若无头结点，需特殊处理首元结点。（2）类C算法描述（5分）：//单链表结构定义typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;//LaLbLc（利用原结点）voidMergeList(LinkListLa,LinkListLb,LinkList*Lc){LNode*pa=La->next; //La的第一个数据结点LNode*pb=Lb->next; //Lb的第一个数据结点LNode*pc=La; //LcLa的头结点Lc=pc;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?papb; //链接剩余部分deleteLb; //Lb的头结点}（3）时间复杂度和空间复杂度：时间复杂度：O(m+n)，其中m、n分别为两表长度。（1分）空间复杂度：O(1)（仅用了常数个指针变量）。（1分）（1）算法思想（3分）：（）0；=1+max(,)。（2）类C算法描述（5分）：//二叉树二叉链表结构定义typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//计算二叉树的深度（高度）intDepth(BiTreeT){if(T==NULL)return0;else{intleftDepth=Depth(T->lchild);intrightDepth=Depth(T->rchild);return(leftDepth>rightDepth?leftDepth:rightDepth)+1;}}C语言的描述（C语言的描述（2版）期末考试试卷及参考答案（四）PAGE1《数据结构》期末考试试卷（四）考试时间：100分钟满分：100分注意事项：C一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后括号内。（）tops（）top->next=s;s->next=top;top=s;s->next=top->next;top->next=s;s->next=top;top=top->next;k（）2k-12^kC.2^(k-1)D.2^k-1ne（）ne2n2e5. d=4的一4（）A.15，40，60，20B.15，40，60，45C.15，40，60，50D.15，40，60，701000X（次。251071head（）head==NULLhead->next==NULLhead->next==headhead!=NULL（）BADCBCDACDABCBDA9. 20为基准记（）A.10，15，14，18，20，36，40，21B.10，15，14，18，20，40，36，21C.10，15，14，20，18，40，36，21D.15，10，14，18，20，36，40，2110.（）A.[41，12，34，45，27]55[72，63]B.[45，34，12，41]55[72，63，27]C.[63，12，34，45，27]55[41，72]D.[12，27，45，41]55[34，63，72]二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。psA的后插点X的序列为 。对于个度为n的线性，第i个素（1≤i≤n+1）之插一元素，需要后动 元素。设字符串S1="ABCDEF"，S2="PQRS"，做操作：SubString(Sub1,S1,2,StrLength(S2)，SubString(Sub2,S1,SteLength(S2),则算S=StrConcat(Sub1,Sub2)串为 。设一完二树有500个点则二树深度为 。设输序为、、3，则经栈作后以到 种同输序列。设有图G存结邻接阵A表，则A中第i中有零个数和等于点i的 。100X X 。n1i个结的亲点号为 右子点号为 。10.设一初记关字为以录字72为基的一趟速序果为 。三、简答题（本大题共4小题，每小题5分，共20分）四、应用题（本大题共2小题，每小题10分，共20分）哈希表关键字序列MOD7，（1）请构造哈希表。（6分）（2）计算等概率情况下查找成功。（4分）PrimA五、算法设计题（本大题共2小题，每小题10分，共20分）问题：设计一个高效算法，将顺序表L中的所有元素逆置，要求算法的空间复杂度为O(1)。要求：写出算法思想、类C语言算法。问题：设计一个算法，输出二叉树中从根结点到每个叶子结点的路径。要求：写出算法思想、类C语言算法（递归或非递归）。参考答案及评分标准（试卷四）一、单项选择题（每题2分）1.C 2.B 3.D 4.D 5.A 6.B 7.C 8.A 9.A 10.A二、填空题（每题2分）1. s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;（顺可调）2. n-i+13. "BCDEDE"4. 9kn≤2^9−1=511，因此深度为9）5. 5（n=3）6. 出度7. 7（2^7=128>100）8. O(1)9. ⌊i/2⌋，2i+110.{5,16,71,23,72,94,73}三、简答题（每题5分））<<（（O(n)。①统计图中每个顶点的入度；②将所有入度为0的顶点入栈；③当栈非空时，取出一个顶点输出，并将其所有邻接顶点的入度减1；若某邻接顶点入度变为0，则将其入栈；④重复步骤③，直到栈为空；⑤若输出的顶点数等于图中顶点总数，则存在拓扑序列；否则，图中存在环，无法进行拓扑排序。主要应用：课程安排、任务调度、依赖分析。1四、应用题1. （1）keyH=(key×3)mod7：H(7)=0H(8)=3H(30)=6H(11)=5H(18)=5，冲突，探测：地址6冲突，地址0冲突，地址1有空H(9)=6，冲突，探测：地址0冲突，地址1冲突，地址2有空H(14)=0，冲突，探测：地址1冲突，地址2冲突，地址3冲突，地址4有空哈希表：[7,18,9,8,14,11,30]（2）ASL成功：(1+1+1+1+4+4+5)/7=17/7≈2.429Prim算法：A，边(A,B)2B可选边(AC)4，(B,C)3，(B,D)1，选(B,D)1D可选边(AC)4，(B,C)3，(DC)5，(DE)8，选(B,C)3C可选边(DE)8，(B,E)6，选(B,E)6E最小生成树边集：{(A,B),(B,D),(B,C),(B,E)}。总权重=2+1+3+6=12五、算法设计题（1（5分：采用双指针法（首尾交换）：i（0），jL.length-1）；②交换L.data[i]与L.data[j]；③然后i++，j--，继续交换，直到i>=j；整个过程只使用常数个辅助变量，空间复杂度为O(1)，时间复杂度为O(n)。（2类C（5：//顺序表结构定义#defineMAXSIZE100typedefintElemType; //int，可根据需求修改typedefstruct{ElemTypedata[MAXSIZE];intlength;}SqList;//逆置顺序表LvoidReverseList(SqList&L){inti=0,j=L.length-1;while(i<j){temp=L.data[i];L.data[i]=L.data[j];L.data[j]=temp;i++;j--;}}（1）算法思想（递归）（5分）：（DFS）），）（）；top（2）类C算法描述（5分）：//二叉树二叉链表定义typedefintElemType; //int，可根据需求修改typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//辅助函数：打印路径voidPrintPath(ElemTypepath[],intlen){for(inti=0;i<len;i++){if(i>0)printf("->");printf("%d",path[i]);}printf("\n");}//主递归函数：求根到所有叶子的路径voidFindLeafPaths(BiTreeT,ElemTypepath[],inttop){if(T==NULL)return;path[top]=T->data; //将当前结点加入路径top++;if((T->lchild==NULL)&&(T->rchild==NULL)){PrintPath(pathtop); //如果是叶子结点，输出路径else //递归遍历左右子树FindLeafPaths(T->lchild,path,top);FindLeafPaths(T->rchild,path,top);}//top是值传递，不影响上层（top--）}//调用接口voidOutputAllPaths(BiTreeT){if(T==NULL)return;ElemTypepath[MAX_DEPTH]; //MAX_DEPTH100FindLeafPaths(T,path,0);}C语言的描述（C语言的描述（2版）期末考试试卷及参考答案（五）PAGE1《数据结构》期末考试试卷（五）考试时间：100分钟满分：100分注意事项：C一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后括号内。（）ABsp（）s->next=p+1;p->next=s;(p).next=s;(s).next=(*p).next;s->next=p->next;p->next=s->next;s->next=p->next;p->next=s;A[0..m]（）rear=rear+1rear=(rear+1)mod(m-1)rear=(rear+1)modmrear=(rear+1)mod(m+1)（）G1643343G（）101112n（）O(n)O(nlog₂n)m=14H(key)=keymod114addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空。如用二次探测法处理冲突，则关键字为49的结点的地址是（）8359AGGi（）i0i0i0i0381（）1213141510.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，用归并排序法对该序列进行一趟归并后结果为（）A.15，25，35，50，20，40，80，85，36，70B.15，25，35，50，80，20，85，40，70，36C.15，25，35，50，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，85二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。数据物结主包括 和 两况。设一完二树有128个结，该全叉的深为 有 子结。设输序为、、3，则经栈作后以到 种同输序列。设有图G存结邻接阵A表，则A中第i中有零个数和等于点i的 。设哈曼中有n个点，该夫树有 个为1的点。设有组始键序为第3直插序结后的结是 。设有组始键序为第3简选序结后的结是 。设一二树前遍序列中遍序均为ABC，后遍序为 。设有顺表有n据元，利二查法查数元素X的比较数不超过 。设散数H(k)=kmod决突方为址求算中一个键字时，先算散地，然将插到地所指链的 。三、简答题（本大题共4小题，每小题5分，共20分）AVL（DFS）（BFS）四、应用题（本大题共2小题，每小题10分，共20分）给定关键字序列{45，24，53，12，37，93}，（1）构造一棵二叉排序树。（5分）（2）画出删除结点37后的二叉排序树。（5分）已知AOE网如下图所示，求：（1）各事件的最早发生时间ve和最迟发生时间vl。（5分）（2）该工程的关键路径和完成工程的最短时间。（5分）五、算法设计题（本大题共2小题，每小题10分，共20分）Li。要求：写出算法思想、类C语言算法。1C参考答案及评分标准（试卷五）一、单项选择题（每题2分）1.C 2.D 3.D 4.C 5.B 6.B 7.D 8.B 9.B 10.A二、填空题（每题2分）1. 2. n1=0n1=1，计算得n0=64）3. 5出度0（02）6. 12，24，35，27，18，267. 12，18，24，27，35，268. CBA9. ⌊log₂n⌋+110.表头（解析：无需遍历链表，时间复杂度O(1)，效率最高）三、简答题（每题5分）（-1，0，1。应用有BFS（）n-1四、应用题（1）4524左，531224左，37249353右。（2）删除37（叶子结点）：直接删除。删除后的二叉排序树如下：：（1）各事件的最早发生时间ve和最迟发生时间vl①最早发生时间ve从源点V0正向计算）ve(V0)=0ve(V1)=ve(V0)+5=5ve(V2)=ve(V0)+6=6ve(V3)=max{ve(V1)+3,ve(V2)+6}=max{5+3,6+6}=12ve(V4)=max{ve(V2)+3,ve(V3)+3}=max{6+3,12+3}=15ve(V5)=ve(V3)+4=12+4=16ve(V6)=max{ve(V3)+1,ve(V4)+1}=max{12+1,15+1}=16ve(V7)=ve(V4)+4=15+4=19ve(V8)=max{ve(V5)+5,ve(V6)+2,ve(V7)+2}=max{16+5,16+2,19+2}=21ve(V9)=max{ve(V5)+4,ve(V8)+2}=max{16+4,21+2}=23vl（V9）ve(V9)=23vl(V8)=vl(V9)−2=23−2=21vl(V7)=vl(V8)−2=21−2=19vl(V6)=vl(V9)−2=21−2=19vl(V5)=min{vl(V9)−4,vl(V8)−5}=min{23−4,21−5}=16vl(V4)=min{vl(V6)−1,vl(V7)−4}=min{19−1,19−4}=15vl(V3)=min{vl(V5)−4,vl(V6)−1,vl(V4)−3}=min{16−4,19−1,15−3}=12vl(V2)=min{vl(V3)−6,vl(V4)−3}=min{12−6,15−3}=6vl(V1)=vl(V3)−3=12−3=9vl(V0)=min{vl(V1)−5,vl(V2)−6}=min{9−5,6−6}=0（2）该工程的关键路径为v0→v2→v3→v4→v7→v8→v9；最短完成时间是23。五、算法设计题（1）算法思想（5分）：j=0ppj<ipj++。pj==ipNULL。（2）算法描述（5分）：//单链表结构定义typedefstructLNode{ElemTypedata; //数据域，ElemType为元素类型structLNode*next; //指针域}LNode,*LinkList;//LiNULLLNode*GetElem(LinkListL,inti){if(i<=0returnNULL; //i不合法LNode*p=L; //p指向头结点intj=0; //jpj个结点）while((p!=NULL)&&(j<i)){p=p->next;j++;}if((j==i)&&(p!=NULL))returnp; //j==ip!=NULLi个结点C语言的描述（C语言的描述（2版）期末考试试卷及参考答案（六）PAGE1elsereturnNULL;}1（1）算法思想（递归）（5分）：采用递归遍历方式（如先序、中序、后序均可），对每个结点判断其度是否为1：(left≠NULLright==NULL)或(left==NULL且right≠NULL)，则该结点度为1，计数加1；1=1（01）+1+1（2）算法描述（5分）：//二叉树二叉链表结构定义typedefstructBiTNode{ElemTypedata; //数据域structBiTNode*lchild; //左孩子指针structBiTNode*rchild; //右孩子指针}BiTNode,*BiTree;//1的结点个数intCountDegreeOne(BiTreeT){if(T==NULL)return0;intcount=0;//判断当前结点是否度为1if(((T->lchild!=NULL)&&(T->rchild==NULL))||((T->lchild==NULL)&&(T->rchild!=NULL))){count=1;}//递归统计左右子树returncount+CountDegreeOne(T->lchild)+CountDegreeOne(T->rchild);}《数据结构》期末考试试卷（六）考试时间：100分钟满分：100分注意事项：C一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后括号内。（）ni（）n-in-i+1n-i-1iFT1、T2T3FB，T1、T2T3的N1、N2N3B（）N1-1N2-1N2+N3N1+N3（）O(n)O(nlog₂n)O(log₂n)top（）top=top+1;top=top-1;top->next=top;top=top->next;（）n（）n(n-1)n+1nn(n+1)500010（）Gne）n，ee，n2n，en，2e（）BADCBCDACDABCBDA二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。设指量p向链中点针量s指被插的点结点A的后面入点X需要的语序：s->next=p->next; 。设无图G有n点e边则邻矩作为的储构行度优遍历时的间杂为 。设一二树前遍序列中遍序均为ABC，该叉的遍历列为 。设散表长为列数H(k)=kmod线性测解冲突根据组初始关字列(8，15，16，22，30，32)造的列表平查长是 。5. 设一初关字列为则第3简选排序的结果为 。6. 设一初关字列为则第3直插排序的结果为 。设一完二树有21个结，果照上下、左右顺从1开始序编号则号为8的亲点的号是 编为8左子点编是 。设一初记关字列为则以20中的趟快排序结为 。设二排树高为h，则该中找字key最多需要较 次。在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择 三、简答题（本大题共4小题，每小题5分，共20分）四、应用题（本大题共2小题，每小题10分，共20分）已知一棵二叉树的后序遍历序列为DGEBHIFCA，中序遍历序列为DBGEACHFI，（1）请画出此二叉树。（5分）（2）写出该二叉树的先序遍历序列。（2分）（3）画出该二叉树对应的中序线索二叉树。（3分）对关键字序列{72，87，61，23，94，16，5，58}进行堆排序，（1）画出初始建立的大根堆（树形表示）。（5分）（2）写出第一趟排序结束后（即交换堆顶元素后调整堆）的结果序列。（5分）五、算法设计题（本大题共2小题，每小题10分，共20分）ABABCC要求：写出算法思想、类C语言算法。问题：设计一个非递归算法，求二叉树的高度。要求：写出算法思想、类C语言算法。参考答案及评分标准（试卷六）一、单项选择题（每题2分）1.C 2.A 3.A 4.C 5.D 6.A 7.C 8.B 9.D 10.A二、填空题（每题2分）1. p->next=s;2. 3. CBA4. 8/3（ASL1+2+2+4+4+3)/616/6=8/3≈2.67）5. 10，13，27，76，65，97，386. 38，65，76，97，13，27，107. 4，168. [19，18，16] 20 [22，30]h快速三、简答题（每题5分）O(n)。1。1（）。四、应用题二叉树（1）二叉树如下：（2）先序：ABDEGCFHI（3）中序线索化：对每个结点，若左空则指向前驱，若右空则指向后继。堆排序（1）初始序列：728761239416558。建立大根堆：948761587216523。树如下：（2）第一趟排序结束后序列：8772615823165[94]。交换堆顶元素后调整堆如下：五、算法设计题（1）算法思想（5分）：ABijABA[i]B[j]C将另一个表剩余元素依次复制到C的末尾。该方法时间复杂度为O(m+n)，空间复杂度为O(m+n)（m、n分别为A、B的长度）。（2）算法描述（5分）：//顺序表结构定义如下：typedefstruct{ElemType*data; //元素数组intlength; //当前长度}SqList;//A、BCvoidMergeList(SqListA,SqListB,SqList&C){inti=0,j=0,k=0;C.length=A.length+B.length;C.datanewElemType[C.length]; //分配空间//双指针归并while((i<A.length)&&(j<B.length)){if(A.data[i]<=B.data[j])C.data[k++]=A.data[i++];elseC.data[k++]=B.data[j++];}//AB剩余元素while(i<A.length)C.data[k++]=A.data[i++];while(j<B.length)C.data[k++]=B.data[j++];}说明：newElemType[...]分配；使用完毕后，应由调用方负责释放：delete[]C.data;，避免内存泄漏。（）（1）算法思想（5分）：采用层序遍历（广度优先搜索）思想，利用队列实现：levelSize=1height=0；levelSize）1；height。此方法避免了递归调用栈，适用于深度很大的树。（2）算法描述（5分）：//二叉树二叉链表结构定义typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//非递归求二叉树高度intTreeHeight(BiTreeT){if(T==NULL)return0;QueueQ; //定义队列InitQueue(Q); //初始化队列EnQueue(Q,T); //根结点入队intheight=0;while(!QueueEmpty(Q)){intlevelSize=QueueLength(Q); //当前层的结点数height++; //进入新的一层//一次性处理当前层所有结点for(inti=0;i<levelSize;i++){BiTreep;DeQueue(Q,p); //出队一个结点if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}returnheight;}说明：QueueInitQueueEnQueueDeQueueQueueEmptyQueueLengthQueueLength()（如用临时变量保存当前队列中元素个数。C语言的描述（C语言的描述（2版）期末考试试卷及参考答案（七）PAGE10《数据结构》期末考试试卷（七）考试时间：100分钟满分：100分注意事项：C一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后括号内。（）i=1;while(i<=n)i=i*3;O(n)O(log₃n)O(1)p（）p->next->prior=p->prior;p->prior->next=p->next;p->next=p->next->next;p->next->prior=p;p->prior->next=p;p->prior=p->prior->prior;p->prior=p->next->next;p->next=p->prior->prior;a,b,c,d,e,fb,d,c,f,e,a（）3456ABCCBA（）BCACBAABCCABGE={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)}a出发进行（）aedfcbacfebdaebcfdaedfbcn（）nn-1C.n(n-1)/2D.nlog₂n1000X（）251071设哈希表长m=14，哈希函数H(key)=keymod11。表中已有4个结点：addr(15)=4，49（）835965（）876510.设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为（）A.10，15，14，18，20，36，40，21B.10，15，14，18，20，40，36，21C.10，15，14，20，18，40，36，21D.15，10，14，18，20，36，40，21二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。设需对5个同记关键进排至需要较 多需较 快速序法平时复杂为 最况下时复度为 。设二排树高为h，则该中找字key最多需要较 次。设在为20的序进行分比一查找功结数有 个，比较次找功结数有 m0N₀1N₁，……m的结为Nm，则N₀= 。6. 设一初记关字列为则用选法立的初堆为 。设无图G的接矩为A则A第i行非0素的数 第i上非0元素的数填于大或小）。设前遍某叉的列为序历二叉的为则后遍历该二树序为 。设散数H(k)=kmod决突方为址求算中一个键字时，先算其 然后历链。10.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个度为2有子则用并序方对记录键序进一归并的结果为 。三、简答题（本大题共4小题，每小题5分，共20分）四、应用题（本大题共2小题，每小题10分，共20分）关键字序列{19，14，23，01，68，20，84，27}，哈希函数H(key)=key%13，用链地址法处理冲突。（1）构造哈希表。（5分）（2）求等概率情况下查找成功的平均查找长度ASL。（3分）（3）求等概率情况下查找不成功的平均查找长度ASL。（2分）对下图用Prim算法从顶点1开始构造最小生成树，写出每一步选择的边和顶点。边权：(1,2)=3，(1,3)=4，(1,4)=5，(2,3)=2，(2,5)=6，(3,4)=1，(3,5)=7，(4,5)=8五、算法设计题（本大题共2小题，每小题10分，共20分）LO(1)。C问题：设计算法判断二叉树是否为完全二叉树。要求：写出算法思想、类C语言算法。参考答案及评分标准（试卷七）一、单项选择题（每题2分）1.B 2.A 3.A 4.B 5.A 6.C 7.B 8.A 9.B 10.A二、填空题（每题2分）⌈log₂(5!)=log₂120≈6.9→7；n(n−1)/2=5×4/2=10）h4. 1，25. 1+N₂+2N₃+3N₄+…+(m−1)Nm（）（解析：树的性质：总分支数=总结点数−1，总分支数=1•N₁+2•N₂+…+m•Nm；总结点数=N₀+N₁+…+Nm。所以N₁+2N₂+…+mNm=(N₀+N₁+…+Nm)−1⇒N₀=1+N₂+2N₃+3N₄+…+(m−1)Nm）6. 80，75，55，56，63，44，31，38等于BDCA）10.15，25，35，50，20，40，80，85，36，70三、简答题（每题5分）入栈（）（入队（出队）（（（BFS）1。O(log₂n)O(n)在插入或删除后自动调整结构，保持树的平衡性，从而保证所有操作的时间复杂度稳定在O(log₂n)，提高效率。DFS（1）（n−1iinin−1次。（2）堆排序：）或最小四、应用题哈希表（1）哈希地址：ASL（2）插找成功的平均查找长度ASL定义：ASL=所有关键字查找长度之和÷关键字总数。ASL成功=(1+2+3+1+1+2+1+1)/8=12/8=1.5（3）ASL（13==ASL不成功=(0+3+0+1+0+0+2+1+0+0+1+0+0)/13=8/13(≈0.615)Prim算法1(1,2)=32(1,3)=4，(1,4)=5，(2,3)=2，(2,5)=6，选(2,3)=23(1,4)=5，(3,4)=1，(3,5)=7，选(3,4)=14(4,5)=8，选(2,5)=65生成树：1-2，2-3，3-4，2-5；总权值=3+2+1+6=12五、算法设计题1．链表逆置（1）算法思想（5分）：采用迭代法从第一个实际数据结点开始，逐个将结点的next指针反向：① pL->next）q：p（）rNULL）② pnextrr=p，p=q③ pL->nextr（。O(1)O(n)。（2）算法描述（5分）：//单链表结构定义typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidReverseList(LinkListL //L是带头结点的单链表LNode*p,*q,*r;p=L->next; //p指向第一个数据结点r=NULL; //r指向已逆置部分的首结点（初始为空）while(p!=NULL){q=p->next; //保存下一个结点p->next=r; //将当前结点指向前一个（反转指针）r=p; //r前移p=q; //p移到下一个待处理结点}L->next=r; //头结点指向新的首元结点}2．判断完全二叉树（1）算法思想（5分）：判断方法（基于层序遍历）：①对二叉树进行层序遍历（使用队列）。②在遍历过程中：（NULL），③具体步骤：（O(n)（2）算法描述（5分）：//二叉树二叉链表结构定义typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//判断是否为完全二叉树intIsCompleteBinaryTree(BiTreeT){if(T==NULLreturn1; //空树视为完全二叉树QueueQ;InitQueue(&Q);EnQueue(&Q,T);BiTNode*p;while(!QueueEmpty(Q //层序遍历，直到遇到第一个空结点DeQueue(Q,p);if(p==NULLbreak; //遇到空结点，停止入队//无论孩子是否为空，都入队（关键！）EnQueue(Q,p->lchild);EnQueue(Q,p->rchild);}whileQueueEmpty(Q //检查队列中剩余结点是否全为空DeQueue(Q,p);if(p!=NULL)return0; //出现非空结点，不是完全二叉树}return1; //是完全二叉树}说明：Queue、InitQueue、EnQueue、DeQueue、QueueEmpty为队列的基本操作，假设已实现。C语言的描述（C语言的描述（2版）期末考试试卷及参考答案（八）PAGE1《数据结构》期末考试试卷（八）考试时间：100分钟满分：100分注意事项：C一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后括号内。（）存储2. 09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）（）for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;O(m+n)qpAs指向XABX（）s->next=p->next;p->next=s;q->next=s;s->next=p;p->next=s->next;s->next=p;p->next=s;s->next=q;、、3、5、6（）A.5，3，4，6，1，2B.3，2，5，6，4，1C.3，1，2，5，4，6D.1，5，4，6，2，310551A[5][4]A[0][0]（）10192855（）8. (50，40，95，20，15，70，60，45)d=44（）A.40，50，20，95B.15，40，60，20C.15，20，40，50D.45，40，15，209. 52）A.15，25，35，50，20，40，80，85，36，70B.15，25，35，50，80，20，85，40，70，36C.15，25，35，50，80，85，20，36，40，70D.15，25，35，50，80，20，36，40，70，85SubString(&Sub,"DATASTRUCTURE",5,9)Sub（）"STRUCTURE""DATA""ASTRUCTUR""DATASTRUCTURE"二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。psA的后插点X的序列为 。设完有图有n个点该全向中有 条向完全向图中有n个点则完无向中有 无向。设关字列为用筛选建则须从第 个素始。解决希突两主方法是 和 。50023的点有 高为h完二树最少有 个点最多有 个点。设有组始键序为第3直插序结后的结是 。设有组始键序为第3简选序结后的结是 。设一二树前遍序列中遍序均为ABC，该叉的遍历列为 。设有顺表有n据元，利二查法查数元素X的比较数不超过 。三、简答题（本大题共4小题，每小题5分，共20分）四、应用题（本大题共2小题，每小题10分，共20分）已知一棵二叉树的先序遍历序列为ABDEGCFH，中序遍历序列为DBGEACHF，（1）画出该二叉树。（5分）（2）写出该二叉树的后序遍历序列。（2分）（3）将该二叉树转换为对应的森林。（3分）对关键字序列{36，28，45，13，67，36，25，18}进行排序，（1）写出直接插入排序的前3趟结果。（4分）（2）写出冒泡排序的前3趟结果。（3分）（3）写出归并排序的第一趟归并结果。（3分）五、算法设计题（本大题共2小题，每小题10分，共20分）xO(n)O(1)。C问题：设计算法复制一棵二叉树，返回新树的根结点指针。要求：写出算法思想、类C语言算法。参考答案及评分标准（试卷八）一、单项选择题（每题2分）1.C 2.B 3.C 4.B 5.B 6.B 7.A 8.B 9.A 10.A二、填空题（每题2分）1. s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;2. n(n-1)，n(n-1)/23. ⌊n/2⌋4. 5. n=n0+n1+n2+n3=n1+2n2+3n3n1+2n2+3n3=(n0+n1+n2+n3)−1；整理并代入：n2=21，n0=50；⇒n3=14）6. 2^(h-1)，2^h-17. 12，24，35，27，18，268. 12，18，24，27，35，26CBA10.⌊log₂n⌋+1三、简答题（每题5分）1. （1）（（（2）不同点：栈：限定仅在一端（栈顶）进行插入和删除，遵循“后进先出（LIFO）”原则；（FIFO）”原则。（1）n（2）构造方法：每次从森林中选出两个权值最小的树合并，生成新结点（权为两者之和），重复直至只剩一棵树。（3）（）：如如（1）O(1)；（O(n)时（2）邻接表：优点：空间复杂度为O(n+e)，节省空间（尤其稀疏图）；遍历某顶点的所有邻接点只需O(度)时间，效率高。缺点：判断两顶点是否相邻需遍历链表，时间复杂度O(度)；结构稍复杂，需动态分配内存。总结：稠密图用邻接矩阵，稀疏图用邻接表。（1））；O(n)（），平均O(n²)（2）快速排序：部≥pivot；关键区别：冒泡是相邻交换、逐个“冒泡”；快排是分区+递归、跳跃式调整。四、应用题二叉树（1）二叉树如下：（2）后序：DGEBHFCA（3）二叉树转换为三棵树组成的森林如下：（1）直接插入排序前3趟：第1趟：28,36,45,13,67,36,25,18第2趟：28,36,45,13,67,36,25,18第3趟：13,28,36,45,67,36,25,18（2）冒泡排序前3趟：第1趟：28,36,13,45,36,25,18,67第2趟：28,13,36,36,25,18,45,67第3趟：13,28,36,25,18,36,45,67（3）归并排序的第一趟归并结果：28,36,13,45,36,67,18,25四、算法设计题x（1）算法思想（5分）：采用双指针（快慢指针）法，在一次遍历中完成删除操作：i（）k（）即≠x）k。L.data[i]!=xL.data[k]k++L.data[i]==x，（）。k。该方法原地覆盖，不使用额外数组，时间复杂度为O(n)，空间复杂度为O(1)。（2）算法描述（5分）：//顺序表结构定义#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];intlength; //当前长度}SqList;//Lx的元素voidDeleteAllX(SqList*L,intx){intk=0; //k（即保留元素的个数）for(inti=0;i<L->length;i++){if(L->data[i]!=x){L->data[k]=L->data[i]; //x元素k++;}//若L->data[i]==x，则跳过（不保留）}L->length=k; //更新顺序表长度}说明：该算法稳定（x元素的相对顺序）；仅遍历一次，时间复杂度为O(n)；仅使用常数个辅助变量（i,k），空间复杂度为O(1)；适用于顺序存储结构（如数组实现的线性表）。（1）算法思想（5分）：采用递归方法：若原树为空（NULL），则新树也为空，直接返回NULL；否则：该过程按照先序遍历的顺序进行，形成一棵结构和内容完全相同的新二叉树。（2）算法描述（5分）：//二叉树二叉链表结构定义typedefstructBiTNode{intdata; //假设数据域为整型（可根据需要修改）structBiTNode*lchild; //左孩子指针structBiTNode*rchild; //右孩子指针}BiTNode,*BiTree;//复制二叉树，返回新树的根指针BiTreeCopyTree(BiTreeT){if(T==NULL)returnNULL; //空树，返回空//创建新结点BiTreenewRoot=newBiTNode;newRoot->data=T->data;//递归复制左右子树newRoot->lchild=CopyTr