1、山東工商學(xué)院試卷20032004 學(xué)年 第 一 學(xué)期課程名稱 計(jì)算機(jī)學(xué)科方法導(dǎo)論（ B卷；開卷 ） 適用班級(jí) 考試時(shí)間 120 分鐘 班級(jí) 學(xué)號(hào) 姓名 題號(hào) 一 二 三 四 五 六 七 八 九 成績(jī) 滿分 20 15 24 6 20 15 100 得分 評(píng)卷人一、填空題（每小題2分，共20分）1、計(jì)算作為一門學(xué)科報(bào)告的存在的局限性是 。2、在統(tǒng)一對(duì)學(xué)科的認(rèn)識(shí)之后，ACM和IEEE/CS聯(lián)合小組將計(jì)算機(jī)科學(xué)、計(jì)算機(jī)工程、計(jì)算機(jī)科學(xué)和工程、計(jì)算機(jī)信息學(xué)以及其它類似名稱的專業(yè)及其研究范疇統(tǒng)稱為 。3、進(jìn)程同步中有代表性的典型問題有 和 。4、除了思維、認(rèn)知可以看作是一種計(jì)算外，有關(guān)視覺認(rèn)知理論的學(xué)者

2、也把視覺看作是一種計(jì)算。其中，以 的計(jì)算視覺理論最為著名。計(jì)算視覺理論目前已得到廣泛地應(yīng)用。5、CC1991的含義是 。6、虛擬機(jī)（virtual machine，也被譯為如真機(jī)）是一個(gè)抽象的計(jì)算機(jī)，它由軟件實(shí)現(xiàn)，并與實(shí)際機(jī)器一樣，都具有一個(gè) 并可以使用不同的存儲(chǔ)區(qū)域。7、數(shù)據(jù)結(jié)構(gòu)由三部分組成，它們是 。8、高級(jí)語言中理論形態(tài)的主要內(nèi)容有 。9、喬姆斯基把人所具有的創(chuàng)造和理解正確句子的能力稱為語言的“創(chuàng)造性”（Creativity）。而語言“創(chuàng)造性”過程的本質(zhì)，其實(shí)就是 ，進(jìn)一步而言，其實(shí)質(zhì)也就是一個(gè)字符串到 的變換過程。10、一個(gè)算法是對(duì)于所有的輸入元素x，都在有窮步驟內(nèi)終止的一個(gè)計(jì)算x0=

3、x，xk+1=F(xk)，(k0)，該性質(zhì)表示 對(duì)任何輸入元素x，該序列表示算法 結(jié)束。二、判斷正誤，正確的寫“T”，錯(cuò)誤的寫“F”（每小題1.5分，共15分）1、現(xiàn)在，人們對(duì)計(jì)算學(xué)科的認(rèn)知已相當(dāng)成熟，從而使我們能夠以一般科學(xué)技術(shù)方法論為指導(dǎo)，科學(xué)地建立起計(jì)算學(xué)科自己的方法論計(jì)算機(jī)科學(xué)與技術(shù)方法論。本書作者認(rèn)為本課程要求本科一年級(jí)學(xué)生對(duì)本書的內(nèi)容完全掌握。（ ） 2、語言W定義為：初始符號(hào)集：a，b，c，d，e。形成規(guī)則：上述符號(hào)組成的有限符號(hào)串中，能組成一英語單詞的為一公式；否則不是。語言W為一形式語言。 （ ）3、計(jì)算機(jī)科學(xué)與技術(shù)方法論在“Computing as a discipline

