中級(jí)軟件設(shè)計(jì)師單項(xiàng)^選擇考試卷模擬考試題_0

1、姓名：_ 班級(jí)：_ 學(xué)號(hào)：_-密-封 -線- 標(biāo)簽:標(biāo)題考試時(shí)間：120分鐘 考試總分：100分題號(hào)一二三四五總分分?jǐn)?shù)遵守考場(chǎng)紀(jì)律，維護(hù)知識(shí)尊嚴(yán)，杜絕違紀(jì)行為，確?？荚嚱Y(jié)果公正。1、活動(dòng)頭磁盤，每個(gè)記錄面只有一個(gè)讀寫磁頭，訪問(wèn)磁盤尋址時(shí)間包括（ ）兩部分時(shí)間。 （ ）a.啟動(dòng)時(shí)間，尋址譯碼時(shí)間b.尋道時(shí)間，等待時(shí)間c.尋道時(shí)間，讀寫時(shí)間d.等待時(shí)間，讀寫時(shí)間2、計(jì)算機(jī)病毒是一種隱藏在計(jì)算機(jī)工作程序中的一種破壞性程序，它可以修改別的程序，使被修改的程序也具有這種特性。具有（ ）a.很強(qiáng)傳染破壞能力b.可預(yù)防的特性c.可以人為控制的特性d.容易發(fā)現(xiàn)，容易控制的性能3、結(jié)構(gòu)化分析方法是一種面向（ ）

2、的需求分析方法。 （ ）a.數(shù)據(jù)b.數(shù)據(jù)流c.控制d.控制流4、數(shù)據(jù)流圖中的頂層圖可以有（ ）個(gè)加工。 （ ）b.1c.不多于9d.任意5、風(fēng)險(xiǎn)分析包括：風(fēng)險(xiǎn)識(shí)別、(16)、風(fēng)險(xiǎn)評(píng)估、(17)。（16）處填（ ）a.風(fēng)險(xiǎn)引導(dǎo)b.風(fēng)險(xiǎn)分散c.風(fēng)險(xiǎn)預(yù)測(cè)d.風(fēng)險(xiǎn)總結(jié)6、風(fēng)險(xiǎn)分析包括：風(fēng)險(xiǎn)識(shí)別、(16)、風(fēng)險(xiǎn)評(píng)估、(17)。（17）處填（ ）a.風(fēng)險(xiǎn)說(shuō)明b.風(fēng)險(xiǎn)回避c.風(fēng)險(xiǎn)比較d.風(fēng)險(xiǎn)控制7、序列圖有兩個(gè)不同于協(xié)作圖的特征，它們是（ ）a.協(xié)作圖有對(duì)象線、協(xié)作圖有控制焦點(diǎn)b.協(xié)作圖有對(duì)象線、序列圖有控制焦點(diǎn)c.序列圖有對(duì)象生命線、序列圖有控制焦點(diǎn)d.序列圖有對(duì)象生命線、協(xié)作圖有控制焦點(diǎn)8、理發(fā)店問(wèn)題。

3、有一個(gè)理發(fā)店，有m個(gè)理發(fā)師，店內(nèi)配置了m個(gè)理發(fā)椅，分別與理發(fā)師一一對(duì)應(yīng)；此外還配置了n個(gè)等待座席，供顧客在店內(nèi)等候理發(fā)。一旦等候的顧客坐滿等候座席，只能在門外排隊(duì)等候進(jìn)入理發(fā)店。試考慮最簡(jiǎn)單的方案，用p、v操作來(lái)實(shí)現(xiàn)能夠保證顧客先來(lái)先進(jìn)入理發(fā)店的秩序，需要（ ）a.1個(gè)信號(hào)量，初值為m+nb.2個(gè)信號(hào)量，初值分別為m，nc.2個(gè)信號(hào)量，初值分別為m+n，0d.3個(gè)信號(hào)量，初值分別為m，n，09、我國(guó)標(biāo)準(zhǔn)分為國(guó)家標(biāo)準(zhǔn)、行業(yè)標(biāo)準(zhǔn)、地方標(biāo)準(zhǔn)和企業(yè)標(biāo)準(zhǔn)4類，（ ）是企業(yè)標(biāo)準(zhǔn)的代號(hào)。 （ ）a.gbb.qjc.qd.db10、一個(gè)批處理系統(tǒng)配置了一臺(tái)打印機(jī)和若干個(gè)作業(yè)管理進(jìn)程，作業(yè)程序在運(yùn)行過(guò)程中的零星

