离散数学课件课后练习

数据结构与算法,2012年秋季,（一）线性结构,1、给定一个有n个元素的线性表。若采用顺序存储结构，则在等概率前提下，向其插入一个元素需要移动的元素个数平均为（）。AnBn/2C(n-1)/2D(n+1)/22、已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半搜索90时，需进行次搜索可确定搜索成功；搜索40时需进行次搜索才能确定不成功。,一、单选题、填空,B,2，4,3、以下程序中划线语句的执行次数是（）。intsum(intn)intsum=0,i,j;for(i=1;i=n;i+)p=1;for(j=1;j=i;j+)p*=j;sum+=p;returnsum;An(n+1)/2Bn(n+1)Cn(n-1)/2Dn(n-1),A,4、计算机执行下面的语句时，语句s的执行次数为。for(i=1;irlink=p-rlink;p-rlink-llink=p-llink;Bp-llink=p-llink-llink;p-llink-rlink=p;Cp-rlink-llink=p;p-rlink=p-rlink-rlinkDp-rlink=p-llink-llink;p-llink=p-rlink-rlink;7、递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A队列B多维数组C栈D.线性表,A,C,8、用I表示入栈操作，O表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的I和O操作串为（）。AIIOOIIOOBIOIOIIOOCIOIIOIOODIOIIOOIO9、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（）A1和5B2和4C4和2D5和1,C,B,10、数组A0.5,0.6的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是（）。A1175B1180C1205D121011、算术表达式a+b*（c+d/e）转为后缀表达式后为（）。Aab+cde/*Babcde/+*+Cabcde/*+Dabcde*/+,A,B,13、设有一组关键码19，01，23，14，55，20，84，27，68，11，10，77，采用散列函数H（key）=key%13，处理冲突的方法是线性探测再散列的方法（即dj+1=（dj+1）%m）若在018（即m=19）的散列地址空间中对该关键码构造散列表，则关键码14对应的地址是（）。A1B2C3D14,B,12、散列技术中的冲突指的是（）。A两个元素具有相同的序号B两个元素的关键码不同，而其他属性相同C数据元素过多D不同关键码的元素对应于相同的存储地址,D,二、解答题,1、设有三对角矩阵，如上图所示，将带状区域中的元素ai,j(|i-j|1)放在一维数组B中，则（1）B的大小为多少？（2）元素ai,j在B中的位置是什么？（B的下标从0开始计，以行优先方式存储）,参考解答,（1）B的大小：3n-2,（2）,解：用除留余数法，H(k)=k%p，p=13，各元素的散列地址如下：H(65)=0，H(23)=10，H(31)=5，H(26)=0，H(7)=7，H(91)=0，H(53)=1，H(15)=2，H(72)=7，H(52)=0，H(49)=10，H(68)=3，,参考解答,三、算法阅读,1、已知一带表头节点的单链表L为（5，7，0，9，4，2，8），first指针指向表头节点，data为链表的值域，link为指针域。阅读以下程序，回答问题。templatevoidChain:fun(Typemin,Typemax)ChainNode*pr=first,*p=first-link;while(p)if(p-datamin,（1）说明该程序的功能；（2）试画出执行L.fun(3,7);调用后的L链表的逻辑示意图。,参考解答,（1）删除单链表中所有大于min且小于max的元素。（2）first-7-0-9-2-8。,算法阅读,voidfun(SListTable,structSListTableint*elem;intsize;,2、list是一个顺序存储的线性表的非递减序列，阅读算法，说明其功能。,阅读示例,【算法功能】删除非递减有序顺序表中值相等的多余元素。,i,j,list,四、算法填空？,1、【算法功能】从一个顺序存储在线性表的非递减序列删除值相等的多余元素。,structSListTableint*elem;intsize;,voiddeleteDuplicate(SListTable（3）,参考解答,（1）j+;,（2）list.elemj=list.elemi;,（3）list.size=j;,（1）Fibonacci序列0,1,1,2,3,5,8,13,21,34.，其中每个元素是前两个元素之和，可递归定义为：试利用栈来模拟计算的递归调用，编写一个非递归实现的算法代码，并给出必要的注释。【注明】已知栈的三个运算定义如下（可直接使用）：Push（S，x）：元素x入S栈；Pop（S，x）：S栈顶元素出栈；S_IsEmpty（S）：判断栈空，true为空，false不为空。另外，top为栈顶指针。,5、算法设计与实现,inti,x1,x2;for(i=0;i2;i+)couti”,”;Push(S,i);for(i=2;i=n;+)Pop(S,x1);Pop(S,x2);x1+=x2;coutx1“,“;Push(S,x2);Push(S,x1);,荷兰国旗问题,（2）【荷兰国旗问题】设有红、白、蓝三种颜色的条块组成的条块数组（颜色随机排列），请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。,【算法思想】利用选择排序的思想。首先从序列中选择所有的红色条块，依次放到序列的前面，然后再从剩余的序列中选择所有的白色条块，依次放到红色条块后面。这样经过两趟选择，时间复杂度为O(n)。设这些条块颜色依次存放在L0,n-1中，,voidSort(intL,intn)inti,j;i=0;for(j=i;jn;j+)if(Lj=0)if(j!=i)Swap(Li,Lj);i+;for(j=i;jbottom;i-)if(listiLB0;则LC0=LB0同时j+;,2,3,5,6,7,0,3,4,6,7,8,9,LA,LB,i=0,j=1,0,LC,接下来LB1与LA0比较，以后都一样比较，直至其中一个表到达表尾,当其中一个顺序表到末尾时，直接将另一个表的剩余元素移到新表中。,2,3,5,6,7,0,3,4,6,7,8,9,LA,LB,i=4,j=0,0,6,7,7,9,8,2,3,3,4,5,6,LC,【算法思想】1、设三个指针（实际是整型变量）i，j，k分别指向A，B和C中某个元素，初值：i，j为1，k为0；2、分别从A和B中取得i，j所指向的两个元素；3、比较两元素的大小，谁小就把谁先插入到C中k所指的位置；4、A或B中剩余部分直接插入C中即可。,顺序表合并算法思想,LinearList*/,TgetI;TgetJ;while(i=n,/剩余部分处理while(ilink=first;first=q;hb.first=NULL;/【注意】如果不将hb.first置空，析构的时候会出问题return*this;,1、一棵高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有成立。A、n=h+mB、h+m=2nC、m=h-1D、n=2m-1,D,2、已知一棵完全二叉树中共有768结点，则该树中共有_个叶子结点。,384,3、已知一棵完全二叉树中共有767结点，则该树中共有_个叶子结点。（软考真题）,384,完全二叉树中度为1的节点数只有两种可能：要么为0个（奇数个结点），要么为1个（偶数个结点）。,4、设节点x和y是二叉树中任意两个节点，在该二叉树的前序遍历序列中x在y之前，而在后序遍历序列中x在y之后，则x和y的关系是：A、x是y的左兄弟B、x是y的右兄弟C、x是y的祖先D、x是y的后裔,C,软考真题,5、已知某二叉树的中序遍历序列是dgbaechf，后序遍历序列是gdbehfca，则其前序遍历序列是（）。AabdgcefhBagdbecfhCabdgechfDadbgcefh,A,6、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是（）。A二叉搜索树B哈夫曼树C堆DAVL树7、用一维数组存放的一棵完全二叉树：ABCDEFGHI，写出中序遍历该二叉树时访问节点的顺序。,HDIBEAFCG,C,8、初始关键码序列为E，D，X，K，H，L，M，C，P，用筛选法所建的最大堆得到的序列是。9、给定14个字母，假设它们的权值都相等。采用Huffman编码，则每个字母的平均编码长度是。,XPMKHLECD,54/14（或3.857）,D,11、有组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始最大堆为：A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，38,B,12、在数据压缩编码应用中，Huffman算法可以用来构造具有（1）的二叉树，这是一种采用了（2）算法的算法。（1）A、前缀码B、最优前缀码C、后缀码D、最优后缀码（2）A、贪心B、分治C、递推D、回溯,解答：（1）B（2）A,13、假设用于通信的电文仅由a，b，c，d，e，f，g，h，8个字母组成，各字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。（1）试为这8个字母设计Huffman编码（需画出相应的Huffman树）。（2）使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。（提示：试从两种编码的带权路径长度上进行比较说明）,WPLHF=2.61，WPLEQ=3提高通信信道的利用率，提高报文发送速度或/和节省存储空间。,课堂练习,B,14、有数据53，30，37，12，45，24，96，从空二叉树开始逐个插入数据来形成二叉搜索树，若希望高度最小，则应选择下面哪个序列输入。A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，53,15、一棵二叉搜索树，其节点A、B、C、D、E、F依次存放在一个起始地址为n（假定地址以字节为单位顺序编号）的连续区域中，每个节点占4个字节：前2个字节存放节点值，后2个字节依次存放左指针、右指针。若该二叉搜索树的根节点为E，则它的一种可能的前序遍历为(1)，相应的层序遍历为(2)。在以上两种遍历的情况下，节点C的左指针Lc的存放地址为(3)，Lc的内容为(4)。节点A的右指针Ra的内容为(5)。（1）A.EAFCBDB.EFACDBC.EABCFDD.EACBDF（2）A.EAFCBDB.EFACDBC.EABCFDD.EACBDF（3）A.n+9B.n+10C.n+12D.n+13（4）A.n+4B.n+8C.n+12D.n+16（5）A.n+4B.n+8C.n+12D.n+16,解答：（1）D；（2）A；（3）B；（4）A；（5）B,16、已知一长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sept，Oct，Nov，Dec）。（1）依次取表中各元素构造一棵二叉搜索树（按照在英文字典中的先后顺序比较元素值的大小）；并求其在等概率情况下搜索成功时的平均搜索长度。（2）若对表中元素进行排序构成有序表，求在等概率情况下对此有序表进行折半搜索成功的平均搜索长度。（3）按表中元素顺序构造一棵AVL树，并求其在等概率情况下搜索成功的平均搜索长度。,解答：（1）42/12；（2）37/12；（3）38/12,二叉搜索树,Jan,Feb,July,Nov,Sept,Mar,June,May,Oct,Apr,Aug,Dec,折半搜索,Mar,Jan,Apr,July,Nov,Oct,June,May,Sept,Aug,Feb,Dec,AVL树,17、下图为一棵AVL树（关键码按字典顺序排列）。要求绘制出加入一个新结点时二叉树的形态；若发生不平衡，需要指明相应的平衡化旋转类型。（1）画出插入关键码cow后的AVL树。（3分）（2）画出在插入关键码cow后继续插入关键码him后的AVL树。（3分）（3）计算经过（1）和（2）结点插入后，该AVL树在等概率情况下搜索成功的平均搜索长度（ASL）。（2分）,参考解答,课后练习,18、假定一组数据对象为(40,28,16,56,50,32,30,63），按次序插入每个对象生成一棵AVL树，根据插入过程画出相应旋转过程和最终结果。,19、假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是。A.树B.图C.线性表D.集合,B,20、在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为。AeB2eCn2-eDn2-2e,D,软考真题,21、设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构（矩阵元素Aij等于0/1分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为（1），其中非零元素数目为为（2）。A.E2B.N2C.N2-E2D.N2+E2A.NB.N+EC.ED.N-E,软考真题,解答：（1）B；（2）C,22、若采用邻接矩阵来存储简单有向图，则某个顶点i的入度等于该矩阵。A、第i行中值为1的元素个数B、所有值为1的元素总数C、第i行及第i列中值为1的元素总个数D、第i列中值为1的元素个数,D,软考真题,23、假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是。AO(n)BO(e)CO(n+e)DO(n*e),C,24、若G是一个具有36条边的非连通无向图（不含自回路和多重边），则图G至少有个顶点。A、11B、10C、9D、8,B,有n个顶点的无向图至多有n(n-1)/2条边。,软考真题,25、无向图G=(V,E)，其中：V=a,b,c,d,e,f，E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是（）。Aa,b,e,c,d,fBa,c,f,e,b,dCa,e,b,c,f,dDa,e,d,f,c,b,D,26、已知带权的无向图G如左图所示（1）画出G的邻接表结构（要求：顶点的各邻接边的链接顺序按照顶点序号由小到大的顺序链接）；（2）基于上述邻接表结构，从顶点A出发，分别写出按深度优先和宽度优先遍历图G的顶点序列。,深度优先遍历序列：ABDCE宽度优先遍历序列：ABCED,算法设计,27、设二叉树节点表示的数据元素类型为T，二叉树以二叉链表表示。一棵二叉树的最大枝长和最小枝长分别定义如下：最大枝长就是二叉树层次；最小枝长就是离根节点距离最近的叶节点距离根路径上的边数。例如，节点数目n=1的二叉树其最大最小枝长都为0，n=2的二叉树其最大最小枝长都为1.请设计一个算法，同时求出一棵二叉树的最大和最小枝长。请从以下几个方面来阐述和表达此算法：（1）（3分）请给出二叉链表表示的二叉树节点BinaryTreeNode的定义，该定义只是服务于（3）中所需要实现的算法，够用即可；（2）（3分）请概要说明此算法思想；（3）（12分）编写算法：函数头建议定义为：templatevoidFarNearleaf(BinaryTreeNode*root,int（4）（2分）请在算法关键的地方给出必要的注释。,参考解答,（1）二叉链表表示的二叉树节点BinaryTreeNode的定义:templateclassBinaryTreeNodepublic:voidFarNearleaf(BinaryTreeNode*root,int,参考解答,（2）算法思想【方法一】DFS深度优先遍历解法按照后序遍历方式求树的最大/小枝长在左右子树最大/最小枝长确定的条件下：根root的最大枝长是左右子树较大的最大枝长+1最小枝长为左右子树较小的最小枝长+1注意区分单支树或给出递推公式NearLeaf(T:B,L,R)=min(NearLeaf(L),NearLeaf(R)+1FarLeaf(T:B,L,R)=max(FarrLeaf(L),FarLeaf(R)+1,参考解答,（2）算法思想【方法二】BFS广度优先遍历（层次遍历）解法层次遍历时，遇到的第一个叶节点必有最小枝长，遇到的而最后一个叶节点必有最大枝长。,3、算法实现【方法一】templatevoidFarNearLeaf(BinaryTreeNode*root,int,if(root-leftPtr=NULL),28、二叉树采用链式存储结构，试设计一个算法计算一棵二叉树的所有结点数。,f(b)=0若b=NULLf(b)=1若b-leftChild=NULL且b-rightChild=NULLf(b)=f(b-leftChild)+f(b-rightChild)+1其他,templateintBinaryTree:nodes(BinTreeNode*t)if(t=NULL)return0;if(t-leftChild=NULL,二叉树采用链式存储结构，试设计一个算法计算一棵二叉树的所有叶结点数。二叉树采用链式存储结构，试设计一个算法计算一棵二叉树的所有非叶结点数。二叉树采用链式存储结构，试设计一个算法计算一棵二叉树的所有度为1的结点数。,1、在文件“局部有序”或文件长度较小的情况下，最佳的内部排序方法是（）A、插入排序B、堆排序C、归并排序D、快速排序,A,最不合适的是？,2、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是。A、G中有弧B、G中有一条从Vj到Vi的路径C、G中没有弧D、G中有一条从Vi到Vj的路径,B,3、设有向图G的顶点集合为v1,v2,v3,v4,v5，边的集合为，G的拓扑序列是。,v1，v2，v3，v4，v5,4、设要将序列（Q，H，C，Y，P，A，M，S，R，D，F，X）中的关键码按升序排列，则两路归并排序第一趟的排序结果是（）。A（F，H，C，D，P，A，M，Q，R，S，Y，X）B（P，A，C，S，Q，D，F，X，R，H，M，Y）C（H，Q，C，Y，A，P，M，S，D，R，F，X）D（H，C，Q，P，A，M，S，R，D，F