4、”報(bào)告的基礎(chǔ)上，從一般科學(xué)技術(shù)方法論的角度闡述了計(jì)算學(xué)科的主要內(nèi)容，為嚴(yán)格而富有挑戰(zhàn)性的綜述性課程（導(dǎo)論）的教學(xué)提供了一個(gè)新的思路。 （ ）4、馮.諾依曼型計(jì)算機(jī)等實(shí)現(xiàn)技術(shù)屬于學(xué)科中設(shè)計(jì)形態(tài)的內(nèi)容。（ ） 5、西爾勒的“中文屋子”從功能的角度來判定機(jī)器能否思維，標(biāo)志著現(xiàn)代機(jī)器思維問題討論的開始。 （ ）6、算法的時(shí)間復(fù)雜度和算法的空間復(fù)雜度屬于算法分析中的研究?jī)?nèi)容。（ ） 7、.精簡(jiǎn)指令系統(tǒng)計(jì)算機(jī)（）主要是指一種計(jì)算機(jī)產(chǎn)品, 而不只是一種體系結(jié) 構(gòu)的思想。 （ ）8、在計(jì)算領(lǐng)域中認(rèn)識(shí)指的是抽象過程（感性認(rèn)識(shí)）和理論過程（理性認(rèn)識(shí)），實(shí)踐指的是學(xué)科中的設(shè)計(jì)過程。（ ）9. 根據(jù)圖靈的觀點(diǎn)可以得到

5、這樣的結(jié)論：凡是能用算法方法解決的問題，也一定能用圖靈機(jī)所解決；反之則不一定，即圖靈機(jī)解決不了的問題，而算法卻有可能解決。（ ）10. 由阿達(dá)爾定律的定量形式可知，如果某一計(jì)算中所含的必須串行執(zhí)行的操作占10%，那么，不管一臺(tái)并行計(jì)算機(jī)系統(tǒng)中有多少個(gè)處理器，其最大可能的加速只能是10 。（ ）三、問答題（24分，每小題4分）1、什么是算法？在算法的分析中應(yīng)考慮哪些問題？2、簡(jiǎn)述“歐拉回路”與“哈密爾頓回路”的區(qū)別。3、為什么說自然語言的“創(chuàng)造性”過程的本質(zhì)與計(jì)算過程的本質(zhì)是一致的？4、計(jì)算領(lǐng)域工作者應(yīng)具備什么能力？6、畫出計(jì)算學(xué)科二維定義距陣。四、請(qǐng)用自然語言給出求解斐波那契數(shù)的遞歸算法。（6

6、分）五、計(jì)算題（15分）1、假設(shè)一對(duì)剛出生的兔子一個(gè)月后就能長(zhǎng)大，再過一個(gè)月就能生下一對(duì)兔子，并且此后每個(gè)月都能生一對(duì)兔子，且新生的兔子在第二個(gè)月后也是每個(gè)月生一對(duì)兔子。問：一對(duì)兔子11個(gè)月內(nèi)可繁殖成多少對(duì)兔子？（5分） 2、判定方程200 x+80y=24是否有整數(shù)解。（寫出歐幾里德算法步驟）（5分）3、求下列阿克曼函數(shù)值：（5分）（1）A(1,1) （2）A(2,1) 六、通過計(jì)算機(jī)學(xué)科方法導(dǎo)論的學(xué)習(xí)，談一談在四年學(xué)習(xí)中，如何學(xué)好計(jì)算機(jī)科學(xué)與技術(shù)這個(gè)專業(yè)（20分 要求用Word排版，字?jǐn)?shù)不少于3500字，打印好寒假前交）計(jì)算機(jī)科學(xué)與技術(shù)方法論試卷B答案填空題（每小題2分，共20分）對(duì)計(jì)算學(xué)

7、科二維定義矩陣“橫向”關(guān)系的內(nèi)容，即對(duì)抽象、理論和設(shè)計(jì)3個(gè)過程的內(nèi)在聯(lián)系與發(fā)展規(guī)律的認(rèn)識(shí)不清楚，未能科學(xué)地、完整地建立起計(jì)算學(xué)科的方法論。計(jì)算學(xué)科 生產(chǎn)者消費(fèi)者問題、哲學(xué)家共餐問題。 D.Marr 1990年，ACM和IEEE-CS聯(lián)合攻關(guān)組在計(jì)算作為一門學(xué)科報(bào)告的基礎(chǔ)上提交了關(guān)于計(jì)算學(xué)科教學(xué)計(jì)劃的Computing Curricula 1991（簡(jiǎn)稱CC1991）報(bào)告 。 指令集 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（或稱物理結(jié)構(gòu)）及其運(yùn)算 形式語言和自動(dòng)機(jī)理論；形式語義學(xué)：操作、指稱、公理、代數(shù)、并發(fā)和分布式程序的形式語義 由有限數(shù)量的詞根據(jù)一定的規(guī)則產(chǎn)生正確句子的過程，到另一個(gè)字符串 任何一個(gè)

