真誠(chéng)為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請(qǐng)指正。 一、選擇題 1．一個(gè).java文件中可以有（ ）個(gè)public類。 A．一個(gè) B．兩個(gè) C．多個(gè) D．零個(gè) 2．一個(gè)算法應(yīng)該是（     ） A．程序     B．問題求解步驟的描述     C．要滿足五個(gè)基本特性     D．A和C 3．用計(jì)算機(jī)無法解決“打印所有素?cái)?shù)”的問題，其原因是解決該問題的算法違背了算法特征中的（ ） A．唯一性 B．有窮性 C．有0個(gè)或多個(gè)輸入 D．有輸出 4．某校有6位學(xué)生參加學(xué)生會(huì)主席競(jìng)選，得票數(shù)依次為130，20，98，15，67，3。若采用冒泡排序算法對(duì)其進(jìn)行排序，則完成第二遍時(shí)的結(jié)果是（ ） A．3，15，130，20，98，67 B．3，15，20，130，98，67 C．3，15，20，67，130，98 D．3，15，20，67，98，130 5．下列關(guān)于算法的描述，正確的是（ ） A．一個(gè)算法的執(zhí)行步驟可以是無限的 B．一個(gè)完整的算法必須有輸出 C．算法只能用流程圖表示 D．一個(gè)完整的算法至少有一個(gè)輸入 6．Java Application源程序的主類是指包含有（ ）方法的類。 A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法 7．找出滿足各位數(shù)字之和等于5的所有三位數(shù)可采用的算法思路是（ ） A．分治法 B．減治法 C．蠻力法 D．變治法 8．在編寫Java Application程序時(shí)，若需要使用到標(biāo)準(zhǔn)輸入輸出語句，必須在程序的開頭寫上( )語句。 A、import java.awt.* ; B、import java.applet.Applet ; C、import java.io.* ; D、import java.awt.Graphics ; 9．計(jì)算某球隊(duì)平均年齡的部分算法流程圖如圖所示，其中：c用來記錄已輸入球員的人數(shù)，sum用來計(jì)算有效數(shù)據(jù)之和，d用來存儲(chǔ)從鍵盤輸入的球員年齡值，輸入0時(shí)表示輸入結(jié)束。 圖中空白處理框①和②處應(yīng)填入的是（ ） A．① sum ← sum + d B．① sum ← sum + c ② c ← c + 1 ② c ← c + 1 C．① sum ← sum + d D．① sum ← sum + c ② d ← d + 1 ② d ← d + 1 10．報(bào)名參加冬季越野賽跑的某班5位學(xué)生的學(xué)號(hào)是：5，8，11，33，45。利用折半查找，查找學(xué)號(hào)為33號(hào)學(xué)生的過程中，依次被訪問到的學(xué)號(hào)是（ ） A．5，11，33 B．8，33 C．11，45，33 D．11，33 11．表達(dá)式（short）8/9.2*5的值的類型為 A．short B． int C．double D．float 12． 設(shè)x為int型變量，則執(zhí)行一下語句段后，x的值為 x=10; x+=x-=x-x; A．10 B．20 C．40 D．30 13．下列代碼的執(zhí)行結(jié)果是 public class StringTest{ public static void main(String args[]){ int a=4,b=6,c=8; String s=”abc”; System.out.println(a+b+s+c); System.out.printin(); } } A．a(chǎn)babcc B．464688 C．46abc8 D．10abc8 14． 下列程序段執(zhí)行后t3的結(jié)果是 int t1 = 2, t2 = 3, t3; t3=t1<t2? t1:t2+t1 A．2 B．4 C．5 D．6 15．要計(jì)算當(dāng)0〈x〈10時(shí)，y=x，應(yīng)當(dāng)使用的語句是 A．if(0<x<10)y=x; B．if(0<x|x<10)y=x; C．if(0<x&x<10)y=x; D．if(0<x^x<10)y=x; 16．對(duì)一組數(shù)據(jù)（2，12，16，88，5，10）進(jìn)行排序，若前三趟排序結(jié)果如下， 第一趟：2，12，16，88，5，10 第二趟：2，5，16，88，12，10 第三趟：2，5，10，88，12，16 則采用的排序方法是（ ） A．冒泡排序 B．合并排序 C．快速排序 D．選擇排序 17．類與對(duì)象的關(guān)系是（ ） A． 建筑圖紙和建筑物的關(guān)系 B． 汽車與發(fā)動(dòng)機(jī)的關(guān)系 C． 人與黑人的關(guān)系 D． 沒有關(guān)系 18．JAVA語言二維數(shù)組定義中，第二維的長(zhǎng)度 ( ) A．可以不相等 B．必須相等 C．高維數(shù)組長(zhǎng)度與低維數(shù)組長(zhǎng)度相同 D．固定長(zhǎng)度 19．算法必須具備（ ）這三個(gè)特性。 A．可執(zhí)行性、可移植性、可擴(kuò)充性 B．可執(zhí)行性、確定性、有窮性 C．確定性、有窮性、穩(wěn)定性 D．易讀性、穩(wěn)定性、安全性 20．如下圖所示，該流程圖所表示的算法違背了算法的有窮性特征，下列修改方法中，可以改正該錯(cuò)誤的是（ ） A．將①處改為 i ← 0 B．將②處改為 s ≥ 0 ? C．將③處改為 i ← i-2 D．將④處改為 s ← s-i 二、填空題 1．一個(gè)顯而易見的事實(shí)是：大部分算法的執(zhí)行時(shí)間隨著 輸入量的增加 而增大。 2．算法是 求解某一問題所使用的一系列清晰的指令 。 3．算法分析時(shí)間效率模型的基本數(shù)學(xué)公式是： T(n) ≈ CopC(n) 。 4．算法設(shè)計(jì)技術(shù)是 用算法解題的一般性方法 ，用于解決不同計(jì)算領(lǐng)域的多種問題。 5．三個(gè)漸進(jìn)符號(hào)： O 、 ? 和 ? 。 6．效率分析框架主要關(guān)心一個(gè)算法的 基本操作次數(shù)的增長(zhǎng)次數(shù) ，并把它作為算法效率的主要指標(biāo)。 7．Java源程序的文件名和程序中定義的 主類名 應(yīng)保持一致，包括字母大小寫的匹配。 8．算法中常見的問題類型包括： 排序 、 查找 、字符串處理和組合問題等。 9．類中的 構(gòu)造 方法是一個(gè)特殊的方法，其名稱與類名相同。 10．面向?qū)ο蟪绦蛟O(shè)計(jì)語言中的3個(gè)重要特性分別是 封裝 、 繼承 和 多態(tài) 。 11．Java源程序文件的擴(kuò)展名為 java ，編譯生成的字節(jié)碼文件的擴(kuò)展名為 class 。 12．大多數(shù)算法的效率可以分為常數(shù)、 對(duì)數(shù) 、線性、平方、 立方 和指數(shù)等。 三、簡(jiǎn)答題 1．什么是算法？算法的五個(gè)重要特征是什么？ 答：算法是求解某一問題所使用的一系列清晰的指令。 答： （1）輸入：有零個(gè)或多個(gè)由外部提供的量作為算法的輸入. （2）輸出：算法產(chǎn)生至少一個(gè)量作為輸出. （3）確定性：組成算法的每條指令是清晰的,無歧義的. （4）有限性：在執(zhí)行了有窮步驟后運(yùn)算終止. （5）可行性：運(yùn)算都是基本運(yùn)算，原理上能在有限時(shí)間內(nèi)完成. 2．請(qǐng)簡(jiǎn)述蠻力算法的優(yōu)點(diǎn)？ 答： 蠻力算法是一種簡(jiǎn)單直接地解決問題的方法。蠻力法具有如下優(yōu)點(diǎn)：(1)應(yīng)用范圍廣；(2)不受實(shí)例規(guī)模的限制；(3)當(dāng)要解決的問題實(shí)例不多,設(shè)計(jì)更高效算法的代價(jià)太大時(shí)可選用；(4)對(duì)解決一些小規(guī)模的問題實(shí)例仍然有效；(5)可作為衡量其他算法的參照物。 3．算法設(shè)計(jì)與分析過程的典型步驟都包括哪些？ 答： （1）了解問題的內(nèi)容 （2）了解計(jì)算設(shè)備的性能 （3）在精確解法和近似解法之間選擇 （4）確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu) （5）算法設(shè)計(jì)技術(shù) （6）詳細(xì)表述算法的方法 （7）證明算法的正確性 （8）分析算法 （9）為算法寫代碼 4．請(qǐng)簡(jiǎn)述分治法的基本思路？ 答： 將規(guī)模為N的問題分解為k個(gè)規(guī)模較小的子問題，使這些子問題相互獨(dú)立可分別求解，再將k個(gè)子問題的解合并成原問題的解。如子問題的規(guī)模仍很大，則反復(fù)分解直到問題小到可直接求解為止。 在分治法中,子問題的解法通常與原問題相同,自然導(dǎo)致遞歸過程。 5．請(qǐng)簡(jiǎn)述減治法的基本思路？ 答： 減治技術(shù)利用了一個(gè)問題給定實(shí)例的解和同樣問題較小實(shí)例的解之間的某種關(guān)系。一旦建立了這種關(guān)系，既可以從頂至底（遞歸地），也可以從底至頂（非遞歸地）來運(yùn)用該關(guān)系。 減治法有三種主要的變種： n 減常數(shù)(如1)：:每此迭代規(guī)模減小n→n-1 n 減因子(如1/2)：每此迭代規(guī)模減半n→ n/2 n 減可變規(guī)模：每此迭代減小的規(guī)模不同 6．請(qǐng)簡(jiǎn)述遞歸算法設(shè)計(jì)的基本思路？ 答： 遞歸的執(zhí)行過程由分解過程和求值過程兩部分構(gòu)成。 實(shí)際上, 遞歸思路是把一個(gè)不能或不好直接求解的“大問題”轉(zhuǎn)化成一個(gè)或幾個(gè)“小問題”來解決，再把這些“小問題”進(jìn)一步分解成更小的“小問題”來解決，如此分解，直至每個(gè)“小問題”都可以直接解決(此時(shí)分解到遞歸出口)。 但遞歸分解不是隨意的分解，遞歸分解要保證“大問題”與“小問題”相似，即求解過程與環(huán)境都相似。并且有一個(gè)分解的終點(diǎn)。從而使問題可解。 7．請(qǐng)簡(jiǎn)述變治法的基本思路？ 答： 變治法的技術(shù)基于變換思想。變治法分為兩個(gè)階段的工作：首先在“變”的階段，出于這樣或那樣的原因，將問題的實(shí)例變得更容易求解；然后是“治”的階段，對(duì)問題的實(shí)例進(jìn)行求解。 根據(jù)對(duì)問題實(shí)例的變換方式不同，變治法有三種主要的類型： （1）實(shí)例化簡(jiǎn)——變換為同樣問題的一個(gè)更簡(jiǎn)單或者更方便的實(shí)例； （2）改變表現(xiàn)——變換為同樣實(shí)力的不同表現(xiàn)； （3）問題化簡(jiǎn)——變換為另一個(gè)問題的實(shí)例，這種問題的算法是已知的。 8．請(qǐng)簡(jiǎn)述時(shí)空權(quán)衡法的基本思路？ 答： 時(shí)空權(quán)衡法的基本思路是對(duì)問題的部分或全部輸入做預(yù)處理，然后對(duì)得到的額外信息使用額外的存儲(chǔ)空間來存儲(chǔ)。通過實(shí)現(xiàn)更快或更方便的數(shù)據(jù)存取，以加速后面問題的求解來提高算法的效率。 四、算法實(shí)現(xiàn)題 1．對(duì)于任意非負(fù)整數(shù)n，計(jì)算階乘函數(shù)F(n) = n！的值。因?yàn)楫?dāng)n ≥ 1時(shí)，n！= 1×2×3×……×（n-1）×n = (n-1)！×n。并且根據(jù)定義，0！= 1，所以可以使用下面的遞歸算法計(jì)算n！：F(n) = F(n-1) × n。 請(qǐng)編寫Java應(yīng)用程序，由鍵盤輸入n的值，在屏幕上輸出計(jì)算的n！的結(jié)果。 import java.io.*; public class FN { static long f(int n) { long r = 1; if(n != 0) r = n * f(n-1); return r; } public static void main(String args[]) throws IOException { //輸入N的值 byte[] buf = new byte[10]; System.out.println("請(qǐng)輸入一個(gè)整數(shù)："); System.in.read(buf); String str=new String(buf); int n=Integer.parseInt(str.trim()); //計(jì)算N！的值 long result = f(n); //輸出結(jié)果 System.out.println(n + "!=" + result); } } 2．斐波那契數(shù)列：0，1，1，2，3，5，8，13，21，34，…… 這個(gè)數(shù)列可以用一個(gè)簡(jiǎn)單的遞推式和兩個(gè)初始條件來定義： 當(dāng)n > 1時(shí)，F(xiàn)(n) = F(n-1) + F(n-2) F(0) = 0，F(xiàn)(1) = 1 請(qǐng)編寫Java應(yīng)用程序，由鍵盤輸入n的值代表要生成斐波那契數(shù)列的項(xiàng)數(shù)，在屏幕上輸出n項(xiàng)斐波那契數(shù)列。 import java.io.*; public class Fb{ /*斐波那契數(shù)列算法*/ int f(int n){ int r; if(n <= 1) r = n; else r = f(n-1) + f(n-2); return r; } public static void main(String args[]) throws IOException{ System.out.println("請(qǐng)輸入所求斐波那契數(shù)列的項(xiàng)數(shù)："); byte buf[] = new byte[20]; System.in.read(buf); String t1 = new String(buf); int n = Integer.parseInt(t1.trim()); Fb f1 = new Fb(); int b; System.out.println("輸出包含" + n + "項(xiàng)的斐波那契數(shù)列："); for(int i = 0; i <= n; i++) { b = f1.f(i); System.out.print(b + " "); } System.out.println(); } } 3．編寫基于Java語言的選擇排序算法。 /*** * 功能：該算法用選擇排序?qū)o定的數(shù)組排序 * 輸入：一個(gè)亂序的整數(shù)數(shù)組a[ ] * 輸出：升序排列的整數(shù)數(shù)組a[ ] ***/ public void selectionSort (int a[ ]) { int temp,min; for(int i=0;i<a.length-1;i++) { min = i; for(int j=i+1;j<a.length;j++) if(a[min] > a[j]) min = j; temp = a[i]; a[i] = a[min]; a[min] = temp; } } 4．編寫基于Java語言的冒泡排序算法。 /*** * 功能：該算法用冒泡排序?qū)o定的數(shù)組排序 * 輸入：一個(gè)亂序的整數(shù)數(shù)組a[ ] * 輸出：升序排列的整數(shù)數(shù)組a[ ] ***/ public void bubbleSort(int a[ ]) { int temp; for(int i=0;i<a.length-1;i++) for(int j=0;j<a.length-1-i;j++) if(a[j]>a[j+1]) { temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; } } 5．編寫基于Java語言的順序查找算法。 /*** * 功能：該算法實(shí)現(xiàn)順序查找功能 * 輸入：一個(gè)整數(shù)數(shù)組a[ ]和一個(gè)要查找的鍵值k * 輸出：如果在數(shù)組中找到k，則返回對(duì)應(yīng)數(shù)組元素的下標(biāo)；如果在數(shù)組中找不到k，則返回-1 ***/ public int seqSearch(int a[ ],int k) { int i = 0; while((i < a.length ) && ( a[i] != k )) i = i + 1; if( i < a.length) return i; else return -1; } 6．編寫基于Java語言的折半查找算法。 /*** * 功能：該算法實(shí)現(xiàn)折半查找功能 * 輸入：一個(gè)已經(jīng)按照升序排列好的整數(shù)數(shù)組a[ ]和一個(gè)要查找的鍵值k * 輸出：如果在數(shù)組中找到k，則返回對(duì)應(yīng)數(shù)組元素的下標(biāo)；如果在數(shù)組中找不到k，則返回-1 ***/ public int binarySearch(int a[ ], int k) { int low = 0; int upper = a.length - 1; while(low <= upper) { int mid = (low+upper) / 2; if(k == a[mid]) return mid; else if(des < a[mid]) upper = mid - 1; else low = mid + 1; } return -1; } 7．編寫基于Java語言的字符串匹配算法。 /*** * 功能：該算法實(shí)現(xiàn)字符串匹配功能 * 輸入：一個(gè)n個(gè)字符的字符串str代表一段文本 一個(gè)m個(gè)字符的字符串key代表一個(gè)模式 * 輸出：如果查找成功的話，返回文本的第一個(gè)匹配字符串中第一個(gè)字符的位置， 否則返回-1 ***/ public int stringMatch(String str,String key) { int j; int n = str.length(); int m = key.length(); for(int i = 0; i <= (n - m); i++) { j = 0; while((j < m) && (key.charAt(j) == str.charAt(i+j))) { j = j + 1; System.out.println(i + "," + j); if(j == m) return i; } } return -1; } 8．編寫基于Java語言的直接插入排序算法。 /*** * 功能：該算法用直接插入排序?qū)o定的數(shù)組排序 * 輸入：一個(gè)亂序的整數(shù)數(shù)組a[ ] * 輸出：升序排列的整數(shù)數(shù)組a[ ] ***/ public void insertSort (int a[ ]) { int temp,i,j; for(i=1;i<a.length;i++) { temp=a[i]; j=i-1; while(j>=0 && a[j]>=temp) { a[j+1]=a[j]; j--; } a[j+1]=temp; } } 9 / 9