- 相關推薦
騰訊2014校園招聘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<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;
}
}
6. 求三角形面積
給出三角形的三個邊長為a、b、c，求三角形的面積。
(注意考慮是不是三角形)
double GetArea(int a,int b,int c)
{
if(a-b>=c || a+b<=c)
return -0.1;
else{
double s=0.5*(a+b+c);
double area=sqrt(s*(s-a)*(s-b)*(s-c));
return area;
}
}
7. 壓縮字符串
例如字串”aaabbbbccccc”，轉換成相鄰字符+個數的形式壓縮，成為”a3b4c5”。
(如果有10個數相同) 假設需要考慮解壓縮
char *MergeString(const char * ch)
{
char *s=(char *)malloc(sizeof(ch));
if(s!=NULL)
{
int len=strlen(ch), i=0,j=0,k=0;
for(;i<len;i=j)
{
int num=0;
while(ch[j]==ch[i]) j++,num++;
s[k++]=ch[i];
sprintf(s+k,"%d",num);
k=strlen(s);
}
}
return s;
}
8. 如何判斷一個單向鏈表是否有環。
int ISCircle(pListNode head)
{
pListNode p1=head;
p1=p1->m_pNext;
while(p1!=NULL)
{
if(p1==head) return 1;
else p1=p1->m_pNext;
}
return 0;
}
9. 判斷一個字符串是否對稱。
aabbaa , efffe返回true
aabac返回false
int SymmetricString( const char *ch)
{
int len=strlen(ch);
int i=0,j=len-1;
if(len%2!=0) return 0;
for(i=0,j=len-1;i<=len/2;i++,j--)
{
if(ch[i]!=ch[j]) return 0;
}
return 1;
}
10. 判斷一個字符串是否是另一個字符串的字串
int next[20];
void get_next(const char* T,int next[])
{
int i=0,j=-1;next[0]=-1;
int len=strlen(T);
while(i<len)
{
if(j==-1||T[i]==T[j]) {++i;++j;next[i]=j;}
else j=next[j];
}
}
int index_KMP(const char * S,const char * T)
{
int i=0,j=0;
get_next(T,next);
int lens=strlen(S),lent=strlen(T);
while(i<lens &&j<lent){
if(j==-1 ||S[i]==T[j]){++i;++j;}
else j=next[j]; }
if(j>=lent) return i-lent;
else return -1;
}
鏈表的定義，棧的定義：
typedef struct stack
{
int top;
int space[MAXLEN+1];
}Stack;
int push(Stack *s,int num)
{
if(s->top>=sizeof(s->space)/sizeof(int)) return -1;//Error s->space[s->top++]=num;
return num;
}
int pop(Stack *s)
{
if(s->top<0) return -1;
return s->space[--s->top];
}
int IsEmpty(Stack *s)
{
return s->top==0;
}
typedef struct ListNode {
int m_nKey;
struct ListNode *m_pNext;
}ListNode,*pListNode;
pListNode CreateList()
{
srand((unsigned long)time(NULL));
pListNode head,p1,p2;
head=(pListNode)malloc(sizeof(ListNode));
p1=head;p2=p1;
int i=MAXLEN;
while(i--){
p2=(pListNode)malloc(sizeof(ListNode));
p2->m_nKey= rand()*rand()%(MAXLEN*rand());
p1->m_pNext=p2;
p1=p2;
}
p2->m_pNext=NULL;
return head;
}
void PrintList(pListNode head)
{
pListNode p=head;
do{
printf("%d/n",p->m_nKey);
p=p->m_pNext;
}while(p!=NULL);
}
【騰訊校園招聘C語言筆試題】相關文章：
騰訊技術類校園招聘筆試試題(A8卷)11-21
華為C語言筆試題12-12
華為筆試題（C語言）12-10
基礎C++/C語言筆試題分享11-21
yahoo在線筆試題（c語言）12-12
C語言筆試試題及答案07-31
c語言筆試題目及答案08-17
騰訊筆經11-28
2015C語言筆試題及答案08-08
計算機C語言試題及答案02-25