4、輸出被存放在（ ）a.lc.n2-ed.n2-2e13、為適應(yīng)網(wǎng)絡(luò)帶寬和降低存儲(chǔ)器存儲(chǔ)容量的要求，科技工作者開(kāi)發(fā)了許多算法，用于壓縮各種各樣的數(shù)據(jù)，假設(shè)處理系統(tǒng)的計(jì)算精度足夠高，由此造成的數(shù)據(jù)損失可忽略。其中，逆向離散小波變換（idwt）（ ）a.對(duì)重構(gòu)圖像的質(zhì)量有損失b.對(duì)重構(gòu)圖像的質(zhì)量沒(méi)有損失c.變換前后數(shù)據(jù)項(xiàng)的數(shù)目不相等d.變換前后的系數(shù)具有相同含義14、下列實(shí)數(shù)是聲音信號(hào)的采樣值： 使用 （ ）a.ab.bc.cd.d15、彩色圖像的每個(gè)像素用位數(shù)表示。例如，每個(gè)像素用4位表示時(shí)，最大顏色數(shù)為24=16種：每個(gè)像素用16位表示時(shí)，最大顏色數(shù)為216=65536種；每個(gè)像素用24位表示時(shí)

5、，最大顏色數(shù)為224=16777216種；如果每個(gè)像素用32位表示，其中8位為(alpha)通道，最大顏色數(shù)為（ ）種。 （ ）a.216=65536b.224=16777216c.232=4294967296d.28=25616、在關(guān)系數(shù)據(jù)庫(kù)中，對(duì)于一個(gè)模式的分解是多種多樣的，但是分解后產(chǎn)生的模式應(yīng)與原模式等價(jià)，這種等價(jià)可定義為（ ）a.保持函數(shù)依賴、無(wú)損連接性b.非函數(shù)依賴、無(wú)損連接性c.非函數(shù)依賴、雙向連接d.保持函數(shù)依賴、滿足最高范式17、關(guān)系數(shù)據(jù)庫(kù)規(guī)范化理論不包括（ ）a.數(shù)據(jù)依賴b.范式c.模式設(shè)計(jì)方法d.結(jié)構(gòu)化18、對(duì)象是由對(duì)象名、(45)、(46)組成的。（45）處填（ ）a.

6、關(guān)系b.屬性c.引用d.類19、對(duì)象是由對(duì)象名、(45)、(46)組成的。（46）處填（ ）a.實(shí)例b.算法c.指針d.方法20、下述（ ）都是面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言。 （ ）a.smalltalk、c+、javab.basic、c+、javac.asp、java、cd.fortran、c+、c21、（ ）主要是在分布式異構(gòu)環(huán)境下建立應(yīng)用系統(tǒng)框架和對(duì)象構(gòu)件，在應(yīng)用系統(tǒng)框架的支撐下，開(kāi)發(fā)者可以將軟件功能包裝為更易管理和使用的對(duì)象，這些對(duì)象可以跨越不同的軟硬件平臺(tái)進(jìn)行互操作。 （ ）a.分布式異構(gòu)系統(tǒng)b.遠(yuǎn)程調(diào)用技術(shù)c.對(duì)象工廠d.分布式對(duì)象技術(shù)22、設(shè)結(jié)點(diǎn)x和y是二叉樹(shù)中任意的兩個(gè)結(jié)點(diǎn)，在該二叉

7、樹(shù)的先根遍歷序列中x在y之前，而在其后根遍歷序列中x在y之后，則x和y的關(guān)系是（ ）a.x是y的左兄弟b.x是y的右兄弟c.x是y的祖先d.x是y的后裔23、設(shè)f表示某個(gè)二元邏輯運(yùn)算符，pfq的真值表如下所示，則pfq等價(jià)于（ ）。 （ ）a.ab.bc.cd.d24、設(shè)集合z26=0，1，25)，乘法密碼的加密函數(shù)為ek:z26z26，ek(i)=(ki) mod 26，密鑰kz26-0，則加密函數(shù)e7(i)=(7i)mod 26是一個(gè)（ ）函數(shù)。 （ ）a.單射但非滿射b.滿射但非單射c.非單射且非滿射d.雙射25、在osi參考模型中能實(shí)現(xiàn)路由選擇、擁塞控制與互聯(lián)功能的層是（ ）a.傳輸層

