2013年四川省数据基础.doc

2013年四川省数据基础 [ ], int a,b,c,d, datatype x)//n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中.{i=a; j=d; flag=0; //flag是成功查到x的标志while(ilt;=b amp;amp; jgt;=c)if(A[i][j]==x) {flag=1;break;}else if (A[i][j]gt;x) j--; else i++;if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型.else printf(“矩阵A中无%d 元素”，x)；}算法search结束。[算法讨论]算法中查找x的路线从右上角开始，向下（当xgt;A[i,j]）或向左（当xlt;A[i,j]）。向下最多是m，向左最多是n。最佳情况是在右上角比较一次成功，最差是在左下角（A[b,c]），比较m+n次，故算法最差时间复杂度是O(m+n）。34、设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。void quickpass(int r[], int s, int t){int i=s, j=t, x=r[s];while(ilt;j){while (ilt;j amp;amp; r[j]gt;x) j=j-1; if (ilt;j) {r[i]=r[j];i=i+1;}while (ilt;j amp;amp; r[i]lt;x) i=i+1; if (ilt;j) {r[j]=r[i];j=j-1;}}r[i]=x;}35、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(kgt;1) 层上叶子结点个数{if(bt==null || klt;1) 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(frontlt;=rear){p=Q[++front];if(level==k amp;amp; !p-gt;lchild amp;amp; !p-gt;rchild) leaf++; //叶子结点if(p-gt;lchild) Q[++rear]=p-gt;lchild; //左子女入队if(p-gt;rchild) Q[++rear]=p-gt;rchild; //右子女入队if(front==last) {level++; //二叉树同层最右结点已处理,层数增1last=rear; } //last移到指向下层最右一元素if(levelgt;k) return (leaf); //层数大于k 后退出运行}//while }//结束LeafKLevel36、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2] 记录开始分二路插入。编写实现二路插入排序算法。37、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(kgt;1) 层上叶子结点个数{if(bt==null || klt;1) 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(frontlt;=r