Java面试之数据结构& 算法& 计算机基础

迷南。 2021-12-17 13:05 257阅读 0赞

### 1、一个byte 几个单位？【基础】 ###

答：8bit。

### 2、常用UNIX 命令(Linux 的常用命令)（至少10 个）【基础】 ###

答：ls pwd mkdir rm cp mv cd ps ftp telnet ping env more echo

### 3、后序遍历下列二叉树，访问结点的顺序是？【基础】 ###

A
    / \
    B C
    / \ \
    D E F
    / / \
    G N I
    / \
    J K

答：顺序为：DJGEBKNIFCA 。

### 4、排序都有哪几种方法？请列举。用JAVA 实现一个快速排序。【基础】 ###

答：排序的方法有：插入排序（直接插入排序、希尔排序），交换排序（冒泡排序、快速排序），选择排序（直接选择排序、堆排序），归并排序，分配排序（箱排序、基数排序）；快速排序的伪代码：  
//使用快速排序方法对a\[ 0 :n- 1 \]排序  
从a\[ 0 :n- 1 \]中选择一个元素作为middle，该元素为支点；  
把余下的元素分割为两段left 和right，使得left 中的元素都小于等于支点，  
而right 中的元素都大于等于支点；  
递归地使用快速排序方法对left 进行排序；  
递归地使用快速排序方法对right 进行排序；  
所得结果为left + middle + right。

### 5、写一种常见排序。【基础】 ###

答：C++中冒泡排序：

void swap( int& a, int& b ){
    int c=a; a = b; b = c;
    }
    void bubble( int* p, int len ){
    bool bSwapped;
    do {
    bSwapped = false;
    for( int i=1; i<len; i++ ){
    if( p[i-1]>p[i] ){
    swap( p[i-1], p[i] );
    bSwapped = true;
    }
    }
    }while( bSwapped );
    }

### 6、写一个一小段程序检查数字是否为质数；以上的程序你采用的哪种语言写的？采用该种语言的理由是什么？【基础】 ###

答：代码如下：

#include <math.h>
    bool prime( int n ){
    if(n<=0) exit(0);
    for( int i=2; i<=n; i++ )
    for( int j=2; j<=sqrt(i); j++)
    if((n%j==0) && (j!=n))
    return false;
    return true;
    }

采用C++，因为其运行效率高。

### 7、编程题：设有ｎ个人依围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为1，2，…，n，打印出出列的顺序；要求用java 实现。【中等难度】 ###

答：代码如下：

package test;
    public class CountGame {
    private static boolean same(int[] p,int l,int n){
    for(int i=0;i<l;i++){
    if(p[i]==n){
    return true;
    }
    }
    return false;
    }
    public static void play(int playerNum, int step){
    int[] p=new int[playerNum];
    int counter = 1;
    while(true){
    if(counter > playerNum*step){
    break;
    }
    for(int i=1;i<playerNum+1;i++){
    while(true){
    if(same(p,playerNum,i)==false) break;
    else i=i+1;
    }
    if(i > playerNum)break;
    if(counter%step==0){
    System.out.print(i + " ");
    p[counter/step-1]=i;
    }
    counter+=1;
    }
    }
    System.out.println();
    }
    public static void main(String[] args) {
    play(10, 7);
    }
    }

### 8、写一个方法1000 的阶乘。【较难】 ###

答：C++的代码实现如下：

#include <iostream>
    #include <iomanip>
    #include <vector>
    using namespace std;
    class longint {
    private:
    vector<int> iv;
    public:
    longint(void) { iv.push_back(1); }
    longint& multiply(const int &);
    friend ostream& operator<<(ostream &, const longint &);
    };
    ostream& operator<<(ostream &os, const longint &v) {
    vector<int>::const_reverse_iterator iv_iter = v.iv.rbegin();
    os << *iv_iter++;
    for ( ; iv_iter < v.iv.rend(); ++iv_iter) {
    os << setfill('0') << setw(4) << *iv_iter;
    }
    return os;
    }
    longint& longint::multiply(const int &rv) {
    vector<int>::iterator iv_iter = iv.begin();
    int overflow = 0, product = 0;
    for ( ; iv_iter < iv.end(); ++iv_iter) {
    product = (*iv_iter) * rv;
    product += overflow;
    overflow = 0;
    if (product > 10000) {
    overflow = product / 10000;
    product -= overflow * 10000;
    }
    iv_iter = product;
    }
    if (0 != overflow) {
    iv.push_back(overflow);
    }
    return *this;
    }
    int main(int argc, char **argv) {
    longint result;
    int l = 0;
    if(argc==1){
    cout << "like: multiply 1000" << endl;
    exit(0);
    }
    sscanf(argv[1], "%d", &l);
    for (int i = 2; i <= l; ++i) {
    result.multiply(i);
    }
    cout << result << endl;
    return 0;
    }