吉林大学计算机图形学2008级试卷B答案

南昌航空大学2008—2009学年第1学期期末考试课程名称:数字逻辑B A 卷参考答案及评分标准一. 基本题(共55分)1. 完成下列数制转换。

(每空3分，共15分)(1) (37)8＝( )2＝( )16 解: (37)8＝(11111)2＝(1F)16(2) (125)10＝( )2＝( )8＝( )16解: (125)10＝(1111101)2＝(175) 8＝(7D) 162. 用真值表证明等式: B A B A +=⋅ (10分)解:3. 用布尔代数化简逻辑函数表达式: C B A C B A C B A C B A F +++=。

(10分)解： C B A C B A C B A C B A F +++=C B A C B A C C B A ++=)(C B A C B A B A ++=C B A C A A B ++=)( C B A C A B ++=)(C B A C B A B ++=C B C A B A ++=4. 已知A 、B 为输入，F 为输出，波形如下图所示。

根据波形图写出真值表及函数F 的表达式。

(10分)解: (1)(2)4. 用卡诺图化简表达式:∑Φ∑,,,(m,7,4,3,0(AF。

(10分)11BCD),15=))14+,9,8(,12,13解:卡诺图如下:由卡诺图可得：F CD CD=+二．电路分析题(共25分)1. 组合逻辑电路分析。

(10分)分析下面组合逻辑电路，（1）写出下图组合逻辑的函数表达式；(3分)（2）根据表达式写出真值表；(3分)（3）分析电路的逻辑功能。

(4分)解：（1）从输入端开始逐级写出函数表达式。

（3分） AB P =1 BC P =2 AC P =3AC BC AB AC BC AB P P P F ++===321（2）列出真值表。

（3分）（3分析：A 、B 、C 三人对某事件进行表决，同意用“1”表示； 不同意用“0”表示。

《计算机图形学》考试试卷
一、图形与图像的定义及其相互关系
二、计算机图形学的应用。

三、试给出直线的中点画线法算法过程。

P22
四、已知多边形P=(P0P1P2P3P4P5P6P0)；其各边坐标分别为（2，5）（2，10）（9，
6）（16，11）（16，4）（12，2）（7，2）（2，5），在用y-x算法对其实现扫描转换时，请写出ET和扫描线y=3与y=8时AET的内容。

五、在二维空间，欲求某点关于直线y = ax + b的对称点，试写出对应的变换
矩阵。

设二维空间中任一条直线l：y=mx+h,那么点P(x0,y0)关于l的对称点P'(x1,y1)的公式如下：
故变换矩阵为可看成先做缩放变换再做平移变换，然后再做整体缩放变换，矩阵如下：
六在三维空间，欲求某点关于平面y = ax + by + c的对称点，试写出对应的变换矩阵。

七试写出phong光照模型，并指出个参数的含义。

P134
八 conns曲面的给定条件及各条件的作用。

九试写出三维图形平移变换，比例变换和旋转变换的变换矩阵。

十对多边形明暗处理时，双线性亮度插值法的算法思路。

1查色表原理及优点
2参数方程描述自由曲线的优先
3：试给出关于变截面的三个正则结合算子的表达式4：平面几何投影分类
5。

《计算机图形学》练习题１。

直线扫描转换的Bresｅnham算法(1) 请写出生成其斜率介于０和1之间的直线的Bresｅnhaｍ算法步骤。

(2) 设一直线段的起点和终点坐标分别为(1,1)和(8,5),请用Brｅsenhａm算法生成此直线段,确定所有要绘制象素坐标、(1)①输入线段的两个端点,并将左端点存储在(ｘ0,y0)中②将(ｘ０,y0)装入帧缓存,画出第一个点③计算常量∆ｘ, ∆y, 2∆y, aｎd ２∆y—２∆x,并得到决策参数的第一个值:p0 = 2∆y —∆x④从k=0开始,在沿线路径的每个xｋ处,进行下列检测:假如pｋ < 0,下一个要绘制的点就是(ｘk +1,yk) ,同时pk+１= pk + 2∆y否则下一个要绘制的点就是(xｋ +1, ｙk +1),同时ｐk＋１ = pk + 2∆y— 2∆x⑤重复步骤４,共∆x—1次(2)m=(5－1)／(8－1)=０、5７x＝7 y=4P0=2y—x=12y=8 2ｙ－２x=-62、已知一多边形如图1所示,其顶点为V1、Ｖ2、Ｖ3、Ｖ４、V５、V6,边为Ｅ1、E2、E３、E４、Ｅ５、E6。

用多边形的扫描填充算法对此多边形进行填充时(扫描线从下到上)要建立边分类表(ｓｏrtｅd edｇe ｔable)并不断更新活化边表(aｃtive eｄｇｅ liｓt)。

(1)在表1中填写边分类表中每条扫描线上包含的边(标明边号即可);(2)在表２中写出边分类表中每条边结构中各成员变量的初始值(3) 指出位于扫描线y=6,7,8,9和10时活化边表中包含那些边,并写出这些边中的ｘ值、y max值、和斜率的倒数值１/m。

表１边分类表x图1多边形的边和顶点边 x y max 1/m ４ 1 1 9 ７ 4 6 0 0 5 1 ９ 7 6 ０ 0 ６ 1 9 ６ 6 0 0 ７ 1 １ ８ ７ 7 9 0 1 －1 8 2 ７ 9 9 1 －1 93 ３ 69 9 ９１ －13。

[考研类试卷]2008年工程硕士研究生学位课程（数值分析）真题试卷B一、填空题请完成下列各题，在各题的空处填入恰当的答案。

1 为了使计算y=11+的乘除法运算次数尽量地少，应将该表达式改为_____．2 求方程x-f(x)=0根的牛顿迭代格式是_____3 设A=则‖A‖∞=_______4 解方程组的Jacobi迭代格式为______5 设f(x)=8x4+3x3-98x+1,则差商f[2，4，8，16，32]=______6 记h=(b-a)／n，x i=a+ih，0≤i≤n，则计算I(f)=的复化Simpson公式为______，代数精度为______7 用简单迭代法求非线性方程x-lnx=2在(2，+∞)内的根，要求精确至6位有效数字，并说明所用迭代格式为什么是收敛的．8 给定线性方程组 1)写出Gauss-Seidel迭代格式； 2)分析此迭代格式的收敛性．9 1)给定如下数据表：求f(x)的2次插值多项式L(x)；2)利用如下数据表：求f(x)的3次插值多项式H(x)．10 求a，b，使得达到最小，并求出此最小值．11 求系数A1，A2，A3，使得求积公式≈A1f(-1)+A2f(-1/3)+A3f(2/3)的代数精度尽可能高，并指出所达到的代数精度的次数．12 给定常微分方程初值问题取正整数n，并记h=(b-a)／n，x i=a十ih，0≤i≤n．1)分析如下求解公式的局部截断误差y i+1=y i+[f(x i+1,y i+1)+f(x i,y i)](A)2)分析如下求解公式的局部截断误差y i+1=y i+[3f(x i，y i)-f(x i-1，y i-1)]；(B)3)指出以上两个求解公式各是儿阶公式，并从局部截断误差的大小、显隐格式及单多步公式几方面作一个简单的比较．。

