笔试题错题集锦

最近在刷笔试题，实在是看不下去，可还是得硬着头皮看下去，毕竟要想活得比别人漂亮，找个好工作很关键啊！！！所以收集一些平时不太了解或者易错的题。未完，待续~~

C/C++

一：

先看下面一段简单的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
int main()
{
	double i = 10.0000;
	if(i == 10)
		printf("i是10\n");
	for(i = 0; i != 10; i += 0.1)
	{
		printf("%.1f\n", i);
		if(i == 10)
			break;
	}
  return 0;
}

运行结果如下：

1
2
3
4
5
6
7
8
9
10
i是10
0.0
……
9.8
9.9
10.0
10.1
10.2
10.3
……

解析

2进制的浮点数表示有一个很大的问题——它并不可以精确表示所有实数。只有可以写成2^a+2^b+2^c+…这种形式并且精度不能太多的实数才可以用浮点数来精确表示。而大多数实数仅仅保存了一个四舍五入后的近似值而已。譬如，0.1在单精度浮点数中实际值为0.100000001490116119384765625。

正是这种非精确的表示形式，造成了浮点数运算的误差。不管加减乘除，只要涉及到了浮点数，结果不是精确值，只是近似值。所以，在浮点数的运算中，请尽量避免用==比较结果，可以用 a+b<某个很小的数来代替。

二：

1
2
3
4
5
6
7
8
9
10
#include<stdio.h>
int main()
{
	int count = 1;
	count = count++;
	
	printf("%d%d%d\n",count++,count++,count++);
	printf("%d\n",count);
  	return 0;
}

结果如下：

1
2
321
4

解析

首先，函数printf从左往右读取，然后将先读取放到栈底，最后读取的放在栈顶，处理时候是从栈顶开始的，所以我们看见的结果是，从右边开始处理的。

再者，如果一个表达式（或子表达式）只计算出值而不改变环境，我们就说它是引用透明的，这种表达式早算晚算对其他计算没有影响（不改变计算的环境。当然，它的值可能受到其他计算的影响）。如果一个表达式不仅算出一个值，还修改了环境，就说这个表达式有副作用（因为它多做了额外的事）。i++ 就是有副作用的表达式。其非原子操作。

程序语言通常都规定了执行中变量修改的最晚实现时刻（称为顺序点）。程序执行中存在一系列顺序点（时刻），语言保证一旦执行到达一个顺序点，在此之前发生的所有修改（副作用）都必须实现（必须反应到随后对同一存储位置的访问中），在此之后的所有修改都还没有发生。在顺序点之间则没有任何保证。

C/C++ 语言的规定告诉我们，任何依赖于特定计算顺序、依赖于在顺序点之间实现修改效果的表达式，其结果都没有保证。

所以这类代码不要写！！！

三：

子类和子类型

提到“子类”和“子类型”是不同的，替换原则只适合于子类型关系，而一般编程语言只是考虑了子类关系，子类说明了新类是继承自父类，而子类型强调的是新类具有父类一样的行为（未必是继承）。

一种类型当它至少提供了另一种类型的行为，则这种类型是另一种类型的子类型。

公有继承下派生类为基类的子类型，其他都只是子类。

四：

delete和delete[]

当用delete来释放用new int[]申请的内存空间时，由于其为基本数据类型没有析构函数，所以使用delete与delete []相同，两者都会释放申请的内存空间；若是自定义的数据类型，有析构函数时，用new []申请的空间，必须要用delete []来释放，因为要delete []时会逐一调用对象数组的析构函数，然后释放空间。

所以一个简单的使用原则就是：new 和 delete、new[] 和 delete[] 对应使用。

五：

下面的程序可以从0….n-1中随机等概率的输出m个不重复的数。这里我们假设n远大于m。

1
2
3
4
5
6
7
8
9
10
knuth(int n, int m)
{ 
    srand((unsigned int)time(0)); 
    for (int i = 0; i < n; i++) { 
        if ( ) { 
            cout << i << endl;
            ( );
        }
     }
}

选项依次为

1
2
3
4
rand()%(n-i)<=m   m--
rand()%(n-i)<m   m--
rand()%(n-i)>=m   m++
rand()%(n-i)>m   m++

解析

由这个for循环循环n次，且在满足条件时才输出i,可知，输出m个不同值的要求已满足，因为每次输出的都是i值，而i值每次都是不一样的，m–保证了程序在输出了m个值后就停止循环。

在i=0时，rand()%(n-i)的取值范围为0到n-1，共n个数，此时要输出0只需要rand()%(n-i)小于m，故i=0被输出的概率为m/n;

