腾讯2019校园招聘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;

　　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;

　　}

　　}