招聘笔试题

腾讯校园招聘C语言笔试题和面试题答案目(一)

1. 输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:

struct ListNode

{

int m_nKey;

ListNode m_pNext;

};

A: 递归方法逆序输出,栈方法逆序输出。

(任意实现一种既可)

void PrintListUsingRecursicve(pListNode head)

{

if(head!=NULL)

{

PrintListUsingRecursicve(head->m_pNext);

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

}

}

void PrintListUsingStack(pListNode head)

{

Stack s;

s.top=0;

pListNode p=head;

do{

push(&s,p->m_nKey);

p=p->m_pNext;

}while(p!=NULL);

while(!IsEmpty(&s))

{

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

}

}

2. 二元树的深度

题目:输入一棵二元树的根结点,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

#include

#include

#include

#include

#define MAXLEN 100

#define MAXNUM 10

typedef int Tree[MAXLEN];

Tree bt;

int GetDeep(int i)

{

int l=0,r=0;

if(bt[i2]!=-1)

{

l=GetDeep(i2)+1;

}

if(bt[i2+1]!=-1)

{

r= GetDeep(i2+1)+1;

}

return l>r?l:r;

}

int main()

{

int i=0;

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

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

bt[i]=i;

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

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

return 0;

}

3. 整数的二进制表示中1的个数

题目:输入一个整数,求该整数的二进制表达中有多少个1。例如输入10,由于其二进制表示为1010,有两个1,因此输出2。

(关键是能不能想到后面的那个方法,只要想到这个方法既可)

int Bit1inInt(int i)

{

int result=0;

do{

result+=i&1;

}while(i=i>>1);

return result;

}

4. 从上往下遍历二元树

题目:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。

(先序,中序,后序三种方式实现)

如果从上往下,从左到右的话只有一种遍历的方式:广度优先遍历。

#include

#include

#include

#include

#define MAXLEN 100

#define MAXNUM 10

typedef int Tree[MAXLEN];

Tree bt;

typedef struct queue

{

int begin,end;

int space[MAXLEN];

}Queue;

int main()

{

int i=0;

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

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

bt[i]=i;

Queue qe;

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

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

while(qe.begin!=qe.end)

{

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

{

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

}

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

{

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

}

qe.begin++;

}

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

for(i=0;i

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

return 0;

}

先序,中序,后序三种方式的只是遍历二元树

typedef int Tree[MAXLEN];

Tree bt;

void PreOrderTraverse(int i)

{

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

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

PreOrderTraverse(i2);//lchild

PreOrderTraverse(i2+1);//rchild

}

void InOrderTraverse(int i)

{

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

InOrderTraverse(i2);//lchild

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

InOrderTraverse(i2+1);//rchild

}

void PostOrderTraverse(int i)

{

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

PostOrderTraverse(i2);//lchild

PostOrderTraverse(i2+1);//rchild

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

}

int main()

{

int i=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);

return 0;

}

5. 查找链表中倒数第k个结点

题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下:

struct ListNode

{

int m_nKey;

ListNode m_pNext;

};

(最快的方法,只遍历一遍)

int FindCoundDownInList(pListNode head,int num)

{

pListNode p1,p2;

p1=p2=head;

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

if(p1==NULL) return 0;

else{

while(p1!=NULL)

{

p1=p1->m_pNext;

p2=p2->m_pNext;

}

return p2->m_nKey;

}

}

大家都在看