专栏名称: Python技术博文
分享有关Python知识，了解IT界最新技术，让我们一起从菜鸟变成大牛吧！
目录
相关文章推荐
Python爱好者社区  ·  深度学习“四大名著”发布！Python、机器 ... ·  2 天前  
Python爱好者社区  ·  刷新三观，深圳某公司重新定义八小时工作制 ·  2 天前  
Python中文社区  ·  快来体验OpenAI最新o1模型！ ·  5 天前  
Python爱好者社区  ·  今天面试了一个字节女生，当场想给她offer！ ·  1 周前  
Python中文社区  ·  400+业务场景接入，大模型，彻底爆发！ ·  1 周前  
51好读  ›  专栏  ›  Python技术博文

近几年微软笔试题汇总分类解析

Python技术博文  · 公众号  · Python  · 2017-06-15 09:17

正文

这里对2010年至今的微软笔试题做了一个汇总和分类，然后进行了解答和分析，每一类题中涉及到的知识点和方法在很多别家公司的笔试面试中也有用，希望下面的内容能在大家找工作的时候给大家一些帮助。

1、数组，排序相关

1、合并两个已排好序的数组在最坏情况下需要比较多少次？ （2010年9月校招考题）

(A)2n (B)2n-1 (C)2n+1 (D)2n-2 (E)None of above

分析：最后所生成的数组元素个数为2n个. 最坏情况为: 每比较一次,只确定一个元素的位置(最后一次比较确定两个元素的位置,即倒数第一个和倒数第2个),所以总的最坏比较次数为2n-1.


2、编程题   （2010年9月校招考题）

        一个rotated sorted array是一个在某处交换了元素的sorted array，例如，rotated sorted array[13, 27, 37, 2, 3, 5]是从sorted array[2, 3, 5, 13, 27, 37]变换而来的，这个sorted array是以增序排好序的。

         现在需要计算给定值在rotated sorted array中的索引。例如，27在rotated sorted array[13, 27, 37, 2, 3, 5]中的索引是2。注意：如果想得满分，程序的时间复杂度需要小于O(n)。

分析：旋转数组求下标问题。

     如果数组是有序数组，进行二分查找的时间复杂度是O(logN)。在旋转数组中，二分查找的情况稍微复杂一些，如下图所示，数组平分后一半是有序数组，一半仍是旋转数组。

   确定下次二分查找在前半段区间还是后半段区间进行。
仔细分析该问题，可以发现，每次根据low和high求出mid后，mid左边（[low, mid]）和右边（[mid, high]）至少一个是有序的。
     a[mid]分别与a[left]和a[right]比较，确定哪一段是有序的。
如果左边是有序的，若x且x>a[left], 则right=mid-1；其他情况，left =mid+1；
如果右边是有序的，若x> a[mid] 且x则left=mid+1；其他情况，right =mid-1；

代码如下：


[cpp] view plain copy

  1. int binary_search_rotate_arry(int *a, int n, int x)  

  2. {  

  3.     int low = 0, high = n - 1, mid;  

  4.     while(low <= high)  

  5.     {  

  6.         mid = low + ((high - low) >> 1);  

  7.         if(a[mid] == x)  

  8.             return mid;  

  9.         if(a[mid] >= a[low])  

  10.         {//左边有序  

  11.             if(x = a[low])  

  12.                 high = mid - 1;  

  13.             else  

  14.                 low = mid + 1;  

  15.         }  

  16.         else //右边有序  

  17.         {  

  18.             if(x > a[mid] && x <= a[high])  

  19.                 low = mid + 1;  

  20.             else  

  21.                 high = mid - 1;  

  22.         }  

  23.         //cout <  

  24.     }  

  25.     return -1;  

  26. }  



3、一个文件中有多行信息，每一行信息中，第一个为一个key，后面用空格间隔若干symbol，例如： 

B A C D E（每一行中的一个symbol至多出现一次，且不与key重复），表示B关联。 

若一行中只有一个值，如 C 则表示无关联。 

现在求写出一个算法，判断一个文件下的所有行中所包含的关联，能否囊括所有元素的关联，使之形成一个sort链，达到例如：A的效果。 

例1 

input: 

A B C 

B C 

C 

（means:A） 

output： 

It can be sorted determine. 

例2 

input: 

