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

C语言的描述（C语言的描述（2版）期末考试试卷及参考答案（六）PAGE1《数据结构》期末考试试卷（六）考试时间：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=CopyTree(T->lchild);newRoot->rchild=CopyTree(T->rchild);returnnewRoot; //返回新树的根}说明：new分配；使用完毕后，应由调用方负责释放：delete，避免内存泄漏。C语言的描述（C语言的描述（2版）期末考试试卷及参考答案（九）PAGE10《数据结构》期末考试试卷（九）考试时间：100分钟满分：100分注意事项：C一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后括号内。（）（head（）head==0head->next==0head->next==headhead!=0O(nlog₂n)的是（）（）（）40（）3456（）O(n)O(n²)O(n^½)O(log₂n)（）O(n)O(nlog₂n)O(log₂n)k（）A.2^(k-1)-1B.2^(k-1)C.2^k-1D.2^k二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。pAAq=p->next;p->next= ;free(q);设完有图有n个点，该全向中有 条向。设关字列为用筛选建则须从第 个素始。解决希突两主方法是 和 。设一树T度为4，中为1,2,3,4的点分为4,2,1,1，则T叶子点数。6. 设一初记关字列为则用选法立的初堆为 。设有图G存结邻接阵A表，则A中第i中有零个数和等于点i的 。设前遍某叉的列为序历二叉的为则后遍历该二树序为 。设哈数H(k)=kmod决突方为址求算中一个键字时，先算其 然后历链。10.设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个度为2有子则用并序方对记录键序进一归并的结果为 。三、简答题（本大题共4小题，每小题5分，共20分）四、应用题（本大题共2小题，每小题10分，共20分）H(key)=key%11（1）构造哈希表。（5分）（2）求等概率情况下查找成功的平均查找长度ASL。（3分）（3）求等概率情况下查找不成功的平均查找长度ASL。（2分）用Dijkstra算法求下图中从顶点A到其他各顶点的最短路径，写出执行过程。五、算法设计题（本大题共2小题，每小题10分，共20分）问题：将两个递增有序的单链表合并为一个递减有序的单链表，要求利用原链表结点。要求：写出算法思想、类C语言算法。问题：设计算法将二叉树中所有结点的左右子树互换。要求：写出算法思想、类C语言算法。参考答案及评分标准（试卷九）一、单项选择题（每题2分）1.C 2.A 3.A 4.A 5.B 6.D 7.B 8.A 9.C 10.B二、填空题（每题2分）1. q->next2. n(n-1)3. ⌊n/2⌋（n/2）4. 5.8（=；n0=n−8=8）6. 80，75，55，56，63，44，31，38入度BDCA）10.15，25，35，50，20，40，80，85，36，70三、简答题（每题5分）（1）存储空间：结点）（2）空间分配：（3）访问效率：O(1)。O(n)。（4）插入/删除操作：O(n)。O(n)。（5）内存局部性：（。（1）（2）查找过程：从根结点开始，设待查关键字为key：keykeykey该过程可递归或迭代实现，平均时间复杂度为O(log2n)，最坏（退化为链表）为O(n)。（1）（DFS）：（2）广度优先遍历（BFS）：（）。（1）直接插入排序：O(n)O(n2)。（2）希尔排序：dkdkdk=1O(nlog2n)。（3）主要区别：四、应用题关键字序列：{22,41,53,46,30,13,01,67}哈希函数：H(key)=keymod11冲突处理：线性探测法哈希表大小：由于模11，通常取表长m=11（地址0～10）（1）构造哈希表（地址0～10）：将结果填入长度为11的哈希表（下标0～10）：空位用“∅”表示。（2）查找成功的平均查找长度（ASL成功）（=（）。每个关键字的探测次数：总比较次数=1+1+1+2+4+1+1+3=14，关键字个数n=8，所以：ASL成功=14/8=1.75（3）查找不成功的平均查找长度（ASL不成功）（0注意：查找失败时，必须探测到第一个空位置才停止。i（0≤i≤10）keyH(key)=ikeyi总和=6+5+4+3+2+1+1+1+9+8+7=47，共有m=11个可能的哈希地址（等概率）所以：ASL不成功=47/11≈4.27Dijkstra算法初始：S={A}，dist={0，3，∞，2，∞，∞}D，S={A,D}dist[E]=3，dist={0，3，∞，2，3，∞}B，S={A,D,B}dist[C]=4，dist={0，3，4，2，3，∞}E，S={A,D,B,E}dist[F]=5，dist={0，3，4，2，3，5}C，S={A,D,B,E,C}，dist={0，3，4，2，3，5}F最终结果：四、算法设计题）（1）算法思想（5分）：（2）算法描述（5分）：//单链表结构定义typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;//L1、L2L1的头结点作为结果链表头结点LinkListMergeDescend(LinkListL1,LinkListL2){LNode*p1=L1->next; //L1的第一个数据结点LNode*p2=L2->next; //L2的第一个数据结点LNode*temp;while((p1!=NULL)&&(p2!=NULL) //合并过程：每次选较小的结点，头插if(p1->data<=p2->datatemp=p1;p1=p1->next;}else{temp=p2;p2=p2->next;}temp->next=L1->next; //L1中L1->next=temp;}//处理剩余的L1结点（如果还有）while(p1!=NULL){temp=p1;p1=p1->next;temp->next=L1->next;L1->next=temp;}//L2结点（如果还有）while(p2!=NULL){temp=p2;p2=p2->next;temp->next=L1->next;L1->next=temp;}DeleteL2; //L2的头结点returnL1;}说明：next指针，没有创建新结点。L1L1成为递减链表。头插法：每次取下较小结点，插入结果链表头部，实现递增变递减。L2链表已不存在，释放其头结点避免内存泄漏。（1）算法思想（5分：）（2）算法描述（5分）：//二叉树二叉链表结构定义typedefstructBiTNode{intdata; //数据域（类型可泛化）structBiTNode*lchild; //左孩子指针structBiTNode*rchild; //右孩子指针}BiTNode,*BiTree;//将二叉树中所有结点的左右子树互换（镜像）voidSwapChildren(BiTreeT){if(T==NULLreturn; //空树，直接返回//交换当前结点的左右孩子指针BiTNode*temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;//递归处理左子树（注意：此时左子树已是原来的右子树）SwapChildren(T->lchild);//递归处理右子树（此时右子树是原来的左子树）SwapChildren(T->rchild);}说明：函数无返回值，直接在原树上修改（原地操作；时间复杂度：O(n)，每个结点访问一次；空间复杂度：，h为树高（递归栈深度，最坏)（退化为链表。C语言的描述（C语言的描述（2版）期末考试试卷及参考答案（十）PAGE10《数据结构》期末考试试卷（十）考试时间：100分钟满分：100分注意事项：C一、单项选择题（本大题共10小题，每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后括号内。程序：i=1;while(i<=n)i=i*2; 的时间复度（）O(n)O(log₂n)O(nlog₂n)p）q=p->next;p->data=q->data;p->next=q->next;free(q);q=p->next;q->data=p->data;p->next=q->next;free(q);q=p->next;p->next=q->next;free(q);q=p->next;p->data=q->data;free(q);6（5678n（）nn/2C.(n+1)/2D.(n-1)/25. (13，18，24，35，47，50，62)24的元素需要经过（）次比较。1234、、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，365（）8765212223（）05678GE={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)}a（）aedfcbacfebdaebcfdaedfbc（）i=0，s=0;while(s<n){i++;s=s+i;}O(n)O(n^½)O(log₂n)二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。

