【文章內(nèi)容簡(jiǎn)介】 在大型的科學(xué)計(jì)算與復(fù)雜問(wèn)題求解時(shí)，具體的算法針對(duì)具體問(wèn)題，可以有無(wú)數(shù)種。但一般常用類型有：迭代法、遞推法、回溯法、遞歸法、貪婪法、窮舉法、規(guī)劃法等。 遞歸算法是常用算法之一，它的基本思想是把一個(gè)大的問(wèn)題 (不妨設(shè)規(guī)模為 N)分解為一些規(guī)模較小的問(wèn)題，從這些較小問(wèn)題的解，構(gòu)造出大問(wèn)題的解，而這些規(guī)模較小的問(wèn)題，用同樣的方法分解成更小的問(wèn)題 ，并從更小問(wèn)題的解，構(gòu)造出較小的問(wèn)題。不斷地分解問(wèn)題成更小的問(wèn)題，一層層下去，一般來(lái)說(shuō)，分解到最后的小問(wèn)題 (例如N=1 時(shí) )應(yīng)該是可直接求解的。 依據(jù)上述思想，遞歸算法的過(guò)程一般分為遞推和回歸兩個(gè)階段。在遞推階段把復(fù)雜問(wèn)題逐級(jí)推到簡(jiǎn)單一點(diǎn)的問(wèn)題的求解。在遞推到小問(wèn)題能直接求解時(shí)，遞推終止。在回歸階段，則從所獲得的最簡(jiǎn)單的直接解，逐級(jí)返回，得到大問(wèn)題的解。 軟考社區(qū) ()中國(guó)軟考資訊、交流中心 ！ 提供 軟考 歷年試題，模擬試題， 電子教程 ， 軟考新聞 ， 各地軟考辦 ， 軟考經(jīng)驗(yàn)心得 等。 軟考社區(qū)論壇： ●散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計(jì)算轉(zhuǎn)化為記錄的存放地址。因?yàn)樯⒘泻瘮?shù)不是一對(duì)一的關(guān)系，所以選擇好的 (35) 方法是散列文件的關(guān)鍵。 (35) A．散列函數(shù) B．除余法中的質(zhì)數(shù) C．沖突處理 D．散列函數(shù)和沖突處理 【解析】在散列法中，選擇好的散列函數(shù)和沖突處理方法是其關(guān)鍵。 ●最佳二叉搜索樹(shù)是 (36) 。 (36) A．關(guān)鍵碼個(gè)數(shù)最少的二叉搜索樹(shù) B．搜索時(shí)平均比較次數(shù)最少的二叉搜索樹(shù) C．所有結(jié)點(diǎn)的左子樹(shù)都為空的二叉搜索樹(shù) D．所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉搜索樹(shù) 【解析】最佳二叉搜索樹(shù)是搜索時(shí)平均比較次數(shù)最少的二叉搜索樹(shù)。 ●已知有二維數(shù)組 A［ 0．． n1］［ 0．． n1］，其中當(dāng) i+j=n 時(shí)， A［ i］［ j］≠ 0，現(xiàn)在要將 A數(shù)組壓縮存儲(chǔ)到一維數(shù)組 T［ 0..m］，其中 mn。數(shù)組 T 的第一個(gè)元素 T［ 0］ =A［ 1］［ n1］ T［ 1］ =A［ 2］［ n2］，……，依次類推，那么放入 A［ i］［ j］ (i+j=n)的元素是 (37) 。 (37) A． T［ i+j］ B． T［ i*n+j］ C． T［ i］ D． T［ i1］ 【解析】由題可知，除第 0 行外，每一行只存儲(chǔ)一個(gè)元素，因此 i行應(yīng)存放在 T［ i1］之中。 ●將兩個(gè)長(zhǎng)度為 n 的遞增有序表歸并成一個(gè)長(zhǎng)度為 2n 的遞增有序表，最少需要進(jìn)行 關(guān)鍵字比較 (38) 次。 (38) A． n B． n21 C． 2n1 D． 2n2 【解析】由于兩個(gè)表有序，最少比較是一個(gè)表的最大結(jié)點(diǎn)，比另一個(gè)表的所有結(jié)點(diǎn)小。如 {l， 2， 3}和 {4， 5， 6}。我們只要將表中第一個(gè)結(jié)點(diǎn) (最小結(jié)點(diǎn) )，和另個(gè)表中所有結(jié)點(diǎn)比較，比較次數(shù)為另個(gè)表的表長(zhǎng)。 ●對(duì)于一個(gè)具有 n 個(gè)結(jié)點(diǎn)和 e 條邊的無(wú)向圖，若采用鄰接表表示，則所有邊鏈表中邊結(jié)點(diǎn)的總數(shù)為 (39) 。 (39) A． 2e B． e/4 C． e／ 2 D． n+2e 【解析】用鄰 接表表示無(wú)向圖，圖中每條邊在鄰接表中會(huì)出現(xiàn)兩次，因此，對(duì)于一個(gè)具有 n個(gè)結(jié)點(diǎn)和 e 條邊的無(wú)向圖，所有邊鏈表中邊結(jié)點(diǎn)的總數(shù)為 2e。 ●在需要經(jīng)常查找結(jié)點(diǎn)的前驅(qū)與后繼的場(chǎng)合中，使用 (40) 比較合適。 (40) A．單鏈表 B．循環(huán)鏈表 C．鏈棧 D．雙鏈表 【解析】雙鏈表，一個(gè)鏈指向前驅(qū)結(jié)點(diǎn)，一個(gè)鏈指向后繼結(jié)點(diǎn)。 ●在操作系統(tǒng)中，對(duì)信號(hào)量 S 的 P 原語(yǔ)操作定義中，使進(jìn)程進(jìn)入相應(yīng)等待隊(duì)列等待的條件是 (41) 。 (41) A． S0 B． S=0 軟考社區(qū) ()中國(guó)軟考資訊、交流中心 ！ 提供 軟考 歷年試題，模擬試題， 電子教程 ， 軟考新聞 ， 各地軟考辦 ， 軟考經(jīng)驗(yàn)心得 等。 軟考社區(qū)論壇： C． S≠ 0 D． S0 【解析】 P(S)原語(yǔ)操作為： 1)將信號(hào)量 S 的值減 1，即 S=S1； 2)如果 S≥ 0，則該進(jìn)程繼續(xù)執(zhí)行；否則該進(jìn)程置為等待狀態(tài)，排入等待隊(duì)列。 ●下面幾個(gè)方面中： Ⅰ．語(yǔ)法Ⅱ．語(yǔ)義Ⅲ．語(yǔ)句Ⅳ．語(yǔ)用 程序設(shè)計(jì)語(yǔ)言的定義一般應(yīng)包括 (42) 。 (42) A．Ⅰ、Ⅱ和Ⅲ B．Ⅰ、Ⅱ和Ⅳ C．Ⅰ、Ⅱ、Ⅲ和Ⅳ D．Ⅰ、Ⅲ和Ⅳ 【解析】程序設(shè)計(jì)語(yǔ)言的定義一般應(yīng)包括語(yǔ)法、語(yǔ)義和語(yǔ)用幾個(gè)方面。語(yǔ)法是指記號(hào)的組合規(guī)則；語(yǔ)義指記號(hào)的特定意義；而語(yǔ)用是指程序與使用者的關(guān)系。 ●下面是關(guān)于 CPU 與主存儲(chǔ)器之間的 Cache 的敘述，其中正確的是 (43) 。 (43) A． Cache 存放的只是主存儲(chǔ)器中某一部分內(nèi)容的映象 B． Cache 能由用戶直接訪問(wèn) C．位于主板上的 L2 Cache 要比與 CPU 封裝在一起的 L2 Cache 速度快 D．位于主板上的 L2 Cache 要比與 CPU 做在一基片上的 L2 Cache 速度快 【解析】 Cache 負(fù)責(zé)解決主存與 CPU 之間速度的協(xié)調(diào)問(wèn)題。 Cache 中存放著主存的一部分副本 (主存中的部分內(nèi)容 )，不能由用戶直接訪問(wèn)。 Cache 可以有多級(jí)，離 CPU 越近的，速度越快。 ●某電視臺(tái)擬將他人已出版的《衛(wèi)生小常識(shí)》 VCD光盤(pán)在該電視臺(tái)的 生活 節(jié)目中播放，那么，該電視臺(tái) (44) 。 (44) A．可以不經(jīng)該 VCD 光盤(pán)出版者許可，但必須向其支付報(bào)酬 B．既不必經(jīng)該 VCD 光盤(pán)出版者許可，也不必向其支付報(bào)酬 C．既須經(jīng)該 VCD 光盤(pán)出版者許可，也須向其支付報(bào)酬 D．只須經(jīng)該 VCD 光盤(pán)出版者許可，但不必向其支付報(bào)酬 【解析】我國(guó)的《中華人民共和國(guó)著作權(quán)法》第四十五條規(guī)定：電視臺(tái)播放他人的電影作品和以類似攝制電影的方法創(chuàng)作的作品、錄像制品，應(yīng)當(dāng)取得制片者或者錄像制作者許可，并支付報(bào)酬；播放他人的錄像制品，還應(yīng)當(dāng)取得著作權(quán)人許可，并支付報(bào)酬。 ● (45) 是面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言不同于其他語(yǔ)言的主要特點(diǎn)。是否建立了豐富的 (46) 是衡量一個(gè)面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言成熟與否的一個(gè)重要標(biāo)志。 (47) 是在類及子類之間自動(dòng)地共享數(shù)據(jù)和方法的一種機(jī)制。 (45) A．繼承性 B．消息傳遞 C．多態(tài)性 D．封裝性 (46) A．函數(shù)庫(kù) B．類庫(kù) C．?dāng)?shù)據(jù)庫(kù) D．方法庫(kù) (47) A．調(diào)用 B．引用 C．消息傳遞 D．繼承 【解析】面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言的主要特點(diǎn)是繼承性、封裝性和多態(tài)性，但由于面向過(guò)程的程序設(shè)計(jì)語(yǔ)言本身也具有一定的封裝性和多態(tài)性。面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言對(duì)程序員開(kāi)放的不再是函數(shù)庫(kù)，而是類庫(kù)。豐富的類庫(kù)可以軟考社區(qū) ()中國(guó)軟考資訊、交流中心 ！ 提供 軟考 歷年試題，模擬試題， 電子教程 ， 軟考新聞 ， 各地軟考辦 ， 軟考經(jīng)驗(yàn)心得 等。 軟考社區(qū)論壇： 加速軟件的開(kāi)發(fā)，減少開(kāi)發(fā)人員的勞動(dòng)，提高軟件的質(zhì)量，具有重要的意義。當(dāng)今成熟的面向?qū)ο笤O(shè)計(jì)語(yǔ)言都具有 豐富的類庫(kù)。子類通過(guò)對(duì)父類的繼承可以立刻擁有父類的成員變量和成員方法。 ●白盒測(cè)試方法一般適合用于 (48) 測(cè)試。 (48) A．單元 B．系統(tǒng) C．集成 D．回歸 【解析】 白盒測(cè)試中，源程序?qū)y(cè)試人員開(kāi)放，允許測(cè)試人員根據(jù)程序的結(jié)構(gòu)設(shè)計(jì)和選擇相應(yīng)的測(cè)試用例，以達(dá)到遍歷程序的所有邏輯路徑的目的，因此白盒測(cè)試適用于單元測(cè)試。 ●在 YUV彩色空間中對(duì) YUV分量進(jìn)行數(shù)字化，對(duì)應(yīng)的數(shù)字化位數(shù)通常采用 Y： U： V= (49) 。 (49) A． 8： 4： 4 B． 8： 4： 2 C． 8： 2： 4 D． 4： 8： 2 【解析】在現(xiàn)代彩色電視系統(tǒng)中，通常采用三管彩色攝像機(jī)或彩色 CCD 攝像機(jī)，它把攝得的彩色圖像信號(hào)，經(jīng)分色棱鏡分成 RGB 3個(gè)分量信號(hào)，再經(jīng)過(guò)放大和γ校正得到 RGB，經(jīng)矩陣變換電路得到亮度信號(hào) Y、色差信號(hào)RY(記為 U)及 BY(記為 V)，最后發(fā)送端將 Y、 U 及 V 3個(gè)信號(hào)進(jìn)行編碼，用同一信道發(fā)送出去。這就是我們常用的 YUV彩色空間。在 YUV彩色空間，數(shù)字化后通常為 Y： U： V=8： 4： 4 或 Y： U： V=8： 2： 2，即把亮度信號(hào) Y 的每個(gè)像素都數(shù)字化為 8bit(256 級(jí)亮度 )，而 U、 V色差信號(hào)