真誠(chéng)為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請(qǐng)指正一、選擇題1．一個(gè).java文件中可以有（ ）個(gè)public類(lèi)A．一個(gè) B．兩個(gè) C．多個(gè) D．零個(gè)2．一個(gè)算法應(yīng)該是（???? ）A．程序???? B．問(wèn)題求解步驟的描述 ???C．要滿足五個(gè)基本特性 ??? D．A和C3．用計(jì)算機(jī)無(wú)法解決“打印所有素?cái)?shù)”的問(wèn)題，其原因是解決該問(wèn)題的算法違背了算法特征中的（ ）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，67C．3，15，20，67，130，98 D．3，15，20，67，98，1305．下列關(guān)于算法的描述，正確的是（ ）A．一個(gè)算法的執(zhí)行步驟可以是無(wú)限的 B．一個(gè)完整的算法必須有輸出C．算法只能用流程圖表示 D．一個(gè)完整的算法至少有一個(gè)輸入6．Java Application源程序的主類(lèi)是指包含有（ ）方法的類(lèi)。

A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法7．找出滿足各位數(shù)字之和等于5的所有三位數(shù)可采用的算法思路是（ ）A．分治法 B．減治法 C．蠻力法 D．變治法8．在編寫(xiě)Java Application程序時(shí)，若需要使用到標(biāo)準(zhǔn)輸入輸出語(yǔ)句，必須在程序的開(kāi)頭寫(xiě)上( )語(yǔ)句A、import java.awt.* ; B、import java.applet.Applet ;C、import java.io.* ; D、import java.awt.Graphics ;9．計(jì)算某球隊(duì)平均年齡的部分算法流程圖如圖所示，其中：c用來(lái)記錄已輸入球員的人數(shù)，sum用來(lái)計(jì)算有效數(shù)據(jù)之和，d用來(lái)存儲(chǔ)從鍵盤(pán)輸入的球員年齡值，輸入0時(shí)表示輸入結(jié)束圖中空白處理框①和②處應(yīng)填入的是（ ）A．① sum ← sum + d B．① sum ← sum + c ② c ← c + 1 ② c ← c + 1C．① sum ← sum + d D．① sum ← sum + c ② d ← d + 1 ② d ← d + 110．報(bào)名參加冬季越野賽跑的某班5位學(xué)生的學(xué)號(hào)是：5，8，11，33，45。

利用折半查找，查找學(xué)號(hào)為33號(hào)學(xué)生的過(guò)程中，依次被訪問(wèn)到的學(xué)號(hào)是（ ）A．5，11，33 B．8，33 C．11，45，33 D．11，3311．表達(dá)式（short）8/9.2*5的值的類(lèi)型為A．short B． int C．double D．float12． 設(shè)x為int型變量，則執(zhí)行一下語(yǔ)句段后，x的值為 x=10;x+=x-=x-x;A．10 B．20 C．40 D．3013．下列代碼的執(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．10abc814． 下列程序段執(zhí)行后t3的結(jié)果是int t1 = 2, t2 = 3, t3;t3=t1

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è)顯而易見(jiàn)的事實(shí)是：大部分算法的執(zhí)行時(shí)間隨著 輸入量的增加 而增大2．算法是 求解某一問(wèn)題所使用的一系列清晰的指令 3．算法分析時(shí)間效率模型的基本數(shù)學(xué)公式是： T(n) ≈ CopC(n) 4．算法設(shè)計(jì)技術(shù)是 用算法解題的一般性方法 ，用于解決不同計(jì)算領(lǐng)域的多種問(wèn)題5．三個(gè)漸進(jìn)符號(hào)： O 、 ? 和 ? 6．效率分析框架主要關(guān)心一個(gè)算法的 基本操作次數(shù)的增長(zhǎng)次數(shù) ，并把它作為算法效率的主要指標(biāo)7．Java源程序的文件名和程序中定義的 主類(lèi)名 應(yīng)保持一致，包括字母大小寫(xiě)的匹配8．算法中常見(jiàn)的問(wèn)題類(lèi)型包括： 排序 、 查找 、字符串處理和組合問(wèn)題等。