华中科技大学文华学院2008～2009学年度第一学期《计算方法》考试试卷B答案课程性质：必修使用范围：本科考试时间：2009年4月22日考试方式：闭卷学号专业班级学生姓名成绩一、单项选择题（每小题3分，共30分，请将正确选择填入下表中）1．π=3.141 592 6…，若取值为3.141 5，其有效数字位数是（）位。

A.3B.4C.5D.62．-0.002 00的绝对误差限是（）。

A.0.005B.0.0005C.0.00005D.0.0000053．ln2=0.693 147 18…，精确到10-3的近似值是（）。

A.0.690B.0.700C.0.693D.0.6944．正方形的边长约为100cm，要使其面积误差不超过1cm2，测量边长的绝对误差限应为（）cm。

A.0.5B.0.05C.0.005D.0.00055．设x>0，x的相对误差为δ，则ln x的相对误差为（）。

A. δ/xB.δxC.δx2D.δ/x26．用二分法求方程f(x)=0在[1,2]的近似根，要求误差不超过0.5*10-3，至少要二分（）次。

A. 7B.8C.9D.107．近似值a=4.123，则a2的误差限为（）。

A.0.5*10-1B. 0.5*10-2C.0.5*10-3D. 0.5*10-48．设S=gt2/2，假定g是准确的，而对t的测量有0.1秒的误差，则当t减少时， S的绝对误差（）。

