2015江苏省数据理论基础文档.pdfVIP

1、假设以I 和O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列 可表示为仅由 I 和 O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15 分） （1）下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true，否则返回false （假定被判定的操作序列已存入一维数组中）。 2、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。 int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k1) 层上叶子结点个数 {if(bt==null || k1) return(0); BiTree p=bt,Q[]; //Q 是队列，元素是二叉树结点指针,容量足够大 int front=0,rear=1,leaf=0; //front 和rear 是队头和队尾指针, leaf 是叶子结点数 int last=1,level=1; Q[1]=p; //last 是二叉树同层最右结点的指针，level 是二叉树的层 数 while(front=rear) {p=Q[++front]; if(level==k !p-lchild !p-rchild) leaf++; //叶子结点 if(p-lchild) Q[++rear]=p-lchild; //左子女入队 if(p-rchild) Q[++rear]=p-rchild; //右子女入队 if(front==last) {level++; //二叉树同层最右结点已处理,层数增1 last=rear; } //last 移到指向下层最右一元素 if(levelk) return (leaf); //层数大于k 后退出运行 }//while }//结束LeafKLevel 3、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排 列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后 选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各 元素也必须做相应变动。 void Translation （float *matrix，int n） //本算法对n×n 的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。 {int i,j,k,l； float sum，min； //sum 暂存各行元素之和 float *p, *pi, *pk; for(i=0; in; i++) {sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1 个元素. for (j=0; jn; j++){sum+=*(pk); pk++;} //求一行元素之和. *(p+i)=sum; //将一行元素之和存入一维数组. }//for i for(i=0; in-1; i++) //用选择法对数组p 进行排序 {min=*(p+i); k=i; //初始设第i 行元素之和最小. for(j=i+1;jn;j++) if(p[j]min) {k=j; min=p[j];} //记新的最小值及行号. if(i!=k) //若最小行不是当前行,要进行交换(行元素及行元素之和) {pk=matrix+n*k; //pk指向第k 行第1 个元素. pi=matrix+n*i; //pi 指向第i 行第1 个元素. for(j=0;jn;j++) //交换两行中对应元素. {sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;} sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和. }//if }//for i free(p); //释放p 数组. }// Translation [算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方 法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2). 4、设一