笔试题

诺基亚笔试：
时间为2个小时，全是C语言题
开始有些小题，基本不难，有一个递归函数的题稍难，具体记不清了。
4题编程题如下：
1. 用尽量少的时间和空间找出一个单链表的倒数K个节点
实现起来比较简单，用双指针一前一后就可以实现

2. 实现二叉树的层次遍历
这个可以用队列的形式实现

3. 已经两个矩形的坐标，求两矩形的交叉矩形坐标
比较难，原因如下：
A：两矩形可能不相交或包含
B：两矩形可能不是水平的
网上有很多实现方法，看了都不是很满意，本人也不知道如何实现

4. 实现stricmp函数，不能用其它任何函数
比较简单

freescale笔试题：
共7题40分钟，比较简单
1. 说出查询和中断的优缺点
2. 编程实现strcpy
3. int *a, char *b,的地址和数据占用的字节数
4. 大小端编程判断
还有3题不记得了

诺基亚第2题实现方法：
树的层次遍历用到一个队列,加入队列后,然后从前面出队,出队同时把孩子入队,就OK了 #include "stdafx.h"
#include<iostream>
using namespace std; typedef struct Tree{
 int key;
 struct Tree *lchild;
 struct Tree *rchild;
}SNode,*STree; typedef struct Queue{
 struct Queue *next;
 struct Tree TNode;
}QNode,*QTree;
void En(QTree &Tail,STree T)
{
 QTree p = (QNode*)malloc(sizeof(QNode));
 p->next = NULL;
 p->TNode.key = T->key;
 p->TNode.lchild = T->lchild;
 p->TNode.rchild = T->rchild; 
 Tail->next = p;
 Tail = Tail->next;
} STree De(QTree &Head)
{
 cout<<Head->next->TNode.key<<"    ";
 Head = Head->next;
 return &(Head->TNode);
}
void CreatQueue(QTree &head,QTree &tail,STree T)
{
 En(tail,T);
 STree t;
 while(head != tail)
 {
  t = De(head);
  if(t->lchild)
   En(tail,t->lchild);
  if(t->rchild)
   En(tail,t->rchild);
 }
 return;
} void CreatBiTree(STree &T,int a)
{
 if(!T)
 {
  if(!(T = (SNode*)malloc(sizeof(SNode))))
  {
   return ;
  }
  T->key = a;
  T->lchild = T->rchild = NULL;
  return;
 }
 else
 {
  if(T->key > a)
   CreatBiTree(T->lchild,a);
  else
   CreatBiTree(T->rchild,a);
 }
}
void PreOrder(STree T)
{
 if(T)
 {
  cout<<T->key<<"    ";
  if(T->lchild)
   PreOrder(T->lchild);
  if(T->rchild)
   PreOrder(T->rchild);
  return;
 }
 else
  return;
}
void InOrder(STree T)
{
 if(T)
 {
  if(T->lchild)
   InOrder(T->lchild);
  cout<<T->key<<"    ";
  if(T->rchild)
   InOrder(T->rchild);
  return;
 }
 else
  return;
}   void run()
{
 int a[] = {55, 70, 39,12,79};
 STree T = (SNode *)malloc(sizeof(SNode));
 T->key = a[0];
 T->lchild = NULL;
 T->rchild = NULL;
 for(int i = 1;i < 5;i++)
 {
  CreatBiTree(T,a[i]);
 }
 cout<<"Pre     visit: ";
 PreOrder(T);
 cout<<endl;
 cout<<"Inorder visit: ";
 InOrder(T);
 cout<<endl;
 QTree head = (QNode*)malloc(sizeof(QNode));
 QTree tail;
 tail = head;
 cout<<"Level visit:   ";
 CreatQueue(head,tail,T);
} int main()
{
 run();
 getchar();
 return 0;
}

