68数据结构

1.将森林转换为二叉树。用左子女-右兄弟表示实现的树定义：typedefstructnode{TreeDatadata;structnode*firstChild,*nextSibling;}TreeNode;2.图的邻接矩阵、邻接表的存储表示。图的邻接矩阵存储：两点之间有边矩阵对应的位置处填1，两点之间无边对应位置处填0EdgeDataEdge[NumVertices][NumVertices];图的邻接表存储：2.计算AOE网络的关键路径。完成整个工程所需的时间取决于从源点到汇点的最长路径长度,即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径关键活动：最早开始时间和最晚开始时间相等4.画出下图的结构，并分别给出以A顶点开始的深度优先遍历和广度优先遍历。12NULL03NULL031225NULL34NULL0123454NULL5NULLABCDEF深度优先搜索：ABDCEFBCADFE广度优先搜索：ABCDEF5.(1)哈希函数常用的构造方法有哪些?处理冲突的方法有哪些？(2)用除留余数法构建哈希表，并以线性探测再散列处理冲突。1、常用的构造方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法处理冲突的方法：开放定址法、再哈希法、链地址法2、除留余数法：H(key)=key%p------------m为表长，p为不大于m的素数P为素数？如key（关键字）：123918243321若p=9则哈希函数值为：330663可见，当p的因子中含有素数3，则所有含因子3的关键字都对应到“3的倍数”的地址上，从而增加了冲突的可能!/**表长为6，关键字个数6，p=m且p为素数，故p取5,但是这样最后一个数21将永远不会放到下标为5的地方！那么这个p的取法不是有错吗？还是说表长必须比给的关键字个数大？**/如key（关键字）：123918243321若p=7则哈希函数值为:544350先行探测在散列处理冲突：Key=18：18%7=4(冲突)(4+1)%7=5(冲突)(5+1)%7=6key=33:33%7=5（冲突）(5+1)%7=6（冲突）(6+1)%7=0Key=21:21%7=0(冲突)(0+1)%7=1所以最后得：54630101234563321243912186.证明二叉树性质：n0=n2+1(n0度为0的结点；n2:度为2的结点)n1为度为1的节点，e表示二叉树的边数；这里用到的一个等式是二叉树边的两种表达:e=n0+n1+n2-1//每一个节点对应一条边，根节点除外所以减一e=2*n2+n1//2倍的度为2的节点数目加上度为1的节点数目，就是边的数目得：n0=n2+n17.求最小生成树1、Prim（普里姆）算法从连通图中的某一顶点u0出发,选择与它关联的具有最小权值的边，将其顶点加入到生成树顶点集合中2、Kruskal（克鲁斯卡尔）算法对每一条边按照权值从小到大排序，每一次选择最小的权值的边，注意避免选择出现环的边！8.以权重集合{4,5,6,7,8}构建哈夫曼树（霍夫曼树）。带权路径长度达到最小的二叉树即为哈夫曼树。9.给出用下列关键字构建大顶堆的全过程，关键字集合为{7040558174184670}01234567704055817418467010.给出上述集合数据的快速排序的过程选定初始关键字temp，首先从右向左遍历，当遇到比temp小的时候，就让a[i]=a[j],i++;然后重左向右遍历，当遇到比temp大的时候，就让a[j]=a[i],j--;然后循环做上述两个过程，直到i==j时，就让a[i]=temp;这时枢轴就是a[i];然后递归调用从（l,i-1）和(i+1,r);11.请按照给出的数字顺序构造二叉排序树。如：50308020409010253585238812.计算从顶点b到其它顶点的最短路径。15defbac2206301012413答题不能这样写，这样写最多2分，要写出步骤！这只是草稿，方便看！Dijkstra逐步求解的过程:b,a,2b,e,10b,a,c,22b,e,d,23b,a,c,f,2813.二叉树计数。1、由二叉树的前序序列和中序序列可唯一地确定一棵二叉树前序序列{ABHFDECKG}//确定根节点中序序列{HBDFAEKCG}//在前序序列确定根节点的基础上，确定左右孩子节点2、计算具有n个结点的不同二叉树的棵数14.给出求顺序表A和B并集和交集的程序实现，要求并集存储在表A当中。运行结果：La:0123456789Lb:024681012141618BingJi:01234567891012141618JiaoJi:02468请按任意键继续...代码：#includeiostream#defineNewSeqList(SeqList*)malloc(sizeof(SeqList))#defineNewListData(int*)malloc(40*sizeof(int))usingnamespacestd;typedefstruct{int*data,length;}SeqList;voidSetL(SeqList*&L){cout请输入共多少数：;cinL-length;for(inti=0;iL-length;++i)cinL-data[i];}voidShow(SeqList*&L){for(inti=0;iL-length;++i)coutL-data[i];coutendl;}boolInL(SeqList*&L,int&key){for(inti=0;iL-length;++i)if(key==L-data[i])returntrue;returnfalse;}voidInsert(SeqList*&L,intkey){L-data[L-length++]=key;}voidDelete(SeqList*&L,int&pos){//pos代表要删除的元素的下标for(inti=pos;iL-length-1;++i)L-data[i]=L-data[i+1];--L-length;}voidUnion(SeqList*&La,SeqList*&Lb){for(inti=0;iLb-length;++i)if(!InL(La,Lb-data[i]))Insert(La,Lb-data[i]);//如果Lb中元素不在La中就把该元素插入到La中}voidIntersect(SeqList*&La,SeqList*&Lb){for(inti=0;iLa-length;++i)if(!InL(Lb,La-data[i])){Delete(La,i);--i;}//如果La中元素不在Lb中就把La中该元素删除}intmain(){SeqList*La=NewSeqList,*Lb=NewSeqList;//NewSeqList用宏定义创建结构体La-data=NewListData;//NewListData用宏定义创建数组Lb-data=NewListData;La-length=Lb-length=0;SetL(La);//向顺序表La输入数据SetL(Lb);//向顺序表Lb输入数据cout输出集合La：;Show(La);cout输出集合Lb：;Show(Lb);Union(La,Lb);//并集cout并集结果：;Show(La);Intersect(La,Lb);//交集cout交集结果：;Show(La);system(pause);return0;}15.用C语言给出邻接表的定义。给出构建邻接表的源程序（先后输入顶点表和边表）。编写程序求顶点表中顶点V的入度和出度。无向图的每个顶点的入度和出度相等，所以只要求出入度即可。有向图求入度和出度有两种方法：1、求入度一个一个遍历，遇到即ans++2、在一个结构体中建立两个表，入度表，和出度表，查询的时候做相同的遍历即可法1：（按无向图来处理的，若按有向图处理只需删去建tail-head的代码即可）运行结果：pleaseinputVertexNumandEdgeNum:45pleaseinputVertexNode:ABCDpleaseinputEdgeasAB10:AC2AB1AD3BC1BD5AChuDuis:3BChuDuis:3CChuDuis:2DChuDuis:2ARuDuis:3BRuDuis:3CRuDuis:2DRuDuis:2请按任意键继续...代码：#includeiostream#includecstringusingnamespacestd;constintVertexNum=10;typedefstructnode{intdex,cost;structnode*link;}EdgeNode;typedefcharVertexData;typedefstruct{VertexDatadata;EdgeNode*first_link;}VertexNode;typedefstruct{VertexNodeVexList[VertexNum];intn,e;}AdjGraph;intFindPos(AdjGraph&G,char&ch){for(inti=0;iG.n;++i)if(G.VexList[i].data==ch)returni;}voidCrateGraph(AdjGraph&G){coutpleaseinputVertexNumandEdgeNum:endl;cinG.nG.e;coutpleaseinputVertexNode:endl;for(inti=0;iG.n;++i){cinG.VexList[i].data;G.VexList[i].first_link=NULL;}coutpleaseinputEdgeasAB10:endl;for(inti=0;iG.e;++i){charch1,ch2;inthead,tail,key;cinch1ch2key;head=FindPos(G,ch1);tail=FindPos(G,ch2);EdgeNode*p=newEdgeNode;p-cost=key;p-dex=tail;p-link=G.VexList[head].first_link;G.VexList[head].first_link=p;p=newEdgeNode;p-cost=key;p-dex=head;p-link=G.VexList[tail].first_link;G.VexList[tail].first_link=p;}}voidEveryChuDu(AdjGraph&G){for(inti=0;iG.n;++i){intans=0;EdgeNode*p=G.VexList[i].first_link;while(p){++ans;p=p-link;}coutG.VexList[i].dataChuDuis:ansendl;}coutendlendl;}voidEveryRuDu(AdjGraph&G){EdgeNode*p;for(inti=0;iG.n;++i){intans=0;for(intj=0;jG.n;++j){if(j==i)continue;p=G.VexList[j].first_link;while(p){if(p-dex==i)++ans;p=p-link;}}coutG.VexList[i].dataRuDuis:ansendl;}coutendl;}intmain(){AdjGraphG;CrateGraph(G);EveryChuDu(G);EveryRuDu(G);system(pause);ret