算法设计练习题

算法设计练习题1、设一棵二叉树以二叉链表为存放结构，结点结构为lchild|data|rchild。设计一个算法，求在前根序列中处于第k个位置结点。2、设某单链表Ｌ结点结构为data|next,编写算法判断该链表元素是否是递增。3、设有一单链表L，结点结构为data|next，结点个数最少3个，试画出链表L结构图，并编写算法判断该单链表L中元素是否成等差关系，即：设各元素值次为a1,a2,a3,…,an，判断ai+1-ai=ai-ai-1是否成立，其中i满足2<=i<=n-1.4、设有一棵二叉树以二叉链表作为存放结构，结点结构为lchild|data|rchild,其中data域中存放一个字符，设计一个算法按前根遍历次序仅打印出data域为数字字符（即‘0’<=data<=‘95、写出一个在带头结点单链表上删除表中第i个结点算法。单链表结点类型及单链表类型定义：typedefstructnode{DataTypedata；structnode*next；}Node,*LinkList;6、给出求二叉树结点数算法。二叉树二叉链表存放表示：typedefstructBiTNode{DataTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;7.写出一个删除单链表表头结点和表尾结点算法。单链表结点类型及单链表类型定义：typedefstructnode{DataTypedata；structnode*next；}Node,*LinkList;8、已知一带头结点单链表，由头指针H指向，其结点类型以下：typedefstructnode{elemtypedata;structnode*next;}NODE,*NODEPTR;现要在链表中删除其关键字为aidkey结点，其程序以下：intdeletelm(NODEPTRH,keytypeaidkey)/*若删除成功，则返回1，不然返回0*/{NODEPTRpre,p;pre=H;p=H->next;while(p&&p->data.key!=aidkey){pre=p;①;}if(p){②;free(p);return1;}elsereturn0;}9、已知待排序线性表结构定义以下：#defineMAXSIZE200typedefintkeytype;typedefstruct{keytypekey;othertypeother;}redtype;typedefstruct{redtyper[MAXSIZE];intlength;}sqlist;其中L->r[0]用于作暂时单元，数据从L->r[1]开始存放。采取直接选择排序算法以下：voidinsertsort(sqlist*L){inti,j,k;for(i=1;i<L->length;i++){k=i;for(j=i+1;j<L->length;j++)if(L->r[j].key<L->r[k].key)③;if(i!=k){L->r[0]=L->r[i];④;L->r[k]=L->r[0];}}}10、编写一个函数：将两个递增有序单链表A和B归并生成一个递减有序单链表C，要求利用原表(即A表和B表)结点空间存放表C。假设线性表单链表存放结构以下：typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;11、试编写一个函数交换二叉树中全部结点左、右子树。假设二叉树采取二叉链表存放表示。二叉树二叉链表存放表示以下：typdedefstructBTNode{intdata;structBTNode*lchild,*rchild;}BTNode,*BTree;12、已知单链表L中结点是按值非递减有序排列，试编写一个函数将值为x结点插入表L中，使得L依然有序。线性表单链表存放结构以下：typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;13、以二叉链表作为存放结构，试编写一个函数求二叉树中叶子数。二叉树二叉链表存放表示以下：typdedefstructBTNode{intdata;structBTNode*lchild,*rchild;}BTNode,*BTree;14、假设在长度大于1循环单链表中，既无头结点也无头指针。s为指向链表中某个结点指针，试编写一个函数删除结点*s前趋结点。线性表单链表存放结构以下：typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;15、试编写一个函数求一棵二叉树中结点数。假设二叉树采取二叉链表存放表示。二叉树二叉链表存放表示以下：typdedefstructBTNode{intdata;structBTNode*lchild,*rchild;}BTNode,*BTree;16、回文是指正读和反读均相同字符序列，如“abba”和“abdba”等均是回文。试编写一个函数判定给定字符串是否为回文。17、试编写一个函数，将一个有n个非零元素整型一维数组A[n]拆分为两个一维数组，使得A[]中大于零元素存放在B[]中，小于零元素存放在C[]中。18、有一个单链表，其头指针为head，编写一个函数计算数据域为x结点个数。线性表单链表存放结构以下：typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;19、已知在一维数组A[s+t]中依次存放着两个次序表（a0,a1,...as-1,）和（b0,b1,...bt-1,），试编写一个函数，将数组中两个次序表位置交换，即将（b0,b1,...bt-1,）放在（a0,a1,...as-1,）前面。20、编写一个函数求二叉树高度，假设二叉树采取二叉链表存放表示。二叉树二叉链表存放表示以下：typdedefstructBTNode{intdata;structBTNode*lchild,*rchild;}BTNode,*BTree;

参考答案Bitreptrsearch(bitreptrt,intk){if(t!=null){count++;if(count==k)return(t);else{search(t->lchild,k);search(t->rchild,k);}}}3.Intisviser(lklistL){p=L;while(p->next!=null)if(p->data<p->next->data)p=p->next;elsereturn(0);return(1);}单链表结构图以下列图所表示。．．．．．．a1a2an算法：intisrise(lklistL){p=L->next;b=p->data–L->data;while(p->next!=NULL){q=p->next;if(q->data–p->data!=b)return(0)elsep=q;}return(1);}4．VoidNchar(bitreptrt){if(t!=Null){if(t->data>=’0’)&&(t->data<=‘9’)printf(“%dNchar(t->lchild);Nchar(t->rchild);}}5.voidDel_LinkList(LinkListL,inti){Node*p,*s;intj;p=L;j=0;while(p->next!=NULL&&j<i-1)/*查找第i-1个结点，用p指向*/{p=p->next;j++;}if(p==NULL){printf(“第i-1个结点不存在\n”);return;}if(p->next==NULL){printf(“第i个结点不存在\n”);return;}s=p->next;p->next=s->next;free(s);}6.intnodes(BiTreet){intnl,nr;if(t==NULL)return0;if(t->lchild==NULL&&t->rchild==NULL)return1;nl=nodes(t->lchild);nr=nodes(t->rchild);return(nl+nr+1);}7.intdelht（Node*head）｛Node*q；if（*head＝＝NULL）return0｛q=head->next;free(*head);*head=q;｝if（q！＝NULL）{if（q->next==NULL）{free(q);*head=NULL}}else{while(q->next->next!=NULL)q=q->next;free(q->next);q->next=NULL;}}return0；｝8.①p=p->next;②pre->next=p->next;9.③k=j;④L->r[i]=L->r[k];10、解：分析：设A,B,C均为不带头结点单链表（1）当有序表A，B均非空时，找出两表中元素最小一个元素，然后将此结点插入到C表中，重复上述步骤。（2）当A，B两表有一个为空表时，将另一表中元素次序地插入到C表中。（3）因为C按递减排序，所以在C表中插入元素时，应一直插入到C表表头。LinkListWlink_llist(LinkListA,LinkListB){while((A!=NULL)&&(B!=NULL))if(A->data<b->data){p=A;A=A->next;}elsep->next=C;C=p;}if(A==NULL)A=B;while(A!=NULL){p=A;A=A->next;p->next=C;C=p;}return(C);}11、解：采取后根遍历递归访问方法，交换每一个结点左右子树。Voidexchg_tree(BTreeBT){if(BT!=null)/*非空*/{exchg_tree(BT->lchild);/*交换左子树全部结点指针*/exchg_tree(BT->rchild);/*交换右子树全部结点指针*/p=BT->lchild;/*交换根结点左右指针*/BT->lchild=BT->rchild;->rchild=p;}}12、解：分析：首先从表头开始查找待插入位置直接前趋，找到后，插入待插结点。/*设L表带头结点*/voidCR_lklist(LinkListL,intx){LNode*p,q,s;q=L;p=q->next;s=(LNode*)malloc(sizeof(LNode));s->data=x;/*生成待插结点，用s指向*/while((p!=NULL)&&(p->data<s->data)){q=p;p=p->next;}/*查找插入位置直接前驱，用q指向*/s->next=p;q->next=s;/*插入*/}13、解：本算法基本思想是：先求左子树叶子数，再求右子树叶子数，二者相加就是对应二叉树叶子数。intleafcount(BTreeT)/*求二叉树T叶子数*/{intleaf;if(T==NULL)leaf=0;/*当二叉树为空时，叶子数等于0*/elseif(T->lchild==NULL)&&(T->rchild==NULL)leaf=1;/*当二叉树仅含一个根结点时，叶子数为1*/else{L=leafcount(T->lchild);/*求左子树叶子数*/R=leafcount(T->lchild);/*求右子树叶子数*/leaf=L+R;/*左、右子树叶子数之和等于二叉树叶子数*/}return(leaf);}14.解：分析：设置两个指针，分别指向*S及其后继，然后按循环链表特征，次序往下查找*s直接前趋，找到后删除。voidDELETE_Xlklist(LinkLists){LNode*p,*q;p=s;q=p->next;while(q->nest!=s){p=q;q=q->next;}p->next=s;free(q);}15、解：intBTreeCount(BTreebt){if(bt==NULL)return0; elsereturnBTreeCount(bt->lchild)+BTreeCount(bt->rchild)+1; }16、解：#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];inttop;}SqStack;/*栈次序存放表示*/intexample(chara[]){SqStacks;intn,i;InitStack(&s);n=strlen(a);for(i=0;i<n/2;i++)Push(&s,a[i]);i=n/2;while(i<n&&a[i]==a[n-i-1])i++;if(i>=n)return1;elsereturn0;}17、解：voidfenjie(intA[],intB[],intC[],intn){inti,j,k;i=j=-1;for(k=0;k<n;