－－－－－－－－－－－－－－－－
其它遍历
//建立二叉树
typedef struct bitnode{
char data;
struct bitnode *lchild;
struct bitnode *rchild;
}bitnode,*bitree;
//初始化二叉树
void createbitree(bitree &t){
char ch;
scanf("%c",&ch);
if(ch==' ')
t=NULL;
else{
t=(bitnode *)malloc(sizeof(bitnode));
t->data=ch;
createbitree(t->lchild);
createbitree(t->rchild);
}
}
//先序遍历二叉树
void preordertraverse(bitree &t){
if(t){
printf("%c",t->data);
preordertraverse(t->lchild);
preordertraverse(t->rchild);
}
}
//中序遍历二叉树
void inordertraverse(bitree &t){
if(t){
inordertraverse(t->lchild);
printf("%c",t->data);
inordertraverse(t->rchild);
}
}
//后序遍历二叉树
void postordertraverse(bitree &t){
if(t){
postordertraverse(t->lchild);
postordertraverse(t->rchild);
printf("%c",t->data);
}
}

//二叉树叶子结点
int leafnumber(bitree &t){
if(!t)
return 0;
else if(!t->lchild&&!t->rchild)
return 1;
else
return leafnumber(t->lchild)+leafnumber(t->rchild);
}
//二叉树的深度
int depth(bitree &t){
int depthval,depthleft,depthright;
if(!t)
depthval=0;
else{
depthleft=depth(t->lchild);
depthright=depth(t->rchild);
depthval=1+(depthleft>depthright?depthleft:depthright);
}
return depthval;
}
//树的深度
int treedepth(bitree &t){
int h1,h2,h;
if(!t)
return 0;
else
{
h1=treedepth(t->lchild);
h2=treedepth(t->rchild);
h=(h1+1)>h2?(h1+1):h2;
}
return h;
}
//二叉 树的复制
void copybitree(bitree t,bitree &newt){
if(t)
{
newt=(bitnode *)malloc(sizeof(bitnode));
newt->data=t->data;
copybitree(t->lchild,newt->lchild);
copybitree(t->rchild,newt->rchild);
}
else
newt=NULL;
}
//队的建立
typedef struct qnode{
bitree data;
struct qnode *next;
}qnode,*queueptr;
typedef struct{
queueptr front;
queueptr rear;
}linkqueue;
// 队的初始化
int initqueue(linkqueue &q){
q.front=q.rear=(queueptr)malloc(sizeof(qnode));
if(!q.front)
return 0;
q.front->next=NULL;
return 1;
}
//进队
int enqueue(linkqueue &q,bitree e){
queueptr p=(queueptr)malloc(sizeof(qnode));
if(!p)
return 0;
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;
}
//出队
int dequeue(linkqueue &q,bitree &e){
if(q.front==q.rear)
return 0;
queueptr p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
free(p);
return 1;
}
//判断队 是否为空
int emptyqueue(linkqueue &q){
if(q.rear==q.front)
return 1;
else
return 0;
}

// 二叉树层次遍历
void layerorder(bitree e){
linkqueue q;
initqueue(q);
if(e)
enqueue(q,e);
while(!emptyqueue(q))
{
dequeue(q,e);
printf("%c",e->data);
if(e->lchild)
enqueue(q,e->lchild);
if(e->rchild)
enqueue(q,e->rchild);
}
}
void main(){
bitree t;
bitree newt;
printf("二叉树为：");
createbitree(t);
printf("先序遍历：");
preordertraverse(t);
printf("\n");
printf("中序遍历：");
inordertraverse(t);
printf("\n");
printf("后序遍历：");
postordertraverse(t);
printf("\n");
printf("层次遍历：");
layerorder(t);
printf("\n");
printf("叶子结点个数为：%d\n",leafnumber(t));
printf("二叉树的深度为：%d\n",depth(t));
printf("二叉树转换为树后对应的深度为：%d\n",treedepth(t));
printf("复制的二叉树先序遍历为：");
copybitree(t,newt);
preordertraverse(newt);
printf("\n");

}