騰訊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;

　　}

　　}