问几个C的面试题？

meilinxiaoxue

原帖由 duanius 于 2008-1-24 13:04 发表
49楼让我受益匪浅 感谢
不过还是想小声问下  gcc的几个优化级别是不是都要试下呢？
记不清每个级别具体优化什么 但没理由不优化寄存器的吧。。。

不好意思,我以为gcc默认会优化（结果要指定）,你说的没错,指定O1就优化了正确的代码.

yovn

原帖由 u239 于 2008-1-25 09:08 发表
AVL树的生成复杂性好像也是O(nlogn)吧，AVL树的查找复杂性是O(logn)。哈希倒是个可行的方法。

我不认为Hash可行，理论分析是到不了的，AVL树的生成是显然可以的。生成的复杂度是O(N),之前想了堆的生成，仔细想想，不行，就没想下去了，AVL确实是可以的。

dinghwy

原帖由 cugb_cat 于 2008-1-22 16:48 发表

遍历数组，因为数组中只有两个是相同的，所以哈希出来的数值基本是不一样的（只有那两个是一样的），当访问数组中一个元素的时候就去看看哈希表中是否已经有该元素了，如果有了就找出来了。
上述是在不考虑哈 ...

那样的hash函数应该比较好找吧。

Sorehead

我错了，AVL树查找的时间复杂度是O(logn)，所以是不行的。

dxcnjupt

说hash的朋友仔细想一下：
“查看hash表里是否有这个元素”
关键就在于这个步骤的复杂度。
直接搜索是O(n)，排序后搜索是O(logn)
对每一个数，都要hash一次搜索一次，结果是O(n*logn)

除非是搜索hash表时用位图，因为位图直接用下标取值就可以了，所以对每个数，只要O(1)常数时间。

cugb_cat

哈希与位图有本质区别吗？为什么每个数都要搜索一次哈希表？直接定位不行吗？

Edengundam

整形数组A[N], 其中只有两个元素是相同的，设计一个复杂度为O(n)的算法，将其找出。

既然是int, 那么就用bit来表示, 没有明确要求时间和空间, 因此假设是时间, bit位被占用, 表示重复出现. 复杂度就是O(n).

T-bagwell

原帖由 cugb_cat 于 2008-1-25 13:01 发表
哈希与位图有本质区别吗？为什么每个数都要搜索一次哈希表？直接定位不行吗？

能否解释解释第一题的答案
为什么我

1. [root@localhost root]# ./a.out
   
2. 10.733874 10.733874
   
3. 1
   
4. 1
   
5. [root@localhost root]# cat a.c
   
6. #include <stdio.h>
   
7. 
   
8. int main()
   
9. {
   
10.         float a=1.399923,b=4.222839,c=5.111112;
    
11.         printf("%f %f\n",(a+b)+c,(a+c)+b);
    
12.         printf("%d\n",((a+b)+c)==((a+c)+b));
    
13.         printf("%d\n",((a+b)+c)==((b+a)+c));
    
14.         return 0;
    
15. }

复制代码

谢谢啊