1、设有一组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(i while (i while (i } r[i]=x; } 2、我们用l代表最长平台的长度,用k指示最长平台在数组b中的起始位置(下标)。用j 记住局部平台的起始位置,用i指示扫描b数组的下标,i从0开始,依次和后续元素比较,若局部平台长度(i-j)大于l时,则修改最长平台的长度k(l=i-j)和其在b中的起始位置(k=j),直到b数组结束,l即为所求。 void Platform (int b[ ], int N) //求具有N个元素的整型数组b中最长平台的长度。 {l=1;k=0;j=0;i=0; while(i {while(i if(i-j+1>l) {l=i-j+1;k=j;} //局部最长平台 i++; j=i; } //新平台起点 printf(“最长平台长度%d,在b数组中起始下标为%d”,l,k); }// Platform 3、4、void LinkList_reverse(Linklist &L) //链表的就地逆置;为简化算法,假设表长大于2 { p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) { q->next=p;p=q; q=s;s=s->next; //把L的元素逐个插入新表表头 } q->next=p;s->next=q;L->next=s; }//LinkList_reverse 4、设t是给定的一棵二叉树,下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量,且在调用count(t)之前都置为0. typedef struct node {int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t) {if (t->lchild!=NULL) if (1)___ N2++; else NL++; else if (2)___ NR++; else (3)__ ; if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; } 26.树的先序非递归算法。 void example(b) btree *b; { btree *stack[20], *p; int top; if (b!=null) { top=1; stack[top]=b; while (top>0) { p=stack[top]; top--; printf(“%d”,p->data); if (p->rchild!=null) {(1)___; (2)___; } if (p->lchild!=null) (3)___; (4)__; }}}} 5、二部图(bipartite graph) G=(V,E)是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图,使得:V1中的任何两个结点在图G中均不相邻,V2中的任何结点在图G中也均不相邻。 (1).请各举一个结点个数为5的二部图和非二部图的例子。 (2).请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图,并分析程序的时间复杂度。设G用二维数组A来表示,大小为n*n(n为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【 6、对二叉树的某层上的结点进行运算,采用队列结构按层次遍历最适宜。 int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数 {if(bt==null || k<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(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(level>k) return (leaf); //层数大于k 后退出运行 }//while }//结束LeafKLevel