在i=1时，rand()%(n-i)的取值范围为0到n-2，共n-1个数，若i=0没有被输出，则m–未被执行，此时i=1被输出的概率为m/(n-1)，若i=0已经被输出了，则m变为m-1，此时i=1被输出的概率为(m-1)/(n-1)；由概率论的知识，可知此时i=1被输出的概率为P=(1-m/n)*(m/(n-1))+m/n*((m-1)/(n-1))=m/n；以此类推，可知每个数被输出的概率都为m/n。

六：

下面代码会输出什么

1
2
3
4
5
6
int main(int argc, char **argv)
{
    int a[4] = {1, 2, 3, 4};
    int *ptr = (int *)(&a + 1);
    printf("%d", *(ptr - 1));
}

解析

&a是数组指针，其类型为int()[4]；
而指针加1要根据指针类型加上一定的值，不同类型的指针+1之后增加的大小不同，a是长度为4的int数组指针，所以要加5\sizeof(int)，所以ptr实际是a[4],但是ptr与（&a+1）类型是不一样的，这点非常重要，所以ptr-1只会减去sizeof(int*)，a和&a的地址是一样的，但意思就不一样了，a是数组首地址，也就是a[0]的地址，&a是对象（数组）首地址，a+1是数组下一元素的地址，即a[1]，&a+1是下一个对象的地址，即a[4]。

七：

指针

声明一个指向含有10个元素的数组的指针，其中每个元素是一个函数指针，该函数的返回值是int，参数是int*，正确表示为

1
int (*(*p)[10])(int *)

八：

已知表达式++a中的”++”是作为成员函数重载的运算符,则与++a等效的运算符函数调用形式为a.operator++()。

解析

前置单目运算符重载为类的成员函数时，不需要显式说明参数，即函数没有形参。后置单目运算符重载为类的成员函数时，函数要带有一个整型形参。

九：

当使用free释放掉一个指针内容后，指针变量的值被置为NULL，这句话错误。

解析

free指的是释放该指针所指向的内存资源，指针仍然指向原来的堆地址，即仍然可以继续使用，这很危险。因为操作系统已经认为这块内存可以使用，它会毫不考虑的将他分配给其他程序。为了防止指针成为野指针，需要在free后将指针置为NULL。

十：

const用法

const出现在*左边，如const char* p，表示p所指向的变量内容不可变，指针指向可以改变；const出现在*右边，如char* const p，表示p是个常量指针，即不能指向其他变量，而指向的变量内容可变；const出现在*左边和右边，如const char* const p，表示p的指向不能改变，指向的变量内容也不能改变。

十一：

拷贝构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "stdio.h"
class A
{
    public:
    A()
    {
        printf("1");
    }
    A(A &a)
    {
        printf("2");
    }
    A &operator=(const A &a)
    {
        printf("3");
        return *this;
    }
};
int main()
{
    A a;
    A b = a;
}

输出结果为12。

解析

拷贝构造函数调用时机：

  • 对象以值传递的方式传入函数参数
  • 对象以值传递的方式从函数返回
  • 对象需要通过另外一个对象进行初始化

可以参考C++拷贝构造函数详解

每个类只能有一个析构函数，没有返回值类型，也没有参数。

十二：

C++中，下面四个表达式中错误的一项是()。

1
2
3
4
a+=(a++)
a+=(++a)
(a++)+=a
(++a)+=(a++)

解析

A： a+=(a++) 先计算a++ ，因为a为后++,a左边是左值不会报错 ;

B： a+=(++a) 先计算++a,因为a为前++, a左边是左值不会报错 ;

C：(a++) += a 这个是错误的。因为左值只能是变量,不能是表达式，(a++)是后++, 所以a不会先计算a++,是表达式。所以会报错。

D：(++a) +=(a++) 先计算++a,然后再去计算a +=(a++) ,所以左边也是左值 ;

十三：

补码和求补运算

  • 原码
    原码表示法最高位为符号位，该位为0表示正数，1表示负数。其余位表示数的绝对值。
  • 反码
    对于一个带符号的数来说，正数的反码与其原码相同；负数的反码为其原码除符号位以外的各位按位取反。反码常用来做求补码过程中的中间形式。
  • 补码
    正数的补码与其原码和反码相同；负数的补码是对它的原码除符号位以外各位取反，并在末位加1而得到，即为该数的补码加1。计算机内的数一般以补码形式表示。在补码中用(-128)D代替了(-0)D，注意：(-128)D没有相对应的原码和反码，(-128)D = (1000,0000)B。
  • 求补运算
    求补运算不考虑符号位，对它的原码各位取反，并在末位加1而得到。对一个数进行求补运算所得的是该数相反数的补码。

十四：

typedef与结构结合使用

typedef struct tagMyStruct
{
　int iNum;
　long lLength;
} MyStruct;

这语句实际上完成两个操作：

