中國大學mooc《大學計算機-計算思維導論SPOC（張麗杰）(哈爾濱工業(yè)大學) 》章節(jié)測試答案

title大學計算機-計算思維導論SPOC（張麗杰）(哈爾濱工業(yè)大學)中國大學mooc答案100分最新版content

第1講計算機、計算與計算思維第1講測驗1、計算機器的基本目標是什么？答案:能夠執(zhí)行一般的任意復雜的計算規(guī)則2、衡量存儲設(shè)備性能的指標包括_。答案:其它三個選項都包括3、計算之樹中，網(wǎng)絡(luò)化思維是怎樣概括的？答案:機器網(wǎng)絡(luò)、信息網(wǎng)絡(luò)和人-機-物互聯(lián)的網(wǎng)絡(luò)化社會4、計算機包括_____。答案:其它三個選項都包括5、“人”計算與“機器”計算有什么差異？答案:其它選項的說法都正確6、衡量微處理器芯片性能好壞的指標包括_。答案:其它選項都包括7、關(guān)于計算系統(tǒng)，下列說法正確的是_。答案:計算系統(tǒng)由微處理器、存儲設(shè)備、輸入設(shè)備和輸出設(shè)備構(gòu)成8、人類應具備的三大思維能力是指_____。答案:實驗思維、理論思維和計算思維9、自動計算需要解決的基本問題是什么？答案:數(shù)據(jù)和計算規(guī)則的表示、自動存儲和計算規(guī)則的自動執(zhí)行10、電子計算機器的基本特征是什么？答案:其它三個選項都正確11、計算系統(tǒng)的發(fā)展方向是_。答案:其它三個選項都是正確的12、計算之樹中，通用計算環(huán)境的演化思維是怎樣概括的？答案:程序執(zhí)行環(huán)境—由CPU-內(nèi)存環(huán)境，到CPU-存儲體系環(huán)境，到多CPU-多存儲器環(huán)境，再到云計算虛擬計算環(huán)境13、計算之樹中，兩類典型的問題求解思維是指__。答案:算法和系統(tǒng)14、本課程中擬學習的計算思維是指_____。答案:蘊含在計算學科知識背后的具有貫通性和聯(lián)想性的內(nèi)容15、計算學科的計算研究什么?答案:面向機器可自動執(zhí)行的求解一般問題的計算規(guī)則16、摩爾定律是指_。答案:芯片集成晶體管的能力每18個月增長一倍，其計算能力也增長一倍17、下列說法正確的是_。答案:軟盤是可移動的可更換的永久存儲器18、IBM提出的SmartPlanet基本特點是什么_。答案:其它選項內(nèi)容結(jié)合在一起才是SmartPlanet19、關(guān)于計算系統(tǒng)的網(wǎng)絡(luò)化的說法正確的是_。答案:未來互聯(lián)網(wǎng)將發(fā)展為包括物聯(lián)網(wǎng)、社會網(wǎng)絡(luò)、服務網(wǎng)絡(luò)以及與現(xiàn)實中各種網(wǎng)絡(luò)深度融合的網(wǎng)絡(luò)系統(tǒng)20、為什么要學習計算思維?因為

_。答案:不僅僅是其它三個選項的理由,有很多理由說明大思維比小技巧更重要，思維的學習比知識的學習更重要21、計算之樹概括了計算學科的經(jīng)典思維，它是從幾個維度來概括的？答案:六個維度：計算技術(shù)的奠基性思維、通用計算環(huán)境的演化思維、社會/自然與計算的融合思維、問題求解思維、網(wǎng)絡(luò)化思維和數(shù)據(jù)化思維22、計算之樹中，計算技術(shù)的奠基性思維包括__。答案:0和1、程序和遞歸23、如何學習計算思維？答案:其它三個選項都是正確的

第2講符號化、計算化與自動化第2講測驗1、易經(jīng)的乾卦是從“天”這種自然現(xiàn)象抽象出來的，為什么稱其為“乾”而不稱其為“天”呢？______。答案:“天”是一種具體事物，只能在自然空間中應用，若變換到不同空間應用，可能會引起混淆；而“乾”是抽象空間中的概念，是指具有“天”這種事務的性質(zhì)，應用于不同的空間時不會產(chǎn)生這種問題2、易經(jīng)的符號化案例，啟示我們______。答案:其它選項的說法都正確3、關(guān)于漢字內(nèi)碼，下列說法不正確的是______。答案:漢字內(nèi)碼是機器存儲和顯示漢字所使用的編碼4、0和1的思維反映了語義符號化→符號計算化→計算0(和)1化→0(和)1自動化→分層構(gòu)造化→構(gòu)造集成化，關(guān)于此思維的說法不正確的是______。答案:其它三個選項的說法有不正確的5、假設(shè)基本門電路的符號為，已知如下電路

問該電路所實現(xiàn)的正確的邏輯運算為______。答案:P=A

XOR

B6、下列說法不正確的是______。答案:其它三個選項的說法有不正確的7、已知：關(guān)于和的邏輯運算式如下：

=(

XOR

)XOR

=(

AND

)OR((

XOR

)AND

)如果

=1，

=1，

=1，則，

的值為______。答案:1,18、假設(shè)基本門電路的符號為，已知如下電路問該電路不能實現(xiàn)的功能為______。答案:當A=1，B=1，則P=19、邏輯的符號化案例，啟示我們______。答案:其它三個選項都正確10、將十六進制數(shù)586轉(zhuǎn)換成16位的二進制數(shù)，應該是______。答案:000001011000011011、若用8位0，1表示一個二進制數(shù)，其中1位即最高位為符號位，其余7位為數(shù)值位。的原碼、反碼和補碼表示，正確的是______。答案:

00001111，00001111，0000111112、若用5位0，1表示一個二進制數(shù)，其中1位即最高位為符號位，其余4位為數(shù)值位。若要進行11–4的操作，可轉(zhuǎn)換為11(-4)的操作，采用補碼進行運算，下列運算式及結(jié)果正確的是______。答案:0101111100=0011113、已知A-Z的ASCII碼是41H-5AH，請將下面一段ASCII碼存儲的文件解析出來，正確的是______。

“010001110100010101000111010001100100100001000010”答案:GEGFHB14、計算機內(nèi)部使用的編碼的基本特征是______。答案:唯一性和公共性15、已知：M、N和K的值只能有一個1，其他為0，并且滿足下列所有邏輯式：((MAND(NOTK))OR((NOTM)ANDK))=1；(NOTN)AND((MAND(NOTK))OR((NOTM)ANDK))=1；(NOTN)AND(NOTK)=1；問：M、N、K的值為______。答案:1，0，016、關(guān)于十進制245的下列說法不正確的是______。答案:它轉(zhuǎn)換為二進制表示為1101010117、已知：關(guān)于和的邏輯運算式如下：

=(

XOR

)XOR

=(

AND

)OR((

XOR

)AND

)問：

如果

=1，

=0，

=1，則，

