LoveSi

自处超然,处人蔼然,无事澄然,遇事斩然,得意淡然,失意泰然

常用链接

统计

最新评论

2010年10月16日 #

c++面试常问的问题

1.c与c++的区别

   1.全新的程序程序思维,C语言是面向过程的,而C++是面向对象的。 
   2
C语言有标准的函数库,它们松散的,只是把功能相同的函数放在一个头文件中;而C++对于大多数的函数都是有集成的很紧密,特别是C语言中没有的C++中的API是对Window系统的大多数API有机的组合,是一个集体。但你也可能单独调用API 
   3
,特别是C++中的图形处理,它和语言的图形有很大的区别。C语言中的图形处理函数基本上是不能用在中C++中的。C语言标准中不包括图形处理。 
   4
CC++中都有结构的概念,但是在C语言中结构只有成员变量,而没成员方法,而在C++中结构中,它可以有自己的成员变量和成员函数。但是在C语言中结构的成员是公共的,什么想访问它的都可以访问;而在VC++中它没有加限定符的为私有的。 
   4
C语言可以写很多方面的程序,但是C++可以写得更多更好,C++可以写基于DOSr程序,写DLL,写控件,写系统。 
   5
C语言对程序的文件的组织是松散的,几乎是全要程序处理;而c++对文件的组织是以工程,各文件分类明确。 
   6
C++中的IDE很智能,和VB一样,有的功能可能比VB还强。 
   7
C++对可以自动生成你想要的程序结构使你可以省了很多时间。有很多可用的工具如加入MFC中的类的时候,加入变量的时候等等。 
   8
C++中的附加工具也有很多,可以进行系统的分析,可以查看API;可以查看控件。 
   9
,调试功能强大,并且方法多样。

2.数组和链表的优缺点
   
   数组在内存中开辟连续的一块区域,如果一个数据要两个内存单元,一组5个数据10个单元就够了,无需标记其地址,因为数组定义时候标顶了第一个原许的地址,其他四个都知道了。链表可以是连续的,也可以是不连续的,但一般都是不连续的。
  1.链表灵活,数组简洁。  
  2
。要在数据中间做插入或删除,链表高效些,因为数组得把数据往前/后挪。  
  3
。数组的简索比链表快,因为它可以直接用偏移(offset)而链表要一接接地找。  
  4
。数组的建立/销毁比链表要快。  
3. malloc/new, free/delete之间的区别
   
malloc,free 是C语言的标准函数库,new/delete 是C++的运算符,他们都可以动态申请内存和释放内存; 
   对于非内部数据类型的对象而言, 光用malloc/free无法满足动态对象的需求. 对象要创建的同时要自动执行构造函数,对象在消亡之前要执行析构函数,由于malloc/free不是运算符,不在编译器控制权限之内,不能把构造函数和析构函数的务强加于malloc/free上. 因此,C++语言需要一个动态内存分配和初始化的运算符new和一个能完成清理与释放内存的运算符delete

不要企图用malloc/free来完成动态对象的内存管理,应该用new/delete。由于内部数据类型的“对象”没有构造与析构的过程,对它们而言malloc/free和new/delete是等价的。
既然new/delete的功能完全覆盖了malloc/free,为什么C++不把malloc/free淘汰出局呢?这是因为C++程序经常要调用C函数,而C程序只能用malloc/free管理动态内存。
  malloc/free功能还有一好处,就是可以和realloc组合使用,在需要扩大内存块时不一定会导致内存移动;而用new/delete实现时只能用new[]-copy-delete[]操作序列完成,每次都会导致内存移动。


posted @ 2010-10-16 20:01 LoveSi 阅读(1127) | 评论 (0)编辑 收藏

2010年10月10日 #

笔试碰到的算法题

至今笔试都悲剧的被拒,先发几道笔试中遇到的算法题
1.给定一整数序列A1, A2,... An (可能有负数),求A1~An的一个子序列Ai~Aj,使得Ai到Aj的和最大.
例如:整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。
int max_sub2(int a[], int size)
{
    
int  max = 0;
    
int temp_sum = 0;
    
for(int i = 0; i < size; i++)
    
{
        temp_sum 
+= a[i];
        
if(temp_sum > max)
            max 
= temp_sum;
        
else if(temp_sum < 0)
            temp_sum 
= 0;
    }

    
return max;
}

