清华大学部分专业课试题（转）

zhouheng1212

  2005年试题
一、简单回答以下问题（共6小题，每小题5分，共30分）
1、什么样的解是线性规划的退化解，退化为什么会引起求解过程的循环？
2、用EXCEL求解线性规划并进行敏感性分析时，在敏感性分析表中，可以找到"递减成本"的数据，请解释什么是递减成本，写出其表达式，并解释递减成本的经济含义？
3、简述求解整数规划的分支定办法中"分支"与"定界"的含义？
4、简述求最大流问题的最小割-最大流定理。
5、简述求解无约束非线性规划的梯度法与共轭梯度法的异同。
6、a、b、c在什么范围内取值时，以下面矩阵为行对策人的赢得矩阵的二人零和对策问题的矩阵元素（1，1）是该矩阵的鞍点。
二、（20分）某企业使用四种化工原料生产六种化工产品，生产每种产品的投入产出系数见下表：
（表中的成本和价格的单位为万元/吨，最大、最小需求数量和原料可用数量的单位为吨）
每种产品的投入产出系数列在表中，例如生产一吨A产品需要0.5吨原料1，0.1吨原料2，0.2吨原料3，0.4吨原料4，其他产品需要的原料数可依此类推。原料的成本和可使用数量列在表的最后两列；产品的销售价格在表的最后一行。产品的产量应该大于最小需求量，同时也要小于最大需求量。构造的求销售利润最大的线性规划模型用EXCEL求解后的敏感性分析报告如下表：
可变单元格：
约束：
（1）该问题的最优解中应该有几个基变量（提示：应包括松弛变量中的基变量），根据敏感性分析表中提供的信息，判断那些变量是基变量？
（2）从表中可知：产品D的单位利润最高（34万元/吨），但它对目标池数的边际贡献却最小（递减成本为-0.1万元/吨）；产品C的单位利润最低（21万元/吨），但它对目标函数的边际贡献却最大（递减成本为12.3万元/吨），为什么会有这样矛盾的现象，请解释其中的原因？
（3）四种原料中哪种原料的影子价格最高，如果企业还可以从市场上获得这种原料，企业可以出的最高价格是多少？
（4）在保持最优基不变的前提下，你建议该企业应继续采购哪种原材料，采购多少可以使企业获得最大的收益？
（5）产品C价格在什么范围内变化时该问题的最优基保持不变？
（6）该企业正考虑生产一种新产品E，该产品计划售价为60万元/吨，需要0.7吨原料1，0.1吨原料2，0.2吨原料3和0.3吨原料4，是否应该生产这种新产品？ 三、（20分）某工厂要利用m种原料在T个月内生产n种产品。市场第t个月对第j（j=1……n）种产品的最大需求为 ,j产品的市场销售价格为
；生产单位j产品需要使用数量为
的第i（i=1......m）种原料，i原料的单位采购成本为
，每个月可使用的数量不能超过原料供应能力
；工厂需要使用q种设备生产n种产品，生产j产品需要使用数量为
的k(k=1……q)种设备的生产能力。工厂的第k种设备的最大加工能力限制为
；使用第k种设备单位生产能力的成本为
；当生产能力紧张时，允许工厂利用库存调节各个月份可能出现的供需之间的矛盾，第j种产品的库存费用为
。请为该厂构造一个求销售利润最大的生产优化线性规划模型。（注:  , , , , , , , 不随时间变化）
四、（20分）某连锁商业公司主要从事大型家用电器的分销业务，在一个城市设有4个零售商场，每个商场每月平均销售家用电器的数量见下表：
各个商场销售的电器需要由分销中心配送，因此该公司需要决策在什么地方建立分销中心。备选的地点有3个，在每个地点设立分销中心的固定成本见下表：
从各个备选地点供应各个商场的变动分销成本（元/每台）见下表：
该公司希望设计一个使分销成本（固定成本+变动成本）最小的建设方案，并考虑以下限制条件：
（1）最多设立两个分销中心；
（2）在地点A和地点B不能同时设分销中心；
请写一个满足上述要求的整数规划模型。
五、（15分）某公司计划用50万投资一项新产品开发，根据技术人员的周密分析，新产品开发成功的概率为90%，成功后每年可获利8万，如果开发失败则会失去全部投资。该公司的另一个选择是将这笔钱存入银行，每年可得利息3万。为降低投资风险，公司可聘请一投资咨询公司进行投资咨询，咨询公司收费为1.2万元。该公司以往200例咨询意见实施结果的统计资料见下表：