8、輸入元素x均為一個(gè)計(jì)算序列，即x0，x1，x2，xk。，在第k步 判斷正誤，判斷正誤，正確的寫“T”，錯(cuò)誤的寫“F”（每小題1分，共1分）1、F 2、F 3、F 4、T 5、F 6、T 7、F 8、T 9、F 10、T問答題（每小題5分，共2分）：什么是算法？在算法的分析中應(yīng)考慮哪些問題？答：一個(gè)算法，就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個(gè)解決某一特定類型問題的運(yùn)算序列。解一個(gè)問題，往往有若干不同的算法，這些算法決定著根據(jù)該算法編寫的程序性能的好壞。那么，在保證算法正確性的前提下，如何確定算法的優(yōu)劣就是一個(gè)值得研究的課題。在算法的分析中，一般應(yīng)考慮以下3個(gè)問題：（1）算法的時(shí)間復(fù)雜度；（

9、2）算法的空間復(fù)雜度；（3）算法是否便于閱讀、修改和測(cè)試。2、簡(jiǎn)述“歐拉回路”與“哈密爾頓回路”的區(qū)別。答：為了解決哥德斯堡七橋問題，歐拉用4個(gè)字母A、B、C、D代表4個(gè)城區(qū)，并用7條線表示7座橋，只有4個(gè)點(diǎn)和7條線，這樣做是基于該問題本質(zhì)考慮的，它抽象出問題最本質(zhì)的東西，忽視問題非本質(zhì)的東西（如橋的長(zhǎng)度等），從而將哥尼斯堡七橋問題抽象為一個(gè)數(shù)學(xué)問題，即經(jīng)過圖中每邊一次且僅一次的回路問題了。歐拉在論文中論證了這樣的回路是不存在的，后來，人們把有這樣的回路稱為“歐拉回路”。 “哈密爾頓回路”3、為什么說自然語言的“創(chuàng)造性”過程的本質(zhì)與計(jì)算過程的本質(zhì)是一致的？答：文字輸入計(jì)算機(jī)后，要使計(jì)算機(jī)對(duì)自然

10、語言進(jìn)行處理, 就必須使其形式化。因此，如何解決自然語言語法和語義的形式化問題，成為計(jì)算機(jī)處理自然語言的關(guān)鍵。喬姆斯基把人所具有的創(chuàng)造和理解正確句子的能力稱為語言的“創(chuàng)造性”（Creativity）。而語言“創(chuàng)造性”過程的本質(zhì)，其實(shí)就是由有限數(shù)量的詞根據(jù)一定的規(guī)則產(chǎn)生正確句子的過程，進(jìn)一步而言，其實(shí)質(zhì)也就是一個(gè)字符串到另一個(gè)字符串的變換過程。顯然，語言“創(chuàng)造性”過程的本質(zhì)與計(jì)算過程的本質(zhì)是一致的，因此，可以將自然語言也看作是一種計(jì)算，從而自然語言能否實(shí)現(xiàn)形式化的爭(zhēng)論也就不存在了。4、“圖靈測(cè)試”不要求接受測(cè)試的思維機(jī)器在內(nèi)部構(gòu)造上與人腦一樣，它只是從功能的角度來判定機(jī)器是否能思維，也就是從行為

