腾讯2014校园招聘C语言笔试题

发布时间:2014-03-11 编辑:思莹 手机版

  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<stdio.h>

  #include<stdlib.h>

  #include<string.h>

  #include<time.h>

  #define MAXLEN 100

  #define MAXNUM 10

  typedef int Tree[MAXLEN];

  Tree bt;

  int GetDeep(int i)

  {

  int l=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;

  }

  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]=i*2;

  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<stdio.h>

  #include<stdlib.h>

  #include<string.h>

  #include<time.h>

  #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[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]);

  return 0;

  }

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

  typedef int Tree[MAXLEN];

  Tree bt;

  void PreOrderTraverse(int i)

  {

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

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

  PreOrderTraverse(i*2);//lchild

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

  }

  void InOrderTraverse(int i)

  {

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

  InOrderTraverse(i*2);//lchild

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

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

  }

  void PostOrderTraverse(int i)

  {

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

  PostOrderTraverse(i*2);//lchild

  PostOrderTraverse(i*2+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;

  }

  }

本文已影响
腾讯2014校园招聘C语言笔试题相关推荐