DS习题讲解VIP免费

下载本文档

阅读 93
下载 30
格式 doc
大小 544.5 KB
约9页
2024-11-11 发布于河南
收藏
评论
点赞(0)
海报
举报

下载本文档

1、利用原来的存储空间实现单链表的就地逆置。voidresverse(LinkList&L){p=L->next;//L为单链表的头结点L->next=null;while(p){q=p;p=p->next;q->next=L->next;L->next=q;}}2、编写计算数组元素累加和的递归函数templateTRsum(Ta[],intn){//计算a[0:n-1]的和if(n>0)returnRsum(a,n-1)+a[n-1];return0;}3、编程实现在带头结点的head单链表的结点a之后插入新元素x。classnode{public:elemtypedata;node*next;};voidlkinsert(node*head,elemtypex){node*s,*p;s=newnode;s->data=x;p=head->next;while(p!=NULL)&&(p->data!=a)p=p->next;if(p==NULL)cout<<”不存在结点a!”;else{s->next=p->next;p->next=s;1}}4、在栈顶指针为HS的链栈中编写计算该链栈中结点个数的函数。intcount(node*HS){node*p;intn=0;p=HS;while(p!=NULL){n++;p=p->next;}return(n);}5、给定二叉树的两种遍历序列，分别是：前序遍历序列：ABECDFGHIJ；中序遍历序列：EBCDAFHIGJ，试画出二叉树。当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：6、编写递归算法，计算二叉树中叶子结点的数目。intNumOfLeaves(Node*t)const{if(t==NULL)return0;elseif(t->left==Null&&t->right==Null)return1；elsereturnNumOfLeaves(t->left)+NumOfLeaves(t->right);}7、写出求二叉树深度的算法。intDepth(Node*t)const{if(t==NULL)return0;else{intlt=Depth(t->left),rt=Depth(t->right);return1+((lt>rt)?lt:rt);}}2EBCDFHIGJAABEFCDHIGJABEFCDGJHIABEFCDGJHI8、编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。intGet_Sub_Depth(BinaryTreeT,intx)//求二叉树中以值为x的结点为根的子树深度{if(T->data==x){cout<lchild)Get_Sub_Depth(T->lchild,x);if(T->rchild)Get_Sub_Depth(T->rchild,x);//在左右子树中继续寻找}}//Get_Sub_DepthintGet_Depth(BinaryTreeT)//求子树深度的递归算法{if(!T)return0;else{m=Get_Depth(T->lchild);n=Get_Depth(T->rchild);return(m>n?m:n)+1;}}//Get_Depth9、画出一次一个地将10、12、1、14、6、5、8、15、3、9、7、4、11、13和2插入一个初始为空的最小堆的结果。10、改写Binaryheap的insert函数，在0号数组元素中存放插入项的副本。voidinsert(constComparable&x){if(currentSize==array.size()-1)3array.resize(array.size()*2);//Percolateupinthole=++currentSize;for(;hole>1&&x=left;j--)R[j+1]=R[j];//元素后移R[left]=temp;}}12、对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各趟的结果。1．①直接插入排序序号123456789101112关键字834063138435965739796115i=24083[63138435965739796115]i=3406383[138435965739796115]i=413406383[8435965739796115]i=51340638384[35965739796115]i=6133540638384[965739796115]i=713354063838496[5739796115]i=81335405763838496[39796115]i=9133539405763838496[796115]4i=1013353940576379838496[6115]i=111335394057616379838496[15]i=12131535394057616379838496②直接选择排序序号123456789101112关键字834063138435965739796115i=113[4063838435965739796115]i=21315[63838435965739796140]i=3131535[838463965739796140]i=413153539[8463965783796140]i=51315353940[63965783796184]i=6131535394057[966383796184]i=713153539405761[6383799684]i=81315353940576163[83799684]i=9131535394057616379[839684]i=10131535394057...

1、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
3、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。

碎片内容