整理算法设计练习题

1、精品文档算法设计练习题1、设一棵二叉树以二叉链表为存储结构,结点结构为Ichild |data |rchild.设计一个算法,求在前根序列中处于第k个位置的结点.2、 设某单链表L的结点结构为data |next,编写算法判断该链表的元素是 否是递增的.3、设有一单链表L,结点结构为|data|next,结点个数至少3个,试画出链表L的结构图,并编写算法判断该单链表L中的元素是否成等差关系,即：设各元素值次为ai,a?,a3,an,判断a+i-a=ai-a-i是否成立,其中i满足2<=i<=n-1.4、 设有一棵二叉树以二叉链表作为存储结构,结点结构为 |lchild|data|r

2、child, 其中data域中存放一个字符,设计一个算法按前根遍历顺序仅打印出data域为 数字的字符即0' <=data<= '9'5、 写出一个在带头结点的单链表上删除表中第i个结点的算法.单链表的结点类型及单链表类型定义：typedef struct node DataType data；struct node *n ext;Node, *Lin kList;6给出求二叉树的结点数的算法.二叉树的二叉链表存储表示：typedef struct BiTNode DataType data;struct BiTNode *lchild,*rchild;Bi

3、TNode, *BiTree;7. 写出一个删除单链表的表头结点和表尾结点的算法.单链表的结点类型及单链表类型定义：typedef struct node DataType data；struct node *n ext;Node, *Lin kList;8、 一带头结点的单链表,由头指针H指向,其结点的类型如下：typedef struct node elemtype data;struct node *n ext;NODE,*NODEPTR;现要在链表中删除其关键字为aidkey的结点,其程序如下:int deletelm(NODEPTR H,keytype aidkey)/*假设删除成功

4、,那么返回1,否那么返回0*/ NODEPTR pre,p;pre=H;p=H->n ext;while(p&&p->data.key!=aidkey) pre=p; ；if(p) ;free(p);return 1;else return 0;9、待排序的线性表的结构定义如下：#defi ne MAXSIZE 200typedef int keytype;typedef struct keytype key;othertype other;redtype;typedef struct redtype rMAXSIZE;int len gth;sqlist;其中L-

5、>r0用于作临时单元,数据从L->r1开始存放.采用直接选择排序的算法如下：void in sertsort(sqlist *L) int i,j,k;for(i=1;i<L->le ngth;i+) k=i;for(j=i+1;j<L->le ngth;j+)if(L->rj.keyvL->rk.key) ；if(i!=k) L->rO=L->ri; ；L->rk=L->rO;10、编写一个函数：将两个递增有序的单链表 A和B归并生成一个递减有序 的单链表C,要求利用原表(即A表和B表)的结点空间存放表Co假设线性表的单

6、链表存储结构如下：typedef struct LNodeint data;struct LNode *n ext;LNode, *Li nkList;11、 试编写一个函数交换二叉树中所有结点的左、右子树.假设二叉树采用 二叉链表存储表示.二叉树的二叉链表存储表示如下：typdedef struct BTNodeint data;struct BTNode *lchild, *rchild;BTNode, *BTree;12、单链表L中的结点是按值非递减有序排列的,试编写一个函数将 值为x的结点插入表L中,使得L仍然有序.线性表的单链表存储结构如下：typedef struct LNodei

7、nt data;struct LNode *n ext;LNode, *Li nkList;13、以二叉链表作为存储结构,试编写一个函数求二叉树中叶子数.二叉树的二叉链表存储表示如下：typdedef struct BTNodeint data;struct BTNode *lchild, *rchild;BTNode, *BTree;14、假设在长度大于 1 的循环单链表中,既无头结点也无头指针. s 为指向 链表中某个结点的指针,试编写一个函数删除结点 *s 的前趋结点. 线性表的单链表存储结构如下： typedef struct LNodeint data;struct LNode *n

8、ext;LNode, *LinkList;15、试编写一个函数 求一棵二叉树中的结点数. 假设二叉树采用二叉链表存 储表示.二叉树的二叉链表存储表示如下：typdedef struct BTNodeint data;struct BTNode *lchild, *rchild;BTNode, *BTree;16、 回文是指正读和反读均相同的字符序列,如“abba和“ abdbh'等均 是回文.试编写一个函数判定给定字符串是否为回文.17、 将一个顺序表L中的元素逆置.如：L=a1,a2,an,那么逆置后L=an,a2,a1.顺序表类型定义如下：typedef struct DataTy

9、pe dataMAXSIZE ；int last； SeqList;18、编写一个函数求二叉树的高度,假设二叉树采用二叉链表存储表示. 二叉树的二叉链表存储表示如下： typdedef struct BTNodeint data;struct BTNode *lchild, *rchild;BTNode, *BTree;19、 在一维数组As+t中依次存放着两个顺序表(ao, ai, . as-1)和(bo,b1, . bt-1, ) ,试编写一个函数, 将数组中两个顺序表的位置互换, 即将( b0, b1, . bt-i,)放在(ao, ai, . as-i,)的前面.20、 有一个单链表,

