数据结构试题大题编程及参考答案

依据结构考试题参考答案1、设顺序表L中的数据元素递增有序。试写一算法，将数据元素x插入到顺序表L的适当位置，以保持该表的有序性。解：存储结构为：typedefstmctSeqList{DataType*data;hitMaxLen;hitlen;}SeqList;算法如下：voidinsertLx(SeqList&L,DataTypux){if(L,len=L.niaxlen)retuni;inti=L.len-l;wliile(i>=0&&x<L.data[i]){L.data[i+1]=L.data[i];L.data[i+l]=x;L.len++;}2、试写一个算法，在带头结点的单链表L的元素x前插入一个结点y。解：存储结构如下：typedefstiuctLnode{ElemTypedata;stmctLnode*next;}Lnode,*LuikList;算法如下：voidinsert_y_befbre_x(LinkListL,ElemTypex,ElemTypey){Lnode*q,*p=L;wliile(p->next&&p->next->data!=x)p=p->next;〃找x的前驱结点p;if(!p->next)return;//若不存在结点x,则返回；q=newLnode;q->data=y;q->next=p->next;p->next=q;}3、试写一个算法，统计带头指针的单链表L的元素个数。解：存储结构如下：typedefstiuctLnode{ElemTypedata;stmctLnode*next;}Lnode,*LuikList;算法如下：hitlength(LinkListL){mtlen=0;Lnode*p=L;wliile(p){len++;p=p->next;}returnlen;}注：如果单链表是带头结点的，则算法如下：hitlength(LinkListL){mtlen=O;Lnode*p=L->next;;wliile(p){len++;p=p->next;}returnlen;}4、试写一个算法，在带头结点的单链表L的第k个结点后插入一个结点x。解：存储结构如下：typedefstiuctLnode{ElemTypedata;stmctLnode*next;}Lnode,*LiiikList;算法如下：voidinsert_aftei_k(LiiikListL,mtk,ElemTypex){if(k<0)return;Lnode*p=L;mti=0;wlule(p&&i<k){i++;p=p->next;}〃找到第k个结点p;if(!p)return;〃若不存在第k个结点，则返回；q=newLnode;q->data=x;q->next=p->next;p->next=q;}注：如果是在L的第k个结点前插入一个结点，则找第k-1个结点p,然后插入。5、试写一个算法，在带头结点的单链表L中删除所有的数据元素为x的结点。解：存储结构如下：typedefstiuctLnode{ElemTypedata;structLnode*next;}Lnode,*LiiikList;算法如下：voidDelete_all_x(LinkListL,Elemtypex){Lnode*p,*q;p=L;while(p){if(p->next&&p->next->data==x){q=p->next;p->next=q->next;deleteq;}elsep=p->next;}}注意：要删除所有的值为X的结点。6、假设一个单循环链表L的数据域为整型，设计一个算法，求该表中所有结点的数据之和。解：存储结构如下：typedefstiuctLnode{ElemTypedata;stmctLnode*next;}Lnode,*LiiikList;假设L带头结点，且L指向头结点，则算法如下：hitsum_Of_Data(LuikListL){mts=0;Lnode*p=L->next;wliile(p!=L){s+=p->data;p=p->next;}returns;}假设L不带头结点，且L指向循环链表中任何一个结点，则算法如下：hitsum_ofLdata(LinkListL){iiits=0;Lnode*p=L;if(L){s+=p->data;p=p->next;wliile(p?=L){s-r=p->data;p=p->next;}}returns;}注：以上两种情形，只要给出其中一种情形的解即可。7、假设二叉树用二叉链表存储，设计一个算法，求二叉树的结点个数。解：存储结构如下：typedefstructbitnode{ElemTypedata;stmctbitnode*lchild,*rcluld;Jbitnode,*bitree;算法如下：hitnodes(bitreeT){if(!T)return0;elseretuni(l+nodes(T->lcluld)+nodes(T->rchild));}8、写一个算法，建立二叉树的二叉链表。解：存储结构如下：typedefcharElemType;typedefstructbitiiode{ElemTypedata;stmctbitnode*lchild,*rcluld;Jbitnode,*bitree;算法如下：voidcreacbitiee(bitree&T){〃按扩展的先序序列输入结点，输入表示空。ElemTypech;cin»ch;if(cH铲)T=0;else{T=newbitiiode;T->data=ch;creat_bitiee(T->lchuild);creaCbitiee(T->rcluld);}}或者写成以下算法：bitreecieat_bitree(void){〃按扩展的先序序列输入结点，输入表示空。bitreeT;ElemTypech;cin»ch;if(cH铲)T=0;else{T=newbitiiode;T->data=ch;creat_bitiee(T->lchuild);creat_bitree(T->ichild);}leturnT;}9、假设一棵二叉树的光序序列为EBADCFHGIKJ,中序序列为ABCDEFGHUK,请画出该二叉树，并写出后序序列。解：该二叉树如下：

后序序列为：ACDBGJKIHFEo中序序列为DBGEHJACIF,请画出该二10、假设一棵二叉树的层次序列为ABCDEFGHIJ,叉树，并写出其先序序列和后序序列。中序序列为DBGEHJACIF,请画出该二解：该二叉树如下：先序序列为：ABDEGHJCH：后序序列为：DGJHEBIFCAo11、编写一个递归算法，将用二叉链表表示的二叉树的所有结点的左、右子树交换。解：存储结构如下：typedefcharElemType;typedefstmctbitiiode{ElemTypedata;structbitnode*lchild,*rcluld;Jbitnode,*bitree;算法如下：voidexchange(bitree&T){if(!T)return;bitieetemp;temp=T->lcluld;T->lchild=T->rcliild;T->rchild=temp;exchange(T->lchild);exchange(T->rchild);}12、试写出二叉链表表示的二叉树的先序遍历的非递归算法。解：存储结构如下：typedefcharElemType;typedefstructbitiiode{ElemTypedata;structbitnode*lchild,*rcluld;Jbitnode,*bitree;算法如下：voidpreoidei(bitreeT){〃先序遍历，当前结点入栈。#defineMaxNum20bitreestackfMaxNum];mttop=0;〃指向栈顶的下一