第十章排序-例题

第十章综合题1.什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的?2.设待排序的关键字序列为(15, 21, 6, 30, 23, 6′, 20, 17), 试分别写出使用以下排序方法每趟排序后的结果。

并说明做了多少次比较。

(1) 直接插入排序(2) 希尔排序(增量为5,2,1) (3) 起泡排序(4) 快速排序(5) 直接选择排序(6) 锦标赛排序(7) 堆排序(8) 二路归并排序(9) 基数排序3.在起泡排序过程中，什么情况下关键字会朝向与排序相反的方向移动，试举例说明。

在快速排序过程中有这种现象吗？4.快速排序在什么情况下所需关键字的比较次数最多？此时关键字比较次数应为多少？5.用直接插入排序方法对序列(94,32,40,90,80,46,21,69)进行排序（由小到大），试写出排序的过程。

6.已知初始序列为(125 ，11， 22， 34， 15， 44， 76， 66， 100， 8 ，14， 20， 2，5， 1)，写出采用希尔排序算法排序的每一趟的结果（增量为5，3，1）。

7.写出对初始序列(50,72,43,85,75,20,35，45，65，30)进行直接选择排序的过程。

8.若用冒泡排序对关键字序列(18,16,14,12,10,8),进行从小到大的排序，所需进行的关键字比较次数是多少。

9.给出关键字序列(27，18，21，77，26，45，66，34)，试写出快速排序过程。

10.无序序列为(10，2，13，15，12，14)，用堆排序方法从小到大排序，画出堆排序的初态、建堆和重建堆的过程。

11.写出对序列(28，16，32，12，60，2，5，72)进行2路归并排序的过程。

12.给出如下关键字序列(321，156，057，046，028，007，331，033，034，063)，试按链式基数排序方法，列出每一趟分配和收集的过程。

13.若参加锦标赛排序的关键字有11个，为了完成排序，至少需要多少次关键字比较？14.手工跟踪对以下各序列进行堆排序的过程。

第10章排序10.1 知识点分析1．排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。

（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。

（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。

（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。

2．直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。

3．二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。

4．希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。

然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。

5．冒泡排序冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。

每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。

6．快速排序快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。

第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。

第十章排序一、单项选择题1.有一组序列48,36,68,99,75,24,58,52进行快速排序，要求结果按从小到大排序，则进行一次划分之后结果为_____。

A. (24 28 36) 48 (52 68 75 99)B. (28 36 24) 48 (75 99 68 52)C. (36 68 99) 48 (75 24 28 52)D. (28 36 24) 48 (99 75 68 52)2.已知两个有序表，若要将它们组合成一个新的有序表，最好的方法是_____。

A. 希尔排序B. 二分插入排序C. 合并排序D. 冒泡排序3.排序译意风稳定的和不稳定的之分，下列四个说法中，只有______是正确的。

A. 快速排序是稳定的排序方法B. 堆排序是不稳定的排序方法C. 希尔排序是稳定的排序方法D. 冒泡排序是不稳定的排序方法4. 下列排序方法中，____方法是不稳定的。

A. 冒泡排序B. 希尔排序C. 冒泡排序D. 直接插入排序5. 下列排序方法中，在待排序的数据已经有序时，花费时间反而最多的是______。

A.快速排序B. 希尔排序C. 冒泡排序D. 堆排序6. 快速排序方法在最好情况下的时间复杂度为______。

A. O(n)B. O(n2)C. O(nlog2n)D.(log2n)7. 下列排序方法中，时间复杂度不受数据初始状态影响，恒为O(n2)的是_______。

A. 堆排序B.冒泡排序C. 直接选择排序D.快速排序8. 依次将待排序序列中的元素和有序子序列合并为一个新的有序子序列的排序方法是____。

A. 快速排序B.插入排序C. 冒泡排序D. 堆排序9. 在表R中排序前已按键值递增顺序排序，则_____方法的比较次数最少。

A. 直接插入排序B. 快速排序C. 归并排序D. 选择排序10. 已知表A中每个元素距其最终位置不远，采用______方法最节省时间。

A. 堆排序B. 冒泡排序C. 快速排序D. 直接选择排序11. 在下列排序方法中，字比较的次数与记录的初始排列次序无关的是______。

