1、函数实现单链表的插入算法。intListInsert(LinkListL,inti,ElemTypee){LNode*p,*s;intj;p=L;j=0;while((p!=NULL)&&(jnext;j++;}if(p==NULL||j>i-1)returnERROR;s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next)p->next=sreturnOK;}/*ListInsert*/2、函数ListDelete_sq实现顺序表删除算法。intListDelete_sq(Sqlist*L,inti){intk;if(i<1||i>L->length)returnERROR;for(k=i-1;klength-1;k++)L->slist[k]=L->slist[k+1]--L->LengthreturnOK;}3、函数实现单链表的删除算法。intListDelete(LinkListL,inti,ElemType*s){LNode*p,*q;intj;p=L;j=0;while((p->next!=NULL)&&(jnext;j++;}if(p->next==NULL||j>i-1)returnERROR;q=p->next;p->next=q->next;*s=q->data;free(q);returnOK;}/*listDelete*/4、栈的基本操作函数：intInitStack(SqStack*S);//构造空栈intStackEmpty(SqStack*S);//判断栈空intPush(SqStack*S,ElemTypee);//入栈intPop(SqStack*S,ElemType*e);//出栈函数conversion实现十进制数转换为八进制数，请将函数补充完整。voidconversion(){InitStack(S);scanf(“%d”,&N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,&e);printf(“%d”,e);}}//conversion5、函数实现串的模式匹配算法。intindex_bf(sqstring*s,sqstring*t,intstart){inti=start-1,j=0;while(ilen&&jlen)if(s->data[i]==t->data[j]){i++;j++;}else{i=i-j+1;j=0;}if(j>=t->len)returni-t->len+1;elsereturn-1;}}/*listDelete*/6、二叉树后序遍历递归算法voidfunction(Bitree*t){if(p!=NULL){function(p->lchild);function(p->rchild);printf(“%d”,p->data);}}7、编写求一棵二叉树中结点总数的算法。答案：（以先序遍历的方法为例）voidcount_preorder(Bitree*t,int*n){if(t!=NULL){*n++;count_preorder(t->lchild);count_preorder(t->lchild);}}8、函数InOrderTraverse(Bitreebt)实现二叉树的中序遍历。voidInOrderTraverse(BiTreebt){if(bt!=NULL){InOrderTraverse(bt->lchild);printf(“%c”,bt->data);InOrderTraverse(bt->rchild);}9、函数depth实现返回二叉树的高度。intdepth(Bitree*t){if(t==NULL)return0;else{hl=depth(t->lchild);hr=depth(t->rchild);if(hl>hr)returnhl+1;elsereturnhr+1;}}10.交换二叉树结点左右子树的递归算法Bitree*function(Bitree*bt){Bitree*t,*t1,*t2;if(bt==NULL)t=NULL;else{t=(Bitree*)malloc(sizeof(Bitree));t->data=bt->data;t1=function(bt->left);t2=function(bt->right);t->left=t2;t->right=t1;}return(t);}11、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。答案：二叉树形态12、编写求一棵二叉树中结点总数的算法。答案：（以先序遍历的方法为例）voidcount_preorder(Bitree*t,int*n){if(t!=NULL){*n++;count_preorder(t->lchild);count_preorder(t->lchild);}}13、实现图的深度优先遍历算法typedefstruct{intvexnum,arcnum;charvexs[N];intarcs[N][N];}graph;voidfuntion(inti,graph*g){intj;printf("node:%c\n",g->vexs[i]);visited[i]=TRUE;for(j=0;jvexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j]))function(j,g);}14、对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：（1）平均时间复杂度低于O（n2）的排序方法；希尔、快速、堆、归并（2）所需辅助空间最多的排序方法；归并AFHGDECB15、编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。答案：voidlinklist_c(Lnode*head){Lnode*p;p=head;if(!p)returnERROR;while(p->next!=NULL)p=p->next;p->next=head;}设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）
