中級軟件設(shè)計師單項^選擇考試卷模擬考試題_0

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

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

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

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

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

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

7、樹的先根遍歷序列中x在y之前，而在其后根遍歷序列中x在y之后，則x和y的關(guān)系是（ ）a.x是y的左兄弟b.x是y的右兄弟c.x是y的祖先d.x是y的后裔23、設(shè)f表示某個二元邏輯運算符，pfq的真值表如下所示，則pfq等價于（ ）。 （ ）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是一個（ ）函數(shù)。 （ ）a.單射但非滿射b.滿射但非單射c.非單射且非滿射d.雙射25、在osi參考模型中能實現(xiàn)路由選擇、擁塞控制與互聯(lián)功能的層是（ ）a.傳輸層

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

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

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

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

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

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

14、下搜索失敗的時間復(fù)雜度為(58)。（58）處填（ ）a.o(log n)b.o(n log n)c.o(logk n)d.o(n logk n)43、假定一棵三叉樹的結(jié)點數(shù)為50，則它的最小高度為（ ）a.3b.4c.5d.644、堆排序是(54)類排序，堆排序平均執(zhí)行的時間復(fù)雜度和需要附加的存儲空間復(fù)雜度分別是(55)。（54）處填（ ）a.插入b.歸并c.基數(shù)d.選擇45、堆排序是(54)類排序，堆排序平均執(zhí)行的時間復(fù)雜度和需要附加的存儲空間復(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)存的真實地址。指令中地址碼所表示的地址稱為(3)，將此地址經(jīng)過變換或運算而得到的操作數(shù)的真實地址稱為(4)，相對于某一寄存器內(nèi)容而言的距物理地址的差距值稱為(5)。（3）處填（ ）a.物理地址b.形式地址c.偏移地址d.間接地址47、尋址是指控制器根據(jù)指令的地址碼尋找操作數(shù)存于內(nèi)存的真實地址。指令中地址碼所表示的地址稱為(3)，將此地址經(jīng)過變換或運算而得到的操作數(shù)的真實地址稱為(4)，相對于某一寄存器內(nèi)容而言的距物理地址的差距值稱為(5)。（4）處填（ ）a.物理地址b.形式地址c.偏移地址d.間接地址48、尋址是指控制器根據(jù)指令的地址碼尋

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

17、dend訂單編號， orderdate下訂日期，cid客戶編號， qty數(shù)量。每張訂單具有唯一的訂單編號；每張訂單編號中可包含多種書籍，但每種書籍的編號僅允許出現(xiàn)一次。則“訂單”實體的主鍵是(33)，“訂單明細(xì)”實體的主鍵是(34)。請將正面的sql語句空缺部分補充完整。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個關(guān)系模式：書籍 books(bid，bname，price，author, publisher)訂單 orders(ordend，orderdate，cid)訂單明細(xì) orderlist (orderid，bid，qty)其中各屬性的含義是：bid書籍編號，price單價，author作者，publisher出版商，ordend訂單編號， orderdate下訂日期，cid客戶編號， qty數(shù)量。每張訂單具有唯一的訂單編號；每張訂單編號中可包含多種書籍，但每種書籍的編號僅允許出現(xiàn)一次。則“訂單”實體的主鍵是(33)，“訂單明細(xì)”實體的主鍵是(34

19、)。請將正面的sql語句空缺部分補充完整。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個關(guān)系模式：書籍 books(bid，bname，price，author, publisher)訂單 orders(ordend，orderdate，cid)訂單明細(xì) orderlist (orderid，

20、bid，qty)其中各屬性的含義是：bid書籍編號，price單價，author作者，publisher出版商，ordend訂單編號， orderdate下訂日期，cid客戶編號， qty數(shù)量。每張訂單具有唯一的訂單編號；每張訂單編號中可包含多種書籍，但每種書籍的編號僅允許出現(xiàn)一次。則“訂單”實體的主鍵是(33)，”訂單明細(xì)”實體的主鍵是(34)。請將正面的sql語句空缺部分補充完整。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個關(guān)系模式：書籍 books(bid，bname，price，author, publisher)訂單 orders(ordend，orderdate，cid)訂單明細(xì) orderlist (orderid，bid，qty)其中各屬性的含義是：bid書籍編號，price單價，author作者，publisher出版商，ordend訂單

22、編號， orderdate下訂日期，cid客戶編號， qty數(shù)量。每張訂單具有唯一的訂單編號；每張訂單編號中可包含多種書籍，但每種書籍的編號僅允許出現(xiàn)一次。則“訂單”實體的主鍵是(33)，“訂單明細(xì)”實體的主鍵是(34)。請將正面的sql語句空缺部分補充完整。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個關(guān)系模式：書籍 books(bid，bname，price，author, publisher)訂單 orders(ordend，orderdate，cid)訂單明細(xì) orderlist (orderid，bid，qty)其中各屬性的含義是：bid書籍編號，price單價，author作者，publisher出版商，ordend訂單編號， orderdate下訂日期，cid客戶編號， qty數(shù)量。每張訂單具有唯一的訂單編號；每張訂單編號中可包含多種書籍，但每

24、種書籍的編號僅允許出現(xiàn)一次。則“訂單”實體的主鍵是(33)，“訂單明細(xì)”實體的主鍵是(34)。請將正面的sql語句空缺部分補充完整。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