2. 任何一个基于"比较"的内部排序的算法,若对6个元素进行排序,则在最坏情况下所需的比较次数至少为____。

   据严蔚敏数据结构,问题等价于给n个不同的砝码和一台天平要称几次能分辨它们的顺序。n个记录的序列可能出现的初始状态有n!个,则描述n个记录排序过程的判定树必有n!个叶子节点,若有n个叶子节点,则二叉树的高度至少为log 2 n,(2为底),也即是说必然存在一条长为log 2 n!的路径,求出来n10,(取上界)

3. 对一个表达式求值时,首先要把表达式转换为后缀表达式,然后在利用栈求值。

posted @ 2010-10-10 16:37 LoveSi 阅读(695) | 评论 (2)编辑 收藏

淘宝笔试

1.如果n为偶数,则将它除以2,如果n为奇数,则将它加1或者减1。问对于一个给定的n,怎样才能用最少的步骤将它变到1。
例如 n= 61
n-- 60
n/2 30
n/2 15
n++ 16
n/2 8
n/2 4
n/2 2
n/2 1

参照网上的讨论,这道题的意思其实是看最后两位的二进制数:AB。如果B为偶数,则直接/ 2,如果B为奇数,则看A的值,若A为1,则该值+1,若为0,则该值-1。
#include <iostream>
using std::cin;
using std::cout;
using std::endl;

int main()
{
    
int n;
    cin
>>n;
    
int count = 0;
    
while( n > 1)
    
{
        
if( n%2 == 0)
            n 
/= 2;
        
else if( n == 3)
            n
--;
        
else
            n 
+= (n % 4 - 2);
        count
++;
    }


    cout
<<"times:"<<count<<endl;
    
return 0;
}


2.编一个有3个线程的程序,由Main主线程进入,生产者线程产生一个随机的整数。这个整数存在List中,再由消费者线程读取List数据,并显示。
3.列举3种你最喜欢的语言(Java/c++)框架,它们的特点和你喜欢的原因。
4.前缀表达式和后缀表达式的问题。
   35,15,+,80,70,-,*,20,/               //后缀表达方式
   (((35+15)*(80-70))/20)=25           //中缀表达方式  
   /,*,+,35,15,-,80,70, 20             //前缀表达方式

人们习惯的运算方式是中缀表达式。而碰到前缀,后缀方式。。迷茫。其实仅仅是一种表达式子的方式而已(不被你习惯的方式),我这里教你一种也许你老师都没跟你讲的简单转换方式。一个中缀式到其他式子的转换方法~~这里我给出一个中缀表达式~           a+b*c-(d+e)
第一步:按照运算符的优先级对所有的运算单位加括号~
                 式子变成拉:((a+(b*c))-(d+e))
第二步:转换前缀与后缀表达式
        前缀:把运算符号移动到对应的括号前面
                 则变成拉:-( +(a *(bc)) +(de))
                 把括号去掉:-+a*bc+de  前缀式子出现
        后缀:把运算符号移动到对应的括号后面
              则变成拉:((a(bc)* )- (de)+ )-
              把括号去掉:abc*+de+-  后缀式子出现
发现没有,前缀式,后缀式是不需要用括号来进行优先级的确定的。
后天晚上会有笔试,我会把最新的发上来~~~~~~~~

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~2011年的笔试
1前面的选择题记不清了.就上c++的答题吧?
2.不用sizeof,计算int的字节数
3.MAC地址字符串XX:XX:~~~最后改成XX-XX-XX-XX的标准形式
4.色子问题:有一枚筛子,每个面都有一个数字:1~6。很显然,你会倾向于认为这6个面出现的概率是相等的,也就是,你倾向认为:P(x1)=P(x2)=…=P(x6)=1/6其中,P(xi)表示出现数字xi的概率。
假如,我告诉你,这枚筛子与其它筛子不同,似乎,他很容易滚到4或者5这个面,所以这个筛子滚了好多次以后,它出现的平均值是4.5。这个时候,你会怎样分配P(x1)~P(x6)的概率呢?



 

posted @ 2010-10-10 16:28 LoveSi 阅读(2112) | 评论 (1)编辑 收藏

2010年10月9日 #

智力题目集锦

     摘要: 1.你有5瓶药,每个药丸重10克,只有一瓶受到污染的药丸重量发生了变化,每个药丸重9克。给你一个天平,你怎样一次就能测出哪一瓶是受到污染的药呢?—— 1给5个瓶子标上1、2、3、4、5。   2从1号瓶中取1个药丸,2号瓶中取2个药丸,3号瓶中取3个药丸,4号瓶中取4个药丸,5号瓶中取5个药丸。   3把它们全部放在天平上称一下重量。   4现在用1×10+2×10+3...  阅读全文

