2011年福建省数据总结加强
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、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。 #include typedef char datatype; typedef struct node{ datatype data; struct node * next; } listnode; typedef listnode* linklist; /*--------------------------------------------*/ /* 删除单链表中重复的结点 */ /*--------------------------------------------*/ linklist deletelist(linklist head) { listnode *p,*s,*q; p=head->next; while(p) {s=p; q=p->next; while(q) if(q->data==p->data) {s->next=q->next;free(q); q=s->next;} else { s=q; /*找与P结点值相同的结点*/ q=q->next; } p=p->next; } return head; } 3、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。