1、请画出该公司新产品开发的决策树
2、应用EMV准则分析公司是否应该投资；
3、与咨询相关的样本信息期望值是多少？完全信息期望值是多少？
六、（15分）某银行分理处经理需要确定周末需要的前台营业员人数。统计资料表明，周末的顾客到达时间间隔和营业员为顾客服务的时间都服从负指数分布，平均每分钟有2名顾客到达银行，营业员平均需要2分钟时间为一位顾客服务。银行在周末每增加一名营业员的平均成本为90元/小时。然而银行还需要考虑因排队时间过长而带来的损失，统计数据表明，顾客排队等待时间每增加1分钟会产生0.5元的与服务质量相关的损失（如银行信誉，顾客流失等造成的损失）。请问银行经理应安排多少营业员参加周末服务才可以使总成本最小化。不同服务台数量s和不同服务强度p对应的全部服务台忙的概率（即p（j≥s））见下表：
p       s=4         s=5         s=6         s=7
0.40      0.09         0.06        0.04        0.03
0.50      0.17         0.13        0.10        0.08
0.60      0.29         0.24        0.20        0.17
0.70      0.43         0.38        0.34        0.30
0.75      0.51         0.46        0.42        0.39
0.80      0.60         0.55        0.52        0.49
0.85      0.69         0.65        0.62        0.60
0.90      0.79         0.76        0.74        0.72
0.95      0.89         0.88        0.87        0.85
七、（15题）线性回归是一种常用的数理统计方法，这个方法要求用一条直线拟和二维平面上的一系列点
假定拟和直线方程的表达式为y=a+bx，然后用某种准则确定待定系数a和b，通常采用最小二乘法，但也可以采用其他准则。请根据以下准则建立求解待定系数a和b的线性规划模型：
解：线性规划问题为：
                  
八、（15分）考虑资源最优分配的线性规划问题（P）可以写成以下形式：
max:   cx
s.t．   Ax≤b
        0≤x≤u
式中，c是产品的单位价格，b为可以使用资源的数量，u是市场对产品需求的上限，A矩阵是生产各种单位产品需要消耗各种资源数量的消耗矩阵，x是决定生产数量的决策变量。如果我们假定使用的资源还没有买入（b也为决策变量），令p＞0为各种资源的市场价格，问题p可以变为：
max:   cx-pb
s.t.   Ax-b≤0
    0≤x≤u, b≥0
1、证明新问题总有最优解；
2、令
代表p的对偶最优解，这里已经显性地表示出对偶最优解的值取决于b的取值，证明b的最优解值b*满足y*(b*)=p

zhouheng1212