数据结构题第六章树和⼆叉树简答题1、有⼀棵树的括号表⽰为A(B,C(E,F(G)),D),回答下⾯的问题：这棵树的根结点是谁？这棵树的叶⼦结点是什么？结点C的度是多少？这棵树的度是多少？这棵树的深度是多少？结点C的孩⼦结点是哪些？结点C的双亲结点是谁？2、若⼀棵度为4的树中度为1,2,3,4的结点个数分别是4,3,2,2，则该树中叶⼦结点的个数是多少？总结点个数是多少？3、⼀棵⾼度为h的完全k次数，如果按照层次⾃上向下、⾃左向右的顺序从1开始对全部结点编号，试问：最多有多少个结点？最少有多少个结点？编号为q的结点的第i个孩⼦结点的编号是多少？4、若⼀棵⼆叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为结点的总个数为5、⼀棵完全⼆叉树有1001个结点，其中叶⼦结点的个数为6、⼀棵⾼度为h的完全⼆叉树⾄少有个结点。

7、⼀棵⾼度为5的完全⼆叉树⾄多有个结点。

8、设⾼度为h的⼆叉树上只有度为0和度为2的结点，则此类⼆叉树⾄少包含个结点。

9、⼀个具有1025个结点的⼆叉树的⾼度h为10、在⼀棵完全⼆叉树中，结点个数为n，则编号最⼤的分⽀结点的编号为11、⼀棵⼆叉树的先序遍历为ABCDEF，中序遍历为CBAEDF，则后序遍历为12、⼀棵⼆叉树的先序遍历为ABCDEFG，它的中序遍历可能为A.CABDEFGB. ABCDEFGC.DACEFBGD.ADCFEGB思考：⼆叉树的先序和中序遍历相同的条件是？⼆叉树的后序和中序遍历相同的条件是？13、⼀棵⼆叉树的后序遍历为DABEC，中序遍历为DEBAC，则先序遍历为14、⼀棵⼆叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该⼆叉树根结点的右孩⼦为16、根据使⽤频率为5个字符设计的赫夫曼编码不可能的是A.111,110,10,01,00B.000,001,010,011,1C.100,11,10,1,0D.001,000,01,11,1017、根据使⽤频率为5个字符设计的赫夫曼编码不可能的是A. 000,001,010,011,1B.0000,0001,001,01,1C. 000,001,01,10,11D.00,100,101,110,11118、设有13个值，⽤它们组成⼀棵赫夫曼树，则该赫夫曼树共有个结点。

9.1选择题1．从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（）排序法。

A）插入B）选择C）希尔D）二路归并【答案】A2．下面各种排序方法中，最好情况下时间复杂度为O(n)的是（）A）快速排序B）直接插入排序C）堆排序D）归并排序【答案】B3．用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时，无序序列的变化情况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则所采用的排序方法是（）Ａ）选择排序Ｂ）希尔排序Ｃ）归并排序Ｄ）快速排序【答案】Ｄ4．下面给出的四种排序法中，（）排序是不稳定排序法。

A）插入B）冒泡C）二路归并D）堆【答案】D5．快速排序方法在（）情况下最不利于发挥其长处。

Ａ）要排序的数据量太大Ｂ）要排序的数据中含有多个相同值Ｃ）要排序的数据已基本有序Ｄ）要排序的数据个数为奇数【答案】Ｃ6．一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）Ａ）38,40,46,56,79,84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,84,56,79【答案】Ｃ7．对记录的关键码{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：50,26,38,80,70,90 ,8,30,40,2050,8,30,40,20,90,26,38,80,7026,8,30,40,20,80,50,38,90,708,20,26,30,38,40,50,70,80,90其使用的排序方法是（）A）快速排序B）基数排序C）希尔排序D）归并排序【答案】C8．以下序列不是堆的是（）A）100,85,98,77,80,60,82,40,20,10,66B）100,98,85,82,80,77,66,60,40,20,10C）10,20,40,60,66,77,80,82,85,98,100D）100,85,40,77,80,60,66,98,82,10,20【答案】D【解析】根据堆采用完全二叉树的顺序存储形式及堆的特点，因第一个结点即根结点关键字值最大，则应建立一个大根堆，但依据此数据序列建立起堆后关键字值为40的左右孩子结点分别为60、66，不符合大根堆特点。

第十章内部排序一、择题1．用直接插入排序法对下面四个表进行（由小到大）排序，比较次数最少的是（B）。

A．（94，32，40，90，80，46，21，69）插32，比2次插40，比2次插90，比2次插80，比3次插46，比4次插21，比7次插69，比4次B．（21，32，46，40，80，69，90，94）插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次插90，比1次插94，比1次C．（32，40，21，46，69，94，90，80）插40，比1次插21，比3次插46，比1次插69，比1次插94，比1次插90，比2次插80，比3次D．（90，69，80，46，21，32，94，40）插69，比2次插80，比2次插46，比4次插21，比5次插32，比5次插94，比1次插40，比6次2．下列排序方法中，哪一个是稳定的排序方法（BD）。

A．希尔排序B．直接选择排序C．堆排序D．冒泡排序下列3题基于如下代码：for(i=2;i<=n;i++){ x=A[i];j=i-1;while(j>0&&A[j]>x){ A[j+1]=A[j];j--;}A[j+1]=x}3．这一段代码所描述的排序方法称作（A）。

A．插入排序B．冒泡排序C．选择排序D．快速排序4．这一段代码所描述的排序方法的平均执行时间为（D）A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)5．假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B）。

