《2012-广东省数据结构考试基础》由会员分享，可在线阅读，更多相关《2012-广东省数据结构考试基础（15页珍藏版）》请在金锄头文库上搜索。
1、1、编写一个过程，对一个nn矩阵，通过行变换，使其每行元素的 平均值按递增顺序排列。 2、 连通图的生成树包括图中的全部 n 个顶点和足以使图连通的 n-1 条边，最小生成树是边上权值之和最小的生成树。故可按权值从大 到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最 大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍 连通，继续向下删；直到剩 n-1 条边为止。 void SpnTree (AdjList g) /用“破圈法”求解带权连通无向图的一棵最小代价生成树。 typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整 型数 no
2、de edge; scanf( %d%d, /输入边数和顶点数。 for (i=1;i=e;i+) /输入 e 条边：顶点，权值。 scanf(%d%d%d , for (i=2;i=e;i+) /按边上的权值大小，对边进行逆序 排序。 edge0=edgei; j=i-1; while (edgej.w=n) /破圈，直到边数 e=n-1. if (connect(k) /删除第 k 条边若仍连通。 edgek.w=0; eg-; /测试下一条边 edgek，权值 置 0 表示该边被删除 k+; /下条边 /while /算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现
3、， 3、我们可用 “破圈法”求解带权连通无向图的一棵最小代价生成树。 所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步 骤，直到没有圈为止。请给出用 “破圈法”求解给定的带权连通无向图的 一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注： 圈就是回路。 4、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二 叉树。 29. 试找出满足下列条件的二叉树 1）先序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同 5、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判 左右子树是否相似，采用递归算法。
4、int Similar(BiTree p,q) /判断二叉树 p 和 q 是否相似 if(p=null else if(!p else return(Similar(p-lchild,q-lchild) /设顶点信息就是顶点编号，权是整 型数 node edge; scanf( %d%d, /输入边数和顶点数。 for (i=1;i=e;i+) /输入 e 条边：顶点，权值。 scanf(%d%d%d , for (i=2;i=e;i+) /按边上的权值大小，对边进行逆序 排序。 edge0=edgei; j=i-1; while (edgej.w=n) /破圈，直到边数 e=n-1. if
5、(connect(k) /删除第 k 条边若仍连通。 edgek.w=0; eg-; /测试下一条边 edgek，权值 置 0 表示该边被删除 k+; /下条边 /while /算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现， 7、有一种简单的排序算法，叫做计数排序 （count sorting）。这种排 序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放 到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相 同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表 中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录， 统计出的计数值
6、为 c，那么，这个记录在新的有序表中的合适的存放位 置即为 c。 (1) (3 分)给出适用于计数排序的数据表定义; (2) (7 分)使用 Pascal 或 C 语言编写实现计数排序的算法； (3) (4 分)对于有 n 个记录的表，关键码比较次数是多少? (4) (3 分)与简单选择排序相比较，这种方法是否更好?为什么? 8、假设以 I 和 O 分别表示入栈和出栈操作。栈的初态和终态均为 空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操 作的序列为合法序列，否则称为非法序列。（15 分） （1）A 和 D 是合法序列，B 和 C 是非法序列。 （2）设被判定的操作序列已存入一
7、维数组 A 中。 int Judge(char A) /判断字符数组 A 中的输入输出序列是否是合法序列。 如 是，返回 true，否则返回 false。 i=0; /i 为下标。 j=k=0; /j 和 k 分别为 I 和字母 O 的的个 数。 while(Ai!=0) /当未到字符数组尾就作。 switch(Ai) caseI: j+; break; /入栈次数增 1。 caseO: k+; if(kj)printf(“序列非法 n”)；exit(0); i+; /不论 Ai是I或O，指针 i 均后移。 if(j!=k) printf(“序列非法n”)；return(false); els
8、e printf(“序列合法n”)；return(true); /算法结束。 9、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上， 层次遍历序列中的每个结点都是 “局部根”。确定根后，到二叉树的中序 序列中，查到该结点，该结点将二叉树分为“左根右”三部分。若左、右 子树均有，则层次序列根结点的后面应是左右子树的根；若中序序列中 只有左子树或只有右子树，则在层次序列的根结点后也只有左子树的 根或右子树的根。这样，定义一个全局变量指针 R，指向层次序列待处 理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然 后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据 结构定
9、义如下： typedef struct int lvl; /层次序列指针，总是指向当前“根结点”在层次 序列中的位置 int l,h; /中序序列的下上界 int f; /层次序列中当前“根结点”的双亲结点的指针 int lr; / 1双亲的左子树 2双亲的右子树 qnode; BiTree Creat(datatype in,level,int n) /由二叉树的层次序列 leveln和中序序列 inn生成二叉树。 n 是 二叉树的结点数 if (ndata=level0; p-lchild=null; p-rchild=null; /填写该结点数 据 for (i=0; ilchild=n
10、ull; s.lvl=+R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s); else if (i=n-1) /根结点无右子树，遍历序列的 1n-1 是左子树 p-rchild=null; s.lvl=+R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); else /根结点有左子树和右子树 s.lvl=+R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);/左子树有关 信息入队列 s.lvl=+R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enq
11、ueue(Q,s);/右子树有关 信息入队列 while (!empty(Q) /当队列不空，进行循环，构造二叉树的左右 子树 s=delqueue(Q); father=s.f; for (i=s.l; idata=levels.lvl; p-lchild=null; p-rchild=null; /填写该 结点数据 if (s.lr=1) father-lchild=p; else father-rchild=p； /让双亲的子女指针指向该结点 if (i=s.l) p-lchild=null; /处理无左子女 s.lvl=+R; s.l=i+1; s.f=p; s.lr=2; enque
12、ue(Q,s); else if (i=s.h) p-rchild=null; /处理无右子女 s.lvl=+R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); elses.lvl=+R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);/左子 树有关信息入队列 s.lvl=+R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); /右子树有 关信息入队列 /结束 while (!empty(Q) return(p); /算法结束 10、 将顶点放在两个集合 V1 和 V2。对每个顶点，检查其和邻接 点是否在同一
13、个集合中，如是，则为非二部图。为此，用整数 1 和 2 表 示两个集合。再用一队列结构存放图中访问的顶点。 int BPGraph (AdjMatrix g) /判断以邻接矩阵表示的图 g 是否是二部图。 int s; /顶点向量，元素值表示其属于那个集合 （值 1 和 2 表示两个集合） int Q;/Q 为队列，元素为图的顶点，这里设顶点信息就 是顶点编号。 int f=0,r,visited; /f 和 r 分别是队列的头尾指针,visited 是访问数组 for (i=1;i=n;i+) visitedi=0;si=0; /初始化，各顶点 未确定属于那个集合 Q1=1; r=1; s1
14、=1;/顶点 1 放入集合 S1 while(fr) v=Q+f; if (sv=1) jh=2; else jh=1;/准备v的邻接点的集合号 if (!visitedv) visitedv=1; /确保对每一个顶点，都要检查与其邻接点不应 在一个集合中 for (j=1,j=n;j+) if (gvj=1)if (!sj) sj=jh; Q+r=j; /邻接点入队列 else if (sj=sv) return(0); /非二部图 /if (!visitedv) /while return(1); /是二部图 算法讨论 题目给的是连通无向图，若非连通，则算法要修改。 11、#define maxsize 栈空间容量 void InOutS(int smaxsize) /s 是元素为整数的栈，本算法进行入栈和退栈操作。 int top=0; /top 为栈顶指针，定义 top=0 时为栈 空。 for(i=1; i=n; i+) /n 个整数序列作处理。 scanf(“%d”, /从键盘读入整数序列。 if(x!=-1) / 读入的整数不等于-1 时入栈。 if(top=maxsize-1)printf(“栈满n”);exit(0); else s+top=x; /x 入栈。 else /读入的整数等于-1 时退栈。 if(top=