2004年试题 一、是非选择题（每小题1分） 1、如果一个线性规划问题有可行解，就一定有最优解。（ ） 2、线性规划的原问题有可行解，则其对偶问题也一定有可行解。（ ） 3、一种资源的影子价格的大小可以衡量该资源的稀缺程度。（ ） 4、影子价格为零的资源并不意味着没有任何价值。（ ） 5、若非线性规划的可行域是凸集，则用梯度法找到的最优解是全局最优解。（ ） 6、非线性规划的最优解总可以在其可行域的边界上找到。（ ） 7、整数规划可行解的数目比线性规划少得多，因此比线性规划更容易求解。（ ） 8、整数规划的线性规划松弛问题的最优解可能是该问题的最优解。（ ） 9、最小费用流问题可以被描述为一个线性规划问题。（ ） 10、网络计划方法中的关键路径法实际是在寻找耗时最长的路径。（ ） 二、请从下面每个小问题中选出一个正确答案。 1、设x是线性规划的一个基本可行解，如果其中一个分量 =0，则： A）只有该解不退化时， 才可能是一个基变量 B）只有该解退化时， 才可能是一个基变量 C）无论该解是否退化， 一定是一个非变量； D）只有该解退化时， 才一定是一个非基变量； 2、已知某一求极大值的线性规划的最优目标函数值，如果加入一个新变量， A）只有是非负变量时，目标函数值会上升； B）只有是自由变量时，目标函数值才会上升； C）无论是什么变量，目标函数值不会下降。 D）无论是什么变量，目标都不会上升。 3、设一线性规划有最优解，某一约束为等式约束，则该约束对应的对偶变量： A）一定大于等于零；               B）一定小于等于零； C）一定等于零；                   D）以上都不对。 4、已知一运输问题，以下问题参数的修改，哪一种一定不会改变当前最优解的结果是： A）有的费用系数都乘10 B）所有的费用系数都加10 C）所有供应量和需求量都加10 D）所有供应量和需求量都 5、若要表达：选择A的前提是C必须入选， 以下哪个约束表达正确？ A）A+C≤1    B）A+C≥0 C）A-C=0      D）A-C≤0 注：A、C代表0-1决策变量 6、对一个求目标函数最大的混合整数规划问题，以下中不正确的是： A）其线性规划松弛问题的最优解可能是该整数规划问题的最优解； B）该问题可行解的个数是有限的； C）任一可行解的目标函数值不可能大于其线性规划松弛问题的目标函数值； D）该问题可行解中可能存在不取整数值的变量。 7、以下关于动态规划的陈述中不正确的是 A）使用动态规划必须满足无后效性原则； B）动态规划可求解多阶段优化问题。 C）动态规划的损益函数要满足可分离性、单调性和递推性； D）动态规划只能倒推求解。 8、M/M/N/K表示的排队系统中： A）顾客到达符合正态分布，服务时间符合负指数分布，系统队列容量为N，有K个服务台； B）顾客到达符合Poisson分布，服务时间符合指数分布，有N个服务台，系统队列容量为K； C）顾客到达符合负指数分布，服务时间符合泊松分布，系统队列容量为K，有N个服务台； D）顾客到达符合负指数分布，服务时间符合泊松分布，有K个服务台，服务队列容量为N； 9、运用决策分析方法进行决策分析时： A）用最大期望值准则确定的方案一定时最好方案； B）用最大期望值准则与效用期望值最大准则确定的方案是等价的； C）决策者的风险偏好不同，用效用期望最大准则确定的方案可能会不同； D）决策者的风险偏好不同，用最大期望值准则确定的方案可能会不同。 10、以下命题中，不正确的是： A）矩阵对策问题一定存在混和策略意义睛的最优解； B）矩阵对策问题的赢得矩阵中不一定存在鞍点； C）指派问题可以描述为一类特殊线性规划问题，但它的任何可行解都严重退化； D）标准运输问题可以描述为一个线性规划问题，其约束系数矩阵是一个满秩的矩阵。 三、（15分）下面的运输表中，1、2、3为需求点，一、二、三为供应点，表中的数为运输成本，请用运输表求解该运输问题。 四、（15分）超级市场上班的员工数量如果能随商城客流量大小而调整，则可在满足一定服务质量的前提下，减少人力资源的投入，从而可以降低运作成本。某超市根据统计，在一个典型工作日，每个时间段需要的值班员工数量如下： 9：00-11：00   30人 11：00-13：00   50人 13：00-15：00   40人 15：00-17：00   45人 17：00-19：00   60人 19：00-21：00   40人 超市员工可以选择上全时班（连续工作8小时）或上半时班（连续工作4小时），但上半时班的员工人数不能超过每一时段使用员工总数的50%。超市按工作小时付给员工工资，上全时班和上半时班的小时工资率相同，请为该超市构造一个数学模型，使每天使用的员工费用最小。 五、（20分）某工厂使用四种原料生产六种产品，生产每种产品的投入产出系数及其他经济参数见下表： （表中的成本和价格的单位为万元/吨，最小需求数量和原料可用数量的单位为吨） 每种产品的投入产出系数列在表中，例如生产一吨产品A需要0.6吨原料1，0.3吨原料3，0.2吨原料4，其他产品需要的原料数可依此类推。原料的成本和可使用数量列在表的最后两列；产品的销售价格在表的最后一行。产品的产量应该大于最小需求量，同时也要小于最大需求量。构造的求销售利润最大的线性规划模型用EXCEL求解后的敏感性分析报告如下表： （1）根据模型的解判断哪些变量是基变量，哪些是非基变量，简单说明你的理由； （2）当前解中哪个产品对目标函数的边际贡献最大，哪个产品对目标函数的边际贡献最小； （3）产品B的价格在什么范围内变化时该2该的最优基保持不变？ （4）原料3的影子价格是多少？如果市场上还可以以每吨22万元的价格采购到原料3，该工厂是否可以考虑继续采购原料3，在影子价格不变的前提下最多还能采购多少？ （5）该厂正考虑生产一种新产品E，该产品计划售价为50万元/吨，需要0.4吨原料2，0.7吨原料3，0.3吨原料4，是否应该生产这种新产品？ 五、（20分）一个制造企业使用一种原材料制造两种产品A和B，一个单位的原材料的采购成本为C元，可以制造出k1单位的产品A和k2单位的产品B，如果企业生产出x1单位的产品A，可以在市场上以 的价格将其售出；如果企业生产出x2单位的产品B，可以在市场上以 的价格将其售出。企业最多能够从供应商处得到的原材料的数量Z单位。企业希望能构造一个非线性规划使企业获得的利润最大化。 1、写出该问题的数学模型； 2、写出该问题的最优条件（K-T条件） 3、请解释本问题的拉格朗日乘子（对偶解）的经济含义。 六、（20分）一架货机有三个货舱；前舱，中舱和后舱，每个货舱货运能力的限制如下表： 货机需要运送下列四种货物： 为保持飞机平衡，各个货舱装货重量与能力的比例必须相同（例如，如果前舱装6吨货，占实际装货能力的50%，则中舱必须装9吨，后舱必须装5吨，也要占能力的50%）。根据运输规定，每个货仓最多只能装载两种货物，各个货舱可以按任何比例混装两种货物，请构造一个混合整数规划模型，使一架飞机在满足装载限制的前提下获得的运费最大化。 七、（20分）请用动态规划求解下面的规划问题 八、（10分）考虑下面的线性规划问题： 令 为该问题的最优解，假定 ，证明 是一个凹函数（如果定义在 上的函数f满足 ，则称该函数为凹函数）。