的值為______。答案:0，118、易經(jīng)是用0和1符號化自然現(xiàn)象及其變化規(guī)律的典型案例。下列說法不正確的是______。答案:易經(jīng)僅僅是以自然現(xiàn)象為依托，對人事及未來進行占卜或算卦的一種學說19、邏輯運算是最基本的基于“真/假”值的運算，也可以被看作是基于“1/0”的運算，1為真，0為假。關(guān)于基本邏輯運算，下列說法不正確的是______。答案:“異或”運算是“相同為1，不同為0”20、將十進制數(shù)126.375轉(zhuǎn)換成二進制數(shù)，應該是______。答案:01111110.011021、下列數(shù)中最大的數(shù)是______。答案:22、關(guān)于計算機為什么基于二進制數(shù)來實現(xiàn)，下列說法不正確的是______。答案:其它三個選項的說法有不正確的23、關(guān)于二進制算術(shù)運算，下列說法不正確的是______。答案:二進制算術(shù)運算的符號位不能和數(shù)值位一樣參與運算但能得到正確的結(jié)果24、關(guān)于二進制數(shù)計算部件的實現(xiàn)，下列說法正確的是______。答案:設(shè)計和實現(xiàn)一個最簡單的計算部件只需實現(xiàn)邏輯與、或、非、異或等基本運算即可，則所有加減乘除運算即可由該計算部件來實現(xiàn)25、關(guān)于二進制小數(shù)的處理，下列說法不正確的是______。答案:其它選項的說法有不正確的26、若用8位0，1表示一個二進制數(shù)，其中1位即最高位為符號位，其余7位為數(shù)值位。的原碼、反碼和補碼表示，正確的是______。答案:10010010，11101101，1110111027、若用5位0，1表示一個二進制數(shù)，其中1位即最高位為符號位，其余4位為數(shù)值位。若要進行-7–4的操作，可轉(zhuǎn)換為(-7)(-4)的操作，采用補碼進行運算，下列運算式及結(jié)果正確的是______。答案:1100111100=1010128、若用5位0，1表示一個二進制數(shù)，其中1位即最高位為符號位，其余4位為數(shù)值位。若要進行-7–13的操作，可轉(zhuǎn)換為(-7)(-13)的操作，采用補碼進行運算，下列運算式及結(jié)果正確的是______。答案:1100110011=01100(溢出)29、關(guān)于漢字外碼，下列說法不正確的是______。答案:漢字外碼有拼音碼、音型碼、字型碼和字模點陣碼30、假設(shè)基本門電路的符號為已知如下電路

問該電路不能實現(xiàn)的功能為______。答案:當A=0，B=1，則P=031、假設(shè)基本門電路的符號為已知如下電路

問該電路所實現(xiàn)的正確的邏輯運算為______。答案:P=AXORB32、假設(shè)基本門電路的符號為已知如下電路

問該電路不能實現(xiàn)的功能為______。答案:當A=1，B=1，則P=133、關(guān)于十進制235，下列正確的是______。答案:其ASCII碼為001100100011001100110101

第3講程序與遞歸：組合、抽象與構(gòu)造第3講測驗1、關(guān)于遞歸定義的函數(shù)，下列說法正確的是_____。答案:有些遞歸定義的函數(shù)可以“迭代計算”，有些遞歸定義的函數(shù)則必須“遞歸計算”2、遞歸計算是重要的執(zhí)行手段。例如一種形式的阿克曼函數(shù)如下所示：

任何一個A(m,n)都可以遞歸地進行計算，例如A(1,2)的遞歸計算過程如下所示：A(1,2)=A(0,A(1,1))=A(0,A(0,A(1,0)))=A(0,A(0,A(0,1)))=A(0,A(0,2))=A(0,3)=4。請你按上述方法遞歸計算下列項，并判斷，計算結(jié)果正確的是_____。答案:A(1,n)=n+23、遞歸計算是重要的執(zhí)行手段。例如一種形式的阿克曼函數(shù)如下所示：

任何一個A(n,m)都可以遞歸地進行計算，例如m=1時，A(n,1)的遞歸計算過程如下所示：m=1時，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2n請你按上述方法遞歸計算m=2時，即A(n,2)，并判斷計算結(jié)果正確的是_____。答案:A(n,2)=

4、用遞歸是可以定義語言的。如表述命題邏輯的一種語言可以如下定義：(1)一個命題是其值為真或假的一個判斷語句；(2)如果X是一個命題，Y也是一個命題，則XandY，XorY,notX也是一個命題；(3)如果X是一個命題，則(X)也是一個命題，括號內(nèi)的命題運算優(yōu)先；(4)命題由以上方式構(gòu)造。若X，Y，Z，M等均是一個命題，問不符合上述遞歸定義的語句是_____。答案:

(XandYnotZ)5、已知f(x)=5，，其中均為自然數(shù)，新函數(shù)h可遞歸的構(gòu)造如下：h(0,x)=f(x),且h(S(n),x)=g(h(n,x),n,x)，請按遞歸式進行計算下列式子，正確的是_____。答案:

h(1，x)=56、用條件運算符定義一個過程。正確的定義為_____。

答案:7、一般而言，設(shè)計和實現(xiàn)一個計算系統(tǒng)，需要設(shè)計和實現(xiàn)_____。答案:基本動作、控制基本動作的指令和一個程序執(zhí)行機構(gòu)8、關(guān)于計算系統(tǒng)與程序，下列說法正確的是_____。答案:任何系統(tǒng)都需要程序，只是這個程序是由人來執(zhí)行還是由機器自動執(zhí)行，可以由機器自動執(zhí)行程序的系統(tǒng)被稱為計算系統(tǒng)9、已知一個新運算被定義為(define

(newCalc

x

y)(

(+

x

1)

(

y

2)))，問正確使用了newCalc并得到正確結(jié)果的為_____。答案:(newCalc

4

5)，其結(jié)果為5010、關(guān)于“程序”和“遞歸”的關(guān)系，下列說法不正確的是_____。答案:其它選項的說法有不正確的11、用條件運算符定義一個過程。正確的定義為_____。答案:12、已知一個運算被定義為(define

(firstCalc

x)

(*

x

x))，在其基礎(chǔ)上進一步定義新運算secondCalc為，下列運算組合式書寫正確的是_____。答案:(define(secondCalcxyz)

(+

(firstCalc

x)

(firstCalc

y)

(firstCalc

z)))13、已知一個運算被定義為(define

(firstCalc

x)

(*

x

x))，在其基礎(chǔ)上進一步定義新運算為(define

(secondCalc

x)

(firstCalc

(firstCalc

(firstCalc

x))))，問secondCalc表達的運算功能為_____。答案:14、若要表達從1計算到n的運算組合式，(

…(

(

(

(*

1

1)

2)

3)

4)

…n)定義一個過程。正確的定義為_____。答案:15、按原始遞歸的定義，h是由f和g遞歸地構(gòu)造出來的。假設(shè)已知h(n)=n!，請給出構(gòu)造h的f和g的函數(shù)。正確的是_____。答案:f()是常數(shù)為1的函數(shù)；16、已知，,其中均為自然數(shù)，新函數(shù)h可遞歸的構(gòu)造如下：h(0,x)=f(x),且h(S(n),x)=g(h(n,x),n,x)，請按遞歸式進行計算下列式子，不正確的是_____。答案:h(4，x)=12x17、斐波那契數(shù)列與阿克曼函數(shù)都是遞歸函數(shù)，但它們是不同的，下列說法不正確的是_____。