posted @ 2010-10-09 23:39 LoveSi 阅读(495) | 评论 (0)编辑 收藏

2010年10月7日 #

诺西笔试题目

1.统计1 个word(32bit)里面的1的bit数;
      
int count_1(int word)
{
        
int num = 0;

    
while (word > 0{
        num
++;
        word 
= word & (word - 1);
    }


    
return num;
}


int main()
{
    
int word = 1200;
    
int num = count_1(word);
    
    
return 0;
}
2. strcpy的实现
char *strcpy(char *dest, const char *src)
{
    
if (dest == NULL || src == NULL)
        
return NULL;
    
if (dest == src)
        
return dest;
    
char *destCpy = dest;
    
while((*dest++ = *src++!= '\0')
        ;
    
return destCpy;
}

3.找出因子只有2,3,5的第1500个数,如1,2,3,4,5,6,8,9,10为满足条件的数,设计有效算法
  满足这个条件的数据都应该满足v = 2^x * 3^y * 5^z, 从http://blog.csdn.net/wwd252/archive/2008/09/04/2882645.aspx看到了算法,借鉴一下
   
#include <stdio.h>
#include 
<iostream>
using std::cout;
#define   N   1500   


int   main()   
{   
    
long  result[N];   
    
int   p2, p3, p5;   
    
int   i;   
    result[
0= 1;   
    p2 
= p3 = p5 = 0;

    
for(i = 1; i < N; ++i){   
        
int min;   
        min 
= result[p2] * 2;   
        
if(min > result[p3] * 3)
            min 
= result[p3] * 3;   
        
if(min > result[p5] * 5)
            min 
= result[p5] * 5;  
        result[i] 
= min;  


        
if(result[p2] * 2 <= result[i])
            p2
++;   
        
if(result[p3] * 3 <= result[i])
            p3
++;   
        
if(result[p5] * 5 <= result[i])
            p5
++;   
    }
   
    cout
<<result[N- 1]; 
}

这道题我觉着关键就是设立一个机制,判断哪个指数加1。

   

posted @ 2010-10-07 22:51 LoveSi 阅读(1160) | 评论 (3)编辑 收藏

Moto笔试题目

1、智能指针

智能指针是存储指向动态分配(堆)对象指针的类, 用于生存期控制, 能够确保自动正确的销毁动态分配的对象,防止内存泄露。它的一种通用实现技术是使用引用计数(reference count)。智能指针类将一个计数器与类指向的对象相关联,引用计数跟踪该类有多少个对象共享同一指针。每次创建类的新对象时,初始化指针并将引用计数置为1;当对象作为另一对象的副本而创建时,拷贝构造函数拷贝指针并增加与之相应的引用计数;对一个对象进行赋值时,赋值操作符减少左操作数所指对象的引用计数(如果引用计数为减至0,则删除对象),并增加右操作数所指对象的引用计数;调用析构函数时,构造函数减少引用计数(如果引用计数减至0,则删除基础对象)。

智能指针就是模拟指针动作的类。所有的智能指针都会重载 -> * 操作符。智能指针还有许多其他功能,比较有用的是自动销毁。这主要是利用栈对象的有限作用域以及临时对象(有限作用域实现)析构函数释放内存。当然,智能指针还不止这些,还包括复制时可以修改源对象等。智能指针根据需求不同,设计也不同(写时复制,赋值即释放对象拥有权限,引用计数等,控制权转移等)。auto_ptr 即是一种常见的智能指针。
     
智能指针通常用类模板实现:
       template <class T>
       class smpoint
       {
          public:
              smpoint(T * p): _p(p){}
              T & operator * (){return *_p;}
              T * operator -> (){return _p;}
              ~smpoint(){delete _p;}
          private:
              T * _p;
        }

2printf()可变参数如何实现http://www.vckbase.com/document/viewdoc/?id=1830

 
int printf(char *fmt, ...),关键是几个宏的实现

3、标准模板库vector追加数据如何实现。是底层如何实现,不能用现有的东东。

在追加对象前先判断预留的空间是否满足需求,如果不满足则根据分配策略,另分配足够的空间 (一般使用平方增加策略),复制以前的对象数组,再释放原来的空间,然后把对象追加到尾部。如果任何一个操作环节失败,则至少保留原数组不受影响(异常安全保证策略)。

4java的垃圾收集机制如何实现为什么?如果是你自己实现垃圾收集机制,如何实现? 用什么数据结构?

垃圾收集没有统一的实现。《深入Java虚拟机》中提了几种算法,包括引用计数,跟踪收集,拷贝收集(这个挺有趣的),还有重头火车算法。但是这本书有点旧了,新的技术不清楚。
最简单的实现做法,莫过于new的时候纪录,程序exit的时候批量delete……

5.二叉排序树和哈希表那个查找效率高,实用于pda

质量精良的hash肯定是查找效率最高的。但是pda上,应该是二叉树比较好吧。在内存限制的条件下,hash可能会有变态表现。而有序二叉树的查找算法就比较稳定,空间复杂度n,最坏时间复杂度nlog(n),而且避免了不同情况下hash函数的设计困难。

6.  .net的底层实现机制。

虚拟机
 

7、过程间通信如何实现。

windows用管道,unix用文件描述符,或者用socket
 

8、迭代问题,什么问题用迭代,迭代在操作系统中如何实现的

迭代算法是用电脑解决问题的一种基本方法。他利用电脑运算速度快、适合做重复性操作的特点,让电脑对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出他的一个新值。
递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。

9、如何交换两个变量,不能用中间变量。

int   i;        
int   j;        
j   =  
i   +   j-   i   =   j);

a   =   a^b;
b=   a^b;
a   =   b^a;


10cc++ static函数的区别???

C 语言中 static 关键字作用于函数时起限制函数作用域的作用,其static函数作用域被限制为当前文件中,该函数定义之后部分。
C++
的全局函数用static 修饰和 C 语言中一个意思 (C++ 标准建议此种情况用匿名名字空间包含该函数来代替static关键字);但类成员函数如果用static 修饰表示是类的作用域而不是对象作用域,可以直接通过类名来引用。

11const 函数的作用,如何实现钩子函数。

类的设计者通过将函数声明为 const 以表明它们不修改类对象。
const
函数内不允许修改数据成员 (需要注意的是,虽然在 const 函数内,指针成员变量不允许被修改,但对指针所指向内容的修改是允许的)
一个 const 类对象只能调用 const 成员函数 (构造和析构函数除外)

12、两层容错技术怎么实现?

 

13、写出函数指针,函数返回指针,const指针,指向const的指针,指向constconst指针。

     函数指针:函数类型 *指针变量名)(形参表) --int *f)(int a);

      --1.说明函数指针变量(int*f)(int a));2.要对函数指针变量赋值(f = func);3.要用(*指针变量)(参数表);调用函数((*f)(ab))

      指针函数:类型标识符 *函数名(参数表) int * fint x int y

      Const 指针:int *const ptr

      指向const的指针:const int *ptr

      指向constconst指针:const int *const ptr

      