zhouheng1212

2002年试题 一、（15分）某工厂要利用m种原料在T个月内生产n种产品。市场第t个月对第j（j=1……n）种产品的最大需求为 ,j产品的市场销售价格为 ；生产单位j产品需要使用数量为 的第i（i=1......m）种原料，i原料的单位采购成本为 ，每个月可使用的数量不能超过原料供应能力 ；工厂需要使用q种设备生产n种产品，生产j产品需要使用数量为 的k(k=1……q)种设备的生产能力。工厂的第k种设备的最大加工能力限制为 ；使用第k种设备单位生产能力的成本为 ；当生产能力紧张时，允许工厂利用库存调节各个月份可能出现的供需之间的矛盾，第j种产品的库存费用为 。请为该厂构造一个求销售利润最大的生产优化线性规划模型。（注:  , , , , , , , 不随时间变化） 二、（20分）已知线性规划为： 某厂使用甲、乙、丙三种原料生产A，B两种产品，每生产一吨A产品需要原料甲0.6吨，原料乙0.2吨，原料丙0.3吨，每生产一吨B产品需要原料甲0.3吨，原料乙0.6吨，原料丙0.4吨。三种原料的成本分别为18、15、12元/吨；可使用的数量分别为30、20、40吨；每生产一吨A、B产品的生产成本为5和3元；它们的市场销售价格分别为37和42元（参数见下表） 构造的求销售利润最大的线性规划模型用EXCEL求解后的敏感性分析报告如下表： 构造的球销售利润最大的线性规划模型用EXCEL求解后的敏感性分析报告如下表： （1）请写出该问题的数学模型及其对偶问题； （2）如果原料甲和原料乙各增加10吨，当前基是否仍保持最优，如果各减少10吨呢？ （3）A、B产品的价格在什么范围内变化时该问题的最优基保持不变？ （4）请根据每感性分析报告说明哪种原料最紧缺，哪种原料最不紧缺，并说明你的理由； （5）该厂正考虑生产一种新产品C，该产品计划售价为50元，生产成本为7元，需要0.4吨原料甲，0.7吨原料乙，0.3吨原料丙，问：是否应该生产这种新产品？ 三、（15分）在下面的运输表中，1、2、3、4为需求点，一、二、三、四为供应点，小方格中的数字为运输成本，目前已得到一个可行解。 1、表中的解是否为基本解？ 2、表中的解是否为最优解？ 3、写出该运输问题的表达式。 4、若费用系数 由11增至14，表中的解是否仍为最优解？若不是，则求出新的最优解。 四、（20分）房地产开发商面临一个五年开发规划问题：他目前已经得到三个房地产开发项目的许可，然而由于资金和建设力量的限制，必须确定一个最优的开发计划。三个房地产开发项目的数据如下： 项目收益应在项目建成之后获得，即：若在第一年建设项目A，项目一年建成，则收益在第二年开始获得。建设时间超过一年的项目，其建设投资平均分滩在建设周期内，开发商面临的其他限制为： （1）每年用于建设的资金不能超过6000万元； （2）每年可以使用的建筑工人总数最多为500人； （3）由于项目管理上的原因，每年只能允许1个项目开工，同时施工建设的项目不能超2项。 请为该开发商构造一个满足上述约束限制，并使五年内租金收益最大的整数规划模型。 五、（20分）一软件公司需要在自主开发一种微机上使用的会计软件和接受其他公司的委托进行办公自动化软件开发之间进行抉择。如果选择自主开发，根据过去的开发经验，开发一个会计软件需要投资20万元。如果软件开发得很成功（功能好于市场上已经存在的任何类似的产品，概率为20%），他们开发的软件产品可能以100万元的价格买给一个大的软件公司；如果比较成功（好于部分市场产品，概率为60%），价格将降为50万元；如果不成功（概率为20%），则无法卖出该产品。公司若决策接受其他公司的委托开发办公自动化软件，则可从客户支付的软件开发费中获得20万元利润。该软件公司还可以出2万元聘请一个咨询公司就该产品的开发问题进行咨询。根据以往的统计，该咨询公司咨询准确性的概率（P（咨询意见|成功状态））如下表： （1）画出完整的决策树，并根据最大期望值方法找出最优决策路线。 （2）是否请咨询公司进行咨询，其咨询意见的样本信息期望值是多少？ （3）本问题的完全信息期望值是多少？ （4）总结和比较有咨询和无咨询时该公司的最优决策的风险特征。 六、（10分）设有线性规划问题（P）： 。 （1）写出它的对偶问题。 （2）设 是（P）的最优解，证明存在 ，对所有j满足： 是矩阵A的第j个列向量， 分别为x,c,l,u的第j个分量。                           2003年试题 一、（30分）请从下面每个小问题中选出一个正确答案（每小题3分）： 1、设x是一个线性规划问题的基本可行解，如果其中一个分量 >0，则：（） A）无论解是否退化， 一定是一个基变量； B）只有解不退化时， 才是一个基变量； C）只有解退化时， 才是一个基变量； D） 是非基变量 2、已知某一求极大值的线性规划的最优目标函数值，如果加入一个新约束，（） A）只有新约束是大于等于约束时，最优目标函数值会下降； B）只有新约束是小于等于约束时，最优目标函数值会下降； C）无论加入什么样的约束，最优目标函数值不会上升； D）无论加入什么样的约束，最优目标函数值不会下降。 3、设一线性规划有最优解，其对偶解的某一个分量大于零，则该分量对应的约束（） A）可能是紧约束，也可能是松约束； B）只能是紧约束，且当右边项增加时，其目标函数值下降； C）只能是松约束，且当右边项发生变化时目标函数值不会变化； D）不可能是松约束，且当右边项增加时，其目标函数值上升； 4、以下关于对偶解的陈述中正确的是：（） A）对偶解的经济含义是它所对应的变量的改变量与目标函数改变量的比值； B）实际成本大于零的资源的对偶解可能为零； C）一种资源的对偶解总大于为该资源付出的价格； D）一种资源的对偶解总小于为该资源付出的价格； 5、设线性规划问题 有最优解，且最优解值Z>0；如果c和b分别被v乘，则改变后的问题（） A）也有最优解，最优解值仍为Z； B）也有最优解，最优解值大于Z； C）也有最优解，最优解值小于Z； D）无法判断有无最优解。 6、已知一运输问题，并已求得该运输问题的最优解，以下几种对该问题参数的修改，哪一种一定不会改变当前最优解的结构。 A）所有的费用系数都加10； B）所有的费用系数都乘10； C）所有供应量和需求量都加10； D）所有供应量和需求量都乘10。 7、以下关于整数规划的命题中不正确的是： A）用分支定界法求解整数规划问题时首先要求解放松整数要求的线性规划松弛问题； B）整数规划解的数目比线性规划少得多，但整数规划问题也可能有无数多个可行解； C）求解整数规划问题要比求解线性规划问题难得多； D）分支定界方法不能求解有连续变量的混合整数规划问题； 8、对一个求目标函数最大的混合整数规划问题，以下命题中不正确的是（ ） A）其线性规划松弛问题的最优解可能是该整数规划问题的最优解。 B）该问题可行解的个数是有限的； C）任一可行解的目标函数值不可能大于其线性规划松弛问题的目标函数值； D）该问题可行解中可能存在不取整数值的变量。 9、以下关于网络计划方法的命题中，正确的是：（ ） A）关键路径法的实质是求网络图中耗时最长的路径。 B）网络计划网络图中不可能有多于一条的关键路径。 C）网络计划方法中引入的虚拟活动不可能位于关键路径上； D）减少非关键路径上活动的完成时间可以减少项目完成时间。 10、以下关于矩阵对策问题的命题，不正确的是：（ ） A）矩阵对策问题可能不存在纯策略意义下的最优解； B）矩阵对策问题可以表述为两个互为对偶的线性规划问题； C）矩阵对策问题可能存在混和策略意义下的最优解； D）矩阵对策问题不可能存在多个最优解。 二、（15分）已知一个求最大化的线性规划问题迭代到某一步的单纯形表如下： 问：a,b,c,d满足什么条件时： （1）原问题的解可行，对偶问题的解还不可行； （2）原问题的解是唯一不退化的最优解； （3）原问题的解为最优解，但退化； （4）原问题无界； （5）原问题无解（不可行）。 三、（15分）求解下面的最小费用流问题： 四、（15分）已知一非线性规划模型如下： 试写出该问题的K-T条件，并利用K-T条件求解该问题。 五、（20分）线性回归是一种常用的数理统计方法，这个方法要求用一条直线拟和二维平面上的一系列点 。假定拟和直线方程的表达式为y=a+bx，然后用某种准则确定待定系数a和b，通常采用最小二乘法，但也可以采用其他准则。请根据以下准则建立求解待定系数a和b的线性规划模型：                    六、(25分)万佳公司主要生产和销售复印机，影响复印机销售量的主要因素之一是公司能否提供快捷的维修服务。根据历年统计表明，如果维修服务机构的距离在200公里之内，销售量将会明显的提高，下表是华北地区四个主要城市在不同服务条件下一年销售复印机数量的预测。 每台复印机的销售利润为1万元，在每个城市设立一个服务机构每年的平均费用为80万元，各个城市之间的距离如下表所示： 请根据造能使该公司年利润最大的整数规划问题。（只写模型，不必求解） 七、（25分）一计算机芯片厂生产的某种芯片是以10个芯片为一个批次通过两道主要工序生产出来的。大量统计表明，一个批次的芯片经过生产的第一道工序的一次加工后会有80%的批次的产品合格率为90%，有20%的批次的产品合格率为50%，合格率为90%的批次下一道工序的加工成本为1000元，而合格率为50%的批次的下一道工序的加工费将高达4000元。为避免质量差的批次进入下一道工序，工厂还可以选择以1000元的成本将芯片重新在第一个工序中再加工一次。经两次加工后的产品的合格率将稳定在90%。芯片厂还有另外一种选择，即从每批中抽检一个产品，根据抽检结果决定该批次是直接进入下一道工序，还是在第一道工序中再加工一次。抽检一个产品的检查成本为100元。 （1）芯片厂希望每个批次的加工成本最小应如何决策，画出该问题的决策树； （2）计算与抽检相关的样本信息期望值； （3）计算该问题的完全信息期望值； （4）列出该问题最优决策的风险特征表。

