下载文档原格式
中国科学技术大学一九九五年招收硕士学位研究生入学考试试题试题名称:程序设计.选择题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)在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是A2)快速排序在最坏情况下，时间复杂度是，比的性能差3)就平均时间而言, 最佳 (共4分)c) 0( W) C: a ）堆排序;D: a ）堆排序;A: a ）直接插入排序；b ）起泡排序；c ）简单选择排序;B: a) O(n log n);b ）起泡排序；c ）选择排序 b ）快速排序；c ）归并排序12. 一程序规定的职能是:“输入三个整 数作为三边的边长构成三角形，判别 是等腰三角形，等边三角形，或是一 般三角形，再做计算....... ”.若用等价 类划分方法对该程序做功能测试，至 少应对该程序的输入数据考虑 A 个等价类，其中包括—个有效等 价和C 个无效等价类.,B,C:（答案写在填空的字母后面）1）3; 2）5; 3）7; 4） 12;5) 15; 6) 18; 7)21; 8) 259） 33; 10） 40二叉树如图所示给出先序遍历的节点问顺序; __________出中序遍历的节点问顺序; __________出后序遍历的节点问顺序; __________用二叉链表作为存储结构，将出现多少个空指针（nil ）域?（共4分）13. 下列函数 (6分) function calc(x,y:integer): integer; beginif y=l then calc := xelse calc := calc ( x, y-1 ) + x end;a,b 均为正整数，则calc (a,b) =1) a*(b-l); 2) a*b; 3) a + b 4) a+a14. 程序段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>03)boO 4)bo0 and cAO二.程序改错与填空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 Sund oN := ord(succ(date)) 一c: for n := 1 to 10dobegin1：语句； 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[l..n] of integer;i,k: integer;procedure output 1;beginfor i := 1 to n do write(A[i]:3);writein;end; {output 1)procedure permute(k: integer);var i,t: integer;beginif k=l then output 1else beginfor i:=l to do begint:=A[k];A[k]:=A[i];A[i]:=t;------------- , t：=； A[k]:=:--------------- , end {for) end {else) end; { permute }begink:=n;for i:=l to k do A[i]:=i;permute(k)end.三.编程题:（语言可任选,要求思路清晰，书写工整）1.编写程序将一个循环队列的内容倒置,该循环队列存储在一个数组A[l..n] 中,例如图a 中为倒置前的队列，图b 中为倒置后的队列.要求倒置后的队列 从数组的第一个元素开始存储，整个程序的运行时间为0（n ）. （15分）2.设计一个程序，使输入的句子按如下方式改造之后输出： 1） 单词之间只留一个空格做间隔； 2） 句子结束后必须紧跟句号；3） 如果把句子的单词从左到右依次编号为1,2,3,…则对于第奇数个 单词，只要直接复制就行了,而对于第偶数个单词，应按反序打 印.（15分）例如：输入句子是：this u u u is u u 3. u u silly u u u u program ——;改造后的输出是：this u si u a u yllis u program. (a )(b )。
中科大2023年843科目试题全文共四篇示例，供读者参考第一篇示例：中科大2023年843科目试题中科大2023年843科目试题在学术界引起了广泛的争议和讨论。
这份试题共包含了各类不同科目的考题，涉及了数理、工程、人文、社会等多个领域。
下面我们将逐一介绍其中的一部分试题内容。
数学试题：1. 计算\int_0^1 \frac{1}{x+1} dx；2. 证明勾股定理：a^2 + b^2 = c^2；3. 解方程组：\begin{cases} x + y = 5 \\ 2x - y = 3\end{cases}；4. 求解微分方程：\frac{dy}{dx} = 2x；5. 计算\lim_{x \to 0} \frac{\sin x}{x}。
物理试题：1. 将一个质量为m的物体从高度为h的斜面顶端滑下，求其最终速度；2. 已知一个光滑水平面上有一质量为m的物体，初速度为v_0，求它在t 时间后的位移；3. 在空气中自由落体的重力加速度约为g = 9.8 m/s^2，已知一个物体自由落体t秒后的速度v，求它的高度；4. 将一个质量为m的物体用力水平拉动，求它的加速度；5. 用牛顿第二定律推导匀加速直线运动的位移公式。
化学试题：1. 用化学方程式表示硫酸与氢氧化钠中和的反应过程；2. 已知一个反应的生成物为氧气和氢氧化钠，求该反应的方程式；3. 用化学式表示乙醇的结构；4. 硝酸铜与氢氧化钠反应得到什么产物？写出反应式；5. 用分子式表示氧化铁的结构。
工程试题：1. 设计一个简单的小车，使其能够在水平地面上行走；2. 制作一个简易的电路，包括电源、开关和LED灯；3. 根据给定材料设计一个简单的风筝；4. 利用简单材料制作一个可以测量温度的仪器；5. 设计一个简易的太阳能发电设备。
以上仅仅是中科大2023年843科目试题中的一小部分内容，试题种类繁多，覆盖了多个学科领域，旨在全面考核学生的综合能力和学识水平。
一、概念题：（1）排序算法时间复杂度：排序算法最好最坏平均插入O(n)O(n2)O(n2)归并O(nlogn)O(nlogn)O(nlogn)快排O(nlogn)O(n2)O(nlogn)排序算法空间复杂度：1、所有简单排序和堆排序都是0(1)2、快速排序为0(logn)，要为递归程序执行过程栈所需的辅助空间3、归并排序和基数排序所需辅助空间最多，为O(n)（2）渐近记号1、渐近确界：Θ(g(n))={f(n):存在正常数c1和c2和n0，使对所有的n>= n0，都有0<=c1g(n)<=f(n)<=c2g(n)}。
大Θ记号给出函数的渐进确界。
2、渐近下界：Ω(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=cg(n)<=f(n)}。
大Ω记号给出函数的渐进下界。
3、渐近上界：O(g(n))={f(n):存在正常数c和n0，使对所有的n>=n0，都有0<=f(n)<=cg(n)}。
大O记号给出函数的渐进上界。
（3）二叉查找树：执行基本操作的时间与树的高度成正比。
搜索、插入、删除的复杂度等于树高，期望O(lgn)，最坏O(n)（数列有序，树退化成线性表）（4）红黑树：1、时间复杂度：基本动态集合操作：O(log n)，n是树中元素的数目。
2、性质：1)节点是红色或黑色。
2)根节点是黑色。
3)每个叶节点（NIL节点）是黑色的。
4)如果一个结点是红的，则它的两个儿子都是黑的（不能有两个连续红结点）5)从任一节点到其子孙结点的所有路径都包含相同数目的黑色节点。
3、相关概念，定理：1）黑高度：从某个结点出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数称为该结点x的黑高度，bh(x)。
红黑树的黑高度定义为其根节点的黑高度。
2）一颗有n个内结点的红黑树的高度至多为2lg(n+1)。
(用2-3-4树理解)3）在一颗黑高度为K的红黑树中，总结点数最多有22k+1-1，此时内结点最多为22k-1（满二叉树，红黑交替），内结点最少有2k-14）RB-INSERT-FIXUP操作所作的旋转不超过两次，RB-DELETE-FIXUP所作的操作至多三次旋转（5）动态规划：1、装配线调度：FASTEST-WAY时间复杂度O（n）2、矩阵链乘法：MATRIX-CHAIN-ORDER时间复杂度O（n3）3、最长公共子序列：LCS-LENGTH时间复杂度为O（mn），m、n为序列的长度4、最优二叉查找树：OPTIMAL-BST时间复杂度为O（n3）（6）贪心算法：1、活动选择问题：初试时活动已按结束时间排序，O（n），否则可在O（nlgn）内排序2、哈夫曼编码：Q用最小二叉堆实现，运行时间在O（nlgn）3、任务调度问题：时间复杂度为O（n2），因为算法中O（n）次独立性检查中每一次都有花O（n）的时间（7）二项堆：1、可合并堆时间复杂度过程二叉堆（最坏）二项堆（最坏）Fibonacci（平摊）MAKE-HEAPΘ(1)Θ(1)Θ(1)INSERTΘ(lgn)Ω(lgn)Θ(1)MINIMUMΘ(1)Ω(lgn)Θ(1) EXTRACT-MINΘ(lgn)Θ(lgn)O(lgn) UNIONΘ(n)Θ(lgn)Θ(1) DECREASE-KEYΘ(lgn)Θ(lgn)Θ(1) DELETEΘ(lgn)Θ(lgn)O(lgn)2、二项树B k是一种递归定义的树，由两颗B k-1连接而成，其中一颗树的根是另一颗树的根的最左孩子性质：1）共有2k个结点2）树的高度为k3）在深度i处恰有(上k,下i)（因此叫二项树）个结点，其中i=0,...,k；4）根的度数为k，它大于任何其他结点的度数，并且，如果对根的子女从左到右编号为k-1，k-2,...，0，子女i是子树Bi的根。
黄宇《算法设计与分析》课后习题解析（⼆）第2章：从算法的视⾓重新审视数学的概念2.1：(向下取整)题⽬：请计算满⾜下⾯两个条件的实数的区间解析：根据向下取整的含义，令，讨论a的取值范围即可解答：令，则可得：即：故的取值区间为：2.2: (取整函数)题⽬：证明：对于任意整数,（提⽰：将n划分为）。
解析：根据提⽰将n进⾏划分，根据取整函数的定义⽤k表⽰取整函数，即可证明；证明如下：因为对于任意整数,可划分为，则:① ；② ；综上：对于任意整数,, 得证；2.3: (斐波拉契数列)对于斐波拉契数列，请证明：1）题⽬：是偶数当且仅当n能被3整除解析：由斐波拉契数列的递归定义式，容易联想到数学归纳法；证明如下：（采⽤数学归纳法）i)当n = 1,2,3时，依次为1，1，2，符合命题；ii)假设当（k>=1）时命题均成⽴，则：① 当n = 3k+1时，是奇数，成⽴；② 当n = 3k+2时，是奇数，成⽴；③ 当 n = 3(k+1)时，是偶数，成⽴；综上：归纳可得为偶数当且仅当，得证;2）题⽬：x x =1+a (0<a <1)x =1+a (0<a <1)⌊x ⌋=1⇒⌊x ⌋=21⌊x ⌋=2⌊1+a +22a ⌋=1a +22a <1⇒0<a <−21⇒1<a +1<⇒21<x <2x (1，)2n ≥1⌈log (n +1)⌉=⌊logn ⌋+12≤k n ≤2−k +11n ≥12≤k n ≤2−k +11k +1=⌈log (2+k 1)⌉≤⌈log (n +1)⌉≤⌈log (2)⌉=k +1k +1=>⌈log (n +1)⌉=k +1k =⌊log (2)⌋≤k ⌊logn ⌋≤⌊log (2−k +11)⌋=k =>⌊logn ⌋=k n ≥1⌈log (n +1)⌉=k +1=⌊logn ⌋+1F n F n n ≤3k F =n F +n −1F =n −2F +3k F =3k −1>F 3k +1F =n F +3k +1F =3k >F 3k +2F =n F +3k +2F =3k +1>F 3k +3F n 3∣n F −n 2F F =n +1n −1(−1)n +1解析：同1）理，容易联想到数学归纳法证明如下：（采⽤数学归纳法）i)当n = 2时，, 易知成⽴；ii)假设当 n = k 时命题成⽴，① 若k = 2m, 则,当n = k+1 = 2m+1时，要证命题成⽴，即证： => ,代⼊递推式, 得：, 易知是恒等式，故命题成⽴；②当 k=2m+1时，同①理可证命题成⽴；综上：归纳可得，得证；2.4：(完美⼆叉树)给定⼀棵完美⼆叉树，记其节点数为，⾼度为，叶节点数为，内部节点数为1）题⽬：给定上述4个量中的任意⼀个，请推导出其他3个量解析：根据完美⼆叉树的结构特点易得解答：（仅以已知⾼度h推导其他三个量为例，其余同理）已知⾼度为h，可得：节点数：叶节点数：内部节点数：2）题⽬：请计算完美⼆叉树任意⼀层的节点个数：① 如果任意指定深度为的⼀层节点，请计算该层节点个数；② 如果任意指定⾼度为的⼀层节点，请计算该层节点个数；解析：根据完美⼆叉树的结构特点易得（注意节点深度和节点⾼度是互补的，相加为树⾼）解答：① ; ② ;2.5: (⼆叉树的性质)对于⼀棵⾮空的⼆叉树T，记其中叶节点的个数为，有1个⼦节点的节点个数为，有两个⼦节点的节点个数为1）题⽬：如果T是⼀棵2-tree，请证明。
中科⼤-组合数学复习知识点⼀、鸽巢原理定理：n+1个物品放⼊n个盒⼦中，那⾄少有 1 个盒⼦中⾄少有 2 个物品。
解题思路：构造部分和序列正整数a i=2s i×r i,s i为⾮负整数,r i为奇数加强形式：m个物品放⼊n个盒⼦中，⾄少有 1 个盒⼦中⾄少有mn个物品。
若物品数与盒⼦数相等，则⾄少 1 个盒⼦中⾄少有 1 个物品。
若m=n+1，则⾄少 1 ⼀个盒⼦中⾄少有 2 个物品。
解题思路：递增⼦序列问题：构造{m k},m k表⽰从a k开始的最长递增⼦序列长度将集合分成 n 部分，使⽤加强形式取余⼆、排列与组合2.1 集合的排列组合r排列=P(n,r)=A rn =n! (n−r)!r圆排列=1r P(n,r)=1r A rn=n!r(n−r)!r组合数=nr=C rn=n!r!(n−r)!定理：(n0)+(n1)+⋯+(nn)=2n解题思路：能被 3 整除的数，各位数字之和也要能被 3 整除2.2 多重集合定理：多重集合M={∞⋅a1,∞⋅a2,⋯,∞⋅a k}的r排列数为k r.定理：多重集合M={k1⋅a1,k2⋅a2,⋯,k n⋅a n}的全排列数为(k1+k2+⋯+k n)!k1!k2!⋯k n!.只适⽤全排列，如果 k 排列，则⽤指数型⽣成函数。
定理：多重集合M={∞⋅a1,∞⋅a2,⋯,∞⋅a k}的r组合数为(k+r−1r)=C rk+r−1.证明⽅法：对应求⾮负整数解⽅案数x1+x2+⋯+x k=r =>r 个相同的球放⼊ k 个不同的盒⼦中定理：多重集合M={∞⋅a1,∞⋅a2,⋯,∞⋅a k}，要求各元素⾄少出现⼀次的r组合数为(r−1k−1)=C k−1r−1.证明⽅法：对应求满⾜⼀定条件的整数解⽅案数x1+x2+⋯+x k=r,x i≥1例题：求⽅程x1+x2+x3+x4=18满⾜条件x1≥3,x2≥1,x3≥4,x4≥2的整数解数⽬。
解：令y1=x1−3,y2=x2−1,y3=x3−4.y4=x4−2，则原⽅程变为y1+y2+y3+y4=8的⾮负整数解数⽬，(8+4−1 8)⌈⌉()课后习题 13，不穿过直线y=x课后习题 13，不穿过直线y=x的⾮降路径数？三、⼆项式系数⼆项式定理：(x+y)n=x n+(n1)x n−1y+(n2)x n−1y2+⋯+y n=∑ni=0(ni)x n−i y i⽜顿⼆项式定理：(1+x)α=∑∞r=0(αr)x r,(αr)=α(α−1)⋯(α−r+1)r!,α为⼀切实数,|x|<1α=−n 时，有(αr)=(−1)r(n+r−1r)(1+x)−n=∑∞r=0(−1)r(n+r−1 r)x r(1−x)−n=∑∞r=0(n+r−1 r)x r(1+x)−1=1−x+x2−x3+⋯(1−x)−1=1+x+x2+x3+⋯α=12时，有(αr)=(−1)r−11r22r−1(2r−2r−1)(1+x)12=∑∞r=1(−1)r−11r22r−1(2r−2r−1)x r,Catalan数基本性质：对称关系：(nr)=(nn−r)递推关系：(nr)=(n−1r)+(n−1r−1)=C rn−1+C r−1n−1组合恒等式：C1 n +2C2n+3C3n+⋯+nC nn=n2n−1C k 0+C k1+C k2+⋯+C kn=C k+1n+1∑n i=0(C in)2=C n2n∑r i=0C imC r−in=C rm+n,Vandermonde恒等式∑m i=0C imC r+in=C m+rm+n多项式定理：(x1+x2+⋯+x t)n=∑(nn1n2⋯n t)x n11x n22⋯x n tt,(nn1n2⋯n t)=n!n1!n2!⋯n t!例题：展开 (2x1−3x2+5x3)6，则 x31x2x23系数为解：6!3!1!2!23(−3)52多项式定理性质：展开式项数为n1+n2+⋯+n t=n的⾮负整数解个数，为(n+t−1 n)∑(nn1n2⋯n t)=t n,令所有xi都为1四、容斥原理定理：|¯A1∩¯A2∩⋯∩¯A m|=|S|−∑|Ai|+∑|A i∩A j|+⋯+(−1)m|A1∩A2∩⋯∩A m|推论：|A1∪A2∪⋯∪A m|=|S|−|¯A1∩¯A2∩⋯∩¯A m|欧拉函数的证明欧拉函数表⽰⼩于 n 且与 n 互素的整数的个数n =p i 11p i 12⋯p iq q 记 A i ={x |x ≤n 且p i |x} ，表⽰与 p i 成倍数的那些数那么 φ(n)=|¯A 1∩¯A 2∩⋯∩¯A q |=n ∏q i=1(1−1p i )定义：N (P i 1,P i 2,⋯,P i k ) 表⽰ S 中具有性质 P i 1,P i 2,⋯,P i k的元素个数ω(k )=∑N (P i 1,P i 2,⋯,P i k) 表⽰具备 k 个性质的元素计数，其中⼀个元素会被多次计数。
