资源描述：
《《算法设计练习题》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、算法设计练习题1、设一棵二叉树以二叉链表为存储结构，结点结构为 lchild
2、data
3、rchild。设计一个算法，求在前根序列中处于第k个位置的结点。2、设某单链表Ｌ的结点结构为data
4、next,编写算法判断该链表的元素是否是递增的。3、设有一单链表L，结点结构为data
5、next，结点个数至少3个，试画出链表L的结构图，并编写算法判断该单链表L中的元素是否成等差关系，即：设各元素值次为a1,a2,a3,…,an，判断ai+1-ai=ai-ai-1是否成立，其中i满足2<=i<=n-1.4、设有一棵二叉树以二叉链表作为存储结构，结
6、点结构为lchild
7、data
8、rchild,其中data域中存放一个字符，设计一个算法按前根遍历顺序仅打印出data域为数字的字符（即‘0’<=data<=‘9’）5、写出一个在带头结点的单链表上删除表中第i个结点的算法。单链表的结点类型及单链表类型定义：typedefstructnode{DataTypedata；structnode*next；}Node,*LinkList;6、给出求二叉树的结点数的算法。二叉树的二叉链表存储表示：typedefstructBiTNode{DataTypedata;structBiTNode*l
9、child,*rchild;}BiTNode,*BiTree;7.写出一个删除单链表的表头结点和表尾结点的算法。单链表的结点类型及单链表类型定义：typedefstructnode{DataTypedata；structnode*next；}Node,*LinkList;8、已知一带头结点的单链表，由头指针H指向，其结点的类型如下：typedefstructnode{elemtypedata;structnode*next;}NODE,*NODEPTR;12现要在链表中删除其关键字为aidkey的结点，其程序如下：intdeletel
10、m(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{r
11、edtyper[MAXSIZE];intlength;}sqlist;其中L->r[0]用于作临时单元，数据从L->r[1]开始存放。采用直接选择排序的算法如下：voidinsertsort(sqlist*L){inti,j,k;for(i=1;ilength;i++){k=i;12for(j=i+1;jlength;j++)if(L->r[j].keyr[k].key)③;if(i!=k){L->r[0]=L->r[i];④;L->r[k]=L->r[0];}}}10、编写一个函数：将两个递增有序的单链表A和
12、B归并生成一个递减有序的单链表C，要求利用原表(即A表和B表)的结点空间存放表C。假设线性表的单链表存储结构如下：typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;11、试编写一个函数交换二叉树中所有结点的左、右子树。假设二叉树采用二叉链表存储表示。二叉树的二叉链表存储表示如下：typdedefstructBTNode{intdata;structBTNode*lchild,*rchild;}BTNode,*BTree;12、已知单链表L中的结点是按值非递减有序排
13、列的，试编写一个函数将值为x的结点插入表L中，使得L仍然有序。线性表的单链表存储结构如下：typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;13、以二叉链表作为存储结构，试编写一个函数求二叉树中叶子数。12二叉树的二叉链表存储表示如下：typdedefstructBTNode{intdata;structBTNode*lchild,*rchild;}BTNode,*BTree;14、假设在长度大于1的循环单链表中，既无头结点也无头指针。s为指向链表中某个结点的指针
14、，试编写一个函数删除结点*s的前趋结点。线性表的单链表存储结构如下：typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;15、试编写一个函数求一棵二叉