wangqingqing123

LZ 辛苦了 呵呵
有没有2008年的环境微生物啊

man-friday

辛苦了~~
可惜没看到826信号的

zhouheng1212

2000年清华大学数字逻辑试题



数字逻辑部分（50分）
  1  (10分)
图1所示总线上接有8个TTL型驱动器和16个TTL型接收器。驱动器和接收器的功能表如图2所示，它们的主要有关直流参数为：
正常态下“1”输出电流IOH>=6mA
高阻态下输出漏电流IOZ<=20uA
正常态下“0”输出电流IOL>=24mA
数据端“1”输入电流IIL<=1.6mA
高阻态下数据端“0”输入电流IILZ<=40uA
请分析：驱动器能否可靠驱动接收器。
2  (16分)
在数字集成电路手册中，可常见到表达电路输出或输入电压状态变化的一些时序序号，请
说明以下表达输出电压变化的符号的意义。
  3  (24分)
① 设计一个能周期性地产生“*”序列信号的移位寄存器，该电路工作前要清零。记忆元件用正沿延迟型D触发器，附加门电路限用NAND电路。给出设计过程。
② 对本题①的移位寄存器电路，如果触发器的参数有：  =20ns、数据建立时间=10ns、数据保持时间=4ns、NAND的=6ns，请估算寄存器的最高工作频率。

