几个算法测试题及答案

1、编程：编写一个截取字符串的函数，输入为一个字符串和字节数，输出为按字节截取的字符串。 但是要保证汉字不被截半个，如“我ABC”4，应该截为“我AB”，输入“我ABC汉DEF”，6，应该输出为“我ABC”而不是“我ABC+汉的半个”。
答：代码如下：
package test;

class SplitString
{
String SplitStr;
int SplitByte;
public SplitString(String str,int bytes)
{
SplitStr=str;
SplitByte=bytes;
System.out.println("The String is:′"+SplitStr+"′;SplitBytes="+SplitByte);
}
public void SplitIt()
{
int loopCount;

loopCount=(SplitStr.length()%SplitByte==0)?(SplitStr.length()/SplitByte):(SplitStr.length()/Split

Byte+1);
System.out.println("Will Split into "+loopCount);
for (int i=1;i<=loopCount ;i++ )
{
if (i==loopCount){


System.out.println(SplitStr.substring((i-1)*SplitByte,SplitStr.length()));
} else {

System.out.println(SplitStr.substring((i-1)*SplitByte,(i*SplitByte)));
}
}
}
public static void main(String[] args)
{
SplitString ss = new SplitString("test中dd文dsaf中男大3443n中国43中国人


0ewldfls=103",4);
ss.SplitIt();
}

}

2、求两个数的最大公约数

解答：
欧几理德原理:辗转相除法
public static int zdgys(int a,int b){
int x = a%b;
if(x==0) return b;
else return zdgys(b,x);

}

3、有一个1001个元素的数组a[n]，每个元素都在1到1000这些整数中取值，其中有一个数值重复了，现在要设计一个算法找出这个数字，且每个元素只能被访问一次。不能用辅助的存储容器。

4、冒泡排序算法
解答：
package parent.career.blest;


/**
* 冒泡排序算法演示:从小到大排列数组元素
* 原理：第一个元素和后面的一个元素比较，比较结果再和后面一个元素比较，依次类推
* 接着，第二个和后面元素比较，依次类推
*/
public class Maopao{
public static int[] mppx(int[] array){
for(int i =0;i<array.length; i++){
for(int j=i; j<array.length; j++){
int temp;
if(array[i]>array[j]){
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
return array;
}
public static void main(String args[]){
//测试
int[] ar ={12,23,1,23,45,11,42,9,45,2,16,77,86,56,43};
ar = mppx(ar);
for(int i = 0;i<ar.length;i++){
System.out.print(ar[i]+" ");
}
}

}

5、从键盘接收一个整数，并用递归求其阶乘。
解答：
package parent.career.blest;
import java.io.*;
/**
* 用递归求阶乘算法
* 从键盘接收一个整数，然后求其阶乘
*/
public class DG_JC{
public static int DG(int n){
if(n==1) return 1;
else return n*DG(n-1);
}
public static void main(String args[]){
int n = 0;
System.out.print("请输入一个整数：");
try{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
br.close();
}catch(IOException e){
e.printStackTrace();
}
System.out.println("阶乘"+n+"! = "+DG(n));
}

}

6、写出下列算法的时间复杂度。
(1)冒泡排序 O(n*n)
(2)选择排序 O(n*n)
(3)插入排序 O(n*n)
(4)快速排序 O(n*log n)
(5)堆排序 O(n*log n)
(6)归并排序 O(n*log n)