大学计算机基础第三章习题.pdf

大学计算机基础第三章习题--第1页

1、关于“存储程序”，下列说法不正确的是_____。

A.将“指令”和“数据”以同等地位保存在存储器中，以便于机器自动读取自动处理

B.之所以将“程序”和“数据”事先存储于存储器中，是因为输入的速度满足不了机器处理

的速度，为使机器连续自动处理，所以要“存储程序”

C.依据“存储程序”原理，机器可由四大部分构成：运算器、存储器、输入设备和输出设备

D.冯.诺依曼计算机的本质就是“存储程序、连续自动执行”

正确答案：C

2、关于“图灵机”，下列说法不正确的是_____。

A.图灵机给出的是计算机的理论模型,是一种离散的、有穷的、构造性的问题求解思路

B.图灵机的状态转移函数q,X,Y,R(或L或N),p，其实就是一条指令，即在q状态下，当输

入为X时，输出为Y，读写头向右(R)、向左(L)移动一格或不动(N)，状态变为p

C.凡是能用算法方法解决的问题也一定能用图灵机解决；凡是图灵机解决不了的问题任何算

法也解决不了

D.上述有不正确的

正确答案：D

3、关于“图灵机”和“计算”，下列说法不正确的是_____。

A.计算就是对一条两端可无限延长的纸带上的一串0和1，一步一步地执行指令，经过有限

步骤后得到的一个满足预先规定的符号串的变换过程

B.“数据”可被制成一串0和1的纸带送入机器中进行自动处理，被称为数据纸带；处理数

据的“指令”也可被制作成一串0和1的纸带送入机器中，被称为程序纸带；机器一方面阅

读程序纸带上的指令，并按照该指令对数据纸带上的数据进行变换处理

C.计算机器可以这样来制造：读取程序纸带上的指令，并按照该指令对数据纸带上的数据做

相应的变换，这就是图灵机的基本思想

D.上述有不正确的

正确答案：D

4、下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；

状态集合{S1，S2，S3，S4，S5}，其中S1为起始状态，S5为终止状态；箭头表示状态转换，

其上标注的如in,out,direction表示输入是in时，输出out，向direction方向移动一格，同

时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移

动)、L(向左移动)、N(停留在原处)。

该图灵机的功能是_____。

大学计算机基础第三章习题--第1页

大学计算机基础第三章习题--第2页

A.识别是否如0101的0、1串，即一个0接续一个1，且0的个数和1的个数相

同

B.识别是否如000111的0、1串，即左侧连续0的个数和右侧连续1的个数相同

的0、1串

C.将形如0101的0、1串，即一个0接续一个1，且0的个数和1的个数相同，

转换为XYXY，XYXYXYXY的形式

D.将形如000111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、

1串转换为XXXYYY，XXXXYYYY的形式

正确答案：D

5、下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；

状态集合{S1，S2，S3，S4，S5，S6}，其中S1为起始状态，S6为终止状态；箭头表示状态

转换，其上标注的如in,out,direction表示输入是in时，输出out，向direction方向移动一

格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为

R(向右移动)、L(向左移动)、N