答案:阿克曼函數(shù)也可如斐波那契數(shù)列一樣自前項(第n-1項)計算到后項(第n項)18、已知f(x)=x，,其中均為自然數(shù)，新函數(shù)h可遞歸的構(gòu)造如下：h(0,x)=f(x),且h(S(n),x)=g(h(n,x),n,x)，請按遞歸式進行計算下列式子，正確的是_____。答案:h(4，x)=5x+619、已知一個新運算被定義為(define

(newCalc

x

y)(*

(+

x

1)

(+

y

1)))，問(newCalc(newCalc(newCalc1

1)

2)

3)的計算結(jié)果為_____。答案:6420、已知一個新運算被定義為(define

(newCalc

x

y)(*

(+

x

1)

(+

y

1)))，問(newCalc

(newCalc(newCalc1

1)

(newCalc1

1))

(newCalc11))的計算結(jié)果為_____。答案:13021、關(guān)于“遞歸”，下列說法不正確的是_____。答案:“遞歸”與遞推式一樣，都是自遞推基礎(chǔ)計算起，由前項(第n-1項)計算后項(第n項)，直至最終結(jié)果的獲得22、關(guān)于程序，下列說法不正確的是_____。答案:其它選項的說法有不正確的23、關(guān)于“遞歸”，下列說法不正確的是_____。答案:其它選項的說法不全正確24、關(guān)于原始遞歸函數(shù)的理解，下列說法不正確的是_____。答案:其它選項的說法有不正確的25、對于計算式，其正確的運算組合式(前綴表示法)為_____。答案:(/

(+

10

(/

20

(+

8

4)))

(+

(

3

6)

(*

8

2)))26、關(guān)于程序，下列說法不正確的是_____。答案:普通人是很難理解“程序”的，其也和“程序”無關(guān)27、請用define運算，定義一個過程實現(xiàn)計算，其正確定義的過程為_____。答案:(define

(cube

x)

(*

x

x

x))28、熟悉下列運算組合式(前綴表達式)，其中結(jié)果為56的是_____。答案:(

(+

5

3)

(+

5

2))29、已知一個新運算被定義為(define

(newCalc

x

y)(

(+

x

1)

(

y

2)))，問newCalc可以完成的計算功能為_____。答案:(x+1)*2y第4講馮.諾依曼計算機—機器級程序及其執(zhí)行第4講測驗1、關(guān)于“存儲程序”，下列說法不正確的是_____。答案:依據(jù)“存儲程序”原理，機器可由四大部分構(gòu)成：運算器、存儲器、輸入設(shè)備和輸出設(shè)備2、已知某機器的核心部件及其結(jié)構(gòu)關(guān)系如下圖示意。請仔細理解該結(jié)構(gòu)圖，并回答問題。當CPU在讀取指令階段，下列說法正確的是_____。答案:第1個節(jié)拍進行A1，C3；第2個節(jié)拍進行D1，C2，D63、已知某機器的核心部件及其結(jié)構(gòu)關(guān)系如下圖示意。請仔細理解該結(jié)構(gòu)圖，并回答問題。當CPU在執(zhí)行指令階段，假設(shè)當前執(zhí)行的指令“0000010000001000—將8號單元內(nèi)容取出到寄存器中并與運算器中寄存器的值相乘，結(jié)果保留在中”，則下列說法正確的是_____。答案:第3個節(jié)拍進行A2，C3，C1；第4個節(jié)拍進行D1，C4，D2；第5個節(jié)拍進行C54、已知某機器的指令集合及指令格式如下表示意。

已經(jīng)編制好并存儲在存儲器中的一段程序如下表示意，請閱讀這段程序，并回答問題。

若要使該程序完成計算，則需修正存儲的數(shù)據(jù)，正確的修正是_____。答案:8號存儲單元存放數(shù)0000000000000011，9號存儲單元存放數(shù)0000000000001000，10號存儲單元存放數(shù)0000000000000010，11號存儲單元存放數(shù)00000000000001105、下圖是一個存儲器的簡單模型-與或陣列圖。

圍繞該存儲器模型，請寫出由、、、產(chǎn)生、、、、的邏輯表達式，書寫不正確的是_____。答案:6、關(guān)于“圖靈機”，下列說法不正確的是_____。答案:其它三個選項有不正確的7、關(guān)于“圖靈機”和“計算”，下列說法不正確的是_____。答案:其它三個選項有不正確的8、下圖是一個存儲器的簡單模型。內(nèi)容為1010的存儲單元的地址編碼是_____。

答案:109、已知某機器的指令集合及指令格式如下表示意。

已經(jīng)編制好并存儲在存儲器中的一段程序如下表示意，請閱讀這段程序，并回答問題。

該程序所能完成的計算是_____。答案:10、已知某機器的指令集合及指令格式如下表示意。

已經(jīng)編制好并存儲在存儲器中的一段程序如下表示意，請閱讀這段程序，并回答問題。

關(guān)于存儲器存放的內(nèi)容，下列說法正確的是_____。答案:

3號存儲單元存放的是指令，而8號存儲單元存放的是數(shù)據(jù)11、已知某機器的核心部件及其結(jié)構(gòu)關(guān)系如下圖示意。請仔細理解該結(jié)構(gòu)圖，并回答問題。當CPU在執(zhí)行0001000000001001指令時，IR的值是_____。答案:000100000000100112、已知某機器的核心部件及其結(jié)構(gòu)關(guān)系如下圖示意。請仔細理解該結(jié)構(gòu)圖，并回答問題。關(guān)于機器指令的執(zhí)行，則下列說法不正確的是_____。答案:沒有時鐘與節(jié)拍發(fā)生器，機器的指令也能正確地執(zhí)行13、下圖為用狀態(tài)轉(zhuǎn)換圖示意的一個圖靈機，其字母集合為{0,1,X,Y,B}，其中B為空白字符；狀態(tài)集合{S1，S2，S3，S4，S5}，其中S1為起始狀態(tài)，S5為終止狀態(tài)；箭頭表示狀態(tài)轉(zhuǎn)換，其上標注的如<in,out,direction>表示輸入是in時，輸出out，向direction方向移動一格，同時將狀態(tài)按箭頭方向?qū)崿F(xiàn)轉(zhuǎn)換，其中in,out均是字母集中的符號，direction可以為R(向右移動)、L(向左移動)、N(停留在原處)。

該圖靈機的功能是_____。答案:將形如000111，00001111的0、1串，即左側(cè)連續(xù)0的個數(shù)和右側(cè)連續(xù)1的個數(shù)相同的0、1串轉(zhuǎn)換為XXXYYY，XXXXYYYY的形式14、下圖為用狀態(tài)轉(zhuǎn)換圖示意的一個圖靈機，其字母集合為{0,1,X,Y,B}，其中B為空白字符；狀態(tài)集合{S1，S2，S3，S4，S5，S6}，其中S1為起始狀態(tài)，S6為終止狀態(tài)；箭頭表示狀態(tài)轉(zhuǎn)換，其上標注的如<in,out,direction>表示輸入是in時，輸出out，向direction方向移動一格，同時將狀態(tài)按箭頭方向?qū)崿F(xiàn)轉(zhuǎn)換，其中in,out均是字母集中的符號，direction可以為R(向右移動)、L(向左移動)、N(停留在原處)。

該圖靈機的功能是_____。答案:識別是否如000111，00001111的0、1串，即左側(cè)連續(xù)0的個數(shù)和右側(cè)連續(xù)1的個數(shù)相同的0、1串15、下圖是一個存儲器的簡單模型。為01的存儲單元，其內(nèi)容是_____。

答案:011116、下圖是一個存儲器的簡單模型。當=10時,的內(nèi)容是_____。

答案:10101017、已知一個存儲器芯片M的4位二進制地址編碼為，其8條數(shù)據(jù)線為。如果需要構(gòu)造256個存儲單元且每個存儲單元的字長為16位的存儲器，問下列說法正確的是_____。答案:總計需要M芯片32個18、關(guān)于“馮.諾依曼計算機”的結(jié)構(gòu)，下列說法正確的是_____。答案:以“運算器”為中心的馮.諾依曼計算機和以“存儲器”為中心的馮.諾依曼計算機是有差別的，前者不能實現(xiàn)并行利用各個部件，受限于運算器；后者可以實現(xiàn)并行利用各個部件19、已知一個存儲器芯片M的4位二進制地址編碼為，其8條數(shù)據(jù)線為。如果需要構(gòu)造64個存儲單元且每個存儲單元的字長為16位的存儲器，該存儲器的6位二進制地址編碼線為，16條數(shù)據(jù)線為，問下列說法正確的是_____。答案:總計需要M芯片8個，分成4組，每組兩個；將分別連接到8個M芯片的上；將用一個2-4譯碼器進行譯碼形成4條控制線，每一條控制一組中的兩個M芯片；將分別連接到這4個組中的第一個芯片的上，而將分別連接到這4個組中的另一個芯片的上20、下圖是一個存儲器的簡單模型。下列說法不正確的是_____。

