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

第4讲-习题解析 战德臣 哈尔滨工业大学计算机学院教授.博士生导师 教育部大学计算机课程教学指导委员会委员 OKOK ZhanDCZhanDC Research Center on Intelligent Computing for Enterprises Services, Harbin Institute of Technology 模拟练习题 战德臣教授 1、关于“图灵机”，下列说法不正确的是_____ 。(A|B|C|D|E) (A)图灵机给出的是计算机的理论模型； (B)图灵机的状态转移函数q, X, Y, R(或L或N), p，其实就是一条指令，即在q 状态下，当输入为X时，输出为Y ，读写头向右(R)、向左(L)移动一格或不动 (N)，状态变为p； (C)图灵机是一种离散的、有穷的、构造性的问题求解思路； (D)凡是能用算法方法解决的问题也一定能用图灵机解决；凡是图灵机解决不了 的问题，人和算法也解决不了； (E)上述有不正确的。 q, X, Y, R, p q, X, Y, L, p q, X, Y, N, p 模拟练习题 战德臣教授 2、关于“图灵机”和“计算”，下列说法不正确的是_____ 。(A|B|C|D) (A)计算就是对一条两端可无限延长的纸带上的一串0和1，一步一步地执行指 令，经过有限步骤后得到的一个满足预先规定的符号串的变换过程； (B)“数据”可被制成一串0和1的纸带送入机器中进行自动处理，被称为数据纸 带；处理数据的“指令”也可被制作成一串0和1的纸带送入机器中，被称为程序纸 带；机器一方面阅读程序纸带上的指令，并按照该指令对数据纸带上的数据进行 变换处理。 (C)计算机器可以这样来制造：读取程序纸带上的指令，并按照该指令对数据纸 带上的数据做相应的变换，这就是图灵机的基本思想； (D)上述有不正确的。 模拟练习题 战德臣教授 3、下图为用状态转换图示意的一个图灵机，其字母集合为{0, 1, X,Y, B}，其中B为空白字符；状态 集合{S ，S ，S ，S ，S } ，其中S 为起始状态，S 为终止状态；箭头表示状态转换，其上标注的 1 2 3 4 5 1 5 如in, out, direction表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方 向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留 在原处)。 该图灵机的功能是_____ 。(A|B|C|D) (A)识别是否如01010、1串，即一个0接续一个1，且0的个数和1的个数相同； (B)识别是否如000111 的0 、1串，即左侧连续0 的个数和右侧连续1的个数相同的0 、1 串； (C)将形如0101 的0 、1 串，即一个0接续一个1，且0 的个数和1的个数相同， 转换为 XYXY ，XYXYXYXY 的形式； (D)将形如0001110、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换 为XXXYYY ，XXXXYYYY 的形式。 从起始状态开始，对输入串进行处理，如果在待处理 输入串结束时，图灵机能到终止状态，则说明其正确 地处理