A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)6．在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。

A．左、右两个子表都已各自排好序B．左边子表中的元素都不大于右边子表中的元素C．左边子表的长度小于右边子表的长度D．左、右两个子表中元素的平均值相等7．对n个记录进行堆排序，最坏情况下的执行时间为（C）。

第10章排序（参考答案）部分答案解释如下：18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。

20. 本题为步长为3的一趟希尔排序。

24.枢轴是73。

49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。

64. 因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。

二、判断题5. 错误。

例如冒泡排序是稳定排序，将4,3,2,1按冒泡排序排成升序序列，第一趟变成3,2,1,4，此时3就朝向最终位置的相反方向移动。

12. 错误。

堆是n个元素的序列，可以看作是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。

22. 错误。

待排序序列为正序时，简单插入排序比归并排序快。

三、填空题1. 比较,移动2.生成有序归并段（顺串）,归并3.希尔排序、简单选择排序、快速排序、堆排序等4. 冒泡,快速5. (1)简单选择排序 (2)直接插入排序（最小的元素在最后时）6. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。

7. n(n-1)/28.题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。

(1)!=null (2)p->next (3)r!=null (4)r->data<q->data(5)r->next (6)p->next9. 题中为操作方便，先增加头结点（最后删除），p指向无序区的前一记录，r指向最小值结点的前驱，一趟排序结束，无序区第一个记录与r所指结点的后继交换指针。

(1)q->link!=NULL (2)r!=p (3)p->link (4)p->link=s (5)p=p->link10.(1)i<n-i+1 (2)j<=n-i+1 (3)r[j].key<r[min].key (4)min!=i (5)max==i(6)r[max]<-->r[n-i+1]11.(1)N (2)0 (3)N-1 (4)1 (5)R[P].KEY<R[I].KEY (6)R[P].LINK(7)(N+2)(N-1)/2(8)N-1 (9)0 (10)O(1)(每个记录增加一个字段) (11)稳定（请注意I的步长为-1）12. 3,(10,7,-9,0,47,23,1,8,98,36) 13.快速14.(4,1,3,2,6,5,7)15.最好每次划分能得到两个长度相等的子文件。

《数据结构与算法》第二部分习题精选一、填空题1. 大多数排序算法都有两个基本的操作：和。

2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较次。

(可约定为从后向前比较)3. 在插入和选择排序中，若初始数据基本正序，则选用；若初始数据基本反序，则选用。

4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记录基本无序，则最好选用。

5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。

若对其进行快速排序，在最坏的情况下所需要的时间是。

6. 对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间是。

7．对于n个记录的表进行2路归并排序，整个归并排序需进行趟（遍），共计移动次记录。

二、单项选择题（）1．将5个不同的数据进行排序，至多需要比较次。

Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25（）2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序（）3．排序方法中，从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为Ａ. 希尔排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序（）4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。

Ａ. 从小到大排列好的Ｂ. 从大到小排列好的Ｃ. 元素无序Ｄ. 元素基本有序（）5．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2 （）6．快速排序在下列哪种情况下最易发挥其长处。

Ａ. 被排序的数据中含有多个相同排序码Ｂ. 被排序的数据已基本有序Ｃ. 被排序的数据完全无序Ｄ. 被排序的数据中的最大值和最小值相差悬殊（）7．对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)（）8．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40,38, 46 , 79, 56, 84Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38,46, 84, 56, 79（）9．在最好情况下，下列排序算法中排序算法所需比较关键字次数最少。