答案:該存儲器既可讀出，又可寫入21、下圖是一個存儲器的簡單模型。當存儲單元的內(nèi)容是100101時，其存儲單元的地址編碼是_____。

答案:0022、已知一個存儲器芯片M的4位二進制地址編碼為，其8條數(shù)據(jù)線為，下列說法正確的是_____。答案:該存儲器共有即16個存儲單元23、已知某機器的指令集合及指令格式如下表示意。

已經(jīng)編制好并存儲在存儲器中的一段程序如下表示意，請閱讀這段程序，并回答問題。

存儲器2號存儲單元中存放的指令功能是_____。答案:將運算器中寄存器A的數(shù)，加上10號存儲單元的數(shù)，結(jié)果保留在運算器的寄存器A中24、已知某機器的指令集合及指令格式如下表示意。

已經(jīng)編制好并存儲在存儲器中的一段程序如下表示意，請閱讀這段程序，并回答問題。

存儲器1號存儲單元中存放的指令功能是_____。答案:將運算器中寄存器A的數(shù)，乘以9號存儲單元的數(shù)2，結(jié)果保留在運算器的寄存器A中25、保存下一條將要執(zhí)行的指令地址的寄存器是_____。答案:PC26、保存正在執(zhí)行指令的寄存器是_____。答案:IR27、已知某機器的核心部件及其結(jié)構(gòu)關(guān)系如下圖示意。請仔細理解該結(jié)構(gòu)圖，并回答問題。當CPU在執(zhí)行0001000000001001指令時，PC的值是_____。答案:000000000000001028、已知某機器的指令集合及指令格式如下表示意。

已經(jīng)編制好并存儲在存儲器中的一段程序如下表示意，請閱讀這段程序，并回答問題。

若要使該程序完成任意方程式，則需修正存儲的數(shù)據(jù)，正確的修正是_____。答案:8號存儲單元存放數(shù)x的二進制數(shù)，9號存儲單元存放數(shù)a的二進制數(shù)，10號存儲單元存放數(shù)b的二進制數(shù)，11號存儲單元存放數(shù)c的二進制數(shù)29、下圖是一個存儲器的簡單模型-與或陣列圖。

圍繞該存儲器模型，請寫出由、產(chǎn)生、、、的邏輯表達式，書寫正確的是_____。答案:30、下圖為用狀態(tài)轉(zhuǎn)換圖示意的一個圖靈機，其字母集合為{V，C，+，=，“空格”，；}；狀態(tài)集合{S1，S2，S3，S4，S5，S6，S7}，其中S1為起始狀態(tài)，S7為終止狀態(tài)；箭頭表示狀態(tài)轉(zhuǎn)換，其上標注的如<in,out,direction>表示輸入是in時，輸出out，向direction方向移動一格，同時將狀態(tài)按箭頭方向?qū)崿F(xiàn)轉(zhuǎn)換，其中in,out均是字母集中的符號，null表示什么也不寫，direction可以為R(向右移動)、L(向左移動)、N(停留在原處)。

該圖靈機的功能是_____。答案:其它三個選項全部能夠識別31、下圖為用狀態(tài)轉(zhuǎn)換圖示意的一個圖靈機，其字母集合為{V，C，+，=，“空格”，；}；狀態(tài)集合{S1，S2，S3，S4，S5，S6，S7}，其中S1為起始狀態(tài)，S7為終止狀態(tài)；箭頭表示狀態(tài)轉(zhuǎn)換，其上標注的如<in,out,direction>表示輸入是in時，輸出out，向direction方向移動一格，同時將狀態(tài)按箭頭方向?qū)崿F(xiàn)轉(zhuǎn)換，其中in,out均是字母集中的符號，null表示什么也不寫，direction可以為R(向右移動)、L(向左移動)、N(停留在原處)。

關(guān)于該圖靈機的功能，說法不正確的是_____。答案:其它三個選項有該圖靈機不能識別的符號串形式第5講現(xiàn)代計算機—復雜環(huán)境下程序執(zhí)行第5講測驗1、關(guān)于現(xiàn)代計算機系統(tǒng)，下列說法正確的是_____。答案:人們認為，計算機不僅僅包括硬件和軟件，還包括網(wǎng)絡(luò)和數(shù)據(jù)，很多的軟件都可通過網(wǎng)絡(luò)來使用，人們的注意力已經(jīng)從關(guān)注軟硬件轉(zhuǎn)移為關(guān)注各種各樣的數(shù)據(jù)2、關(guān)于“計算機軟件”，下列說法正確的是_____。答案:計算機軟件包括操作系統(tǒng)、計算機語言處理系統(tǒng)、輔助性工具軟件以及各種應用軟件3、關(guān)于“存儲體系”，下列說法正確并完整的是_____。答案:其它三個選項的說法全都正確4、關(guān)于“磁盤”，下列說法不正確的是_____。答案:CPU可以一個存儲字一個存儲字地讀寫磁盤5、關(guān)于“內(nèi)存”，下列說法不正確的是_____。答案:當機器斷電時，內(nèi)存信息會短暫保留6、關(guān)于“操作系統(tǒng)”，下列說法不正確的是_____。答案:操作系統(tǒng)僅僅是管理CPU執(zhí)行任何應用程序的一組程序7、關(guān)于操作系統(tǒng)體現(xiàn)了“分工-合作-協(xié)同”的基本思想，下面說法不正確的是_____。答案:其它三個選項的說法有不正確的8、磁盤上有一些重要的區(qū)域，那里存放著操作系統(tǒng)管理磁盤所要使用的重要信息。這些區(qū)域是_____。答案:其它三個選項全部包括9、操作系統(tǒng)管理信息的基本單位是_____。答案:文件10、文件分配表中記錄的是文件在磁盤上存儲的簇塊鏈—一個簇塊可以是一個扇區(qū)或是若干連續(xù)的扇區(qū)，如果文件分配表被破壞了會帶來什么影響？答案:其它三個選項全部正確11、下圖給出了操作系統(tǒng)管理磁盤與文件的基本思路圖，關(guān)于“文件1”的下列說法不正確的是_？

答案:該文件的第3個簇塊是第24號簇塊—此信息存放在FAT表的第32號表項中12、操作系統(tǒng)管理內(nèi)存的基本思路可以用學校教務處管理教學樓和教室來類比，通過類比回答，下列哪些問題不是內(nèi)存管理的基本問題？答案:內(nèi)存與外存的信息交換問題–讀寫磁盤，即將外存中的信息讀出到內(nèi)存中，或者將內(nèi)存中的信息更改返存到磁盤中13、下圖為復雜環(huán)境中，在操作系統(tǒng)管理下進行程序執(zhí)行的基本思想示意圖。請關(guān)注圖中第?④號線。箭頭線?④的含義指將應用程序由外存中裝載到內(nèi)存中，這項工作被稱為“程序裝載作業(yè)”；關(guān)于“程序裝載作業(yè)”，下列說法正確的是_。