A.增加B.不变C.减少D.按平方增加9．若F(x)=f(x)+g(x)，则差商F[x0,x1]=f[x,x1]（）g[x,x1]。

A.+B.-C.*D./10．迭代公式为x k+1=ϕ(x k)，要使迭代收敛，就要求（）。

A.ϕ’(x)>0B.ϕ’(x)<1C. 0<ϕ’(x)<1D. -1<ϕ’(x)<1二、计算题（每小题10分，共70分，要有过程，无过程则无分）1．设f(x)=8x 5-0.4x 4+4x 3-9x+1，用秦九韶算法求f(3)。

《 计算机图形学 》 期末考试卷（A ） 答案 一、填空题 〖每空2分，共计10分〗 1．Y 方向，X 方向 2．正负角度法，射线法 3．提高分辨率，区域采样 4．计算机图形学，图象处理，模式识别 5．M-n 或 m-n+1 二、选择题〖每小题1分，共计10分〗 1.B 2.C 3.B 4.D 5.D 6.A 7.B 8.D 9. c 10.A 三、计算题 〖每题15分，共计15分〗 解：（1） P 1 P 2与X 轴的夹角为： 948-1-3--1arctg arctg ==θ 1分 （2）将坐标系平移至P 1 (-1,-1)点 ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=111010001A T 2分 （3） 绕原点转-θ角 ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-=1000cos sin 0sin cos θθθθB T 2分 （4） 以X 轴对称 ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-=100010001C T 2分 （5） 绕原点转θ角 江 南 大 学 考1⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-=1000cos sin 0sin cos θθθθD T 2分（6）将坐标系平移回原处 ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--=111010001E T（7） 变换矩阵：T=T A*T B*T C*T D*T E 3分（8） 求变换后的三角形ABC 各顶点的坐标A ’、B ’、C ’ 3分 A ’: [][]T Y X A A ⨯=1211'' B ’: [][]T Y X B B ⨯=12151' C ’: [][]T Y X C C ⨯=1531'' 四、算法应用题 〖每题分值题后标明，共计45分〗 1..用Bresenham 算法生成直线段。

方向计长以解：X x y 1650605<=--=∆∆ 步共走走步数6616==∆∆=t x k 是第一象限的线段 ⎪⎩⎪⎨⎧⎩⎨⎧<≥+=+=++++0)(0)(111,1,11i r i i r i i i i x y x y y x x εε 试 卷 专 用 纸江南大学考2222)5.0()1()5.0,1(),(R y x y x F y x F d i i i i M M --++=-+== y 方向的变化情况：⎩⎨⎧≥<=+)0( 1-)0(1d y d y y i i i （3分）(3)递推公式：（4分）当d<0时，下一步的中点坐标为：M （x i ＋2，y i －0.5）。

计算机图形学作业答案第二章图形系统第二章图形系统1． 什么是图像的分辨率？什么是图像的分辨率？解答：在水平和垂直方向上每单位长度（如英寸）所包含的像素点的数目。

在水平和垂直方向上每单位长度（如英寸）所包含的像素点的数目。

2． 计算在240像素像素//英寸下640640××480图像的大小。

图像的大小。

解答：（640/240640/240））×(480/240)(480/240)或者（或者（或者（8/38/38/3）×）×）×22英寸。

英寸。

3． 计算有512512××512像素的2×2英寸图像的分辨率。

英寸图像的分辨率。

解答：512/2或256像素像素//英寸。

英寸。

第三章 二维图形生成技术a) 一条直线的两个端点是（0，0）和（6，18），计算x 从0变到6时y 所对应的值，并画出结果。

