二分图及其应用

高中数学选修2-3《2.2二项分布及其应用》测试卷解析版一．选择题（共6小题）1．三个元件T1，T2，T3正常工作的概率分别为且是互相独立的，按图种方式接入电路，电路正常工作的概率是（）A．B．C．D．【分析】电路正常工作的条件是T1必须正常工作，T2，T3至少有一个正常工作，由此利用相互独立事件乘法公式和对立事件概率公式能求出电路正常工作的概率．【解答】解：∵三个元件T1，T2，T3正常工作的概率分别为且是互相独立的，图种方式接入电路，∴电路正常工作的条件是T1必须正常工作，T2，T3至少有一个正常工作，∴电路正常工作的概率：P＝（1﹣）＝．故选：C．【点评】本题考查概率的求法，是基础题，解题时要认真审题，注意相互独立事件乘法公式和对立事件概率计算公式的合理运用．2．抛掷3枚质地均匀的硬币，A＝{既有正面向上又有反面向上}，B＝{至多有一个反面向上}，则A与B关系是（）A．互斥事件B．对立事件C．相互独立事件D．不相互独立事件【分析】由于A中的事件发生与否对于B中的事件是否发生不产生影响，故A与B是相互独立的，从而得出结论．【解答】解：由于A中的事件发生与否对于B中的事件是否发生不产生影响，故A与B 是相互独立的，故选：C．【点评】本题主要考查相互独立事件的定义，属于基础题．3．某地区空气质量监测资料表明，一天的空气质量为优良的概率是0.75，连续两天为优良的概率是0.6，已知某天的空气质量为优良，则随后一天的空气质量为优良的概率是（）A．0.8B．0.75C．0.6D．0.45【分析】设随后一天的空气质量为优良的概率为p，则由题意可得0.75×p＝0.6，由此解得p的值．【解答】解：设随后一天的空气质量为优良的概率为p，则由题意可得0.75×p＝0.6，解得p＝0.8，故选：A．【点评】本题主要考查相互独立事件的概率乘法公式的应用，属于基础题．4．投篮测试中，每人投3次，至少投中2次才能通过测试．已知某同学每次投篮投中的概率为0.6，且各次投篮是否投中相互独立，则该同学通过测试的概率为（）A．0.648B．0.432C．0.36D．0.312【分析】判断该同学投篮投中是独立重复试验，然后求解概率即可．【解答】解：由题意可知：同学3次测试满足X∽B（3，0.6），该同学通过测试的概率为＝0.648．故选：A．【点评】本题考查独立重复试验概率的求法，基本知识的考查．5．设某批产品合格率为，不合格率为，现对该产品进行测试，设第ε次首次取到正品，则P（ε＝3）等于（）A．C32（）2×（）B．C32（）2×（）C．（）2×（）D．（）2×（）【分析】根据题意，P（ε＝3）即第3次首次取到正品的概率，若第3次首次取到正品，即前两次取到的都是次品，第3次取到正品，由相互独立事件的概率计算可得答案．【解答】解：根据题意，P（ε＝3）即第3次首次取到正品的概率；若第3次首次取到正品，即前两次取到的都是次品，第3次取到正品，则P（ε＝3）＝（）2×（）；故选：C．【点评】本题考查相互独立事件的概率计算，解题的关键在于正确理解P（ε＝3）的意义．6．已知P（B|A）＝，P（A）＝，则P（AB）＝（）A．B．C．D．【分析】根据条件概率的公式，整理出求事件AB同时发生的概率的表示式，代入所给的条件概率和事件A的概率求出结果．【解答】解：∵P（B/A）＝，P（A）＝，∴P（AB）＝P（B/A）•P（A）＝＝，故选：D．【点评】本题考查条件概率与独立事件，本题解题的关键是记住并且会利用条件概率的公式，要正确运算数据，本题是一个基础题．二．填空题（共1小题）7．为了考察某校各班参加课外小组的人数，从全校随机抽取5个班级，把每个班级参加该小组的人数作为样本数据，已知样本平均数为7，样本方差为4，且样本数据互不相同，则样本数据中的最大值为10．【分析】本题可运用平均数公式求出平均数，再运用方差的公式列出方差表达式，再讨论样本数据中的最大值的情况，即可解决问题．【解答】解：设样本数据为：x1，x2，x3，x4，x5，平均数＝（x1+x2+x3+x4+x5）÷5＝7；方差s2＝[（x1﹣7）2+（x2﹣7）2+（x3﹣7）2+（x4﹣7）2+（x5﹣7）2]÷5＝4．从而有x1+x2+x3+x4+x5＝35，①（x1﹣7）2+（x2﹣7）2+（x3﹣7）2+（x4﹣7）2+（x5﹣7）2＝20．②若样本数据中的最大值为11，不妨设x5＝11，则②式变为：（x1﹣7）2+（x2﹣7）2+（x3﹣7）2+（x4﹣7）2＝4，由于样本数据互不相同，这是不可能成立的；若样本数据为4，6，7，8，10，代入验证知①②式均成立，此时样本数据中的最大值为10．故答案为：10．【点评】本题考查的是平均数和方差的求法．计算方差的步骤是：①计算数据的平均数；②计算偏差，即每个数据与平均数的差；③计算偏差的平方和；④偏差的平方和除以数据个数．三．解答题（共9小题）8．某商场一号电梯从1层出发后可以在2、3、4层停靠．已知该电梯在1层载有4位乘客，假设每位乘客在2、3、4层下电梯是等可能的．（Ⅰ）求这4位乘客中至少有一名乘客在第2层下电梯的概率；（Ⅱ）用X表示4名乘客在第4层下电梯的人数，求X的分布列和数学期望．【分析】（I）根据题意知每位乘客在第2层下电梯的概率都是，至少有一名乘客在第2层下电梯的对立事件是没有人在第二层下电梯，根据对立事件和相互独立事件的概率公式得到结果．（II）由题意知X的可能取值为0，1，2，3，4，由题意可得每个人在第4层下电梯的概率均为，且每个人下电梯互不影响，得到变量符合二项分布，根据二项分布的公式写出分布列和期望．【解答】解：（Ⅰ）设4位乘客中至少有一名乘客在第2层下电梯的事件为A，…（1分）由题意可得每位乘客在第2层下电梯的概率都是，…（3分）则．…（6分）（Ⅱ）X的可能取值为0，1，2，3，4，…（7分）由题意可得每个人在第4层下电梯的概率均为，且每个人下电梯互不影响，所以，．…（9分）X01234P…（11分）．…（13分）【点评】本题看出离散型随机变量的分布列和期望，本题解题的关键是看出变量符合二项分布的特点，后面用公式就使得运算更加简单9．为了了解某年段1000名学生的百米成绩情况，随机抽取了若干学生的百米成绩，成绩全部介于13秒与18秒之间，将成绩按如下方式分成五组：第一组[13，14）；第二组[14，15）；…；第五组[17，18]．按上述分组方法得到的频率分布直方图如图所示，已知图中从左到右的前3个组的频率之比为3：8：19，且第二组的频数为8．（Ⅰ）将频率当作概率，请估计该年段学生中百米成绩在[16，17）内的人数；（Ⅱ）求调查中随机抽取了多少个学生的百米成绩；（Ⅲ）若从第一、五组中随机取出两个成绩，求这两个成绩的差的绝对值大于1秒的概率．【分析】（1）根据频率分步直方图中小正方形的面积是这组数据的频率，用长乘以宽得到面积，即为频率．（II）根据所有的频率之和是1，列出关于x的方程，解出x的值做出样本容量的值，即调查中随机抽取了50个学生的百米成绩．（III）本题是一个古典概型，试验发生所包含的事件是从第一、五组中随机取出两个成绩，满足条件的事件是成绩的差的绝对值大于1秒，列举出事件数，根据古典概型概率公式得到结果．【解答】解：（Ⅰ）百米成绩在[16，17）内的频率为0.32×1＝0.32，则共有1000×0.32＝320人；（Ⅱ）设图中从左到右前3个组的频率分别为3x，8x，19x依题意，得3x+8x+19x+0.32+0.08＝1，∴x＝0.02设调查中随机抽取了n个学生的百米成绩，∴n＝50∴调查中随机抽取了50个学生的百米成绩．（Ⅲ）百米成绩在第一组的学生数有3×0.02×1×50＝3，记他们的成绩为a，b，c 百米成绩在第五组的学生数有0.08×1×50＝4，记他们的成绩为m，n，p，q．则从第一、五组中随机取出两个成绩包含的基本事件有{a，b}，{a，c}，{a，m}，{a，n}，{a，p}，{a，q}，{b，c}，{b，m}，{b，n}，{b，p}，{b，q}，{c，m}，{c，n}，{c，p}，{c，q}，{m，n}，{m，p}，{m，q}，{n，p}，{n，q}，{p，q}，共21个其中满足成绩的差的绝对值大于1秒所包含的基本事件有{a，m}，{a，n}，{a，p}，{a，q}，{b，m}，{b，n}，{b，p}，{b，q}，{c，m}，{c，n}，{c，p}，{c，q}，共12个，∴P＝【点评】本题考查样本估计总体，考查古典概型的概率公式，考查频率分布直方图等知识，考查数据处理能力和分析问题、解决问题的能力．10．某校高二年级某班的数学课外活动小组有6名男生，4名女生，从中选出4人参加数学竞赛考试，用X表示其中男生的人数，（1）请列出X的分布列；（2）根据你所列的分布列求选出的4人中至少有3名男生的概率．【分析】（1）本题是一个超几何分步，用X表示其中男生的人数，X可能取的值为0，1，2，3，4．结合变量对应的事件和超几何分布的概率公式，写出变量的分布列和数学期望．（2）选出的4人中至少有3名男生，表示男生有3个人，或者男生有4人，根据第一问做出的概率值，根据互斥事件的概率公式得到结果．【解答】解：（1）依题意得，随机变量X服从超几何分布，随机变量X表示其中男生的人数，X可能取的值为0，1，2，3，4．．∴所以X的分布列为：X01234P（2）由分布列可知至少选3名男生，即P（X≥3）＝P（X＝3）+P（X＝4）＝+＝．【点评】本小题考查离散型随机变量分布列和数学期望，考查超几何分步，考查互斥事件的概率，考查运用概率知识解决实际问题的能力．11．某批产品共10件，已知从该批产品中任取1件，则取到的是次品的概率为P＝0.2．若从该批产品中任意抽取3件，（1）求取出的3件产品中恰好有一件次品的概率；（2）求取出的3件产品中次品的件数X的概率分布列与期望．【分析】设该批产品中次品有x件，由已知，可求次品的件数（1）设取出的3件产品中次品的件数为X，3件产品中恰好有一件次品的概率为；（2）取出的3件产品中次品的件数X可能为0，1，2，求出相应的概率，从而可得概率分布列与期望．【解答】解：设该批产品中次品有x件，由已知，∴x＝2…（2分）（1）设取出的3件产品中次品的件数为X，3件产品中恰好有一件次品的概率为…（4分）（2）∵X可能为0，1，2∴…（10分）∴X的分布为：X012P则…（13分）【点评】本题以实际问题为载体，考查等可能事件的概率，考查随机变量的期望与分布列，难度不大．12．某班组织知识竞赛，已知题目共有10道，随机抽取3道让某人回答，规定至少要答对其中2道才能通过初试，他只能答对其中6道，试求：（1）抽到他能答对题目数的分布列；（2）他能通过初试的概率．【分析】（1）设随机抽出的三道题目某人能答对的道数为X，且X＝0、1、2、3，X服从超几何分布，根据超几何分步的概率公式写出概率和分布列．（2）要答对其中2道才能通过初试，则可以通过初试包括两种情况，即答对两道和答对三道，这两种情况是互斥的，根据上一问的计算可以得到．【解答】解：（1）设随机抽出的三道题目某人能答对的道数为X，且X＝0、1、2、3，X 服从超几何分布，分布列如下：X0123P即X0123P（2）要答对其中2道才能通过初试，则可以通过初试包括两种情况，这两种情况是互斥的，根据上一问的计算可以得到【点评】本题考查超几何分布，本题解题的关键是看出变量符合超几何分布，这样可以利用公式直接写出结果．13．甲有一个箱子，里面放有x个红球，y个白球（x，y≥0，且x+y＝4）；乙有一个箱子，里面放有2个红球，1个白球，1个黄球．现在甲从箱子任取2个球，乙从箱子里再取1个球，若取出的3个球颜色全不相同，则甲获胜．（1）试问甲如何安排箱子里两种颜色的个数，才能使自己获胜的概率最大？（2）在（1）的条件下，求取出的3个球中红球个数的数学期望．【分析】（1）根据甲从箱子任取2个球，乙从箱子里在取1个球，若取出的3个球颜色全不相同，则甲获胜，可得甲获胜的概率，再利用基本不等式，可得x，y的值；（2）由题意知取出的3个球中红球个数ξ的取值为1，2，3，4，分别求出其发生的概率，进而求出次数ξ的数学期望【解答】解：（1）由题意，；∴，当且仅当x＝y＝2时“＝”成立所以当红球与白球各2个时甲获胜的概率最大（2）取出的3个球中红球个数ξ＝0，1，2，3，所以【点评】本题以摸球为素材，考查等可能事件的概率，考查离散型随机变量的期望，考查基本不等式的运用，解题的关键是理解题意，搞清变量的所有取值．14．甲乙两班进行消防安全知识竞赛，每班出3人组成甲乙两支代表队，首轮比赛每人一道必答题，答对则为本队得1分，答错不答都得0分，已知甲队3人每人答对的概率分别为，，，乙队每人答对的概率都是．设每人回答正确与否相互之间没有影响，用ξ表示甲队总得分．（Ⅰ）求随机变量ξ的分布列及其数学期望E（ξ）；（Ⅱ）求在甲队和乙队得分之和为4的条件下，甲队比乙队得分高的概率．【分析】（Ⅰ）由题设知ξ的可能取值为0，1，2，3，分别求出P（ξ＝0），P（ξ＝1），P （ξ＝2），P（ξ＝3），由此能求出随机变量ξ的分布列和数学期望E（ξ）．（Ⅱ）设“甲队和乙队得分之和为4”为事件A，“甲队比乙队得分高”为事件B，分别求出P（A），P（AB），再由P（B/A）＝，能求出结果．【解答】解：（Ⅰ）由题设知ξ的可能取值为0，1，2，3，P（ξ＝0）＝（1﹣）（1﹣）（1﹣）＝，P（ξ＝1）＝（1﹣）（1﹣）+（1﹣）××（1﹣）+（1﹣）（1﹣）×＝，P（ξ＝2）＝++＝，P（ξ＝3）＝＝，∴随机变量ξ的分布列为：ξ01 2 3P数学期望E（ξ）＝0×+1×+2×+3×＝．（Ⅱ）设“甲队和乙队得分之和为4”为事件A，“甲队比乙队得分高”为事件B，则P（A）＝++＝，P（AB）＝＝，P（B|A）＝＝＝．【点评】本题考查离散型随机变量的期分布列和数学期望，考查条件概率的求法，是历年高考的必考题型之一，解题时要注意排列组合知识的合理运用．15．如图，李先生家住H小区，他工作在C科技园区，从家开车到公司上班路上有L1、L2两条路线，L1路线上有A1、A2、A3三个路口，各路口遇到红灯的概率均为；L2路线上有B1、B2两个路口，各路口遇到红灯的概率依次为，．（1）若走L1路线，求最多遇到1次红灯的概率；（2）若走L2路线，求遇到红灯次数X的数学期望；（3）按照“平均遇到红灯次数最少”的要求，请你帮助李先生从上述两条路线中选择一条最好的上班路线，并说明理由．【分析】（1）利用二项分布即可得出；（2）利用相互独立事件的概率计算公式及离散型随机变量的期望计算公式即可得出；（3）由于走路线L1时服从二项分布即可得出期望，比较走两条路的数学期望的大小即可得出要选择的路线．【解答】解：（1）设“走L1路线最多遇到1次红灯”为事件A，包括没有遇到红灯和只遇到红灯一次两种情况．则，所以走L1路线，最多遇到1次红灯的概率为．（2）依题意，X的可能取值为0，1，2．，，．随机变量X的分布列为：X012P所以．（3）设选择L1路线遇到红灯次数为Y，随机变量Y服从二项分布Y～，所以．因为EX＜EY，所以选择L2路线上班最好．【点评】熟练掌握二项分布列、相互独立事件的概率计算公式及离散型随机变量的期望计算公式及其意义是解题的关键．16．某篮球队与其他6支篮球队依次进行6场比赛，每场均决出胜负，设这支篮球队与其他篮球队比赛中获胜的事件是独立的，并且获胜的概率均为．（1）求这支篮球队首次获胜前已经负了两场的概率；（2）求这支篮球队在6场比赛中恰好获胜3场的概率；（3）求这支篮球队在6场比赛中获胜场数的期望．【分析】（1）首次获胜前已经负了两场说明已经比赛三场，前两场输，第三场嬴，用乘法公式即可求得概率；（2）6场比赛中恰好获胜3场的情况有C63，比赛六场胜三场，故用乘法公式即可．（3）由于X服从二项分布，即X～B（6，），由公式即可得出篮球队在6场比赛中获胜场数的期望．【解答】解：（1）这支篮球队首次获胜前已经负了两场的概率为P＝＝（2）6场比赛中恰好获胜3场的情况有C63，故概率为C63×＝20××＝（3）由于X服从二项分布，即X～B（6，），∴EX＝6×＝2【点评】本题考查二项分布与n次独立重复试验的模型，考查根据所给的事件类型选择概率模型的方法，以及用概率模型求概率与期望的能力。

算法———艺术二分图匹配剖析很多人说，算法是一种艺术。

但是对于初学者的我，对算法认识不是很深刻，但偶尔也能感受到他强大的魅力与活力。

这让我追求算法的脚步不能停止。

下面我通过分析匈牙利算法以及常用建图方式，与大家一起欣赏算法的美。

匈牙利算法匈牙利算法是用来解决最大二分图匹配问题的，所谓二分图即“一组点集可以分为两部分，且每部分内各点互不相连，两部分的点之间可以有边”。

所谓最大二分图匹配即”对于二分图的所有边，寻找一个子集，这个子集满足两个条件，1：任意两条边都不依赖于同一个点。

2：让这个子集里的边在满足条件一的情况下尽量多。

首先可以想到的是，我们可以通过搜索，找出所有的这样的满足上面条件的边集，然后从所有的边集中选出边数最多的那个集合，但是我们可以感觉到这个算法的时间复杂度是边数的指数级函数，因此我们有必要寻找更加高效的方法。

目前比较有效的方法有匈牙利算法和通过添加汇点和源点的网络流算法，对于点的个数都在200 到300 之间的数据，我们是采取匈牙利算法的，因为匈牙利算法实现起来要比网络流简单些。

下面具体说说匈牙利算法：介绍匈牙利之前，先说说“增广轨”。

定义：若P是图G中一条连通两个未匹配顶点的路径，并且属最大匹配边集M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广轨定义总是抽象的下面通过图来理解它。

图中的线段（2->3, 3->1, 1->4）便是上面所说的p路径，我们假定边（1,3）是以匹配的边，（2,3）（1,4）是未匹配的边，则边（4,1）边（1,3）和边（3,2）在路径p上交替的出现啦，那么p就是相对于M的一条增广轨，这样我们就可以用边1,4 和边2,3来替换边1,3 那么以匹配的边集数量就可以加1,。

匈牙利算法就是同过不断的寻找增广轨实现的。

很明显如果二分图的两部分点分别为n 和m，那么最大匹配的数目应该小于等于MIN（n,m）; 因此我们可以枚举任第一部分（的二部分也可以）里的每一个点，我们从每个点出发寻找增广轨，最后吧第一部分的点找完以后，就找到了最大匹配的数目，当然我们也可以通过记录找出这些边。

一共有RecuCal.m LockMap.m BuildMatrix.m Edmonds.m GUI1.m 这几个文件，我把它们合到一块粘上去了,你再把他们分开保存就可以了.其中前三个文件都是为建立邻接矩阵服务的，Edmonds.m是匈牙利算法的主文件，GUI1.m只是调用Edmonds.m做个界面而已。

调用关系是GUI1.m调用Edmonds.m；Edmonds.m调用BuildMatrix.m和LockMap.m ；LockMap.m调用RecuCal.m最后运行GUI1.m就ok了#LockMap.mfunction [LMA, LMB] = LockMap(n, m)% LOCKMAP - 求解满足条件锁并设置相应的映射% 输入参数:n 表槽数,m 表高度数。

% 输出参数:LMA,LMB 分别为二维矩阵表示自然数到满足条件锁之间的映射。

global jiA ouB ary A B mm NN = n; mm = m;jiA=0; ouB=0;A=[]; B=[];ary = zeros(1, n);RecuCal(n);LMA=A; LMB=B;[lena, n] = size(LMA);[lenb, n] =size(LMB);if lena>lenbtemp = LMA; LMA=LMB;LMB=temp;temp = lena;lena=lenb;lenb=temp;end#RecuCal.mfunction RecuCal(n)% RECUCAL - 递归函数global jiA ouB ary A B mm Nif n ==1for k=1:mm% 调用递归函数时要用到的变量所以% 设为全局ary(1) = k;Max = max(ary); Min = min(ary);num = 0; neighbor = 0;for i=1:Nnum = num + (Max-ary(i))*(ary(i)-Min);if (i~=N)neighbor = max(neighbor, abs(ary(i)-ary(i+1)));endendif (neighbor > mm-1.5)&&(num > 0.5)if mod(sum(ary), 2)% 奇数,属于 A 类jiA = jiA+1;A(jiA,:) = ary;else% 偶数,属于 B 类ouB = ouB+1;B(ouB,:) = ary;endendendelsefor k=1:mmary(n) = k;RecuCal(n-1);endend#BuildMatrix.mfunction AB = BuildMatrix(LMA, LMB)% BUILDMATRIX - 建立邻接矩阵,若 i 与 j 之间可以互开则 AB(i,j)=1,否则为0。

二分上界(或答案)法的应用前言：在当今的信息学竞赛中，很多题目都令人无从下手，但如果我们先假定出题目的答案，问题就立刻迎刃而解。

下面我们从几道例题谈谈二分答案法的应用。

例题一：草莓(noi2003)题意简述：定义：S"皿表示第/块草莓田中所有草莓重量的和(1< 1< k) Ox = min {sug |1 < j “}你的任务就是要把一片草莓田分割成k块,且分割方案需要满足如下的条件：1•每一块中的草莓必然是通过触须直接或者间接和其他草莓相连接的；2.这种分割方案所对应的x尽可能的大。

最后输出你的分割方案和结果。

算法分析：这是一道结果提交类问题，其中有6个数据都是树，现在我们对树的问题进行讨论。

初一看，这题很难找到有效的模型，关键在于有的时候切出sum很大的一块反而不好，因为题目中需要的是相对平均，因此，纯粹的贪心很难成立。

我们试着稍微改变一下题目，假设题目要求求一种答案不小于x的方法，我们该如何处理呢？很快我们有了头绪，首先通过宽度搜索建树，然后从叶子结点开始向上处理，如果有以某个结点为根的子树的权值和超过了x,我们就将该结点以及它所在的子树作为一个连通块，从图中删去。

这样的做法一定是正确的，因为sum—旦超过了x,如果把更多的结点给这个连通块显然是没有必要的。

一直进行这样的处理，如果割出了k个连通块以上，则问题有解，否则问题无解。

因为只要扫描一遍，因此这个问题的时间复杂度为O(N)o既然我们已经可以在0(N)的时间类解决上述子问题，那么能比较高效地求解原题呢？我们可以枚举每一个x再加以判断，这样复杂度较高。

比较好的方法是采用二分法，假如一个解在某个去间[a, b],首先我们判断(a+b)/2是否可行，如果可行，则枚举[(a+b)/2+l,b],否则枚举[a,(a+b)/2-l]o那么，只需判断logm 次即可(其中m为所有点的权值和)。

如果不知道x,可不可以用上面的方法呢？答案是否定的，因为你不知道剩下部分的情况，所以无法在恰当的时候做出正确的选择。