串； (C)将形如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同， 转换为 XYXY， XYXYXYXY的形式； (D)将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换 为XXXYYY， XXXXYYYY的形式。
的问题，人和算法也解决不了； (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)上述有不正确的。
第4讲-习题解析
战德臣
哈尔滨工业大学计算机学院 教授.博士生导师 教育部大学计算机课程教学指导委员会委员
OK ZhanDC
Research Center on Intelligent Computing for Enterprises & Services,
Harbin Institute of Technology
下一 状态 S2 S2 S2 S3 S3 S3 S1 S2 S2 S2 S3 S3 … S3 S3 … S1 S4 S4 S4 S5
当前处 理位置
1 2 3 4 3 2 1 2 3 4 5 4 … 6 5 … 3 4 5 6 7
纸带上的
战完德整臣数据教授 000 111 X00 111 X00 111 X00 111 X00 Y11 X00 Y11 X00 Y11 X00 Y11 XX0 Y11 XX0 Y11 XX0 Y11 XX0 YY1
从起始状态开始，对输入串进行处理，如果在待处理 输入串结束时，图灵机能到终止状态，则说明其正确 地处理了输入串。输出串就是其处理结果。如果遇到 不在字母集合中的符号，或者遇到当前状态下不能处 理的输入，则机器就终止执行，即未到终止状态而终 止执行，则说明其不能处理此类输入串。
模拟练习题
验证D选项： 000111，00001111的0、1串，即左 侧连续0的个数和右侧连续1的个数相 同的0、1串转换为XXXYYY， XXXXYYYY的形式。
当前状态 输入
S1
0
S2
0
S2
0
S2
1
S3
0
S3
0
S3
X
S1
0
S2
0
S2
Y
S2
1
S3
Y
…
…
S2
1
S3
Y
…
…
S3
X
S1
Y
S4
Y
S4
Y
S4
B
输出 X 0 0 Y 0 0 X X 0 Y Y Y … Y Y … X Y Y Y B
行动 方向
R R R L L L R R R R L L … L L … R R R R N
行利用各个部件； (D)冯.诺依曼计算机提出“运算”和“存储”分离完全没有必要。
模拟练习题
战德臣 教授
9、下图是一个存储器的简单模型。围绕该存储器模型，回答下列问题。 (1)下列说法不正确的是_____。(A|B|C|D) (A)该存储器可存取4个4位的存储单元； (B)该存储器其中的一个存储单元的内容是1010； (C)该存储器既可读出，又可写入； (D)该存储器的地址码分别是00，01，10和11。
00 0 01
1 10 11
01 1 1
模拟练习题
战德臣 教授
10、下图是一个存储器的简单模型。围绕该存储器模型，回答下列问题。
(1)当A1A0=10时，D5D4D3D2D1D0的内容是_____。(A|B|C|D|E) (A) 100101； (B)011101； (C)101010； (D)010101；(E)都不对。
存储位、存储字
00 1 01
存储单元 存储单元的地址编码A1A0
0 10 11 1 0 1 0 1 0
存储单元的内容D3D2D1D0
地址编码线，简称地址线A1A0
地址控制线W3,W2,W1,W0
数据线D3,D2,D1,D0
模拟练习题
战德臣 教授
10、下图是一个存储器的简单模型。围绕该存储器模型，回答下列问题。 (2) 当 存 储 单 元 的 内 容 是 100101 时 ， 其 存 储 单 元 的 地 址 编 码 A1A0 是 _____ 。 (A|B|C|D|E) (A)00； (B)01； (C)10； (D)11； (E)没有该存储单元。
(3) A1A0为01的存储单元，其内容D3D2D1D0是_____。(A|B|C|D) (A)0101； (B)1010； (C)0111； (D)1110； (E)没有该存储单元。
存储位、存储字
存储单元
存储单元的地址编码A1A0 存储单元的内容D3D2D1D0 地址编码线，简称地址线A1A0 地址控制线W3,W2,W1,W0 数据线D3,D2,D1,D0
模拟练习题
战德臣 教授
3、下图为用状态转换图示意的一个图灵机，其字母集合为{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(停留 在原处)。 该图灵机的功能是_____。(A|B|C|D) (A)识别是否如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同； (B)识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1
存储位、存储字
存储单元
存储单元的地址编码A1A0 存储单元的内容D3D2D1D0 地址编码线，简称地址线A1A0 地址控制线W3,W2,W1,W0 数据线D3,D2,D1,D0
模拟练习题
战德臣 教授
9、下图是一个存储器的简单模型。围绕该存储器模型，回答下列问题。
(2)内容为1010的存储单元的地址编码A1A0是_____。(A|B|C|D) (A)00； (B)01； (C)10； (D)11； (E)没有该存储单元。
V=V; V=C; V=C+C; V=C+V; V=V+C; V=V+V;
都能识别
V=V V=C+C+C; V=C+V+C; V=V+C V=V+V
不能识别
模拟练习题
战德臣 教授
7、关于“存储程序”，下列说法不正确的是_____。(A|B|C|D) (A)将“指令”和“数据”以同等地位保存在存储器中，以便于机器自动读取自动处
串； (C)将形如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同， 转换为 XYXY， XYXYXYXY的形式； (D)将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换 为XXXYYY， XXXXYYYY的形式。
理； (B)之所以将“程序”和“数据”事先存储于存储器中，是因为输入的速度满足不了 机器处理的速度，为使机器连续自动处理，所以要“存储程序”； (C)依据“存储程序”原理，机器可由四大部分构成：运算器、存储器、输入设备
和输出设备； (D)冯.诺依曼计算机的本质就是“存储程序、连续自动执行”。
模拟练习题
V=C+M V=C+C V =C+C
不能识别
V =C+C；
V=C+C;
能识别
模拟练习题
战德臣 教授
6、下图为用状态转换图示意的一个图灵机，其字母集合为{V，C，+，=，“空格”，；}；状态集合 {S1，S2，S3，S4，S5，S6，S7}，其中S1为起始状态，S7为终止状态；箭头表示状态转换，其上标 注的如<in, out, direction>表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭 头方向实现转换，其中in,out均是字母集中的符号，null表示什么也不写，direction可以为R(向右移 动)、L(向左移动)、N(停留在原处)。 关于该图灵机的功能，说法不正确的是_____。(A|B|C|D) (A)既能够识别“V=C+C；”形式的符号串，又能识别“V=V+C；”形式的符号串； (B)既能够识别“V=C；”形式的符号串，又能识别“V=V；”形式的符号串； (C)既能够识别“V=V+C；”形式的符号串，又能识别“V=C+V；”形式的符号串； (D)上述说法不正确，即有该图灵机不能识别的符号串形式。
… XXX YY1 XXX YYY
… XXX YYY XXX YYY XXX YYY XXX YYY XXX YYY
模拟练习题
战德臣 教授
4、下图为用状态转换图示意的一个图灵机，其字母集合为{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(停留在原处)。 该图灵机的功能是_____。(A|B|C|D) (A)识别是否如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同； (B)识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1