答案:程序裝載作業(yè)是由“作業(yè)和進程管理程序”，調(diào)用“磁盤管理程序暨<程序裝載>程序”完成的14、下圖為復雜環(huán)境中，在操作系統(tǒng)管理下進行程序執(zhí)行的基本思想示意圖。請關(guān)注圖中的“合作：操作系統(tǒng)對任務、作業(yè)和進程的管理與控制”部分，執(zhí)行該“合作”工作的也是一個進程，關(guān)于該進程，下列說法不正確的是_。

答案:執(zhí)行“合作”工作的進程，是應用程序進程的一個重要組成部分15、下圖為復雜環(huán)境中，在操作系統(tǒng)管理下進行程序執(zhí)行的基本思想示意圖。圖中示意的是一個CPU面對多個進程的情況，關(guān)于這個問題，下列說法不正確的是_。

答案:一個CPU只能執(zhí)行一個進程。執(zhí)行另一個進程時需將前一個進程從內(nèi)存中清除以騰出空間給后一個進程使用16、下圖為復雜環(huán)境中，在操作系統(tǒng)管理下進行程序執(zhí)行的基本思想示意圖。圖中示意的是一個CPU面對多個進程的情況。現(xiàn)在很多的微處理器都可能是多核微處理器，即有多個CPU。關(guān)于多CPU問題，下列說法正確的是_。

答案:多個CPU可以執(zhí)行多個進程，多個進程可以被分配到不同的CPU上同時執(zhí)行17、操作系統(tǒng)有啟動階段、工作階段和關(guān)閉階段。問下列工作，哪些不是啟動階段的工作？答案:將內(nèi)存內(nèi)容寫回外存中18、操作系統(tǒng)有啟動階段、工作階段和關(guān)閉階段。問下列工作，哪些不是關(guān)閉階段的工作？答案:加載服務程序19、關(guān)于計算機系統(tǒng)的工作過程，下列說法不正確的是_。答案:計算機接通電源后執(zhí)行的第一個程序就是內(nèi)存中的操作系統(tǒng)程序20、關(guān)于裝載進內(nèi)存的程序，下列說法正確的是_。答案:正確的裝載次序：ROM-BIOS

→

操作系統(tǒng)

→

應用程序21、你理解什么是云嗎?下列說法不正確的是_。答案:雖然軟件商通過“云”可以收集客戶相關(guān)的信息，但這些信息是沒有什么價值的22、你理解什么是云嗎?下列說法不正確的是_。答案:普通人將自己的數(shù)據(jù)放在“云”中，更多的是他們相信云是安全的、可靠的，而云也確實是安全的、可靠的23、下圖給出了操作系統(tǒng)管理磁盤與文件的基本思路圖。文件分配表與所能夠管理的磁盤空間大小是有關(guān)系的。例如磁盤的一簇被定義為4KB(8個扇區(qū))，則文件分配表的大小，即表項的多少，為所能管理的簇的數(shù)目的多少。如果一個文件分配表的表項數(shù)為，問其能管理的磁盤空間為_？

答案:KB24、下圖為復雜環(huán)境中，在操作系統(tǒng)管理下進行程序執(zhí)行的基本思想示意圖。關(guān)于“操作系統(tǒng)”和“應用程序”，下列說法不正確的是_。

答案:操作系統(tǒng)自身的進程，不由操作系統(tǒng)調(diào)度和執(zhí)行；操作系統(tǒng)僅管理各個應用程序的進程25、下圖為復雜環(huán)境中，在操作系統(tǒng)管理下進行程序執(zhí)行的基本思想示意圖。請關(guān)注圖中第⑥⑦⑧???號線。箭頭線⑥?的含義指為管理CPU的使用，需要對每個進程的基本信息進行管理；箭頭線?⑦的含義指若要使CPU從一個進程的執(zhí)行切換到另一個進程的執(zhí)行，需要保留當前正在執(zhí)行的進程的相關(guān)狀態(tài)信息，并將下一個要執(zhí)行進程的指令代碼的存儲單元地址送給CPU的程序計數(shù)器PC；箭頭線?⑧的含義指“進程”被CPU執(zhí)行。下列說法不正確的是_。

答案:其它選項的說法有不正確的26、下圖給出了操作系統(tǒng)管理磁盤與文件的基本思路圖，觀察“文件2”在磁盤上的存儲，圖中的FAT表還沒有給出其簇塊鏈的信息。填寫FAT表關(guān)于文件2的信息，下列說法不正確的是_？

答案:FAT表的第51號表項應該填寫49，第49號表項應該填寫End27、下圖為復雜環(huán)境中，在操作系統(tǒng)管理下進行程序執(zhí)行的基本思想示意圖。這里的“復雜環(huán)境”是相對于“內(nèi)存中單一程序由CPU執(zhí)行的簡單環(huán)境”。那么關(guān)于環(huán)境“復雜性的體現(xiàn)”，下列說法正確的是_。

答案:其它選項都是復雜性的體現(xiàn)，然而復雜性不限于這些28、下圖為復雜環(huán)境中，在操作系統(tǒng)管理下進行程序執(zhí)行的基本思想示意圖。關(guān)于“程序”與“進程”，下列說法不正確的是_。

答案:其它選項的說法有不正確的29、現(xiàn)代計算環(huán)境是多樣化的。關(guān)于現(xiàn)代計算環(huán)境，下列說法不正確的是_。答案:其它選項的說法有不正確的30、在使用計算機時，若直接通過斷電的方式來關(guān)閉機器，會存在什么問題，下列說法不正確的是_。答案:因瞬時電路沖擊，將造成計算機硬件，如主板等的損壞31、下圖為復雜環(huán)境中，在操作系統(tǒng)管理下進行程序執(zhí)行的基本思想示意圖。關(guān)于“任務”、“作業(yè)”與“進程”，下列說法不正確的是_。

答案:其它選項的說法有不正確的32、你理解什么是云嗎?下列說法不正確的是_。答案:云雖可定制任意數(shù)目CPU、任意容量內(nèi)存和外存構(gòu)成的計算機，但這樣的計算機也是沒有什么實用價值的33、關(guān)于磁盤與文件管理，下列說法不正確的是_____。答案:其它選項的說法有不正確的34、下圖給出了操作系統(tǒng)管理磁盤與文件的基本思路圖，觀察“文件3”在磁盤上的存儲，圖中的FAT表沒有給出其全部的簇塊鏈的信息。填寫FAT表關(guān)于文件3的信息，下列說法正確的是_？

答案:FAT表的第27號表項應該填寫2835、下圖給出了操作系統(tǒng)管理磁盤與文件的基本思路圖。文件分配表與所能夠管理的磁盤空間大小是有關(guān)系的。如果磁盤的一簇被定義為1KB(2個扇區(qū))，文件分配表的表項數(shù)為，則其能管理的磁盤空間大小為KB?，F(xiàn)在磁盤空間已經(jīng)為KB，問該如何進行管理呢_？

答案:將原來一簇為1KB，重新定義為一簇為16KB36、下圖為復雜環(huán)境中，在操作系統(tǒng)管理下進行程序執(zhí)行的基本思想示意圖。復雜環(huán)境中程序的執(zhí)行，需要解決_。