8、b.應(yīng)用層c.網(wǎng)絡(luò)層d.物理層26、cmm模型將軟件過(guò)程的成熟度分為5個(gè)等級(jí)。從（ ）級(jí)別開(kāi)始，建立了基本的項(xiàng)目管理過(guò)程來(lái)跟蹤成本、進(jìn)度和機(jī)能，制定了必要的過(guò)程紀(jì)律，并基于以往的項(xiàng)目的經(jīng)驗(yàn)來(lái)計(jì)劃與管理新的項(xiàng)目。 （ ）a.優(yōu)化級(jí)b.管理級(jí)c.定義級(jí)d.可重復(fù)級(jí)27、需求分析的任務(wù)是借助于當(dāng)前系統(tǒng)的物理模型導(dǎo)出目標(biāo)系統(tǒng)的邏輯模型，解決目標(biāo)系統(tǒng)“做什么”的問(wèn)題。（ ）并不是需求分析的實(shí)現(xiàn)步驟之一。 （ ）a.獲得當(dāng)前系統(tǒng)的物理模型b.抽象出當(dāng)前系統(tǒng)的邏輯模型c.建立目標(biāo)系統(tǒng)的邏輯模型d.建立目標(biāo)系統(tǒng)的物理模型28、圖1-5uml類圖所示意的設(shè)計(jì)模式的意圖是（ ）。 （ ）a.使原本由于接口不兼容而

9、不能一起工作的那些類可以一起工作b.使算法可獨(dú)立于使用它的客戶而變化c.定義對(duì)象間的一種一對(duì)多的依賴關(guān)系，當(dāng)一個(gè)對(duì)象的狀態(tài)發(fā)生改變時(shí)，所有依賴于它的對(duì)象都得到通知并被自動(dòng)更新d.將一個(gè)請(qǐng)求封裝為一個(gè)對(duì)象，從而可用不同的請(qǐng)求對(duì)客戶進(jìn)行參數(shù)化，將請(qǐng)求排隊(duì)或記錄請(qǐng)求日志，支持可撤銷的操作29、黑盒測(cè)試注重于測(cè)試軟件的功能性需求，主要用于軟件的后期測(cè)試。（ ）不能用黑盒測(cè)試檢查出來(lái)。 （ ）a.功能不對(duì)或遺漏錯(cuò)誤b.界面錯(cuò)誤c.外部數(shù)據(jù)庫(kù)訪問(wèn)錯(cuò)誤d.程序控制結(jié)構(gòu)錯(cuò)誤30、在用例建模過(guò)程中，若幾個(gè)用例執(zhí)行了同樣的功能步驟，此時(shí)可以把這些公共步驟提取成獨(dú)立的用例。這種用例稱為(41)。在uml用例圖上，將

10、用例之間的這種關(guān)系標(biāo)記為(42)。（41）處填（ ）a.擴(kuò)展用例b.抽象用例c.公共用例d.參與用例31、在用例建模過(guò)程中，若幾個(gè)用例執(zhí)行了同樣的功能步驟，此時(shí)可以把這些公共步驟提取成獨(dú)立的用例。這種用例稱為(41)。在uml用例圖上，將用例之間的這種關(guān)系標(biāo)記為(42)。（42）處填（ ）a.associationb.extendsc.usesd.inheritances32、軟件生存周期包括6個(gè)階段，即制定計(jì)劃、(11)、設(shè)計(jì)、(12)、測(cè)試、(13)。（11）處填（ ）a.系統(tǒng)分析b.需求分析c.模塊分解d.數(shù)據(jù)抽象33、軟件生存周期包括6個(gè)階段，即制定計(jì)劃、(11)、設(shè)計(jì)、(12)、測(cè)試

