《广东省数据结构考试基础》由会员分享，可在线阅读，更多相关《广东省数据结构考试基础（11页珍藏版）》请在金锄头文库上搜索。
1、、编写一种过程，对一种nn矩阵,通过行变换,使其每行元素的平均值按递增顺序排列。2、 连通图的生成树涉及图中的所有n个顶点和足以使图连通的n1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条目前权值最大的边后，就去测试图与否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩-1条边为止。 void Spnree （AdjLitg) /用“破圈法”求解带权连通无向图的一棵最小代价生成树。tpdef uct it i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( d%,&e,&n)
2、 ; /输入边数和顶点数。 for (i=1;=e；i+) /输入条边：顶点,权值。 caf（d%d%d ,&egei. ，edij ,&edgeiw）; (i;i=e;i+) /按边上的权值大小，对边进行逆序排序。 edge0=gei; =i1;whil（edgej.w） /破圈，直到边数e=n-1. i (connet（k）) /删除第k条边若仍连通。 dgek.w0； g-； /测试下一条边egek，权值置0表达该边被删除k+; /下条边 /whi /算法结束。 connect()是测试图与否连通的函数，可用图的遍历实现，3、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓
3、“破圈法”就是“任取一圈，去掉圈上权最大的边”,反复执行这一环节，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的具体算法,并用程序实现你所给出的算法。注：圈就是回路。4、证明由二叉树的中序序列和后序序列,也可以唯一拟定一棵二叉树。29 试找出满足下列条件的二叉树1）先序序列与后序序列相似 )中序序列与后序序列相似3)先序序列与中序序列相似 4）中序序列与层次遍历序列相似 、两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树，可判左右子树与否相似,采用递归算法。 t mila(BiTreep,q） /判断二叉树p和q与否相似 i（=null& q=nul) re
4、turn (1);lse i(!p& q | & !q) etur （0); ese retun(Siia（p-lcd,qlchd) & Silar(pchid,q-rchil)/结束Simiar6、 连通图的生成树涉及图中的所有n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条目前权值最大的边后,就去测试图与否仍连通,若不再连通,则将该边恢复。若仍连通，继续向下删;直到剩n1条边为止。 vodnTree (Ajs ） /用“破圈法”求解带权连通无向图的一棵最小代价生成树。tedef s nt i,j,wn
5、e； /设顶点信息就是顶点编号，权是整型数 node ede; scan( %d，&e，&） ; /输入边数和顶点数。 fr(i1；ie；i) /输入条边:顶点,权值。 anf（%ddd ,&edgei.i ，&edgei.j ,&dgei.）; or (i=2;e；i+) /按边上的权值大小,对边进行逆序排序。 edge0=dgei; ji-1;whie (edge.wn) /破圈，直到边数e1. i (connec（k)） /删除第k条边若仍连通。 edgek.w=0;e-; /测试下一条边edgek，权值置表达该边被删除； /下条边 /whil /算法结束。 conet()是测试图与否连
6、通的函数,可用图的遍历实现，7、有一种简朴的排序算法,叫做计数排序(oun sortig)。这种排序算法对一种待排序的表(用数组表达)进行排序，并将排序成果寄存到另一种新的表中。必须注意的是，表中所有待排序的核心码互不相似，计数排序算法针对表中的每个记录,扫描待排序的表一趟,登记表中有多少个记录的核心码比该记录的核心码小，假设针对某一种记录，记录出的计数值为c,那么，这个记录在新的有序表中的合适的寄存位置即为c。 (1)(3分)给出合用于计数排序的数据表定义; () (7分）使用Psal或语言编写实现计数排序的算法； (3)(4分)对于有n个记录的表，核心码比较次数是多少？ (4) (3分)与
7、简朴选择排序相比较,这种措施与否更好?为什么？8、假设以I和O分别表达入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表达为仅由I和O构成的序列,称可以操作的序列为合法序列,否则称为非法序列。（5分) （1)A和D是合法序列,B和C是非法序列。 (2）设被鉴定的操作序列已存入一维数组中。 int Jdge(chr A) /判断字符数组A中的输入输出序列与否是合法序列。如是,返回te，否则返回fale。 i=0; /为下标。 j=k0; /和k分别为I和字母O的的个数。 while（i!=0) /当未到字符数组尾就作。 swich(Ai) aseI:+; beak； /入栈次数增1。
8、 caseO: k+；i（kj)pritf(“序列非法n”）；exit(0）; i+;/不管Ai是I或O，指针i均后移。 if(j！k）print(“序列非法n”）；eturn(fas）; else prinf（“序列合法”);tun(tue); /算法结束。、二叉树的层次遍历序列的第一种结点是二叉树的根。事实上，层次遍历序列中的每个结点都是“局部根”。拟定根后，到二叉树的中序序列中，查到该结点,该结点将二叉树分为“左根右”三部分。若左、右子树均有,则层顺序列根结点的背面应是左右子树的根；若中序序列中只有左子树或只有右子树,则在层顺序列的根结点后也只有左子树的根或右子树的根。这样,定义一种全局
9、变量指针R，指向层顺序列待解决元素。算法中先解决根结点，将根结点和左右子女的信息入队列。然后,在队列不空的条件下，循环解决二叉树的结点。队列中元素的数据构造定义如下：tpedef struct itvl； /层顺序列指针,总是指向目前“根结点”在层顺序列中的位置int ,； /中序序列的下上界in ; /层顺序列中目前“根结点”的双亲结点的指针int lr； / 1双亲的左子树 2双亲的右子树qnode; iTrert(datatypei,leve，in n)/由二叉树的层顺序列leveln和中序序列inn生成二叉树。n是二叉树的结点数if (nlhild=nl; prlnul; /填写该结点
10、数据f （i=0; i； +) /在中序序列中查找根结点,然后,左右子女信息入队列 f (ini=level0) reak；i (=0) /根结点无左子树，遍历序列的n-1是右子树 -lchild=nul; s.lvl=+R; s.l=i+1； shn-1; sf=p;s.l=2; equeu(Q,）; ese i (i=n-1)/根结点无右子树,遍历序列的1n-1是左子树-rhldnull； .l=+R; sl=1; si-1； sf； slr=1; enqueue（，s); lse /根结点有左子树和右子树lv=+R;s.l=0; .hi-1; s.f=p; s.l=1;eneue(Q，)
11、;/左子树有关信息入队列s.lvl=+R; s.l=1；.h=n-1;sf=p；s.lr2;nuee(Q，s);/右子树有关信息入队列while (!epty(Q)） /当队列不空，进行循环，构造二叉树的左右子树 s=dee(); father=sf; for (is.l；i=s.; i+) (ini=evels.lv)bea;p(bitetr)mallo(sizeo(inode); /申请结点空间 -data=leveslvl; p-lcild=ll;pchild=null; /填写该结点数据 if (s.r=1) fater-lhild=p; le fterchid=; /让双亲的子女指针指向该结点 if (=s.l） p-lhld=null; /解决无左子女vl=+R; sl=i+1; =p； r2; enquue(Q,s）; ese if (i=s