答案:其它選項的所有問題，并且注意其使用的次序37、關(guān)于普通計算機的主機箱中有什么，下列說法正確的是_____。答案:主機箱中有電源，主板。主板上有微處理器和內(nèi)存(條)；還有各種磁盤驅(qū)動器被連接到主板上進而接受CPU的控制；主板上還有若干個插槽，這些插槽可用于各種外部設(shè)備的接口電路板與主板的連接；主板上也有若干已做好的接口，直接用于連接各種外部設(shè)備第6講由機器語言到高級語言—程序編寫編譯第6講測驗1、關(guān)于表達式，下列說法不正確的是_____。答案:比較表達式中不能含有算術(shù)表達式，邏輯表達式中可以含算術(shù)表達式2、已知A=40；B=30；C=100；D=50，計算表達式(A+(C–B)*3)/D的值，結(jié)果為_____。答案:53、已知A=40；B=30；C=100；D=50，計算表達式(A*A–B*B)+D的值，結(jié)果為_____。答案:7504、已知A=40；B=30；C=100；D=50，邏輯“與”運算符為and，“或”運算符為or，“非”運算符為not。計算表達式(A>B)

and(B<C)的值，結(jié)果為_____。答案:真5、已知A=40；B=30；C=100；D=50，邏輯“與”運算符為and，“或”運算符為or，“非”運算符為not。計算表達式C>A+B+D的值，結(jié)果為_____。答案:假6、已知程序如下，若X=10,Y=50,Z=30該程序執(zhí)行完成后，X的值為_____。X

=

Z

+

Y；

If

Y

<

Z

{

X

=

X

–

Y；

}

Else{

X=

X

–

Z；

}

X

=

X

–

Y；

If

X

<

Z

{

X

=

Y

+20；

}

X

=

X

–

Z；

If

X

>

Y

{

X

=

X

–

Y；

}答案:407、讀程序，并回答問題：程序行(60)執(zhí)行了多少次？次數(shù)為_____。

(10)

N

=

6；

(20)X

=

0；

(30)Y

=

1；

(40)For

I

=

1

To

N-1

Step

1

(50)Z

=

X

+

Y；

(60)

X

=

Y；

(70)

Y

=

Z；

(80)Next

I；答案:58、關(guān)于計算機語言的編譯，下列說法不正確的是_____。答案:其它三個選項有不正確的9、已知如下多元素變量，已知I=2；J=4；則M[I][J]的值為_____。

答案:4410、已知如下多元素變量，已知I=2；J=2；則M[I+1][J+1]的值為_____。

答案:011、已知A=40；B=30；C=100；D=50，邏輯“與”運算符為and，“或”運算符為or，“非”運算符為not。計算表達式(A>B+20)or(B+60<C)的值，結(jié)果為_____。答案:真12、已知如下多元素變量，已知I=1；J=1；則M[I+1][J]+2的值為_____。

答案:4713、已知A=40；B=30；C=100；D=50，邏輯“與”運算符為and，“或”運算符為or，“非”運算符為not。計算表達式A+A*5的值，結(jié)果為_____。答案:24014、已知如下多元素變量。

執(zhí)行下列程序，執(zhí)行完成后，Sum1和Sum2的值分別為_____。(10)

int

J；

(20)

int

Sum1=0，Sum2=0；

(30)

For

J=1

to

4

Step

1

(40)

{

Sum1

=

Sum1

+

M[J][J]；

(50)

Sum2

=

Sum2

+

M[5-J][5-J]；

}答案:66,6615、已知函數(shù)Fact的程序如下，在執(zhí)行Fact(4)的過程中，F(xiàn)act函數(shù)被調(diào)用的次數(shù)為_____。Long

Int

Fact(int

n)

{Long

Int

x;

If

(n

>

1)

{

x

=

Fact(n-1);

return

(n+x)*2;

}

else

return

1;

}答案:416、已知程序如下，該程序?qū)崿F(xiàn)的功能為_____。main()

{

int

i,n;

long

sum

=

0,

p

=

1;

…//輸入n值的語句，略

for(i

=

1;

i

<=

n;

i++)

{

p

=

p

i;

sum

=

sum

+

p;

}

…//輸出sum值的語句，略

}答案:sum=1!+2!+…+n!17、已知X=21，

Y=15，

Z=22，計算表達式

((X>Y)or(Y>Z))and((X<Y)or(Y<Z))的值，結(jié)果為_____。答案:真18、已知X=21，

Y=15，

Z=22，計算表達式

((X>Y)AND(Y>Z))OR((X<Y)AND(Y<Z))的值，結(jié)果為_____。答案:假19、已知程序如下，若X=30,Y=30,Z=30該程序執(zhí)行完成后，X的值為_____。X

=

Z

+

Y；

If

Y

<

Z

{

X

=

X

–

Y；

}

Else{

X=

X

–

Z；

}

X

=

X

–

Y；

If

X

<

Z

{

X

=

Y

+20；

}

X

=

X

–

Z；

If

X

>

Y

{

X

=

X

–

Y；

}答案:2020、讀程序，并回答問題：該程序執(zhí)行完成后，X的值為_____。

X=1；

Y=2；

Sum=0；

Do

{Sum

=

X+Y；

X=X+1；

Y=Y+1；

}

While

(Sum<=20)；答案:1121、讀程序，并回答問題：該程序執(zhí)行完成后，Z的值為_____。

(10)

N

=

6；

(20)X

=

0；

(30)Y

=

1；

(40)For

I

=

1

To

N-1

Step

1

(50)Z

=

X

+

Y；

(60)

X

=

Y；

(70)

Y

=

Z；

(80)Next

I；答案:822、已知函數(shù)Fact的程序如下，在執(zhí)行Fact(5)的過程中，F(xiàn)act函數(shù)被調(diào)用的次數(shù)為_____。Long

Int

Fact(int

n)

{Long

Int

x;

If

(n

>

1)

{

x

=

Fact(n-1);

return

n*x;

}

else

return

1;

}答案:523、關(guān)于不同抽象層面的計算機，下列說法不正確的是_____。答案:不同抽象層次的計算機指的是各種抽象層次的硬件系統(tǒng)，只有硬件計算機才能被稱為計算機24、已知函數(shù)Fact的程序如下，F(xiàn)act(4)的值為_____。Long

Int

Fact(int

n)

{Long

Int

x;

If

(n

>

1)

{

x

=

Fact(n-1);

return

(n+x)*2;

}

else

return

1;

}答案:4425、關(guān)于計算機語言，下列說法不正確的是_____。答案:所有源程序最后都需被轉(zhuǎn)換為匯編語言程序，機器才能夠執(zhí)行26、關(guān)于普通計算機語言(或者說程序)的基本構(gòu)成要素，下列說法最完整的是_____。答案:常量與變量、表達式、語句和函數(shù)27、讀程序，并回答問題：該程序執(zhí)行完成后，N的值為_____。N

=

101;

If

N/2

==

0

Then

N

=

N/2;

Else

N

=

N

*

3

+

1;

End

If答案:30428、關(guān)于計算機語言，下列說法不正確的是_____。答案:其它三個選項有不正確的29、從語言編譯角度看計算機語言，下列說法不正確的是_____。答案:其它三個選項有不正確的30、已知如下多元素變量。

執(zhí)行下列程序，執(zhí)行完成后，Sum1和Sum2的值分別為_____。(10)

int

I

=

3，J；

(20)

int

Sum1=0，Sum2=0；

(30)

For

J=1

to

4

Step

1

(40)

{

Sum1

=

Sum1

+

M[I][J]；

(50)

Sum2

=

Sum2

+

M[J][I]；

}答案:149,10531、已知A=40；B=30；C=100；D=50，邏輯“與”運算符為and，“或”運算符為or，“非”運算符為not。計算表達式A<A*5的值，結(jié)果為_____。答案:真32、已知如下多元素變量。

執(zhí)行下列程序，程序執(zhí)行完成后，Sum1和Sum2的值分別為_____。(10)

int

J；

(20)

int

Sum1=0，Sum2=0；

(30)

For

J=1

to

4

Step

1

(40)

