12级数据结构期末试卷_A答案

《12级数据结构期末试卷_A答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构与算法A卷答案12-13学年第一学期一、选择题：（本题共20小题，每题2分，共40分〉1-5：AABDC6-10：DDDBC11-15：CBCDD16-20：ABCAB二、分析运算题（本题共6小题，每题5分，共30分》（1）如果输入序列为123,先进入栈结构后进入队列结构，试写出所有的出队列序列JuHuduuuJu歹歹歹歹歹歹o序序芋序序序17)z17)z177^7.分分分分分03111A1A1111•二-z(xz«z(xzfzl（2）假设一棵二叉树的前序（先序）遍历序列为ABDECF和中序序列为DBEAFC,画出二叉树并写出后序遍历序列。①

2、（3分）②后序遍历：DEBFCA（2分）（3）用二叉树表示算术表达式如图1所示。①按图画出对应的算术表达式②写出后序（后缀）表达式算术表达式：（a+b+c*（d+e）+f）*（g+h）（2分）后序表达式：ab+cde+*+f+gh+*（3分）（4）请写出有向图2中顶点1-6的入度和出度1：入度：3出度：02:入度：2出度：2度度度度入入入入度度度度岀岀出出1122:1:3（入度25分，岀度25分）（5）给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权夕卜部路径长度的树称为huffman（赫夫曼）树。给定项及相应的权如下表：画出相应的huffman树

3、。（5分）l=JHF（6）已经邻接矩阵如图3所示，判断该图是有向图还是无向图，用顶点1・6画出该图。有向图（2分）（3分）三、程序填空题（本题共5空，每空2分，共10分〉77717712345/{/(z(z(zz(p!=NULLp=p->next;Q.front=二Q.rearQ.front~>next=p->next;Q.rear=Qfront;!1!、算法设计题（本题共2小题,共20分〉1、(10分)算法如下:voidmove(sqlistL)inti=0,j=L.lenght-1,k;1分inttemp;while(i

4、(L.elem[i]<=0)i++;2分while(L.elem[j]>=0)j―;2分if(ilchild==NULL&&T->rchild==NULL)return1;elsereturn(leaf(T->lchild)+leaf(T->rchild));