并画出结果。

解答：由于直线的方程没有给出，所以必须找到直线的方程。

下面是寻找直线方程（由于直线的方程没有给出，所以必须找到直线的方程。

下面是寻找直线方程（y y ＝mx mx＋＋b ）的过程。

首先寻找斜率：）的过程。

首先寻找斜率： m m ＝＝ ⊿y/y/⊿⊿x x ＝＝ （y 2－y 1）/（x 2－x 1） ＝ （1818－－0）/(6/(6－－0) 0) ＝＝ 3 接着b 在y 轴的截距可以代入方程y ＝3x 3x＋＋b 求出求出 0 0 0＝＝3（0）＋）＋b b 。

因此b ＝0，所以直线方程为y ＝3x 3x。

b) 使用斜截式方程画斜率介于0°和45°之间的直线的步骤是什么？°之间的直线的步骤是什么？ 解答：1.1. 计算dx dx：：dx dx＝＝x 2－x 1。

2.2. 计算dy dy：：dy dy＝＝y 2－y 1。

3.3. 计算m ：m ＝dy/dx dy/dx。

4.4. 计算b: b b: b＝＝y 1－m ×x 15.5. 设置左下方的端点坐标为（x ，y ），同时将x end 设为x 的最大值。

广州大学2008-2009学年第一学期考试卷参考答案课 程：高等数学（B 卷）（90学时） 考 试 形 式： 闭卷 考试一．填空题（每空2分，本大题满分16分）1．设⎩⎨⎧≤>=002x x x x x f ,,)(，则=-))2((f f 4 .2. 若函数 ⎩⎨⎧>+≤=112x b ax x x x f ,,)( 在1=x 处可导，则=a 2 ，=b -1 .3．0=x 是x xy sin =的第 一 类间断点，是xy 1si n =的第 二 类间断点。

4．已知10=')(x f ，则=--+→hh x f h x f h )()(lim0002 .5．设)(),(x G x F 是)(x f 的两个原函数，则='=')()(x G x F )(x f ，='-])()([x G x F ___0___.二．选择题 (每小题3分, 本大题满分15分)学院专业班 级 姓 名1. 当0→x 时, 12-x e是2x 的( C )无穷小.(A) 高阶 (B) 低阶 (C) 同阶 (D) 等价 2. 函数3x y =在点(1,1)处的切线方程为 ( B ).(A) 23--=x y (B) 23-=x y (C) 23+=x y (D) 13+-=x y 3．设)(x f 的一个原函数是x cos ，则='⎰dx x f x )( ( A ). (A) C x x x +--cos sin (B) C x x x +-cos sin (C) C x x x +-sin cos (D) C x x x ++-sin cos .4. 若函数)(x f 在点0x x =可导是)(x f 在点0x x =连续的（ A ）。

(A) 充分条件 (B) 必要条件 (C) 充要条件 (D) 无关条件.5.设)(x f 在区间I 内具有二阶导数，且在I 内0>'')(x f ，则)(x f 在I 内是( B ).(A) 凸函数 (B) 凹函数 (C) 周期函数 （D ）单减函数三．解答下列各题（每小题6分，本大题满分30分）1．2211xx y +-=ln ，求dy . 解：)ln()ln(2211x x y +--=221212x xx x y +--=' 144-=x x………………………………………………………………..4分 dx x xdx y dy 144-='=∴……………………………………………….6分2．=y x e 2，求n 阶导数).()(0n y .解：,xe y 22=',x e y 222='',x e y 232=''',)()(x n n e x y 22=∴……………………………………………………………4分 .)()(n n y 20=∴………………………………………………………………..6分3．设曲线参数方程为)(sin cos 0>>⎩⎨⎧==b a tb y ta x ，求dxdy . 解：dt dxdt dy dx dy =………………………………………………………………….3分 t ab t a t b cot sin cos -=-=……………………………………………….6分4．求321x x x )sin (lim +→.解：22223123211x x xx x x x x sin sin)sin (lim )sin (lim ⋅→→+=+2231201⎪⎭⎫⎝⎛→⎪⎪⎭⎫⎝⎛+=x x x x x sin sin )sin (lim …………………………………………….3分3e =…………………………………………………...……………………….6分5．求⎪⎭⎫⎝⎛--→x x x ln lim 1111.解：=⎪⎭⎫⎝⎛--→x x x ln lim 1111⎪⎪⎭⎫⎝⎛--+→x x x x x ln )(ln lim 111……………………………….2分 ⎪⎪⎪⎪⎭⎫⎝⎛-+-+=→x x x x x 1111ln lim⎪⎭⎫⎝⎛+--+=→111x x x x x ln lim ………………………………………………………4分 ∞= …………………………………………………………..…..6分四．计算下列积分（每小题6分，本大题满分18分）1．xdx x 22⎰cos . 解：x d x xdx x 221222sin cos ⎰⎰=()dx x x x x ⎰⋅-=222212sin sin ……………………………………………..2分 ()x d x x x 22212cos sin ⎰+= ()xdx x x x x 222212cos cos sin ⎰-+=……………………………………4分 C x x x x x +⎪⎭⎫⎝⎛-+=22122212sin cos sin ………………………….…..…..6分 2．⎜⎠⎛-220221dx xx .解：令t x sin =，则tdt dx cos =⎜⎠⎛-=⎜⎠⎛-40222202211πtdt t t dx x xcos sin sin ……………………..………....2分 dt t ⎰=402πsin ……………………..…………………………………………..3分dt t ⎰-=4221πcos 40422π⎪⎭⎫ ⎝⎛-=t t sin ………………………………………………………….….5分.418-=π……………………..……………………………………………….6分3．⎰∞++12211dx x x )(.解：⎰∞++12211dx x x )( ⎰∞+⎪⎭⎫ ⎝⎛+-=122111dx x x…………………………………………………...….2分 +∞⎪⎭⎫⎝⎛--=11x x arctan ……………………..………………………………....4分 .41π-=………………………………………………………………………..6分六．（本题满分6分）计算由抛物线2x y =与x y =所围图形绕x 轴旋转一周所得立体的体积. 解：根据旋转体体积公式知dx x x V ⎰-=142)(π……………………..…………………………………3分105353⎪⎪⎭⎫⎝⎛-=x x π π152=………..………………………………………………………………6分七．（本题满分7分）1． 证明当0>x 时，有x x x >++212)ln(. 证明：令x x x x f -++=212)ln()(，………………………………...2分 则当0>x 时，011112>+=-++='xx x x x f )(，……………………….4分x x x x f -++=212)ln()(在),(+∞0上严格单调递增。

天津师范大学考试试卷2009 —2010学年第一 学期期末考试试卷（B 卷）科目： 离散数学学院： 管理学院专业：08信管、物流一、 单项选择题:在每小题的备选答案中选出一个正确答案，并将正确答案的代（每小题 分，本大题共 分）1.谓词公式(∀x)(P(x) ( ∃y)R(y)) → Q(x)中量词(∀x)的辖域是（ ）。

A. (∀x) (P(x) ( ∃y)R(y))B. P(x)C. P(x) ( ∃y)R(y)D. P(x),Q(x)2. 下列公式中哪些公式不是前束范式（ ）。

A. x ∀∃y(P(x) q(y))B. ∀x ∀y(P(x) Q(y) ( ∃z)S(z))C.Q(a,b)D. P3. 给定解释N 如下：个体域为自然数D N ；D N 上特定元素a = 0；D N 上特定函数f(x,y) = x+y , g(x,y) = x ∙y ； D N 上特定谓词E(x,y)为x=y ,下列公式为真的是（ ）。

A. ∀xE(g(x,a),x) B. ∀x ∀y ∀zE(f(x,y),z) C. ∀x ∀yE(f(x,y),g(x,y)) D. ∃x ∃yE(f(x,y),g(x,y))4. 设集合X≠∅，则空关系∅不具备的性质是（）。

xA.反自反性B.自反性C.对称性D.传递性5. 下列各式中，哪个不成立（）。

A.(∀x) (P(x) Q(x))⇔(∀x) (P(x) (∀x)Q(x))B.(∃x)(P(x) Q(x))⇔(∃x) (P(x) (∃x)Q(x)C.(∀x) (P(x) Q(x))⇔(∀x) (P(x) (∀x)Q(x)D.(∀x) (P(x) Q)⇔(∀x) (P(x) Q)6. 设个体域A={a,b},则∃x(F(x) G(x))消去量词为（）。

A. F(a) G(a)B. F(b) G(b)C. ( F(a) G(a) (F(b) G(b)))D. F(a) G(b)7. 给定A={1,2,3,4}，A上的关系R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}满足的性质是（）。

2008级_计算理论_试卷答案《计算理论》试卷答案（2008级）一、一台DFA M的状态图如右：(8分)1、请指出M的起始状态是什么？2、请指出M的接受状态集是什么？3、对输入aabb，M经过的状态序列是什么？4、请给出机器M的形式描述。

参考答案：1、q12、{q2}3、q1,q2,q3,q1,q14、M=({q1,q2,q3},{a,b},δ， q1,{q2}).转换函数δ二、证明：设M是一台识别语言B的DFA，交换M的接受状态与非接受状态得到一台新的DFA，则这台新的DFA识别语言B的补集。

(8分)参考答案：设M’是一台将DFA M 的接受态与非接受态交换后的DFA，接下来证明M识别B语言，则M’识别B的补集：假定M’识别x ，则对于x 在M’上运行将结束于M’的一个接受态，因为M和M’交换了接受态与非接受态，因此对于x运行于M，将会结束于一个非接受态，所以x∈/ B。

类似地，如果x不被M’接受，则它一定被M接受。

故M’恰好接受所有不被M接受的那些串，因此M’识别B的补集。

既然B是任意的正则语言，且我们已构造出一台自动机识别它的补集，它表明任何正则语言的补也是正则的。

因此，正则语言类在补运算下封闭。

三、令∑＝｛0，1，＋，＝｝和ADD＝｛x = y + z | x，y，z是二制整数，且x是y与z的和｝，请用泵引理证明ADD不是正则的。

(8分) 参考答案：假定ADD是正则的。

让P作为泵引理中的泵长度，选择S的串形式为1P＝0P＋1P作为ADD的一个成员。

因为S有长度大于P，由泵引理保证它能分割成形如：S＝xyz的三部分，满足泵引理的条件。

泵引理的第三个条件有｜xy｜≤P，《它表明对于K≥1，y就是1K。

这是xy2z是串1P＋K＝OP＋1P，而它不是ADD的成员，由泵引理导出矛盾，因此ADD不是正则的。

四、请将下述CFG转换成等价的乔姆斯基范式文法。

(8分)A→BAB｜B｜εB→00｜ε参考答案：S0→AB｜CC｜BA｜BD｜BB｜εA→AB｜CC｜BA｜BD｜BBB→CCC→0D→AB五、上下文无关文法CFG＝（V，∑，R，E），其中V＝｛E，T，F｝，∑＝｛a，＋，×，(，)｝，规则为：E→E＋T｜TT→T×F｜FF→(E)｜a请给出如下字符串的派生: (8分)1、a＋a2、((a))参考答案：1、E=>E+T=>T+T=>F+T=>F+F=>a+F=>a+a2、E=>T=>F=>(E)=>(T)=>(F)=>((E))=>((T))=>((F))=>((a))六、语言A＝｛w｜w所包含的0的个数不是1的个数的二倍｝是字母表｛0,1｝上的语言，请以实现描述水平级给出判定该语言的图灵机：(8分)参考答案：对于输入串w扫描带子且标记第一个没有被标记的0，如果没有未被标记的0，则到第5步继续标记下一个没有被标记的0，如果没有，则接受，否则，将指针移到带子的最前端扫描带子且标记第一个没有被标记的1，如果没有，则接受将指针移到带子的最前端，重复第1步将指针移到带子的最前端，扫描带子，看是否有未被标记的1，如果没有则拒绝，否则接受。

信息学院本科生2007－2008学年第二学期数据结构期末考试试卷(A卷)专业：______________年级：______________学号：______________姓名：______________成绩：______________一、单项选择、填空题（本题共22分）1.（2分）基数排序算法可达到线性时间复杂性，原因是___________A．设计了巧妙的关键字比较交换方法。

B．不通过关键字比较，而是通过关键字值进行分类。

C．以上都不对。

2.（2分）n节点的二叉搜索树的高度为____________，n节点的A VL树的高度为____________。

A．O(logn) B．O(n)C．O(nlogn) D．O(n2)3.（2分）数据集合规模为n，采用Hash技术解决搜索问题，Hash表桶数目为m，则插入、删除、搜索操作的平均时间复杂性为____________，最坏情况时间复杂性为____________。

A．O(1) B．O(logn)C．O(n) D．O(nlogn)4.（2分）n个节点的二叉树，其先序遍历和中序遍历结果相同，则其可能的结构有多少种？____________。

A．1 B．nC．n2 D．2n5.（2分）一棵有序树可转换为一棵二叉树，其后根遍历（按顺序递归遍历所有子树，然后再访问根）对应二叉树的____________。

A．先序遍历B．中序遍历C．后序遍历D．以上都不对6.（3分）4层5阶B-树，插入一个新元素最多需要进行几次磁盘读写操作？____________A．10 B．11C．12 D．137.（2分）用邻接链表描述有向图，下面哪个操作性能较差？___________A．计算顶点出度B．求顶点邻接至的顶点集合C．计算边的总数D．求顶点邻接于的顶点集合8.（2分）6个顶点的最大堆，排在降序第三位的关键字有几个可能的位置？____________A．3 B．4C．5 D．69.（2分）通过相邻元素比较－交换操作构造的排序算法，时间复杂性下界为____________，通过任意元素对比较－交换操作构造的排序算法，时间复杂性下界为____________。

一．判断题（请在后面括号中打T或F）1．阴极射线管的技术指标主要是分辨率和显示速度; （Y）2．光栅扫描式图形显示器可看作是点阵单元发生器，可直接从单元阵列中的一个可编地址的象素画一条直线到另一个可编地址的象素; （N ）3．计算机图形学标准通常是指数据文件格式标准和子程序界面标准; （Y）4．在种子填充算法中所提到的八向连通区域算法同时可填充四向连通区; （Y）5．边填充算法中是将扫描线与多边形交点左方的所有象素取补; （N ）6．插值得到的函数严格经过所给定的数据点；逼近是在某种意义上的最佳近似;（Y）7．齐次坐标提供了坐标系变换的有效方法，但仍然无法表示无穷远的点；（N ）8．若要对某点进行比例、旋转变换，首先需要将坐标原点平移至该点，在新的坐标系下做比例或旋转变换，然后在将原点平移回去；（Y）9．显式方程和参数曲线均可以表示封闭曲线或多值曲线；（N ）10. 凡满足G'连续的曲线同时满足C'连续条件，反之则不成立；（N ）11．计算机图形生成的基本单位是线段。

（ F ）12．一个逻辑输入设备可以对应多个物理输入设备。

（T ）13．DDA（微分方程法）是Bresenham算法的改进。

（ F ）14．光的强度计算公式通常表示为：I = 0.59I + 0.30I + 0.11I ( T )15．Bezier曲线具有对称性质。

（T ）16．Gourand光照模型能够即使出高光部位的亮度。

（F ）17．NURBS曲线方法不能够提供标准解析曲线和自由曲线的统一数学表达。

（ F ）18．Phong算法的计算量要比Gourand算法小得多。

（ F ）19．齐次坐标系不能表达图形中的无穷远点。

（F ）20．欧拉公式v – e + f = 2也适用于三维形体中的相关信息描述。

（T ）二．单选题1．下面关于反走样的论述哪个是错误的？（D ）A.提高分辨率；B.把象素当作平面区域进行采样；C.采用锥形滤波器进行加权区域采样；D.增强图象的显示亮度；2．多边形填充时，下述哪个论述是错误的？（ C ）A.多边形被两条扫描线分割成许多梯形，梯形的底边在扫描线上，腰在多边形的边上，并且相间排列；B. 多边形与某扫描线相交得到偶数个交点，这些交点间构成的线段分别在多边形内、外，并且相间排列；C. 在判断点是否在多边形内时，一般通过在多边形外找一点，然后根据该线段与多边形的交点数目为偶数即可认为在多边形内部，若为奇数则在多边形外部，而且不需考虑任何特殊情况；D. 边的连贯性告诉我们，多边形的某条边与当前扫描线相交时，很可能与下一条扫描线相交；3． 下面关于NURBS 的论述，哪个是错误的？（ B ）A. 可通过控制顶点和权因子来改变形状；B. 仅具有仿射不变性，但不具有透射不变性；C. 非有理B 样条、有理及非有理Bezier 曲线、曲面是NURBS 的特例；D. 可表示标准解析形状和自由曲线、曲面；4． 在光亮度插值算法中，下列论述哪个是错误的？（ D ）A. Gouraud 明暗模型计算中，多边形与扫描平面相交区段上每一采样点的光亮度值是由扫描平面与多边形边界交点的光亮度插值得到的；B. Phong 明暗处理模型中，采用了双线性插值和构造法向量函数的方法模拟高光；C. Gouraud 明暗模型和Phong 明暗处理模型主要是为了处理由多个平面片近似表示曲面物体的绘制问题；D. Phong 明暗模型处理的物体表面光亮度呈现不连续跃变；5． 下述关于Bezier 曲线]1,0[),(),(21∈t t P t P 的论述，哪个是错误的？ （ A ）A. P P P ==)0()1(21,在P 处)0(),1(21P P 的切矢量方向相同，大小相等，则)(),(21t P t P 在P 处具有G 1连续；B. P P P ==)0()1(21,在P 处)0(),1(21P P 的切矢量方向相同，大小相等，则)(),(21t P t P 在P 处具有C 1连续；C. 若保持原全部顶点的位置不变，只是把次序颠倒过来，则新的Bezier 曲线形状不变，但方向相反。

2011-2012学年第1学期2008级《高级语言程序设计》重修考试试题(B卷)考试时间：2012年04月班级学号姓名✧请将答案写在答题纸上，写清题号，不必抄题，字迹工整、清晰；✧答题纸和试题纸上都写上班级、学号和姓名，交卷时将试题纸、答题纸和草纸一并交上来。

✧每个题目不必给出对应的PAD图，但要添加必要的注释，程序命名和书写要规范。

一、[20分] 编写函数，实现按照如下公式计算的功能。

f(n)=0/(1*2!)+1/(2*3!)+2/(3*4!)+3/(4*5!)+…+n/((n+1)*(n+2)!)，其中n为自然数。

二、[20分] 编写bool函数，判断给定的整数数组a[n]中是否存在元素a[i] (0<i<n)，等于其前边的所有元素之和，即a[i]＝a[0]+a[1]+…+a[i-1]。

三、[20分] 编写一个递归函数，计算组成给定正整数n的所有数字之和。

例如：输入参数为1035，则返回结果应该为9（通过1+0+3+5=9得到）。

四、[20分] 构造一个表示教师的结构体（包含3个字段：姓名、性别、年龄），编写函数，读入M个教师的信息，存入一个结构体数组中，如下图所示。

图1 管理教师信息的结构体数组例如：一个教师的信息为Zhangsan、true、50，另一个教师的信息为Lisi、false、37。

五、[20分] 设有一个保存教师信息的单链表（每个结点包含4个字段：姓名、性别、年龄、后继指针），如下图所示。

构造该链表中一节的数据类型声明；编写函数，在给定链表上查找所有女教师的信息，并存储到指定文件output.txt中。

图2 管理教师信息的单链表第 1 页共1 页。