1) 定义一个新的结构类型

struct tagMyStruct
{
　int iNum;
　long lLength;
};

分析：tagMyStruct称为“tag”，即“标签”，实际上是一个临时名字，struct 关键字和tagMyStruct一起，构成了这个结构类型，不论是否有typedef，这个结构都存在。

我们可以用struct tagMyStruct varName来定义变量，但要注意，使用tagMyStruct varName来定义变量是不对的，因为struct 和tagMyStruct合在一起才能表示一个结构类型。

2) typedef为这个新的结构起了一个名字，叫MyStruct。

typedef struct tagMyStruct MyStruct;

因此，MyStruct实际上相当于struct tagMyStruct，我们可以使用MyStruct varName来定义变量。

十五

可以重载的运算符：

算术运算符：+,-,*,/,%,++,–;

位操作运算符：&,|,~,^,＜＜,＞＞

逻辑运算符：!,&&,||;

比较运算符：＜,＞,＞=,＜=,==,!=;

赋值运算符：=,+=,-=,*=,/=,%=,&=,|=,^=,＜＜=,＞＞=;

其他运算符：[],(),-＞,,(逗号运算符),new,delete,new[],delete[],-＞*。

不能被重载的运算符：

.,.*,::,?:

十六

static关键字

静态局部变量具有局部作用域。它只被初始化一次，自从第一次初始化直到程序结束都一直存在，他和全局变量的区别在于全局变量对所有的函数都是可见的，而静态局部变量只对定义自己的函数体始终可见。

静态全局变量也具有全局作用域，他与全局变量的区别在于如果程序包含多个文件的话，他作用于定义它的文件里，不能作用到其他文件里，即被static关键字修饰过的变量具有文件作用域。这样即使两个不同的源文件都定义了相同的静态全局变量，他们也是不同的变量。

全局变量、静态局部变量、静态全局变量都在静态存储区分配空间，而局部变量在栈分配空间。

TIPS：

1、若全局变量仅在单个文件中访问，则可以讲这个变量修改为静态全局变量。

2、若全局变量仅在单个函数中使用，则可以将这个变量修改为该函数的静态局部变量。

3、全局变量、静态局部变量、静态全局变量都存放在静态数据存储区。

4、函数中必须要使用static变量的情况：当某函数的返回值为指针类型时，则必须是static的局部变量的地址作为返回值，若为auto类型，则返回为错指针。

十七

虚函数和纯虚函数

虚函数为了重载和多态的需要，在基类中是有定义的，即便定义是空，所以子类中可以重写也可以不写基类中的此函数。
纯虚函数只是一个接口，是个函数的声明而已，子类必须实现该函数。

十八

sizeof

当参数分别如下时，sizeof返回的值表示的含义如下：
数组——编译时分配的数组空间大小；
指针——存储该指针所用的空间大小（存储该指针的地址的长度，是长整型，一般为4）；
类型——该类型所占的空间大小；
对象——对象的实际占用空间大小；
函数——函数的返回类型所占的空间大小。函数的返回类型不能是void。
数组作为形参时，数组的数组名会退化成一个指向该类型数组的指针，只要是指针，在32位系统中所占的字节数就是4，在64位系统中所占的字节数是8。

十九

sizeof

32位机器上定义如下结构体：

1
2
3
4
5
6
7
8
9
struct xx
{
    long long _x1;
    char _x2;
    int _x3;
    char _x4[2];
    static int _x5;
};
int xx::_x5;

sizeof(xx)大小是多少。

解析

静态变量不占用类空间。结构体要特别注意字节对齐，有两条原则：1）结构体变量中成员的偏移量必须是成员大小的整数倍；2）结构体的最终大小必须是结构体最大简单类型的整数倍。x1的偏移量是0，长度是8，符合；x2的偏移量是8，长度是1，符合；x3的偏移量是9，长度是4，不符合，需要在x2之后填充3字节使得x3的偏移量达到12；x4的偏移量是16，长度是2，符合；此时总长度为（8）+（1+3）+（4）+（2）=18，而最大简单类型为long long长度为8，因此需要在x4之后再填充6字节，使得总长度达到24可被8整除。因此sizeof(xx)的结果为24。

二十

sizeof

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
下面四个类A,B,C,D,在32位机器上sizeof(A),sizeof(B),sizeof(C),sizeof(D)值分别为()
class A{
};
class B{
    char ch;
    int x;
};
class C{
public:
    void Print(void){}
};
class D
{
public:
    virtual void Print(void){}
};

空类编译器会将sizeof（）的值变为1；类的大小只与非静态成员和虚函数的大小有关，而与其他普通函数成员无关，与构造函数析构函数也无关。