9．類(lèi)中的 構(gòu)造 方法是一個(gè)特殊的方法，其名稱(chēng)與類(lèi)名相同10．面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言中的3個(gè)重要特性分別是 封裝 、 繼承 和 多態(tài) 11．Java源程序文件的擴(kuò)展名為 java ，編譯生成的字節(jié)碼文件的擴(kuò)展名為 class 12．大多數(shù)算法的效率可以分為常數(shù)、 對(duì)數(shù) 、線性、平方、 立方 和指數(shù)等三、簡(jiǎn)答題 1．什么是算法？算法的五個(gè)重要特征是什么？答：算法是求解某一問(wèn)題所使用的一系列清晰的指令答：（1）輸入：有零個(gè)或多個(gè)由外部提供的量作為算法的輸入.（2）輸出：算法產(chǎn)生至少一個(gè)量作為輸出.（3）確定性：組成算法的每條指令是清晰的,無(wú)歧義的.（4）有限性：在執(zhí)行了有窮步驟后運(yùn)算終止.（5）可行性：運(yùn)算都是基本運(yùn)算，原理上能在有限時(shí)間內(nèi)完成.2．請(qǐng)簡(jiǎn)述蠻力算法的優(yōu)點(diǎn)？答：蠻力算法是一種簡(jiǎn)單直接地解決問(wèn)題的方法蠻力法具有如下優(yōu)點(diǎn)：(1)應(yīng)用范圍廣；(2)不受實(shí)例規(guī)模的限制；(3)當(dāng)要解決的問(wèn)題實(shí)例不多,設(shè)計(jì)更高效算法的代價(jià)太大時(shí)可選用；(4)對(duì)解決一些小規(guī)模的問(wèn)題實(shí)例仍然有效；(5)可作為衡量其他算法的參照物3．算法設(shè)計(jì)與分析過(guò)程的典型步驟都包括哪些？答： （1）了解問(wèn)題的內(nèi)容 （2）了解計(jì)算設(shè)備的性能 （3）在精確解法和近似解法之間選擇 （4）確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu) （5）算法設(shè)計(jì)技術(shù) （6）詳細(xì)表述算法的方法 （7）證明算法的正確性 （8）分析算法 （9）為算法寫(xiě)代碼4．請(qǐng)簡(jiǎn)述分治法的基本思路？答：將規(guī)模為N的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，使這些子問(wèn)題相互獨(dú)立可分別求解，再將k個(gè)子問(wèn)題的解合并成原問(wèn)題的解。

如子問(wèn)題的規(guī)模仍很大，則反復(fù)分解直到問(wèn)題小到可直接求解為止在分治法中,子問(wèn)題的解法通常與原問(wèn)題相同,自然導(dǎo)致遞歸過(guò)程5．請(qǐng)簡(jiǎn)述減治法的基本思路？答：減治技術(shù)利用了一個(gè)問(wèn)題給定實(shí)例的解和同樣問(wèn)題較小實(shí)例的解之間的某種關(guān)系一旦建立了這種關(guān)系，既可以從頂至底（遞歸地），也可以從底至頂（非遞歸地）來(lái)運(yùn)用該關(guān)系減治法有三種主要的變種：n 減常數(shù)(如1)：:每此迭代規(guī)模減小n→n-1n 減因子(如1/2)：每此迭代規(guī)模減半n→ n/2n 減可變規(guī)模：每此迭代減小的規(guī)模不同6．請(qǐng)簡(jiǎn)述遞歸算法設(shè)計(jì)的基本思路？答：遞歸的執(zhí)行過(guò)程由分解過(guò)程和求值過(guò)程兩部分構(gòu)成實(shí)際上, 遞歸思路是把一個(gè)不能或不好直接求解的“大問(wèn)題”轉(zhuǎn)化成一個(gè)或幾個(gè)“小問(wèn)題”來(lái)解決，再把這些“小問(wèn)題”進(jìn)一步分解成更小的“小問(wèn)題”來(lái)解決，如此分解，直至每個(gè)“小問(wèn)題”都可以直接解決(此時(shí)分解到遞歸出口) 但遞歸分解不是隨意的分解，遞歸分解要保證“大問(wèn)題”與“小問(wèn)題”相似，即求解過(guò)程與環(huán)境都相似并且有一個(gè)分解的終點(diǎn)從而使問(wèn)題可解 7．請(qǐng)簡(jiǎn)述變治法的基本思路？答：變治法的技術(shù)基于變換思想變治法分為兩個(gè)階段的工作：首先在“變”的階段，出于這樣或那樣的原因，將問(wèn)題的實(shí)例變得更容易求解；然后是“治”的階段，對(duì)問(wèn)題的實(shí)例進(jìn)行求解。

