《算法分析与设计》期末复习题

.

6．编写基于Java语言的折半查找算法。 /***

* 功能：该算法实现折半查找功能

* 输入：一个已经按照升序排列好的整数数组a[ ]和一个要查找的键值k

* 输出：如果在数组中找到k，则返回对应数组元素的下标；如果在数组中找不到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]) else

return mid;

if(des < a[mid]) upper = mid - 1; else

low = mid + 1;

} return -1;

7．编写基于Java语言的字符串匹配算法。 /***

* 功能：该算法实现字符串匹配功能

* 输入：一个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++) { } return -1;

j = 0;

while((j < m) && (key.charAt(j) == str.charAt(i+j))) { }

j = j + 1;

System.out.println(i + \if(j == m)

return i;

8．编写基于Java语言的直接插入排序算法。 /***

* 功能：该算法用直接插入排序对给定的数组排序 * 输入：一个乱序的整数数组a[ ] * 输出：升序排列的整数数组a[ ] ***/

public void insertSort (int a[ ]) {

int temp,i,j; }

for(i=1;i

temp=a[i]; j=i-1;

while(j>=0 && a[j]>=temp) { }

a[j+1]=temp;

a[j+1]=a[j]; j--;

.