析和算法。它是一个带回溯的探索问题需要用递归算法求解。另外.关节点的判断准则有 两个:其一为根至少两个或两个以上的子女:其二为除根和叶结点外,其他结点的子女或 子孙有指向该结点祖先的“回边”。掌握了这些概念,此问题就迎刃而解了。还需要了解: 重连通图中任意两个顶点之间至少有两条路径相通,这有助丁将非重连通图改为重连通图。 【例4.2】设有13个初始归并段,其长度分别为28,16,37,12,5,9,13,14,20,17,30,12,18 试画出4路归并时的最佳归并树,并计算它的带权路径长度WP 【解答】因为(13-1)%(4-1)=12%3=0,所以不需要添加空段。最住归并树为 WPL=(5+9+13+12+i6+14+17+18+28+37+20+30)*2+42-4 【分析】这是外排序中求最佳归并树问题,它是只有度为0和度为k的正则k又树,满足条 件n=(k-1)n+1,其中,n0是度为0的结点个数,n是度为k的结点个数,k是归并路数 最佳归并树的构造仿照霍夫曼树,长度小的初始归并段离根远,长度大的初始归并段离根 近。需要注意的是:当(m-1)%(k-1)-m≠0时,需要补充k-m-1个空的初始归并段 才能构成正则k叉树 【例4.3】设散列表为HI[0..121,即表的大小为m=13:采用双散列法解决冲突,散列函 数和再散列函数分别为: H(key)-key%13;(注:%是求余数运算 H,亠(H,1÷REV(kcy+1)%11+1)%13 2,3.…,m1 其中,函数REⅤ(r)表小顛倒10进制数x的各位,如REV(37)-73REV(7)=7等。若插 入的关键码序列为2,8.31,20,19、18.53,27。试画出插入这8个关键码后的散列表 【解答】散列表HT[0..12],散列函数与再散列函数为 H (key)=key 913 1=(H,+REV(key+1)‰11+1)%13; 插入关键码序列为;2,8,31,20,19,18,53,27 H(2)=2,比较次数为1 H(8)=8,比较次数为 H,(31)=5,比较次数为 H,(20)-7,比较次数为1 H(19)=6,比较次数为 J(18)=5,泻突,H1=9比较次数为2 H(53)=1,比较次数为1 Il(27)=1,冲突,H1-7,冲突,H2=0,比较次数为3 插人8个关键码后的散列表 5678 127153211311201118
【分析】散列表长度和再散列函数的选取是关键。由于要求再散列函数计算出来的结果,即 发生冲突时向后跨多大距离找下一个”空位”,必须与表的长度质、因此为简化问题求解 的难度,一般设表的长度为质数,题设为13.其次,再散列函数是待散列对象的关键码的 函数,计算结果的取值范围在1~n-1之间,其中n是表的长度。因此选取REV(key+ 1)%11+1,其取值范围在1~11之间除1退化为线性探查外,其他都与13质。需罢注 意的是:双散列法对表长度的要求天如二次探查法严格,那里要求表的长度一定是满足 4+3的质数且表的装载因子不超过0.5。此题容易出错的地方是应用再散列函数处理冲 突时发生简单计算错误,一处出错,会影响后面一连串出错,一定要仔细。 0.2.5综合算法题 【例5.1】有一种简单的排序算法,叫做计数排序( count sorting),这种排序算法对个待 排序的表(用数组表示)进行排序.并将排序结果存放到另一个新的表屮。必须注意的是,長 中所有待排序的关键码互不相同。计数排序算法针对表屮的每个记录,扫描待排序的長 趟,统计表中有多少个记录的关键码比该记录的关键码小、假设针对某一个记录,统计出的 计数值为c那么,这个记录在新的有序表中的合适的存放位置即为c (1)给出适用于计数排序的数据表定义 (2)使用C亠+语言编写实现计数排序的算法; (3)对于有n个记录的表,关键比较次数是多少 【解答】 (1)数据表定义 数据表的前视声明 template < class Type class Element 据表元素类的定义 关键码 field otherdata: 其他数据成员 Type getkey()( return key; 1 取当前结点的关键码 void setKey( const Type x)i key=x: 将结点的飞键吗修改为x template class Type. >class datalist t 用顺序表来行储待排序的元素这些元素的类型足1ype datalist( int MaxSz-I)efault SIze): MaxSize< Maxsz), CurreniSize(() Vector-new Elemer MasT S Eletment .Type>←Vcto 有储待排序元素的向量 int Maxsize. CurrentSize 最人元素个数与当前兀素个数
(2)计数排序的算法 【案1】 template < class Type> oid count sort( datalist< Type>>& initlist, datalist< Type > resuliLis1)( fori 0: i initi. st, Current Size: 1++) fer=initI ist. Vcctor[1].getKey() result.ist. V_ =initL ist. Vector[ ultI. ist CurrentSize= initL ist CurrentSize: 【方案2】 woid counisori(datalist< Type > titlIst, datalist. Type > resu ti i t)t int *c=new int[ist CurrentS r int i=0;i initl isl. Current Sizc;..)cij=0 for( int j=i+l:i< initlist CurrentSize;ji.+) if (initList Vector getKey()<, initList Vector:. getKey())clil++i else|++ for(i-0; i. init List. Current Size: i+-) rsuitl, Ist, Vector.ci=initl ist Vector[i: result List. Current site initList Current Size (3)对于m个记录的表,【方案1】屮关键码比较次数为n2【方案2】中关键码比较次数 为 【分析】编写算法的题可能是学生比较棘于的问题,特别是在考试这样个氛围,时间又短 促,想编出…个好算法不太容易。…个建议是首先仔细阅读试题,了解它到底要你十什么 然后用一个简单的例子走一下·总结每一步向下走用什么语句,再做归纳。也可以按照结构 化程序设计的方法,先搭框架,再根据例子填入细节。总之,要想又快又好地编写出算法,还 要靠平时的基本训练,多做题.自主做題,各种题型都见过了,考试时自然文思泉涌,笔下就 流畅了。 0.2.6填空题 【例6.1】下面给出的是一个在二叉树中查找值为x的结点,并打印该结点所有祖先结点的
算法,在此算法中,假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式 因退栈时需要区分其左、右子树是否已经遍历,故在结点进栈时附带有一个标志,=0,进入 左子树、1,进入有子树。用栈ST保存结点指针ptr及其标志tag、top是栈顶指针 void print(Bin Tree Node*t; Type &x)i k sT: /置空栈 hile(t!=NULL&&t->>data T x II top!=0) whlle(t !- NULI, &&t-data 〈/:寻找值为x的结点 ST iop].ptr=t /进栈 ST-[topl if(t 1-NULL. &&t->dala=. x) 找到值为x的结点 for(i=1: cout < STTi. ptr->data << endl: else I hile( top>0&&sT[top].tag==1)/未找到值为x的结点 ST/ tag=I: /转向右子树 (1)请将缺失的语句补上(8分) (2)请给出对子右图所示的又树,使用上述算法搜 索值为9的结点和值为10的结点的结果,以及在栈ST 中的变化。(top是栈顶指针) 【解答】 (1)请将缺失的语句补上 t=t->>leftChild
D t=STLtop1. ptr->rightChild (2)搜索值为9的结点 搜索值为10的结点 par tag 山感 【分析】人们常说,读别人的程序不如自已重编。此话有一定道理。各人的思路不同,编程 语言的运用和编程技巧的水平不同,编程风格不问,即使是几个人编写同一个功能的程序 能面貌相差极大,读別人的程序自然困难很大。但现实是将来要做技术支持必须读别人 的程序。所以,必縯有这方面的基本训练和技能。一个矬汊是:通过试题叙述阅读来了解思 路,通过实例分析来了解程序结构,再通过实例跟踪来检验填空后的程序,从而得到最终的 解答。 0.3小结 数据结构课程是计算机专业的基础课程,是一门知识性、实践性都很强的课程。数据结 构及算法编写与分析都是不容易的。学好它需要付出极大的功夫,在平时勤学多练。如果 有碰运气或取巧的想法,}有八九通不过考试。有…次在中央电大直播课堂进行期末答疑, 位学员不问问题,在网上传来一句话:“救救我吧,我已经考了两次没通过了。”对此,只能 为他遗憾。希望他能重新学习,把某础打扎实,考试才能顺利过关。就怕平时不看书,不做 作业或抄别人的作业,到考试时照样不会,自然一次次通不过了。最后,祝愿同学们通过自 己的勤奋努力取得优良的成绩