3计算机招聘笔试试题精华.doc
《3计算机招聘笔试试题精华.doc》由会员分享，可在线阅读，更多相关《3计算机招聘笔试试题精华.doc（40页珍藏版）》请在冰点文库上搜索。
试题6：
voidGetMemory（char**p,intnum）
{
*p=（char*）malloc（num）;
}
voidTest（void）
{
char*str=NULL;
GetMemory（&str,100）;
strcpy（str,"hello"）;
printf（str）;
free（str）;
str=NULL;
}
答：
malloc后，应判断*p是否NULL
标准的new运算符在分配失败时，抛出一个bad_alloc类型的异常。
在任何情况下，校验标准形式new运算符返回结果
都不能起到检测错误的功效。
voidtest（void）
{
charstr=（char）malloc（100）
strcpy（str,"hello"）;
free（str）;
if（str!
=null）
{
strcpy（str “world”）;//野指针
printf（str）
}
}
请问运行test函数会有什么样的结果？
篡改动态内存区的内容，后果难以预料，非常危险。
因为free（str）之后，str成为野指针，
if（str!
=null）语句不起作用。
如果数组做函数形参，那么就蜕变为普通指针（不是指针常量），而且失去了常量性，可以被修改
voidtest（charstr[100]）{
str++;
}
试题7：
编写类String的构造函数、析构函数和赋值函数
答：
classString{
public:
String（constchar*str=NULL）;
String（constString&other）;
~String（）;
String&operator=（constString&other）;
private:
char*m_data;
};
String:
:
String（constchar*str）{
if（str==NULL）{
m_data=newchar[1];//arrarynew
}
else{
m_data=newchar[strlen（str）+1];
strcpy（m_data,str）;
}
}
String:
:
String（constString&other）{
m_data=newchar[strlen（other.m_data）+1];
strcpy（m_data,other.m_data）;
}
String:
:
~String（）{
delete[]m_data;//arraydelete
}
String&String:
:
operator=（constString&other）{
if（this==&other）
return（*this）;
delete[]m_data;
m_data=newchar[strlen（other.m_data）+1];
strcpy（m_data,other.m_data）;
return（*this）;
}
试题8：
请说出C++中static和const关键字尽可能多的作用
答：
static的作用：
1）static局部变量，作用域为本函数内，但是生存期是整个程序运行期，不同于auto变量，只初始化一次，下次调用时维持上次的值。
2）static全局变量，作用域为本文件内，生存周期是整个程序运行期
3）static全局函数，作用域为本文件内
4）类的static成员变量，该变量属于类，而不属于具体的对象，所有对象共有一份copy
5）类的static成员函数，该函数属于类，而不属于具体的对象，所有对象共有一份copy，技术层面就是该函数不接受this指针
const的作用：
1）const变量，欲阻止一个变量被改变，用const关键字。
必须定义时初始化，以后就没机会了
2）指针常量和常量指针，constchar*p，char*constp，constchar*constp
3）const形参，说明函数体不应该改变该形参的值
4）const成员函数，说明该函数不能够修改该类的成员变量，技术层面其this指针为constC*this
5）返回值为const，使得返回值不能作左值,举例
constclassAoperator*（constclassA&a1,constclassA&a2）
如果返回值不是const的，那么下面的代码也正确,而这样的操作在C++的内置类型上是不行的，
classAa,b,c;
（a*b）=c;
字符串匹配及KMP算法-----自己总结，比书上更容易懂 收藏
问题：
主串s（长度n），模式串s（长度m），从主串s中找到第一个s的位置
1.原始算法
思路：
两个指针（并不是真正的指针，方便描述而已）i和j，i指向s的元素，j指向s的元素；
如果s[i]==p[j]，那么i++，j++，往下走；
如果s[i]!
=p[j]，i回退到本次串匹配（即i-j）的下一个位置（即i-j+1），j回退到0
#include
#include
intindex（constchar*s,constchar*p）{
intn=strlen（s）;
intm=strlen（p）;
inti=0,j=0;
while（i if（s[i]==p[j]）{
i++;
j++;
}
else{
i=i-j+1;
j=0;
}
}
if（j==m）
return（i-j）;
else
return-1;
}
voidmain（）
{
char*s="abcdabcdef";
char*p="abcde";
printf（"%d\n",index（s,p））;//打印结果4
}
2.KMP算法
2.1KMP的原理
上面算法的时间复杂度O（n*m）。
大师们在大概三十年前提出了一个O（n+m）的算法，KMP算法。
KMP算法主要是解决s[i]!
=p[j]的时候，i回退的问题，就是：
当s[i]!
=p[j]时，i不回退，j回退到合适位置k，那么k如何确定？
我画了个包含i,j,k关系的图，很清晰，一看就明白了，不像书上的罗列几个式子，根本不知缘由。
如图所示，某次匹配中，要判断s[i]!
=s[j]之前，必然存在的条件：
1）si-j+1 ...si-1 =p1...pj-1
如果假设j回退到合适位置k，那么k得满足：
2）si-k+1...si-1 = pj-k+1...pj-1 =p1...pk-1
由此引入：
2.2KMP的next[j]在C语言中定义
2.3KMP算法实现
把上面的原始算法稍微改动就得到KMP算法：
intkmp_index（constchar*s,constchar*p,int*index）{
intn=strlen（s）;
intm=strlen（p）;
inti=0,j=0;
while（i if（（j==-1）||（s[i]==p[j]））{//注意j==-1，说明p[0]和当前的p[j]不相等，
i++;
j++;
}
else{
j=next[j];
}
}
if（j==m）
return（i-j）;
else
return-1;
}
计算next[j]，这个从人的直觉上很容易求出来：
j-1之前，p的前k个字符和后k个字符相同的最大k值。
怎么用计算机来写程序呢？
求next[j]自身也是一个串匹配的问题，可以用我们在1.原始算法的方法来求（此处略），
也可以模仿上面的kmp_index来写，首先看个例子：
j 0 1 2 3 4 5 6 7
a b a a b c a c
next[j]-10 0 1 1 2 0
next[0]:
-1;
next[1]:
next[0]是-1，所以next[1]=0（-1++）；
next[2]:
next[1]是0，p[1]!
=p[0]，继续，next[0]是-1，所以next[2]=0（-1++）；
next[3]:
next[2]是0，p[2]==p[0],所以next[3]是1（0++）；
....
求next[5]：
next[4]是1，因为p[4]==p[1],所以next[5]=2（1++）;
求next[6]：
next[5]是2，因为p[5]!
=p[2],继续，next[2]是0，因为p[5]!
=p[0],继续，next[0]是-1,所以next[6]=0（-1++）;
求next[7]：
next[6]是0，因为p[6]==p[0],所以next[6]=1（0++）;
Oulipo
TimeLimit:
1000MS
MemoryLimit:
65536K
TotalSubmissions:
7395
Accepted:
2879
Description
TheFrenchauthorGeorgesPerec（1936–1982）oncewroteabook,Ladisparition,withouttheletter 'e'.HewasamemberoftheOulipogroup.Aquotefromthebook:
ToutavaitPairnormal,maistouts’affirmaitfaux.ToutavaitFairnormal,d’abord,puissurgissaitl’inhumain,l’affolant.Ilauraitvoulusavoiroùs’articulaitl’associationquil’unissaitauroman:
stirsontapis,assaillantàtoutinstantsonimagination,l’intuitiond’untabou,lavisiond’unmalobscur,d’unquoivacant,d’unnon-dit:
lavision,l’avisiond’unoublicommandanttout,oùs’abolissaitlaraison:
toutavaitl’airnormalmais…
Perecwouldprobablyhavescoredhigh（orrather,low）inthefollowingcontest.Peopleareaskedtowriteaperhapsevenmeaningfultextonsomesubjectwithasfewoccurrencesofagiven“word”aspossible.Ourtaskistoprovidethejurywithaprogramthatcountstheseoccurrences,inordertoobtainarankingofthecompetitors.Thesecompetitorsoftenwriteverylongtextswithnonsensemeaning;asequenceof500,000consecutive 'T'sisnotunusual.Andtheyneverusespaces.
Sowewanttoquicklyfindouthowoftenaword,i.e.,agivenstring,occursinatext.Moreformally:
giventhealphabet{'A', 'B', 'C',…, 'Z'}andtwofinitestringsoverthatalphabet,aword W andatext T,countthenumberofoccurrencesof W in T.AlltheconsecutivecharactersofWmustexactlymatchconsecutivecharactersof T.Occurrencesmayoverlap.
Input
Thefirstlineoftheinputfilecontainsasinglenumber:
thenumberoftestcasestofollow.Eachtestcasehasthefollowingformat:
·Onelinewiththeword W,astringover{'A', 'B', 'C',…, 'Z'},with1≤|W|≤10,000（here|W|denotesthelengthofthestring W）.
·Onelinewiththetext T,astringover{'A', 'B', 'C',…, 'Z'},with|W|≤|T|≤1,000,000.
Output
Foreverytestcaseintheinputfile,theoutputshouldcontainasinglenumber,onasingleline:
thenumberofoccurrencesoftheword W inthetext T.
SampleInput
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
SampleOutput
1
3
0
KMP算法，套模板
#include
#include
charW[100001],T[1000001];
intnext[100001];
intL0,L1;
/*自匹配函数*/
/*预先计算每个位置发生不匹配的时候,把位置存到next里*/
voidPreFix（）
{
inti,j;
L0=strlen（W）;
next[0]=-1;
j=-1;
for（i=1;i{
while（j>=0&&W[j+1]!
=W[i]）
j=next[j];
if（W[j+1]==W[i]）
j++;
next[i]=j;
}
}
/*匹配函数*/
/*进行W与T的匹配,
*当W[j+1]与T[i]不匹配时,j回到最近的能够匹配的位置next[j]*/
intMatch（）
{
inti,j,M;
L1=strlen（T）;
j=-1;
M=0;
for（i=0;i{
while（j>=0&&W[j+1]!
=T[i]）
j=next[j];
if（W[j+1]==T[i]）
j++;
if（j==L0-1）
{
j=next[j];
M++;
}
}
returnM;
}
intmain（）
{
intt;
scanf（"%d",&t）;
while（t--）
{
scanf（"%s%s",W,T）;
PreFix（）;
printf（"%d\n",Match（））;
}
return0;
}
C/C++常见面试题（8）----平衡二叉树（AVL树） 收藏
平衡二叉树的旋转，查找，插入节点，删除节点
平衡二叉树，（AVL树，BalencedBinarySearchTree）。
1.定义
1）是一棵二叉查找树（BST）
2）任意一棵子树，其左右子树的高度差不大于1
由于实现起来要考虑不少细节，所以本篇不再提供代码，主要描述思路。
其实思路有了，问题解决起来就容易了；如果没有思路，一切都白扯。
1.1查找
查找算法和BST一样
1.2四种旋转
1.2.1LL型
structAVLTreeNode{
intdata;
intbf;//balancefactor
structAVLTreeNode*left,*right;
};
voidr_rotate（AVLTreeNode*p）{
...
AVLTreeNode*tmp;
tmp=p->left;
p->left=tmp->right;
tmp->right=p;
...
}
1.2.2RR型
voidl_rotate（AVLTreeNode*p）{
...
AVLTreeNode*tmp;
tmp=p->right;
p->right=tmp->left;
tmp->left=p;
...
}
1.2.3LR
voidlr_rotate（AVLTreeNode*p）{
...
l_rotate（p->left）;
r_roteate（p）;
...
}
1.2.4RL
voidrl_rotate（AVLTreeNode*p）{
...
r_rotate（p->right）;
l_roteate（p）;
...
}
#include
#include
classValue
{
public:
Value（intnVal）{
m_nVal=nVal;
printf（"CallValue:
:
Value（intnValue）\n"）;
}
~Value（）{
printf（"CallValue:
:
~Value（）\n"）;
}
Value&operator=（intnVal）
{
m_nVal=nVal;
printf（"CallValue:
:
operator=\n"）;
return*this;
}
voidDump（）{
printf（"Value:
:
m_nVal=%d\n",m_nVal）;
}
protected:
intm_nVal;
};
classBase
{
public:
Base（）{
Init（）;
}
virtual~Base（）{
Release（）;
}
virtualvoidInit（）{
printf（"CallBase:
:
Init（）\n"）;
}
virtualvoidRelease（）{
printf（"CallBase:
:
Release（）\n"）;
}
virtualvoidDump（）{
printf（"CallBase:
:
Dump（）\n"）;
}
};
classDerive:
publicBase
{
public:
Derive（）{
printf（"CallDerive:
:
Derive（）\n"）;
}
~Derive（）{
printf（"CallDerive:
:
~Derive（）\n"）;
}
virtualvoidInit（）{
m_Val=2;
printf（"CallDerive:
:
Init（）\n"）;
}
virtualvoidRelease（）{
printf（"CallDerive:
:
Release（）\n"）;
}
virtualvoidDump（）{
m_Val.Dump（）;
}
protected:
升级会员 