发信人: micheal (平凡的世界), 信区: Math
标 题: 清华99年研究生组合数学A卷
发信站: 哈工大紫丁香 (Fri Apr 7 15:11:32 2000), 转信
发信站: 南京大学小百合站 (Mon Jan 31 08:31:43 2000), 转信
发信人: wizard (半仙), 信区: e_note
标 题: 99年研究生组合数学A卷
发信站: 酒井BBS (Fri Jan 7 18:34:26 2000), 转信
99年组合数学A卷
1.设序列{ai}、{bj}满足a1<a2<...<am，b1<b2<...<bn，且ai不等于
bj，对i=1,2,...,m，j=1,2,...,n。将{ai}与{bj}归并成{ck}，c1<
c2<...<c(m+n)，算法描述如下：
i<--j<--k<--l
当i<=m且j<=n时做
若ai<bj，
则ck=ai，i=i+1，k=k+1，
否则ck=bj，j=j+1，k=k+1，
若i>m，
则ck=bj，j=j+1，k=k+1，直到j>n
否则j>n
则ck=ai，i=i+1，k=k+1，直到i>m。
设m=20000，n=1000
1）有多少种归并结果？
2）最少要做多少次ai与bj的比较？
3）最多要做多少次ai与bj的比较？
4）平均要做多少次ai与bj的比较？（精确到个位）
2.在平面直角坐标系中
1）证明33个整点中必有9个整点的重心是整点；
2）证明4n-3个整点中必有n个整点的重心是整点，n=（2^a）*（3^b），
a，b是非负整数。
3.把k1个a1，k2个a2，……，kr个ar放在n个不同的盒子里，每个盒子
放入的元素个数不限，有多少种放法？每盒不空，有多少种放法？
4.在正20面体的每个面上任意做一条三角形的高，有多少方案？
5.如图：1表示白地，0为灰格子
111111……11
010101……01
给2*2n的路，用1x1和1x2的砖铺面，灰色格子出不铺留种花，有多
少种方案？在所有的方案中用了多少1x2的砖？
6.用单纯形法解下列线性规划问题：
minz=3x1+x2+2x3,
3x1+2x2+x3 >=9,
4x1+3x2+2x3>=8,
x1 +2x3+3x3>=10,
x1,x2,x3>=0
--
--
※ 修改:．micheal 于 Apr 7 15:15:30 修改本文．[FROM: hitsat.hit.edu.c]