根據(jù)對(duì)問(wèn)題實(shí)例的變換方式不同，變治法有三種主要的類(lèi)型： （1）實(shí)例化簡(jiǎn)——變換為同樣問(wèn)題的一個(gè)更簡(jiǎn)單或者更方便的實(shí)例； （2）改變表現(xiàn)——變換為同樣實(shí)力的不同表現(xiàn)； （3）問(wèn)題化簡(jiǎn)——變換為另一個(gè)問(wèn)題的實(shí)例，這種問(wèn)題的算法是已知的8．請(qǐng)簡(jiǎn)述時(shí)空權(quán)衡法的基本思路？答：時(shí)空權(quán)衡法的基本思路是對(duì)問(wèn)題的部分或全部輸入做預(yù)處理，然后對(duì)得到的額外信息使用額外的存儲(chǔ)空間來(lái)存儲(chǔ)通過(guò)實(shí)現(xiàn)更快或更方便的數(shù)據(jù)存取，以加速后面問(wèn)題的求解來(lái)提高算法的效率四、算法實(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?。篎(n) = F(n-1) × n請(qǐng)編寫(xiě)Java應(yīng)用程序，由鍵盤(pán)輸入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è)初始條件來(lái)定義：當(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)編寫(xiě)Java應(yīng)用程序，由鍵盤(pán)輸入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．編寫(xiě)基于Java語(yǔ)言的選擇排序算法。

/**** 功能：該算法用選擇排序?qū)o定的數(shù)組排序* 輸入：一個(gè)亂序的整數(shù)數(shù)組a[ ]* 輸出：升序排列的整數(shù)數(shù)組a[ ]***/public void selectionSort (int a[ ]){ int temp,min; for(int i=0;i a[j]) min = j; temp = a[i]; a[i] = a[min]; a[min] = temp; }}4．編寫(xiě)基于Java語(yǔ)言的冒泡排序算法/**** 功能：該算法用冒泡排序?qū)o定的數(shù)組排序* 輸入：一個(gè)亂序的整數(shù)數(shù)組a[ ]* 輸出：升序排列的整數(shù)數(shù)組a[ ]***/public void bubbleSort(int a[ ]){ int temp; for(int i=0;ia[j+1]) { temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; }}5．編寫(xiě)基于Java語(yǔ)言的順序查找算法。

/**** 功能：該算法實(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．編寫(xiě)基于Java語(yǔ)言的折半查找算法/**** 功能：該算法實(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．編寫(xiě)基于Java語(yǔ)言的字符串匹配算法。

/**** 功能：該算法實(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．編寫(xiě)基于Java語(yǔ)言的直接插入排序算法/**** 功能：該算法用直接插入排序?qū)o定的數(shù)組排序* 輸入：一個(gè)亂序的整數(shù)數(shù)組a[ ]* 輸出：升序排列的整數(shù)數(shù)組a[ ]***/public void insertSort (int a[ ]){ int temp,i,j; for(i=1;i=0 && a[j]>=temp) { a[j+1]=a[j]; j--; } a[j+1]=temp; }}9 / 9。