《算法分析與設計》期末復習題

真誠為您提供優(yōu)質(zhì)參考資料，若有不當之處，請指正一、選擇題1．一個.java文件中可以有（ ）個public類A．一個 B．兩個 C．多個 D．零個2．一個算法應該是（???? ）A．程序???? B．問題求解步驟的描述 ???C．要滿足五個基本特性 ??? D．A和C3．用計算機無法解決“打印所有素數(shù)”的問題，其原因是解決該問題的算法違背了算法特征中的（ ）A．唯一性 B．有窮性 C．有0個或多個輸入 D．有輸出4．某校有6位學生參加學生會主席競選，得票數(shù)依次為130，20，98，15，67，3若采用冒泡排序算法對其進行排序，則完成第二遍時的結(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．一個算法的執(zhí)行步驟可以是無限的 B．一個完整的算法必須有輸出C．算法只能用流程圖表示 D．一個完整的算法至少有一個輸入6．Java Application源程序的主類是指包含有（ ）方法的類。

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

利用折半查找，查找學號為33號學生的過程中，依次被訪問到的學號是（ ）A．5，11，33 B．8，33 C．11，45，33 D．11，3311．表達式（short）8/9.2*5的值的類型為A．short B． int C．double D．float12． 設x為int型變量，則執(zhí)行一下語句段后，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í)行性、可移植性、可擴充性 B．可執(zhí)行性、確定性、有窮性C．確定性、有窮性、穩(wěn)定性 D．易讀性、穩(wěn)定性、安全性20．如下圖所示，該流程圖所表示的算法違背了算法的有窮性特征，下列修改方法中，可以改正該錯誤的是（ ）A．將①處改為 i ← 0 B．將②處改為 s ≥ 0 ?C．將③處改為 i ← i-2 D．將④處改為 s ← s-i二、填空題 1．一個顯而易見的事實是：大部分算法的執(zhí)行時間隨著 輸入量的增加 而增大2．算法是 求解某一問題所使用的一系列清晰的指令 3．算法分析時間效率模型的基本數(shù)學公式是： T(n) ≈ CopC(n) 4．算法設計技術(shù)是 用算法解題的一般性方法 ，用于解決不同計算領(lǐng)域的多種問題5．三個漸進符號： O 、 ? 和 ? 6．效率分析框架主要關(guān)心一個算法的 基本操作次數(shù)的增長次數(shù) ，并把它作為算法效率的主要指標7．Java源程序的文件名和程序中定義的 主類名 應保持一致，包括字母大小寫的匹配8．算法中常見的問題類型包括： 排序 、 查找 、字符串處理和組合問題等。

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

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

根據(jù)對問題實例的變換方式不同，變治法有三種主要的類型： （1）實例化簡——變換為同樣問題的一個更簡單或者更方便的實例； （2）改變表現(xiàn)——變換為同樣實力的不同表現(xiàn)； （3）問題化簡——變換為另一個問題的實例，這種問題的算法是已知的8．請簡述時空權(quán)衡法的基本思路？答：時空權(quán)衡法的基本思路是對問題的部分或全部輸入做預處理，然后對得到的額外信息使用額外的存儲空間來存儲通過實現(xiàn)更快或更方便的數(shù)據(jù)存取，以加速后面問題的求解來提高算法的效率四、算法實現(xiàn)題1．對于任意非負整數(shù)n，計算階乘函數(shù)F(n) = n！的值因為當n ≥ 1時，n！= 1×2×3×……×（n-1）×n = (n-1)！×n并且根據(jù)定義，0！= 1，所以可以使用下面的遞歸算法計算n?。篎(n) = F(n-1) × n請編寫Java應用程序，由鍵盤輸入n的值，在屏幕上輸出計算的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("請輸入一個整數(shù)："); System.in.read(buf); String str=new String(buf); int n=Integer.parseInt(str.trim()); //計算N！的值 long result = f(n); //輸出結(jié)果 System.out.println(n + "!=" + result); }}2．斐波那契數(shù)列：0，1，1，2，3，5，8，13，21，34，……這個數(shù)列可以用一個簡單的遞推式和兩個初始條件來定義：當n > 1時，F(xiàn)(n) = F(n-1) + F(n-2) F(0) = 0，F(xiàn)(1) = 1請編寫Java應用程序，由鍵盤輸入n的值代表要生成斐波那契數(shù)列的項數(shù)，在屏幕上輸出n項斐波那契數(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("請輸入所求斐波那契數(shù)列的項數(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 + "項的斐波那契數(shù)列："); for(int i = 0; i <= n; i++) { b = f1.f(i); System.out.print(b + " "); } System.out.println(); }}3．編寫基于Java語言的選擇排序算法。

/**** 功能：該算法用選擇排序?qū)o定的數(shù)組排序* 輸入：一個亂序的整數(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．編寫基于Java語言的冒泡排序算法/**** 功能：該算法用冒泡排序?qū)o定的數(shù)組排序* 輸入：一個亂序的整數(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．編寫基于Java語言的順序查找算法。

/**** 功能：該算法實現(xiàn)順序查找功能* 輸入：一個整數(shù)數(shù)組a[ ]和一個要查找的鍵值k* 輸出：如果在數(shù)組中找到k，則返回對應數(shù)組元素的下標；如果在數(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語言的折半查找算法/**** 功能：該算法實現(xiàn)折半查找功能* 輸入：一個已經(jīng)按照升序排列好的整數(shù)數(shù)組a[ ]和一個要查找的鍵值k* 輸出：如果在數(shù)組中找到k，則返回對應數(shù)組元素的下標；如果在數(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語言的字符串匹配算法。

/**** 功能：該算法實現(xiàn)字符串匹配功能* 輸入：一個n個字符的字符串str代表一段文本 一個m個字符的字符串key代表一個模式* 輸出：如果查找成功的話，返回文本的第一個匹配字符串中第一個字符的位置，否則返回-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ù)組排序* 輸入：一個亂序的整數(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。