排序的练习题数学排序是数学中的一种基本思维方式，它可以帮助我们更好地理清思路、整理信息。

在解决数学问题的过程中，排序的技巧是不可或缺的。

本文将介绍一些排序的练习题，通过实践来提高我们的排序能力。

一、从小到大排序1. 排序整数序列给定一组整数序列：\[2, 7, 5, 3, 1, 9\]，请将它们按照从小到大的顺序进行排序。

解答：\[1, 2, 3, 5, 7, 9\]2. 排序分数序列给定一组分数序列：\[\dfrac{3}{5}, \dfrac{1}{4}, \dfrac{1}{2},\dfrac{2}{3}\]，请将它们按照从小到大的顺序进行排序。

解答：\[\dfrac{1}{4}, \dfrac{2}{3}, \dfrac{1}{2}, \dfrac{3}{5}\]3. 排序小数序列给定一组小数序列：\[0.3, 0.15, 0.8, 0.01\]，请将它们按照从小到大的顺序进行排序。

解答：\[0.01, 0.15, 0.3, 0.8\]二、从大到小排序1. 排序整数序列给定一组整数序列：\[4, 9, 2, 6, 1, 8\]，请将它们按照从大到小的顺序进行排序。

解答：\[9, 8, 6, 4, 2, 1\]2. 排序分数序列给定一组分数序列：\[\dfrac{3}{4}, \dfrac{1}{2}, \dfrac{1}{3},\dfrac{2}{5}\]，请将它们按照从大到小的顺序进行排序。

解答：\[\dfrac{3}{4}, \dfrac{2}{5}, \dfrac{1}{2}, \dfrac{1}{3}\]3. 排序小数序列给定一组小数序列：\[0.8, 0.5, 0.3, 0.01\]，请将它们按照从大到小的顺序进行排序。

解答：\[0.8, 0.5, 0.3, 0.01\]三、多个条件排序有些问题需要根据多个条件进行排序，下面是一些例子。

1. 排序学生信息学生信息包括姓名、年龄和成绩。

一、判断题（第一章绪论）1.数据元素是数据的最小单元。

答案：错误2.一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。

答案：错误3.数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。

答案：正确4.数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。

答案：错误5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算法的时间答案：正确（第二章线性表）6.取顺序存储线性表的第i个元素的时间同i的大小有关。

答案：错误7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

答案：正确8.线性链表的每一个节点都恰好包含一个指针域。

答案：错误9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。

答案：正确10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

答案：错误（第三章栈）11.栈是一种对进栈和出栈作了限制的线性表。

答案：错误12.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN表示栈满。

答案：错误13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。

答案：正确14.空栈就是所有元素都为0上的栈。

答案：错误15.将十进制数转换为二进制数是栈的典型应用之一。

答案：正确（第四章队列）16.队列式限制在两端进行操作的线性表。

答案：正确17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。

答案：错误18.在循环链列队中无溢出现像。

答案：错误19.在循环队列中，若尾指针rear大于头指针front，则元素个数为rear-front。

答案：正确20.顺序队列和循环队列关于队满和队空的判断条件是一样的。

答案：错误（第五章串）21.串是n个字母的有限序列。

答案：错误22.串的堆分配存储是一种动态存储结构。

答案：正确23.串的长度是指串中不同字符的个数。

