1、函数实现单链表的插入算法。
int ListInsert(LinkList L,int i,ElemType e){ LNode *p,*s;int j; p=L;j=0;
while((p!=NULL)&&(j
if(p==NULL||j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode)); s->data=e; s->next=p->next )p->next=s
return OK; }/*ListInsert*/
2、函数ListDelete_sq实现顺序表删除算法。 int ListDelete_sq(Sqlist *L,int i){ int k;
if(i<1||i>L->length) return ERROR;
for(k=i-1;k
L->slist[k]=L->slist[k+1]
--L->Length return OK; }
3、函数实现单链表的删除算法。
int ListDelete(LinkList L,int i,ElemType *s){ LNode *p,*q; int j; p=L;j=0;
while((p->next!=NULL)&&(j
if(p->next==NULL||j>i-1) return ERROR; q=p->next; p->next=q->next; *s=q->data; free(q); return OK; }/*listDelete*/
4、栈的基本操作函数：
int InitStack(SqStack *S); //构造空栈 int StackEmpty(SqStack *S);//判断栈空 int Push(SqStack *S,ElemType e);//入栈
int Pop(SqStack *S,ElemType *e);//出栈
函数conversion实现十进制数转换为八进制数，请将函数补充完整。
void conversion(){ InitStack(S); scanf(“%d”,&N); while(N){
Push(S,N%8); N=N/8;
}
while(!StackEmpty(S)){ Pop(S,&e);
printf(“%d”,e); }
}//conversion
5、函数实现串的模式匹配算法。
int index_bf(sqstring*s,sqstring *t,int start){ int i=start-1,j=0;
while(i
if(s->data[i]==t->data[j]){ i++;j++;
}else{
i=i-j+1;j=0; }
if(j>=t->len)
return i-t->len+1 ; else
return -1; }}/*listDelete*/
6、二叉树后序遍历递归算法
void function(Bitree *t){ if(p!=NULL){
function(p->lchild); function(p->rchild); printf(“%d”,p->data);
} }
7、编写求一棵二叉树中结点总数的算法。 答案： （以先序遍历的方法为例）
void count_preorder(Bitree *t, int *n) {
if(t!=NULL)
{*n++;
count_preorder(t->lchild);
count_preorder(t->lchild); }
}
8、函数InOrderTraverse(Bitree bt)实现二叉树的中序遍历。 void InOrderTraverse(BiTree bt){ if(bt!=NULL){
InOrderTraverse(bt->lchild); printf(“%c”,bt->data);
InOrderTraverse(bt->rchild); }
9、函数depth实现返回二叉树的高度。 int depth(Bitree *t){ if(t==NULL) return 0; else{
hl=depth(t->lchild);
hr= depth(t->rchild) ; if( hl>hr ) return hl+1; else
return hr+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，画出二叉树。
答案：二叉树形态
ABCEDFGH 12、编写求一棵二叉树中结点总数的算法。 答案： （以先序遍历的方法为例）
void count_preorder(Bitree *t, int *n) {
if(t!=NULL)
{*n++;
count_preorder(t->lchild); count_preorder(t->lchild); }
}
13、实现图的深度优先遍历算法 typedef struct{ int vexnum,arcnum; char vexs[N]; int arcs[N][N];
}graph;
void funtion(int i,graph *g){ int j;
printf(\ visited[i]=TRUE;
for(j=0;j
if((g->arcs[i][j]==1)&&(!visited[j])) function(j,g); }
14、对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：
（1）平均时间复杂度低于O（n2）的排序方法；希尔、快速、堆、归并 （2）所需辅助空间最多的排序方法；归并
15、编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。 答案：
void linklist_c(Lnode *head) {Lnode *p; p=head; if(!p) return ERROR;
while(p->next!=NULL)
p=p->next; p->next=head; }
设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）