8、
第二趟：2，5，16，88，12，10
第三趟：2，5，10，88，12，16
則采用的排序方法是（ ）
A．冒泡排序 B．合并排序 C．快速排序 D．選擇排序
17．類(lèi)與對(duì)象的關(guān)系是（ ）
A． 建筑圖紙和建筑物的關(guān)系 B． 汽車(chē)與發(fā)動(dòng)機(jī)的關(guān)系
C． 人與黑人的關(guān)系 D． 沒(méi)有關(guān)系
18．JAVA語(yǔ)言二維數(shù)組定義中，第二維的長(zhǎng)度 ( )
A．可以不相等 B．必須相等
C．高維數(shù)組長(zhǎng)度與低維數(shù)組長(zhǎng)度相同 D．固定長(zhǎng)度
19．算法必須具備（
9、 ）這三個(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è)顯而易見(jiàn)的事實(shí)是：大部分算法的執(zhí)行時(shí)間隨著 輸入量的增加 而增大。
2．算法是 求
10、解某一問(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)造 方法是一
11、個(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ú)歧義的.
12、
（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ù)?/p>
13、數(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)系，既可以從頂至
14、底（遞歸地），也可以從底至頂（非遞歸地）來(lái)運(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í)行過(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í)分解到遞歸出口)。
但遞歸分解不是隨意的分解，遞歸分解要保證“大
15、問(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)衡法的基本思路
16、？
答：
時(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
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("請(qǐng)輸入一個(gè)整數(shù)：");
System.in.read(buf);
String str=new String(buf);
in
18、t 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)斐波
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("請(qǐng)輸入所求斐波那契數(shù)列的項(xiàng)數(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 + "項(xiàng)的斐波那契數(shù)列：");
for(int i = 0; i <= n; i++)
{
b = f1.f(i);
System.out.print(b + " ");
}
System.out.println();
}
}
3．編寫(xiě)基于Ja
21、va語(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])
22、 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;i
23、=0;ja[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 =
24、 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
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、．編寫(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++)
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．編寫(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
《算法分析與設(shè)計(jì)》期末復(fù)習(xí)題
