騰訊2014校園招聘C語言筆試題（附答案）

1.

輸入一個鏈表的頭結(jié)點，從尾到頭反過來輸出每個結(jié)點的值。鏈表結(jié)點定義如下：structListNode{

int

m_nKey;

ListNode*m_pNext;};A:

遞歸方法逆序輸出，棧方法逆序輸出。(任意實現(xiàn)一種既可)voidPrintListUsingRecursicve(pListNodehead){

if(head!=NULL)

{

PrintListUsingRecursicve(head->m_pNext);

printf("%d/n",head->m_nKey);

}}voidPrintListUsingStack(pListNodehead){

Stacks;

s.top=0;

pListNodep=head;

do{

push(&s,p->m_nKey);

p=p->m_pNext;

}while(p!=NULL);

while(!IsEmpty(&s))

{

printf("%d/n",pop(&s));

}}2.

二元樹的深度題目：輸入一棵二元樹的根結(jié)點，求該樹的深度。從根結(jié)點到葉結(jié)點依次經(jīng)過的結(jié)點（含根、葉結(jié)點）形成樹的一條路徑，最長路徑的長度為樹的深度。#include<stdio.h>#include<stdlib.h>#include<string.h>#include<time.h>#defineMAXLEN100#defineMAXNUM10typedefintTree[MAXLEN];Treebt;intGetDeep(inti){

intl=0,r=0;

if(bt[i*2]!=-1)

{

l=GetDeep(i*2)+1;

}

if(bt[i*2+1]!=-1)

{

r=GetDeep(i*2+1)+1;

}

returnl>r?l:r;}intmain(){

inti=0;

memset(bt,-1,sizeof(bt));

for(i=1;i<=MAXNUM;i++)

bt[i]=i;

bt[(i-1)*2]=i*2;

printf("%d/n",GetDeep(1));

return0;}

3.

整數(shù)的二進制表示中1的個數(shù)題目：輸入一個整數(shù)，求該整數(shù)的二進制表達中有多少個1。例如輸入10，由于其二進制表示為1010，有兩個1，因此輸出2。（關(guān)鍵是能不能想到后面的那個方法，只要想到這個方法既可）intBit1inInt(inti){

intresult=0;

do{

result+=i&1;

}while(i=i>>1);

returnresult;}

4.

從上往下遍歷二元樹題目：輸入一顆二元樹，從上往下按層打印樹的每個結(jié)點，同一層中按照從左往右的順序打印。

（先序，中序，后序三種方式實現(xiàn)）如果從上往下，從左到右的話只有一種遍歷的方式：廣度優(yōu)先遍歷。#include<stdio.h>#include<stdlib.h>#include<string.h>#include<time.h>#defineMAXLEN100#defineMAXNUM10typedefintTree[MAXLEN];Treebt;typedefstructqueue{

intbegin,end;

intspace[MAXLEN];}Queue;intmain(){

inti=0;

memset(bt,-1,sizeof(bt));

for(i=1;i<=MAXNUM;i++)

bt[i]=i;

Queueqe;

qe.begin=0;qe.end=0;

qe.space[qe.end++]=bt[1];

while(qe.begin!=qe.end)

{

if(bt[2*qe.space[qe.begin]]!=-1)//lchild

{

qe.space[qe.end++]=bt[2*qe.space[qe.begin]];

}

if(bt[2*qe.space[qe.begin]+1]!=-1)//rchild

{

qe.space[qe.end++]=bt[2*qe.space[qe.begin]+1];

}

qe.begin++;

}

printf("--------------------/n");

for(i=0;i<qe.end;i++)

printf("%d",qe.space[i]);

return0;}

先序，中序，后序三種方式的只是遍歷二元樹typedefintTree[MAXLEN];Treebt;voidPreOrderTraverse(inti){

if(bt[i]==-1){return;}

printf("%d",bt[i]);

PreOrderTraverse(i*2);//lchild

PreOrderTraverse(i*2+1);//rchild}voidInOrderTraverse(inti){

if(bt[i]==-1){return;}

InOrderTraverse(i*2);//lchild

printf("%d",bt[i]);

InOrderTraverse(i*2+1);//rchild}voidPostOrderTraverse(inti){

if(bt[i]==-1){return;}

PostOrderTraverse(i*2);//lchild

PostOrderTraverse(i*2+1);//rchild

printf("%d",bt[i]);}

