湖南大学计算理论引论期末试题2006年秋本科试卷a-答案

湖南大学2006年数学分析一（16分）设()f x 在[]0,+∞内可微并且满足不等式0()ln (2)(0,).f x x x x ⎡⎤≤≤+ ∀∈+∞⎣⎦证明：存在一点(0,)ξ∈+∞使得'2()12f ξξ=-+二（16分）设,m n 为自然数，计算积分10(ln )n m t t dt ⎰.三（16分）设()f x 在(,)-∞+∞上具有二阶导数且''()0,f x >'lim ()0x f x α→+∞=>，'lim ()0x f x β→-∞=>,又存在一点0x ，使0()0f x <.证明方程()0f x =在(,)-∞+∞上有且只有两个实根.四（16分）令{}n a 和{}n η为正数数列，假设lim 0n n η→+∞=，且在(0,1)中有一个数c 使得对每个n 有1n n n a ca η+≤+成立，证明：lim 0.n n a →∞=五．（16分）令{}()n f x 为定义在(,)-∞+∞上的可导函数列，且存在常数0M >，对所有的n 和(,)x ∈-∞+∞有'()n f x M ≤成立.假设对(,)x ∈-∞+∞，有lim ()()n n f x g x →+∞=，则()g x 在(,)-∞+∞上连续.六（18分）已知22116n n π∞==∑.设221(),(01).n x f x x n∞==≤≤∑求证当01x <<时有2()(1)(ln )ln(1)6f x f x x x π+-+-=.七（18分）1）若22222222()0(,)00xy x y x y x y f x y x y ⎧- +≠⎪+=⎨⎪ += ⎩证明：(0,0)(0,0).xy yz f f ≠2）函数(,)z z x y =由方程222()zx y z yf y ++=确定，f 是可微函数，证明222()22.z zx y z xy xz x y∂∂-++=∂∂八（16分）在曲面2221x y z ++=上求点0000(,,)P x y z ，且0000,0,0x y z ≥≥≥使该点处曲面的切平面与三坐标面围成的四面体的体积最小.九（18分）设()f u 有连续的一阶导数，计算11()()x xf dydz f dzdx zdxdy y y x y ∑++⎰⎰ 其中∑是22f x z =+，228y x z =--所围成立体的外侧.湖南大学2007数学分析一（18分）计算：（1）231lim ;2nn k k n n k→∞=++∑（2）n →∞二（16分）设111,2(1),1,2,n n x x x p n +==+>=L ，证明 数列{}n x 收敛.三（16分）设()f x 在[],a b 上连续，在(),a b 内可导，且0b a >>，证明：存在(),,a b ξη∈使得22''()().3a ab b f f ξηη++=四（16分）确定下面函数的连续区间20ln(1)().yx g y dx x+∞+=⎰五（16分）设()n f x 在[],a b 上连续(1,2,)n =L ，且{}()n f x 在开区间(,)a b 内一致收敛于()f x .证明()f x 在闭区间[],a b 上一致收敛.六（18分）设()f t 是[]0,1上的连续函数，令1(,)().F x y f t x y t dt =+-⎰其中,x y 满足221x y +≤，求二阶偏导数xx F 和yy F .七（16分）求函数22221111()arctanln 22ln 22arctan(1)arctan(1)24422x f x x x x x x x x=+-+-++---+-关于x 的幂级数展开式和收敛半径.八（16分）计算积分()(ln()ln .Dx y x y y I ++-=其中区域D 为0,1,x x y y x =+==所围成的三角形区域. 九（16分）设(,)f x y 在区域:12,12C x y -≤-≤上具有二阶连续偏导数，(1,1)0f =，且在点(1,1)达到极值.又设22(,),(,),l lf x y M x y G x y-∂≤∈∂∂ 其中02l ≤≤.取区域:01,01D x y ≤≤≤≤，试证：7(,).12DI f x y dxdy M =≤⎰⎰湖南大学2008数学分析一（16分）设实数列{}n x 满足20()n n x x n --→ →∞.证明1lim0.n n n x x n-→∞-=二（16分）设函数()f x 在()0,1内有定义，且有()x e f x 和()f x e -为()0,1内的单调递增函数. 证明()f x 在()0,1内连续.三（16分）设函数()f x 在[]0,1上可微，且令'01sup ()x f x C <<=<∞证明，对任何正整数n ，有1100(/)().2n j f j n Cf x dx n n-=-≤∑⎰ 四（16分）计算积分sin cos .Dy yI dxdy y=⎰⎰其中D 是由直线y x =与抛物线2x y =所围成的区域.五（16分）证明1()2().Sf ax by cz dxdy c du -++=+⎰⎰⎰其中2222:1,0S x y a b +≤+≠ 六（16分）求()g 'α，设()1g +∞α=⎰七（22分）设函数列()nx n f x n xe α-=，当参数α取什么值时，有 （1） 函数列在闭区间[]0,1上一致收敛。

学院专业班级学号学生姓名计算机科学与技术专业2006级《计算机网络原理》课程考核试卷参考答案试卷 A （A/B/C）考试方式闭卷（闭卷/开卷）考试时间（120分钟）题号一二三四五六七八总分得分一、选择题（在每个小题四个备选答案中选出一个正确答案，填在题末的括号中）（本大题共 20 小题，每小题 1 分，总计 20 分）1. A2. A3. D4. B5. B6. A7. D8. B9. C 10. C二、填空题（本大题共 12 小题，每空 1 分，总计 30 分）1. WAN、MAN、LAN、HAN或PAN2. 传播3. 100、10Mbps、基带传输、双绞线4. 交换机端口、网卡（或主机）5. 广播、端口、MAC地址、网络层协议6. 隐藏终端、RTS/CTS7. IP地址、端口、套接字(Socket)三、简答题（本大题共6小题，总计分30分）1.应用层：定义用户需要的各种网络应用的信息交互协议。

表示层：定义两个端系统之间交换的信息在计算机网络中传输时的格式会话层：在计算机网络中两个端系统之间建立、组织和协调其交互（会话）传输层：在计算机网络中两个端系统之间传送以报文为单位的数据网络层：在计算机网络中两台主机之间传送以分组或包为单位的数据数据链路层：在两个相邻节点间的线路上，无差错地传送以帧为单位的数据物理层：为两个相邻节点提供一个物理连接，将信息以比特流方式在通信线路上传送。

每一层的名称各0.5分，基本功能各0.5分2. 答：There are ten 4000 Hz signals. We need nine guard bands to avoid any interference.The minimum bandwidth required is 4000 ⋅ 10 + 400 ⋅9 =43,600 Hz. （按计算步骤给分和扣分，每个步骤1分）3. 答：The upstream bandwidth is 37 MHz.Using QPSK with 2 bits/Hz, we get 74Mbps upstream.//4进制的The downstream bandwidth is 200 MHz.Using QAM-64, this is 1200 Mbps.//64进制（每个步骤1分）4.答：The output is 011110111110011111010.（2分）5. 答：LH LH LH HL HL HL LH HL LH HL6. 答：Let t = 0 denote the start of transmission. At t = 1 msec, the first frame has beenfully transmitted. At t = 271 msec, the first frame has fully arrived. At t = 272 msec, theframe acknowledging the first one has been fully sent. At t = 542 msec, the 得分得分得分应用层表示层会话层传输层网络层数据链路物理层学院专业班级学号学生姓名acknowledgement-bearing frame has fully arrived. Thus, the cycle is 542 msec. A total of kframes are sent in 542 msec, for an efficiency of k/542. Hence(a) k = 1, efficiency = 1/542 = 0.18%(b) k = 7, efficiency = 7/542 = 1.29%(c) k = 4, efficiency = 4/542 = 0.74%（每小题2分）7. 答：For a 1-km cable, the one-way propagation time is 5 μsec, so 2τ = 10 μsec. To makeCSMA/CD work, it must be impossible to transmit an entire frame in this interval. At 1Gbps, all frames shorter than 10,000 bits can be completely transmitted in under 10 μsec,so the minimum frame is 10,000 bits or 1250 bytes. （按计算步骤给分和扣分，每个步骤1分）8.答：直通方式：接收到目的地址后立刻查询转发表进行转发。

湖南大学2006年招收攻读硕士学位研究生446《管理学》试题评分标准一．简答题（共50分）１．简述管理过程学派的基本观点（6分）参考答案：（1）管理是一个过程，即让别人和自己去实现既定目标的过程。

（2）管理过程的职能有五个，即计划工作、组织工作、人员配备、指挥（指导与领导）和控制。

（3）管理职能具有普遍性。

（4）管理应具有灵活性。

２．简述学习型组织的含义及其特点。

（7分）参考答案：（1）所谓学习型组织是指更适合人性的组织模式。

这种组织由一些学习团队形成社群，他有崇高而正确的核心价值、信心和使命，具有强韧的生命力与实现共同目标的动力，不断创新，持续蜕变（2）学习型组织必须具有五项修炼的技能，即“自我超越”，改善心智模式，建立共同愿景，团队学习和系统思考。

（3）学习型组织具有五大特点：一是精简，组织机构不重叠；二是扁平化，管理层次少；三是有弹性，对变化能及时作出反应；四是不断自我创造，在发展中不断有新思路；五是善于学习，个人、团队、企业都善于接受新事物。

３．简述目标管理的优缺点。

（6分）参考答案：任何事物都是利弊兼备的，目标管理也不例外。

目标管理在全世界产生很大影响，但实施中也出现许多问题。

因此必须客观分析其优点和缺点，了解其利弊，这样就可以兴利除弊，把目标管理的优势尽可能的充分发挥，而将其弱点一直到最低限度。

（1）优点：①促成了管理的改进，使组织的目标性增强，有助于绩效的改进；②有助于改进组织结构和职责分工③有助于调动员工的主动性、积极性、创造性，具有激励作用（2）缺点：①目标难以制定②目标商定和宣讲可能增加管理成本③存在着不灵活的危险④奖惩不一定都能和目标成果相配合，很难保证公正性，削弱了目标管理的效果４．简述战略管理过程及基本步骤。

（7分）参考答案：（1）战略管理过程，一般指主要是战略分析、选择、实施以及评价和调整的过程。

（2）战略管理包含四个关键要素：战略分析----了解组织所处的环境和相对竞争地位；战略选择----战略制定、评价和选择；战略实施----采取措施发挥战略作用；战略评价和调整----检验战略的有效性。

一、解答题1.机器调度问题。

问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。

每件任务的开始时间为s i，完成时间为f i，s i<f i 。

[s i，f i]为处理任务i 的时间围。

两个任务i，j重叠指两个任务的时间围区间有重叠，而并非指i，j的起点或终点重合。

例如：区间[1，4]与区间[2，4]重叠，而与[4，7]不重叠。

一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。

因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。

最优分配是指使用的机器最少的可行分配方案。

问题实例：若任务占用的时间围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法）画出工作在对应的机器上的分配情况。

3. 单源最短路径的求解。

问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。

另外，还给定V中的一个顶点，称为源。

现在要计算从源到所有其它各顶点的最短路长度。

这里路的长度是指路上各边权之和。

这个问题通常称为单源最短路径问题。

解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。

请将此过程填入下表中。

110030maxint10-{1}初始dist[5]dist[4]dist[3]dist[2]uS迭代7. 最长公共子序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。

用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。

其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。

当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。

故此时C[i][j]=0。

其它情况下，由最优子结构性质可建立递归关系如下：00,0 [][][1][1]1,0;max{[][1],[1][]},0;i ji ji jc i j c i j i j x yc i j c i j i j x y⎧==⎪=--+>=⎨⎪-->≠⎩在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。

期末考试试卷（A）卷一、填空题（每小题2分，共20分）1、字母表∑，用∑*表示∑上所有有穷长的串集合，∑*称为∑的①。

2、设z=abc，则z的固有头是①。

3、如何由语言基本符号组成程序中各个语法成分（包括程序）的一组规则叫①。

4、设∑＝{a,b}，∑上的正规式(a|b)(a|b) 相应的正规集为①5、NFA的映象f是从"状态×字"映射到"状态子集"，f为①值函数。

6、LR分析是按规范句型的①为可归约串。

7、结点的①属性值由该结点的兄弟结点和父结点的属性值计算。

8、如果分析树中一结点的属性b依赖于属性c，那么这个结点的属性b的语义规则的计算必须在定义属性c的语义规则的计算①。

9、对于栈式符号表，引入一个显示嵌套层次关系表- ①表，该表总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。

10、任一有向边序列n1 → n2,n2 → n3,…,nk-1 → nk为从结点n1到结点nk的一条通路。

如果n1=nk，则称该通路为①。

二、单项选择（每小题2分，共14分）1、乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。

其中3型文法也称为（）。

A．上下无关文法 B.正规文法C．上下文有关文法 D.无限制文法2、生成非0开头的正偶数集的文法是（）。

A． Z::=ABC B. Z::=ABCC::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|ε B::=BA|B0|0A::=1|2|3|…|9 A::=1|2|3|…|9C. Z::=ABC|2|4|6|8D. Z::=ABC|2|4|6|8C::=0|2|4|6|8 C::=0|2|4|6|8B::=BA|B0|0 B::=BA|B0|εA::=1|2|3|…|9 A::=1|2|3|…|93、简单优先分析法从左到右扫描输入串,当栈顶出现（）时进归约。

A.素短语B.直接短语C.句柄D.最左素短语4、同心集合并有可能产生新的（）冲突。

湖南大学课程考试试卷课程名称： 计算理论引论 ；试卷编号： ；考试时间：120分钟一 单选或填空题（10*3 = 30％） 下列叙述正确的是（ ） A.如果DFA 不接受任何字符串，则该机器识别的语言为{ε}. B.如果DFA 不接受任何字符串，则该机器识别的语言为φ. C.一个DFA 可以没有起始状态. D.一个DFA 的起始状态不能和接受状态相同. 2.下述（目前为止）肯定不正确的是（ ） A ．NP P ⊆ B. P NP ⊆ C.SAT 是NP 完全的 D.SAT 是NP 难的 3.下图中,存在的最大团顶点数为____ A.1 B.3 C.4 D.5 4.识别语言{0n 1n | n ≥ 0}的文法为__________5.下述表达不正确的是（ ）A.所有的RL 均是CFLB.所有的RL 均是图灵可判定的C.所有的CFL 均是图灵可判定的D.若语言A 是图灵可判定的,则A 和A 不全是图灵可识别的6.背包问题:max: p 1x 1+p 2x 2+…+p n x nSt: w 1x 1+w 2x 2+…w n x n <m (x i = 0或1)用动态规划在O (nm )时间解决，背包问题属于____问题.A. PB. NPC.NP 完全7.若判断某语言A 的多带图灵机所花费的时间为n +log n ,则判定问题A 的时间复杂度为（ ）A. O (n )B. O (log n )C.O (2n )D.O (n 2)8.若有A ≤ m B ,则下述叙述正确的是（ ）A.若B 可判定，则A 也可判定B.若B 可判定，则A 也不可判定C.若B 不可识别,则A 也不可识别D.A 和B 间的可判定性不存在任何关系9.若图灵机的当前格局为uaq i bv ,其状态转移函数为),,(),(L c q b q j i =δ,则下一格局为_______.10.若一个关系是自反,对称和传递的,则该关系为_____关系.二 DFA 的形式描述为({q 1,q 2,q 3,q 4},{u,d}, δ, q 3,{ q 3}),其中δ在下表中给出.试. (13%)三 (10%) 将下述公式转换为乔氏范氏S→AA | 0A→SS | 1四给出产生语言A={a i b i c k| i≥0,k≥0}的上下文无关文法，并判断其是否歧义.(10%)五证明：若A和A均为图灵可识别的，则A为图灵可判定的.(10%)六判断下述公式的可满足性，并说明原因.(13%)(x∨y)∧(x∨y)∧(x∨y)七令CONNECTED={<G>|G是连通的无向图},证明：CONNECTED P.(7%) 八证明：上下文无关文法（或语言）在交运算下不封闭.(7%)。

湖南省2006年普通高等学校对口招生考试计算机应用类专业综合知识参考答案一、单选题（共30小题，每小题2分，共60分）二、多选项题（共10小题，每小题3分，共30分）三、基本操作题（共6小题，每小题10分，共60分1、（1）执行菜单命令：“格式”→“段落”；或右击某段落或选项定的多段，执行快捷菜单命令“段落”。

（3分）（2）缩进和间距，中文版式。

（2分）（3）左对齐、右对齐、居中、两端对齐、分散对齐（答对1个给1分，顺序不限，共5分）2、自动筛选、高级筛选（二者可以交换位置）、数据、自动筛选、B（或第二列）（每空2分，共10分）3、图片、F5、幻灯片放映、文件、打印内容（每空2分，共10分）4、网络基本操作：（1）白橙、橙、白绿、绿（每空1分，共4分）（2）568B、568B （每空1分，共2分）（3）直通双绞线、交叉双绞线（每空2分，共4分）5、（1）index on 价格tag dh (5分)（2）copy structure to sp2 （5分）6、（1）⑤、③、⑦、④、⑧（每空1分，共5分）（2）先询问、观察再进行技术诊断先分析考虑再动手操作先软件后硬件先共用后专用先做板卡级检修再做部件检修先检查外设再检查主机严禁带电插拨不要贸然通电（每答对一种得一分，最多得5分）四、程序设计题（共3小题，每小题15分，共45分）五、综合应用题（共5小题，每小题15分，共75分）1、（1）②、⑤、③、①、④（每空2分，共10分）（2）利用PowerPoint的“打包”向导，将演示文稿所需的所有文件与字体文件打包在一起，生成pnpsetup.exe包文件，将生成的包文件pnpsetup.exe拷贝到目标计算机，双击pnpsetup.exe 文件，按提示操作即可。

（5分）2、（1）非对乐用户数字环路、1、8 （每空1分，共3分）（2）连线略（有6根线，每根线1分，共6分）（3）192.168.1.2 192.168.1.3 (每个地址1分，共6分) 255.255.255.0 255.255.255.0192.168.1.1 192.168.1.13、（1）②、①、⑤、③、⑦、④、⑥（每空1分，共7分）（2）数据链路层、物理层、数据链路层、物理层（每空2分，共8分）4、（0.22+（tminute - 3 ）* 0.1）（5分）val(.label3.caption), val(.label.caption) （5分）report from teleph environment preview （5分）5、（1）场振荡电路或扫描电路故障，无场输出。

2006年（秋）笔试试卷参考答案及解析一、选择题I．计算机基础知识（1）C）【解析】Pentium 4对应的处理器型号为5**和6**；Pentium M对应的处理器型号为7**；Pentium D对应的处理器型号为8**到9**。

（2）B）【解析】PCI Express是新一代的总线接口，PCI Express采用了目前业内流行的点对点串行连接，相对于传统PCI总线在单一时间周期内只能实现单向传输，PCI Express的双单工连接能提供更高的传输速率和质量，它们之间的差异跟半双工和全双工类似。

PCI Express是下一阶段的主要传输总线带宽技术，至今依然被看好的AGP8X的性能与PCI Express在性能上的差距虽然不是太明显，但是随着PCI Express的完善，其差距将是不言而喻的。

（3）C）【解析】并非任何负数的补码和原码都不相同，比如负数中-64的原码和补码均为11 000 000，故选项C）错。

（4）D）【解析】+0与-0在补码中只有一种表示方式00000000，而原码中-0表示为10000000，故选项D）不正确。

（5）B）【解析】根据题意，阶符为正，阶码为4，数符为负，尾数为0.01001101，即0.0009625，故真值为-9.625，是规格化数。

（6）D）【解析】选项D）中，00110101B如果视为压缩BCD码则应为35。

故其错误。

（7）A）【解析】表达式的右半部分化简后发现是左部分的非，故其结果肯定为0，选项A）正确。

（8）C）【解析】CPU只能对读入内存中数据进行操作，故要编辑一个存于优盘上文件，必须先读入RAM中才能进行。

（9）D）【解析】地址总线是专门用来传送地址的，由于地址只能从CPU传向外部存储器或I/O 端口，故选项A）错误；由于数据总线中数据的含义是广义的，它可以是真正的数据，也可以指令代码或状态信息，有时甚至是一个控制信息，因此，在实际工作中，数据总线上传送的并不一定仅仅是真正意义上的数据，所以选项B）错误；控制总线用来传送控制信号和时序信号。

一、单项选择题（每空2分，本题共20分）1．集合A DFA={<B,w>|B是DFA，w是串，B接受w}可用来（A）。

A、描述“DFA B 是否接受输入w”这一问题B、解决“P=NP？”问题C、计算语言A DFA时间复杂度D、计算语言A DFA的空间复杂度2．一个集合在条件（ D ）下是可数的。

A、该集合为无限集合B、组成该集合的元素是实数C、该集合的规模大于自然数集合的规模D、该集合是一个有限的集合3．对于一个语言（ D ）的说法是正确的。

A、它是一个序列B、它是一个简单串或复杂串C、在集合并运算下它是封闭的D、不是所有的语言都能被图灵机识别4．如果A≤m B且B是可判定的，则（A）。

A、A也是可判定的B、A不一定是可判定C、A是不可判定的D、A可判定否与B无关5．若一个图灵机M时间复杂度为2n3+6n+7。

则其渐进时间复杂度为( C ）。

A、O(2n3+6n+7)B、O(2n3+6n)C、O(n3)D、o(n3)6. 时间复杂性类TIME(t(n))是（ C ）。

A、时间复杂度为t(n)的图灵机集合B、时间复杂度为O(t(n))的图灵机集合C、由O(t(n))时间的图灵机判定的所有语言的集合D、由o(t(n))时间的图灵机判定的所有语言的集合7．当(A）时，P=NP。

A、语言B是NP完全的且B∈PB、计算速度快到一定峰值时C、计算机内存达到无限D、计算机性价比很高时8. 如果A是NP-完全的，则( C )。

A、一定存在一个B∈NP且B不能多项式时间规约到AB、A不一定属于NPC、A一定属于NPD、若A∈P，则P≠NP9. 对于SAT问题（ C ）的说法是对的。

A、SAT问题不能用线性空间算法解决B、SAT∉PSPACEC、SAT∈PSPACED、SAT∉NP10．如果B是PSPACE完全的，则（C）。

A、B∉NPSPACEB、B∈PC、B∈PSPACED、B一定是NP完全的二、综合应用题(10分+10分+10分+10分+10分,本题共50分)1.将一个DFA与一个正则表达式是否等价问题用一个语言来描述，然后，证明该语言是1可判定的。