中国科学技术大学入学考试 数学

中科大自主招生试题数学中科大自主招生数学试题通常会涵盖广泛的数学知识点，旨在考察学生的数学思维能力、创新能力以及解决实际问题的能力。

以下是一道典型的中科大自主招生数学试题，将会对题目进行详细的解析。

题目：设函数f(x)在区间[a, b]上连续，存在唯一的最大值点x0，最大值为M，即f(x0) = M，且f'(x0) = 0。

若对于任意的x∈[a, b]，f(x)满足下列不等式：f(x) ≤ f(a) + 3(x-a)^2 - 5(x-a)^31.证明函数f(x)在区间[a, b]上是减函数。

2.求f(x)在区间[a, b]上的最大值。

解析：1.首先，我们证明函数f(x)在区间[a, b]上是减函数。

根据题目中的条件，可以得到f'(x0) = 0，即函数在最大值点处的导数为零。

由于导数的定义，导数为零意味着函数在该点处的变化率为零，也就是说函数在该点处是取得极值的可能性最大的地方。

由于函数在最大值点处是取得极值，使得函数在最大值点两侧的变化率相反。

根据函数的凹凸性质，我们可以得出在最大值点左侧的函数是递增的，在最大值点右侧的函数是递减的。

而对于任意的x∈[a, b]，我们都满足条件f(x) ≤ f(a) + 3(x-a)^2 - 5(x-a)^3。

可以发现右侧的式子是一个关于(x-a)的二次减三次函数，也就是说它是一个开口向下的函数图像，这意味着对于任意的x∈[a, b]，都有f(x)的值要小于该函数值，因此函数f(x)在区间[a, b]上是减函数。

2.接下来，我们来求解f(x)在区间[a, b]上的最大值。

根据题目中的条件，我们已经知道函数f(x)的最大值点为x0，最大值为M。

通过导数的定义，我们知道x0是f(x)的临界点，即f'(x0) = 0。

由于函数在最大值点处的导数为零，因此可以推断出函数在最大值点左侧是递增的，在最大值点右侧是递减的。

所以我们只需要找到函数f(x)在区间[a, b]上的临界点即可求得最大值。

2016年中国科学技术大学自主招生数学试题解答王慧兴;王雪芹【期刊名称】《高中数理化》【年(卷),期】2017(000)007【总页数】3页(P20-22)【作者】王慧兴;王雪芹【作者单位】清华大学附属中学;北京师范大学第二附属中学【正文语种】中文从中科大这份自主招生试题看,我们得出以下4点结论: 1) 著名高校自主招生要求考生数学视野开阔,不局限于高考(考试大纲、考试说明),但不超过现行课标设定的知识与能力要求(只是当下常态教学搞全面应试教育,不以课标要求开展教学,譬如按课标编写的《初等数论》、《图论》等等,由于高考不考就不学); 2) 著名高校自主招生命题刻意追求与高考互补,也就是说高考刚刚考过的常态题型不再考查,坚持在课标范围内与高考形成互补; 3) 著名高校自主招生命题更突出对考生能力的考查,继续坚持(不回避)对过往竞赛试题推陈出新,譬如第1、2、3、6、7题在早些年全国高中数学联赛等试题中都有原型,第4题是三角形中的常态问题,另外第5题源于2007年全国高中数学联赛试题2,第8题源于2005年全国高中数学联赛试题加试3,第9题源于国外数学竞赛试题,第10题源于2010年国际数学奥林匹克(IMO)试题3,第11题源于2005年中国数学奥林匹克(CMO)试题6; 4) 对有志赢得更多机会的优秀学子,应把功夫放在平常,及早按课标要求,在常态学习中同时积淀与高考互补的内容,在高考之后登上才智展示的舞台. 以上都是笔者研究高校自主招生试题得出的经验,这些经验已写入笔者著作《自主招生数学备考十二讲》中．下面与读者分享这份精彩思维体操.例1 32 016除以100的余数是________.因为所以340≡1(mod100),从而32016≡316(mod100).再用二进制计算如下：3≡3(mod100),32≡9(mod100),34≡-19(mod100),38≡61(mod100),316≡612=3 721≡21(mod100),综上所述,32 016≡21(mod100).应用欧拉定理可以给出满足3a≡1 (mod 100)的一个正整数a，也可以经枚举发现周期性找出一个这样的正整数.譬如：3a≡1 (mod 100)等价于因为{3n} (mod 22):3,1,3,1,…,所以a是偶数.记a=2b (b∈N*),代入3a≡1 (mod 52),得9b≡1 (mod 52)，必有9b≡1 (mod 5)，但{9n} (mod 5):4,1,4,1,…,所以b=2c (c∈N*),代回9b≡1 (mod 52)，得81c≡1 (mod 52)，但{81n} (mod 25):6,11,16,21,1,…,所以c是5的倍数，记c=5k (k∈N*),从而a=20k,这样得到一个更小的a=20.当然，本题也可应用二项式定理求解例2 复数z1、z2满足|z1|=2,|z2|=3,|z1+z2|=4,则________.由|z1+z2|=4,得即亦即因为Δ=9-9×16=-9×15,所以,方程有2个共轭虚根i.本题灵活应用共轭与模的性质给出解答,也可走代数形式求解途径.由得所以即).由可得故亦即所以i.例3 用S(A)表示集合A的元素和,A⊂{1,2,3,4,5,6,7,8}且S(A)是3的倍数,但不是5的倍数,则集合A的个数是________.先把集合{1,2,3,4,5,6,7,8}中的8个元素按照同余作划分.按模3同余划分:{1,4,7}∪{2,5,8}∪{3,6}.若A≠{1,2,3,4,5,6,7,8},故满足S(A)是3的倍数的真子集A的个数是但其中和数是15的13个子集{8,7}、{8,6,1}、{8,5,2}、{8,4,3}、{8,4,2,1}、{7,6,2}、{7,5,3}、{7,5,2,1}、{7,4,3,1}、{6,5,4}、{6,5,3,1}、{6,4,3,2}、{5,4,3,2,1}以及和数是30的4个子集{4,5,6,7,8}、{2,3,4,6,7,8}、{1,3,5,6,7,8}、{1,2,3,4,5,7,8}这17个子集应当去掉,所以满足题设的真子集A的个数是83-17=66.本题检测组合计数基本技能,常态的问题是单一分组设计,如“求集合{1,2,…,100}的元素之和是3的倍数的三元子集个数”就是一个常态的练习题,求解的关键是按摸3的余数作划分{1,2,…,100}={1,4,7,…,100}∪{2,5,8,…,98}∪{3,6,…,99},再按目标合理分类与分步组合计数得例4 在△ABC中,sin A+2sin Bcos C=0,则tan A的最大值是________.记BC=a,AC=b,AB=c,由正弦定理和余弦定理,得即c2=2a2+b2.再由余弦定理,得当b=c时取“=”.从而故此时).本题检测基于正弦定理和余弦定理探求三角形中最值问题能力,但考生容易囿于三角变换，陷入怪圈,因此,试题设计体现知识自觉调用、检测目标意识.例5 若对任意实数x,都有|2x-a|+|3x-2a|≥a2,则实数a的取值范围是________.由绝对值不等式,得到综上并且当时取到“=”,即所以题设恒成立条件转化为即故实数a的取值范围是].本题检测应用绝对值不等式求最值的基本技能.上述解法带参数求最值，也可换元去掉参数. 首先a=0满足题设,以下设a≠0,换元x=ay,则恒成立条件化为|2y-1|+|3y-2|≥|a|.由在时取“=”,所以故综上所述例6 设则x=(sin a)logbsin a与y=(cos a)logbcos a的大小关系是____.logbx=(logbsin a)2,logby=(logbcos b)2，因为故再由0<b<1可知f(x)=logbx 是减函数,所以f(cos a)>f(sin a)>0,即logbcos a>logbsin a>0,从而(logbcos a)2>(logbsin a)2>0.综上所述,0<logbx<logby,所以1>x>y>0.例7 在梯形ABCD中,AD∥BC,且AC与BD交于点P1,作P1Q1∥AD交CD于Q1,连接AQ1交BD于P2,作P2Q2∥AD交CD于Q2,依此类推,设AD=a,BC=b,则PnQn=________.先算初值, 由所以由此,可得递推公式即由等差数列通项公式,得故).本题检测平面几何中比例计算基本技能,这里给出建构递推数列求解,也可以利用归纳推理、猜想、证明.例8 设an是与最接近的整数,则________.任取n∈N*,存在k∈N*与i∈{0,1,2,…,2k},使n=k2+i,则k.按题设定义,得an=k的充要条件是即亦即i∈{0,1,2,…,k},所以记则因为442<2016<452,所以本题检测基于“换序”更换和式求值的组合能力.例9 设a,b,c>0,且a+b+c=3,求证证明由柯西不等式,得目标转化为证把条件a+b+c=3代入,即得亦即已知成立,故命题得证.本题检测应用柯西不等式推证分式型不等式的基本技能,柯西不等式是证明多元不等式与求多元极值的重要工具.例10 求所有函数f:N*→N*,使得对任意互异正整数x、y,都有0<|f(x)-f(y)|<2|x-y|. 按题意,f(x)≠f(y),∀x、y∈N*(x≠y),即f:N*→N*是单射.任取n∈N*,都有0<|f(n+1)-f(n)|<2,但f(n)、f(n+1)∈N*,所以f(n+1)-f(n)=±1.情形1: 若f(n+1)-f(n)=1 (n∈N*),则任取n∈N*,都有记c=f(1)-1,则f(n)=n+c(n∈N*),其中常数c∈N.经验证,这是满足题设条件的函数. 情形2: 若f(n+1)-f(n)=-1 (n∈N*),则任取n∈N*,都有但无论如何定义正整数f(1),都不能使所有f(n)∈N*,故此情形不存在满足题设的函数f(x).情形3: f(n+1)-f(n)=±1(n∈N*),且则必存在k∈N*(k>1)使得,f(k)=f(k-1)-1,而f(k+1)=f(k)+1,所以f(k+1)=f(k-1),这与f:N*→N*是单射矛盾,故此种情形不存在满足题设的函数f(x).综上所述,满足题设的函数f:N*→N*所有解是f(n)=n+c(n∈N*),其中常数c∈N.本题检测对单射的深刻理解与应用、分类讨论能力与极端性思维能力.例11 求方程2x-5y·7z=1的所有非负整数解(x,y,z).假设y≠0,若y≥1，必有x≥3,方程两边模5，得2x≡1(mod 5).因为{2n} (mod 5):2,4,3,1,…,所以4|x,从而5y·7z=2x-1≡0 (mod 3),矛盾.所以y=0,原方程即2x-7z=1.当x≤3时，解得(x,z)=(1,0),(3,1);当x≥4时，有7,1≡7z=2x-1≡0 (mod 16),矛盾.综上所述,方程共有2个解(x,y,z)=(1,0,0)、(3,0,1).本题检测应用同余性质求解不定方程基本技能,属初等数论典型内容.。