11、主義這個(gè)角度來對(duì)“機(jī)器思維”進(jìn)行定義。盡管圖靈對(duì)“機(jī)器思維”的定義是不夠嚴(yán)謹(jǐn)?shù)模P(guān)于“機(jī)器思維”定義的開創(chuàng)性工作對(duì)后人的研究具有重要意義，因此，一些學(xué)者認(rèn)為，圖靈發(fā)表的關(guān)于“圖靈測(cè)試”的論文標(biāo)志著現(xiàn)代機(jī)器思維問題討論的開始。西爾勒借用語言學(xué)的術(shù)語非常形象地揭示了“中文屋子”的深刻寓意：形式化的計(jì)算機(jī)僅有語法，沒有語義。因此，他認(rèn)為，機(jī)器永遠(yuǎn)也不可能代替人腦。作為以研究語言哲學(xué)問題而著稱的分析哲學(xué)家西爾勒來自語言學(xué)的思考，的確給人工智能涉及的哲學(xué)和心理學(xué)問題提供了不少啟發(fā)。5、計(jì)算領(lǐng)域工作者應(yīng)具備什么能力？答：計(jì)算作為一門學(xué)科報(bào)告指出有兩類能力：（1）面向計(jì)算學(xué)科的思維能力：發(fā)現(xiàn)本領(lǐng)域新的特

12、性的能力。這些特性將導(dǎo)致新的活動(dòng)方式和新的工具的產(chǎn)生。面向計(jì)算學(xué)科的思維能力應(yīng)包含兩層意思：其一是面向計(jì)算學(xué)科方法論的思維能力；其二是面向計(jì)算學(xué)科的數(shù)學(xué)思維能力。在面向計(jì)算學(xué)科的思維方式這類問題上，戴克斯特拉教授告誡我們，在計(jì)算機(jī)科學(xué)的教學(xué)過程中不要用擬人化的術(shù)語，而要用數(shù)學(xué)的形式化方法。（2）使用工具的能力：使用本領(lǐng)域的工具有效地進(jìn)行其他領(lǐng)域?qū)嵺`活動(dòng)的能力。報(bào)告建議：把面向計(jì)算學(xué)科的思維能力作為大學(xué)計(jì)算專業(yè)課程設(shè)計(jì)的主要目的。同時(shí)，計(jì)算專業(yè)工作者必須充分熟悉工具，以便與其他學(xué)科的人們有效地合作，進(jìn)行那些學(xué)科的設(shè)計(jì)活動(dòng)。6、畫出計(jì)算學(xué)科二維定義距陣。答：計(jì)算學(xué)科二維定義矩陣如下三個(gè)過程學(xué)科主領(lǐng)

13、域抽象理論設(shè)計(jì)1離散結(jié)構(gòu)（DS）2程序設(shè)計(jì)基礎(chǔ)（PF）3算法與復(fù)雜性（AL）4體系結(jié)構(gòu)（AR）5操作系統(tǒng)（OS）6網(wǎng)絡(luò)計(jì)算（NC）7程序設(shè)計(jì)語言（PL）8人機(jī)交互（HC）9圖形學(xué)和可視化計(jì)算（GV）10智能系統(tǒng)（IS）11信息管理（IM）12軟件工程（SE）13社會(huì)和職業(yè)的問題（SP）14科學(xué)計(jì)算（CN）四、請(qǐng)用自然語言給出求解斐波那契數(shù)的遞歸算法。（6分）解：解：解斐波那契數(shù)F（n）的遞歸算法如下：開始 如果等于0，那么將0賦值給F(n)；如果等于1，那么將1賦值給F(n)；如果大于或等于2，那么將F(n-2)和F(n-1)的和賦值給F(n)；結(jié)束計(jì)算題（15分）1、答：每個(gè)月的兔子數(shù)都是它的前兩個(gè)月的兔子數(shù)之和，用Fn表示第個(gè)月的兔子數(shù)，則每個(gè)月的兔子數(shù)組成的序列可以形式化的定義為： F0=0，F(xiàn)1=1，F(xiàn)n+2=Fn+1+Fn，n0即第0個(gè)月第1個(gè)月第2個(gè)月第3個(gè)月第4個(gè)月第5個(gè)月第6個(gè)月第7個(gè)月第8個(gè)月第9個(gè)月第10個(gè)月第11個(gè)月01123581321345589一對(duì)兔子11個(gè)月內(nèi)可繁殖成89對(duì)兔子。（5分）2、判定方程200 x+80y=24是否有整數(shù)解。歐幾里德算法求出系數(shù)12和18的最大公因子202和89的最大公因子是40，40不能整除24，故該方程無整數(shù)解