2012 人民搜索实习生招聘笔试题

素颜马尾好姑娘i 2022-05-24 07:29 238阅读 0赞

转自：[http://blog.csdn.net/hackbuteer1/article/details/7581353\#comments][http_blog.csdn.net_hackbuteer1_article_details_7581353_comments]

1、打印汉诺塔移动步骤，并且计算复杂度。

[http://blog.csdn.net/huangxy10/article/details/8046545][http_blog.csdn.net_huangxy10_article_details_8046545]  
方法是递归，将n-1层移到中间柱，然后将最底层移到目标柱，然后再把n-1层移到目标柱。  
f(n) = 2f(n-1) + 1 , f(1) = 1  
f(n) + 1 = 2( f(n-1) + 1 )  
f(n) = 2^n - 1  
T(n) = O(2^n);  
2、计算两个字符串的是否相似（字符的种类，和出现次数相同）

[http://blog.csdn.net/huangxy10/article/details/8046495][http_blog.csdn.net_huangxy10_article_details_8046495]

3、定义二叉树，节点值为int，计算二叉树中的值在\[a,b\]区间的节点的个数。  
任意一种方式遍历二叉树，如果值在 \[a，b\] 之间，计数器+1

4、一条路有k可坑，每次能跳平方数步长（1 4 9 16。。），不能跳到坑里，从a跳到b最少几步？（动态规划题）  
动态转移方程  
f（n） = min（ f(大于n的第一个平方数 -n) ，f（n- 小于n的第一个完全平方数） +１　）  
【 补充 ing  
在一个坐标轴上， 给定两个点，一个起点，一个终点，起点有一个方块，方块可以左右移动，但是移动的长度只能是平方数长（1,4,9,16 ••••） ，同时坐标轴上还有洞，移动的过程中不能越过这个洞，不然会掉下去，问 由起点到终点 至少需要多少次移动，不能到达返回-1】

5、给一个整数数组，求数组中重复出现次数大于数组总个数一半的数。

**\[cpp\]**  [view plain][] [copy][view plain]

1.  **int** MoreThanHalfNum(**int** \*a , **int** n )  
2.  \{  
3.          **int** i , k , num = a\[0\];  
4.          **int** times = 1;  
5.          **for**(i = 1 ; i < n ; ++i)  
6.          \{  
7.              **if**(times == 0)  
8.              \{  
9.                  num = a\[i\];  
10.                 times = 1;  
11.             \}  
12.             **else** **if**(a\[i\] != num)  
13.                 --times;  
14.             **else**  
15.                 ++times;  
16.         \}  
17.         k = 0;  
18.         **for**(i = 0 ; i < n ; ++i)  
19.         \{  
20.             **if**(a\[i\] == num)  
21.                 ++k;  
22.         \}  
23.         **if**(k\*2 <= n)  
24.             **return** -1;    //没有找到  
25.         **else**  
26.             **return** num;   //找到  
27. \}

6、一个128bits 的二进制流，要求找出 里面包含 某8bits 二进制流的数目。  
如果只是一个128bit的流，那就用int对其某个字节，然后移位比较，然后int向后移动3个字节，继续移位比较。如果是很多128bit的流，可以模仿kmp，用上面的方法，每次取int的8bit和目标8bit进行AND操作，结果只有256种可能，事先存一个256的表，查表决定向后跳跃的bit数。

7、交换整型的奇数位和偶数位   
问题定义：  
        Write a program to swap odd and even bits in an integer with as few instructions as possible(e.g, bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc)

**\[cpp\]**  [view plain][] [copy][view plain]

1.  **int** SwapOddEvenBit(**int** x)    
2.  \{    
3.      **return** ( ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));    
4.  \}    
5.  **int** main(**void**)    
6.  \{    
7.      **int** a = 171;    
8.      printf("%d\\n", SwapOddEvenBit(a));    
9.      **return** 0;    
10. \}

8、试着用最小的比较次数去寻找数组中的最大值和最小值。

解法一：  
扫描一次数组找出最大值；再扫描一次数组找出最小值。  
比较次数2N-2  
  
解法二：  
将数组中相邻的两个数分在一组， 每次比较两个相邻的数，将较大值交换至这两个数的左边，较小值放于右边。  
对大者组扫描一次找出最大值，对小者组扫描一次找出最小值。  
比较1.5N-2次，但需要改变数组结构  
   
解法三：  
每次比较相邻两个数，较大者与MAX比较，较小者与MIN比较，找出最大值和最小值。  
方法如下：先将一对元素互相进行比较，然后把最小值跟当前最小值进行比较，把最大值跟当前最大值进行比较。因此每两个元素需要3次比较。如果n为奇数，那么比较的次数是3\*(n/2)次比较。如果n为偶数，那么比较的次数是3n/2-2次比较。因此，不管是n是奇数还是偶数，比较的次数至多是3\*(n/2)，具体的代码如下：

**\[cpp\]**  [view plain][] [copy][view plain]

1.  **void** GetMaxAndMin(**int** \*arr , **int** n , **int** &max , **int** &min)  
2.  \{  
3.      **int** i = 0 ;  
4.      **if**(n & 1)     // 奇数  
5.      \{  
6.          max = min = arr\[i++\];  
7.      \}  
8.      **else**  
9.      \{  
10.         **if**(arr\[0\] > arr\[1\])  
11.         \{  
12.             max = arr\[0\];  
13.             min = arr\[1\];  
14.         \}  
15.         **else**  
16.         \{  
17.             max = arr\[1\];  
18.             min = arr\[0\];  
19.         \}  
20.         i += 2;  
21.     \}  
22.       
23.     **for**( ; i < n ; i += 2)  
24.     \{  
25.         **if**(arr\[i\] > arr\[i+1\])  
26.         \{  
27.             **if**(arr\[i\] > max)  
28.                 max = arr\[i\];  
29.             **if**(arr\[i+1\] < min)  
30.                 min = arr\[i+1\];  
31.         \}  
32.         **else**  
33.         \{  
34.             **if**(arr\[i+1\] > max)  
35.                 max = arr\[i+1\];  
36.             **if**(arr\[i\] < min)  
37.                 min = arr\[i\];  
38.         \}  
39.     \}  
40. \}

[http_blog.csdn.net_hackbuteer1_article_details_7581353_comments]: http://blog.csdn.net/hackbuteer1/article/details/7581353#comments
[http_blog.csdn.net_huangxy10_article_details_8046545]: http://blog.csdn.net/huangxy10/article/details/8046545
[http_blog.csdn.net_huangxy10_article_details_8046495]: http://blog.csdn.net/huangxy10/article/details/8046495
[view plain]: http://blog.csdn.net/hackbuteer1/article/details/7581353#