近两年科大讯飞实习生笔试、面试题

1、第一题是递归判断五子棋问题，在一个棋盘上，0代表空，1代表黑子，2代表白子，现给定一个坐标(ax,ay),代表当前下的黑子的位置，求递归判断黑子是否已经赢了(不考虑赢的趋势，也即仅仅判断当前状态)然后就是问如何求1到1000000内所有素数，(相信弄过一点算法都清楚筛选法)最后问了个如何在一个序列中求第k大的数，笔者当时脑袋一热回答了二叉搜索树+优先级(也OK)，面试官听完后就来了句，不就是堆嘛。1. 已知二叉树的前序遍历为ABCDEFGHIJ，中序遍历为CBEDAHGIJF，请画出其二叉树结构。2.求一个整数数组的最大元素，用递归方法实现。1. #include2. #include3. u

2、singnamespacestd;4. 5. intmaxnum(inta,intn)6. 7. if(n=1)8. returna0;9. if(n1)10. 11. returnmax(a0,maxnum(a+1,n-1);12. 13. 14. intmain()15. 16. intnum10=0,1,2,3,4,5,6,7,8,9;17. coutmaxnum(num,10)n = n （不能写成n = n）。7.写出字符串类的必备构造函数和赋值运算符重载的实现方法。已知类String的原型为：class Stringpublic:String( const char *pStr =

3、 NULL ); / 默认构造函数String( void ); / 析构函数String &operate = ( const String &Source ); / 重载赋值运算符private:char *m_pData; / 指向字符串的指针;8.已知一个整数数组An，写出算法实现将奇数元素放在数组的左边，将偶数放在数组的右边。要求时间复杂度为O(n)。1. voidpartition(intA,intn)2. 3. intx;4. inti=0;5. intj=n-1;6. while(i!=j)7. 8. while(ai%2=1)9. i+;10. while(aj%2=0)11

4、. j+;12. if(ij)13. 14. x=ai;15. ai=aj;16. aj=x;17. 18. 19. 1产生死锁的四个必要条件a互斥使用（资源独占） 一个资源每次只能给一个进程使用b 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放c 请求和保持（部分分配，占有申请）一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）d循环等待存在一个进程等待队列 P1 , P2 , , Pn,其中P1等待P2占有的资源，P2等待P3占有的资源，Pn等待P1占有的资源，形成一个进程2不大于N的所有质数public class GetPrime

5、public static boolean isPrime(int num)for(int i=2;i=Math.Sqrt(num):i+)if(num%i=0)return false;return true;public static void main(String args)for(int i=2;im_pNext; / if the next node is null, the currect is theend of original / list, and its the head of the reversed list if(pNext = NULL) pReversedHe

6、ad = pNode; / reverse the linkage between nodes pNode-m_pNext = pPrev; / move forward on the the list pPrev = pNode; pNode = pNext; return pReversedHead;7、输入 x y z，然后输出序列的可能性X Y ZX Z YY X ZY Z XZ Y X8、怎么用一个类将一个实例完全复制给另外一个实例填空题 有STL库由哪部分组成，简答题： 1.冒泡排序和快速排序的优缺点 2.进程和线程共同使用的技术（好像是这么说的） 3.指针和引用的区别 4.析构函

7、数和普通成员函数的区别3.实现一个字节中空格个数不能超过一个，例如a-b-c应该输出a-b-c,此处-代表空格1. /trimastringbymakemorethanoneblanktooneblank2. char*trim(char*a)3. 4. inti=-1,j=0;5. for(;aj!=0;j+)6. 7. if(aj=aj+1&aj+1=)8. 9. /skipmorethanoneblank10. while(aj=)11. 12. +j;13. 14. -j;/gobacktothelastblank15. 16. a+i=aj;17. 18. a+i=0;19. ret

8、urna;20. 21. intmain(void)22. 23. 24. chara100=abcdef;25. print(a);26. print(trim(a);27. return0;28. 第二部分：填空题（2*6）1. 操作系统中的存储管理常用（虚拟存储器）的方式来摆脱主存容量的限制。2. 满二叉树第i层上的叶子节点数有（2的i-1次方）个。3. 二分查找算法的平均时间复杂度是（logn）。4. 设x=3，y=2，xy=（12）。5. 非成员函数应声明为类的（友元函数）才能访问这个类的private成员。6. 带有（纯虚函数）的类称为抽象类，它只能作为基类来使用。第三部分：简答题

9、（3*6）1.列举你所知道的排序算法和他们的平均时间复杂度。直接插入排序o(n*n) 希尔排序o(nlogn)冒泡排序o(n*n) 快速排序o(knlogn)直接选择排序o(n*n) 堆排序o(nlogn)归并排序o(nlogn)2.列举析构函数与普通类成员函数的不同点。析构函数无返回类型，前面有标志符，系统自动调用的。普通成员函数有返回类型，需要显式调用。3.在c+语言中使用宏定义经常会引起一下错误（如少打括号引起表达式值与预期不符等），列举一些可以替代宏定义的方法。const定义常量inline函数typedef定义别名第四部分:编程题1.裴波那絜数列的形式如下: 1 1 2 3 5 8

10、13. n，编写一个函数计算数列中第n个元素的值。int Fibonax(intn)if(n=1 | n=2) return 1;else return Fibonax(n-1)+Fibonax(n-2);2. 不调用任何系统函数，实现在一个字符串中查找子串的函数，如果包含子串，则返回该子串的位置值。（7分）int GetCommon(char*s1, char *s2, int loca)int len1 = strlen(s1);int len2 = strlen(s2);for(int i = 0; i len1; i+) if(s1i = s20) int as = i, bs = 0

11、, count = 1; while(as + 1 len1 & bs+ 1 len2 & s1+as = s2+bs) count+; if(count = len2) loca = i; return loca; 3.用算法实现将一个输入的数字颠倒，要求不调用任何系统函数，也不能将输入数字转换为字符串作为中间过渡。（8分）方法1：（字符数组，借鉴#include #include #include int main()charstr = ABCD1234efgh; intlength = strlen(str); char* p1 = str;char* p2 = str + length

12、 - 1;while(p1x) s.push(x); while (!s.empty() x = s.pop(); coutnext=first-next ; first-next=second;B、first-next=second-next；second=first；C、second-next=first-next ; second-next=first；D、first-next=second-next；second-next=first；12、以下C语言编译过程的真确步骤是（B）A、预处理 编译 汇编 连接B、预处理 编译 优化（不能少了优化） 汇编 连接C、编译 优化 汇编 运行D、编

13、辑 预处理 编译 汇编 优化 运行13、在C语言程序编译时出现如下错误：“error LNK2019：unresoved external symbolint_cdecl test（int）(?testYAHHZ) referenced”可能的原因是（D）A、函数未定义B、变量未声明C、变量未定义D、函数未声明14、下列关于C语言中的函数叙述错误的是（B）A、一个函数中可以有多条return语句B、调用函数必须要在一条独立的语句中完成C、函数可以通过return语句传递函数值D、主函数main可以带有参数15、在C语言中，打开可读写的二进制文件myfile并向该文件追加写入内容，如果myfil

14、e不存在则创建新文件，正确的调用方式为（）A、fopen（myfile,w）B、fopen（myfile，wb）C、fopen（myfile,r+b）D、fopen（myfile，a+b）a 表示追加文件内容。16、在C语言中，一个short int型数据在内存中占2字节，则short int型数据的取值范围（B）A、-256255B、-3276832767C、-6553665535D、-2147483647-214768364817、下面是对数组s的初始化，其中不正确的是（D）A、char s6=abcd;B、char s6=a,b,c,dC、char s6=;D、char s6=abcde

15、f18、有以下一段程序代码：void GetMemory（char *p，int num）*p=（char *）malloc（num）；void Test（void）char *str=NULL；GetMemory（&str，100）；strcpy（str，hello）;printf(str);请问运行Test函数会有什么样的结果（A）A、helloB、无效指针，输出不确定C、NUllD、程序崩溃19、在32位系统中，有一类：class Apublic:virtual int test();virtual double test2();int test3();protected:double

16、test4();private：int a，b，c；定义了三个变量，加上一个虚函数表指针。大小为16；请问sizeof（A）=（B）A、12B、16C、28D、32成员变量+虚函数表指针（4个字节，多个虚函数也只有一个该指针）。则所有的虚函数保存在虚函数表中，然后类中会有一个指针指向该表；这个指针需要占用空间，所以需要 +4；空类的大小为1.20、有以下一段程序代码：class Apublic:virtual void func1()printf(Asfuncl);void func2()(Asfunc2);class B:public Apublic:virtual void func1()

17、printf(Bsfuncl);void func2()(Bsfunc2);void main()B inst_b；B *ptr_a=&b;ptr_a-func1();ptr_a-func2();程序的输出结果为：（C）A、Asfuncl Bsfunc2B、Bsfuncl Asfunc2C、Bsfuncl Bsfunc2D、Asfuncl Asfunc2二、填空题1、操作系统中的存储管理常用_虚拟存储器_的方式来摆脱主存容量的限制。2、满二叉树第i层上的叶子节点数有_（）_个。3、二分查找算法平均时间复杂程度是_o（log（n）_。4、设x=3，y=2，xy=_12_。5、非成员函数声明为类的

18、_友元函数_才能访问这个类的private成员。6、带有_纯虚函数_的类称为抽象类，它只能作为基类来使用。三、简答题（每题6分，共18分）1、列举你所知道的排序算法和它们的平均复杂程度。答：1、冒泡排序（bubble sort） O(n2)2、鸡尾酒排序(Cocktail sort, 双向的冒泡排序) O(n2)3、插入排序（insertion sort） O(n2)4、选择排序（selection sort） O(n2)5、堆排序（heapsort） O(nlog n)6、快速排序（quicksort） O(nlog n)快速排序：（基于划分即分治的的思想，就是选择一个基准，使得左边小于基准

19、，右边大于基准）希尔排序：选择你一个增量，不断递减来排序。基数排序：对于整数，按照个位，十位，百位来排序O(dn)桶排序： 工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，O(n)各种排序的方式2、列举析构函数与普通类成员函数的不同点。答：1、析构函数名也应与类名相同，只是在函数名前面加一个波浪符，例如stud( )2、它不能带任何参数，也没有返回值（包括void类型）。3、只能有一个析构函数，不能重载4、析构函数在对象生存期即将结束的时刻被自动

20、调用3、在C+语言中使用宏定义经常会引起一些错误（如少打括号引起表达式值与预期不符等），列举一些可以代替宏定义的方法。内联函数从源代码层看，有函数的结构，而在编译后，却不具备函数的性质。编译时，类似宏替换。Method 1：内联函数，Method 2：const方法Method 3：typedef 方法。四、编程题（共三题20分）1、 斐波那契数列的形式如下：1,1,2,3,5,8,13，n，编写一个函数计算数列中第n个元素的值。（5分）（1）、C语言程序实现#includeint feibo(int p)if(p2)return feibo(p-1)+feibo(p-2);else return 1;void main()int i,n;long int sum=0;scanf(%d,&n);sum=feibo(n-1)+feibo(n-2);printf(%dn,sum);（2）、C+语言实现#include using namespace std;int fib(int n)coutProcessing fib(n).;if(n3)return(1);elsereturn(fib(n-2)+fib(n-1);int main()int n,answer;coutn;coutnn;answer=fib(n);coutansweris the nt