下载文档原格式
清北学堂信息学竞赛辅导班测试题及答案1清北学堂信息学竞赛辅导班测试题时间：3⼩时2004年7⽉学校：______ 姓名：______注意：最⼤公约数⽤(a,b)表⽰，a除以b的余数⽤a mod b表⽰，计算题要算出最后结果。
⼀、(8分) 编码在书写以下语句时，要注意可能出现哪些错误？如果不会出错，写“⽆”1.1整数加法：______1.2整数减法：______1.3整数乘法：______1.4整数除法：______1.5实数⽐较：______1.6数组元素访问：______1.7指针所指内容访问：______1.8递归调⽤：______⼆、(8分) 算法分析分析以下程序段的时间复杂度。
其中n为输⼊规模，为正整数。
上限应该尽量紧2.1下述代码段时间复杂度：O(__)a := n * n; a = n*n;2.2下述代码段时间复杂度：O(__)for i:=1 to n do j := j + n; for(i=1;i<=n;i++)j+=n;2.3下述代码段时间复杂度：O(__)for i:=n downto 1 do for(i=n;i>=1;i--)for j:=1 to n do for(j=1;j<=n;j++)k := i * j; k=i*j;2.4下述代码段时间复杂度：O(__)for i:=1 to n do for(i=1;i<=n;i++)for j:=i to n do for(j=i;j<=n;j++)k := 1; k=1;2.5下述代码段时间复杂度：O(__)i := n; i=n;while i>0 do i := i div 2; while(i>0)i/=2;2.6调⽤test(1)的时间复杂度为：O(__)function test(a:integer):integer; int test(int a){ if (a>n) return test(a+1)+test(a+1); } beginif(aend;2.7调⽤test(n)的时间复杂度为：O(__)function test(a:integer):integer; int test(int a){var i:integer; for(int i=1;i<=a;i++)c++;begin if (a>1) return test(a+1)+test(a+1); }for i:=1 to a do c := c + 1;if(a>1) test:=test(a div 2)+test(a div 2);end;2.8下述代码段时间复杂度为：O(__)j:=1; j=1;for i:=1 to n do for(i=1;i<=n;i++){ while(j<=n&&a[j]while (j<=n) and (a[j]j++;end;三、(6分) 调试与测试测试某⼀段程序A3.1 经测试，n扩⼤10倍，运⾏时间扩⼤约100倍，则算法的时间复杂度最有可能是____a. O(n)b. O(n2)c. O(nlogn)3.2 这个程序通常可以⽀持n<=____的规模a. 3000b. 10c. 100,0003.3 对于同样的规模，另⼀个程序B⽐它快2秒，能说明A⽐B的渐进时间复杂度⾼吗？a. 可以b. 不可以3.4 程序中有这样⼀条语句：if ok(a) and ok(b) and ok(c) then funA(b) else funB(c);⽤⽩箱测试法让它覆盖完所有条件，需要⾄少取⼏组a,b,c？a. 2组b. 8组c. 6组3.5 跟踪调试发现，语句a[i]:=2; 执⾏完后b[3]突然变成2了，问题的原因是______；a. 算术运算溢出b. I/O错误c. 下标越界3.6 接上题，如果要让Pascal编译器通知此事，应打开编译开关______。
组合导学一、 基础知识点（1）几种特殊的排列1. 圆排列：从n 个不同元素中不重复地取出m （1≤m ≤n ）个元素在一个圆周上，叫做这n 个不同元素的圆排列。
如果一个m-圆排列旋转可以得到另一个m-圆排列，则认为这两个圆排列相同。
2. 可重复排列：从n 个不同元素中取出m 个元素（同一个元素允许重复取出），按照一定的顺序排成一列，叫做n 个不同元素的一个m-可重排列。
定理：n 个不同元素的m-可重复排列数为m n 。
3. 多组组合：将n 个不同元素分成k 组的组合称为n 个不同元素的k-组合 定理：对于n 个不同元素的k ‐组合，若第i 组有i n 个元素，则不同的分组方法有12!!!...!k n n n n 种。
4. 全错位排列：将编号为1,2,…,n 的n 个元素放入编号为1,2,…,n 的n个容器中，要求编号为k 的元素不放入编号为k 的容器中(k=1,2,…,n).定理：对于n 个元素的全错位排列，总共有1111!(1...(1)1!2!3!!n n n −+−++−种排列方式。
（2）分类计数与分步计数原理（3）求解组合问题的递推方法（4）求解组合问题的母函数法（5）求解组合计数问题的子集类法（6）组合恒等式)1(2321021011111=−++−+−=++++⋅==+==−−−−+++−n n n n n n n nn n n n n m r mn m n m n r n r n r n r n r nr n r n nr n C C C C C C C C C C C C C C r n C C C C C C ……证明组合恒等式的方法有: ①等变形，变换求和指标； ②建立递推关系； ③数学归纳法； ④考虑组合意义； ⑤母函数.（7）抽屉原理、极端原理、容斥原理抽屉原理：如果把n+1个元素分成n 个集合，那么不管怎么分，都存在一个集合，其中至少有两个元素。
极端原理：直接抓住全体对象中的极端情形或它们所具有的某种极端性质加以研究、解决问题的思想方法称为极端性原理。
北京清北学堂数学竞赛导学材料几何特训一导学一、几个重要定理：1、梅涅劳斯定理：设',','C B A 分别是ΔABC 的三边BC ，CA ，AB 或其延长线上的点，若',','C B A 三点共线，则.1''''''=⋅⋅BC AC A B CB C A BA '''AC CB BA，C AP 2=AB 2•BC PC +AC 2•BCBP-BP•PC. 6、欧拉定理、欧拉公式：ΔABC 的外心O ，垂心H ，重心G 三点共线，且.21GH OG =设三角形的外接圆半径为R ，内切圆半径为r ，外心与内心的距离为d ，则d 2=R 2－2Rr ． 二、三角形的五心三角形的外心、重心、垂心、内心及旁心，统称为三角形的五心. 1． 重心：三角形的三条中线交于一点。
（1）设G 为△ABC 的重心，连结AG 并延长交BC 于D ，则D 为BC 的中点，且:2:1AG GD =；（2）重心坐标公式：设G 为△ABC 的重心，则(,)33A B C A B Cx x x y y y G ++++（3）设G 为△ABC 的重心，则ABC ACG BCG ABG S S S S ∆∆∆∆===31； （4）设G 为△ABC 的重心，过G 作DE ∥BC 交AB 于D ，交AC 于E ，过G 作PF ∥AC 交AB 于P ，交BC 于F ，过G 作HK ∥AB 交AC 于K ，交BC 于H ，则（2）三角形任一顶点到垂心的距离，等于外心到对边的距离的2倍； （3）垂心H 关于△ABC 的三边的对称点，均在△ABC 的外接圆上；（4）△ABC 的垂心为H ，则△ABC ，△ABH ，△BCH ，△ACH 的外接圆是等圆； （5）设O ，H 分别为△ABC 的外心和垂心，则HCA BCO ABH CBO HAC BAO ∠=∠∠=∠∠=∠,,．（6）由三角形的垂心造成的四个等(外接)圆三角形，给我们解题提供了极大的便利. （7）垂线定理：2222BD BC AD AC CD AB -=-⇔⊥．高线长：C b B c A abcc p b p a p p ah a sin sin sin ))()((2===---=． 3． 内心：三角形的三条角分线的交点—内切圆圆心。
数学竞赛教案讲义(12)——立体几何第十二章立体几何一、基础知识公理1一条直线。
上如果有两个不同的点在平面。
内．则这条直线在这个平面内，记作：aa．公理2两个平面如果有一个公共点，则有且只有一条通过这个点的公共直线，即若P∈α∩β，则存在唯一的直线m，使得α∩β=m,且P∈m。
公理3过不在同一条直线上的三个点有且只有一个平面。
即不共线的三点确定一个平面．推论l直线与直线外一点确定一个平面．推论2两条相交直线确定一个平面．推论3两条平行直线确定一个平面．公理4在空间内，平行于同一直线的两条直线平行．定义1异面直线及成角：不同在任何一个平面内的两条直线叫做异面直线．过空间任意一点分别作两条异面直线的平行线，这两条直线所成的角中，不超过900的角叫做两条异面直线成角．与两条异面直线都垂直相交的直线叫做异面直线的公垂线，公垂线夹在两条异面直线之间的线段长度叫做两条异面直线之间的距离．定义2直线与平面的位置关系有两种；直线在平面内和直线在平面外．直线与平面相交和直线与平面平行(直线与平面没有公共点叫做直线与平面平行)统称直线在平面外．定义3直线与平面垂直：如果直线与平面内的每一条直线都垂直，则直线与这个平面垂直．定理1如果一条直线与平面内的两条相交直线都垂直，则直线与平面垂直．定理2两条直线垂直于同一个平面，则这两条直线平行．定理3若两条平行线中的一条与一个平面垂直，则另一条也和这个平面垂直．定理4平面外一点到平面的垂线段的长度叫做点到平面的距离，若一条直线与平面平行，则直线上每一点到平面的距离都相等，这个距离叫做直线与平面的距离．定义5一条直线与平面相交但不垂直的直线叫做平面的斜线．由斜线上每一点向平面引垂线，垂足叫这个点在平面上的射影．所有这样的射影在一条直线上，这条直线叫做斜线在平面内的射影．斜线与它的射影所成的锐角叫做斜线与平面所成的角．结论1斜线与平面成角是斜线与平面内所有直线成角中最小的角．定理4(三垂线定理)若d为平面。
数学奥赛教练员培训班讲义（1）第一讲 平面几何平面几何是数学竞赛中的一个基本内容。
它以严密的逻辑结构、灵活的证题方法，在发展学生的逻辑思维能力和空间想象能力等方面起着特殊的作用。
因此在数学竞赛中平面几何的内容占有十分突出的地位。
平面几何主要研究度量关系的证明、位置关系的证明、面积关系解题、几何量的计算、轨迹问题等。
一、与三角形有关的重要定理1.梅涅劳斯定理一直线分别截△ABC 的边BC 、CA 、AB （或其延长线）于D 、E 、F ，则1=∙∙FBAF EA CE DC BD 。
说明：（1）结论的图形应考虑直线与三角形三边交点的位置情况，因而本题图形应该有两个。
（2）结论的结构是三角形三边上的6条线段的比，首尾相连，组成一个比值为1的等式。
（3）其逆定理为：如果D 、E 、F 分别在△ABC 的边BC 、CA 、AB （或其延长线上），并且1=∙∙FBAF EA CE DC BD ，那么D 、E 、F 三点在同一条直线上。
（4）梅氏定理及其逆定理不仅可以用来证明点共线问题，而且是解决许多比例线段问题的有力工具。
用梅氏定理求某个比值的关键，在于恰当地选取梅氏三角形和梅氏线。
2.塞瓦定理设O 是△ABC 内任意一点，AO 、BO 、CO 分别交对边于D ，E ，F ，则1=∙∙FBAF EA CE DC BD 。
说明：（1）该定理可借助于梅氏定理来证明（也可用面积法来证明）。
如果O 点在三角形外，结论仍然是成立的。
（2）其逆定理为：分别在△ABC 三边（所在直线）BC 、CA 、AB 上各取一点D 、E 、F ，若有1=∙∙FBAF EA CE DC BD ，则AD 、BE 、CF 平行或共点。
（3）塞瓦定理及其逆定理是证明三直线交于一点（线共点）问题的重要定理，应用塞瓦定理很容易证明三角形中的主要线段的共点问题。
3.三角形的五心三角形的三条中线共点，三条角平分线共点，三条高线共点，三条中垂线共点。
几何---解析几何导学一、基础知识点假设Q 为椭圆上一点，x 轴正方向到射线2F Q 的到角为θ，x 轴正方向到射线1F Q 的到角为ϕ，那么22cos b F Q a c θ=+，21cos b FQ a c ϕ=−，过焦点2F 且倾斜角为α的焦点弦长为2222cos ab a c α−。
注意，这里的焦半径或者焦点弦都对应于不同的焦点，左焦点和右焦点的结果是不一样的。
这个根据倒角（由直线倾斜角直接得到）求焦半径的方法也可以适用于双曲线和抛物线，大家不妨自己推导出类似的结论。
10.圆锥曲线在其上一点的切线方程：椭圆与抛物线22221x y a b ±=在其轨迹上面一点00(,)P x y 处的切线方程为00221x x y ya b±=；抛物线22y px =在其轨迹上面一点00(,)P x y 处的切线方程为00()y y p x x =+14.直线方程问题：（1）直线系方程：假设两条相交直线1l ：111110,(0)A x B y C A B ++=⋅≠与2l ：222220,(0)A x B y C A B ++=⋅≠交于点P ，那么过P 点的直线系方程（不包括）为111222()0A x B y C A x B y C λ+++++=。
（2）直线的到角公式假设直线R 的斜率存在，分别为12,k k ，且不相互垂直，那么1l 到2l 的到角θ满足2112tan 1k k k k θ−=+，1l 与2l 的夹角ϕ满足2112tan ||1k kk k ϕ−=+。
（3）点到直线的距离，平行直线间的距离 点00(,)P x y 到直线0Ax By C ++=的距离为d =15.圆的问题（1）圆的切线方程过圆222()()x a y b r −+−=上一点00(,)P x y 作圆的切线，则切线的方程为200()()()()x a x a y b y b r −−+−−=，事实上，对于任意的二次方程220Ax By Cxy Dx Ey F +++++=，过其上面一点00(,)P x y 作二次曲线的切线，切线方程为0000000222x x y y x x y yAx x By y CD E F ++++++++=。
清北学堂数学高联一试模拟题（1）及答案清北学堂高联一试模拟题(一)答案1、|a+x|-|x+2019|的最大值是|2019-a|≤2a，解得a≥673。
2、2/√53、3i4、22005-1设集合A={1,2,4,8,16,32,64,128,256,512,1024}，B=S\A。
`任取B的一个子集B1，恰有一个A的子集A1，使得B1的元素和与A1的元素和之和是2048的倍数。
于是S满足条件（但不一定是非空真子集）的子集个数等于B的子集个数22005。
去掉一个空集的情况，但是由于全集不满足条件，所以不用去掉，即为所求答案22005-1。
5、2064由容斥原理得到小于2018的完全平方数与完全5次方数共44+4- 1=47个，注意到452=2025,因此a2018=2018+47+1=20646、15/57、31.从1开始逐项递推即可。
8、31.设两个账号的胜率分别是a/b＞c/d，都是最简分数。
那么0.0045≥a/b-c/d=（ad-bc）/bd≥1/bd，所以bd≥1/0.0045>222。
所以b+d≥2√222＞29。
若b+d=30，而bd＞223，所以（b-d）2≤302-223×4=8。
而b与d同奇偶，所以（b，d）=（14,16）或（15,15）此时b与d不互素，这样的话a/b与c/d通分，分母≤bd/2<150，矛盾。
所以b+d≥31。
假设一个账号14局胜9局，另一个17局胜11局，那么两个胜率差就是(154-153)/(14×17)=1/238≈0.420%9.11.设抛物线方程为. , ,三条切线方程为, ,联立解得：, ,故的外接圆方程为：其中是三条切线方程的左边的式子.展开外接圆方程整理得：其中, ,因为该方程表示圆，故.从而，.故外接圆方程为：代入可知成立.故四点共圆.。
清北学堂高联一试模拟题(五)1.已知集合{1,2,3,4,5}A =，{sin tan 0}B x A x x =∈+≥，则集合B 中所有元素之和为_____.2. 已知,a b 是方程3274log 3log (3)3x x +=-的两个根，则a b +=________．3.互不相等的复数a ，b ，c 满足a²(b+c)=b²(a+c)=2018，则c²(a+b )=___________4.掷四个标准骰子一次，最大数和最小数差为5的概率是__________5. 椭圆x 25+y 24=1两焦点分别为F 1,F 2 ,点 A(0,a) 在椭圆内，从A点发出的一束光线经椭圆第一次反射后过F 1, 第二次反射后过F 2,第三次反射后回到A 点，那么a=__________6.函数f ：N +→N+，满足对所有正整数n 都有f(f(n))=3n ，则f(2018)=______________7.已知数列{}n a 满足:122,6a a ==,且2121n nn a a a +++=+.若2n n a λ≥+对一切正整数n 都成立,则λ的最小值为8.已知长方体ABCD-EFGH 的体积是720，则四面体ACFH 和四面体BDEG 的公共部分的体积是___________⑨已知函数1*(),[0,1],n n n f x x x x n +=-∈∈N .（1）求()n f x 的极大值n a ；（2）求n a 的最大值.10.设0,0,0x y z ≥≥≥，且2221x y z ++=，求2f x y z xyz =++-的最大值和最小值.11. 已知内接于抛物线2y x =的梯形ABCD ，其中//AD BC ，AD BC >，M ，N 分别为AD ，BC 的中点，K 是对角线AC ，BD 的交点，且KM m =，KN n =，求梯形ABCD 的面积（用m ，n 表示）。
专题三：数列的概念序：本章注意培养：观察归纳思想、递推思想、等价转化思想、函数思想解决数列问题。
实例引入：①印度国王奖励象棋发明者时，对象棋各格子里放麦粒，各格子里的麦粒数按位置放置的先后排成一列数：234631,2,2,2,2,,2L ②正整数从小到大依次排成一列：1,2,3,4,5,6,L③正整数的倒数排成一列：111111,,,,,,23456L的精确到1,0.1,0.01,0.001,L 的不足近似值排成一列：1,1.4,1.41,1.414,L⑤1-的1次幂、2次幂、3次幂、4次幂、…，排成一列：1,1,1,1,1,1,1,1,----L⑥无穷多个1排成一列：1,1,1,1,1,1,L一、数列的概念1．数列的定义：___________________________________叫做数列。
（这列数可“有限”也可“无限”） 注意：①数列的一列数是有次序性的，注意“数列”与“数集”的区分! ②数列中的项：数列中的每个数。
③数列的项数：数列中项的序号。
如：Ⅰ）234631,2,2,2,2,,2L ； Ⅱ）111111,,,,,,23456L 。
2．函数观点下“数列”的定义：数列实质上可以看做一个定义域为_________________________的函数()f n ，当自变量n 从1开始从小到大依次取正整数值时对应的一列函数值(1),(2),(3),,(),f f f f n L L （或(1),(2),(3),,()f f f f n L ）。
注意：数列视为正整数为自变量的函数值，与普通的函数有区别，它是离散的。
3．①数列的表示：123,,,,,n a a a a L L ，简记为{}n a 。
其中n a 叫数列的第n 项。
如数列：111111,,,,,,23456L ，简记为1n ⎧⎫⎨⎬⎩⎭。
n a ——数列{}n a 的第n 项（通项），n 为项数；{}n a ——数列123,,,,,n a a a a L L 。
中考几何超前目录几何何其妙动物中的数学“天才”蜜蜂蜂房是严格的六角柱状体，它的一端是平整的六角形开口，另一端是封闭的六角菱锥形的底，由三个相同的菱形组成。
组成底盘的菱形的钝角为109度28分，所有的锐角为70度32分，这样既坚固又省料。
蜂房的巢壁厚0.073毫米，误差极小。
丹顶鹤总是成群结队迁飞，而且排成“人”字形。
“人”字形的角度是110度。
更精确地计算还表明“人”字形夹角的一半——即每边与鹤群前进方向的夹角为54度44分8秒！而金刚石结晶体的角度正好也是54度44分8秒！是巧合还是某种大自然的“默契”？蜘蛛结的“八卦”形网，是既复杂又美丽的八角形几何图案，人们即使用直尺的圆规也很难画出像蜘蛛网那样匀称的图案。
冬天，猫睡觉时总是把身体抱成一个球形，这其间也有数学，因为球形使身体的表面积最小，从而散发的热量也最少。
真正的数学“天才”是珊瑚虫。
珊瑚虫在自己的身上记下“日历”，它们每年在自己的体壁上“刻画”出365条斑纹，显然是一天“画”一条。
奇怪的是，古生物学家发现3亿5千万年前的珊瑚虫每年“画”出400幅“水彩画”。
天文学家告诉我们，当时地球一天仅21.9小时，一年不是365天，而是400天。
亲爱的同学们，你们了解身边的几何学吗？答案是中考要考，而且占到整张试卷的50%以上，好吧，我承认它很重要。
那么，现在就让我们一起开始《中考几何学》的学习吧！第一章三角形的证明【本章进步目标】【★★★★★☆】通过对本节课的学习，你能够：1．对全等三角形的基础判定方法，达到初级运用级别【★★★★☆☆】2．对全等三角形的综合判定方法，达到高级运用级别【★★★★★☆】【第一关】全等三角形的基础判定方法----初级运用【★★★★☆☆】【本关进步目标】【★★★★】能够对【关卡1-1】的5道练习题全部解答正确，表明你对全等三角形的基础判定达到【初级运用】级别；【★★★★】能够对【关卡1-2】的4道练习题全部解答正确，表明你对全等三角形的开放性判定判定达到【初级运用】级别；关卡1-1：全等三角形的基本判定方法【★★★★】【过关指南】内容简介：全等的判定学习重点：全等三角形的判定方法；后续关联：三角形综合有关证明【笔记】1、定义法：完全重合的两个三角形是全等三角形。