2023考研中国科学技术大学自主命题考研真题348文博综合业务课名称：348文博综合
考生须知：1.答案必须写在答题纸上，写在其他纸上无效。

2.答题时必须使用蓝、黑色墨水笔或圆珠笔做答，用其他答题不给分，不得使用涂改液。

一、名词解释(每题10 分，选10 题作答，共100 分)
1、金属文物
2、质文物
3、石质文物
4、媒染法
5、狼毒纸
6、范铸法
7、失蜡法
8、胶黏剂
9、植物纤维
10、文物的时代性
11、文物的多样性
12、文物的史料作用
二、简答题(每题20分，选5题作答，共100分)
1、文物的教育作用体现在哪些方面
2、文物保护与修复基本原理
3、造纸的主要原料
4、造的工艺流程
5、石质文物的生物病害
6、壁画文物的
三、论述题(每题50分，选2题作答，共100分)
1、根据“十四五”文物保护和科技创新规划，谈谈你对“让文物活起来的认识
2、如何传承和发展传统民俗
3、谈谈我国考古学的现状和发展。

2020年安徽省合肥市中国科大创新班初试数学试卷一、填空题1．若z+＝1，则|z+1|﹣|z﹣i|取值范围是 ．2．若|5x+6y|+|9x+11y|≤1，则满足条件的点（x，y）组成的面积为 ．3．函数f（x）＝+所表示的曲线离心率为 ．4．若a1＝1，a2＝3，a n＝2+a n﹣1，求a n＝ ．5．若x2﹣y2＝4p2，其中x，y∈Z+，p为素数，则x3﹣y3＝ ．6．已知a＝20202020，b＝，c＝，则a，b，c 大小顺序 ．7．已知f（x）＝（x﹣1）2+k2，且∀a，b，c∈（0，1），都存在以f（a），f（b），f（c）为边的三角形，则k的取值范围为 ．8．设a1，a2，…，a n为1，2，…，n的一个排列，若i＜j且a i＜a j，则称（a i，a j）为有序对子，设X为a1，a2，…，a n有序对子的个数，则E（X）＝ ．9．求函数f（x）＝3sin2x﹣2sin2x+2sin x﹣cos x，x∈[0，]的值域 ．10．已知f（x）＝x3+ax2﹣x+1﹣a（a∈R），若∀x∈[﹣1，1]，使得|f（x）|≥|x|恒成立，则a 取值范围为 ．11．已知1++……+＜C（n+1），证明：当C＝，不等式成立，且C＜该不等式不成立．2020年安徽省合肥市中国科大创新班初试数学试卷参考答案与试题解析一、填空题1．若z+＝1，则|z+1|﹣|z﹣i|取值范围是　（﹣1，]．　．【考点】复数的模．【分析】由题意设z＝，则|z+1|﹣|z﹣i|＝，再由其几何意义，即平面内一动点A（0，b）到两定点B（，0），C（，1）距离之差求解．【解答】解：由题意设z＝，则|z+1|﹣|z﹣i|＝，其几何意义为平面内一动点A（0，b）到两定点B（，0），C（，1）距离之差，由图可知，当A，B，C三点共线时，距离之差最大，当b→﹣∞时，最小，则0﹣1＝﹣1＜|z+1|﹣|z﹣i|≤．∴|z+1|﹣|z﹣i|的取值范围是（﹣1，]．故答案为：（﹣1，]．【点评】本题考查复数的代数表示法及其几何意义，考查复数模的求法，考查数形结合的解题思想方法，是中档题．2．若|5x+6y|+|9x+11y|≤1，则满足条件的点（x，y）组成的面积为　2　．【考点】简单线性规划．【分析】依题意，将原不等式转化为不等式组，作出可行域，进而求得所求面积．【解答】解：|5x+6y|+|9x+11y|≤1等价于或或或，作出对应的可行域如下图所示，易知平面区域为平行四边形，其面积为．故答案为：2．【点评】本题考查简单的线性规划问题，涉及了平行四边形的面积以及点到直线的距离公式，两点间的距离公式等知识点，属于中档题．3．函数f（x）＝+所表示的曲线离心率为 ．【考点】双曲线的性质．【分析】由坐标轴的旋转变换公式，代入函数f（x）的解析式，化简消去x'y'项，求得θ，可得曲线的标准方程，求得a，b，c，e，计算可得所求值．【解答】解：由坐标轴的旋转变换公式，代入y＝+即x2﹣xy＝﹣，可得x'2cos2θ+y'2sin2θ﹣2x'y'sinθcosθ﹣（x'2sinθcosθ﹣y'2sinθcosθ+x'y'cos2θ﹣x'y'sin2θ）＝﹣，化为x'2（cos2θ﹣sinθcosθ）+y'2（sin2θ+sinθcosθ）﹣x'y'（2sinθcosθ+cos2θ﹣sin2θ）＝﹣，为了得到曲线的标准方程，可令2sinθcosθ+cos2θ﹣sin2θ）＝0，即sin2θ+cos2θ＝0，即tan2θ＝﹣，可取θ＝60°，则曲线的标准方程为﹣＝1，则a2＝2，b2＝，c2＝，e2＝＝，即e＝．故答案为：．【点评】本题考查函数表示的曲线的离心率的求法，运用坐标轴的旋转变换是解题的关键，考查化简运算能力，属于中档题．4．若a1＝1，a2＝3，a n＝2+a n﹣1，求a n＝ ．【考点】数列递推式．【分析】先把已知式子变形为，再累乘即可得a n．【解答】解：由题意可知．于是，所以，当n≥2时有，．当n＝1时也满足上式．故答案为：．【点评】本题考查累乘法求数列通项，正确的将题干所给式子进行变形是解题的关键，属于中档题．5．若x2﹣y2＝4p2，其中x，y∈Z+，p为素数，则x3﹣y3＝　6p4+2　．【考点】有理数指数幂及根式．【分析】x2﹣y2＝4p2＝（2p）2＝（x﹣y）（x+y）其中x，y∈Z+，p为素数，由x，y∈Z+，可得x﹣y，x+y都为奇数或都为偶数．而4p2为偶数，因此（x﹣y）与（x+y）都为偶数．对p，x分类讨论即可得出结论．【解答】解：∵x2﹣y2＝4p2＝（2p）2＝（x﹣y）（x+y）其中x，y∈Z+，p为素数，由x，y∈Z+，可得x﹣y，x+y都为奇数或都为偶数．而4p2为偶数，因此（x﹣y）与（x+y）都为偶数．①若p＝2，则x﹣y＝2，x+y＝8，x＝5，y＝3，∴x3﹣y3＝98．②若p＞2，则p为奇数．∴（x﹣y）（x+y）＝2×2p2．∴x﹣y＝2，x+y＝2p2．设y＝2k+1（k∈Z+），则x＝2k+3，可得：2k+2＝p2，矛盾，因此不成立，舍去．设y＝2k（k∈Z+），则x＝2k+2，可得：2k+1＝p2，∴x＝p2+1，y＝p2﹣1．于是x3﹣y3＝（p2+1）3﹣（p2﹣1）3＝6p4+2．上式对于p＝2时也成立．综上可得：x3﹣y3＝6p4+2．故答案为：6p4+2．【点评】本题考查了整数的性质、素数的性质、分类讨论方法，考查了推理能力与计算能力，属于中档题．6．已知a＝20202020，b＝，c＝，则a，b，c 大小顺序　c＞a＞b　．【考点】不等关系与不等式．【分析】利用基本不等式即可比较出b，c的大小关系；利用不等式的性质即可比较b，a的大小关系；利用即可比较c与a的大小关系．【解答】解：，＝，，∴c＞a＞b．故答案为：c＞a＞b．【点评】本题考查实数的大小比较，属于中档题．7．已知f（x）＝（x﹣1）2+k2，且∀a，b，c∈（0，1），都存在以f（a），f（b），f（c）为边的三角形，则k的取值范围为　（﹣∞﹣1]∪[1，+∞）　．【考点】二次函数的性质与图象．【分析】利用二次函数图象的对称性，三角形的边角性质，两边之和大于第三边解出本题答案．【解答】解：函数f（x）在（0，1）单调递减，由∀a，b，c∈（0，1），都存在已f（a），f（b），f（c）为边的三角形可得，f（0）≤2f（1）即k2≥1，所以k≤﹣1或k≥1．故答案为（﹣∞，﹣1]，或[1，+∞）．【点评】本题考查了二次函数图象的性质，三角形两边之和大于第三边．8．设a1，a2，…，a n为1，2，…，n的一个排列，若i＜j且a i＜a j，则称（a i，a j）为有序对子，设X为a1，a2，…，a n有序对子的个数，则E（X）＝ ．【考点】离散型随机变量的期望与方差．【分析】对于排列A：a 1，a2，…，a n，构造一个排列A1：a n，…，a2，a1，求出x A与的平均值为：＝，对于任意一个排列A都可以构造一个排列A1，由此能求出E（X）．【解答】解：对于排列A：a1，a2，…，a n，构造一个排列A1：a n，…，a2，a1，此时，＝，∴x A与的平均值为：＝，而对于任意一个排列A都可以构造一个排列A1，∴E（X）＝＝．故答案为：．【点评】本题考查离散型随机变量的数学期望的求法，考查平均值、倒序相加求和法等基础知识，考查运算求解能力，是中档题．9．求函数f（x）＝3sin2x﹣2sin2x+2sin x﹣cos x，x∈[0，]的值域　[﹣，5]　．【考点】三角函数的最值．【分析】利用换元法把函数f（x）表示为t的二次函数，然后根据t的取值范围求得函数的值域．【解答】解：设t＝2sin x﹣cos x＝sin（x﹣θ），x∈[0，]，tanθ＝且θ∈（0，），∵x∈[0，]，∴x﹣θ∈[﹣θ，﹣θ]，∴sin（x﹣θ）∈[﹣sinθ，sin（﹣θ）]＝[﹣，]，∴t∈[﹣1，2]，又t2＝4sin2x+cos2x﹣4sin x cos x＝3sin2x+1﹣2sin2x，∴y＝f（x）＝t2+t﹣1，t∈[﹣1，2]，∴﹣≤y≤5，即f（x）的值域为[﹣，5]．故答案为：[﹣，5]．【点评】本题主要考查换元法、二次函数在处理函数值域中的应用，属于中档题．10．已知f（x）＝x3+ax2﹣x+1﹣a（a∈R），若∀x∈[﹣1，1]，使得|f（x）|≥|x|恒成立，则a 取值范围为 ．【考点】函数恒成立问题．【分析】先考虑x＝0时，易知a∈R；当x≠0 时，将|f（x）|≥|x|转化为，令，x∈[﹣1，0）∪（0，1]，利用导数研究函数φ（x）的最值求解即可．【解答】解：情形一：当x＝0 时，易知a∈R；情形二：当x≠0 时，此时|f（x）|＞|x|等价于，令，则，令，则，令u（x）＝x3+3x+1，易知u（x）单调递增，且u（0）＝1，u（﹣1）＝﹣3＜0，由零点存在性定理可知：必有一个x0∈（﹣1，0），使得u（x0）＝0，此时x∈（﹣1，x0），h′（x）＞0，h（x）单调递增，x∈（x0，0），h′（x）＜0，h（x）单调递减，x∈（0，1），h′（x）＞0，h（x）单调递增，①当a⩾1 时，此时h（0）＝a﹣1＞0，则x∈（0，1），φ′（x）＞0，φ（x）单调递增，此时，φ（x）＜φ（1）＝1，不满足题意，②当时，此时由零点存在性定理可知：必有一个x1∈（0，1），使得h（x1）＝0，此时x∈（x1，1），φ′（x）＞0，φ（x）单调递增，此时φ（x）＜φ（1）＝1，不满足题意，③当时，此时，则φ′（x）＜0，此时x∈（﹣1，0），φ（x）单调递减，则φ（x）＜φ（﹣1）＝﹣1，满足题意，同理可得x∈（0，1），φ（x）单调递减，φ（x）＞φ（1）＝1，满足题意，综上所述，a取值范围为．【点评】本题考查利用导数研究函数的单调性、最值，考查不等式恒成立的处理，考查学生的转化能力和运算能力，属于难题．11．已知1++……+＜C（n+1），证明：当C＝，不等式成立，且C＜该不等式不成立．【考点】综合法与分析法(选修）．【分析】先证明当C＝，不等式成立．利用分析法证明；再再证当C＜时，该不等式不成立．利用数列的极限证明．【解答】解：先证明当C＝，不等式成立．要证，只需证，只需证，根据积分的定义易得，令，其在（0，+∞）上为增函数，则原函数，依据积分法，有f（n）＜F（n+1）﹣F（n），所以，命题得证．再证当C＜时，该不等式不成立．因为，又，所以当时，不满足题意．【点评】本题考查分析法证明数列不等式，考查数列的极限，考查转化思想和极限思想，属于难题．。

中国科学技术大学2022年特殊类型（创新班）招生考试数学A 真题及答案解析注意事项：1.答卷前，考试务必将自己的姓名、准考证填写在答题卡上。

2.将答案写在答题卡上，写在本试卷上无效。

3.考试结束后，将本试卷和答题卡一并交回。

4.本试卷共5题，每题20分，共100分。

需要写出必要的计算和证明过程。

一、求满足2022a b c ++=且2022abc 可被整除的正整数集合{},,a b c 个数。

二、求满足如下条件的所有函数()f x ；（1）定义域为1122⎡⎤-⎢⎥⎣⎦，；（2）(0)0f =；（3）1sin ()sin ()33xf x f x -=恒成立。

三、欧拉有著名公式22221111++++=236n π ，求最小正整数n ，使得2211162022nk k π=>-∑。

四、在圆周上独立地随机选取n 个点，求这n 个点可以被半圆周覆盖的概率。

五、设2*()()1,,2!!nn x x f x x n N x R n -=-++∈∈ 。

（1）证明：：方程21()0n f x -=有唯一实数解，记作n a 。

（2）数列{}n a 是否为单调数列?请证明你的结论。

答案解析一、解：337322022⨯⨯=，又c b a ,,不可能为3个奇数，故只考虑3和337两个因子即可；若存在c b a ≠=，则有20222=+c a ，若c 337，则a 337，设11337337a a c c ==，，则6211=+c a ，11,c a 不可能为3的倍数；因此c b a ,,互不相等，由对称性，不妨设c 337：（1）337=c ，1685=+b a ，共56131685=⎥⎦⎤⎢⎣⎡种（2）574=c ，1348=+b a ，共44931348=⎥⎦⎤⎢⎣⎡种（3）1011=c ，1011=+b a ，此时b a ,必有一偶数，恒成立，共505种（4）1348=c ，674=+b a ，共2243674=⎥⎦⎤⎢⎣⎡种（5）1685=c ，337=+b a ，共1123337=⎥⎦⎤⎢⎣⎡种注意到{}1011,674,337在计算过程中重复了2次，故：总计561+449+505+224+112-2=1849种.分析：本题为基础数论题，难度不大，但是需要一定的耐心和细心.二、解：令()()()x x g x g x f x g =⎪⎭⎫ ⎝⎛-=331sin ，，则有()⎥⎦⎤⎢⎣⎡⋅-⎪⎭⎫ ⎝⎛=-38933189x x g x x g ()⎥⎦⎤⎢⎣⎡⎪⎭⎫ ⎝⎛⋅-⎪⎭⎫ ⎝⎛=-n n n xx g x x g 38933189，又∞→n lim 0389331=⎥⎦⎤⎢⎣⎡⎪⎭⎫ ⎝⎛⋅-⎪⎭⎫ ⎝⎛n n n xx g 故有当⎦⎤⎝⎛⋃⎪⎭⎫⎢⎣⎡-∈21,00,21x 时，()x x g 89=，()πk x x f 289arcsin +=()Z k ∈，当0=x 时，()0=x g ，()0=x f .三、解：即求202211111121212122<=-=-∑∑∑∑+∞+==+∞==n k n k k n k k k k k b π即有()()111112-<<+k k k k k ，可得()n k k k n k n k 1111112=-<∑∑+∞+=+∞+=.因此，当2022=n 时，20221120232<∑+∞=k k 成立.而当2021≤n 时，()2022111111112≥+=+>∑∑+∞+=+∞+=n k k k n k n k 不成立综上2022min =n .四、解：n 个点分别记做i A ，过i A 和圆心做直线交圆于i B ，最终选取的n 个点记做i C ，其中n i ,,2,1 =，且{}i i i B A C ,∈.故共有n2种选择，且需要保证i C 均在一个半圆弧上，则当且仅当i C 为i A ，i B 这n 2个点种相邻的n 个点，即n 2种情况.又这n 个点同时包含一组i A ，i B 的概率为0，结论具有一般性.因此有：1222-==n n nn P .五、解：（1）()()()11111=-=-='+a x x f x f x f n n ，，()()x f x f 12-='，故()()0122=>f x f 不妨设()x f k 12-在R 上单调递减，且()012=-x f k 有实根k a ，且()02>x f k 恒成立，则()()0212<-='-x f x f k k 恒成立，且()012=+x f k ，()0lim 12>++∞→x f k x .因此()+∞∈∃+,01k a 使得()0112=++k k a f .()()x f x f k k 1222++-='，即有()()()()()0!2222111212222>+-+=>+++++++k a a f a f x f k k k k k k k 其中()0112=++k k a f ，证毕.综上，()x f n 12-在实数域上递减且有唯一实根.（2）()()()()()⎪⎭⎫⎝⎛+-=+-+=+-+121!2!12!221221212n a n a n a n a a f a f n nn n n n n n n n n ()()()()()()()0212!1222332212212<---+--+-=-n n n n n n n a f n n ！又()x f n 12-递减，故n a n 2<证毕()()1112120+-++<=>n n n n n n a a a f a f ，综上，{}n a 为单调递增数列.。

中国科学技术大学一九九五年招收硕士学位研究生入学考试试题试题名称:程序设计一、选择题1.一颗深度为6的平衡二叉树,其每个非终端节点的平衡因子均为1,则该树共有_____个节点.(2分)a) 14; b) 16; c) 18; d) 20; e) 22; f) 242.一个有28条边的非连通无向图,至少应有____个节点.(2分)a) 6; b) 7; c) 8; d) 9; e) 10; f) 113.一颗124个叶节点的完全二叉树,最多有___个节点.(2分)a) 247; b) 248; c) 249; d) 250; e) 2514.按锦标赛排序的方法,决定出8位运动员之间的名次顺序排列,至少需编排____场次的比赛.(考虑最坏情况) (2分)a) 13; b) 14; c) 15; d) 16; e) 175.已知Head(Tail([Head(S),Head(Tail(Tail(S)))]))=[a] ,广义表S满足上式,则S为______.(其中,方括号表示广义表,圆括号表示函数,如[a,b]表示由a,b构成的广义表,而Head()表示取广义表的头部.) (2分)a) [[a,b],b,a] b) [[b,a],[a],[b]]c) [[a],[a,b],[b]] d) [b,[a],[a,b]]e) [[a],[b],[b,a]] f) [[b],[b,a],[a]]6.在下列三种次序的线索二叉树中,___对查找指定节点在该次序下的后继效果较差. (2分)a) 前序线索树b) 中序线索树c) 后序线索树7.有二叉树的前序和后序遍历序列唯一的确定这颗二叉树. (2分)a) 能b) 不能8.在下列两种求图的最小生成树的算法中,___算法适合于求边稀疏的网的最小生成树. (2分)a) Prim; b) Kruskal9.下列无向图的存储结构中,在对无向图的边进行操作时(如删除一条边)____存储结构更为合适a) 邻接表b) 邻接多重表10.在下述几中树中,___可以表示静态查找表. (2分)a) 次优查找树; b) 二叉排序树;c) B- 树d) 平衡二叉树11.答案写在填空的字母后面(1)在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是A(2)快速排序在最坏情况下,时间复杂度是B ,比C 的性能差(3)就平均时间而言, D 最佳(共4分)A: a) 直接插入排序; b) 起泡排序; c) 简单选择排序;B: a) O(n log n); b) O(2n); c) O(3n)C: a) 堆排序; b) 起泡排序; c) 选择排序D: a) 堆排序; b) 快速排序; c) 归并排序12.一程序规定的职能是:“输入三个整数作为三边的边长构成三角形,判别是等腰三角形,等边三角形,或是一般三角形,再做计算…….”.若用等价类划分方法对该程序做功能测试,至少应对该程序的输入数据考虑 A 个等价类,其中包括 B 个有效等价和C 个无效等价类.A,B,C: (答案写在填空的字母后面)(1) 3; (2) 5; (3) 7; (4) 12; (5) 15; (6) 18; (7) 21; (8) 25 (9) 33; (10) 4013.二叉树如图所示（1）给出先序遍历的节点的顺序;_________（2）给出中序遍历的节点的顺序;_________（3）给出后序遍历的节点的顺序;_________（4）用二叉链表作为存储结构,将出现多少个空指针(nil)域?_____(共4分)14.下列函数(6分)function calc(x,y:integer) : integer;beginif y=1 then calc := xelse calc := calc ( x, y-1 ) + xend;a,b 均为正整数,则calc (a,b) = ______1) a*(b-1); 2) a*b; 3) a + b 4) a+a15.程序段read (a,b);c := 3.0 * a + b;if c=0 then a := 1else a := 1.0 + 1.0 / c + 1.0 / b保证该程序段运行不出错的必要条件是:_______. (4分)（1) b>0 （2) a>0 and b>0（3) b≠0 （4) b≠0 and c≠0二、程序改错与填空1.指出下列程序段中的错误位置,对错误编号,说明理由:程序段一: (8分)label 1;const max=50;type day = { Mon , Tue, Wed, Thu, Fri, Sat, Sun};var date:day;N:integer;begina: N:=N-ord('0');b: for date :=Mon to Sundo N := ord(succ(date)) – 1;c: for n := 1 to 10do begin……1: 语句;end;……goto 1;……end.答: ____________________________________________________________________________程序段二. (8分)program type(input,output);var R:real;procedure print(var x:integer, y:real);var z:real;procedure sum(x:integer, y:real);var k:real;beginz:= x+y; k:= 3*z;x:= x+y;end; {sum}beginsum(x,y);writeln(x,y,z,k)end; {print}begin {主程序}readln(R);print(15,R);print(R,R)end.答: ___________________________________________________________________________________________.2.阅读下列程序,填空使之成为一个完整的程序.该程序输出N个元素的全排列.例如N=3时,程序输出为:1 2 32 1 33 2 12 3 11 3 23 1 2 (12分)程序:program pic(input,output);const n=10;var A:array[1..n] of integer;i,k:integer;procedure output1;beginfor i := 1 to n do write(A[i]:3);writeln;end; {output1}procedure permute(k:integer);var i,t:integer;beginif k=1 then output1else begin____________;for i:=1 to ________do begin___________t:=A[k];A[k]:=A[i];A[i]:=t;_________;t:=_______;A[k]:=______;___________;end {for}end {else}end; { permute }begink:=n;for i:=1 to k do A[i]:=i;permute(k)end.三、编程题: (语言可任选,要求思路清晰,书写工整)1.编写程序将一个循环队列的内容倒置,该循环队列存储在一个数组A[1..n]中,例如图a中为倒置前的队列,图b中为倒置后的队列.要求倒置后的队列从数组的第一个元素开始存储,整个程序的运行时间为O(n). (15分)2.设计一个程序,使输入的句子按如下方式改造之后输出:（1）单词之间只留一个空格做间隔;（2）句子结束后必须紧跟句号;（3）如果把句子的单词从左到右依次编号为1,2,3,…则对于第奇数个单词,只要直接复制就行了,而对于第偶数个单词,应按反序打印.(15分)例如: 输入句子是:thissi yllis中国科学技术大学一九九六年招收硕士学位研究生入学考试试题试题名称:程序设计一、单项选择: (20分)1.具有几个节点的完全二叉树的深度是:_____.1) n log 2 2) n log 2 + 1 3) 1)(n log 2+ 4) n log 2 – 12.用单循环链表表示队列,正确的说法是:______1) 可设一个头指针使入队、出队都方便2) 可设一个尾指针使入队、出队都方便3) 必须设头、尾指针才能使入队、出队都方便;4) 无论如何,只可能使入队方便.3.对无向图而言,同一条边在邻接表中用两个节点表示而在邻接多重表中只用一个节点表示,因此邻接多重表所需存储量比邻接表______.1) 少一半 2) 多,但差异不大 3) 少,但差异不大4.一个哈希函数被认为是“好的”,如果它满足条件________.1) 哈希地址分布均匀 2) 保证不产生冲突3) 所有哈希地址在表长范围内 4) 满足 2) 和 3)5.ISAM 文件和VSAM 文件属于___________.1) 索引非顺序文件 2) 索引顺序文件3) 顺序文件 4) 散列文件6.在下述排序算法中_____算法是稳定的排序算法.1) 希尔排序 2) 冒泡排序 3) 快速排序7.平衡二叉树中,若某个节点在左、右子节点的平衡因子为零,则该节点的平衡因子也一定是零,这种说法______.1) 不正确 2) 正确8.在下属三种排序算法中,所需辅助存储量最多的是_____,所需存储量最少的是_______,平均速度最快的是______.1) 堆排序 2) 快速排序 3) 归并排序二、问答题(25分)1.已知某电文中共出现10种不同的字母,各个字母出现的频率分别为A:8, B:5, C:3, D:2, E:7, F:23, G:9, H:15, I:3, J:35 ,现在对这段电文用三进制进行编码(即码字由0,1,2组成),问电文编码总长度最少有多少位?并画出图2.A 是一个三对角矩阵,行数与列数相等,用压缩存储的方法将其压缩存储到一维的数组SA[ 1 .. 3n – 2 ]中(按行序顺序存储),则SA[ k ]对应的矩阵元素的下标为: 行值 i = ________, 列值 j = _______.反过来,若知道A 中元素的下标i , j ,则其存储位置 k=________.(写出表达式)3.设A 是一个栈,栈中共有n 各元素,依次为: n 21a ,,a ,a L ,栈顶元素为n a ,B 是一个循环队列,队列中n 各元素依次为n 21b ,,b ,b L ,队头元素为1b , A 、B 均采用顺序存储结构且存储空间足够大,现要将栈中元素全部移到队列中,使得队列中元素与栈中元素交替排列,即B 中元素为n n 332211a ,b ,,a ,b ,a ,b ,a ,b L ,问至少需要多少次基本操作才能完成上述工作,请写出具体步骤(要求除A、B外所用的其他附加存储量为1,每次出栈、入栈、出队列、入队列均看作一次基本操作).4.试为下列二叉树建立后序线索,画出相应的后序线索二叉树.三、算法描述(15分)以二叉链表作存储结构,编写按层次顺序(从根节点开始)遍历二叉树的算法.四、阅读下列程序,并回答:下列程序是否正确?为什么?如何修改? (5分)var a,b,c,d,e,f:integer;procedure mult(var x,y,z:integer);beginz:=0;while x<>0 dobeginif odd(x) thenz:=z+y;y:=y*z;z:=x div 2 ;end;end;begina:=5; b:=7; d:=11; e:=13;mult(a,b,c); /* 要求输出c=15 */mult(d – b , e – a , f ); /* 要求输出f=32 */end.五、阅读下列程序说明和C程序,把应填处的字句,写在答卷的对应栏内.[程序说明]对于正整数n,输出其和等于n且满足以下限制条件的所有正整数的和式,即组成和式的数字自左至右构成一个非递增的序列.如n = 4 , 程序输出为4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 + 14 = 1 + 1 + 1 + 1程序中给出了分别采用递归和非递归解法的两个函数rd() 和nd() .函数rd() 采用递归解法,它有两个参数 a 和k . 其意义分别是被分解和式的数n ,及当前第k 深度分解.算法思想是对n 的所有合理的和式分解,将分解出的数(称为和数) 存于数组a[ ]中.当其中一个分解已不再需要进一步分解时,即找到一个解,将存于数组a[ ] 中的一个完整和式的和数输出.当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用分解和式函数.函数nd() 以要分解的数为参数,另开设一个数组r[ ],用于存储当前还未分解的余数.在求一个解的第k步时,a[k]为第k个和数,r[k]为相应的余数.当找到一个分解后(此步r[k]等于0,给出解,并做回溯处理,从当前k退回到第一个不为1的和数,将其减1,并将其余数加1,准备去找另一个解;否则,生成下一步的分解和数与余数.(15分)答: 1) ________________ 2) _________________3) ________________ 4) _________________5) ________________ 6) _________________[程序]#define MAXN 100int a[MAXN], r[MAXN];rd(int n, int k){ int j,i;for( j= ①; j >= 1 ; j –– ){if ({ printf("%d = %d",a[0],a[1]);for ( i = 2; i <= k; i ++ )printf(" + %d",a[i]);printf("\n");else ;}}nd(int n){ int i,k;k=0; r[0]=n;do{ if ( ){ %d",a[0],a[1]);for ( i=2; i <= k; i + +)printf(" + %d",a[i]);printf("\n");while ( k > 0 && ) k –– ;if ( k > 0){ a[k]}else { a[k+1] =k + +;} /* else */} while ( k > 0 );}int test_data[] = { 3, 4, 5 };main(){ int i;for ( i=0; i < sizeof test_data/sizeof (int) ; i ++){ a[0] = test_data[i];rd(test_data[i],1);printf("\n___________________\n\n");nd(test_data[i]);printf("\n___________________\n\n");}}六、设计一个程序读入一个字符串,统计该字符串中出现的字符及其次数,然后仪表的形式输出结果.要求用一个二叉树来保存处理结果,字符串中的每个不同的字符用数中不同的节点描述,每个节点包含四个域,格式为:字符该字符的出现次数指向ASCII码小于该字符的左子树指针指向ASCII码小于该字符的右子树指针因此程序的功能是依次从输入字符串中取出一个字符,把它们插入到树中(新出现字符)或修改原树中相应节点的“出现次数”域(已出现字符). (20分)中国科学技术大学一九九七年招收硕士研究生入学考试试题试题名称：程序设计一、选择填空（每空1分，共10分）1.查找几个元素的有序表时，最有效的查找方法是______.a: 数序查找; b:分块查找; c:二分查找; d:二叉排序树2.对一般二叉树而言,求节点按某种序列的前趋节点变得容易的线索二叉树是___和____.a: 前序线索二叉树; b: 中序线索二叉树; c: 后序线索二叉树3.若一个有向图具有拓扑排序序列,那么它的邻接矩阵必定为____.a: 对称矩阵; b: 稀疏矩阵; c: 三角矩阵; d: 一般矩阵4.采用开址定址法解决冲突的哈希查找中,发生集聚的原因主要是____.a: 数据元素过多; b: 负载因子过大; c: 哈希函数选择不当;d: 解决冲突的算法选择不好.5.对n个关键字的文件进行内部排序,在最好情况下,最快的排序方法是____;相应的时间复杂度为_____;该算法的稳定性是_______.A: ①快速排序; ②插入排序; ③归并排序; ④选择排序log n); ④O(n㏑n)B: ①O(2n); ②O(n); ③O(n 2C: ①稳定; ②不稳定6.在K路平衡归并的外部排序中,如果内部选择算法采用堆排序,则总的排序时间与K______.a: 有关; b: 无关7.哈夫曼编码树是一种_____.a: 最优查找树; b: 最优二叉树; c: 平衡二叉树d: B+树二、填空(每空2分,共20分)1.已知一颗二叉树的前序序列和中序序列分别为:ABCDEFG ; CBDEAFG ; 它的后序序列是__________;它的层次序列是___________.2.对8个节点的无向图,若确保其为连通图,至少需要___条边.若确保其为重连通图,至少需____条边.3.采用败者树进行K路归并时,所需工作空间至少为____个,选取一个当前最小关键字需进行____此比较.4.一颗含有15个关键字的4阶B树,其非叶节点数最少不能少于____个,最多可以为____个.5.高度为5的平衡二叉树;其节点数最多可以有____个;最少可以是____个.三、程序阅读(共20分)1.对于正整数n,输出其和等于n且满足以下限制条件的所有正整数的和式, 组成和式的数字自左至右构成一个非递增的序列.如n = 4 , 程序输出为:4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 + 14 = 1 + 1 + 1 + 1test 是实现该功能的C程序段,请将未完成的部分补足,使之完整. Test函数为一递归函数,参数n为被分解和式的数, k为当前的分解深度.算法思想是对n 的所有合理的和式分解,将分解出的数(称为和数) 存于数组a[ ]中.当其中一个分解已不再需要进一步进行时,即找到一个解,将存于a[ ] 中的一个完整和式的和数输出.当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用test函数.#define MAXN 100int a[MAXN];test(int n, int k){ int i,j;for( j= ; j >= 1 ; j –– ) (3分){if ( (3分)for ( i = 2; i <= k; i ++ )printf(" + %d",a[i]);printf("\n");}else test( ; k+1); (4分)}}main(){ test(4,1);}2.设输入为整数数组A[1..n],其中1≤A[i] ≤k (1≤i ≤n);输出数组为B[1..n]; C[1..k]是临时工作空间;阅读下属算法后,回答下列问题:proc Demo(A,B,k) {（1）for i:=1 to k do C[i]:=0;（2）for j:=1 to n do C[A[j]]:= C[A[j]]+1;（3）for i:=2 to k do C[i]:= C[i]+ C[i-1];（4）for j:=n downto 1 do{（5）B[C[A[j]]]:=A[j];（6）C[A[j]]:=C[A[j]]-1;}}(a)当标号(2)行的循环执行完后,C[i] ( 1≤i ≤n )的值有何意义? (3分)(b)当标号(3) 行的循环执行完后,C[i] ( 1≤i ≤n )的值有何意义? (3分)(c)算法执行后,B的内容有和特点?(d)当k=O(n)时,算法的时间复杂度是多少?四、程序设计(20分)1.已知一个n×n的上三角矩阵a的上三角元素已按行主序连续存放在数组b中.请设计一个函数trans将b中元素按列主序连续存放至数组c中. (15分)例:设n=5;=1500001413000121110009876054321a b=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)c=(1,2,6,3,7,10,14,8,11,13,5,9,12,14,15)2.设二叉排序树的存储结构为:type bitree = ^ node;node = recordkey:keytype;size:int;lchild,rchild:bitreeend;其中一个节点x 的size 域的值为以x 为根的子树中节点的总数(包括x 本身).例如下一颗二叉排序树:每个节点图示为若设该二叉排序树高为h,试写一个时间为O(h)的算法Select(T:bitree;i:int),要求该算法返回一个指向二叉排序树T 的中根序列里第i 个最小元素的指针.若i 值非法,返回空指针.例如对上图调用Select(T,7)时返回指向key 为16的节点指针.注意:不允许用中序遍历的方法完成.需要利用节点的Size 信息. (15分)3.请写一个算法求无环连通图T 的中心.(提示:首先将T 中度为1的节点(叶子)删去得到子图T1,然后再删去T 的叶子,…如此反复,直到某个子图Tk 为止.Tk 或者只含一个节点,它即是T 的唯一中心;或者Tk 含有两个节点,它们都是T 的中心).若图有两个中心,求出任意一个即可.存储结构均采用邻接表.在顶点表中可加一个度数域.data degree firstadj┇中国科学技术大学一九九八年招收硕士学位研究生入学考试试题试题名称:程序设计要求: 算法设计题目要求写注解,否则扣分. 写出正确的设计思想和伪代码给分.一、填空(15分,每空1分)1.n 个顶点的无向图的邻接矩阵至少有____非零元素;n 个顶点的有向图是强连通图至少有____条边.2.折半查找的存储结构必须是_____,并且其中存储的关键字必须____;查找成功与不成功的最大比较次数是____.(设关键字总数为n)3.设广义表L=( ( ),( (y), B), L),则L 的长度是______,深度是_____,head(L)是______, tail(L)是______.4.设高度为h 的二叉树无度为1的结点,则此类二叉树至少有____个结点,至多有_____个结点.5.若要将内存中建立的二叉树(不一定是完全二叉树),写到磁盘文件中,则采用_____表示为宜.6.假定有k 个关键字互为同义词,若用线性探测法把这k 个关键字存入散列表中,至少要进行___次探测.7.在基于关键字比较且时间为O( n 2log n)的排序中,若要求排序是稳定的,则可选用___排序;若要求就地排序(及辅助空间为O(1)),则可选用___排序 .二、请在下列各题中选择一个正确的答案(每个选择2分,共20分)1.在一颗m 阶的B 树中:（1）若在某结点中插入一个新关键字而引起结点的分裂,则该结点中原有关键字的个数是:(a) m 个 (b) m – 1个 (c) m – 2 个（2）若在某结点中删除一个新关键字而导致结点的合并,则该结点中原有关键字的个数是:(a) 1m/2−个 (b) m/2个 (c) 1m/2+个2.用ISAM 组织文件适合于(a) 磁带机 (b) 磁盘3.是否存在这样的二叉树,对它采用任何次序的遍历,其遍历产生的节点序列相同?(a) 存在 (b) 不存在4.若一个有向图的邻接矩阵中,主对角线以下的元素均为零,则该图的拓扑有序序列:(a) 不存在 (b) 存在5.对外部排序的k 路平衡归并,采用败者树时,归并效率与k(a) 有关 (b) 无关6.设二叉排序树中关键字由1至1000的整数构成,现要检索关键字为363的结点,下述关键字序列哪一个不可能是二叉排序树上搜索到的序列?(a) 2, 252, 401, 398, 330, 344, 397, 363(b) 924, 220, 911, 244, 898, 258, 362, 363(c) 952, 202, 911, 240, 912, 245, 363(d) 2, 399, 387, 219, 266, 382, 381, 278, 3637.已知待排序的n 个元素可分为n/k 个组,每个组包含k 个元素,且任一组内的各元素均分别大于前一组的所有元素并小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为:(a) O(n 2log n) (b) O(n 2log k) (c) O(k 2log n) (d) O(k 2log k)8.下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序: (a) 二叉排序树 (b) 哈夫曼树 (c) A VL 树 (d) 堆9.将两个各有n 个元素的有序表归并成一个有序表,其最多的比较次数是:(a) 2n (b) n (c) 2n – 1三、(共15分)Fibonacci 树是一种特殊的二叉树,下面给出构造该树的一种算法:procedure FibonacciTree(d:integer ; V ar T:binarytree){ //d 是 Fibonacci 树的深度if d=0 then T := nilelse{ new(T);if d=1 then { T^.leftptr:=nil; T^.rightptr:=nil }else { // d>=2FibonacciTree(d – 2, T^.leftptr);FibonacciTree(d – 1, T^.rightptr); }}}1.画出深度为4的Fibonacci 树(即用d=4调用上述算法的结果) (7分)2.从你画的树中分析深度d 的Fibonacci 树中结点总数和Fibonacci 数的关系.Fibonacci 数定义如下:0F = 1 , 1F = 1 n F = 1-n F + 2-n F n>13.你所画出的Fibonacci 树是否为平衡二叉树?若是,它是否为同样深度的平衡二叉树中节点数目最少的一种? (4分)四、证明若二叉排序数中的一个结点存在两个孩子,则它的中序后继节点没有左孩子, 则它的中序前趋节点没有右孩子. (10分)五、(共25分) 设数组A[1..n]含有n 个互不相同的数,若 i<j 且A[i] > A[j] , 则偶对(i,j)称为A 的一个逆.1.列出数组[3, 4, 9, 7, 1]的五个逆; (2分)2.元素取自集合{1, 2, 3, … n } 的所有数组中,哪一个数组具有最多的逆,其中数是多少? (3分)3.插入排序的运行时间和数组中逆的数目有何关系? (3分)4.写一个算法将两个有序段 r[low..mid] 和 r[mid + 1..high] 归并成一个有序段,并要求在归并的同时求出归并前r[low..high]中逆的总数. (15分)5.利用(4)中的归并算法来对r[1..n]进行归并排序,并同时求出原数组r[1..n]中逆的总数,其时间复杂度是多少? (2分)六、(共15分) 一个有向图G=(V ,E)的平方图 满足下述性质:(u,w) ∈。

