第4章馮諾依曼計算機機器級程序及其執(zhí)行練習題答案解析

1、第4章馮.諾依曼計算機：機器級程序及其執(zhí)行諾依曼計算機：機器級程序及其執(zhí)行1、關于“圖靈機”，下列說法不正確的是_____。(A)圖靈機給出的是計算機的理論模型；(B)圖靈機的狀態(tài)轉(zhuǎn)移函數(shù)，其實就是一條指令，即在q狀態(tài)下，當輸入為X時，輸出為Y，讀寫頭向右(R)、向左(L)移動一格或不動(N)，狀態(tài)變?yōu)閜；(C)圖靈機是一種離散的、有窮的、構造性的問題求解思路；(D)凡是能用算法方法解決的問題也一定能用圖靈機解決；凡是圖靈機解決不了的問

2、題人和算法也解決不了；(E)上述有不正確的。答案：E解釋：本題考核基本的圖靈機模型。20世紀30年代，圖靈提出了圖靈機模型，建立了指令、程序及通用機器執(zhí)行程序的理論模型，奠定了計算理論的基礎，因此(A)正確；選項(B)是圖靈機的五元組形式的指令集，是一個行動集合，又稱狀態(tài)轉(zhuǎn)移函數(shù)，因此正確；圖靈機是一種離散的、有窮的、構造性的問題求解思路，一個問題的求解可以通過構造其圖靈機（即算法和程序）來解決，因此(C)正確；(D)為圖靈可計算性問題

3、，正確。綜上，本題答案為(E)。具體內(nèi)容請參考第四章視頻之“圖靈機的思想與模型簡介”以及第四章課件。2、關于“圖靈機”和“計算”，下列說法不正確的是_____。(A)計算就是對一條兩端可無限延長的紙帶上的一串0和1，一步一步地執(zhí)行指令，經(jīng)過有限步驟后得到的一個滿足預先規(guī)定的符號串的變換過程；(B)“數(shù)據(jù)”可被制成一串0和1的紙帶送入機器中進行自動處理，被稱為數(shù)據(jù)紙帶；處理數(shù)據(jù)的“指令”也可被制作成一串0和1的紙帶送入機器中，被稱為程序紙

4、帶；機器一方面閱讀程序紙帶上的指令，并按照該指令對數(shù)據(jù)紙帶上的數(shù)據(jù)進行變換處理。(C)計算機器可以這樣來制造：讀取程序紙帶上的指令，并按照該指令對數(shù)據(jù)紙帶上的數(shù)據(jù)做相應的變換，這就是圖靈機的基本思想；(D)上述有不正確的。答案：D大學計算機計算思維練習題集當遇到第一個0，將0轉(zhuǎn)換成X，然后向右移一位，進入狀態(tài)S2，該狀態(tài)檢測下一位是否為1，當不是的話，什么都不做，直接向右移一位，知道遇到第一個1，遇到以后，將1轉(zhuǎn)換成Y，向左移動，進入到

5、狀態(tài)S3，該狀態(tài)回溯0、1串，直到遇到X，然后指向在其右側(cè)的符號，返回到S1狀態(tài)。這個過程即為一個左側(cè)連續(xù)0的個數(shù)和右側(cè)連續(xù)1的個數(shù)相同的0、1串，每次都尋找排在最前面的一個0和一個1，將它們分別轉(zhuǎn)換成X，Y，直到所有的0和1轉(zhuǎn)換為X和Y。因此，答案(D)正確。具體內(nèi)容請參考第四章視頻之“圖靈機的思想與模型簡介”以及第四章課件。4、下圖為用狀態(tài)轉(zhuǎn)換圖示意的一個圖靈機，其字母集合為01XYB，其中B為空白字符；狀態(tài)集合S1，S2，S3，S

6、4，S5，S6，其中S1為起始狀態(tài)，S6為終止狀態(tài)；箭頭表示狀態(tài)轉(zhuǎn)換，其上標注的如表示輸入是in時，輸出out，向direction方向移動一格，同時將狀態(tài)按箭頭方向?qū)崿F(xiàn)轉(zhuǎn)換，其中inout均是字母集中的符號，direction可以為R(向右移動)、L(向左移動)、N(停留在原處)。該圖靈機的功能是_____。(A)識別是否如0101，01010101的0、1串，即一個0接續(xù)一個1，且0的個數(shù)和1的個數(shù)相同；(B)識別是否如000111