发信人: ssos (存在与虚无·戒酒戒网), 信区: Math
标 题: 清华大学99组合数学考题(转载)
发信站: 哈工大紫丁香 (2001年11月24日19:04:07 星期六), 转信
【 以下文字转载自 Computer 讨论区 】
【 原文由 ssos 所发表 】
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
--
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]
--
※ 转载:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: 天外飞仙]