《算法分析与设计课件习题选讲第七章前5题》由会员分享，可在线阅读，更多相关《算法分析与设计课件习题选讲第七章前5题（18页珍藏版）》请在装配图网上搜索。
1、2011-10-201第七章1426 电话号码前缀检索1310 二叉查找树，前序中序后序遍历1210 二叉树，知道前序、后序求可能的方法数1090 最小生成树1156 二叉树的前序遍历2011-10-2021426 电话号码前缀检索题目大意：给出N个电话号码（N=10000）,每个电话号码的长度不大于10，当存在一个电话号码是另外一个电话号码的前缀时，则会发生冲突。如果不存在冲突输出YES，否则输出NO2011-10-2031426 电话号码前缀检索解题思路：1.把n个电话号码放进一个set内2.枚举每个电话号码的前缀，查询是否存在于set里2011-10-2041426 电话号码前缀检索in
2、t n;string c11000;set ss;bool isConsistent()ss.clear();for(int i=0;i n;i+)ss.insert(ci);for(int i=0;i n;i+)string st=;for(int j=0;j ci.size()-1;j+)st+=cij;if(ss.count(st)return false;return true;2011-10-2051310 二叉查找树题目大意：给出N个数，按照顺序建立一棵二叉查找树，然后输出该树的前序遍历，中序遍历，后序遍历。2011-10-2061310 二叉查找树struct Node int
3、val;int left,right;Node(int val=0):val(val),left(0),right(0);p300000;2011-10-2071310 二叉查找树void Add(int root,int val)while(true)if(proot.val val)if(proot.right)root=proot.right;else proot.right=+tot；ptot=Node(val);return;else if(proot.left)root=proot.left;else proot.left=+tot;ptot=Node(val);return;20
4、11-10-2081310 二叉查找树inline void Preorder(int root)if(!root)return;printf(%d,proot.val);Preorder(proot.left);Preorder(proot.right);inline void Inorder(int root)if(!root)return;Inorder(proot.left);printf(%d,proot.val);Inorder(proot.right);ninline void Postorder(int root)nnif(!root)return;nPostorder(pro
5、ot.left);nPostorder(proot.right);nprintf(%d,proot.val);n2011-10-2091210 二叉树题目大意：给出一棵二叉树前序遍历和后序遍历的顺序，要求出总共有多少棵不同形态的二叉树满足这样的遍历顺序。2011-10-20101210 二叉树解题思路：1.前序遍历第一个元素是根，后序遍历最后一个元素是根 2.前序遍历第二个元素是某子树的根，但左右不确定 3.在后序遍历中找到前序遍历的第二个元素，那么以这个元素为基准，可以划分新的左右子树 4.当前序遍历的第二个元素出现在后序遍历的倒数第二位，以后序遍历倒数第三位起向左数都是子树的元素，但是左右
6、不确定，因此有2种情况 2011-10-20111210 二叉树long long calc(string pre,string post)long long ans=1;int len=pre.size();for(int i=0;i len-1;i+)int current=len-1;while(prei!=postcurrent)current-;if(current&prei+1=postcurrent-1)ans*=2;return ans;2011-10-20121090 最小生成树题目大意：给出N=500个节点的无向图，每两个点之间都有一条无向边。问该无向图的最小生成树中，最长
7、的一条边的长度。2011-10-20131090 最小生成树解题思路：求最小生成树的算法中，有Prim算法和kruskal算法。Prim算法复杂度N2（N为点数）,Kruskal算法MlogM（M为边数）因此，对于稠密图而言，Prim算法的复杂度更高效率。2011-10-20141090 最小生成树int solve()for(int i=0;i n;i+)ui=false,disti=e0i;int ans=0,p;for(int i=0;i n;i+)p=-1;for(int j=0;j distj)p=j;up=true;ans=max(ans,distp);for(int j=0;j
8、n;j+)if(uj|distj=epj)continue;distj=epj;return ans;2011-10-20151156 二叉树的前序遍历题目大意：给定一棵N个节点的二叉树，输出其前序遍历的顺序解题思路：1.按照题目要求把二叉树读入2.以前序遍历顺序输出（可参考1310）2011-10-20161156 二叉树的前序遍历void Read_Tree()memset(is_root,0,sizeof(is_root);char c;int l,r,m;for(int i=0;i m c l r;is_rootm=!is_rootm;is_rootl=!is_rootl;is_rootr=!is_rootr;pm.Left=l;pm.Right=r;pm.ch=c;for(int i=1;i=1000;i+)if(is_rooti)root=i;2011-10-20171156 二叉树的前序遍历void Preorder(int root)if(!root)return;cout proot.ch;Preorder(proot.Left);Preorder(proot.Right);2011-10-2018谢谢！
算法分析与设计课件习题选讲第七章前5题