中国科学技术大学人文学院高等数学（B）（中国科学院-中国科学技术大学联合命题试卷）1993——2005（1993——2004有答案）管理学院西方经济学（中国科学技术大学命题试卷）1994——1998（1996—1997有答案）（注：1997年的答案共4页，缺P3-P4）概率统计（中国科学院-中国科学技术大学联合命题试卷）2004——2007（2004——2007有答案）概率论与数理统计（中国科学院-中国科学技术大学联合命题试卷）2008（2008有答案）数学系数学分析（中国科学院-中国科学技术大学联合命题试卷）2000，2008（注：2008年试卷为回忆版）数学分析（中国科学技术大学命题试卷）1993，1996——1998高等代数（中国科学院-中国科学技术大学联合命题试卷）2008（注：2008年试卷为回忆版）线性代数（中国科学技术大学命题试卷）1997——1999物理系普通物理（A）（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2003——2008有答案）普通物理（甲）（中国科学院-中国科学技术大学联合命题试卷）1997——1998，2000普通物理（B）（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2004——2008有答案）普通物理（乙型）（中国科学院-中国科学技术大学联合命题试卷）1997——2002（1998，2000——2002有答案）量子力学（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2003——2008有答案）量子力学（实验型）（中国科学技术大学命题试卷）1990——1998（1997有答案）量子力学（实验型）（中国科学院命题试卷）1998——1999量子力学（实验型）（中国科学院-中国科学技术大学联合命题试卷）（2000——2002有答案）量子力学（理论型）（中国科学院-中国科学技术大学联合命题试卷）1990——2002 半导体材料（半导体研究所命题试卷）1996，1998，2000——2001（1996，2000有答案）半导体材料物理（半导体研究所命题试卷）2002——2003半导体集成电路（中国科学院-中国科学技术大学联合命题试卷）2001——2002，2004（2002有答案）半导体模拟集成电路（中国科学技术大学、半导体研究所联合命题试卷）1995——1996，1998（1996，1998，1999有答案）模拟集成电路（中国科学技术大学、半导体研究所联合命题试卷）1997（1997有答案）半导体物理（甲）（中国科学院研究生院命题试卷）2007半导体物理（乙）（中国科学院研究生院命题试卷）2007半导体物理（中国科学院、半导体研究所、中国科学技术大学联合命题试卷）1997——2002，2004（1997——2002有答案）半导体物理[试卷抬头标注为中国科学院微电子中心命题试卷]2004原子核物理（中国科学院-中国科学技术大学联合命题试卷）2000——2002原子物理（中国科学院-中国科学技术大学联合命题试卷）2003——2006（2003——2006有答案）原子物理与量子力学（中国科学院-中国科学技术大学联合命题试卷）2001——2002，2007——2008（2007——2008有答案）热力学与统计物理（中国科学院-中国科学技术大学联合命题试卷）2000——2002，2005——2008（2005——2008有答案）化学物理系物理化学（中国科学院-中国科学技术大学联合命题试卷）1987，1995——2008（1995——2008有答案）物理化学（B）（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2003——2008有答案）物理化学（C）（中国科学院-中国科学技术大学联合命题试卷）2004无机化学（中国科学院-中国科学技术大学联合命题试卷）1999——2008（2001，2003——2008有答案）普通物理（A）（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2003——2008有答案）普通物理（甲）（中国科学院-中国科学技术大学联合命题试卷）1997——1998，2000普通物理（B）（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2004——2008有答案）普通物理（乙型）（中国科学院-中国科学技术大学联合命题试卷）1997——2002（1998，2000——2002有答案）量子力学（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2003——2008有答案）量子力学（实验型）（中国科学技术大学命题试卷）1990——1998（1997有答案）量子力学（实验型）（中国科学院命题试卷）1998——1999量子力学（实验型）（中国科学院-中国科学技术大学联合命题试卷）（2000——2002有答案）量子力学（理论型）（中国科学院-中国科学技术大学联合命题试卷）1990——2002 原子核物理（中国科学院-中国科学技术大学联合命题试卷）2000——2002原子物理（中国科学院-中国科学技术大学联合命题试卷）2003——2006（2003——2006有答案）原子物理与量子力学（中国科学院-中国科学技术大学联合命题试卷）2001——2002，2007——2008（2007——2008有答案）热力学与统计物理（中国科学院-中国科学技术大学联合命题试卷）2000——2002，2005——2008（2005——2008有答案）近代物理系普通物理（A）（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2003——2008有答案）普通物理（甲）（中国科学院-中国科学技术大学联合命题试卷）1997——1998，2000普通物理（B）（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2004——2008有答案）普通物理（乙型）（中国科学院-中国科学技术大学联合命题试卷）1997——2002（1998，2000——2002有答案）量子力学（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2003——2008有答案）量子力学（实验型）（中国科学技术大学命题试卷）1990——1998（1997有答案）量子力学（实验型）（中国科学院命题试卷）1998——1999量子力学（实验型）（中国科学院-中国科学技术大学联合命题试卷）（2000——2002有答案）量子力学（理论型）（中国科学院-中国科学技术大学联合命题试卷）1990——2002 电动力学（中国科学院命题试卷）1998电动力学（中国科学技术大学命题试卷）1999电动力学（中国科学院-中国科学技术大学联合命题试卷）2000——2002电动力学（A）（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2003——2008有答案）电动力学（B）（中国科学院-中国科学技术大学联合命题试卷）2003——2005电子学基础（中国科学院-中国科学技术大学联合命题试卷）2003——2005，2008（2004——2005，2008有答案）原子核物理（中国科学院-中国科学技术大学联合命题试卷）2000——2002原子物理（中国科学院-中国科学技术大学联合命题试卷）2003——2006（2003——2006有答案）原子物理与量子力学（中国科学院-中国科学技术大学联合命题试卷）2001——2002，2007——2008（2007——2008有答案）热力学与统计物理（中国科学院-中国科学技术大学联合命题试卷）2000——2002，2005——2008（2005——2008有答案）力学和机械工程系理论力学（A）（中国科学院-中国科学技术大学联合命题试卷）2005理论力学（B）（中国科学院-中国科学技术大学联合命题试卷）2004——2005机械设计（中国科学院-中国科学技术大学联合命题试卷）2003——2008（2005——2008有答案）电子工程与信息科学系信号与系统（中国科学技术大学命题试卷）1990——1999（1996——1999有答案）（另：有《信号与系统》期末考试试题11份，每份3元。