---恢复内容开始---

一、单项选择题

1、从n个未排序的数中寻找中位数（第[n/2]大的数），平均时间复杂度最优算法的复杂为：

A.O(logn)    B.O(n)    C.O(nlogn)    D.O(n^2)

分析：求无序数组的中位数中位数即是排过序后的处于数组最中间的元素。 不考虑数组长度为偶数的情况。设集合元素个数为n。简单的想了下：思路1） 把无序数组排好序，取出中间的元素            时间复杂度 采用普通的比较排序法 O(N*logN)            如果采用非比较的计数排序等方法， 时间复杂度 O(N), 空间复杂度也是O(N).思路2）           2.1）将前(n+1)/2个元素调整为一个小顶堆，          2.2）对后续的每一个元素，和堆顶比较，如果小于等于堆顶，丢弃之，取下一个元素。 如果大于堆顶，用该元素取代堆顶，调整堆，取下一元素。重复2.2步                     2.3）  当遍历完所有元素之后，堆顶即是中位数。思路3） 熟话说，想让算法跑的更快，用分治！            快速排序之所以得名"快排",绝非浪得虚名！因为快排就是一种分治排序法！            同样，找中位数也可以用快排分治的思想。具体如下：            任意挑一个元素，以改元素为支点，划分集合为两部分，如果左侧集合长度恰为 (n-1)/2，那么支点恰为中位数。如果左侧长度<(n-1)/2, 那么中位点在右侧，反之，中位数在左侧。 进入相应的一侧继续寻找中位点。            这种方法很快，但是在最坏的情况下时间复杂度为O(N^2), 不过平均时间复杂度好像是O(N)。引申一：查找N个元素中的第K个小的元素（来自编程珠玑）编程珠玑给出了一个时间复杂度O（N），的解决方案。该方案改编自快速排序。经过快排的一次划分，   1）如果左半部份的长度>K-1，那么这个元素就肯定在左半部份了   2）如果左半部份的长度==K-1，那么当前划分元素就是结果了。   3）如果。。。。。。。

2、普通PC机器上四字节有符号整数能表示的最小数是多少?

-2^31

 

3、根据程序，写输出？

#include
     
      using namespace std;void foobar(int a,int *b,int **c){    int *p=&a;    *p=101;    *c=b;    b=p;}int main(){    int a=1,b=2,c=3;    int *p=&c;    foobar(a,&b,&p);    cout<
      <<" "<<<" "<
        
         <<" "<<*p<
        
     

分析：输出1 2 3 2

4、从{1,2,3,...20}选3个数字组成一个集合，不允许两个相邻的数字在一个集合中，那么有多少种选择方法？816

分析：这个题可有两种方法来做：

第一种，先求总数，然后减去不符合要求的，即：C(20,3)-C(18,1)-(1+2+3+...+17)*2=816

第二种，C(20,3)-C(18,1)*C(19,1)+C(18,1)，意思就是相邻的两个数共有19对，任取一对，剩余还有18个数再任取一个即C(19,1)*C(18,1)但是重复减了一次三个数相邻情况。。最后加上C(18,1)

5、1024！末尾有几个0？

分析：1024/5+1024/5^2+1024/5^3+1024/5^4+...=253

6、2^N个元素中挑选最大的元素，至少要做多少次比较？

分析：2^N-1次

7、选择哪些是稳定排序：

分析：详见http://blog.csdn.net/johnny710vip/article/details/6895654

8、知道二叉树的前序、中序和后续遍历，二推一，那个不可能？

分析：前序+后续-/>后续。。其他可以。。

9、程序访问内存的性能与下列哪个方面无关？

A.内存总线的带宽

B.内存页面的访问的特权级别

C.CPU片内的cache大小

D.程序读写内存的连续性

10.下列关于UNIX文件系统的说法中，正确的是？

应用程序可以采用内存映射的方式读取文件数据

二、程序设计与算法

1、给定2个大小为n,m的整数集合,分别存放在两个数组中int A[n],B[m],输出两个集合的交集？

private static Set
     
       setMethod(int[] a,int[] b){        Set
      
        set = new HashSet
       
        ();        Set
        
          set2 = new HashSet
         
          ();        for(int i=0; i
         
        
       
      
     

直接Hash。。

2、银行取款排队模拟

3、O(n)时间复杂度对数值范围0到n^2-1的n个数进行排序

#include 
     
      #include 
      
       using namespace std;int n, radix, length_A, digit = 2;void Print(int *A, int start, int end){    int i;    for(i = start; i <= end; i++)    {        if(i == start)cout<<'{
    ';        else cout<<' ';        cout<
       
        = 1; j--)    {        //如果<=D[j]的数字的个数是x,那么排序后A[j]应该出现在第x个位置，即B[x]=A[j]        B[C[D[j]]] = A[j];        C[D[j]]--;    }    delete []C;    delete []D;}//基数排序void Radix_Sort(int *A, int *B){    int i, j;    //依次对每一位进行排序，从低位到高位    for(i = 1; i <= digit; i++)    {        Stable_Sort(A, B, radix-1, i);        //输入的是A，输出的是B，再次排序时要把输出数据放入输出数据中        for(j = 1; j <= length_A; j++)            A[j] = B[j];    }}int main(){    cin>>n;    length_A = n;    int *A = new int[n+1];    int *B = new int[n+1];    bool flag[1000]  = {
   0};    int i;    //生产n个随机的数据范围在0到n^-1之间    for(i = 1; i <= n; i++)    {        do        {            A[i] = rand() % (n*n);        }while(flag[A[i]]);        flag[A[i]] = 1;    }    Print(A, 1, n);    radix = n;    Radix_Sort(A, B);    Print(A, 1, n);    return 0;}