zhouheng1212

一共9道大题，10分、15分、20分不等，过去一个月都，现在努力回忆一下吧：
1、一炮弹在最高点处爆炸分为两部分，一部分垂直下落，另一部分继续飞行。已知：垂直下落的时间19.6S，继续飞行的路程4000米，求炮弹发射点的距离。
2、求一个热力学循环的效率。
3、已知：某种和麦克斯韦分布形式相似（就是指数部分有变化）的速度分布，积分求速率分布、求空间分布，完全是数学积分问题。
4、已知一电磁波的E 、B 矢量，验证麦克斯韦方程组的正确性。（据我所知，麦克斯韦方程组已经考两年了，去年还考了相对论，但今年没考，建议大家复习一定要全面，这样的知识比较偏，但绝不会难！）
5、一电容器充电，求位移电流，求能量（就是坡印亭矢量计算公式）
6、一道分子动理学部分试题。记不住了，但不难。
7、8、好像也记不住了；
9、最后一道是完全超纲（课本上没有相关内容），刚体滚动问题，一个汽车后面有一个圆柱，半径r, 汽车以a加速，后面长L，问汽车运动的距离。

zhouheng1212

数字逻辑部分（50分）
  1  (10分)
图1所示总线上接有8个TTL型驱动器和16个TTL型接收器。驱动器和接收器的功能表如图2所示，它们的主要有关直流参数为：
正常态下“1”输出电流IOH>=6mA
高阻态下输出漏电流IOZ<=20uA
正常态下“0”输出电流IOL>=24mA
数据端“1”输入电流IIL<=1.6mA
高阻态下数据端“0”输入电流IILZ<=40uA
请分析：驱动器能否可靠驱动接收器。







  3  (24分)
