下载文档原格式
计算理论期末练习题（2015）复习重点1、集合序列元组函数关系图串：字母表中符号的有穷序列语⾔:是字符串的集合2、DFA、NFA、NFA到DFA的转换，DFA、NFA的形式化五元组表达3、正则表达式、正则表达式和NFA之间的转换、利⽤泵引理证明不是正则语⾔4、上下⽂⽆关⽂法下推⾃动机乔姆斯基范式（基本概念）CFG到下推⾃动机的转换从右⾄左压⼊栈中5、利⽤泵引理证明不是上下⽂⽆关语⾔6、图灵机、图灵可识别语⾔：接受、拒绝、循环判定器：对所有输⼊都停机的图灵机，永不循环。
图灵可判定语⾔：能让图灵机停机的语⾔，接受或者拒绝要求可以做简单的判定性证明（例如：A DFA、A CFG、HALT-TM、E TM）7、可归约性。
要求可以利⽤规约，完成简单的定理证明。
计算理论练习题1、画出识别下述语⾔的DFA 状态图，其中，字母表为{0,1}。
1）{w|w 从1开始且以0结束}；2）{w|w含有⾄少3个1}；3）{w|w含有⼦串0101}；q1的0⾃循环处考虑004）{w|w的长度不⼩于3，并且第3个符号为0}；5）{w|w从0开始且长度为奇数}；6）{w | w是除11和111以外的任何字符}；7）{w | w不含⼦串110}；2、写出下述语⾔的正则表达式。
1）{w|w不含⼦串110}；(0∪10)*1*2）{w|w的长度不超过5}；ε∪∑∪∑∑∪∑∑∑∪∑∑∑∑∪∑∑∑∑∑3）{w|w是除11和111外的任意串}；ε∪0∑*∪10 ∑*∪110 ∑*∪111 ∑∑*包含11或111的串仍属于题设4）{w|w的奇数位均为1}；(1Σ)*(ε? 1)前⼀个括号为串长为偶数，加后⼀个则奇偶都可以5）{w|w含有⾄少2个0，并且⾄多含1个1}。
0*(00?010?001?100) 0*确保两个0⼀定在，并且最多1个1，不能在外⾯，即有可能为空3、利⽤泵引理证明下述语⾔不是正则的。
1）A1={0n1n2n|n≥0};证明：假设A1是正则的。
第1章习题一、填空题1．计算机科学是主要研究（）、（）和（）的学科。
计算理论、计算机，信息处理2．在模型建立的前提下，利用计算机求解问题的核心工作就（）设计。
算法3．算法是一组规则，它的主要特性是（）、（）、（）、（）和（）。
有限性、可执行性、机械性、确定性，终止性或：有穷性，确定性，能行性，0个或多个输入输入，1个或多个输出4．要使一个问题能够用计算机解决，其必要条件是（）。
具有确定算法或：可以在确定、有限步骤内被解决5．在计算机内，一切信息都是以（）形式表示的。
二进制6．如果说图灵机A能够完全模拟图灵机B，则意味着（）。
如果A和B能够相互模拟，则表示（）。
在给定输入时，A和B有相同的输出 // A和B计算等价7．图灵机中的纸带可以相当于计算机中的（）。
存储器8．第一代计算机的主要部件是由（）和（）构成的。
电子管，继电器9．未来全新的计算机技术主要指（），（）和（）。
光子计算机，生物计算机，量子计算机10．未来电子计算机的发展方向是（）、（）、（）和（）。
巨型化，微型化，网络化，智能化11．目前国际上广泛采用的西文字符编码是标准（），它是用（）位二进制码表示一个字符。
ASCII，712．采用16位编码的一个汉字存储时要占用的字节数为（）。
213．位图文件的存储格式为（），用数码像机拍摄的照片的文件格式一般为（）。
BMP，JPG14．若处理的信息包括文字、图片、声音和电影，则其信息量相对最小的是（）。
文字15．模拟信号是指（）都连续变化的信号。
时间和幅值16．计算机中对信息的组织和管理方式有两种，即（）和（）。
文件，数据库17．软件的测试方法包括（）和（）。
白盒测试，黑盒测试18．普适计算的主要特点是（）。
无处不在的计算模式二、简答题：1．简述计算机采用二进制的原因。
答：主要原因是：①二进制只有0和1两个基本符号，任何两种对立的物理状态都可以归结为二进制表示。
②算术运算规则简单，且适合逻辑运算。
低压进网电工初训（2013年低压理论题库新版）理论题库上海嘉定梵骋电力科技有限公司电工基础单选题：1、在直流电路中，电感元件的（ C ）。
A、容抗值大于零B、感抗值大于零C、感抗值等于零D、感抗值小于零2、在电阻串联的电路中，电路的端电压U等于（ D ）。
A、各串联电阻的端电压B、各串联电阻端电压的平均值C、各串联电阻端电压的最大值D、各串联电阻端电压的总和3、在正弦交流电路中，电压、电流、电动势都是随时间( C )。
A、非周期性变化的B、恒定不变的C、按正弦规律变化的D、按余弦规律变化的4、已知横截面积为10mm2的导线中，流过的电流为200A，则该导线中的电流密度为（ A ）。
A、20A/mm2B、25A/mm2C、30A/mm2D、50A/mm25、规定在磁体内部，磁力线的方向是（ A ）。
A、由S极到达N极B、由N极到达S极C、由N极出发到无穷远处D、由S极出发到无穷远处6、最简单的电路由电源、（ C ）和连接导线四部分组成。
A、电灯和开关B、变压器和负荷C、负荷和开关D、变压器和配电所7、在纯电容的交流电路中，电流的相位超前电压相位（ C ）。
A、30°B、60°C、90°D、180°8、通电直导体在磁场中所受力的大小，与其通过的电流（ B ）。
A、成反比B、成正比C、无关系D、以上答案皆不对9、电路处于断路状态时，电路中没有（ B ）流过。
A、电压B、电流C、电阻D、电功率10、当电源电动势为E，电源内阻为r，外接负载电阻为R时，全电路欧姆定律的数学表达式是（ D ）。
A、Ｉ＝Ｒ／（Ｅ＋r0） B、Ｉ＝（Ｒ＋r）／ＥC、Ｉ＝Ｅ／ＲD、Ｉ＝Ｅ／（Ｒ＋r）11、判断导体内的感应电动势的方向时，应使用（ B ）。
A、左手定则B、右手定则C、顺时针定则D、逆时针定则12、电路中任意两点间电位（ B ）称为电压(或称电位差)。
A、之和B、之差C、之积D、之商13、在交流电路中，关于有功功率P、无功功率Ｑ、视在功率S、功率因数角φ的关系，正确的是（ D ）。
2013-2014(1)计算机应用基础期末理论复习题一、单选题1、MMX是指带有___________的CPU芯片。
CA、自动录音B、大量寄存器C、多媒体功能D、数据压缩2、现代信息技术建立在通讯技术、计算机技术和____________上。
CA、设备技术B、信息技术C、微电子技术D、电路制造技术3、串行接口RS232和USB相比较，在速度上是________。
BA、RS232快B、USB快C、根据情况不确定的D、相同的4、以下__________属于系统软件。
CA、AuthorwareB、CAI软件C、VC++D、FrontPage5、乐器数字接口的英文缩写是________。
CA、RS232CB、USBC、MIDID、FM6、目前按 USB2.0标准，USB的传输速率可以达到_______Mbps。
DA、56B、240C、256D、4807、人类生存和社会发展的基本资源是________。
BA、物质、金钱、石油、股票B、物质、能源、信息C、粮食、煤炭、电力、因特网D、物质、能源、因特网8、____________不被认为是操作系统中可用来支持多媒体的功能。
CA、具有多任务的特点B、采用虚拟内存管理技术C、支持多媒体信息检索功能D、具有管理大容量存储器的功能9、在PowerPoint 2010中，可利用__________来组织大型幻灯片，以简化其管理和导航。
BA、A.动画刷B、节C、占位符D、视图10、常用的IP地址包括ABC三大类，其中，A类地址的第一段取值介于：_______。
DA、1-172B、1-168C、128-191D、1-12611、在html中，“提交按钮”的type属性值为______________。
BA、formB、submitC、resetD、tijiao12、完整的微型计算机硬件系统一般包括外部设备和_________。
AA、主机B、中央处理器C、存贮器D、运算器和控制器13、现代信息技术的主体是__________等。
第三章上下文没关语言略。
a. 利用语言 A={a m b n c n | m,n0} 和 A={a n b n c m | m,n0} 以及例，证明上下文没关语言在交的运算下不关闭。
b.利用 (a) 和 DeMorgan律( 定理，证明上下文没关语言在补运算下不关闭。
证明： a. 先说明 A,B 均为上下文没关文法，对 A 结构 CFG C1S aS|T|T bTc|对 B, 结构 CFG C2S Sc|R|R aRb由此知 A,B 均为上下文没关语言。
0} 不是上下文没关语言，所以上下文无可是由例 , A ∩B={a n b n c n|n 关语言在交的运算下不关闭。
b. 用反证法。
假定 CFL在补运算下关闭，则对于 (a) 中上下文没关语言A,B，A , B也为 CFL，且 CFL对并运算关闭，所以A B也为 CFL，从而知道 A B 为CFL，由DeMorgan定律 A B ＝A∩B，由此A∩B是CFL,这与 (a) 的结论矛盾，所以 CFL对补运算不关闭。
略。
和给出产生下述语言的上下文没关文法和PDA，其中字母表={0,1} 。
a.{w | w起码含有3个1}0,1,1S→A1A1A1A,1,1,1 A→0A|1A|b.{w | w以同样的符号开始和结束}S→0A0|1A10,1,A→0A|1A|0,00,01,11,1c. {w | w的长度为奇数}0,1,0,1,S →0A|1AA →0B|1B|B →0A|1Ad. {w | w 的长度为奇数且正中间的符号为 0}S →0S0|1S1|0S1|1S0|00, 0 0,0 1,1,0,$ 0,,$e. {w | w 中 1 比 0 多}1,00,1 0S →A1A0, ,11,1 ,$,1,$A →0A1|1A0|1A|AA|f. {w | w=w R }S →0S0|1S1|1|00, 0 0,0 1, 1 1,1 ,1, ,$$ 0,,g. 空集S →S给出产生下述语言的上下文没关文法：a ．字母表 {a,b} 上 a 的个数是b 的个数的两倍的全部字符串构成的会合。
五、计算题11 某汽车的总质量m=4600kg,C D =0.75,A=4m 2, 03.01＝δ,03.02=δ,f=0.015,传动系机械效率ηT =0.82,传动系总传动比100==gi i i ,假想发动机输出转矩为T e =35000N.m , 车轮半径m r 360.0=，道路附着系数为4.0=ϕ,求汽车全速从30km/h 加速至50km/h 所用的时间。
由于ϕ>F F t ,所以，t u u a ∆-=12,即st 42.181.94.06.33050=⨯⨯-=∆2 已知某汽车的总质量m=4600kg,C D =0.75,A=4m 2,旋转质量换算系数δ1=0.03,δ2=0.03,坡度角α=5°,f=0.015, 车轮半径r r =0.367m ，传动系机械效率ηT =0.85,加速度du/dt=0.25m/s 2,u a =30km/h,计算汽车克服各种阻力所需要的发动机输出功率？kwdtdu mu Au C Gu Gfu P a aD a a t e 18.5736001)25.030460006.176********.05sin 3081.946005cos 3081.9015.04600(85.01)3600761403600sin 3600cos (133=⨯⨯⨯+⨯⨯++⨯⨯+⨯⨯⨯=δ++α+αη=3 已知某车总质量为8025kg ,L =4m (轴距),质心离前轴的距离为a =2.5m ,至后轴距离为b =1.5m ,质心高度h g =1.15m ,在纵坡度为i =3.5的良好路面上等速下坡时 ,求轴荷再分配系数(注:再分配系数m f 1=F Z 1/F Z ,m f 2=F Z 2/F Z )。
NiF z 81.9309081.980255.25.115.15.11⨯=⨯⨯+⨯+=NiF z 81.9493581.980255.25.115.15.22⨯=⨯⨯+⨯-=385.08025/30901==f m ,615.0385.012=-=f m4 已知某汽车发动机的外特性曲线回归公式为T t q =19+0.4n e -150×10-6n e 2，传动系机械效率ηT =0.90-1.35×10-4n e ，车轮滚动半径r r =0.367m,汽车总质量4000kg ，汽车整备质量为1900kg ，滚动阻力系数f =0.009+5.0×10-5u a ,空气阻力系数×迎风面积＝2.77m 2,主减速器速比i 0=6.0,飞轮转动惯量I f =0.2kg ·m 2,前轮总转动惯量I w 1=1.8 kg ·m 2, 前轮总转动惯量I w 1=3.6 kg ·m 2,发动机的最高转速n max =4100r/min ,最低转速n min =720r/min ,各档速比为:计算汽车在V 档、车速为70km/h 时汽车传动系机械损失功率，并写出不带具体常数值的公式。
上海电机学院 2012–2013学年第_1_学期（023005A1）《理论力学》课程期末考试题库开课学院： 机械学院 考试时间 120 分钟 计算器□√ 草稿纸□√ 答题卡□考试形式: 开卷□/闭卷□√考生姓名： 学号： 班级：题序 一 二 三 四 五 六 七 八 总 分 得分 评卷人一、选择题（共20分，每小题2分）1、作用在一个刚体上的两个力1F 、2F ，且满足120F F +=，则该二力可能的关系是（ ） A ．作用力和反作用力； B ．一对平衡力或作用力和反作用力；C ．一对平衡力或一个力偶；D ．作用力和反作用力或一个力偶。
2、空间平行力系简化的最后结果是（ ）A. 力B.力偶C.力或力偶D. 力螺旋3、各力线均平行于某平面的空间力系独立平衡方程的个数为（ ） A. 3 B. 4 C. 5 D. 64、各力线均平行于某直线的空间力系独立平衡方程的个数为（ ） A. 3 B. 4 C. 5 D. 65、各力线均相交于某直线的空间力系独立平衡方程的个数为（ ） A. 3 B. 4 C. 5 D. 66、平面桁架总杆数m ，总节点数n ，则超静定桁架的条件是（ ） A. m>2n-3 B. m<2n-3 C. m>2n+3 D. m<2n+37、如图，圆盘作定轴转动，若某瞬时其边缘上A 、B 、C 三点的速度、加速度如图所示，则______ ____的运动是不可能的。
（A ）点A ，B ； （B ）点A ，C ； （C ）点B ，C ； （D ）点A ，B ，C 。
8、A ，B 为某平面力系作用面内任意两点，该力系向A 点简化的结果是主矢'RA F 和主矩A M ，向B 点简化的主矩为B M ，则下述结论正确的是( )A ．当0'=RA F 时，必有B A M M = B. 当0'=RA F 时，可能有B A M M ≠C ．当'≠RA F 时，必有B A M M = D. 当0'≠RA F 时，必有B A M M ≠9、空间任意力系向某一定点O 简化，若主矢0≠'R ，主矩00≠M ，则此力系简化的最后结果--------------------。
一．填空题1.语言类P 、PSPACE 、NP 、NPSPACE 、EXPTIME之间的关系为（EXPTIME NPSPACE PSPACE NP P ⊆=⊆⊆）。
2.产生语言{12n 03n |n ≥0}的上下文无关文法是（00011|A A ε→）。
3.命题“利用递归定理，一个TM M 可以得到自己的描述<M>”是（正确的）。
（正确的、错误的）4.命题“A ≤M B 和B A M ≤含义相同”是（正确的）。
（正确的、错误的）5.上下文无关文法为乔姆斯基范式，是指其中的每一个规则具有如下形式（a A BC A →→,）。
6.萨维奇定理指出：对于任何函数f:N →R +,其中f(n)≥n,（ ))(())((2n f SPACE n f NSPACE ⊆ ）7.空间层次定理证明了空间复杂性类不全相同，它们形成一个层次结构，其中（时空界限较大的类比时空界限较小的类）包含更多的语言。
8.语言B 是NL 完全的，如果（1）NL B ∈并且（2）NL 中的每个A （对数空间）可规约到B ，例如（PATH ）是NL 完全的。
9.如果一个最小化问题的近似算法总能找到不超过最优解k 倍的可行解，则称这个算法是（k-优）的。
10.根据概率错误，定义RP 是多项式时间概率图灵机识别的语言类，其中，不在语言中的输入以概率（1）被拒绝。
二．问答题1.说明有穷自动机、正则表达式、下推自动机、图灵机的异同点。
2.对于图示的DFA M ，回答下列问题，并说明理由（1）?0100,DFA A M >∈<是，DFA M 接受0100（2）?011,DFA A M >∈<否，M 不接受011（3）?DFA A M >∈<否，输入不完全，因此形式不正确（4）?0100,REX A M >∈<否，前半部分不是正则表达式，因此形式不正确（5）?DFA E M >∈<否，M 的语言非空（6）?,DFA EQ M M >∈<是，M 接受和它自身相同的语言3.非确定性图灵机、概率图灵机和交错式图灵机是如何体现非确定性的？三．构造题1.构造PDA 。
使其接受语言{0n 1n+1|n ≥0}。
要求给出相应的形式描述和状态转移图。
2.构造一个可判定语言A={0n 1n 0n |n ≥0}的图灵机M ，并分析该图灵机算法的时间复杂性。
q 0 q 1 q 2 01 1 0,11.证明P在并、连接和补运算下封闭。
NP在并和连接运算下封闭。
答案：P在并、链接和补运算下封闭。
(1) 并：对任意L1, L2∈P，设有n a时间图灵机M1和n b时间图灵机M2判定它们，且c=max{a,b}。
对L1⋃L2构造判定器M:M=“对于输入字符串w :1)在w上运行M1，在w上运行M2。
2)若有一个接受则接受，否则拒绝。
”时间复杂度：设M1为O(n a),M2为O(n b)。
令c=max{a,b}。
第一步用时O(n a+n b) ，因此总时间为O(n a+ n b)=O(n c),所以L1⋃L2属于P类，即P在并的运算下封闭。
(2) 连接：对任意L1, L2属于P 类，设有n a时间图灵机M1和n b时间图灵机M2判定它们，且c=max{a,b}。
对L1 L2构造判定器M:M=“对于输入字符串w=w1,w2,…,w n，1)对k=0,1,2,…,n重复下列步骤。
2)在w1w2…w k上运行M1，在w k+1w k+2…w n上运行M2。
3)若都接受，则接受。
否则继续。
4)若对所有分法都不接受则拒绝。
“时间复杂度：(n+1)×(O(n a)+O(n b))=O(n a+1)+O(n b+1)=O(n c+1)，所以L1 L2属于P类，即P 在连接的运算下封闭。
(3)补：L构造判定器M: 对任意L1属于P 类，设有时间O(n a)判定器M1判定它，对1M=“对于输入字符串w :(1)在w上运行M1。
(2)若M1接受则拒绝，若M1拒绝则接受。
”L属于P类，即P在补的运算下封闭。
时间复杂度为：O(n a)。
所以1NP在并和连接运算下封闭(1) 并：对任意L1, L2∈NP，设分别有n a时间非确定图灵机M1和n b时间非确定图灵机M2判定它们，且c=max{a,b}。
构造判定L1⋃L2的非确定图灵机M:M=“对于输入字符串w :1)在w上运行M1，在w上运行M2。
2)若有一个接受则接受，否则拒绝。
”对于每一个非确定计算分支，第一步用时为O(n a)+O(n b)，因此总时间为O(n a+n b)=O(n c)。
所以L1⋃L2∈NP，即NP在并的运算下封闭。
(2) 连接：对任意 L 1, L 2∈NP ，设分别有n a 时间非确定图灵机M 1和n b 时间非确定图灵机M 2 判定它们，且c=max{a,b}。
构造判定L 1 L 2的非确定图灵机M:M=“对于输入字符串w :1) 非确定地将分成两段x,y ，使得w=xy 。
2) 在x 上运行M 1，在y 上运行M 2。
3) 若都接受则接受，否则拒绝。
”对于每一个非确定计算分支，第一步用时O(n),第二步用时为O(n a )+O(n b )，因此总时间为O(n a + n b )=O(n c )。
所以L 1 L 2∈NP ，即NP 在连接运算下封闭。
2.设T={<M>|M 是一个TM ，且每当M 接受w 时，M 也转变w}，证明T 是不可判定的。
3.证明：CLIQUE 是NP 完全的。
答案：首先证明CLIQUE 属于NP下面是CLIQUE 的验证机VV=“对输入<<G ,k>,c>：1）检查c 是否是G 中k 个节点的集合。
2）检查G 是否包含连接c 中结点的所有边。
3）若两项检查都通过，则接受；否则，拒绝。
”再证明3SAT 多项式时间可归约到CLIQUE 。
（书P168）因为3SAT 是NP 完全的，所以CLIQUE 也是NP 完全的。
2012年试题一．判断题1.通用电子计算机（基于布尔电路）与图灵机可以互相模拟。
（错）2.任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。
（对）3.如果一个语言不是图灵可识别的，则其不是图灵可判定的。
（对）4.DFA 与NFA 、PDA 与NPDA （非确定下推自动机），TM 与NTM 在本质上计算能力均相同。
（错）5.任何机器都不能自再生。
（错）二．填空题1.设M=（Q,∑,δ,0q ，F ）为一台有穷自动机，w=w 1w2...w n 是一个字符串且其中w i 是字母表∑的成员。
如果存在Q 中的状态序列r 0,r 1,...,r n 满足（1）r 0=0q（2）（ ()11,++=i i i r w r δ ），i=0，...，n-1（3）F r n ∈则M 接受w2.对于文法G ：()a EXPR EXPR EXPR EXPR EXPR EXPR |||⨯+→，这个文法可以（ 2 ）种方式产生字符串a+a ×a 。
3.BPP 是多项式时间的概率图灵机以错误概率（ 1/3 ）识别的语言类。
4.语言的电路（规模）复杂度是该语言的（ 极小电路族 ）的规模复杂度。
5.按Kolmogorov 理论，不可压缩串看起来就像是（ 随机抛硬币 ）得到的串。
三．简答题1.论述递归定理定义其在涉及“自引用”计算过程中的重要作用。
答：递归定理提供了以任意程序设计语言实现自引用词“这个”的能力。
利用这个能力，任何程序设计语言都有引用它自己的描述的能力。
递归定理扩展了在构造SELF 时使用过得技术，使得一个程序不仅能得到它自己的描述，而且还能用这个描述继续进行计算，而不仅仅将之打印出来。
2.尽可能全面描述DFA 和NFA 的区别和联系。
3.论述：为什么对角化方法可以区分可计算与不可计算4.论述空间层次定理的基本思想。
四．构造题1.构造识别语言{ww R |w ∈{0,1}*}的PDA ，注意w R 表示倒写的w 。
2.构造一个判定语言A={0n 1n |n ≥0}的图灵机M ，并分析该图灵机的时空复杂度。
五．证明题1.证明：A TM 是不可判定的2.考虑这样的问题：一个双带图灵机，检查在计算任意输入串的过程中，它是否在第二条带上写下一个非空白符，将这个问题形式化为一个语言，并证明它是不可判定的。
（P132 5.11） 证明：设C={<M>|M 是双带TM ，当它运行在某输入上时，它在其第二个带上写一个非空白符}。
证明A TM 可规约到C 。
为了得到矛盾设TM R 可判定C ，构造TM S ，它用R 来判定A TM 。
S=“对于输入<M,w>:1）用M 和w 构造下面的双带TM T w 。
T W =“对于任何输入：a.在w 上用第一个带模拟M 。
b.若果模拟表明M 接受，则在第二个带上写一个非空白符。
”2)在<T W >上运行R ，确定T w 是否在第二个带上写了一个非空白符。
3）如果R 接受，则M 接受w ，因此接受；否则拒绝。
”3.思考下述计划安排问题。
有一份期末考试清单F1，...，Fk 需要安排时间，以及学生清单S1，...，Sl 。
每个学生都选择了这些考试的某个子集。
必须将这些考试安排到各时段中，使得同一时段中不会有某个学生同时需要参加两门考试。
试问，如果只用h 个时段，是否存在合乎要求的计划。
将这个问题形式化为一个语言，并证明它是NP 完全的。
（P183 7.29）。
