大学计算机计算思维导论第4讲习题及解析

《大学计算机计算思维导论第4讲习题及解析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4讲-习题解析战德臣哈尔滨工业大学计算机学院教授.博士生导师教育部大学计算机课程教学指导委员会委员OKZhanDCResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology模拟练习题战德臣教授1、关于“图灵机”，下列说法不正确的是_____。(A

2、B

3、C

4、D

5、E)(A)图灵机给出的是计算机的理论模型；(B)图灵机的状态转移函数，其实就是一条指令，即在q状态下，当输入为X时，输出为Y，读写头向右(R)、向左(L)移动一格或不动(N)，

6、状态变为p；(C)图灵机是一种离散的、有穷的、构造性的问题求解思路；(D)凡是能用算法方法解决的问题也一定能用图灵机解决；凡是图灵机解决不了的问题，人和算法也解决不了；(E)上述有不正确的。模拟练习题战德臣教授2、关于“图灵机”和“计算”，下列说法不正确的是_____。(A

7、B

8、C

9、D)(A)计算就是对一条两端可无限延长的纸带上的一串0和1，一步一步地执行指令，经过有限步骤后得到的一个满足预先规定的符号串的变换过程；(B)“数据”可被制成一串0和1的纸带送入机器中进行自动处理，被称为数据纸带；处理数据的“指令”也可被

10、制作成一串0和1的纸带送入机器中，被称为程序纸带；机器一方面阅读程序纸带上的指令，并按照该指令对数据纸带上的数据进行变换处理。(C)计算机器可以这样来制造：读取程序纸带上的指令，并按照该指令对数据纸带上的数据做相应的变换，这就是图灵机的基本思想；(D)上述有不正确的。模拟练习题战德臣教授3、下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；状态集合{S，S，S，S，S}，其中S为起始状态，S为终止状态；箭头表示状态转换，其上标注的1234515如表示输入是in时，输出out，向direction方向移动一格

11、，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。该图灵机的功能是_____。(A

12、B

13、C

14、D)(A)识别是否如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同；(B)识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串；(C)将形如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同，转换为XYXY，XYXYXYXY的形式；(D)将形如000111，00001111的0、1串，

15、即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY，XXXXYYYY的形式。从起始状态开始，对输入串进行处理，如果在待处理输入串结束时，图灵机能到终止状态，则说明其正确地处理了输入串。输出串就是其处理结果。如果遇到不在字母集合中的符号，或者遇到当前状态下不能处理的输入，则机器就终止执行，即未到终止状态而终止执行，则说明其不能处理此类输入串。模拟练习题行动下一当前处纸带上的当前状态输入输出方向状态理位置战德臣教授完整数据S10XRS21000111验证D选项：S200RS22X00111000111，00001111的0、1串，即左S200RS23X00111侧连续

16、0的个数和右侧连续1的个数相S21YLS34X00111同的0、1串转换为XXXYYY，S300LS33X00Y11XXXXYYYY的形式。S300LS32X00Y11S3XXRS11X00Y11S10XRS22X00Y11S200RS23XX0Y11S2YYRS24XX0Y11S21YLS35XX0Y11S3YYLS34XX0YY1…………………S21YLS36XXXYY1S3YYLS35XXXYYY…………………S3XXRS13XXXYYYS1YYRS44XXXYYYS4YYRS45XXXYYYS4YYRS46XXXYYYS4BBNS57XXXYYY模拟练习题战德臣教授4、下图

17、为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；状态集合{S，S，S，S，S，S}，其中S为起始状态，S为终止状态；箭头表示状态转换，其上标12345616注的如表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。该图灵机的功能是_____。(A