A B 

B A 

C 

（means:A） 

output: 

It can't be sorted determine. 

例3 

input: 

A B 

A C 

C 

(means:A

output: 

It can't be sorted determine.

分析：貌似是拓扑排序的一道题，这个博主不懂，大家补充，多谢。


4、数组中最大连续子段和问题，求其最优算法的时间复杂度   （2011年4月实习招聘考题）

分析：典型的动态规划问题


若记b[j]=max(a[i]+a[i+1]+..+a[j]),其中1<=i<=j,并且1<=j<=n。则所求的最大子段和为max b[j]，1<=j<=n。


由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归式为:b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。


据此，可设计出求最大子段和问题的动态规划算法如下：


[cpp] view plain copy

  1. /********************************************************************** 

  2. 动态规划求最大子序列和 

  3. **********************************************************************/  

  4. int Maxsum(int * arr, int size)  

  5. {  

  6.     int maxSum = -INF; //很重要，初始值赋值为负无穷大  

  7.     int sum = 0;  

  8.     for(int i = 0; i 

  9. {  

  10. //小于0则舍弃  

  11.         if(sum 

  12.         {  

  13.             sum = arr[i];  

  14.         }else  

  15.         {  

  16.             sum += arr[i];  

  17.         }  

  18. //比现有最大值大，则替换  

  19.         if(sum > maxSum)  

  20.         {  

  21.             maxSum = sum;  

  22.         }  

  23.     }  

  24.     return maxSum;  

  25. }  


只用到了O(n)的时间复杂度和O(1)的空间复杂度。


5、快排的最优、最坏、平均的复杂度  （2011年4月实习招聘考题）

分析：基础题。最优、平均：O(n log n)，最坏：O(n^2)



6、找出一个数组中，第M大的数，时间复杂度是？

A O(logN)

B O(N)

C O(NlogN)

D O(N2) /*（代表平方）*/

E 以上都不对


分析： 1）利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：

   1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；

   2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)

        2）利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)




7、给出一个一维的点集，求能够包含[n/2]个点的第一个最小区间的左边界和右边界（实际上就是数组）。例如{5,-3,10，4，-2，-5}，第一个包含[n/2]个点的最小区间就是[-5,-2]。（2011年4月实习招聘考题）

分析：这道题目让求解的是前n/2个数，也就是说，我们找到中位数和最大(小)元素即可。而求中位数的方法，在数组有序的时候显然是二分，但这里的数组是无序的，恩，要时刻记得快排的partition算法，在很多时候很有帮助。代码如下：


[cpp] view plain copy

  1. int Partition(int* A, int begin, int end)  

  2. {  

  3. //分治元素  

  4. int X = A[end];  

  5. //A[begin]...A[i-1]  

  6. int i=begin;  

  7. //A[j]...A[end]>=X  

  8. int j=end;  

  9. //循环开始前A[j]是等待被填充的元素，该元素已被保存到X  

  10. while (i

  11. {  

  12. //从前面开始找到小于X的数  

  13. while (A[i]

  14. i++;  

  15. //A[j]被填充，A[i]等待被填充  

  16. if (i

  17. A[j] = A[i];  

  18. while(A[j]>=X && i

  19. j--;  

  20. //A[i]被填充，A[j]等待被填充  

  21. if (i

  22. A[i]=A[j];  

  23. }  

  24. A[i] = X;  

  25. return i;  

  26. }  

  27. /* 

  28. 返回中位数元素 

  29. @para: 

  30. A[begin...end]为所求数组 

  31. middle_index 为中位数的索引 

  32. middle_element为中位数元素，返回用 

  33. */  

  34. void FindMiddleElement(int* A,int begin ,int end,  

  35.   int middle_index,int& middle_element)  

  36. {  

  37. if (!A || begin>end)  

  38. {  

  39. return;  

  40. }  

  41. int split_pos = Partition(A,begin,end);  

  42. if (split_pos == middle_index)  

  43. {  

  44. middle_element = A[split_pos];  

  45. return;   

  46. }  

  47. FindMiddleElement(A,begin,split_pos-1,middle_index,middle_element);  

  48. FindMiddleElement(A,split_pos+1,end,middle_index,middle_element);  

  49. }  



8、N个数，范围从-N到N,可能重复，排序时间复杂度最好能到多少？（2011年9月招聘考题）

分析：答案是O(n)，使用计数排序和位图排序，桶排序都可以达到这个时间复杂度。



9、假设一个长度为80的数组选择排序已完成主循环32次迭代。现在能保证有多少元素是在他们最终的位置？（2012年4月实习生招聘考题）

A、16    B、31   C、32     D、39   E、40

分析：这个不用过多解释吧，对选择排序不了解的详见找工作知识储备(3)---从头说12种排序算法：原理、图解、动画视频演示、代码以及笔试面试题目中的应用


10、下列哪项陈述是对的？（2012年4月实习招聘考题）

A、我们能从一颗二叉树的先序遍历序列和中序遍历序列，确定这颗二叉树。

B、我们能从一颗二叉树的先序遍历序列和后序遍历序列，确定这颗二叉树。

C、近乎排序的数组，插入排序可以比快排更有效。

D、假设T(n)是解决n个元素的问题时候的运行时间，T(N)= O(1)如果n = 1；T(n)＝2×T(N/2)+ O(n)当n＞1；则T(n)是O(nlgn)

E、上述都不对


11、下面哪项(些)陈述是对的？（2012年4月实习招聘考题）

A、插入排序和冒泡排序在大型数据集下效率很低。

B、快速排序是在最坏情况下比较了O（N^2）次。

C、有一序列7,6,5,4,3,2,1。如果使用选择排序（升序），交换操作次数是6

D、堆排序使用两个堆操作：插入、堆调整

E、上述都不对

分析：常规题，对各种排序算法要熟悉


12、最长递增子序列（LIS）是一个序列满足元素的值不断增加的子序列中最长的序列。

例如，里{ 2,1,4,2,3,7,4,6 }是{ 1,2,3,4,6 }，以及LIS的长度为5。

考虑具有n个元素的数组，则得到LIS的长度的最低的时间复杂度和空间复杂度是多少？（2012年4月实习招聘考题）

A、Time : N^2 , Space : N^2
B、Time : N^2 , Space : N
C、Time : NlogN , Space : N
D、Time : N , Space : N
E、Time : N , Space : C

分析：详见找工作知识储备(2)---数组字符串那些经典算法：最大子序列和，最长递增子序列，最长公共子串，最长公共子序列，字符串编辑距离，最长不重复子串，最长回文子串


13、对于以下的定义（2013年4月实习招聘考题）


[cpp] view plain copy

  1. int [][] myArray3 =new int[3][]{  

  2.   new int[3]{5,6,2},  

  3.   new int[5]{6,9,7,8,3},  

  4.   new int[2]{3,2}};  


则myArray3[2][2]返回的是?

    A. 9

    B. 2

    C. 6

    D. overflow

分析：越界导致overflow


14、以下哪些排序方法是稳定的？ （2013年4月实习招聘考题）

A. 冒泡排序

B. 快速排序

C. 堆排序

D. 归并排序

E. 选择排序


15、快速排序的最好时间复杂度是?（2013年9月招聘考题）

A、O(lgn)
B、O(n)
C、O(nlgn)
D、O(n*n)

分析：好吧，这一题就不解释了，大家都知道的。



2、链表相关

1、下列程序的输出是什么？（2012年4月实习招聘考题）


[cpp] view plain copy

  1. #include  

  2. using namespace std;  

  3. struct Item  

  4. {  

  5. char c;  

  6. Item *next;  

  7. };  

  8. Item *Routine1(Item *x)  

  9. {  

  10. Item *prev = NULL,  

  11. *curr = x;  

  12. while(curr)  

  13. {  

  14. Item *next = curr->next;  

  15. curr->next = prev;  

  16. prev = curr;  

  17. curr = next;  

  18. }  

  19. return prev;  

  20. }  

  21. void Routine2(Item *x)  

  22. {  

  23. Item *curr = x;  

  24. while(curr)  

  25. {  

  26. cout<c<<" ";  

  27. curr = curr->next;  

  28. }  

  29. }  

  30. int main(void)  

  31. {  

  32. Item *x,  

  33. d = {'d' , NULL},  

  34. c = {'c' , &d},  

  35. b = {'b' , &c},  

  36. a = {'a' , &b};  

  37. x = Routine1( &a );  

  38. Routine2( x );  

  39. return 0;  

  40. }  


A、 c b a d

B、 b a d c 

C、 d b c a 

D、 a b c d

E、 d c b a

分析：原程序将链表进行翻转了


2、链表和数组的区别是? （2013年4月实习招聘考题）

A. Search complexity when both are sorted

B. Dynamically add/remove

C. Random access efficiency

D. Data storage type

分析：之前看这道题的D选项是有争议的，我这里根据自己的理解还是选上吧


3、给定一个链表L: (L0 , L1 , L2...Ln-1 , Ln). 写程序使得链表中的节点变为(L0 , Ln , L1 , Ln-1 , L2 , Ln-2...).（2013年9月招聘考题）


[cpp] view plain copy

  1. struct Node  

  2. {  

  3. int val_;  

  4. Node* next;  

  5. };  


要求：

1）空间复杂度O(1)  2）节点中只有next域可以改动

分析：其实就是把链表的后半部分翻转，之后再对前半部分和后半部分做一个交叉合并就可以了吧。代码如下：


[cpp] view plain copy

  1. //完成对头为head的链表的反转  

  2. Node* ReverseList(Node*& head)  

  3.     {  

  4.         if ( (head == 0) || (head->next == 0) ) return;// 边界检测  

  5.         Node* pNext = 0;  

  6.         Node* pPrev = head;// 保存链表头节点  

  7.         Node* pCur = head->next;// 获取当前节点  

  8.         while (pCur != 0)  

  9.         {  

  10.             pNext = pCur->next;// 将下一个节点保存下来  

  11.             pCur->next = pPrev;// 将当前节点的下一节点置为前节点  

  12.             pPrev = pCur;// 将当前节点保存为前一节点  

  13.             pCur = pNext;// 将当前节点置为下一节点  

  14.         }  

  15.         Return Pcur;  

  16.     }  

  17. //查找中间节点，使用一快一慢两指针，快指针一次走两步，慢指针一次走一步，最后返回慢指针  

  18. .Node * GetMiddleNode(Node*& head)  

  19. {  

  20. if ( (head == 0) || (head->next == 0) )   

  21.       return NULL;  

  22. Node* pFast = head;//快指针  

  23.     Node* pSlow = head;// 慢指针  

  24. while（pFast ！= Null && pFast->next != Null）  

  25. {  

  26.     pFast = pFat->next->next;  

  27.         pSlow = pSlow->next;  

  28. }  

  29. return pSlow;  

  30. }  

  31. // 交叉合并A和B两链表  

  32. Node* Merge(Node* & A,Node* & B)  

  33. {  

  34.      Node *p,*q,*s,*t;  

  35.      p=A->next;  

  36.      q=B->next;  

  37.      while(p&&q)  

  38.      {  

  39.        s=p->next;  

  40.        p->next=q;  

  41.        if(s)  

  42.        {  

  43.             t=q->next;  

  44.             q->next=s;  

  45.        }  

  46.        p=s;  

  47.        q=t;  

  48.      }  

  49.      return A;  

  50. }  

  51. //完成题目要求的顺序调整  

  52. Node* ReorderList(Node* pHead)  

  53. {  

  54. Node *pMiddle, *pEnd, *nHead;  

  55.     pMiddle =  GetMiddleNode(Node*& head);  

  56. pEnd = ReverseList(pMiddle);      //后半部分反转  

  57. nHead = Merge(pHead , pMiddle);    //链表交叉归并  

  58. return nHead;  

  59. }  


3、树，遍历

1、二叉树的任意两个节点间有一个唯一路径，求出n个节点的二叉树的最长路径的两个节点的最优算法时间复杂度是多少 （2011年4月实习招聘考题）

分析：O(n)就够了:

从叶子节点开始，找到每个结点的经过它能得到的最长路径和它的最长分支，

　　　 (node1)

　　e1/         \e2

  (node2)    (node3)

很明显，经过node1的最长路径为node2和node3的最长分支之和再加上两条边（e1和e2）的长度。


对这道题，多说两句，编程之美3.8有过解答，时间复杂度为O(v)。但是这里有点不同：树的边有权值。


第一种解法：最大距离的节点一定是叶子节点，首先将二叉树看成一个连通图，首先应该求根节点到所有叶节点的最大距离叶节点A，然后求A到所有其他节点的最大距离。假设要求节点A到其他节点之间的最长路径，题目的转换为求解以A为源点的最长路径。采用单源最短路径（dijkstra）的思想求解。这里要求最长路径，因此，每次选择时，应该从未知最大距离的节点集合中选择最大距离的节点加入已知最大距离的节点集合。如果采用堆结构来维护未知节点到A的最大距离，那么时间复杂度为O（vlogv）。


第二种解法：采用编程之美3.8节的递归方法，递归遍历二叉树一次，得出最大距离，时间复杂度为O（v）


思路：对于一路径，其有两种情况

1. 经过根节点，

2. 不经过根节点，

首先来考虑经过根节点的情况，这样把路径分成两部分，一是左子树起点为根节点的最长路径，

二是右子树起点为根节点的最长路径。

从根节点开始的最长路径可以通过遍历该树的叶子节点得到。


然后再考虑不经过根节点的情况，

不经过根节点，那么最长路径要不存在于左子树，要么存在于右子树。这样，我们就把问题

分解成了两个小问题，即取左子树最长路径和右子树最长路径的最大值。


现在，来分析算法复杂度，不妨记二叉树有n个节点，其复杂度为f(n).

经过根节点的复杂度为O(n)，因为其必须遍历所有叶子节点，因此必须遍历所有的节点。

不经过根节点的复杂度为2*f(n/2)，假设左子树和右子树的节点数目相同。从而得到：

f(n) = O(n) + 2*f(n/2)

= O(nlogn)



2、后续遍历的二叉树：DEBFCA，则下列中可能是其前序排列的是？（2011年4月实习招聘考题）
A：ABFCDE
B：ADBFEC
C：ABDECF
D：ABDCEF
E：none of the above


3、一颗3阶B树有2047个key-words，那这颗树的高度最大为多少？（2012年4月实习招聘考题）

A、11     B、12     C、13    D、14
分析：m阶B-树的根节点至少有两棵子树，其他除根之外的所有非终端节点至少含有m/2(向上取整)棵子树，即至少含有m/2-1个关键字。要想让3阶的B-树达到最大的高度，那么每个节点含有一个关键字，即每个节点含有2棵子树，也就是所谓的完全二叉树了，这样达到的高度是最大的。即含有2047个关键字的完全二叉树的高度是多少。很明显求得高度是11。


4、二叉树的先序遍历结果为abcdefg，则它的中序遍历结果可能是？（2012年9月招聘考题）


A、abcdefg
B、gfedcba
C、efgdcba
D、bceadfg
E、bcdaefg

分析：几种遍历方式，年年考，要特别注意。



5、有n个元素的完全二叉树的深度是：（2012年9月招聘考题）

A. D(n)=log2(n)

B. D(n)=1+log2(n)

C. D(n)=n+log2(n)

D. D(n)=1+n*log2(n)


分析：普遍来说，认为根结点深度为1，所以深度=1+ log2(n)



6、我们在得知下列哪些选项的条件下可以还原二叉树？

A. 先序遍历和中序遍历

B. 先序遍历和后序遍历

C. 中序遍历和后序遍历

D. 后序遍历

分析：一定要有一个中序遍历，才便于区分左侧和右侧部分。先序遍历和后续遍历无法确定一颗二叉树。


7、50 万个学生信息，其中有 id 和 name 字段，id 是 7为数字，name 是字符串；问如果要查询 1) 通过 name 查 id 2) 通过 id 查 name 那么，合适的数据结构是 ?（2013年9月招聘考题）

A. 1）叶子节点为hash(100 bucket)的树 2）叶子节点为链表的树

B. 1）叶子节点为链表的树 2）数组

C. 1）叶子节点为链表的树 2）hash(10000 bucket)

D. 1）排序链表 2）数组

分析：名字可能重复，而编号不会重复。查找名字用二叉查找树，找到节点后，会有若干个编号，所以每个节点存一个单链表。如果查找名字，编号是无重复的，有50万个，10000个桶不够用，直接用数组比较好。


4、堆栈性质

1、有一个序列的n个数字为1,2,3，……，n，现有一个栈最多可以保持M个数。将N个数依次进栈后，随机弹出生成序列。例设n为2 ，m为3，输出序列可以是12或21，所以我们得到了2种不同的序列。设n是7，和m是5，请选择该栈的可能出栈序列。（2012年4月实习招聘考题）

A、1,2,3,4,5,6,7
B、7,6,5,4,3,2,1
C、5,6,4,3,7,2,1
D、1,7,6,5,4,3,2
E、3,2,1,7,5,6,4

分析：这道题目不仅在微软笔试出现过，也被很多别家公司当做笔试题考过，甚至出现过相类似的算法大题。它包含一个隐藏的出栈顺序规则：对于编号较小的出现在较大的编号后面时一定是降序排列的，如：1,4,3,2是合理的，而1,4,2,3就是一个错误出栈序列。这道题还需要考虑的一个问题是栈的大小是有限的，连续的降序段的长度不能大于5。综合这两点可选出答案。


2、下面哪一种操作不是stack的基本操作？（2012年9月招聘考题）

A.  入栈

B.  出栈

C.  检查是否为空

D.  排序栈中元素


3、以下这些序列中，哪些不可以写作一个二叉搜索树后序遍历的结果？（2013年9月招聘考题）

A、1,2,3,4,5
B、3,5,1,4,2
C、1,2,5,4,3
D、5,4,3,2,1

分析：根据左右根的顺序。最后一个元素一定可以将前n-1个数分成前后两部分，一部分比它大，一部分比它小。B无法满足这种性质。

5、字符串与指针


1、读程序写运行结果   （2011年4月实习招聘考题）


[cpp] view plain copy

  1. #include  

  2. using namespace std;  

  3. int func(int *s,int row,int col)  

  4. {  

  5.     int count = 0;  

  6.     int start = 1;  

  7.     int current = start;  

  8.     int pending = s[current];  

  9.     do{  

  10.           int r = current/col;  

  11.           int c = current%col;  

  12.           int next = c*row+r;  

  13.           int tmp = pending;  

  14.           pending = s[current];  

  15.           s[current] = tmp;  

  16.     

  17.           ++count;  

  18.           current = next;  

  19.     }while(current != start);  

  20.     return count;  

  21. }  

  22. void test()  

  23. {  

  24.     int s[12];  

  25.     int r = func(s,3,4);  

  26.     cout<

  27. }  

  28. int main()  

  29. {  

  30.     test();  

  31.     system("pause");  

  32.     return 0;  

  33. }  


分析：5


2、拷贝字符串当src和dest有overlap时，使用哪个是安全的，memcpy还是memmove？（2011年9月招聘考题）

分析：几个涉及到拷贝字符串的函数的介绍如下

   char *strcpy(char *dest,char *src);  

   功能：把src所指由NULL结束的字符串复制到dest所指的数组中

   说明:src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。

   返回指向dest的指针

  

   void *memcpy(void *dest,void *src,unsigned int count);

   功能：由src所指内存区域复制count个字符串到dest所指内存区域.

   说明：src和dest所指内存区域不能重叠，函数返回指向dest的指针.

      

   void *memmove (void *dest, const void *src, size_t n);

   从src所指向的对象复制n个字符到dest所指向的对象中。返回指针为dest的值。不会发生内存重叠。


3、下列程序的运行结果是什么？（2012年4月实习招聘考题）


[cpp] view plain copy

  1. char *f(char *str , char ch)  

  2. {  

  3. char *it1 = str;  

  4. char *it2 = str;  

  5. while(*it2 != '\0')  

  6. {  

  7. while(*it2 == ch)  

  8. {  

  9. it2++;  

  10. }  

  11. *it1++ = *it2++;  

  12. }  

  13. return str;  

  14. }  

  15. int main(void)  

  16. {  

  17. char *a = new char[10];  

  18. strcpy(a , "abcdcccd");  

  19. cout<'c');  

  20. return 0;  

  21. }  


A、abdcccd
B、abdd
C、abcc
D、abddcccd
E、Access violation


4、有长度为n的字符串，假设字符串的每个字符都不一样，有多少不同的子串？（2013年9月招聘考题）

 A. n+1

 B. n^2

 C. n(n+1)/2

 D. 2^n-1

 E. n!


6、递归，菲波拉契数列

1、F(0)= 0;F(1)=1; F(n)=(F(n-1)+F(n-2))%5， 求F(2011)  （2011年4月实习招聘考题）

分析：循环数组，写几个就知道了，不过这里循环的长度确实很长。

0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 ...

(2011+1)%20 = 12 ， F(2011) = 4



2、考虑以下计算e的指数次方的递归函数。（2012年4月实习招聘考题）


[cpp] view plain copy

  1. int power(int b , int e)  

  2. {  

  3. if(e == 0)  

  4. return 1;  

  5. if(e % 2 == 0)  

  6. return power(b*b , e/2);  

  7. else  

  8. return b * power(b*b , e/2);  

  9. }  


Asymptotically（渐进地） in terms of the exponent e,the number of calls to power that occur as a result of the call power(b,e) is

A、logarithmic
B、linear
C、quadratic
D、exponential

分析：是对数次的。


2、在计算 f(10)的过程中调用函数f()的次数是? （2013年9月招聘考题）


[cpp] view plain copy

  1. int f(int x)  

  2. {  

  3. if(x <= 2)  

  4. return 1;  

  5. return f(x - 2) + f(x - 4) + 1;  

  6. }  


A、14
B、18
C、20
D、24
E、None of the above.

分析：这道题目博主画了一颗二叉树，数了一下，貌似是14

7、函数、指针与内存管理

1、以下代码执行后的结果是什么？（2012年4月实习招聘考题）


[cpp] view plain copy

  1. void main()  

  2. {  

  3. int i = 11;  

  4. int const *p = &i;  

  5. p++;  

  6. printf("%d",*p);  

  7. }  


A、11
B、12
C、Garbage value
D、Compile error
E、None of above

分析：显然这时候p指向的是未知的内容。


2、以下哪段(些)代码是正确的？C  （2012年4月实习招聘考题）

A  


[cpp] view plain copy

  1. int f()  

  2. {  

  3. int *a = new int(3);  

  4. return *a;  

  5. }  



B


[cpp] view plain copy

  1. int *f()  

  2. {  

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

  4. return a;  

  5. }  


C

[cpp] view plain copy

  1. vector<int> f()  

  2. {  

  3. vector<int> v(3);  

  4. return v;  

  5. }  


D


[cpp] view plain copy

  1. void f(int *ret)  

  2. {  

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

  4. ret = a;  

  5. return ;  

  6. }  


E 都不对


分析：在函数体内，栈上申请的内存，不能返回指针。详见找工作笔试面试那些事儿(3)---内存管理那些事


3、下面哪个是函数指针的声明 ?（2013年9月招聘考题）

A. void *f(int);

B. int (*f)();

C. void (*f(int, void(*)(int)))(int);

D. void (*(*f)(int))();

分析：自己看看函数指针的定义吧。A是返回指针的函数，D是一个返回函数指针的的函数声名。

8、图

1、求下图中S到T的最短路径（2013年4月实习招聘考题）

A. 17

B. 18

C. 19

D. 20

E. 21

分析：反正博主是直接数的



2、下面图的深度优先遍历可能的遍历结果有 :（2013年9月招聘考题）

A. BADECF

B. BADEFC

C. BCAFDE

D. BCFEDA

E. BFDECA

分析：通俗的话讲就是，深搜是每次走到底，无路可走，再重选节点走。





推荐文章
Python爱好者社区  ·  深度学习“四大名著”发布！Python、机器学习等（附免费下载）
2 天前
Python爱好者社区  ·  刷新三观，深圳某公司重新定义八小时工作制
2 天前
Python中文社区  ·  快来体验OpenAI最新o1模型！
5 天前
Python爱好者社区  ·  今天面试了一个字节女生，当场想给她offer！
1 周前
Python中文社区  ·  400+业务场景接入，大模型，彻底爆发！
1 周前
立德融金集团  ·  2016年A股IPO潮涌：低价发行下募资5年新高 中签盈利频创纪录
7 年前
儿童摄影引导技巧  ·  清洁工的婚纱照，看了想哭！
7 年前
午夜漫画站  ·  幻啃漫画：狼来啦
7 年前
OSC开源社区  ·  Spark Streaming场景应用-Kafka 数据读取方式
7 年前
张江发布  ·  活动 | 约！7.1 云栖TechDay，一起论道“设计的力量”
7 年前
Sov5搜索   ·   小百科   ·   移动版
51好读 - 好文章就要读起来!