小米2012春季校园招聘部分笔试题.doc

小米2012春季校园招聘部分笔试题【中山大学2012.04.21】参加了小米的笔试，凭着记忆，把题目分享给大家。这次笔试最后一道题我还没弄懂！欢迎大家一起过来讨论，欢迎各位分享自己的答案。完整版题目：/blog/static/2050971812012322255567/1. 中缀表达式(a+b)*c*(d-e/f) 转成后缀：ab+c*def/-*2. 在一个容量为25的循环队列中，若头指针front=18，尾指针rear=9，则该循环队列中共有（ 9）个元素。3. 若某二叉树的前序访问顺序abdgcefh，中序访问顺序是dgbaechf，则其后序遍历的结点访问顺序是：gdbehfca4. 设一颗完全二叉树共有1699个结点，则该二叉树中叶子结点树为：850这个完全二叉数中，没有度为1的结点。所以结点总数度为2的结点度为0的结点1699N（N1） N=8505. typedef struct char flag3; short value; sampleStruct;union char flag3; short value; sampleUnion;假设 sizeof(char)=1,sizeof(short)=2,那么sizeof(sampleStruct) =?, sizeof(sampleUnion) =?输出结果是：6， 4字符类型占1字节， 可以从任何地址开始short类型占2字节， 必须从2字节倍数地址开始int类型占4字节，必须从4字节倍数地址开始0000 a00001 a10002 a20003 空一个字节0004 b 这个是2倍数的地址0005结构体在内存组织上是顺序式的，联合体则是重叠式，各成员共享一段内存，所以整个联合体的sizeof也就是每个成员sizeof的最大值。4strlen(char*)函数求的是字符串的实际长度，它求得方法是从开始到遇到第一个0,sizeof()函数返回的是变量声明后所占的内存数，不是实际长度char str20=0123456789;int a=strlen(str); /a=10;int b=sizeof(str); /而b=20;6. 假设a=8，b=2012，Recurse()函数的返回值是：int Recurse(int a,int b)If(a=b)If(a=b)return a;else return 0;else return Recurse(a+1,b-1)+a+b; a,b会等于(2012+8)/2=1010, 结果1010+（2012+8）*（1010-8）=20250507. int s=3;for(s=2;s1(5)欲求x3+x5+x6。联合（1）（2）（3）（4）得11x4+x5+2x6=25(6),显然x4=2,又由（5）知x4=2;(6)变为x5+2x6=3（7）；有两种情况：（1）x5=1,x6=1(2)x5=3,x6=0；均成立，所以x3+x5+x6=6+x5+x6=8或9。 9. 请实现下面函数,输入一个参数baseStr是一个（可以更改的）字符串，请将其中所有连续出现的多个空格替换成一个空格，单空格需保留。可以使用任何语言，如需使用任何库函数，必须同时给出库函数的实现。/zhsenl/article/details/7488758/thl331860203/article/details/7262097class ProgramPublic static void RemoveMultipleSpaces(char baseStr)/TODOvoid Deletekongge( char *p)/char *p=str;char *result;int flag=0;while (p!=0)while (*p)= )/有多个空格p+;flag+;/if (flag=0)/没有空格else/有多个空格p-;*result+ = *p+;return result;有几道笔试题记录一下：1.TCP协议属于OSI 7层模型中的（4）层TCP协议属于传输层，在OSI的第四层2.typedef struct char flag3; short value; SampleStruct; typedef union char flag3; short value; SampleUnion;求sizeof(SampleStruct)和sizeof(SampleUnion)写了一段程序测试一下，用的是DEV C+编译器，32位windows xp系统：cppview plaincopy1. #include2. 3. typedefstruct4. 5. charflag3;6. shortvalue;/7. SampleStruct;8. 9. typedefunion10. 11. charflag3;12. shortvalue;/13. SampleUnion;14. 15. intmain()16. 17. SampleStructa;18. SampleUnionb;19. printf(%d,%d,%dn,sizeof(char),sizeof(short),sizeof(a.flag);20. printf(%d,%dn,sizeof(a),sizeof(b);21. 22. return0;23. 返回的结果为：1， 2， 36， 4sizeof(b)=4，猜测是虽然共用体union占字节数由其内部最长的一个变量来决定，sizeof(b.flag)=3，但是为了优化内存其占用字节数为偶数，但是经过测试将struct和union中的short value注释掉后，返回的结果为：1， 2， 33， 33.输入baseStr是一个字符串，请将其中所有连续出现的多个空格都替换成一个空格，单一空格需保留，返回值是替换后的字符串的长度。如果使用任何库函数必须同时给出库函数的实现。public static int RemoveMultipleSpaces(char baseStr)4.存在整型数组result，长度为n并且满足0=low=midhighn，resultlow,mid和resultmid+1,high均已按升序排序，完成函数将resultlow,mid和resultmid+1,high合并升序数组。int *buffer = new intn;void merge(int *result, int low, int mid, int high)For(int j=mid+1,k=low;lowmid &jhigh; k+)if(resultlow1)排序，请使用以上merge函数完成unsort的归并排序。5.字符串A和字符串B，请将A中在B中存在的字符删除，比如A=This is the world，B=abcdefghi，则返回A为Ts s t worl9. 请实现下面函数,输入一个参数baseStr是一个（可以更改的）字符串，请将其中所有连续出现的多个空格替换成一个空格，单空格需保留。可以使用任何语言，如需使用任何库函数，必须同时给出库函数的实现。class ProgramPublic static void RemoveMultipleSpaces(char baseStr)/TODO/说实话，虽然题目很简单，但在考试那么紧的时间内要写得好，也是很有难度的。 /基本思路：先分割出子串，再将子串合并起来。 #include using namespace std; const int N = 100; struct Segment int begin; int end; ; class Program public: static void RemoveMultipleSpaces(char* baseStr) Segment substrsN; memset(substrs,-1,sizeof(substrs); int count = 0; int len = strlen(baseStr); for(int i = 0; i = len | baseStri + 1 != ) substrscount.begin = i; else int j = i; while(baseStr = & i + 1 len & baseStri + 1 = ) i+; if(i != j) substrscount+.end = j; int j = 0; for(int i = 0; i count; i+) if(j = substrs.begin) j = substrs.end + 1; else for(int k = substrs.begin ; k substrs.end + 1; k+) baseStrj+ = baseStrk; baseStrj = 0; ; int main() char aN; gets(a); Program:RemoveMultipleSpaces(a); cout a endl; 10. 在一条直线上有n条线段，已知它们的两个端点。请完成一下代码（两种语言任挑其一），计算这些线段共覆盖了多大的长度（被多条线段覆盖的部分只计算一次）。如Segment：1,9,5,10 Sum=9;C/C+:struct Segmentint start;int end;int Sum(int n, Segment * segments) /n是segments包含的元素个数 /基本思想：位图法 #include #include using namespace std; const int N = 10000; struct Segment int start; int end; ; int coverage(Segment *segments, int n) bool cN; memset(c, 0, sizeof(c); int end = 0; for(int i = 0; i n; i+) for(int j = segments.start; j end) end = segments.end; int max = 0; for(int i= 0; i max) max= count; return max; ; int main() Segment s1; s1.start = 0; s1.end = 5; Segment s2; s2.start = 6; s2.end = 7; Segment ss = s1,s2; cout coverage(ss, 2); JAVA:class Segmentint start;int end;int Sum(Segment segments)解法三：/*Problem: * 一条直线有n个线段，知道首尾坐标，* 求线段总长度，重叠项目组按一次算 * struct sint start;int end;*Author: Lei*Bolg: /-Lei/*/include using namespace std;const int MAX_NODE_NUMBER=20;struct Segment int start; int end;Segment segmentsMAX_NODE_NUMBER;struct TreeNode int left; int right; int cover;/线段树TreeNode tree3*MAX_NODE_NUMBER;void Update（int root，int left，int right） int mid; if（treeroot.cover=0） mid=（treeroot.left+treeroot.right）/2; if（left=treeroot.left & right=treeroot.right） treeroot.cover=1; else if（right = mid） Update（root*2+1，left，right）; else Update（root*2，left，mid）; Update（root*2+1，mid，right）; int Count（int root） if（treeroot.right-treeroot.left=1） return 0; else if（treeroot.cover=1） return treeroot.right-treeroot.left; else return Count（root*2）+Count（root*2+1）; void InitTree（int root，int left，int right） treeroot.cover=0; treeroot.left=left; treeroot.right=right; if（treeroot.right-treeroot.left=1） return ; int mid=（left+right）/2; InitTree（root*2，left，mid）; InitTree（root*2+1，mid，right）;int main（） InitTree（1，1，15）; Update（1，1，4）; Update（1，3，5）; Update（1，2，6）; Update（1，2，3）; Update（1，12，13）; Update（1，8，13）; coutTotal segment length= Count（1）endl; system（PAUSE）; return 0;解法四：java实现源码：public class Line private static int lineLength = 0; private static int start = 0; private static int end = 0; public static void main(String args) Segments s0 = new Segments(); Segments s1 = new Segments(); Segments s2 = new Segments(); s0.setValue(5, 9); s1.setValue(10, 12); s2.setValue(1, 7); Segments segments = new Segments s0, s1, s2 ; segmentsSort(segments); for (int i = 0; i segments.length; i+) System.out.println(segmentsi.start + - + segmentsi.end); for (int i = 0; i end) lineLength += segmentsi.end - segmentsi.start; en