{

Sum1

=

Sum1

+

M[J][J]；

(50)

Sum2

=

Sum2

+

M[5-J][J]；

}答案:66,9533、已知A=40；B=30；C=100；D=50，邏輯“與”運算符為and，“或”運算符為or，“非”運算符為not。計算表達式(A>B)and(A<=B)的值，結(jié)果為_____。答案:假34、讀程序，并回答問題：該程序執(zhí)行完成后，K的值為_____。(10)

K

=

0；

(20)

I

=

2；

(30)

While

(I<=8)

(40)

{

K

=

K

+

I；

(50)

I

=

I

+

2；}答案:2035、已知X=21，

Y=15，

Z=22，計算表達式

((X>Y)AND(Y>Z))OR((X<Z)AND(Y<Z))的值，結(jié)果為_____。答案:真36、讀程序，并回答問題：程序行(40)執(zhí)行了多少次？次數(shù)為_____。(10)

K

=

0；

(20)

I

=

2；

(30)

While

(I<=8)

(40)

{

K

=

K

+

I；

(50)

I

=

I

+

2；}答案:437、已知程序如下，當程序行(60)執(zhí)行了3次以后，Product和Counter的值分別為_____。(10)

main()

(20)

{

int

counter；

(30)

…

//輸入N值的語句，略

(40)

long

product

=

1；

(50)

for

counter

=

1

to

N

step

2

(60)

{

product

=

product

*

counter；

}

(70)

return

product;

(80)

}答案:15，538、已知程序如下，若X=10,Y=20,Z=30，該程序執(zhí)行完成后，X的值為_____。X

=

Z

+

Y；

If

Y

<

Z

{

X

=

X

–

Y；

}

Else{

X=

X

–

Z；

}

X

=

X

–

Y；

If

X

<

Z

{

X

=

Y

+20；

}

X

=

X

–

Z；

If

X

>

Y

{

X

=

X

–

Y；

}答案:1039、讀程序，并回答問題：該程序執(zhí)行完成后，Sum的值為_____。

X=1；

Y=2；

Sum=0；

Do

{Sum

=

X+Y；

X=X+1；

Y=Y+1；

}

While

(Sum<=20)；答案:2140、已知函數(shù)Fact的程序如下，F(xiàn)act(4)的值為_____。Long

Int

Fact(int

n)

{Long

Int

x;

If

(n

>

1)

{

x

=

Fact(n-1);

return

n*x;

}

else

return

1;

}答案:2441、關(guān)于不同抽象層面的計算機，由低層向應用層(高層)的基本層次劃分是_____。答案:微程序機器實際機器操作系統(tǒng)機器匯編語言機器高級語言機器42、已知程序如下，該程序?qū)崿F(xiàn)的功能為_____。(10)

main()

(20)

{

int

counter；

(30)

…

//輸入N值的語句，假設(shè)N為偶數(shù)，略

(40)

long

product

=

1；

(50)

for

counter

=

1

to

N

step

2

(60)

{

product

=

product

counter；

}

(70)

return

product;

(80)

}答案:product=135…*(N-1)第7講算法-程序與計算系統(tǒng)之靈魂第7講測驗1、一般而言，算法設(shè)計完成后，需要進行算法的模擬與分析。通常從哪些方面，進行算法的模擬與分析？答案:其它三個選項全部2、閱讀下面的程序，其時間復雜度為___?int

index

=

5;

int

condition=1;

if

(condition==1)

then

index;

else

index–；

for

i

=

1

to

100

for

j

=

1

to

200

index=index2;答案:O(1)3、一般而言，算法設(shè)計完成后，需要進行算法的模擬與分析。關(guān)于算法的模擬與分析回答問題：算法的時間復雜性T(n)，可以通過評估算法基本語句的執(zhí)行次數(shù)來獲得。分析下列算法的時間復雜性。Start

of

the

algorithm(算法開始)

(1)

輸入結(jié)點的數(shù)目n；

(2)

當前最短路徑Path設(shè)為空，當前最短距離Dtemp設(shè)為最大值；

注：一個路徑是n個結(jié)點的一個組合，任何一個結(jié)點在路經(jīng)中不能重復出現(xiàn)

(3)

組合一條新路徑NewPath并計算該路徑的距離D；

(4)

如果D

(5)

如果所有路徑組合完畢，則結(jié)束；否則轉(zhuǎn)第(3)步繼續(xù)執(zhí)行；

(6)

輸出Path及Dtemp；

End

of

the

algorithm(算法結(jié)束)該算法的時間復雜性表達正確的是___。答案:O(n!)4、一般而言，算法設(shè)計完成后，需要進行算法的模擬與分析。關(guān)于算法的模擬與分析回答問題：分析下列算法的時間復雜性。Start

of

the

Algorithm

(1)

S[1]=1;

Sum=0;

初始化距離數(shù)組D[n][n];

/I層的循環(huán)，即下列步驟為每次找出一個城市，I從2到n，即從找出第2個城市一直到找出第n個城市

(2)

I=2;

/K層的循環(huán)，即下列步驟為從所有未訪問過的城市中查找距離S[I-1]最近的城市j，K依然從2到n尋找

(3)

K=2;

(4)

將Dtemp設(shè)為一個大數(shù)(比所有兩個城市之間的距離都大)

/L層的循環(huán)，即下列步驟為判斷一個城市是否已被訪問過，如果已被訪問，則跳過該城市，尋找新的城市，L從1到I-1，因為已經(jīng)有I-1個城市被訪問過。

(5)

L=1；

(6)

如果S[L]==K，轉(zhuǎn)步驟(10)；

(7)

L=L1；

(8)

如果L<I，轉(zhuǎn)步驟(6)；

/L層的循環(huán)結(jié)束

(9)

如果D[K,S[I-1]]<Dtemp，j=K，Dtemp＝D[K,S[I-1]]；

(10)

K=K1;

(11)

如果K<=N，轉(zhuǎn)步驟(5)。

/K層的循環(huán)結(jié)束

(12)

S[I]=j;

(13)

Sum=SumDtemp;

(14)

I=I1;

(15)

如果I<=N，轉(zhuǎn)步驟(3)，否則，轉(zhuǎn)步驟(16);

/I層的循環(huán)結(jié)束

(16)

Sum=SumD[1,

j]；

(17)

逐個輸出S[N]中的全部元素;

(18)

輸出Sum。

End

of

the

Algorithm該算法的時間復雜性表達正確的是___。答案:5、哥尼斯堡七橋問題，是一個經(jīng)典問題，如下圖(a)所示，描述為“由河流隔開的四塊陸地上建造了七座橋，尋找走遍這七座橋且只許走過每座橋一次最后又回到原出發(fā)點的路徑”。關(guān)于哥尼斯堡七橋問題，著名數(shù)學家歐拉對該問題做了一個抽象：“頂點”為陸地，“邊”為連接兩塊陸地的橋梁。這個抽象被稱為“圖”，并定義了頂點的“度”為連接一個頂點的邊的數(shù)量。關(guān)于此問題回答問題：

參見圖(c)，增加哪些邊，使得能夠找到走遍每一座橋，且每座橋僅走過一次、最后又回到原出發(fā)點的路徑呢？

答案:CG邊6、哥尼斯堡七橋問題，是一個經(jīng)典問題，如下圖(a)所示，描述為“由河流隔開的四塊陸地上建造了七座橋，尋找走遍這七座橋且只許走過每座橋一次最后又回到原出發(fā)點的路徑”。關(guān)于哥尼斯堡七橋問題，著名數(shù)學家歐拉對該問題做了一個抽象：“頂點”為陸地，“邊”為連接兩塊陸地的橋梁。這個抽象被稱為“圖”，并定義了頂點的“度”為連接一個頂點的邊的數(shù)量。關(guān)于此問題回答問題：

