数据结构算法设计期末复习题

二、算法设计1、设计一个算法，通过一趟遍历在单链表中确定值最大的结点。ElemTypeMax(LinkListL){if(L-next==NULL)returnNULL;pmax=L-next;//假定第一个结点中数据具有最大值p=L-next-next;while(p!=NULL){//如果下一个结点存在if(p-datapmax-data)pmax=p;p=p-next;}returnpmax-data;2、设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。voidinverse(LinkList&L){//逆置带头结点的单链表Lp=L-next;L-next=NULL;while(p){q=p-next;//q指向*p的后继p-next=L-next;L-next=p;//*p插入在头结点之后p=q;}}3、设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。voiddelete(LinkList&L,intmink,intmaxk){p=L-next;//首元结点while(p&&p-data=mink){pre=p;p=p-next;}//查找第一个值mink的结点if(p){while(p&&p-datamaxk)p=p-next;//查找第一个值≥maxk的结点q=pre-next;pre-next=p;//修改指针while(q!=p){s=q-next;deleteq;q=s;}//释放结点空间}//if}4、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;ElemTypeDeleteNode(LinkLists)/*删除指针s所指结点的前驱结点，并返回被删结点的元素值*/{LinkListp;p=s-next;while(p-next-next!=s)p=p-next;ElemTypee=p-next-data;p-next=s;returne;}5、已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。voidDeleteItem(SeqList*L,ElemTypeitem){inti=0,j=L-last;while(ij){while(ij&&L-elem[i]!=item)i++;while(ij&&L-elem[i]==item)j--;if(ij){L-elem[i]=L-elem[j];i++;j--;}}L-last=i-1;}6、写一个算法，求出循环链表结点的个数。（不包括头结点）intcount(Linklisthead){intn=0;ListNode.p=head-next;while(p!=head){n++;P=P-next;}returnn;}7、写一算法在单链表上实现线性表的ListLength(L)运算。intListLength(LinkListL){intlen=0;ListNode*p;p=L;//设该表有头结点while(p-next){p=p-next;len++;}returnlen;}8、试写一算法计算二叉树的深度（高度）。intHeight(btrebt)/求二叉树bt的深度{inthl,hr;if(bt==null)return(0);else{hI=Height(bt-lch);hr=Height(bt-rch);if(hlhr)return(hl+1);elsereturn(hr+1);}}9、试写一算法统计用二叉链表表示的二叉树叶子结点总数。intleaf(BinTreeNodeType*ptr){if(ptr==NULL)return0;elseif(ptr-leftChild==NULL&&ptr-rightChild==NULL)return1;elsereturnleaf(ptr-leftChild)+leaf(ptr-rightChild);}10、已知二叉树的定义如下：typedefstructnode{intdata;structnode*lchild,*rchild;}*bitree；试分别写出二叉树的后根遍历和中根遍历的递归算法。后intvisit(bitreeT){if(T==null)return0;visit(T-lchirld);visit(T-rchirld);printf(“%d”,data);}中intvisit(bitreeT){if(T==null)return0;visit(T-lchirld);printf(“%d”,data);visit(T-rchirld);}11、已知二叉树的定义如下：typedefstructnode{intdata;structnode*lchild,*rchild;}*bitree；编写二叉树先序遍历的递归算法。先intvisit(bitreeT){if(T==null)return0;printf(“%d”,data);visit(T-lchirld);visit(T-rchirld);}12、要求二叉树按二叉链表形式存储，写一个建立二叉树的算法。BiTreeCreat()//建立二叉树的二叉链表形式的存储结构{ElemTypex;BiTreebt;scanf(“%d”,&x);//本题假定结点数据域为整型if(x==0)bt=null;elseif(x0){bt=(BiNode*)malloc(sizeof(BiNode));bt-data=x;bt-lchild=creat();bt-rchild=creat();}elseerror(“输入错误”);return(bt);}//结束BiTree