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

数据结构考试题参考答案1、设顺序表L中的数据元素递增有序。试写一算法，将数据元素x插入到顺序表L的适当位置，以保持该表的有序性。解：存储结构为：typedefstructSeqList{DataType*data;intMaxLen;intlen;}SeqList;算法如下：voidinsertLx(SeqList&L,DataTypex){if(L.len==L.maxlen)return;inti=L.len-1;while(i=0&&xL.data[i]){L.data[i+1]=L.data[i];i=i-1;}L.data[i+1]=x;L.len++;}2、试写一个算法，在带头结点的单链表L的元素x前插入一个结点y。解：存储结构如下：typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下：voidinsert_y_before_x(LinkListL,ElemTypex,ElemTypey){Lnode*q,*p=L;while(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的元素个数。解：存储结构如下：typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下：intlength(LinkListL){intlen=0;Lnode*p=L;while(p){len++;p=p-next;}returnlen;}注：如果单链表是带头结点的，则算法如下：intlength(LinkListL){intlen=0;Lnode*p=L-next;;while(p){len++;p=p-next;}returnlen;}4、试写一个算法，在带头结点的单链表L的第k个结点后插入一个结点x。解：存储结构如下：typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下：voidinsert_after_k(LinkListL,intk,ElemTypex){if(k0)return;Lnode*q,*p=L;inti=0;while(p&&ik){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，然后插入。５、试写一个算法，在带头结点的单链表Ｌ中删除所有的数据元素为x的结点。解：存储结构如下：typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;算法如下：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的结点。６、假设一个单循环链表Ｌ的数据域为整型，设计一个算法，求该表中所有结点的数据之和。解：存储结构如下：typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;假设Ｌ带头结点，且Ｌ指向头结点，则算法如下：intsum_Of_Data(LinkListL){ints=0;Lnode*p=L-next;while(p!=L){s+=p-data;p=p-next;}returns;}假设Ｌ不带头结点，且Ｌ指向循环链表中任何一个结点，则算法如下：intsum_of_data(LinkListL){ints=0;Lnode*p=L;if(L){s+=p-data;p=p-next;while(p!=L){s+=p-data;p=p-next;}}returns;}注：以上两种情形，只要给出其中一种情形的解即可。７、假设二叉树用二叉链表存储，设计一个算法，求二叉树的结点个数。解：存储结构如下：typedefstructbitnode{ElemTypedata;structbitnode*lchild,*rchild;}bitnode,*bitree;算法如下：intnodes(bitreeT){if(!T)return0;elsereturn(1+nodes(T-lchild)+nodes(T-rchild));}８、写一个算法，建立二叉树的二叉链表。解：存储结构如下：typedefcharElemType;typedefstructbitnode{ElemTypedata;structbitnode*lchild,*rchild;}bitnode,*bitree;算法如下：voidcreat_bitree(bitree&T){//按扩展的先序序列输入结点，输入‘＃’表示空。ElemTypech;cinch;if(ch==’#’)T=0;else{T=newbitnode;T-data=ch;creat_bitree(T-lchuild);creat_bitree(T-rchild);}}或者写成以下算法：bitreecreat_bitree(void){//按扩展的先序序列输入结点，输入‘＃’表示空。bitreeT;ElemTypech;cinch;if(ch==’#’)T=0;else{T=newbitnode;T-data=ch;creat_bitree(T-lchuild);creat_bitree(T-rchild);}returnT;}9、假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树，并写出后序序列。解：该二叉树如下：后序序列为：ACDBGJKIHFE。10、假设一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树，并写出其先序序列和后序序列。解：该二叉树如下：先序序列为：ABDEGHJCFI；后序序列为：DGJHEBIFCA。11、编写一个递归算法，将用二叉链表表示的二叉树的所有结点的左、右子树交换。解：存储结构如下：typedefcharElemType;typedefstructbitnode{ElemTypedata;structbitnode*lchild,*rchild;}bitnode,*bitree;算法如下：voidexchange(bitree&T){if(!T)return;bitreetemp;temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;exchange(T-lchild);exchange(T-rchild);}12、试写出二叉链表表示的二叉树的先序遍历的非递归算法。解：存储结构如下：typedefcharElemType;typedefstructbitnode{ElemTypedata;structbitnode*lchild,*rchild;}bitnode,*bitree;算法如下：voidpreorder(bitreeT){//先序遍历，当前结点入栈。#defineMaxNum20bitreestack[MaxNum];inttop=0;//指向栈顶的下一位置。bitnode*p;p=T;while(p||top0){while(p){coutp-data;stack[top++]=p;p=p-lchild;}if(top0){p=stack[--top];p=p-rchild;}}coutendl;}注：这里假设访问结点即为输出结点。若访问结点是其它操作，则换成相应的函数便可。