C++ Programmer's Cookbook

{C++ 基础} {C++ 高级} {C#界面,C++核心算法} {设计模式} {C#基础}

笔试题(转)


一、如何判断一个单链表是有环的?(注意不能用标志位,最多只能用两个额外指针)
   struct node { char val; node* next;}
   bool check(const node* head) {} //return false : 无环;true: 有环
    一种O(n)的办法就是(搞两个指针,一个每次递增一步,一个每次递增两步,如果有环的话两者必然重合,反之亦然):
    bool check(const node* head)
    {
         if(head==NULL) 
              return false;   
         node *low=head, *fast=head->next;
         while(fast!=NULL && fast->next!=NULL)
        {
               low=low->next;
               fast=fast->next->next;
               if(low==fast)
                    return true;
        }
       return false;
   }

 二、删除一个单项链表的最中间的元素,要求时间尽可能短(不能使用两次循环)
struct link
{
    int data;
    struct link *next;
};
void delMiddle(link *head)
{
    if(head == NULL)
           return;
    else if(head->next == NULL)
    {
            delete head;
            return;
    }
    else
    {
            link *low = head;
            link *fast = head->next;
            while(fast != NULL && fast->next != NULL)
            {   
                       fast = fast->next->next;
                       if(fast == NULL)
                                    break;
                       low = low->next;
            }
            link *temp = low->next;
            low->next = low->next->next;
            delete temp;
  
    }
}
int main()
{
       struct link *head,*l;
       struct link *s;
       head = (link*)malloc(sizeof(link));
       head->data=0;
       head->next = NULL;
       l = head;
       for(int i=1; i<9; i++)
       {
            s = (link*)malloc(sizeof(link));
            s->data = i;
            s->next = NULL;
            l->next= s;
            l = l->next;
       }
       print(head);
       delMiddle(head);
       print(head);
       return 0;
}

三、输入n,求一个n*n矩阵,规定矩阵沿45度线递增(威盛)
/**
 * 得到如下样式的二维数组
* zigzag(jpeg编码里取象素数据的排列顺序)
*
*   0, 1, 5, 6,14,15,27,28,
*   2, 4, 7,13,16,26,29,42,
*   3, 8,12,17,25,30,41,43,
*   9,11,18,24,31,40,44,53,
*   10,19,23,32,39,45,52,54,
*   20,22,33,38,46,51,55,60,
*   21,34,37,47,50,56,59,61,
*   35,36,48,49,57,58,62,63
 */

void zigzag(int n)
{
 int **a =(int**) malloc(n*sizeof(int *));  //分配空间
 
 if(NULL == a)
  return ;
 int i;
 for(i = 0; i < n; i++) {
        if((a[i] =(int*) malloc(n * sizeof(int))) == NULL) {
            while(--i>=0)
                free(a[i]);
            free(a);
            return;
        }
    }
 
 bool flag = false; //这个标志位用来判断是从45度角生成还是225度角生成
 int count = 0;
 for(i=0; i<n; i++)  //生成的上半部分的数据
 {
  
  if(flag)
  {
   for(int r = 0; r<=i; r++)
   {
    a[r][i-r] = count;
    count++;
   }
   flag = false;
  }
  else
  {
   for(int r = i; r>=0; r--)
   {
    a[r][i-r] = count;
    count++;
   }
   flag = true;
  }
 }
 for(i=n-1; i>=0; i--)  //生成的是下半部分的数据
 {
 // cout<<i<<endl;
  if(flag)
  {
   for(int r = 0; r<=i-1; r++)
   {
    int r1 = n-i+r;       //代表当前行
    int c1 = 2*n-i-1-r1;  //代表当前列
    a[r1][c1] = count;
    count++;
   }
   flag = false;
  }
  else
  {
   for(int r = i-1; r>=0; r--)
   {
    cout<<"ddd"<<endl;
    int r1 = n-i+r;
    int c1 = 2*n-i-1-r1;
 //   cout<<r1<<","<<c1<<endl;
    a[r1][c1] = count;
    count++;
   }
   flag = true;
  }
 }
 for(int r = 0; r<n; r++)
 {
  for(int c=0; c<n; c++)
   cout<<a[r][c]<<",";
  cout<<endl;
 }
}
int main()
{
 int n;
 cin>>n;
 zigzag(n);
 return 0;
}
网上还有一个人写了一个比较巧的算法:
/**
* 得到如下样式的二维数组
* zigzag(jpeg编码里取象素数据的排列顺序)
*
*   0, 1, 5, 6,14,15,27,28,
*   2, 4, 7,13,16,26,29,42,
*   3, 8,12,17,25,30,41,43,
*   9,11,18,24,31,40,44,53,
*   10,19,23,32,39,45,52,54,
*   20,22,33,38,46,51,55,60,
*   21,34,37,47,50,56,59,61,
*   35,36,48,49,57,58,62,63
*/

#include
<stdio.h>
int main()
{
   
int N;
   
int s, i, j;
   
int squa;
    scanf(
"%d", &N);
   
/* 分配空间 */
   
int **a = malloc(N * sizeof(int *));
   
if(a == NULL)
       
return 0;
   
for(i = 0; i < N; i++) {
       
if((a[i] = malloc(N * sizeof(int))) == NULL) {
           
while(--i>=0)
                free(a[i]);
            free(a);
           
return 0;
        }
    }
   
/* 数组赋值 */
    squa
= N*N;   
   
for(i = 0; i < N; i++)
       
for(j = 0; j < N; j++) {
            s
= i + j;
           
if(s < N)
                a[i][j]
= s*(s+1)/2 + (((i+j)%2 == 0)? i : j);
           
else {
                s
= (N-1-i) + (N-1-j);
                a[i][j]
= squa - s*(s+1)/2 - (N - (((i+j)%2 == 0)? i : j));
            }
        }
   
/* 打印输出 */   
   
for(i = 0; i < N; i++) {
       
for(j = 0; j < N; j++)
            printf(
"%-6d", a[i][j]);
        printf(
"\n");
    }
   
return 0;
}

四、打印1到1000的整数,不能使用流程控制语句(for,while,goto等)也不能使用递归
1.
typedef struct _test{
   
static int a;
    _test(){
        printf(
"%d\n",_test::a);
        a
++;
    }
  }Test;
 
int Test::a = 1;

 
int   main()  
  {  
    Test tt[
1000];
   
return 0;
  }  
2.
#include   <stdio.h>
#define   B   P,P,P,P,P,P,P,P,P,P
#define   P   L,L,L,L,L,L,L,L,L,L
#define   L   I,I,I,I,I,I,I,I,I,I,N
#define   I   printf( "%3d   ",i++)
#define   N   printf( "\n ") 
int  main()
{
    int   i   =   1;
    B;
}

#define A(x) x;x;x;x;x;x;x;x;x;x;
int main ()
{
   
int n = 1;
    A(A(A(printf (
"%d ", n++))));

   
return 0;
}


五、struct   S   {
        int   i;
        int   *   p;
};
void   main()
{
        S   s;
        int   *   p   =   &s.i;
        p[0]   =   4;
        p[1]   =   3;
        s.p   =   p;
        s.p[1]   =   1;
        s.p[0]   =   2;
}
问程序会在哪一行死掉。 (microsoft)
解: S   s;
         int   *   p   =   &s.i;        //s.i的地址存储在p里
        p[0]   =   4;                    //修改了s.i
         p[1]   =   3;                    //修改了s.p
         s.p   =   p;                    //s.p指向s.i
         s.p[1]   =   1;               //修改s.p本身
        s.p[0]   =   2;               //s.p指向的是0x00000001,尝试向这里写,出错
     s.p[0]       =       2;   时出错
     因为s.p存的是s.i的地址,s.p[1]为s.p,当s.p[1]=1时,s.p此时存放的是1了,而不是地址s.i,故在s.p[0]   =   2时出错.
此时相当于s.p=ox00000001;地址ox0000001   =   2;当然就出错了

如果语句s.p[0]   =2   先于s.p[1]=1则程序就不会出错.此时语句相当于s.i=2;s.p=1;

六、题目描述:
1.   int   swap(int   *x,int   *y)
{
    if(x==NULL   ¦ ¦   y==NULL)
        return   -1;
    *x   +=   *y;
    *y   =   *x-   *y;
    *x   -=   *y;
      return   1;
}
请改错,溢出已经考虑,不是错误
2.
void   foo(int   *x,   int   *y)
{
    *x   +=   *y;
    *x   +=   *y;
}
void   fun(int   *x,   int   *y)
{  
    *x   +=   2   *   (*y);
  }
问两个函数是否等价,能否互换
解答:第一题的函数是交换。但假如考虑x,   y都是指向同一个变量,结果是这个变量的值为0.
第二题的两个函数是有区别的,也考虑x,y是指向同一个变量.这样第一个函数的结果是这个变量的4倍.但第二个函数的结果是变量的3倍
.

posted on 2008-02-18 13:25 梦在天涯 阅读(4730) 评论(1)  编辑 收藏 引用 所属分类: interview

评论

# re: 笔试题(转) 2008-03-09 16:44 DK_jims

不是吧~ 如果我做此笔试,,不用找工作了????????  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


公告

EMail:itech001#126.com

导航

统计

  • 随笔 - 461
  • 文章 - 4
  • 评论 - 746
  • 引用 - 0

常用链接

随笔分类

随笔档案

收藏夹

Blogs

c#(csharp)

C++(cpp)

Enlish

Forums(bbs)

My self

Often go

Useful Webs

Xml/Uml/html

搜索

  •  

积分与排名

  • 积分 - 1625917
  • 排名 - 5

最新评论

阅读排行榜