① 设计一个能周期性地产生“*”序列信号的移位寄存器，该电路工作前要清零。记忆元件用正沿延迟型D触发器，附加门电路限用NAND电路。给出设计过程。
② 对本题①的移位寄存器电路，如果触发器的参数有： =20ns、数据建立时间 =10ns、数据保持时间 =4ns、NAND的 =6ns，请估算寄存器的最高工作频率。

[ 本帖最后由 zhouheng1212 于 2008-6-28 09:31 编辑 ]

zhouheng1212

共分编译原理和数据库两部分，各占50分，总分100分，时间120分钟
    BTW：今年座次没有按排名来，随便坐
    编译原理部分： （50Pts）
    1.判断 5Pts
    1) 交叉编译器是能够在多台目标机上运行的编译器
    5) S-型文法一定是L-型文法
    2.求DFA，语言如下： 5Pts
    w={a,b}* 其中a的数目为奇数，b的数目为3的倍数
    3.求上下文无关文法,语言如下：5Pts
    w={a^nb^m | n>=2m>=0}
    4.求正规表达式，语言如下：5Pts
    {a,b}*上的 vwv^R 其中|v|>0,且v^R代表v的逆反
    5.已知文法 S->aSb | aabb
    1) 问用自顶向下分析的话，需要向前看几个单词
    2）判断该文法是否LL(1)文法
    6.这个没记住...因为我放弃了55555 6 Pts
    7. 判断是否LL(1)文法，抱歉文法没记住，比较简单，跟书上例题差不多
    8.给你一个文法，然后画出了部分的项目集规范族，留几个空
    1) 填空
    2) 该文法是否LR(0)文法？是否SLR(1)文法
    这个也不难，也是跟书上题目相似，答案是不是LR(0)，是SLR(1)
    引入FOLLOW集后原本出现的移进-规约冲突都可以解决
    9.根据数据流图，一共有5个基本块
    已知B5出口处的活跃变量为空
    求B1，B2，B3，B4入口处和B4出口处的活跃变量集合
    数据库部分 （50Pts）
    1.解释下列英文缩写 4*4=16
    1)DDBMS 2)DML 3)XML (去年原题) 4)3NF
    2.问答题 4*6=24Pts
    1.关系数据库系统中，查询操作的作用是什么
    2.数据库系统中保证并发调度可串行性的封锁协议和时间戳协议有什么不同
    3.事务提交的标志是什么
    4.数据库系统中索引顺序文件组织的最大弊病是什么？如何改进？
    3. 观察下面两个SQL语句 10Pts
    1) SELECT COUNT(DISTINCT *) FROM person;
    2) SELECT COUNT(*) FROM
    (SELECT DISTINCT(*) FROM person);
    这两个语句的作用分别是什么？产生的结果是否相同？

