第4章冯.诺依曼计算机：机器级程序

及其执行

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

(A)图灵机给出的是计算机的理论模型；

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

(C)图灵机是一种离散的、有穷的、构造性的问题求解思路；

(D)凡是能用算法方法解决的问题也一定能用图灵机解决；凡是图灵机解决不了的问题人和算法也解决不了；

(E)上述有不正确的。

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

(A)计算就是对一条两端可无限延长的纸带上的一串0和1，一步一步地执行指令，经过有限步骤后得到的一个满足预先规定的符号串的变换过程；

(B)“数据”可被制成一串0和1的纸带送入机器中进行自动处理，被称为数据纸带；处理数据的“指令”也可被制作成一串0和1的纸带送入机器中，被称为程序纸带；机器一方面阅读程序纸带上的指令，并按照该指令对数据纸带上的数据进行变换处理。

(C)计算机器可以这样来制造：读取程序纸带上的指令，并按照该指令对数据纸带上的数据做相应的变换，这就是图灵机的基本思想；

(D)上述有不正确的。

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

为空白字符；状态集合{S

1，S

2

，S

3

，S

4

，S

5

}，其中S

1

为起始状态，S

5

为终止状态；

箭头表示状态转换，其上标注的如表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。

该图灵机的功能是_____。

(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串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的形式。

答案是：D

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

为空白字符；状态集合{S

1，S

2

，S

3

，S

4

，S

5

，S

6

}，其中S

1

为起始状态，S

6

为终止

状态；箭头表示状态转换，其上标注的如表示输入是in 时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。

该图灵机的功能是_____。

(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串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的形式。

答案是：B

5、下图为用状态转换图示意的一个图灵机，其字母集合为{V，C，+，=，“空

格”，；}；状态集合{S

1，S

2

，S

3

，S

4

，S

5

，S

6

，S

7

}，其中S

1

为起始状态，S

7

为终

止状态；箭头表示状态转换，其上标注的如表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，null表示什么也不写，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。

该图灵机的功能是_____。

(A)能够识别“V=C+C；”形式的符号串；

(B)能够识别“V=C；”形式的符号串；

(C)能够将符号串中的空格去除掉；

(D)上述全部能够识别。

答案是：D

6、下图为用状态转换图示意的一个图灵机，其字母集合为{V，C，+，=，“空

格”，；}；状态集合{S

1，S

2

，S

3

，S

4

，S

5

，S

6

，S

7

}，其中S

1

为起始状态，S

7

为终

止状态；箭头表示状态转换，其上标注的如表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，null表示什么也不写，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。

关于该图灵机的功能，说法不正确的是_____。

(A)既能够识别“V=C+C；”形式的符号串，又能识别“V=V+C；”形式的符号串；

(B)既能够识别“V=C；”形式的符号串，又能识别“V=V；”形式的符号串；

(C)既能够识别“V=V+C；”形式的符号串，又能识别“V=C+V；”形式的符号串；

(D)上述说法不正确，即有该图灵机不能识别的符号串形式。

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

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

(B)之所以将“程序”和“数据”事先存储于存储器中，是因为输入的速度满足不了机器处理的速度，为使机器连续自动处理，所以要“存储程序”；

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

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

8、关于“冯.诺依曼计算机”的结构，下列说法正确的是_____。

(A)冯.诺依曼计算机仅需要三大部件即可：运算器、控制器和存储器；

(B)一般，个人计算机是由中央处理单元(CPU)、存储器、输入设备和输出设备构成，没有运算器和控制器，所以它不是冯.诺依曼计算机；

(C)以“运算器”为中心的冯.诺依曼计算机和以“存储器”为中心的冯.诺依曼计算机是有差别的，前者不能实现并行利用各个部件，受限于运算器；后者可以实现并行利用各个部件；

(D)冯.诺依曼计算机提出“运算”和“存储”完全没有必要。

9、下图是一个存储器的简单模型。围绕该存储器模型，回答下列问题。

(1)下列说法不正确的是_____。

(A)该存储器可存取4个4位的存储单元；

(B)该存储器其中的一个存储单元的内容是1010；

(C)该存储器既可读出，又可写入；

(D)该存储器的地址码分别是00，01，10和11。

答案是：C

(2)内容为1010的存储单元的地址编码A1A0是_____。

(A)00； (B)01； (C)10； (D)11； (E)没有该存储单元。

答案是：C

(3) A1A0为01的存储单元，其内容D3D2D1D0是_____。

(A)0101； (B)1010； (C)0111； (D)1110； (E)没有该存储单元。答案是：C

10、下图是一个存储器的简单模型。围绕该存储器模型，回答下列问题。

(1)当A

1A

=10时，D

5

D

4

D

3

D

2

D

1

D

的内容是_____。

(A) 100101； (B)011101； (C)101010； (D)010101；(E)都不对。答案是：C

(2)当存储单元的内容是100101时，其存储单元的地址编码A

1A

是_____。

(A)00； (B)01； (C)10； (D)11； (E)没有该存储单元。答案是：A

11、下图是一个存储器的简单模型-与或阵列图。请回答下列问题。

(1)围绕该存储器模型，请写出由A

1、A

产生W

3

、W

2

、W

1

、W

的逻辑表达式，书写

正确的是_____。

(A) W

00 = (NOT A

1

) OR (NOT A

)；

(B) W

01 = (NOT A

1

) AND A

；

(C) W

10 = A

1

OR (NOT A

)；

(D) W

11 = A

1

AND (NOT A

)。

(2)围绕该存储器模型，请写出由W

3、W

2

、W

1

、W

产生D

4

、D

3

、D

2

、D

1

、D

的逻辑表

达式，书写不正确的是_____。

(A) D

4 = W

00

OR W

01

OR W

11

；

(B) D

3 = W

10

OR W

11

；

(C) D

2 = W

01

OR W

10

；

(D) D

1 = W

00

OR W

01

OR W

11

；

(E) D

0 = W

00

OR W

10

；

12、已知一个存储器芯片M的4位二进制地址编码为A

3A

2

A

1

A

，其8条数据线为

D

7D

6

D

5

D

4

D

3

D

2

D

1

D

，回答下列问题。

(1)下列说法正确的是_____。

(A)该存储器共有28即256个存储单元；

(B)该存储器共有24即16个存储单元；

(C)该存储器存储单元的位数，即字长为4位；

(D)该存储器的存储容量为24×8字节。

(2)如果需要构造256个存储单元且每个存储单元的字长为16位的存储器，问下列说法正确的是_____。

(A)总计需要M芯片16个；

(B)总计需要M芯片8个；

(C)总计需要M芯片32个；

(D)总计需要M芯片64个。

(*3)如果需要构造64个存储单元且每个存储单元的字长为16位的存储器，该存

储器的6位二进制地址编码线为B

5B

4

B

3

B

2

B

1

B

，16条数据线为E

15

~E

，问下列说法

正确的是_____。

(A)总计需要M芯片8个；将B

3B

2

B

1

B

分别连接到8个M芯片的A

3

A

2

A

1

A

上；将B

5

B

4

用一个2-4译码器进行译码形成4条控制线，每一条控制两个M芯片；将8个芯

片任意分成两组，将E

15~E

8

和E

7

~E

分别连接到这2个组中的每个芯片的D

7

~D

上。

(B)总计需要M芯片16个，分成8组，每组两个；将B

3B

2

B

1

B

分别连接到16个M

芯片的A

3A

2

A

1

A

上；将B

5

B

4

B

3

用一个3-8译码器进行译码形成8条控制线，每一条

控制一组中的两个M芯片；将E

15~E

8

分别连接到这8个组中的第一个芯片的D

7

~D

上，而将E

7~E

分别连接到这8个组中的另一个芯片的D

7

~D

上。

(C)总计需要M芯片8个，分成4组，每组两个；将B

3B

2

B

1

B

分别连接到8个M芯

片的A

3A

2

A

1

A

上；将B

5

B

4

用一个2-4译码器进行译码形成4条控制线，每一条控

制一组中的两个M芯片；将E

15~E

8

分别连接到这4个组中的第一个芯片的D

7

~D

上，而将E

7~E

分别连接到这4个组中的另一个芯片的D

7

~D

上。

(D)总计需要M芯片8个，分成2组，每组4个；将B

3B

2

B

1

B

分别连接到8个M芯

片的A

3A

2

A

1

A

上；将B

5

B

4

用一个2-4译码器进行译码形成4条控制线，每2条控

制线控制一组M芯片；将E

15~E

8

分别连接到第一组每个芯片的D

7

~D

上，而将E

7

~E

分别连接到第2组每个芯片的D

7~D

上。

13、已知某机器的指令集合及指令格式如下表示意。

已经编制好并存储在存储器中的一段程序如下表示意，请阅读这段程序，并回答下述问题。

(1) 关于存储器存放的内容，下列说法正确的是_____。

(A) 3号存储单元存放的是数据，而8号存储单元存放的是指令；

(B) 3号存储单元存放的是数据，而8号存储单元存放的是数据；

(C) 3号存储单元存放的是指令，而8号存储单元存放的是数据；

(D) 3号存储单元存放的是指令，而8号存储单元存放的是指令。

(2) 存储器1号存储单元中存放的指令功能是_____。

(A) 将运算器中寄存器A的数，加上9号存储单元的数2，结果保留在运算器的

寄存器A中；

(B) 将运算器中寄存器A的数，乘以9号存储单元的数7，结果保留在运算器的寄存器A中；

(C) 将运算器中寄存器A的数，乘以10号存储单元的数6，结果保留在运算器的寄存器A中；

(D) 将运算器中寄存器A的数，乘以9号存储单元的数2，结果保留在运算器的寄存器A中。

(3) 存储器2号存储单元中存放的指令功能是_____。

(A) 将10号存储单元的数，取出送到运算器的寄存器A中；

(B) 将运算器中寄存器A的数，加上10号存储单元的数，结果保留在运算器的寄存器A中；

(C) 将运算器的寄存器A中的数，保存到10号存储单元中；

(D) 将运算器中寄存器A的数，乘以10号存储单元的数，结果保留在运算器的寄存器A中。

(*4)该程序所能完成的计算是_____。

(A) 7 × 22+ 6 × 2 + 3；

(B) 2 × 72+ 6 × 7 + 3；

(C) 6 × 32+ 2 × 3 + 7；

(D) 6 × 32+ 7 × 3 + 2；

(E) 以上都不正确。

(*5)若要使该程序完成计算8 × 32+ 2 × 3 + 6，则需修正存储的数据，正确的修正是_____。

(A) 8号存储单元存放数00000000 00000110，9号存储单元存放数00000000 00001000，

10号存储单元存放数00000000 00000010，11号存储单元存放数 00000000 00000011；

(B) 8号存储单元存放数00000000 00001000，9号存储单元存放数00000000 00000011，

10号存储单元存放数00000000 00000010，11号存储单元存放数 00000000 00000110；

(C) 8号存储单元存放数00000000 00000011，9号存储单元存放数00000000 00001000，

10号存储单元存放数00000000 00000010，11号存储单元存放数 00000000 00000110；

(D) 8号存储单元存放数00000000 00000010，9号存储单元存放数00000000 00000011，

10号存储单元存放数00000000 00000110，11号存储单元存放数 00000000 00001000。

(*6)若要使该程序完成任意方程式ax2+bx+c，则需修正存储的数据，正确的修正是_____。

(A) 8号存储单元存放数a的二进制数，9号存储单元存放数x的二进制数，10号存储单元存放数b的二进制数，11号存储单元存放数c的二进制数；(B) 8号存储单元存放数a的二进制数，9号存储单元存放数b的二进制数，10号存储单元存放数c的二进制数，11号存储单元存放数x的二进制数；(C) 8号存储单元存放数x的二进制数，9号存储单元存放数a的二进制数，10号存储单元存放数b的二进制数，11号存储单元存放数c的二进制数；(D) 8号存储单元存放数c的二进制数，9号存储单元存放数b的二进制数，10号存储单元存放数a的二进制数，11号存储单元存放数x的二进制数。

14、已知某机器的核心部件及其结构关系如下图示意。请仔细理解该结构图，并回答下述问题。

(1) 保存下一条将要执行的指令地址的寄存器是_____。

(A) IR； (B) R

0或R

1

；(C) 存储器的地址寄存器；(D) PC。

答案是：D

(2) 保存正在执行指令的寄存器是_____。

(A) IR； (B)R

0或R

1

；(C) 存储器的地址寄存器；(D) PC。

答案是：A

(3) 当CPU在执行000100 0000001001指令时，PC的值是_____。

(A) 00000000 00000001； (B) 00000000 00000010；

(C) 00000000 00000011； (D) 00000000 00000100。

答案是：B

(4) 当CPU在执行000100 0000001001指令时，IR的值是_____。

(A) 00000100 00001000； (B) 00010000 00001001；

(C) 00001100 00001010； (D) 00010000 00001000。

(*5) 当CPU在读取指令阶段，下列说法正确的是_____。

(A) 第1个节拍进行A1，C3；第2个节拍进行D1，C4，D2；

(B) 第1个节拍进行A2，C3；第2个节拍进行D1，C2，D6；

(C) 第1个节拍进行A1，C3；第2个节拍进行D1，C4，D2或D3；

(D) 第1个节拍进行A1，C3，C1；第2个节拍进行D1，C2，D6。

(*6) 当CPU在执行指令阶段，假设当前执行的指令“00000100 00001000—将8号单元内容取出到寄存器R1中并与运算器中寄存器R0的值相乘，结果保留在

R0中”，则下列说法正确的是_____。

(A) 第3个节拍进行A2，C3，C1；第4个节拍进行D1，C4，D2；第5个节拍进行C5；

(B) 第3个节拍进行A1，C3；第4个节拍进行D1，C4，D2；第5个节拍进行C5；

(C) 第3个节拍进行A2，C3, C1；第4个节拍进行D1，C5，D2；

(D) 第3个节拍进行A2，C3，C1；第4个节拍进行D1，C4，D4；第5个节拍进行C5。

(*7) 关于机器指令的执行，则下列说法不正确的是_____。

(A) 控制器不断地从存储器中读取指令，并按照指令的内容进行执行；

(B) 机器指令的执行即是在时钟节拍控制下产生一系列信号的过程；

(C) 没有时钟与节拍发生器，机器的指令也能正确地执行；

(D) 没有PC，机器就不能正确地执行程序。

15、关于“存储在存储器中程序的执行”问题，下列说法不正确的是_____。

(A) 机器需要提供一个其可以执行的指令集合；

(B) 人们用指令集合中的指令编写程序，并将编写好的程序和数据事先存放于存储器中；

(C) 控制器一条接一条的从存储器中读取指令，读取一条指令则执行一条指令，一条指令执行完成后，再读下一条指令；

(D) 当读取一条指令后，程序计数器PC的值自动加1，以指向下一条将要读取的指令；当程序需要转往它处执行时，则可以它处存放指令的地址来修改PC的值即可；

(E)上述说法有不正确的。