11、、(13)。（12）處填（ ）a.反向工程b.編碼c.對(duì)象化d.編寫用例34、軟件生存周期包括6個(gè)階段，即制定計(jì)劃、(11)、設(shè)計(jì)、(12)、測(cè)試、(13)。（13）處填（ ）a.升級(jí)b.用戶交付c.運(yùn)行/維護(hù)d.用戶培訓(xùn)35、風(fēng)險(xiǎn)分析包括：風(fēng)險(xiǎn)識(shí)別、(16)、風(fēng)險(xiǎn)評(píng)估、(17)。（16）處填（ ）a.風(fēng)險(xiǎn)引導(dǎo)b.風(fēng)險(xiǎn)分散c.風(fēng)險(xiǎn)預(yù)測(cè)d.風(fēng)險(xiǎn)總結(jié)36、風(fēng)險(xiǎn)分析包括：風(fēng)險(xiǎn)識(shí)別、(16)、ld.d39、系統(tǒng)響應(yīng)時(shí)間和作業(yè)吞吐量是衡量計(jì)算機(jī)系統(tǒng)性能的重要指標(biāo)。對(duì)于一個(gè)持續(xù)處理業(yè)務(wù)的系統(tǒng)而言，其（ ）a.響應(yīng)時(shí)間不會(huì)影響作業(yè)吞吐量b.響應(yīng)時(shí)間越短，作業(yè)吞吐量越小c.響應(yīng)時(shí)間越短，作業(yè)吞吐量越大d.響應(yīng)

12、時(shí)間越長(zhǎng)，作業(yè)吞吐量越大40、設(shè)集合z26=0，1，25)，乘法密碼的加密函數(shù)為ek:z26z26，ek(i)=(ki) mod 26，密鑰kz26-0，則加密函數(shù)e7(i)=(7i)mod 26是一個(gè)（ ）函數(shù)。 （ ）a.單射但非滿射b.滿射但非單射c.非單射且非滿射d.雙射41、類比二分搜索算法，設(shè)計(jì)k分搜索算法(k為大于2的整數(shù))如下：首先檢查n/k處(n為被搜索集合的元素個(gè)數(shù))的元素是否等于要搜索的值，然后檢查2n/k處的元素，這樣，或者找到要搜索的元素，或者把集合縮小到原來(lái)的1/k；如果未找到要搜索的元素，則繼續(xù)在得到的集合上進(jìn)行k分搜索；如此進(jìn)行，直到找到要搜索的元素或搜索失敗。

13、此k分搜索算法在最壞情況下搜索成功的時(shí)間復(fù)雜度為(57)，在最好情況下搜索失敗的時(shí)間復(fù)雜度為(58)。（57）處填（ ）a.o(log n)b.o(n log n)c.o(logk n)d.o(n logk n)42、類比二分搜索算法，設(shè)計(jì)k分搜索算法(k為大于2的整數(shù))如下：首先檢查n/k處(n為被搜索集合的元素個(gè)數(shù))的元素是否等于要搜索的值，然后檢查2n/k處的元素，這樣，或者找到要搜索的元素，或者把集合縮小到原來(lái)的1/k；如果未找到要搜索的元素，則繼續(xù)在得到的集合上進(jìn)行k分搜索；如此進(jìn)行，直到找到要搜索的元素或搜索失敗。此k分搜索算法在最壞情況下搜索成功的時(shí)間復(fù)雜度為(57)，在最好情況

14、下搜索失敗的時(shí)間復(fù)雜度為(58)。（58）處填（ ）a.o(log n)b.o(n log n)c.o(logk n)d.o(n logk n)43、假定一棵三叉樹(shù)的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（ ）a.3b.4c.5d.644、堆排序是(54)類排序，堆排序平均執(zhí)行的時(shí)間復(fù)雜度和需要附加的存儲(chǔ)空間復(fù)雜度分別是(55)。（54）處填（ ）a.插入b.歸并c.基數(shù)d.選擇45、堆排序是(54)類排序，堆排序平均執(zhí)行的時(shí)間復(fù)雜度和需要附加的存儲(chǔ)空間復(fù)雜度分別是(55)。（55）處填（ ）a.o(n2)和o(1)b.o(nlog2n)和o(1)c.o(nlog2n)和o(n)d.o(n2)和o(1

15、)46、尋址是指控制器根據(jù)指令的地址碼尋找操作數(shù)存于內(nèi)存的真實(shí)地址。指令中地址碼所表示的地址稱為(3)，將此地址經(jīng)過(guò)變換或運(yùn)算而得到的操作數(shù)的真實(shí)地址稱為(4)，相對(duì)于某一寄存器內(nèi)容而言的距物理地址的差距值稱為(5)。（3）處填（ ）a.物理地址b.形式地址c.偏移地址d.間接地址47、尋址是指控制器根據(jù)指令的地址碼尋找操作數(shù)存于內(nèi)存的真實(shí)地址。指令中地址碼所表示的地址稱為(3)，將此地址經(jīng)過(guò)變換或運(yùn)算而得到的操作數(shù)的真實(shí)地址稱為(4)，相對(duì)于某一寄存器內(nèi)容而言的距物理地址的差距值稱為(5)。（4）處填（ ）a.物理地址b.形式地址c.偏移地址d.間接地址48、尋址是指控制器根據(jù)指令的地址碼尋

