问几个C的面试题？

ivhb

原帖由 zicfy 于 2008-1-23 09:43 发表
假设整形长度 32 bits
建个数组C长度是 2的32次方，遍历一遍所给的数组X，使得C[X]++,(i=0...N)
然后再遍历一遍X，如果C[X] == 2，那就是她了。
赐予我空间吧。

为什么还要遍历一遍呢？
if (++ c[x] == 2)
   printf ("found %d\n", x);

zicfy

恩，对对对

embededboy

这个倒是可以
但是空间，太可怕了。。。
数组好大

dxcnjupt

把数组改作位图可以节省内存，耗内存512M。
if(位图.x==0)
   位图.x = 1;
else
   x就是要找的数;

n不大的情况下可以考虑这个算法：
基于hash的位图，先hash一下，把2^32hash到一个比较小的范围，减小内存消耗；但是这样会引入hash冲突。
设hash冲突概率为p，则
复杂度为O(n+n^2*p)
当hash冲突为100%时，复杂度O(n^2)；当hash冲突为0%时，复杂度为O(n)

算法流程：逐个插入数组元素a0.......aend
对于任意一个数an，hash到bn
查看位图的第bn项，若未设置，则是新数，设置位图的bn项为1；若已设置，则搜索数组
1若找到an项则是重复数，完成；
2若没有找到an，则是hash冲突。
当hash冲突时，设置位图下一项即bn+1项。

hash算法要根据输入数据的分布情况来选择，均匀分布的话取模 a%m 就可以了。
在100×n < m < 2^32时，冲突概率p约等于n/m。
如果我们使用10M的内存来存放位图，m=80M，约等于100000000
O(n+n^3/100000000)在n不超过10000的时候可以看作是O(n)。

如果n比较大而可用内存比较小（m小）的话，还是用排序比较好，毕竟这是个O(n^3)的算法.......
------------------------------------
不好意思，一开始把p算成1/m，后来发现算错了................现在应该没错了吧

[ 本帖最后由 dxcnjupt 于 2008-1-23 15:27 编辑 ]

xfstone

int hash(int v,int Max)
{

        char key[10];
        int h=0,a=127,i;


        i=snprintf(key,10,"%d",v);


        for(i= 0;key;++i)
                h=(a*h+key)%Max;

        return   h+v;//加V避免hash value 碰撞
}

struct hashValue{
        int value;
        int index;
};

int main()
{
        int A[]={7,2,3,4,5,6,1,7,8,9,0};
        int len,hlen;
        int v;
        struct hashValue *buff;
        int j;

        len=sizeof(A)/sizeof(int);
        hlen=2*len;


        buff=(struct hashValue*)malloc(sizeof(struct hashValue)*hlen);

        for(j=0;j<len;j++){
                v=hash(A[j],hlen-1);
                if(buff[v].value==v){
                        printf("Find A[%d] and A[%d] ==%d\n",buff[v].index,j,A[j]);
                        break;
                }else {
                        buff[v].value=v;
                        buff[v].index=j;
                }
        }

        exit(0);
}

]$ ./test
Find A[0] and A[7] ==7

[ 本帖最后由 xfstone 于 2008-1-23 15:57 编辑 ]

zenglj

LS  的算法里面双重循环了啊
怎么能满足O(n)

windoze

楼上诸位还是没搞清这个O(N)是啥意思啊……
O(N)滴意思就是花费固定时间滴操作进行N次，哪怕这个固定时间是一个世纪，这里面滴常数都是忽略滴。
所以，尽管分配2^32个元素滴存储空间，表怕内存不够，内存不够就用硬盘，硬盘不够就用磁带，磁带不够就用打印纸+OCR，要是还不够就叫上全球几十亿人一起帮你记，再不够我们附近还有火星……

meilinxiaoxue

//1 extern int foo(void); int main() {   int i;   for(i=0;i<10000;i++) foo();   return i; } //2 extern int foo(void); int i; int main() {   for(i=0;i<10000;i++) foo();   return i; }

这个题目要依靠编译器足够聪明,实际上我试了一下gcc, tiny cc ,borland c++ 5.5,tiny cc出来的结果基本没啥区别,最多也就是个
直接寻址和寄存器寄存器相对寻址的区别,borland c++ 5.5 和 gcc正确的优化了代码：

1的汇编代码：

_main           proc near               ; DATA XREF: .data:0040A0D0o argc            = dword ptr  8 argv            = dword ptr  0Ch envp            = dword ptr  10h                 push    ebp                 mov     ebp, esp                 push    ebx                 xor     ebx, ebx loc_401166:                             ; CODE XREF: _main+12j                 call    sub_401150                 inc     ebx                 cmp     ebx, 3E8h                 jl      short loc_401166                 pop     ebx                 pop     ebp                 retn _main           endp

2的代码:

_main           proc near               ; DATA XREF: .data:0040A0D0o argc            = dword ptr  8 argv            = dword ptr  0Ch envp            = dword ptr  10h                 push    ebp                 mov     ebp, esp                 push    ebx                 mov     ebx, offset unk_40C45C                 xor     eax, eax                 mov     [ebx], eax                 jmp     short loc_401176 ; --------------------------------------------------------------------------- loc_40116F:                             ; CODE XREF: _main+1Cj                 call    sub_401150                 inc     dword ptr [ebx] loc_401176:                             ; CODE XREF: _main+Dj                 cmp     dword ptr [ebx], 3E8h                 jl      short loc_40116F                 pop     ebx                 pop     ebp                 retn _main           endp

可以看到2中每一次循环都在访问内存改变i的值
所以1快

[ 本帖最后由 meilinxiaoxue 于 2008-1-25 10:05 编辑 ]

meilinxiaoxue

3. 保护模式和实模式的区别。

这个我觉得关键就在于虚拟地址有物理地址上面,实模式直接访问物理地址,而保护模式是虚拟地址,在这个基础上实现了权限分割（段选择子的二位标志）,进程空间分隔（页管理实现的虚拟到物理地址映射）