卜人入州八九几市潮王学校第十章排列、组合、概率§10.1分数计算原理和分步计数原理班级：____________学号：___________一、选择题1.等腰三角形的三边长均为正整数，它的周长不大于10，这样不同形状的三角形的种数为〔D〕2.某银行储蓄卡的密码是一个4位数码，某人采用千位、百位上的数之积作为十位、个位上的数字〔如2816〕的方法设计密码，当积为1位数时，十位上数字选0，千位、百位上都能取0，这样设计出来的密码一共有〔C〕A.90个B.99个C.100个D.112个3.一植物园参观途径如下列图，假设要全部参观并且道路不重复，那么不同的参观道路种数一共有〔D〕A、B、C、D、E、F六人依次站在正六边形的六个顶点上传球，从A开场，每次可随意传给相邻的两人之一，假设在5次之内传到D，那么停顿传球；假设5次内传不到D，那么传完5次也停顿传球，那么从开场到停顿，可能出现的不同传法种数是〔B〕A.24B.26C.28D.305.对于任意两个正整数，定义某种运算m，n 〔运算符号用#表示〕；当m,n都为正偶数或者正奇数时，m#n=m+n；当m，n中一个为正奇数，另一个为正偶数时，m#n=mn，那么在上述定义下，M={(a,b)|a#b=36,a∈N*,b∈N*}集合中元素个数为〔B〕A.40B.416.把单位正方体的六个面分别染上6种颜色，并画上只数不同的玉狗，各面的颜色与玉狗的只数对应如表.取同样的4个上述的单位正方体，拼成一个如下列图的程度放置的长方体，那么这个长方体的下底面总计一共画有玉狗的个数为〔C 〕A.15B.16选择题答题卡二、填空题7.在一块并排10垄的田地中，选择2垄分别种植A ，B 两种作物.每种作物一垄.为有利作物生长，要求A ，B 两种作物的间隔不小于6垄，那么不同的选垄方法有_____种〔用数字答题〕.128.一排一共9个座位，甲、乙、丙三人按如下方式入座：每人左右两旁都有空座位，且甲必须在乙、丙两人之间，那么不同的坐法一共有________种〔用数字答题〕.209.从集合{0，1，2，3，5，7，11}中任取3个元素分别作为直线方程Ax +By +C =0中的A 、B 、C ，所得经过坐标原点的直线有_______条.〔结果用数值表示〕3010.某的地号码为84a 1a 2a 3a 4a 5，其中a i ∈{0，1，2，…，9}〔i =1，2，3，4，5〕，假设a 4a 5与a 1a 2或者a 2a 3的数字及排序完全一样，那么称此号码为“好号〞，该地“好号〞的个数和为____________.1990三、解答题11.王华同学有课外参考书假设干本，其中有5本不同的外语书，4本不同的数学书，3本不同的物理书，他欲带参考书到图书馆阅读. 〔1〕假设他从这些参考书中带一本去图书馆，有多少种不同的带法？〔2〕假设带外语、数学、物理参考书各一本，有多少种不同的带法？〔3〕假设从这些参考书中选2本不同学科的参考书带到图书馆，有多少种不同的带法？ 答案：〔1〕12种 〔2〕60种〔3〕47种12.计算机编程人员在编写好程序以后需要对程序进展测试.程序员需要知道到底有多少条执行途径〔即程序从开场到完毕的道路〕，以便知道需要提供多少个测试数据.一般的，一个程序由许多模块组成，如以下列图所示，它是一个具有许多执行途径的程序模块.问：〔1〕这个程序模块有多少条执行途径？〔2〕为了减少测试时间是，程序员需要设法减少测试次数.你能帮助程序员设计一个测试方法，以减少测试次数吗？答案：〔1〕7371条〔2〕在实验试验中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块.这样，他先分别单独测试5个模块，总一共需要的测试总数为18＋45＋28＋38＋43＝172〔次〕.而整个模块只要测试3×2=6〔次〕.这样，测试整个模块的次数就变为172+6＝178〔次〕.显然，178与7371的差距是非常大的.§10.2排列组合的根本问题一中：丁评虎班级：____________学号：___________一、选择题1.在1，2，3，4，5这五个数字所组成的没有重复数字的三位数中，其各个数字之和为9的三位数一共有〔C〕A.6个B.9个C.12个D.18个2.紫光农科院培植的茄子、西红柿、南瓜、黄瓜4个转基因果蔬参加新品种展销会，在布展时，分两层摆放，每层2个，其中茄子和西红柿要放在不同的层架上，那么不同的摆放方式有〔C〕A.4种B.8种C.16种D.32种3.从4名男生和3名女生中选出4人参加某个座谈会，假设这4人中必须既有男生又有女生，那么不的选法一共有〔D〕A.40种B.120种C.35种D.34种4.将标号为1，2……，10的10个球放入标号为1，2，……，10的10个盒子内，每个盒内放一个球，那么恰好有3个球的标号与其所在盒子的标号不一致的放入方法种数为〔B〕A.120B.240C.360D.720A、B、C、D、E、F6位同学站成一排照相，要求同学A、B相邻，C、D不相邻，这样的排队照相方式有〔D〕A.36种B.48种C.42种D.144种6.某外商方案在4个候选城HY3个不同的工程，且在同一个城HY的工程不超过2个，那么该外商不同的HY方案有〔D〕A.16种B.36种C.42种D.60种选择题答题卡二、填空题7.计算1！+2！+3！+…a、b、c、d、e、f中选出四种，分别种在四块不同的土壤A、B、C、D中进展试验，已有资料说明：A土壤不宜种a，B土壤宜种b，但a、b两品种高产，现a、b必种的试验方案有______种.849.如下列图，在排成4×4方阵的16个点，中心4个点在某一圆内，其余12个点在圆外，在16个点中任选3个点构成三角形.其中至少有一个顶点在圆内的三角形一共有_____个.〔用数字答题〕312三、解答题11.用数字0，1，2，3，4，5组成没有重复数字的四位数.〔1〕可组成多少个不同的四位数？〔2〕可组成多少个不同的四位偶数？〔3〕可组成多少个能被3整除的四位数？答案：〔1〕300个〔2〕156个〔3〕96个12.有11名外语翻译人员，一共中5名会英语，4名会日语，另外两名英、日语都精通，从中选出8人，组成两个翻译小组，其中4人翻译英语，另4人翻译日语，问一共有多少种不同的选派方式？§10．3排列组合的综合问题一中：丁评虎班级：___________学号：___________一、选择题021年德国世界杯足球赛一共有32个队参赛，比赛前抽签分成8个小组，每小组4个队，各个组都进展单循环赛〔即每队都要与本小组其他各队比赛一场〕，然后由各小组积分多的两个队出线组成十六强.规定：在小组赛中，胜一场积3分，平一场积1分，负一场积0分〔积分一样取净胜球数或者进球总数多的队，假设再一样，根据其他规定，每小组总可排出前两名〕.假设甲、乙两队分别在两个小组赛中各积5分和2分，那么以下判断正确的选项是〔B〕A.甲队一定出线，乙队不可能出线B.甲队不一定出线，乙队有可能出线C.甲队不一定出线，乙队不可能出线D.甲队一定出线，乙队有可能出线2.设有编号为1，2，3，4，5的五个茶杯和编号为1，2，3，4，5的五个茶杯盖，将五个杯盖盖在五个茶杯上，至少有2个杯盖和茶杯的编号一样的方法有〔B〕A.30种B.31种C.32种D.48种3.要用四种颜色给、、HY、四〔区〕的地区上色，每一〔区〕一种颜色，只要求相邻的〔区〕不同色，那么上色方法有〔C〕A.24种B.32种C.48种D.64种4.书架上的一格内有排好顺序的6本书，假设保持这6本书的相对顺序不变，再放上3本书，那么不同的放法一共有〔C〕A.210种B.252种C.504种D.505种5.将数字1，2，3，4，5，6排成一列，记第i 个数为a i(i=1,2,…,6)，假设a1≠1,a3≠3,a5≠5,a1＜a3＜a5，那么不同的排列方法种数为〔A 〕A.18B.30C.36D.486.某通讯公司推出一组卡号码，卡号的前七位数字固定，从“×××××××0000”到“××××××9999”一共10000个号码，公司规定；凡卡号的后四位带有数字“4”或者“7〞的一律作为“优惠卡〞，那么这组号码中“优惠卡〞的个数为〔C〕A.2000B.4096C.5904D.8320选择题答题卡题号 1 2 3 4 5 6 答案二、填空题7.马路上有编号为1，2，3，……8.某校从8名老师中选派4名老师同时去4个遥远地区支教〔每地1人〕，其中甲和乙不同去，甲和丙只能同去或者同不去，那么不同的选派方案一共有__________种.〔用数字答题〕600 ABCDEF为正六边形，一只青蛙开场在顶点A 处，它每次可随意地跳到相邻两顶点之一，假设在5次之内跳到D点，那么停顿跳动；假设5次之内不能到达D10.安排去某班一天中语文、数学、政治、英语、体育、艺术6门课各一节的课程表，要求数学课排在前3节，英语课排在第6节，那么不同的排法种数为___288___.〔以数字答题〕三、解答题100件产品中有5件次品，如今从中任意抽取4件，按以下条件，各有多少种不同的抽法〔只要求列式〕：〔1〕抽出的都不是次品；〔2〕抽出的至少有1件次品；〔3〕抽出的不都是次品.12.有4个不同的球，四个不同的盒子，把球全部放入盒内.〔1〕一共有多少种放法？〔2〕恰有一个盒子不放球，有多少种放法？〔3〕恰有一个盒内有2个球，有多少种放法？〔4〕恰有两个盒内不放球，有多少种放法？§10．4二项式定理 一中：丁评虎班级：____________学号：___________一、选择题1．在(ax -1)7展开式中含x 4项的系数为-35，那么a 为〔A 〕 A.±1 B.-1C.-21D.±212．在〔1+x 〕5+(1+x )6+(1+x )7的展开式中，x 4系数是通项公式为a n =3n-5的数列的〔A 〕 A.第20项 B.第18项 C.第11项D.第3项3．设n x x )5(-的展开式的各项系数之和为M ，二项式系数之和为N ，M -N =240，那么展开式中x 3项的系数为〔C 〕 A.500 B.-500 C.150 D.-1504．假设nxx )21(2-的展开式中只有第4项的二项式系数最大，那么展开式中的所有项的系数之和是〔D 〕 A.0B.256 C.64D.641 5．对于二项式N*)()1(3∈+n x xn ，有四个判断：①存在*N ∈n ，展开式中有常数项；②对任意*N ∈n ，展开式中没有常数项；③对任意*N ∈n ，展开式中没有x 的一次项；④存在*N ∈n ，展开式中有x 的一次项.上述判断中正确的选项是〔D 〕A.①③B.②③C.②④D.①④ 6．将〔3)2||1||-+x x 展开，其中值为常数的各项之和等于〔C 〕 A.-8B.-12C.-20D.20选择题答题卡二、填空题 7．假设nxx )21(-展开式中含x 2项系数绝对值与含x 4项的系数绝对值相等，那么n8．〔x 2-2x +3〕n =a 0+a 1x +a 2x 2+… +a 2n -1·x2n -1+a 2n ·x 2n，那么〔1〕a 1+a 2+a 3+…+a 2n -1+a 2n =_____23n n -_ 〔2〕a 0+a 2+a 4+…+a 2n -2+a 2n =____262n n+__9．假设A =7254366773333C C C +⋅+⋅+，1634527773331B C C C =⋅+⋅++，那么A -B10．假设n 为奇数，那么112217777nn n n nnnC C C ---+⋅+⋅+⋅⋅⋅+⋅三、解答题11．(1+2x )n的展开式中的第6项和第7项系数相等，求展开式中二项式系数最大的项及展开式系数是中最大的项. 答案：二项式系数最大的项为451120T x = 展开式系数最大的项为6T 5=1792x ，671792T x =12．设数列{}n a 是等比数列，Acm m m a 123321-+⋅=，公比是42)41(xx +的展开式中的第二项〔按x 的降幂排列〕.〔1〕用n 、x 表示通项a n 与前n 项和S n ； 〔2〕假设nnn nnn SS S A c cc+⋅⋅⋅++=2211，答案：用n ,x 表示A n〔1〕1n n a x -=，当x=1，n S n =，当1x ≠时,11n n x S x-=-〔2〕12(1)2(1)(1)1n nn n n x A x x x-⎧⋅=⎪=⎨-+≠⎪-⎩ §10.5随机事件的概率一中：丁评虎班级：____________学号：___________一、选择题1．给出关于满足A ∈B 的非空集A 、B ①假设任取x ∈A ，那么x ∈B 是必然事件； ②假设任取xA ，那么x ∈B 是不可能事件； ③假设任取xB ，那么xA 是随机事件. ④假设任取xB ，那么xA 是必然事件. 〕 A.1个B.2个C.3个D.4个2．现有男生成人，女生4人，将他们任意排成一排，左边4人全是女生的概率是〔A 〕 A.701B.351C.16801D.352 3．将某城分为4个区，如下列图.需要绘制一幅城分区地图，现有红、黄、绿、紫、蓝5种不同颜色，图中①②③④每区只涂一色，且相邻两区必须涂不同的颜色〔不相邻两区所涂颜色不限〕，①被涂成红色的概率是〔A 〕 A.51B.2401 C.52 D.534．停车场可把12辆车停放一排，当有8辆车已停放后，那么所剩4个空位恰连在一起的概率为〔C 〕 A.c8127B.c8128C.c8129D.c812105．有一个奇数列1，3，5，7，9，……如今进展如下分组，第一组有1个数为1，第2组有2个数为3、5，第三组有3个数为7、9、11，……依此类推，那么从第十组中随机抽取一个数恰为3的倍数的概率为〔B 〕 A.101 B.103 C.51 D.53 6．将7个人〔含甲、乙〕分成三个组，一组3人，另两组各2人，不同的分组数为a ，甲、乙分在同一组的概率为p ,那么a 、p 的值分别为〔A 〕 A.215,105==p a B.214,105==p a C.215,210==p aD.214,210==p a 选择题答题卡二、填空题个人排成一排，甲、乙二人都不排在首位和末位的概率是___________.3108．在一次老师联欢会上，到会的女老师比男老师多12人，从这些老师中随机挑选一人表演节目，假设选到男老师的概率为209 9．六位身高全不一样的同学拍照纪念，摄影师要求前后两排各三人，那么后排每人均比前排同学高的概率是____________.1810．在正方体上任选3个顶点连成三角形，那么所得的三角形是直角非等腰三角形的概率为______.37三、解答题11．从0、2、4、6、8这五个数中任取2个，从1、3、5、7、9这五个数字中任取1个. 〔1〕问能组成多少个没有重复数字的三位数？〔2〕求在〔1〕中的这些三位数中任取一个三位数恰好能被5整除的概率.答案：〔1〕260个 〔2〕146512．盒中装有8个乒乓球，其中6个是没有用过的，2个是用过的.〔1〕从盒中任取2个球使用，求恰好取出1个用过的球的概率；〔2〕假设从盒中任取2个球使用，用完后装回盒中，求此时盒中恰好有4个是用过的球的概率.答案：〔1〕37〔2〕1528§10．6互斥事件有一个发生的概率一中：丁评虎班级：____________学号：___________一、选择题1．盒中有10只螺丝钉，其中有3只是坏的，现从盒中随机地抽取4只螺丝钉，那么103等于〔C〕A.恰有1只是坏的的概率B.4只全是好的的概率C.恰有2只是好的的概率D.至多2只是坏的的概率2．笔盒中有12支钢笔，其中一等品8支，二等品4支，从中取出2支，那么恰有1支一等品的概率为〔D 〕 A.334 B.338 C.339 D.33163．6名学生中，3人能独唱，5人能跳舞，从6名学生中随机选取3人，那么选取的3名同学能排演一个由1人独唱，2人伴舞的节目的概率为〔D 〕 A.54B.52C.109 D.2019 4．一辆班车送职工下班，有10个站，车上有30个人，假设某站无人下车，那么班车在此站不停，那么班车停车次数不少于2次的概率为〔A 〕 A.291011-B.291030C.30301091-D.30301095．袋中有大小一样的4只红球和6只白球，随机地从袋中取出1只球，取出后不放回，那么恰好在第5次取完红球的概率为〔B 〕A.2101 B.1052 C.212D.2186．从0到9这10个数字中任取3个数字组成一个没有重复数字的三位数，这个数不能被3整除的概率为〔B 〕 A.5419 B.5435 C.5438 D.6041 选择题答题卡题号 1 2 3 4 5 6 答案二、填空题7．某班委会由4名男生与3名女生组成，现从中选出2人担任正、副班长，其中至少有1名女生中选的概率是___________〔用分数答题〕.578．口袋内装有10个一样的球，其中5个球标有数字0，5个球标有数字1，假设从袋中摸出5个球，那么摸出的5个球所标数字之和小于2或者大于3的概率是__________.〔以数值答题〕136310．有10个外表一样的圆球，其中8个各重a 克，2个各重b克〔a≠b〕，从这10个圆球中任取3个放在天平一端的盘中，再从剩余的7个中任取3个放在天平另一盘中，那么天平平衡的概率为___________.1 3三、解答题11．系统M是由6条网线并联而成的，且这6条网线能通过的信息量个数分别为1，1，2，2，3，3.在关闭所有网线的情况下，再任意接通其中三条网线.〔1〕求系统M恰好通过8个信息量的概率；〔2〕假设通过的信息量低于6个，系统M 就不能保证畅通，试求系统M畅通的概率.答案：〔1〕1 10〔2〕71012．甲、乙两上排球队进展比赛，每局甲获胜的概率为0.6，比赛是采用五局三胜制.〔保存三位有效数字〕〔1〕在前两局乙队以2：0领先的条件下，求最后甲、乙队各自获胜的概率；〔2〕求甲队获胜的概率.答案：〔1〕甲获胜的概率为0.216，乙获胜的概率为0.784；〔2〕甲队获胜的概率为0.683。