的集合。

指示。n

个元素。在二树，针p所结点叶结的件是 。深为k完二树少有 个点。在有表A[1..12]，用二查算查等于A[12]的元，比的素下依次为 。700

个叶子结点。8. V={a,b,c,d,e}，E={(a,b),(a,c),(b,d),(c,e),(d,e)}a出发进深优遍，得到一顶序是 。在堆序快排果从均况排速最快角来虑选排序。已知叉中子为50，仅一孩的点为30，总点为 。三、简答题（本大题共4小题，每小题5分，共20分）四、应用题（本大题共2小题，每小题10分，共20分）1. ((a+b)-c*(d+e)+f)/g2. {45,24,53,12,37,93,30,76,48}：（1）构造二叉排序树。（2）删除结点45后的二叉排序树。（3）计算该二叉排序树（原树）的平均查找长度（假设每个元素查找概率相等）。五、算法设计题（本大题共2小题，每小题10分，共20分）ijC问题：实现二叉树的层次遍历（从上到下，从左到右）。要求：写出算法思想、类C语言算法。参考答案及评分标准（试卷十）一、单项选择题（每题2分）1.B 2.A 3.A 4.C 5.C 6.B 7.B 8.C 9.A 10.B二、填空题（每题2分）3. n-14. 左右子为或p->left==NULL&&p->right==NULL）5. 2^(k-1)6. 6，9，11，127. 350（=⌈n/2⌉，n0=⌈n/2⌉=350）abdecacedb快速10.12n₀n₂1→n₂₀14₀n₁₂5009129）三、简答题（每题5分）（1）（2）折半查找（二分查找）：（（。（1）（2）线索化的目的：（nn+1）（O(1)O(n)：（AOVAOE网。（1）拓扑排序：输入：AOV网（。（2）关键路径：输入：AOE（）。（）/（1）O(log2n)（）O(n)。//AVL）。（2）哈希表：O(1)；最坏）O(n)。+（））。/总结：哈希表适合快速精确查找；二叉排序树适合需要有序性和范围查询的场景。四、应用题（1）"("遇到右括号")"，将栈中的运算符弹出并添加到输出，直到遇到左括号为止，然后((a+b)-c*(d+e)+f)/g((a+b)ab+(ab+)cab+c-(ab+c-)*d+e)ab+c-de*-(ab+c-de*fab+c-de*-f+(ab+c-de*-f/gab+c-de*-f+g/因此，最终的后缀表达式是：ab+cde+*-f+g/（2）求值过程中栈的变化关于求值过程中栈的变化，以下是简化的示意过程（具体数值会根据实际输入改变）：a[a]b[a,b]+[ab+]c[ab+,c]d[ab+,cd]e[ab+,c,d,e]+[abc,de+]输入[abcde+*-]输入-[ab+cde+*-,]f[ab+cde+*f]+[ab+cde*-f+]g[ab+cde*-fg]输入[ab+cde*-f+g/]（1）（2）45（345时）ASL成功）：1:45（1）2:24（2），53（2）3:12（3），37（3），48（3），93（3）4:30（4），764总比较次数=1+(22)