《离散数学课件课后练习.ppt》由会员分享，可在线阅读，更多相关《离散数学课件课后练习.ppt（94页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构与算法数据结构与算法20122012年秋季年秋季年秋季年秋季（一）线性结构（一）线性结构 1 1、给给给给定定定定一一一一个个个个有有有有 nn个个个个元元元元素素素素的的的的线线线线性性性性表表表表。若若若若采采采采用用用用顺顺顺顺序序序序存存存存储储储储结结结结构构构构，则则则则在在在在等等等等概概概概率率率率前前前前提提提提下下下下，向向向向其其其其插插插插入入入入一一一一个个个个元元元元素素素素需要移动的元素个数平均为（需要移动的元素个数平均为（需要移动的元素个数平均为（需要移动的元素个数平均为（）。）。）。）。AAnBnBn/2Cn/2C(n-1)/2D(n-1)/2D(n+
2、1)/2(n+1)/2 2 2、已已已已知知知知有有有有序序序序表表表表为为为为（1212，1818，2424，3535，4747，5050，6262，8383，9090，115115，134134），当当当当用用用用折折折折半半半半搜搜搜搜索索索索9090时时时时，需需需需进进进进行行行行 次次次次搜搜搜搜索索索索可可可可确确确确定定定定搜搜搜搜索索索索成成成成功功功功；搜搜搜搜索索索索4040时时时时需需需需进进进进行行行行 次搜索才能确定不成功。次搜索才能确定不成功。次搜索才能确定不成功。次搜索才能确定不成功。一、单选题、填空一、单选题、填空B B2 2，4 43 3、以下程序中划线语句
3、的执行次数是（、以下程序中划线语句的执行次数是（、以下程序中划线语句的执行次数是（、以下程序中划线语句的执行次数是（）。）。）。）。intsum(intn)intsum(intn)intsum=0,i,j;intsum=0,i,j;for(i=1;i=n;i+)for(i=1;i=n;i+)p=1;p=1;for(j=1;j=i;j+)for(j=1;j=i;j+)p*=j;p*=j;sum+=p;sum+=p;returnsum;returnsum;A An(n+1)/2n(n+1)/2 B Bn(n+1)n(n+1)C Cn(n-1)/2n(n-1)/2D Dn(n-1)n(n-1)A A
4、4 4、计算机执行下面的语句时，语句、计算机执行下面的语句时，语句s s的执行次数为的执行次数为 。for(i=1;in-1;i+)for(i=1;in-1;i+)for(j=1;j=i;j+)for(j=1;jllink-rlink=p-rlink;p-rlink-llink=p-llink;p-llink-rlink=p-rlink;p-rlink-llink=p-llink;B B p-llink=p-llink-llink;p-llink-rlink=p;p-llink=p-llink-llink;p-llink-rlink=p;C C p-rlink-llink=p;p-rlink=
5、p-rlink-rlinkp-rlink-llink=p;p-rlink=p-rlink-rlinkD D p-rlink=p-llink-llink;p-llink=p-rlink-rlink;p-rlink=p-llink-llink;p-llink=p-rlink-rlink;7 7、递归过程或函数调用时，处理参数及返回地址，要用一、递归过程或函数调用时，处理参数及返回地址，要用一、递归过程或函数调用时，处理参数及返回地址，要用一、递归过程或函数调用时，处理参数及返回地址，要用一种称为（种称为（种称为（种称为（）的数据结构。）的数据结构。）的数据结构。）的数据结构。A A队列队列队列队列
6、B B多维数组多维数组多维数组多维数组C C栈栈栈栈D.D.线性表线性表线性表线性表A AC C8 8、用、用、用、用I I表示入栈操作，表示入栈操作，表示入栈操作，表示入栈操作，OO表示出栈操作，若元素入栈顺序为表示出栈操作，若元素入栈顺序为表示出栈操作，若元素入栈顺序为表示出栈操作，若元素入栈顺序为12341234，为了得到，为了得到，为了得到，为了得到13421342出栈顺序，相应的出栈顺序，相应的出栈顺序，相应的出栈顺序，相应的I I和和和和OO操作串为（操作串为（操作串为（操作串为（）。）。）。）。A AIIOOIIOOBIIOOIIOOBIOIOIIOOIOIOIIOOCCIOII
7、OIOODIOIIOIOODIOIIOOIOIOIIOOIO9 9、若用一个大小为、若用一个大小为、若用一个大小为、若用一个大小为6 6的数组来实现循环队列，且当前的数组来实现循环队列，且当前的数组来实现循环队列，且当前的数组来实现循环队列，且当前rearrear和和和和frontfront的值分别为的值分别为的值分别为的值分别为0 0和和和和3 3，当从队列中删除一个元素，再加入两，当从队列中删除一个元素，再加入两，当从队列中删除一个元素，再加入两，当从队列中删除一个元素，再加入两个元素后，个元素后，个元素后，个元素后，rearrear和和和和frontfront的值分别为多少？（的值分别为
8、多少？（的值分别为多少？（的值分别为多少？（）A A 1 1和和和和 5B5B 2 2和和和和4C4C4 4和和和和2D2D 5 5和和和和11C CB B1010、数组、数组、数组、数组A0.5,0.6A0.5,0.6的每个元素占的每个元素占的每个元素占的每个元素占5 5个字节，将其个字节，将其个字节，将其个字节，将其按列优先按列优先按列优先按列优先次次次次序存储在起始地址为序存储在起始地址为序存储在起始地址为序存储在起始地址为10001000的内存单元中，则元素的内存单元中，则元素的内存单元中，则元素的内存单元中，则元素A5A5，55的地的地的地的地址是（址是（址是（址是（）。）。）。）。
9、A A 1175B1175B 1180C1180C1205D1205D121012101111、算术表达式、算术表达式、算术表达式、算术表达式a+b*a+b*（c+d/ec+d/e）转为后缀表达式后为（）转为后缀表达式后为（）转为后缀表达式后为（）转为后缀表达式后为（）。）。）。）。A Aab+cde/*Bab+cde/*Babcde/+*+abcde/+*+CCabcde/*+Dabcde/*+Dabcde*/+abcde*/+A AB B1313、设有一组关键码、设有一组关键码、设有一组关键码、设有一组关键码1919，0101，2323，1414，5555，2020，8484，2727，6
10、868，1111，1010，7777，采用散列函数，采用散列函数，采用散列函数，采用散列函数HH（keykey）=key%13=key%13，处理冲，处理冲，处理冲，处理冲突的方法是线性探测再散列的方法（即突的方法是线性探测再散列的方法（即突的方法是线性探测再散列的方法（即突的方法是线性探测再散列的方法（即d dj+1j+1=（d dj j+1+1）%m%m）若在若在若在若在018018（即（即（即（即m=19m=19）的散列地址空间中对该关键码构造散）的散列地址空间中对该关键码构造散）的散列地址空间中对该关键码构造散）的散列地址空间中对该关键码构造散列表，则关键码列表，则关键码列表，则关键码
11、列表，则关键码1414对应的地址是（对应的地址是（对应的地址是（对应的地址是（）。）。）。）。A A1B1B2C2C3D3D1414B B1212、散列技术中的冲突指的是（、散列技术中的冲突指的是（、散列技术中的冲突指的是（、散列技术中的冲突指的是（）。）。）。）。A A两个元素具有相同的序号两个元素具有相同的序号两个元素具有相同的序号两个元素具有相同的序号B B两个元素的关键码不同，而其他属性相同两个元素的关键码不同，而其他属性相同两个元素的关键码不同，而其他属性相同两个元素的关键码不同，而其他属性相同 C C数据元素过多数据元素过多数据元素过多数据元素过多 D D不同关键码的元素对应于相同
12、的存储地址不同关键码的元素对应于相同的存储地址不同关键码的元素对应于相同的存储地址不同关键码的元素对应于相同的存储地址D D二、解答题二、解答题1 1、设有三对角矩阵，如上图所示，将带状区域中的元素、设有三对角矩阵，如上图所示，将带状区域中的元素、设有三对角矩阵，如上图所示，将带状区域中的元素、设有三对角矩阵，如上图所示，将带状区域中的元素a ai,ji,j(|i-j|1)(|i-j|1)放在一维数组放在一维数组放在一维数组放在一维数组B B中，则中，则中，则中，则（1 1）B B的大小为多少？的大小为多少？的大小为多少？的大小为多少？（2 2）元素）元素）元素）元素a ai,ji,j在在在在
13、B B中的位置是什么？（中的位置是什么？（中的位置是什么？（中的位置是什么？（B B的下标从的下标从的下标从的下标从0 0开始计，开始计，开始计，开始计，以行优先方式存储）以行优先方式存储）以行优先方式存储）以行优先方式存储）参考解答参考解答（1 1）B B的大小：的大小：的大小：的大小：3n-23n-2（2 2）解：用除留余数法，解：用除留余数法，解：用除留余数法，解：用除留余数法，H(k)=k%pH(k)=k%p，p=13p=13，各元素的散列地址如各元素的散列地址如各元素的散列地址如各元素的散列地址如下：下：下：下：H(65)=0H(65)=0，H(23)=10H(23)=10，H(31
14、)=5H(31)=5，H(26)=0H(26)=0，H(7)=7H(7)=7，H(91)=0H(91)=0，H(53)=1H(53)=1，H(15)=2H(15)=2，H(72)=7H(72)=7，H(52)=0H(52)=0，H(49)=10H(49)=10，H(68)=3H(68)=3，参考解答参考解答三、算法阅读三、算法阅读1 1、已知一带表头节点的单链表、已知一带表头节点的单链表、已知一带表头节点的单链表、已知一带表头节点的单链表L L为（为（为（为（5 5，7 7，0 0，9 9，4 4，2 2，8 8），），），），firstfirst指针指向表头节点，指针指向表头节点，指针指向表
15、头节点，指针指向表头节点，datadata为链表的值域，为链表的值域，为链表的值域，为链表的值域，linklink为指针域。阅读为指针域。阅读为指针域。阅读为指针域。阅读以下程序，回答问题。以下程序，回答问题。以下程序，回答问题。以下程序，回答问题。templatetemplatevoidChain:fun(Typemin,Typemax)voidChain:fun(Typemin,Typemax)ChainNode*pr=first,*p=first-link;ChainNode*pr=first,*p=first-link;while(p)while(p)if(p-datamin&p-da
16、tadatamin&p-datalink=p-link;deletep;p=pr-link;pr-link=p-link;deletep;p=pr-link;elseelsepr=p;p=pr-link;pr=p;p=pr-link;（1 1）说明该程序的功能；）说明该程序的功能；（2 2）试画出执行）试画出执行L.fun(3,7);L.fun(3,7);调用调用后的后的L L链表的逻辑示意图。链表的逻辑示意图。参考解答参考解答v（1 1）删除单链表中所有大于）删除单链表中所有大于）删除单链表中所有大于）删除单链表中所有大于minmin且小于且小于且小于且小于maxmax的元素。的元素。的元素
17、。的元素。v（2 2）first-7-0-9-2-8first-7-0-9-2-8。算法阅读算法阅读voidfun(SListTable&list)voidfun(SListTable&list)inti=1;inti=1;intj=0;intj=0;while(ilist.size)while(ilist.size)if(list.elemi!=list.elemj)if(list.elemi!=list.elemj)j+;j+;list.elemj=list.elemi;list.elemj=list.elemi;i+;i+;size=j;size=j;structSListTablest
18、ructSListTable int*elem;int*elem;intsize;intsize;2 2、listlist是一个顺是一个顺是一个顺是一个顺序存储的线性表序存储的线性表序存储的线性表序存储的线性表的非递减序列，的非递减序列，的非递减序列，的非递减序列，阅读算法，说明阅读算法，说明阅读算法，说明阅读算法，说明其功能。其功能。其功能。其功能。阅读示例阅读示例【算法功能算法功能算法功能算法功能】删除非递减有序顺序表中值相等的多余元素。删除非递减有序顺序表中值相等的多余元素。删除非递减有序顺序表中值相等的多余元素。删除非递减有序顺序表中值相等的多余元素。i ij jlistlist四四、
19、算法填空？、算法填空？vv1 1、【算法功能算法功能算法功能算法功能】从一个顺序存储在从一个顺序存储在从一个顺序存储在从一个顺序存储在线性表的非递减序线性表的非递减序线性表的非递减序线性表的非递减序列删除值相等的多列删除值相等的多列删除值相等的多列删除值相等的多余元素。余元素。余元素。余元素。structSListTablestructSListTable int*elem;int*elem;intsize;intsize;voiddeleteDuplicate(SListTable&list)voiddeleteDuplicate(SListTable&list)inti=1;inti=1;
20、intj=0;intj=0;while(ilist.size)while(ilist.size)if(list.elemi!=list.elemj)if(list.elemi!=list.elemj)（1 1）（2 2）i+;i+;（3 3）参考解答参考解答（1 1）j+;j+;（2 2）list.elemj=list.elemi;list.elemj=list.elemi;（3 3）list.size=j;list.size=j;（1 1）FibonacciFibonacci序序序序列列列列0,1,1,2,3,5,8,13,21,34.0,1,1,2,3,5,8,13,21,34.，其其其其
21、中中中中每每每每个个个个元元元元素素素素是前两个元素之和，可递归定义为：是前两个元素之和，可递归定义为：是前两个元素之和，可递归定义为：是前两个元素之和，可递归定义为：试试试试利利利利用用用用栈栈栈栈来来来来模模模模拟拟拟拟计计计计算算算算的的的的递递递递归归归归调调调调用用用用，编编编编写写写写一一一一个个个个非非非非递递递递归归归归实实实实现的算法代码，并给出必要的注释。现的算法代码，并给出必要的注释。现的算法代码，并给出必要的注释。现的算法代码，并给出必要的注释。【注明注明注明注明】已知栈的三个运算定义如下（可直接使用）：已知栈的三个运算定义如下（可直接使用）：已知栈的三个运算定义如下（
22、可直接使用）：已知栈的三个运算定义如下（可直接使用）：PushPush（S S，x x）：元素）：元素）：元素）：元素x x入入入入S S栈；栈；栈；栈；PopPop（S S，x x）：）：）：）：S S栈顶元素出栈；栈顶元素出栈；栈顶元素出栈；栈顶元素出栈；S_IsEmptyS_IsEmpty（S S）：判判判判断断断断栈栈栈栈空空空空，truetrue为为为为空空空空，falsefalse不不不不为为为为空空空空。另另另另外，外，外，外，toptop为栈顶指针。为栈顶指针。为栈顶指针。为栈顶指针。5、算法设计与实现、算法设计与实现inti,x1,x2;inti,x1,x2;for(i=0;
23、i2;i+)couti”,”;Push(S,i);for(i=0;i2;i+)couti”,”;Push(S,i);for(i=2;i=n;+)for(i=2;i=n;+)Pop(S,x1);Pop(S,x1);Pop(S,x2);Pop(S,x2);x1+=x2;x1+=x2;coutx1“,“;coutx1“,“;Push(S,x2);Push(S,x2);Push(S,x1);Push(S,x1);荷兰国旗问题荷兰国旗问题vv（2 2）【荷兰国旗问题荷兰国旗问题荷兰国旗问题荷兰国旗问题】设有红、设有红、设有红、设有红、白、蓝三种颜色的条块组成的条白、蓝三种颜色的条块组成的条白、蓝三种颜色
24、的条块组成的条白、蓝三种颜色的条块组成的条块数组（颜色随机排列），请编块数组（颜色随机排列），请编块数组（颜色随机排列），请编块数组（颜色随机排列），请编写一个时间复杂度为写一个时间复杂度为写一个时间复杂度为写一个时间复杂度为O(n)O(n)的算法，的算法，的算法，的算法，使得这些条块按红、白、蓝的顺使得这些条块按红、白、蓝的顺使得这些条块按红、白、蓝的顺使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。序排好，即排成荷兰国旗图案。序排好，即排成荷兰国旗图案。序排好，即排成荷兰国旗图案。【算法思想算法思想算法思想算法思想】利用选择排序的思想。首先从序列中选择所有利用选择排序的思想。首先从
25、序列中选择所有利用选择排序的思想。首先从序列中选择所有利用选择排序的思想。首先从序列中选择所有的红色条块，依次放到序列的前面，然后再从剩余的序列中的红色条块，依次放到序列的前面，然后再从剩余的序列中的红色条块，依次放到序列的前面，然后再从剩余的序列中的红色条块，依次放到序列的前面，然后再从剩余的序列中选择所有的白色条块，依次放到红色条块后面。这样经过两选择所有的白色条块，依次放到红色条块后面。这样经过两选择所有的白色条块，依次放到红色条块后面。这样经过两选择所有的白色条块，依次放到红色条块后面。这样经过两趟选择，时间复杂度为趟选择，时间复杂度为趟选择，时间复杂度为趟选择，时间复杂度为O(n)O
26、(n)。设这些条块颜色依次存放在。设这些条块颜色依次存放在。设这些条块颜色依次存放在。设这些条块颜色依次存放在L0,n-1L0,n-1中，中，中，中，voidSort(intL,intn)voidSort(intL,intn)inti,j;inti,j;i=0;i=0;for(j=i;jn;j+)for(j=i;jn;j+)if(Lj=0)if(Lj=0)if(j!=i)if(j!=i)Swap(Li,Lj);Swap(Li,Lj);i+;i+;for(j=i;jn;j+)for(j=i;jn;j+)if(Lj=1)if(Lj=1)if(j!=i)if(j!=i)Swap(Li,Lj);Swa
27、p(Li,Lj);i+;i+;鸡尾酒排序鸡尾酒排序vv（3 3）【鸡尾酒排序鸡尾酒排序鸡尾酒排序鸡尾酒排序】是冒泡排序的轻微变形。是冒泡排序的轻微变形。是冒泡排序的轻微变形。是冒泡排序的轻微变形。【鸡尾酒排序鸡尾酒排序鸡尾酒排序鸡尾酒排序】相邻两趟方向相反的冒泡，例如第一趟排相邻两趟方向相反的冒泡，例如第一趟排相邻两趟方向相反的冒泡，例如第一趟排相邻两趟方向相反的冒泡，例如第一趟排序将最大记录冒泡到数组底部，而在第二趟排序中将最小序将最大记录冒泡到数组底部，而在第二趟排序中将最小序将最大记录冒泡到数组底部，而在第二趟排序中将最小序将最大记录冒泡到数组底部，而在第二趟排序中将最小记录冒泡到数组的
28、顶部，请按上述算法思想实现鸡尾酒排记录冒泡到数组的顶部，请按上述算法思想实现鸡尾酒排记录冒泡到数组的顶部，请按上述算法思想实现鸡尾酒排记录冒泡到数组的顶部，请按上述算法思想实现鸡尾酒排序。序。序。序。templatetemplatevoidSwap(T&a,T&b)voidSwap(T&a,T&b)Ttemp;Ttemp;temp=a;temp=a;a=b;a=b;b=temp;b=temp;函数原型：函数原型：函数原型：函数原型：templatetemplatevoidCocktail_sort(Tlist,intvoidCocktail_sort(Tlist,intlist_length)
29、list_length)；请每位同学写在纸上交上来请每位同学写在纸上交上来请每位同学写在纸上交上来请每位同学写在纸上交上来（请写上班学号和姓名）。（请写上班学号和姓名）。（请写上班学号和姓名）。（请写上班学号和姓名）。鸡尾酒排序示例鸡尾酒排序示例参考解答参考解答template void cocktail_sort(T list,int list_length)template void cocktail_sort(T list,int list_length)/the first element of list has index 0/the first element of list ha
30、s index 0 int bottom=0;int bottom=0;int top=list_length-1;int top=list_length-1;bool swapped=true;bool swapped=true;while(swapped=true)while(swapped=true)/if no elements have been swapped,then the list is sorted/if no elements have been swapped,then the list is sorted swapped=false;swapped=false;for
31、(int i=bottom;i top;i+)for(int i=bottom;i listi+1)if(listi listi+1)/test whether the two elements are in the correct order/test whether the two elements are in the correct order Swap(listi,listi+1);Swap(listi,listi+1);/let the two elements change places/let the two elements change places swapped=tru
32、e;swapped=true;/decreases top the because the element with the largest value in the unsorted/decreases top the because the element with the largest value in the unsorted /part of the list is now on the position top /part of the list is now on the position top top=top-1;top=top-1;for(inti=top;ibottom
33、;i-)for(inti=top;ibottom;i-)if(listilisti-1)if(listiLB0;LA0LB0;则则则则LC0=LB0LC0=LB0同时同时同时同时j+;j+;2 23 35 56 67 70 03 34 46 67 78 89 9LALALBLBi=0i=0j=1j=10 0LCLC接下来接下来接下来接下来LB1LB1与与与与LA0LA0比比比比较，以后都一样比较，较，以后都一样比较，较，以后都一样比较，较，以后都一样比较，直至其中一个表到达表直至其中一个表到达表直至其中一个表到达表直至其中一个表到达表尾尾尾尾当其中一个顺序表到末尾时，直接将另一个表的剩余元素移
34、当其中一个顺序表到末尾时，直接将另一个表的剩余元素移当其中一个顺序表到末尾时，直接将另一个表的剩余元素移当其中一个顺序表到末尾时，直接将另一个表的剩余元素移到新表中。到新表中。到新表中。到新表中。2 23 35 56 67 70 03 34 46 67 78 89 9LALALBLBi=4i=4j=0j=00 06 67 77 79 98 82 23 33 34 45 56 6LCLC【算法思想算法思想算法思想算法思想】1 1、设三个指针（实际是整型变量）、设三个指针（实际是整型变量）、设三个指针（实际是整型变量）、设三个指针（实际是整型变量）i i，j j，k k分别指向分别指向分别指向分别
35、指向A A，B B和和和和C C中某个元素，初值：中某个元素，初值：中某个元素，初值：中某个元素，初值：i i，j j为为为为1 1，k k为为为为0 0；2 2、分别从、分别从、分别从、分别从A A和和和和B B中取得中取得中取得中取得i i，j j所指向的两个元素；所指向的两个元素；所指向的两个元素；所指向的两个元素；3 3、比较两元素的大小，谁小就把谁先插入到、比较两元素的大小，谁小就把谁先插入到、比较两元素的大小，谁小就把谁先插入到、比较两元素的大小，谁小就把谁先插入到C C中中中中k k所指的位置；所指的位置；所指的位置；所指的位置；4 4、A A或或或或B B中剩余部分直接插入中剩
36、余部分直接插入中剩余部分直接插入中剩余部分直接插入C C中即可。中即可。中即可。中即可。顺序表合并算法思想顺序表合并算法思想LinearList&LinearListLinearList&LinearList:Merge(constLinearList&A,constLinearList&B):Merge(constLinearList&A,constLinearList&B)inti=1,j=1,k=0;inti=1,j=1,k=0;intn=A.Length();intn=A.Length();intm=B.Length();intm=B.Length();/*/*if(MaxSizem+
37、n)if(MaxSizem+n)MaxSize=m+n;MaxSize=m+n;deleteelement;deleteelement;element=newTMaxSize+1;element=newTMaxSize+1;length=0;length=0;*/*/TgetI;TgetI;TgetJ;TgetJ;while(i=n&j=m)while(i=n&j=m)getI=A.Get(i);getI=A.Get(i);getJ=B.Get(j);getJ=B.Get(j);if(getI=getJ)if(getI=getJ)Insert(k,getI);Insert(k,getI);k+
38、;k+;i+;i+;elseelseInsert(k,getJ);Insert(k,getJ);k+;k+;j+;j+;/剩余部分处理剩余部分处理剩余部分处理剩余部分处理while(i=n)while(i=n)getI=A.Get(i);getI=A.Get(i);Insert(k,getI);Insert(k,getI);k+;k+;i+;i+;while(j=m)while(j=m)getJ=B.Get(j);getJ=B.Get(j);Insert(k,getJ);Insert(k,getJ);k+;k+;j+;j+;return*this;return*this;函数的不同形式函数的不
39、同形式classLinearListclassLinearList privateprivate：publicpublic：LinearList&Merge(constLinearList&A,constLinearList&B);LinearList&Merge(constLinearList&A,constLinearList&B);LinearListMerge(constLinearList&A,constLinearList&B);LinearListMerge(constLinearList&A,constLinearList&B);voidMerge(constLinearLis
40、t&A,constLinearList&B,voidMerge(constLinearList&A,constLinearList&B,LinearList&C);LinearList&C);；2、单链表合并、单链表合并 将将将将MergeMerge函数设计成为函数设计成为函数设计成为函数设计成为ChainChain类的成员函数；类的成员函数；类的成员函数；类的成员函数；写写写写main()main()函数测试函数测试函数测试函数测试MergeMerge的正确性。的正确性。的正确性。的正确性。【题目及要求题目及要求题目及要求题目及要求】设设设设A A和和和和B B分别表示两个不带表头结点的非递
41、减分别表示两个不带表头结点的非递减分别表示两个不带表头结点的非递减分别表示两个不带表头结点的非递减有序单链表，试设计一个算法，将这两个有序链表合并成一个有序单链表，试设计一个算法，将这两个有序链表合并成一个有序单链表，试设计一个算法，将这两个有序链表合并成一个有序单链表，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存非递增有序的单链表。要求结果链表仍使用原来两个链表的存非递增有序的单链表。要求结果链表仍使用原来两个链表的存非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他存储空间。表中允许有重复的数据。储空间，不另外占
42、用其他存储空间。表中允许有重复的数据。储空间，不另外占用其他存储空间。表中允许有重复的数据。储空间，不另外占用其他存储空间。表中允许有重复的数据。函数的不同形式函数的不同形式templatetemplateclassChainclassChain publicpublic：Chain&Merge(Chain&hb);Chain&Merge(Chain&hb);voidMerge(Chain&hb);voidMerge(Chain&hb);voidMerge(Chain&ha,Chain&hb);voidMerge(Chain&ha,Chain&hb);templatetemplateChain
43、&Chain:Merge(Chain&hb)Chain&Chain:Merge(Chain&hb)/将当前链表将当前链表将当前链表将当前链表thisthis与链表与链表与链表与链表hbhb按逆序合并，结果放在当前链表按逆序合并，结果放在当前链表按逆序合并，结果放在当前链表按逆序合并，结果放在当前链表thisthis中。中。中。中。ChainNode*pa,*pb,*q,*p;ChainNode*pa,*pb,*q,*p;pa=first;pa=first;pb=hb.first;/pb=hb.first;/检测指针检测指针检测指针检测指针pa,pbpa,pbfirst=NULL;first=N
44、ULL;/结果链表初始化结果链表初始化结果链表初始化结果链表初始化while(pa!=NULL&pb!=NULL)/while(pa!=NULL&pb!=NULL)/当两链表都未结束时当两链表都未结束时当两链表都未结束时当两链表都未结束时 if(pa-datadata)/if(pa-datadata)/从从从从papa链中摘下链中摘下链中摘下链中摘下 q=pa;q=pa;pa=pa-link;pa=pa-link;elseelse/从从从从pbpb链中摘下链中摘下链中摘下链中摘下 q=pb;q=pb;pb=pb-link;pb=pb-link;q-link=first;q-link=first
45、;first=q;first=q;/链入结果链的链头链入结果链的链头链入结果链的链头链入结果链的链头 p=(pa!=NULL)?pa:pb;/p=(pa!=NULL)?pa:pb;/处理未完链的剩余部分处理未完链的剩余部分处理未完链的剩余部分处理未完链的剩余部分while(p!=NULL)while(p!=NULL)q=p;q=p;p=p-link;p=p-link;q-link=first;q-link=first;first=q;first=q;hb.first=NULL;hb.first=NULL;/【注意】如果不将【注意】如果不将【注意】如果不将【注意】如果不将hb.firsthb.f
46、irst置空，析构的时候会出问题置空，析构的时候会出问题置空，析构的时候会出问题置空，析构的时候会出问题return*this;return*this;1 1、一棵高度为、一棵高度为、一棵高度为、一棵高度为h h的满二叉树共有的满二叉树共有的满二叉树共有的满二叉树共有n n个结点，其中有个结点，其中有个结点，其中有个结点，其中有mm个叶子个叶子个叶子个叶子结点，则有结点，则有结点，则有结点，则有成立。成立。成立。成立。A A、n=h+mBn=h+mB、h+m=2nh+m=2nCC、m=h-1Dm=h-1D、n=2m-1n=2m-1 D D22、已知一棵完全二叉树中共有、已知一棵完全二叉树中共有
47、、已知一棵完全二叉树中共有、已知一棵完全二叉树中共有768768结点，则该树中共有结点，则该树中共有结点，则该树中共有结点，则该树中共有_个叶子结点。个叶子结点。个叶子结点。个叶子结点。384384 3 3、已知一棵完全二叉树中共有、已知一棵完全二叉树中共有、已知一棵完全二叉树中共有、已知一棵完全二叉树中共有767767结点，则该树中共有结点，则该树中共有结点，则该树中共有结点，则该树中共有_个叶子结点。（软考真题）个叶子结点。（软考真题）个叶子结点。（软考真题）个叶子结点。（软考真题）384384完全二叉树中度为完全二叉树中度为完全二叉树中度为完全二叉树中度为1 1的节点数只有两种可能：要么
48、为的节点数只有两种可能：要么为的节点数只有两种可能：要么为的节点数只有两种可能：要么为0 0个个个个（奇数个结点），要么为（奇数个结点），要么为（奇数个结点），要么为（奇数个结点），要么为1 1个（偶数个结点）。个（偶数个结点）。个（偶数个结点）。个（偶数个结点）。4 4、设节点设节点设节点设节点x x和和和和y y是二叉树中任意两个节点，在该二叉树的前是二叉树中任意两个节点，在该二叉树的前是二叉树中任意两个节点，在该二叉树的前是二叉树中任意两个节点，在该二叉树的前序遍历序列中序遍历序列中序遍历序列中序遍历序列中x x在在在在y y之前，而在后序遍历序列中之前，而在后序遍历序列中之前，而在后序
49、遍历序列中之前，而在后序遍历序列中x x在在在在y y之后，则之后，则之后，则之后，则x x和和和和y y的关系是：的关系是：的关系是：的关系是：A A、x x是是是是y y的左兄弟的左兄弟的左兄弟的左兄弟B B、x x是是是是y y的右兄弟的右兄弟的右兄弟的右兄弟C C、x x是是是是y y的祖先的祖先的祖先的祖先D D、x x是是是是y y的后裔的后裔的后裔的后裔C C软考真题软考真题5 5、已知某二叉树的、已知某二叉树的、已知某二叉树的、已知某二叉树的中序遍历序列是中序遍历序列是中序遍历序列是中序遍历序列是dgbaechfdgbaechf，后序遍历序列后序遍历序列后序遍历序列后序遍历序列
50、是是是是gdbehfcagdbehfca，则其前序遍历序列是（，则其前序遍历序列是（，则其前序遍历序列是（，则其前序遍历序列是（）。）。）。）。A AabdgcefhBabdgcefhBagdbecfhagdbecfhCCabdgechfDabdgechfD adbgcefhadbgcefhA A6 6、若从二叉树的任一结点出发到根的路径上所经过的结点、若从二叉树的任一结点出发到根的路径上所经过的结点、若从二叉树的任一结点出发到根的路径上所经过的结点、若从二叉树的任一结点出发到根的路径上所经过的结点序列序列序列序列按其关键字有序按其关键字有序按其关键字有序按其关键字有序，则该二叉树是（，则该二