最新消息:三苏博客专业为广大站长朋友提供网站源码

工程师面试题目

Linux 三苏 149浏览 0评论

1,反转二叉树

BiTree ReversedBiTree(BiTree root)
{
if (root == null) {
return null;
}
root->left = ReversedTree(root->left);
root->right = ReversedTree(root->right);

BiTree tmp = root->left;
root->left = root->right;
root->right = tmp;
return root;
}

 

2,从一个字符串中找出出现频率最高的字符

int[] x = new int[26];
char[] ca = str.toCharArray();
for(int i=0;i <ca.length;i++){
x[ca[i]-‘a’]++;
}
for(int i=0;i <ca.length;i++){
System.out.println(“字符”+(char)(‘a’+i)+”出现了”+ca[i]+”次”);
}

3,快速排序

快速排序选择基准的三种方法:

  • 1,选第一个;
  • 2,随机选
  • 3,选择1,nn/2 的平均数

四种优化方法:

  • 优化1:当待排序序列的长度分割到一定大小后,使用插入排序(对于小规模部分有序的数组,快排不如插排好)
  • 优化2:在一次分割结束后,可以把与Key相等的元素聚在一起,继续下次分割时,不用再对与key相等元素分割
  • 优化3:优化递归操作,使用为递归进行优化
  • 优化4:使用并行或多线程处理子序列

void quicksort(int arr[],int left,int right)
{
int i,j,t,temp;
if(left>=right)
return;
temp=a[left]; //temp中存的就是基准数
i=left;
j=right;
while(i!=j)
{
while(a[j]>=temp && i<j) //顺序很重要,要先从右边开始找
j–;
while(a[i]<=temp && i<j) //再找右边的
i++;
if(i<j) //交换两个数在数组中的位置
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[left]=a[i]; //最终将基准数归位
a[i]=temp;
quicksort(arr,left,i-1);//继续处理左边的,这里是一个递归的过程
quicksort(arr,i+1,right);//继续处理右边的 ,这里是一个递归的过程

4,二分查找

int BinSearch(int arr[],int low,int high,int num)
{
while(low<=high)
{
int mid=(low+high)/2;
if(num==arr[mid]) return mid;
else if(num < arr[mid]) high=mid-1;
else low=mid+1;
}
return -1;
}

5,希尔排序

void shellsort2(int a[], int n)
{
int j, gap;

for (gap = n / 2; gap > 0; gap /= 2)
for (j = gap; j < n; j++)//从数组第gap个元素开始
if (a[j] < a[j – gap])//每个元素与自己组内的数据进行直接插入排序
{
int temp = a[j];
int k = j – gap;
while (k >= 0 && a[k] > temp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = temp;
}
}

6,冒泡排序(在某趟冒泡排序过程中,若没有发现一个逆序对,就可以直接结束整个排序过程)

void bubble_sort(int arr[],int n)
{
int flag=1;
for(int i=0;i<n && flag;i++)
{
flag=0;
for(int j=0;j<n-i;j++)
if(a[j]>a[j+1])
{
int tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
flag=1;
}
}
}

7,选择排序

void select_sort(int arr[],int n)
{
for(int i=0;i<n;i++)
{
int k=i;
for(int j=i+1;j<n;j++)
if(a[j]<a[k])
k=j;
if(k!=i)
{
int tmp=a[i];
a[i]=a[k];
a[k]=tmp;
}
}
}

8,插入排序

void insert_sort(int arr[],int n)
{
for(int i=2;i<n;i++)
{
if(a[i]<a[i-1])
{
a[0]=a[i];
for(int j=i;a[0]<a[j];j–)
a[j+1]=a[j]; //记录后移
a[j+1]=a[0]; //插入到正确的位置
}
}
}

9,木桶排序

#include <stdio.h>
int main()
{
int a[11],i,j,t;
for(i=0;i<=10;i++)
a[i]=0; //初始化为0

for(i=1;i<=5;i++) //循环读入5个数
{
scanf(“%d”,&t); //把每一个数读到变量t中
a[t]++; //进行计数
}

for(i=0;i<=10;i++) //依次判断a[0]~a[10]
for(j=1;j<=a[i];j++) //出现了几次就打印几次
printf(“%d “,i);
}

10,实现一个逆转函数

#!/usr/bin/env python
# coding=utf-8

 

string_reversed = lambda x:x[::-1]

if __name__ == ‘__main__’:
s = ‘abcde’
print string_reversed(s)

转载请注明:三苏博客 » 工程师面试题目

发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址