下面所示的圖(c)，能否找到走遍每一座橋，且每座橋僅走過一次、最后又回到原出發(fā)點的路徑呢？

答案:一定不能找到7、TSP-旅行商問題，是一個經(jīng)典問題，如下圖所示，描述為“有n個城市，任何兩個城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)必須經(jīng)過每一個城市且只能在每個城市逗留一次，最后回到原出發(fā)城市，問如何事先確定好一條最短的路線使其旅行的費用最少”。圍繞TSP，回答

關(guān)于下列四個數(shù)學抽象，說法正確的是_____。

答案:數(shù)學抽象I、II、III和IV都可以被認為是TSP問題8、數(shù)據(jù)通常要存儲在存儲器中，存儲器是按地址訪問的存儲單元的集合，因此存儲器可被認為是按線性方式組織數(shù)據(jù)。數(shù)組是高級語言中經(jīng)常使用的一種數(shù)據(jù)結(jié)構(gòu)，其按照不同的下標可訪問數(shù)組的不同的元素。如下圖所示：

關(guān)于數(shù)組和存儲器，下列說法不正確的是_____。答案:和存儲器一樣，一維數(shù)組是按線性方式組織數(shù)據(jù)，一個數(shù)據(jù)元素需要一個或多個存儲單元來存儲，一個下標即相當于一個存儲單元的地址9、堆棧(stack)是一種特殊的串行形式的數(shù)據(jù)結(jié)構(gòu)，其特殊支出在于只能允許在鏈結(jié)串行或陣列的一端（稱為堆棧頂端指針，top）進行加入數(shù)據(jù)(push)或輸出數(shù)據(jù)(pop)的運算。其示意圖如下所示。假定當前堆棧頂端指針top=10，欲將棧底的元素取出，其他的元素仍然保持在棧中，則需要進行_次彈出操作，_次推入操作答案:10，910、閱讀下列算法，回答：算法執(zhí)行的結(jié)果為___。Start

of

the

algorithm(算法開始)

(1)

N=10；

(2)

i=2；sum=2；

(3)

如果

i<=N，則執(zhí)行第(4)步，否則轉(zhuǎn)到第(8)步執(zhí)行；

(4)

如果i

%

2

==0

則轉(zhuǎn)到第(6)步執(zhí)行；

(5)

sum

=

sum

i；

(6)

i

=

i1；

(7)

返回到第(3)步繼續(xù)執(zhí)行；

(8)

輸出sum的結(jié)果。

End

of

the

algorithm(算法結(jié)束)答案:2611、算法的時間復雜性，可以表達為關(guān)于問題規(guī)模n的一個函數(shù)T(n)，T(n)可以用大O表示法來處理。問T(n)=O(f(n))是什么意思？正確的是___。答案:T(n)是與f(n)同數(shù)量級的函數(shù)12、算法的時間復雜性T(n)，可以通過計算算法基本語句的執(zhí)行次數(shù)來獲得。分析下列程序的時間復雜性。(10)

K

=

0；

(20)

I

=

2；

(30)

While

(I<=8)

(40)

{

K

=

K

I；

(50)

I

=

I

2；}該程序時間復雜性表達正確的是___。答案:O(1)13、對于算法類問題求解，下列說法正確的是___。答案:一般而言，算法類問題求解包括數(shù)學建模、算法策略設(shè)計、算法的數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)設(shè)計、算法的程序?qū)崿F(xiàn)、算法的正確性與復雜性分析五個基本步驟14、哥尼斯堡七橋問題，是一個經(jīng)典問題，如下圖(a)所示，描述為“由河流隔開的四塊陸地上建造了七座橋，尋找走遍這七座橋且只許走過每座橋一次最后又回到原出發(fā)點的路徑”。關(guān)于哥尼斯堡七橋問題，著名數(shù)學家歐拉對該問題做了一個抽象：“頂點”為陸地，“邊”為連接兩塊陸地的橋梁。這個抽象被稱為“圖”，并定義了頂點的“度”為連接一個頂點的邊的數(shù)量。關(guān)于此問題回答問題：

下面所示的圖(d)和圖(e)，問能否找到走遍每一座橋，且每座橋僅走過一次的路徑呢？

答案:圖(d)一定不能找到；圖(e)一定能夠找到15、TSP-旅行商問題，是一個經(jīng)典問題，如下圖所示，描述為“有n個城市，任何兩個城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)必須經(jīng)過每一個城市且只能在每個城市逗留一次，最后回到原出發(fā)城市，問如何事先確定好一條最短的路線使其旅行的費用最少”。圍繞TSP，回答關(guān)于TSP問題的遍歷算法和貪心算法，下列說法正確的是_____。

答案:對TSP問題而言，遍歷算法和貪心算法求得的解是不一樣的，貪心算法是求近似解，執(zhí)行更快一些，而遍歷算法是求精確解，執(zhí)行更慢一些16、算法是計算系統(tǒng)的靈魂，為什么？不正確的是_____。答案:問題求解都可以歸結(jié)到算法的構(gòu)造與設(shè)計，系統(tǒng)和算法的關(guān)系是：算法是龍，而系統(tǒng)是睛，畫龍要點睛17、哥尼斯堡七橋問題，是一個經(jīng)典問題，如下圖(a)所示，描述為“由河流隔開的四塊陸地上建造了七座橋，尋找走遍這七座橋且只許走過每座橋一次最后又回到原出發(fā)點的路徑”。關(guān)于哥尼斯堡七橋問題，著名數(shù)學家歐拉對該問題做了一個抽象：“頂點”為陸地，“邊”為連接兩塊陸地的橋梁。這個抽象被稱為“圖”，并定義了頂點的“度”為連接一個頂點的邊的數(shù)量。關(guān)于此問題回答問題：對河流隔開的m塊陸地上建造的n座橋梁，能否找到走遍這n座橋且只許走過每座橋一次最后又回到原出發(fā)點的路徑呢？

答案:不確定能不能找到18、背包問題的定義是：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。背包問題的一個例子：應該選擇哪些盒子，才能使價格盡可能地大，而保持重量小于或等于15kg？其示意圖如下：

假定求解該問題的一種貪心策略是：優(yōu)先選擇能裝下盒子中價格最高的，依據(jù)該算法策略所得到的解的總價值是_____。答案:1519、背包問題的定義是：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。背包問題的一個例子：應該選擇哪些盒子，才能使價格盡可能地大，而保持重量小于或等于15kg？其示意圖如下：

假定求解該問題的一種貪心策略是：最大程度地利用背包的容量（15kg），依據(jù)該算法策略所得到的解的總價值是_____。答案:820、關(guān)于數(shù)據(jù)結(jié)構(gòu)，下列說法不正確的是_？答案:在樹結(jié)構(gòu)中，指針用于表達元素之間的邏輯關(guān)系——父子關(guān)系，每個元素的指針指向其父節(jié)點，因此一個元素可以有一個或多個指針21、關(guān)于算法的特性，下列說法不正確的是_____。答案:算法可以有零個或多個輸入，也可以有零個或多個輸出，此即算法的輸入輸出性22、關(guān)于算法的命題，下列說法不正確的是_____。答案:算法所規(guī)定的計算/處理步驟是有限的，但算法實際執(zhí)行的計算/處理步驟可以是無限的23、關(guān)于算法與程序、計算機語言之間的關(guān)系，下列說法不正確的是_____。答案:算法只能由高級（計算機）語言實現(xiàn)，不能通過機器語言實現(xiàn)2