sizeof()是针对实例的，因此类的大小只跟非static成员变量以及虚函数有关；（static变量非实例独占，sizeof()不考虑；普通成员函数，包括构造函数，被各实例共享，因此也不归sizeof()考虑）。
A：空类的sizeof()为1；
B：补齐后sizeof()为8；
C：普通成员函数不考虑，类的sizeof()仍为1；
D：类中含虚函数，编译器会自动生成一个虚函数表，类需要一个指针来指向该虚表，因此类的sizeof()为4；

二十一

结构体对齐

原则1、

普通数据成员对齐规则：第一个数据成员放在offset为0的地方，以后每个数据成员存储的起始位置要从该成员大小的整数倍开始（比如int在32位机为４字节，则要从4的整数倍地址开始存储）。

原则2、

结构体成员对齐规则：如果一个结构里有某些结构体成员，则该结构体成员要从其内部最大元素大小的整数倍地址开始存储。（struct a里存有struct b，b里有char，int，double等元素，那b应该从8的整数倍开始存储。）

原则3、

结构体大小对齐规则：结构体大小也就是sizeof的结果，必须是其内部成员中最大的对齐参数的整数倍，不足的要补齐。

java

一：

有如下4条语句：

1
2
3
4
Integer i01=59;
int i02=59;
Integer i03=Integer.valueOf(59);
Integer i04=new Integer(59);

输出结果为false的是

1
2
3
4
System.out.println(i01==i02);
System.out.println(i01==i03);
System.out.println(i03==i04);
System.out.println(i02==i04);

解析

Integer对象自动缓存int值范围在low~high（-128~127），如果超出这个范围则会 Integer.valueOf 自动装箱为包装器类型；当包装器类型和基本数据类型进行“==”比较时，包装器类型会自动拆箱为基本数据类型。

在Java中，会对-128到127的Integer对象进行缓存，当创建新的Integer对象时，如果符合这个这个范围，并且已有存在的相同值的对象，则返回这个对象，否则创建新的Integer对象。

Integer i01=59;//自动装箱，实质就是调用Integer.valueOf(int i)方法，如果-128<i<127，则直接返回常量池中的值，否则new一个。在该题中，i01 == i02 == i03 都是返回常量池中的值。 int和Integer 比较时，Integer会先进行拆装，比较的是两个的值是否相等。两个Integer对象比较时是比较地址。

所以本题为答案为System.out.println(i03==i04)。

linux

一：

fork() 函数复制时将父进程的所以资源都通过复制数据结构进行了复制，然后传递给子进程，所以fork()函数不带参数。

clone() 函数则是将部分父进程的资源的数据结构进行复制，复制哪些资源是可选择的，这个由参数列表中的clone_flags设定，所以 clone() 函数带参数，没有复制的资源可以通过指针共享给子进程。另外，clone()返回的是子进程的pid。

vfork()创建的子进程与父进程共享数据段,而且由vfork()创建的子进程将先于父进程运行。

操作系统

一：

线程和进程

二：

Little-endian和 Big-endian

数据结构

一：

一序列进栈顺序为1,2,3,4,5，存在多少种可能的出栈序列。

解析

卡塔兰数的一般项公式为

二：

各种排序算法时间复杂度.

排序方法 平均时间 最好时间 最坏时间 空间复杂度
桶排序(不稳定) O(n+k) O(n+k) O(n^2) O(n+k)
基数排序(稳定) O(nk) O(nk) O(nk) O(n+k)
归并排序(稳定) O(nlogn) O(nlogn) O(nlogn) O(n)
快速排序(不稳定) O(nlogn) O(nlogn) O(n^2) O(logn)
堆排序(不稳定) O(nlogn) O(nlogn) O(nlogn) O(1)
希尔排序(不稳定) O(n^1.25) O(1)
冒泡排序(稳定) O(n^2) O(n) O(n^2) O(1)
选择排序(不稳定) O(n^2) O(n^2) O(n^2) O(1)
插入排序(稳定) O(n^2) O(n) O(n^2) O(1)

三：

二叉树不是度为2的有序树。

解析

一棵度为二的有序树与一棵二叉树的区别在于：
有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。2个结点的有序树只有一种基本形态，2个结点的二叉树具有两种基本形态。

四：

广义表中表的第一个元素为表头，其余部分构成的表为表尾，所以一个广义表的表尾始终是一个广义表。

五：

二叉树的高度和深度相同，都是二叉树中节点层数最大的值，其中根节点层数为1。

设计模式

构造器模式(类中构造静态类Builder，用于构建合法域内的对象，而非使用构造函数)
享元模式（多个对象都是同一个值，这些对象都是不可变的，就可以共享这些值，比如Integer.ValueOf）

参考资料

为什么浮点数运算会有误差

C/C++ 语言中的表达式求值