noip的题目、10．将 5 个数的序列排序,不论原先的顺序如何,最少都可以通过（ ）次比较,完成从小到大的排序.A.

noip的题目、
10．将 5 个数的序列排序,不论原先的顺序如何,最少都可以通过（ ）次比较,完成从小到大的排序.
A. 6 B. 7 C. 8 D. 9 E. 10
1．将 2006 个人分成若干不相交的子集,每个子集至少有 3 个人,并且：
（1）在每个子集中,没有人认识该子集的所有人.
（2）同一子集的任何 3 个人中,至少有 2 个人互不认识.
（3）对同一子集中任何 2 个不相识的人,在该子集中恰好只有 1 个人认识这两个人. 则满足上述条件的子集最多能有 个?
我知道答案、有没有解析啊、、菜鸟路过、解析、

5个数通过7次比较排序的方法如下.

5个数之间的大小关系构成的一个树形图T.T中的一个结点代表一个数,而一条边代表它所

关联的两个数的大小关系,T的根就是中位数.显然T中的一条边要由一次比赛来确定.在
下
面的图中,如果x大于y,则节点x在节点y的上方且x和y有一条边相连.另外,*表示一般的

数,o表示下一次即将进行比较的两个数.

第1步,先任取两个数比较,结果为：

*
|
* o o *

第2步,再取另外两个数比较,结果为：

o o
| |
* * *

第3步,按照上图比较其中两个标记为o的数,比较结果只有一种情况：

*
/ \
o *
|
* o

第4步,按照上图比较其中两个标记为o的数,比较结果有两种情况：

o o *
\ / \ / \
* * * *
| / \
* o o

第5步,按照上图比较其中两个标记为o的数,比较结果有两种情况：


* *
| / \
* * o
/ \ |
o o o
| |
* *

第6步,按照上图比较其中两个标记为o的数,比较结果有三种情况：

* * *
| | / \
* * o o
| | \ /
* * *
| / \ |
* o o *
|
*
其中第一种情况已经排好序了
第7步,按照上图比较其中两个标记为o的数,比较结果只有一种情况：

*
|
*
|
*
|
*
|
*

所以只需要7步比较就可以把5个数排好序
第二题
取其中一个满足要求的子集A来分析：
A＝｛a1,a2,a3...an (n>=3)｝
a1,a2,a3中至少有2个人互不认识 ,假设a1和a2不认识!
则：A中必只有一个人am认识a1和a2!
而A中除了am所有的人都不认识a1和a2!
再看看,认识am的人都有谁,显然a1和a2认识!
若还存在一个am1认识am,则：am1不认识a1,不认识a2
所以：A中必定有且只有一个am2认识am1和a1!
而上面我们说到A中除了am所有的人都不认识a1和a2!
所以我们假设的am1不成立!
换言之,认识am的人就只有a1和a2!
假设集合中的另一个元素am3,显然他不认识am,
那么显然根据（3）,集合中必有一个人认识am,和am3
而我们说了认识am的人就只有a1和a2!
所以我们假设的am3不成立!
所以A中只能有3个元素!｛a1,a2,am｝
但是这样的话am就认识了集合中的所有人,不符合（1）
所以这样的子集是不存在的!

为使答案最大（1）考虑子集中有3或四人不满足条件（2）5个人时,设为ABCDE五人,分别用平面内五个点表示,若两点之间有线段相连,表示两人认识,否则表示不认识则,构造图形 （3）因此2006人中可以考虑其中2000人分成400个五人子集,其余6人一个所以最多401
OIERs团队为您解答.