zhouheng1212

清华大学2006年CS专业考研试题
计组部分
一、填空题
1. a,b为两个1位2进制数，Carryin为低位进位，Carryout为高位进位，用and,or写出带进
位的1位加法器的Carryout并化简，Carryout=____
2. 5段流水线分别为IF,__,EX,__,WB.
3. 一个串行程序可并行部分占%90，规模不变的情况下，串行程序并行化后加速比不超过
_______
4. 二进制补码1111 1111 1111 1111 1111 1111 1111 1011化为十进制后为_______
二、判断题
1.CISC计算机比RISC计算机指令多。
2.速度为10MIPS的计算机一定比速度为5MIPS的计算机快。
3.SRAM比DRAM的速度快，成本高。
4.SCSI硬盘与SATA硬盘的速度，价格比较.
5.PCI-Express与AGP都可用于显卡接口
6.SPECCPU 2000基准测试程序可用于测I/O性能。
7.IEEE 754是计算机中的二进制整数算术标准。
8.全相联与直接映象Cache的比较
9.INTEL P4功率小于10w
10.64位CPU一般比32位CPU快一倍
11.增加流水线段数可提高CPU频率
12.VHDL是硬件描述语言。
13.EPIC是VLIW的发展
三、简答题
1.试说明为何编译程序要进行如下优化
for(j=0;j<200;j++)
  {for(i=0;i<20;i++)
   {
   A[j]=A[j]+1;
   }
}
编译优化后
for(i=0;i<20;i++)
  {for(j=0;j<200;j++)
   {
   A[j]=A[j]+1;
   }
}
2.硬盘平均寻道时间为12ms，传输速率为10MB/s，磁盘控制器延时为2ms,则一个转速为72
00r/min的硬盘写1KB数据时间为多少?
3.为什么要设置二叉分支预测指令？画出2bit转移预测的状态图
数据结构
证明题:
1 证明在一棵满二叉树中分支B与叶子节点n0满足关系 B=2(n0-1)
2.证明，完全无向图中,两个顶点之间简单路径书目为:
  1 + A(n-2,1) + A(n-2,2) + ... + A(n-2,n-2)
其中A(m,n)是m取n的排列数。
作图题:
给了一个Dijkstra无向连通图的最小生成树算法描述，要你根据该描述作出最小生成树及
并查集的变化。
程序填空
给了一段排序算法，用静态链表描述的
1 问你这是什么排序算法（里面写着selectsort）
2 把挖去的5个空填上 （发现只有4个）
程序设计题
用链表表示的多项式
1 写类的描述
2 insert算法，如果相同指数合并，没有就插入
3 利用insert,给出多项式乘法的算法
操作系统
1 给出一个并发程序的描述:
semaphore X1=X2=Y=1;
int c1=c2=0;
procedure f1:
  p(X1)
  if (++c1 = 1) p(Y)
  v(X1)
  compute A
  p(X1)
  if (--c1 = 0) v(Y)
  v(X1)
procedure f2:
  p(X2)
  if (++c2 = 1) p(Y)
  v(X2)
  compute B
  p(X2)
  if (--c2 = 0) v(Y)
  v(X2)
问computeA和computeB各自能有多少并发执行，会不会出现饿死？
2 给出一个cpu的频率，使用基于时间片的轮转队列调度，并给出了参数。求调度的效率和
响应时间。
3 使用多级页表，给出一些参数，如虚实地址空间大小、页大小、页表项大小等，问:
a) 多级页表的优点
b) 如果页表限制在一个页面里，问有多少页表项？
c) 进程页表占用多少内存？
4 把一个UNIX文件卷复制到另一个磁盘上，问:
a) UNIX文件卷由哪几部分组成？
b) 只复制文件数据，包括目录之后，不能访问，为什么？
c) 终于搞好了之后，发现有重复的硬链接，为什么？
5 给出了一个使用pthread的程序代码，里面系统调用包括fork()，thread()，join()等等
，中间穿插print HELLO。问最后一共打印了多少个HELLO