16、找操作數(shù)存于內(nèi)存的真實(shí)地址。指令中地址碼所表示的地址稱為(3)，將此地址經(jīng)過(guò)變換或運(yùn)算而得到的操作數(shù)的真實(shí)地址稱為(4)，相對(duì)于某一寄存器內(nèi)容而言的距物理地址的差距值稱為(5)。（5）處填（ ）a.物理地址b.形式地址c.偏移地址d.間接地址49、在書店受訂管理中涉及到以下3個(gè)關(guān)系模式：書籍 books(bid，bname，price，author, publisher)訂單 orders(ordend，orderdate，cid)訂單明細(xì) orderlist (orderid，bid，qty)其中各屬性的含義是：bid書籍編號(hào)，price單價(jià)，author作者，publisher出版商，or

17、dend訂單編號(hào)， orderdate下訂日期，cid客戶編號(hào)， qty數(shù)量。每張訂單具有唯一的訂單編號(hào)；每張訂單編號(hào)中可包含多種書籍，但每種書籍的編號(hào)僅允許出現(xiàn)一次。則“訂單”實(shí)體的主鍵是(33)，“訂單明細(xì)”實(shí)體的主鍵是(34)。請(qǐng)將正面的sql語(yǔ)句空缺部分補(bǔ)充完整。create table orderlist (orderid char (20)，bd char(6)，qty numberic(9)，(35)(orderid，bid)，(36)(orderid)(37)(bid)（33）處填（ ）a.orderidb.cidc.(orderid，orderdate)d.(orderdat

18、e，cid)50、在書店受訂管理中涉及到以下3個(gè)關(guān)系模式：書籍 books(bid，bname，price，author, publisher)訂單 orders(ordend，orderdate，cid)訂單明細(xì) orderlist (orderid，bid，qty)其中各屬性的含義是：bid書籍編號(hào)，price單價(jià)，author作者，publisher出版商，ordend訂單編號(hào)， orderdate下訂日期，cid客戶編號(hào)， qty數(shù)量。每張訂單具有唯一的訂單編號(hào)；每張訂單編號(hào)中可包含多種書籍，但每種書籍的編號(hào)僅允許出現(xiàn)一次。則“訂單”實(shí)體的主鍵是(33)，“訂單明細(xì)”實(shí)體的主鍵是(34

19、)。請(qǐng)將正面的sql語(yǔ)句空缺部分補(bǔ)充完整。create table orderlist (orderid char (20)，bd char(6)，qty numberic(9)，(35)(orderid，bid)，(36)(orderid)(37)(bid)（34）處填（ ）a.orderidb.cidc.(orderid，bid)d.(bid，qty)51、在書店受訂管理中涉及到以下3個(gè)關(guān)系模式：書籍 books(bid，bname，price，author, publisher)訂單 orders(ordend，orderdate，cid)訂單明細(xì) orderlist (orderid，

20、bid，qty)其中各屬性的含義是：bid書籍編號(hào)，price單價(jià)，author作者，publisher出版商，ordend訂單編號(hào)， orderdate下訂日期，cid客戶編號(hào)， qty數(shù)量。每張訂單具有唯一的訂單編號(hào)；每張訂單編號(hào)中可包含多種書籍，但每種書籍的編號(hào)僅允許出現(xiàn)一次。則“訂單”實(shí)體的主鍵是(33)，”訂單明細(xì)”實(shí)體的主鍵是(34)。請(qǐng)將正面的sql語(yǔ)句空缺部分補(bǔ)充完整。create table orderlist (orderid char (20)，bd char(6)，qty numberic(9)，(35)(orderid，bid)，(36)(orderid)(37)(b

21、id)（35）處填（ ）a.primary keyb.foreign keyc.foreign key (orderid) references ordersd.foreign key (bid) references books52、在書店受訂管理中涉及到以下3個(gè)關(guān)系模式：書籍 books(bid，bname，price，author, publisher)訂單 orders(ordend，orderdate，cid)訂單明細(xì) orderlist (orderid，bid，qty)其中各屬性的含義是：bid書籍編號(hào)，price單價(jià)，author作者，publisher出版商，ordend訂單

22、編號(hào)， orderdate下訂日期，cid客戶編號(hào)， qty數(shù)量。每張訂單具有唯一的訂單編號(hào)；每張訂單編號(hào)中可包含多種書籍，但每種書籍的編號(hào)僅允許出現(xiàn)一次。則“訂單”實(shí)體的主鍵是(33)，“訂單明細(xì)”實(shí)體的主鍵是(34)。請(qǐng)將正面的sql語(yǔ)句空缺部分補(bǔ)充完整。create table orderlist (orderid char (20)，bd char(6)，qty numberic(9)，(35)(orderid，bid)，(36)(orderid)(37)(bid)（36）處填（ ）a.primary keyb.foreign keyc.foreign key (orderid) re

23、ferences ordersd.foreign key (bid) references books53、在書店受訂管理中涉及到以下3個(gè)關(guān)系模式：書籍 books(bid，bname，price，author, publisher)訂單 orders(ordend，orderdate，cid)訂單明細(xì) orderlist (orderid，bid，qty)其中各屬性的含義是：bid書籍編號(hào)，price單價(jià)，author作者，publisher出版商，ordend訂單編號(hào)， orderdate下訂日期，cid客戶編號(hào)， qty數(shù)量。每張訂單具有唯一的訂單編號(hào)；每張訂單編號(hào)中可包含多種書籍，但每

24、種書籍的編號(hào)僅允許出現(xiàn)一次。則“訂單”實(shí)體的主鍵是(33)，“訂單明細(xì)”實(shí)體的主鍵是(34)。請(qǐng)將正面的sql語(yǔ)句空缺部分補(bǔ)充完整。create table orderlist (orderid char (20)，bd char(6)，qty numberic(9)，(35)(orderid，bid)，(36)(orderid)(37)(bid)（37）處填（ ）a.primary keyb.foreion keyc.foreign key (orderid) references ordersd.foreign key (bid) references books54、the turing

25、 machine is an abstract(71)of computer execution and storage introduced in 1936 by alan turing to give a mathematically precise definition of(72). or mechanical procedure. as such it is still widely used in theoretical computer science, especially in(73)theory and the theory of computation. the thes

26、is that states that turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as turings thesis.every turing machine computes a certain(74)partial function over the strings over its alphabet. in that sense it behaves like a computer with a

27、 fixed program. however, as alan luring already described, we can encode the action table of every turing machine in a string. thus we might try to construct a turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then compute

28、s the tape that the encoded turing machine would have computed. as turing showed, such a luring machine is indeed possible and since it is able to simulate any other turing machine it is called a(75)turing machine.a universal turing machine is turing complete. it can calculate any recursive function

29、, decide any recursive language, and accept any recursively enumerable language. according to the church-turing thesis, the problems solvable by a universal turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of thos

30、e terms.（71）處填（ ）a.implementb.patternc.toold.model55、the turing machine is an abstract(71)of computer execution and storage introduced in 1936 by alan turing to give a mathematically precise definition of(72). or mechanical procedure. as such it is still widely used in theoretical computer science,

31、especially in(73)theory and the theory of computation. the thesis that states that turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as turings thesis.every turing machine computes a certain(74)partial function over the strings ove

32、r its alphabet. in that sense it behaves like a computer with a fixed program. however, as alan luring already described, we can encode the action table of every turing machine in a string. thus we might try to construct a turing machine that expects on its tape a string describing an action table f

33、ollowed by a string describing the input tape, and then computes the tape that the encoded turing machine would have computed. as turing showed, such a luring machine is indeed possible and since it is able to simulate any other turing machine it is called a(75)turing machine.a universal turing mach

34、ine is turing complete. it can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language. according to the church-turing thesis, the problems solvable by a universal turing machine are exactly those problems solvable by an algorithm or an effecti

35、ve method of computation, for any reasonable definition of those terms.（72）處填（ ）a.operationb.calculatingc.algorithmd.mechanics56、the turing machine is an abstract(71)of computer execution and storage introduced in 1936 by alan turing to give a mathematically precise definition of(72). or mechanical

36、procedure. as such it is still widely used in theoretical computer science, especially in(73)theory and the theory of computation. the thesis that states that turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as turings thesis.ever

37、y turing machine computes a certain(74)partial function over the strings over its alphabet. in that sense it behaves like a computer with a fixed program. however, as alan luring already described, we can encode the action table of every turing machine in a string. thus we might try to construct a t

38、uring machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then computes the tape that the encoded turing machine would have computed. as turing showed, such a luring machine is indeed possible and since it is able to simulate any o

39、ther turing machine it is called a(75)turing machine.a universal turing machine is turing complete. it can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language. according to the church-turing thesis, the problems solvable by a universal turi

40、ng machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.（73）處填（ ）a.intricacyb.complexityc.complicacyd.difficulty57、the turing machine is an abstract(71)of computer execution and storage introduced in 1936 by a

41、lan turing to give a mathematically precise definition of(72). or mechanical procedure. as such it is still widely used in theoretical computer science, especially in(73)theory and the theory of computation. the thesis that states that turing machines indeed capture the informal notion of effective

42、or mechanical method in logic and mathematics is known as turings thesis.every turing machine computes a certain(74)partial function over the strings over its alphabet. in that sense it behaves like a computer with a fixed program. however, as alan luring already described, we can encode the action

43、table of every turing machine in a string. thus we might try to construct a turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then computes the tape that the encoded turing machine would have computed. as turing showed, su

44、ch a luring machine is indeed possible and since it is able to simulate any other turing machine it is called a(75)turing machine.a universal turing machine is turing complete. it can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language. acc

45、ording to the church-turing thesis, the problems solvable by a universal turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.（74）處填（ ）a.fixedb.steadyc.variationald.changeable58、the turing machine is an

46、 abstract(71)of computer execution and storage introduced in 1936 by alan turing to give a mathematically precise definition of(72). or mechanical procedure. as such it is still widely used in theoretical computer science, especially in(73)theory and the theory of computation. the thesis that states

47、 that turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as turings thesis.every turing machine computes a certain(74)partial function over the strings over its alphabet. in that sense it behaves like a computer with a fixed program

48、. however, as alan luring already described, we can encode the action table of every turing machine in a string. thus we might try to construct a turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then computes the tape tha

49、t the encoded turing machine would have computed. as turing showed, such a luring machine is indeed possible and since it is able to simulate any other turing machine it is called a(75)turing machine.a universal turing machine is turing complete. it can calculate any recursive function, decide any r

50、ecursive language, and accept any recursively enumerable language. according to the church-turing thesis, the problems solvable by a universal turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.（75）處填

51、（ ）a.universalb.specialc.completed.changeable59、the notion of np-completeness has provided a(66)mathematical definition for(67)intractability of np problems. but this measure applies only to worst-case complexity. being np-complete does not(68)that a problem is intractable on the average case. indee

52、d, some np-complete problems are “(69)on average”, though some may not be. levin initiated the study of average-case intractability, he showed that a bounded tiling problem under a simple distribution is average-case np-complete. since then, several additional average-case np-complete problems have

53、been shown within levins(70). this paper is intended to provide a comprehensive survey of average-case np-complete problems that have been published so far, and the techniques of obtaining these results.（66）處填（ ）a.relaxedb.roughc.rigorousd.feasible60、the notion of np-completeness has provided a(66)m

54、athematical definition for(67)intractability of np problems. but this measure applies only to worst-case complexity. being np-complete does not(68)that a problem is intractable on the average case. indeed, some np-complete problems are “(69)on average”, though some may not be. levin initiated the st

55、udy of average-case intractability, he showed that a bounded tiling problem under a simple distribution is average-case np-complete. since then, several additional average-case np-complete problems have been shown within levins(70). this paper is intended to provide a comprehensive survey of average-case np-complete problems that have been published so far, and the techniques of obtaining these results.（67）處填（ ）a.accessingb.calculatingc.countingd.measuring61、the notion of