14、函数调用如何实现,注意什么问题。

在函数调用的时候,使用栈传递参数,可变参数函数的实现与函数调用的栈结构有关,正常情况下c/c++的函数参数入栈规则为__stdcall, 它是从右到左的,即函数中的最右边的参数最先入栈。对于函数

 void fun(int a, int b, int c) {     int d;      ...    }

其栈结构为

    0x1ffc-->d

    0x2000-->a

    0x2004-->b

    0x2008-->c

对于任何编译器,每个栈单元的大小都是sizeof(int), 而函数的每个参数都至少要占一个栈单元大小

 

15、指针和引用的差别 

      1.指针初始化的时候,可以指向一个地址或者为空,而引用必须初始化为另一个变量;

      2.指针是一个变量,占用4个字节,引用是一个别名;指针可以指向NULL,但引用必须与一个已经存在的变量绑定,而且这种绑定不可修改。

      3.指针可以被重新赋值与指向另外一个不同的对象,但是引用则总是指向在初始化时被指定的对象,以后不能更改

 16、拷贝构造函数如何实现,什么情况下会用到。

   拷贝构造函数的几个用处:
      1)
用一个类对象初始化该类的另一个对象的时候:
         A a;
         A b(a);
         A b = a;
      2)
把一个类对象赋值给该类的另一个对象的时候:
         A b;
         b = a;
      3)
传参数和返回时:
         A f (A a) //
传参和返回都会调用拷贝构造函数
         {
             // ...
         }
     
实现时要注意的是:
      1)
当类中有指针变量成员时,确认是直接拷贝指针变量的值,还是重新分配内存然后递归拷贝构造。
      2)
是否有每个对象必须有唯一值的成员变量 (比如账号)。其实 1) 也可以归为 2)

 


 


posted @ 2010-10-07 15:31 LoveSi 阅读(615) | 评论 (2)编辑 收藏

仅列出标题