intmain()

{

inti=0;

memset(bt,-1,sizeof(bt));

for(i=1;i<=MAXNUM;i++)

bt[i]=i;

printf("/n---------------/n");

PreOrderTraverse(1);

printf("/n---------------/n");

InOrderTraverse(1);

printf("/n---------------/n");

PostOrderTraverse(1);

return0;

}

5.

查找鏈表中倒數(shù)第k個結(jié)點題目：輸入一個單向鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。鏈表的倒數(shù)第0個結(jié)點為鏈表的尾指針。鏈表結(jié)點定義如下：structListNode{

int

m_nKey;

ListNode*m_pNext;};

（最快的方法，只遍歷一遍）intFindCoundDownInList(pListNodehead,intnum){

pListNodep1,p2;

p1=p2=head;

while(num-->0&&p1!=NULL)p1=p1->m_pNext;

if(p1==NULL)return0;

else{

while(p1!=NULL)

{

p1=p1->m_pNext;

p2=p2->m_pNext;

}

returnp2->m_nKey;

}}6.

求三角形面積給出三角形的三個邊長為a、b、c，求三角形的面積。

（注意考慮是不是三角形）

doubleGetArea(inta,intb,intc){

if(a-b>=c||a+b<=c)

return-0.1;

else{

doubles=0.5*(a+b+c);

doublearea=sqrt(s*(s-a)*(s-b)*(s-c));

returnarea;

}}7.

壓縮字符串例如字串”aaabbbbccccc”，轉(zhuǎn)換成相鄰字符+個數(shù)的形式壓縮，成為”a3b4c5”。

（如果有10個數(shù)相同）

假設(shè)需要考慮解壓縮char*MergeString(constchar*ch){

char*s=(char*)malloc(sizeof(ch));

if(s!=NULL)

{

intlen=strlen(ch),i=0,j=0,k=0;

for(;i<len;i=j)

{

intnum=0;

while(ch[j]==ch[i])j++,num++;

s[k++]=ch[i];

sprintf(s+k,"%d",num);

k=strlen(s);

}

}

returns;}

8.

如何判斷一個單向鏈表是否有環(huán)。intISCircle(pListNodehead){

pListNodep1=head;

p1=p1->m_pNext;

while(p1!=NULL)

{

if(p1==head)return1;

elsep1=p1->m_pNext;

}

return0;}

9.

判斷一個字符串是否對稱。aabbaa,efffe返回trueaabac返回falseint

SymmetricString(constchar*ch){

intlen=strlen(ch);

inti=0,j=len-1;

if(len%2!=0)return0;

for(i=0,j=len-1;i<=len/2;i++,j--)

{

if(ch[i]!=ch[j])return0;

}

return1;}

10.

判斷一個字符串是否是另一個字符串的字串

intnext[20];voidget_next(constchar*T,intnext[]){

inti=0,j=-1;next[0]=-1;

intlen=strlen(T);

while(i<len)

{

if(j==-1||T[i]==T[j]){++i;++j;next[i]=j;}

elsej=next[j];

}}intindex_KMP(constchar*S,constchar*T){

int

i=0,j=0;

get_next(T,next);

intlens=strlen(S),lent=strlen(T);

while(i<lens&&j<lent){

if(j==-1||S[i]==T[j]){++i;++j;}

elsej=next[j];

}

if(j>=lent)returni-lent;

elsereturn-1;}

鏈表的定義，棧的定義：typedefstructstack{

inttop;

intspace[MAXLEN+1];}Stack;intpush(Stack*s,intnum){

if(s->top>=sizeof(s->space)/sizeof(int))return-1;//Error

s->space[s->top++]=num;

returnnum;}intpop(Stack*s){

if(s->top<0)return-1;

returns->space[--s->top];}intIsEmpty(Stack*s){

returns->top==0;}typedefstructListNode{

intm_nKey;

structListNode*m_pNext;}ListNode,*pListNode;pListNodeCreateList(){

srand((unsignedlong)time(NULL));

pListNodehead,p1,p2;

head=(pListNode)malloc(sizeof(ListNode));

p1=head;p2=p1;

inti=MAXLEN;

while