10、其头指针为head,编写一个函数计算数据域为x的结点的个数.线性表的单链表存储结构如下：typedef struct LNodeint data;struct LNode *next;LNode, *LinkList;21、 试编写一个函数,将一个有n个非零元素的整型一维数组 An拆分为 两个一维数组,使得 A 中大于零的元素存放在 B 中,小于零的元素存放在 C 中.精品文档参考答案1. Bitreptr search(bitreptr t ,int k)if (t!=null)co un t+;if (cou nt= =k)return (t);else search(t->lchi

11、ld,k); search(t->rchild,k);3. Int isviser(lklist L)P=L;while(p->n ext!=null)if (p->data <p->n ext->data) p=p->n ext; else return(O);return(1);单链表的结构图如下列图所示a1a2an算法：int isrise (lklist L) p = L -> next; b = p -> data -L -> data; while (p -> next != NULL) q =p -> n e

12、xt;if (q -> data -p -> data !=b) return(0) else p = q;return(1);4. Void Nchar (bitreptr t) if (t != Null) if (t -> data >= '' && (t -> data <= 9')printf ( %d,t -> data );Nchar (t -> lchild);Nchar (t -> rchild);5.void Del_LinkList(LinkList L,int i)Node *

13、p,*s; int j;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(第“个结点不存在n);return;s=p->next; p->next=s->next;free(s);6.int nodes(BiTree t) int nl,nr; if(t=NULL) return 0;if(t->lchi

14、ld=NULL&&t->rchild=NULL) return 1; nl=nodes(t->lchild);nr=nodes(t->rchild); return(nl+nr+1);7.int delht(Node *head ) Node *q;if (*head= = NULL ) return 0 q=head->next ; free(*head) ;*head=q;if (q != NULL )if ( q->next= NULL )free(q); *head= NULL else while (q->next->next

15、!= NULL) q=q->next;free(q->next);q-> next= NULL; return 0；8.p=p->next;pre->next=p->next;9. k=j; L->ri=L->rk;10、解：分析：设 A,B,C 均为不带头结点的单链表( 1)当有序表 A,B 均非空时,找出两表中元素最小的一个元素,然后将此 结点插入到 C 表中,重复上述步骤.( 2 )当 A, B 两表有一个为空表时,将另一表中元素顺序地插入到 C 表中.(3)由于C按递减排序,因此在C表中插入元素时,应始终插入到 C表表 头.LinkLis

16、t Wlink_llist(LinkList A, LinkList B) 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、解： 采用后根遍历递归访问的方法,交换每一个结点的左右子树 Void exchg_tree(BTree BT)if (BT!=null)/* 非空*/exchg_t

17、ree(BT->lchild); /* 交换左子树所有结点指针 */ exchg_tree(BT->rchild); /* 交换右子树所有结点指针 */ p=BT->lchild; /* 交换根结点左右指针 */ BT->lchild=BT->rchild; ->rchild =p;12、解： 分析：首先从表头开始查找待插入位置的直接前趋,找到后,插入待插结点./*设L表带头结点*/void CR_lklist(LinkList L, int x)LNode *p,q,s;q=L;p=q->next;s=(LNode *)malloc(sizeof(L

18、Node); s->data=x; /*生成待插结点,用 s指向 */ while(p!=NULL)&&(p->data<s->data)q=p;p=p->next;/*查找插入位置的直接前驱,用q指向*/s->next=p; q->next=s; /*插入*/13、解：本算法的根本思想是： 先求左子树的叶子数, 再求右子树的叶子数, 两者相加就 是对应二叉树的叶子数.int leafcount (BTree T) /* 求二叉树 T 的叶子数 */ int leaf;if(T=NULL)leaf=0;/* 当二叉树为空时,叶子数等于

19、0*/else if(T->lchild=NULL)&&(T->rchild=NULL)leaf=1;/*当二叉树仅含一个根结点时,叶子数为1*/elseL=leafcount(T->lchild); /* 求左子树的叶子数 */R=leafcount(T->lchild); /* 求右子树的叶子数 */leaf=L+R; /* 左、右子树叶子数之和等于二叉树的叶子数 */return(leaf);14.解：分析：设置两个指针,分别指向 *S 及其后继,然后按循环链表特性,顺序 往下查找 *s 的直接前趋,找到后删除.void DELETE_Xlklis

20、t(LinkList s)LNode *p,*q;p=s; q=p->next;while (q->nest!=s) p=q; q=q->next;p->next=s; free(q);15、解：int BTreeCount ( BTree bt) if ( bt = NULL ) return 0;else return BTreeCount ( b-t> lchild ) + BTreeCount ( bt -> rchild ) + 1; 16、解：#define MAXSIZE 100typedef structint dataMAXSIZE;int

21、 top;SqStack; /* 栈的顺序存储表示 */int example(char a)SqStack s; int n,i;InitStack(&s); n=strlen(a);for(i=0;i<n/2;i+) Push(&s,ai);i=n/2;while(i<n&&ai=an-i-1) i+;if(i>=n)return 1;else return 0; 17、解：void insersion(SeqList *L) int i,j,t;for(i=0, j=L->last; i<j; i+, j-)t=L->datai; L->datai