8、
第二趟：2，5，16，88，12，10
第三趟：2，5，10，88，12，16
則采用的排序方法是（ ）
A．冒泡排序 B．合并排序 C．快速排序 D．選擇排序
17．類與對象的關(guān)系是（ ）
A． 建筑圖紙和建筑物的關(guān)系 B． 汽車與發(fā)動機的關(guān)系
C． 人與黑人的關(guān)系 D． 沒有關(guān)系
18．JAVA語言二維數(shù)組定義中，第二維的長度 ( )
A．可以不相等 B．必須相等
C．高維數(shù)組長度與低維數(shù)組長度相同 D．固定長度
19．算法必須具備（
9、 ）這三個特性。
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．算法是 求
10、解某一問題所使用的一系列清晰的指令 。
3．算法分析時間效率模型的基本數(shù)學(xué)公式是： T(n) ≈ CopC(n) 。
4．算法設(shè)計技術(shù)是 用算法解題的一般性方法 ，用于解決不同計算領(lǐng)域的多種問題。
5．三個漸進符號： O 、 ? 和 ? 。
6．效率分析框架主要關(guān)心一個算法的 基本操作次數(shù)的增長次數(shù) ，并把它作為算法效率的主要指標。
7．Java源程序的文件名和程序中定義的 主類名 應(yīng)保持一致，包括字母大小寫的匹配。
8．算法中常見的問題類型包括： 排序 、 查找 、字符串處理和組合問題等。
9．類中的 構(gòu)造 方法是一
11、個特殊的方法，其名稱與類名相同。
10．面向?qū)ο蟪绦蛟O(shè)計語言中的3個重要特性分別是 封裝 、 繼承 和 多態(tài) 。
11．Java源程序文件的擴展名為 java ，編譯生成的字節(jié)碼文件的擴展名為 class 。
12．大多數(shù)算法的效率可以分為常數(shù)、 對數(shù) 、線性、平方、 立方 和指數(shù)等。
三、簡答題
1．什么是算法？算法的五個重要特征是什么？
答：算法是求解某一問題所使用的一系列清晰的指令。
答：
（1）輸入：有零個或多個由外部提供的量作為算法的輸入.
（2）輸出：算法產(chǎn)生至少一個量作為輸出.
（3）確定性：組成算法的每條指令是清晰的,無歧義的.
12、
（4）有限性：在執(zhí)行了有窮步驟后運算終止.
（5）可行性：運算都是基本運算，原理上能在有限時間內(nèi)完成.
2．請簡述蠻力算法的優(yōu)點？
答：
蠻力算法是一種簡單直接地解決問題的方法。蠻力法具有如下優(yōu)點：(1)應(yīng)用范圍廣；(2)不受實例規(guī)模的限制；(3)當要解決的問題實例不多,設(shè)計更高效算法的代價太大時可選用；(4)對解決一些小規(guī)模的問題實例仍然有效；(5)可作為衡量其他算法的參照物。
3．算法設(shè)計與分析過程的典型步驟都包括哪些？
答：
（1）了解問題的內(nèi)容
（2）了解計算設(shè)備的性能
（3）在精確解法和近似解法之間選擇
（4）確定適當?shù)?/p>
13、數(shù)據(jù)結(jié)構(gòu)
（5）算法設(shè)計技術(shù)
（6）詳細表述算法的方法
（7）證明算法的正確性
（8）分析算法
（9）為算法寫代碼
4．請簡述分治法的基本思路？
答：
將規(guī)模為N的問題分解為k個規(guī)模較小的子問題，使這些子問題相互獨立可分別求解，再將k個子問題的解合并成原問題的解。如子問題的規(guī)模仍很大，則反復(fù)分解直到問題小到可直接求解為止。
在分治法中,子問題的解法通常與原問題相同,自然導(dǎo)致遞歸過程。
5．請簡述減治法的基本思路？
答：
減治技術(shù)利用了一個問題給定實例的解和同樣問題較小實例的解之間的某種關(guān)系。一旦建立了這種關(guān)系，既可以從頂至
14、底（遞歸地），也可以從底至頂（非遞歸地）來運用該關(guān)系。
減治法有三種主要的變種：
n 減常數(shù)(如1)：:每此迭代規(guī)模減小n→n-1
n 減因子(如1/2)：每此迭代規(guī)模減半n→ n/2
n 減可變規(guī)模：每此迭代減小的規(guī)模不同
6．請簡述遞歸算法設(shè)計的基本思路？
答：
遞歸的執(zhí)行過程由分解過程和求值過程兩部分構(gòu)成。
實際上, 遞歸思路是把一個不能或不好直接求解的“大問題”轉(zhuǎn)化成一個或幾個“小問題”來解決，再把這些“小問題”進一步分解成更小的“小問題”來解決，如此分解，直至每個“小問題”都可以直接解決(此時分解到遞歸出口)。
但遞歸分解不是隨意的分解，遞歸分解要保證“大
15、問題”與“小問題”相似，即求解過程與環(huán)境都相似。并且有一個分解的終點。從而使問題可解。
7．請簡述變治法的基本思路？
答：
變治法的技術(shù)基于變換思想。變治法分為兩個階段的工作：首先在“變”的階段，出于這樣或那樣的原因，將問題的實例變得更容易求解；然后是“治”的階段，對問題的實例進行求解。
根據(jù)對問題實例的變換方式不同，變治法有三種主要的類型：
（1）實例化簡——變換為同樣問題的一個更簡單或者更方便的實例；
（2）改變表現(xiàn)——變換為同樣實力的不同表現(xiàn)；
（3）問題化簡——變換為另一個問題的實例，這種問題的算法是已知的。
8．請簡述時空權(quán)衡法的基本思路
16、？
答：
時空權(quán)衡法的基本思路是對問題的部分或全部輸入做預(yù)處理，然后對得到的額外信息使用額外的存儲空間來存儲。通過實現(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應(yīng)用程序，由鍵盤輸入n的值，在屏幕上輸出計算的n！的結(jié)果。
import java.io.*;
public class FN
17、
{
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);
in
18、t 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應(yīng)用程序，由鍵盤輸入n的值代表要生成斐波那契數(shù)列的項數(shù)，在屏幕上輸出n項斐波
19、那契數(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];
Syste
20、m.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．編寫基于Ja
21、va語言的選擇排序算法。
/***
* 功能：該算法用選擇排序?qū)o定的數(shù)組排序
* 輸入：一個亂序的整數(shù)數(shù)組a[ ]
* 輸出：升序排列的整數(shù)數(shù)組a[ ]
***/
public void selectionSort (int a[ ])
{
int temp,min;
for(int i=0;i a[j])
22、 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;i
23、=0;ja[j+1])
{
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
5．編寫基于Java語言的順序查找算法。
/***
* 功能：該算法實現(xiàn)順序查找功能
* 輸入：一個整數(shù)數(shù)組a[ ]和一個要查找的鍵值k
* 輸出：如果在數(shù)組中找到k，則返回對應(yīng)數(shù)組元素的下標；如果在數(shù)組中找不到k，則返回-1
***/
public int seqSearch(int a[ ],int k)
{
int i =
24、 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，則返回對應(yīng)數(shù)組元素的下標；如果在數(shù)組中找不到k，則返回-1
***/
public int binarySearch(int a[ ], int k
25、)
{
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
26、．編寫基于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++)
27、 {
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
《算法分析與設(shè)計》期末復(fù)習(xí)題
