资源描述
第一题是递归判断五子棋问题，在一个棋盘上，0代表空，1代表黑子，2代表白子，现给定一个坐标(ax,ay),代表当前下的黑子的位置，求递归判断黑子是否已经赢了(不考虑赢的趋势，也即仅仅判断当前状态)
然后就是问如何求1到1000000内所有素数，(相信弄过一点算法都清楚筛选法)
最后问了个如何在一个序列中求第k大的数，笔者当时脑袋一热回答了二叉搜索树+优先级(也OK)，面试官听完后就来了句，不就是堆嘛。。。
1. 已知二叉树的前序遍历为ABCDEFGHIJ，中序遍历为CBEDAHGIJF，请画出其二叉树结构。
2.求一个整数数组的最大元素，用递归方法实现。
1. <span>#include <iostream>
2. #include <cmath>
3. using namespace std;
4.
5. int maxnum(int a[], int n)
6. {
7. if(n == 1)
8. return a[0];
9. if(n>1)
10. {
11. return max(a[0], maxnum(a+1,n-1));
12. }
13. }
14. int main()
15. {
16. int num[10] = {0,1,2,3,4,5,6,7,8,9};
17. cout<<maxnum(num,10)<<endl;
18. return 0;
3.什么是虚拟存储器？虚拟存储器的特点是什么？
虚拟存储器：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。
特点：多次性、对换性、虚拟性。
多次性是指一个作业被分成多次调入内存运行，亦即在作业运行时没有必要将其全部装入，只需将当前要运行的那部分程序和数据装入内存即可；以后每当要运行到尚未调入的那部分程序时，再将它调入。
对换性是指允许在作业的运行过程中进行换进、换出，亦即，在进程运行期间，允许将那些暂不使用的程序和数据，从内存调至外村的对换区（换出），待以后需要时再将它们从外存调至内存（换进）。
虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。
4.什么是this指针？其主要功能是什么？
this指针是类的一个自动生成、自动隐藏的私有成员，它存在于类的非静态成员函数中，指向被调用函数所在的对象的地址。全局仅有一个this指针，当一个对象被创建时，this指针就指向对象数据的首地址。
一种情况就是，在类的非静态成员函数中返回类对象本身的时候，直接使用
return *this；另外一种情况是当参数与成员变量名相同时使用this指针，如this->n = n （不能写成n
= n）。
7.写出字符串类的必备构造函数和赋值运算符重载的实现方法。
已知类String的原型为：
class String
{
public:
String( const char *pStr = NULL ); // 默认构造函数
~String( void ); // 析构函数
String &operate = ( const String &Source ); // 重载赋值运算符
private:
char *m_pData; // 指向字符串的指针
};
8.已知一个整数数组A[n]，写出算法实现将奇数元素放在数组的左边，将偶数放在数组的右边。要求时间复杂度为O(n)。
1. <span>void partition(int A[], int n)
2. {
3. int x;
4. int i = 0;
5. int j = n-1;
6. while(i != j)
7. {
8. while( a[i]%2 == 1)
9. i++;
10. while (a[j]%2 == 0)
11. j++;
12. if(i < j)
13. {
14. x = a[i];
15. a[i] = a[j];
16. a[j] = x;
17. }
18. }
19. }
1产生死锁的四个必要条件
a互斥使用（资源独占） 一个资源每次只能给一个进程使用
b 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放
c 请求和保持（部分分配，占有申请）
一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）
d循环等待
存在一个进程等待队列 {P1 , P2 , … , Pn},其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程
2不大于N的所有质数
public class GetPrime
{
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;i<=N;i++)
{
if(isPrime(i))
{
System.out.println(i+"is a Prime");
}
}
}
3共享内存，管道，文件，socket传输的优缺点
Linux 进程间通信 linux下进程间通信的几种主要手段简介：
管道（Pipe）及有名管道（named pipe）：管道可用于具有亲缘关系进程间的通信，有名管道克服了管道没有名字的限制，因此，除具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。
信号（Signal）：信号是比较复杂的通信方式，用于通知接受进程有某种事件发生，除了用于进程间通信外，进程还可以发送信号给进程本身；linux除了支持Unix早期信号语义函数sigal外，还支持语义符合Posix.1标准的信号函数sigaction（实际上，该函数是基于BSD的，BSD为了实现可靠信号机制，又能够统一对外接口，用sigaction函数重新实现了signal函数）；
报文（Message）队列（消息队列）：消息队列是消息的链接表，包括Posix消息队列system V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。
共享内存：使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。 往往与其它通信机制，如信号量结合使用，来达到进程间的同步及互斥。
信号量（semaphore）：主要作为进程间以及同一进程不同线程之间的同步手段。
套接口（Socket）：更为一般的进程间通信机制，可用于不同机器之间的进程间通信。起初是由Unix系统的BSD分支开发出来的，但现在一般可以移植到其它类Unix系统上：Linux和System V的变种都支持套接字。
由于要考虑跨平台，首先砍掉一批（关于IPC的跨平台问题，我在“跨平台开发”系列中会提到）。剩下的IPC类型中，能够进行数据传输的IPC就不多了，主要有如下几种：套接字（以下简称Socket）、共享内存、管道、文件。其中Socket是我强烈推荐的IPC方式，
理由如下：使用Socket可以天然地支持分布式部署；
使用Socket可以比较容易地实现多种编程语言的混合（比如C++、Java、Python、Flex都支持Socket）；
使用Socket还可以省掉了一大坨“锁操作”的代码。
列位看官中，或许有人在担心Socket的性能问题，其实大可不必多虑。当两个进程在本机上进行Socket通讯时，由于可以使用localhost环回地址，数据不用经过物理网卡，操作系统内核还可以进行某些优化。这种情况下，Socket相对其它几种IPC机制，不会有太大的性能偏差。
最后再补充一下，Socket方式也可以有效防止扯皮问题。举个例子：张三写了一个进程A，李四写了一个进程B，进程A通过Socket方式发数据给进程B。突然有一天，两个进程的通讯出故障了。然后张三就说是李四接收数据出错；李四就说张三发送数据出错。这时候怎么办捏？很简单，随便找个Sniffer软件当场抓一下数据包并Dump出来看，问题就水落石出了。
4、 TCP/IP建立连接过程
在TCP/IP协议中，TCP协议提供可靠的连接服务，采用三次握手建立一个连接。
第一次握手：建立连接时，客户端发送syn包(syn=j)到服务器，并进入SYN_SEND状
态，等待服务器确认；
第二次握手：服务器收到syn包，必须确认客户的SYN（ack=j+1），同时自己也发送一个
SYN包（syn=k），即SYN+ACK包，此时服务器进入SYN_RECV状态；
第三次握手：客户端收到服务器的SYN＋ACK包，向服务器发送确认包ACK(ack=k+1)，此包发送完毕，客户端和服务器进入ESTABLISHED状态，完成三次握手。
式查询创建视图.查询只从包含查询所需数据的远程服务器的表中读取所需的数据.被分布式查询引用的其他服务器,在视图中都将不会被访问.
6、题目：输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。链表结点定义如下：
Struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
ListNode *ReverseIteratively(ListNode* pHead)
{
ListNode* pReversedHead = NULL;
ListNode* pNode = pHead;
ListNode* pPrev = NULL;
while(pNode != NULL)
{
// get the next node, and save it at pNext
ListNode* pNext = pNode->m_pNext;
// if the next node is null, the currect is theend of original
// list, and it's the head of the reversed list
if(pNext == NULL)
pReversedHead = 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 Z
X Z Y
Y X Z
Y Z X
Z Y X
8、怎么用一个类将一个实例完全复制给另外一个实例
填空题 有STL库由哪部分组成，
简答题： 1.冒泡排序和快速排序的优缺点
2.进程和线程共同使用的技术（好像是这么说的）
3.指针和引用的区别
4.析构函数和普通成员函数的区别
3.实现一个字节中空格个数不能超过一个，例如a--b-c应该输出a-b-c,此处-代表空格
1. //trim a string by make more than one blank to one blank
2. char* trim(char* a)
3. {
4. int i=-1,j=0;
5. for (;a[j]!='\0';j++)
6. {
7. if (a[j]==a[j+1] && a[j+1]==' ')
8. {
9. //skip more than one blank
10. while (a[j]==' ')
11. {
12. ++j;
13. }
14. --j;// go back to the last blank
15. }
16. a[++i]=a[j];
17. }
18. a[++i]='\0';
19. return a;
20. }
21. int main( void )
22. {
23.
24. char a[100]="a b c d e f";
25. print(a);
26. print(trim(a));
27. return 0;
28. }
第二部分：填空题（2*6）
1. 操作系统中的存储管理常用（虚拟存储器）的方式来摆脱主存容量的限制。
2. 满二叉树第i层上的叶子节点数有（2的i-1次方）个。
3. 二分查找算法的平均时间复杂度是（logn）。
4. 设x=3，y=2，x<<y=（12）。
5. 非成员函数应声明为类的（友元函数）才能访问这个类的private成员。
6. 带有（纯虚函数）的类称为抽象类，它只能作为基类来使用。
第三部分：简答题（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 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(s1[i] == s2[0])
{
int as = i, bs = 0, 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 <stdio.h>
#include <string.h>
#include <dos.h>
int main()
{
charstr[] = "ABCD1234efgh";
intlength = strlen(str);
char* p1 = str;
char* p2 = str + length - 1;
while(p1< p2)
{
char c = *p1;
*p1 = *p2;
*p2 = c;
++p1;
--p2;
}
printf("strnow is %s\n",str);
system("pause");
return0;
}
方法2：递归或栈
void reverse()
{
stack s;
int x;
while (cin>>x)
{
s.push(x);
}
while (!s.empty())
{
x = s.pop();
cout<<x;
}
}
一、单选题
2、有一盆衣服（已经洗过了，需要漂洗），请问在漂洗次数固定的情况下如何分配水才能把衣服洗得最干净（C）
A、从少到多 B、从多到少
C、平均分配，是求函数极值问题 D、随便洗
3、用力拉一根橡皮筋，橡皮筋上有没有点还处在原来的位置没有被拉走（B）
A、有 B、没有
C、有是有、有时没有 D、一般人拉没有，刘谦拉就有
4、假设一个应用程序需要使用多个提供不同功能但在皆接口上有差异的类，适合使用的设计模式是（D(确定)）
A、装饰模式 B、迭代器模式
装饰模式是在不必改变原类文件和使用继承的情况下，动态的扩展一个对象的功能。它是通过创建一个包装对象，也就是装饰来包裹真实的对象。
迭代器模式是一种设计模式，是一种最简单也最常见的设计模式。它可以让使用者透过特定的接口巡访容器中的每一个元素而不用了解底层的实作。
C、工厂模式 D、适配器模式
5、结构化程序设计主要强调的是（C）
A、程序的规模 B、程序的效率
C、程序的易读性 D、程序设计语言的先进性
6、SQL Server中，删除一个表的命令是（C）
A、DELETE B、CLEAR C、DROP D、REMOVVE
7、以下关于互斥量说法错误的是：（B）
A、单线程程序不需要使用互斥量
B、互斥量可以被两个以上的线程锁定
C、互斥量的激活是原子操作
D、互斥量的创建和销毁可以在不同的线程进行
8、在Windows任务管理器中发现某个进程CPU占用率长时间处于100%,以下可能导致该现象的原因是（D）
A、程序处于大量I/O过程中 B、多线程导致进程死锁
C、等带另一个程序响应 D、程序进入死循环
9、假设进程中一个生产者线程，10个消费者线程，为保证进程间不出现死锁，信号量的初值可以设置为（C）
A、-1 B、0
C、1 D、10
10、使用两个栈共享一片空间时，当（D）时，才产生溢出
A、其中一个栈的栈底到达这片内存空间的中心点
B、其中一个栈的栈顶到达这片内存空间的中心点
C、两个栈均不空，且一个栈的栈顶到达另一个栈的栈底（不可能发生这种情况）
D、两个栈的栈顶在这片内存空间的某一位置相遇
11、在一个单链表HL中，若要在指针所指节点的后面插入一个有指针second所指向的节点，则执行（A）
A、second->next=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、在C语言程序编译时出现如下错误：
“error LNK2019：unresoved external symbol"int__cdecl test（int）"(?test@@YAHH@Z) referenced”可能的原因是（D）
A、函数未定义 B、变量未声明 C、变量未定义 D、函数未声明
14、下列关于C语言中的函数叙述错误的是（B）
A、一个函数中可以有多条return语句
B、调用函数必须要在一条独立的语句中完成
C、函数可以通过return语句传递函数值
D、主函数main可以带有参数
15、在C语言中，打开可读写的二进制文件myfile并向该文件追加写入内容，如果myfile不存在则创建新文件，正确的调用方式为（D）
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、-256~255 B、-32768~32767
C、-65536~65535 D、-2147483647-2147683648
17、下面是对数组s的初始化，其中不正确的是（D）
A、char s[6]={"abcd"}; B、char s[6]={'a','b','c','d'}
C、char s[6]="" ; D、char s[6]="abcdef"
18、有以下一段程序代码：
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、hello B、无效指针，输出不确定
C、NUll D、程序崩溃
19、在32位系统中，有一类：
class A
{
public:
virtual int test();
virtual double test2();
int test3();
protected:
double test4();
private：
int a，b，c；定义了三个变量，加上一个虚函数表指针。大小为16
}；
请问sizeof（A）=（B）
A、12 B、16 C、28 D、32
成员变量+虚函数表指针（4个字节，多个虚函数也只有一个该指针）。
则所有的虚函数保存在虚函数表中，然后类中会有一个指针指向该表；这个指针需要占用空间，所以需要 +4；
空类的大小为1.
20、有以下一段程序代码：
class A
{
public:
virtual void func1(){printf("A'sfuncl");}
void func2(){("A'sfunc2")};
}
class B:public A
{
public:
virtual void func1(){printf("B'sfuncl");}
void func2(){("B'sfunc2")};
}
void main()
{
B inst_b；
B *ptr_a=&b;
ptr_a->func1();
ptr_a->func2();
}
程序的输出结果为：（C）
A、A'sfuncl B'sfunc2 B、B'sfuncl A'sfunc2
C、B'sfuncl B'sfunc2 D、A'sfuncl A'sfunc2
二、填空题
1、操作系统中的存储管理常用__虚拟存储器__的方式来摆脱主存容量的限制。
2、满二叉树第i层上的叶子节点数有_２^（ｉ－１）___个。
3、二分查找算法平均时间复杂程度是___o（log（n））_____。
4、设x=3，y=2，x<<y=___12___。
5、非成员函数声明为类的__友元函数_____才能访问这个类的private成员。
6、带有____纯虚函数____的类称为抽象类，它只能作为基类来使用。
三、简答题（每题6分，共18分）
1、列举你所知道的排序算法和它们的平均复杂程度。
答：1、冒泡排序（bubble sort） — O(n^2)
2、鸡尾酒排序(Cocktail sort, 双向的冒泡排序) — O(n^2)
3、插入排序（insertion sort）— O(n^2)
4、选择排序（selection sort）— O(n^2)
5、堆排序（heapsort）— O(nlog n)
6、快速排序（quicksort）— O(nlog n)
快速排序：（基于划分即分治的的思想，就是选择一个基准，使得左边小于基准，右边大于基准）
希尔排序：选择你一个增量，不断递减来排序。
基数排序：对于整数，按照个位，十位，百位来排序O(dn)
桶排序： 工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，O(n)
各种排序的方式
2、列举析构函数与普通类成员函数的不同点。
答：1、析构函数名也应与类名相同，只是在函数名前面加一个波浪符~，例如~stud( )
2、它不能带任何参数，也没有返回值（包括void类型）。
3、只能有一个析构函数，不能重载
4、析构函数在对象生存期即将结束的时刻被自动调用
3、在C++语言中使用宏定义经常会引起一些错误（如少打括号引起表达式值与预期不符等），列举一些可以代替宏定义的方法。
内联函数从源代码层看，有函数的结构，而在编译后，却不具备函数的性质。编译时，类似宏替换。
Method 1：内联函数，
Method 2：const方法
Method 3：typedef 方法。
四、编程题（共三题20分）
1、 斐波那契数列的形式如下：1,1,2,3,5,8,13……，n，编写一个函数计算数列中第n个元素的值。（5分）
（1）、C语言程序实现
#include<stdio.h>
int feibo(int p)
{
if(p>2)
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("%d\n",sum);
}
（2）、C++语言实现
#include <iostream>
using namespace std;
int fib(int n)
{
cout<<"Processing fib("<<n<<")...";
if(n<3)
{return(1);}
else
{return(fib(n-2)+fib(n-1));}
}
int main()
{
int n,answer;
cout<<"Enter number:";
cin>>n;
cout<<"\n\n";
answer=fib(n);
cout<<answer<<"is the "<<n<<"th Fibonacci number\n";
return 0;
}
int fabnc(int n)
{
if (n==1||n==0)
{
return 1;
}
else
return fabnc(n-1)+fabnc(n-2);
}
2、不调用任何系统函数，实现一个字符串查找子串的函数，如果包含字串，则返回该字符串的位置值，如果不包含，则返回-1。（7分）
int substring(char* str,char* substr)
{
char* p,*q;
char* temp;
p=str;
q=substr;
int count=1;
while (*p!='\0')
{
while (*p!=*q)
{
p++;
count++;
}
temp=p;
if (*p=='\0')
{
return -1;
}
while((*p==*q)&&*q!='\0')
{
p++;
q++;
}
if (*q!='\0')
{
p=temp+1;
q=substr;
count++;
}
else
break;
}
cout<<*p<<" "<<*q<<endl;
if (*q=='\0')
{
return count;
}
else
{
p=NULL;
q=NULL;
temp=NULL;
return -1;
}
}
分两步，
第一步：找到字符串中与子串首字符相等的字符在字符串中的位置。
第二步：比较以后的字符是否相等。如果不等，记录上次找到的第一次相等的位置，从这以后再寻找找到字符串中与子串首字符相等的字符在字符串中的位置。
然后再比较以后的字符是否相等。
2、 用算法实现将一个输入的数字颠倒（输入12345->54321），要求不调用任何系统函数，也不能将输入的数字转换为字符串作为中间过渡。（8分）
#include <iostream>
using namespace std;
int revernum(int num)
{
int a[15];
int b,temp;
int revernum=0;
while (num!=0)
{
b=num%10;
revernum=(revernum*10)+b;
num=num/10;
}
return revernum;
}
int main()
{
int num;
int num1=56435;
cout<<"please input the test number"<<endl;
cin>>num;
cout<<revernum(num)<<endl;
system("pause");
}
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
