嵌入式笔试面试题(6)---排序及查找

时间:2021-05-16 19:40:20

1、就排序算法所用的辅助空间而言,堆排序,快速排序,归并排序的关系是 

A.堆排序〈快速排序〈归并排序   B.堆排序〈 归并排序〈 快速排序

C.堆排序〉归并排序〉快速排序    D.堆排序 >  快速排序 > 归并排序

 E.以上答案都不对  

 

2、编程题二分法(折半查找算法)

#include<stdio.h>

//int find(int aim,int data[],int size);

 

int main(int argc, const char *argv[])

{

    int a[]={1,2,3,4};

    int aim=2;

    int n=find(aim,a,4);

    printf("%d\n",n);

 

    return 0;

}

 

int find(int aim,int data[],int size)

{

    int ret =-1;

    int left=0;

    int right=size-1;

 

    while(left<=right)

    {

       int mid=(left+right)/2;

       if(aim<data[mid])

       {

              right=mid-1;

       }else if(aim>data[mid])

       {

              left=mid+1;

       }else

       {

              ret=mid;

              return ret;

              

       }

    }

    printf("--------------------\n");

    return ret;

}

3、简述冒泡排序的思想:

将下列数据进行冒泡排序的进行从小到大排序,并写出每次排序后的结果: 1 5 4 8 11 2 6 9 3

#include <stdio.h>

int main(int argc, const char *argv[])

{

    int a[]={1,5,3,6,2};

 

    int i=0,j=0;

    int n=sizeof(a)/sizeof(a[0]);

    int t=0;

    for(i=0;i<n-1;i++)

    {

       for(j=0;j<n-1-i;j++)

       {

          if(a[j]>a[j+1])

          {

              t=a[j+1];

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

              a[j]=t;

          }

       }

    }

 

    for(i=0;i<n;i++)

    {

        printf("%d ",a[i]);

    }

    return 0;

}

 

 

4、下面哪种排序法对123456798在空间和时间上最优

A. 快速排序 B. 冒泡排序

C. 插入排序 D. 堆排序