一套笔试题

Posted by zhangxiaojian on September 14, 2015

前一阵想着能不能挣点外块改善生活,就应聘当某在线教育的解题员,这是阿里几年前的一套笔试题,也是让我试着做的题。看了下,网上应该没有解答这么详细的,毕竟也花了一些功夫。至于应聘,觉得此公司有点混乱,就罢了。另外貌似也失去了改善生活的动力。不过好东西,还是要放出来~

1.有一个虚拟存储系统,若进程在内存中占3页(开始时内存为空),若采用先进先出(FIFO)页面淘汰算法,当执行如下访问页号序列后1,2,3,4,5,1,2,5,1,2,3,4,5,会发生多少缺页?

A、7              B、8                            C、9                          D10

 解析:进程在内存中有3页,如果访问的页号不在内存中,就发生了一次缺页。缺页后换出内存中最先被加载进来的页,同时将要访问的页加载进内存(FIFO)。按照题中顺序(注意开始内存为空):表格下方是每次请求表格上方页时内存中的页队列。

t1

2.设有一个顺序栈S,元素s1、s2、s3、s4、s5、s6依次进栈,如果6个元素的出栈顺序为s2、s3、s4、s6、s5、s1,则顺序栈的容量至少应为多少? 

  • A、2                     **B**、3                            C、4                           D、5

解析:栈的特点是后进先出。

第一个出栈的是s2,那么s1肯定在栈中,s2出栈后s3和s4分别进栈,出栈。接着s5,s6

进栈。此时栈空间为3。最后s6,s5,s1依次出栈。如图所示:

3.下列关于文件索引结构的叙述中,哪一个是错误的?

A、采用索引结构,逻辑上连续的文件存放在连续的物理块中 B、系统为每个文件建立一张索引表 C、索引结构的优点是访问速度快,文件长度可以动态变化 D、索引结构的缺点是存储开销大

解析:索引结构将一个逻辑文件的信息存放在外存的若干物理块中,这些物理块可以不连续。系统为每个文件建立一个索引表,索引表存放文件信息所在的逻辑块号和与之对应的物理块号。优点是可以进行随机访问,文件增删比较方便。但是索引表增大了存储开销。

4【0、2、1、4、3、9、5、8、6、7】是以数组形式存储的最小堆,删除堆顶元素0后的结果是()

A、【2、1、4、3、9、5、8、6、7】 B、【1、2、5、4、3、9、8、6、7】 C、【2、3、1、4、7、9、5、8、6】 D、【1、2、5、4、3、9、7、8、6】

解析最小堆是一颗二叉树,根节点的值始终小于它的左右孩子节点。使用数组表示的最小堆如左图所示:

t3

选取堆中最后一个叶子节点7作为堆顶元素,自上而下进行调整:7大于左右孩子节点,而右孩子节点1小于左孩子节点2,将1和7交换位置。此时右子树堆被破坏,采用相同的方式自定向下调整,交换7和5的位置即可。答案如右图所示。

5.某页式存储管理系统中,地址寄存器长度为24位,其中页号占14位,则主存的分块大小是()字节。

A、10       B2^10       C、2^14                     D、2^24

解析页式存储首先根据虚拟地址找到页表,再通过页表链接到实际的内存块。如图所示:虚拟地址一共24bit,页号14bit 用来寻找对应的页表条目,页表条目中存的是内存块的物理地址。10bit的寻址空间表示页偏移,也就是一个内存块的大小。

t4

6.在一个长为33厘米的光滑凹轨上,在第3厘米、第6厘米、第19厘米、第22厘米、第26厘米处各有一个钢珠,凹轨很细,不能同时通过两个钢珠,开始时,钢珠运动方向是任意的。两个钢珠相撞后,以相同速度反向运动。假设所有钢珠初始速度为每秒运动1厘米,那么所有钢珠离开凹轨的最长可能时间是()

A、30      B、26                        C、38                      D、33

解析:要时间最长就要求钢珠碰撞次数尽量多,而且尽量靠近凹轨的中部,中部是15.15cm处,那么初始化运动方向就是这样(这里把凹轨抽象成一条直线):

t5

这里需要注意一个细节,AB的距离和CD的距离相等。

  • BC第一次相撞,耗时5s,相撞位置12.5cm处。

  • 此时BC反向,耗时5s,分别同时与AD相撞,此时相撞后A出轨,不必考虑。AB在12.5-1.5 = 11cm处相撞。CD在12.5+1.5 = 14cm处相撞。

  • BC此时距离3cm,DE距离4cm。BC耗时5s第二次相撞,位置依然是12.5cm处。B相撞后出轨。此时DE距离相撞还有0.5s,C与D同向右运动0.5s,DE相撞时C在12.5+0.5 = 13cm处。DE相撞在13+3 = 16cm处。E出轨。

  • 最终剩下C和D,C在13cm处,D在16cm处。它们耗时5s在14.5cm处相撞。14.5 < 15.15。最后出轨的是D,从右边出轨,耗时33-14.5 = **18.5s**

  • 5 + 1.5 + 1.5 + 0.5 + 1.5 + 18.5 = 30s

7.std::vector::iterator重载了下面哪些运算符? **A++**        B、»                      **C**(前置)                   D==

解析:iterator的行为像普通指针一样,可以自增++,*解引用,==比较。但却不能»进行移位操作。

8.下列运算符,在C++语言中不能重载的是()

A、*           B、?:     C::                           D、delete

解析c++中不能重载的操作符有包括 ::   .*   .   ?:   四种。

9.在排序方法中,元素比较次数与元素的初始排列无关的是()

A、Shell 排序 B、归并排序 C、直接插入排序                D、选择

解析:直接插入排序和Shell排序首先淘汰,直接插入排序在基本有序的时候时间复杂度O(n),每个元素进来只需要一次比较即可。Shell排序是直接插入排序的改进,在直接插入排序之前,先经过几次比较交换使元素初始排列基本有序,再执行插入排序。归并排序在子序列两两合并的时候仍然需要比较,如果两个序列本身就有序,那么只需要一次比较,如果无序,比较次数就不止一次。选择排序,每次从n-i+1个记录中选取最小的记录放在第i个位置,每选择一次都要便利比较剩下的n-i+1个记录,因此比较次数与序列长度有关,与初始化位置无关。

10.给定如下代码: int x[4]={0}; int y[4]={1}; 数组x和y的值为()

A、{0,0,0,0},{1,1,1,1} B、{0,0,0,0},{1,0,0,0} C、{0,不确定},{1,不确定} D、与编译器相关

解析:当数组使用 {} 进行初始化时,首先使用变量的默认初始化方式初始化数组中每个元素,然后再使用{}中的值进行赋值操作。int 默认初始化为0。

11.给出以下定义,下列哪些操作是合法的?

const char p1 = “hello”; char const p2 = “world”; A、p1++                      Bp1[2]=’w’; C、p2[2]=’l’;                    D、p2++

解析: const char* **表示char类型的指针,且指针的值const,不能被修改。char* const 表示char类型的指针,且指针所指内容是const,内容值不可被修改。A和D修改的是指针,B和C修改的是指针指向的内容。**

12.假设在n进制下,下面的等式成立,n值是() 567*456=150216

A、9                B、10                 C12                     D18

解析:直接进行乘法计算,首先根据结果个位为6,淘汰10进制。18进制计算如下:

t6

13.关于struct和class,下列说法正确的是()

Astruct的成员默认是public,class的成员默认是private B、struct不能继承,class可以继承 C、struct可以有无参构造函数 D、struct的成员变量只能是public

解析:struct是c语言关键字,c++引入class后,为了兼容c语言,仍保留struct关键字,它们唯一的区别就是struct默认是public,class模式是private。

14.定义一个函数指针,指向的函数有两个int形参并且返回一个函数指针,返回的指针指向一个有一个int形参且返回int的函数?

Aint ((F)(int, int))(int) B、int (F)(int, int) C、int ((F)(int, int)) D、(*F)(int, int)(int)

解析:为了方便理解,首先假设返回的是一个int值,那么应该是这样:int (F)(int,int) 。现在需要返回的是一个函数指针,类型为 int (F)(int)。合并起来,int ((F))(int,int)(int)。

比较绕,一般的指针类型 都是Type* value,这种形式,函数指针不同之处是把形参放在了value的后面,Type* value(arg1,arg2…)。

选项B C D都有不同程度的信息丢失,B返回值为int。C返回值少了形参。D 返回值少了返回的函数指针的返回类型。

15.声明一个指向含有10个元素的数组的指针,其中每个元素是一个函数指针,该函数的返回值是int,参数是int*,正确的是()

A、(int p[10])(int); B、int [10]p(int *); C、int ((p)[10])(int *); D、int ((int *)[10])p; E、以上选项都不正确

解析函数指针类型int (F)(int) , 数组中含有的数据类型是函数指针,数组的声明方式是 Type p[10]。使用函数指针替换Type,注意形参在后面。(int* p[10]) (int*)。

B声明了一个函数指针,返回类型是int类型大小为10的数组指针。C 声明的数组返回的函数指针类型为 int* (F)(int),函数的返回类型是int*,不是int。D 是错误的,编译不能通过。

16.一个栈的输入序列为….n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是()

A、不确定 Bn-i+1 C、i D、n-i

解析:栈的特点是后进先出,第一个出栈的是n,那么出栈顺序只能是n ,n-1 ,n-2 … 1。输出第i个元素的值与i的和为 n+1 。所以第i个元素值为 n-i+1。

17.下列代码编译时会产生错误的是()

#include <iostream>
using namespace std;
struct Foo
{
    Foo() {  }
    Foo(int) {  }
    void fun()   {  }
};
int main(void)
{
    Foo a(10);    //语句1
        fun();      //语句2
        Foo b();      //语句3
        fun();      //语句4
        return 0;
}

A  语句1             B、语句2           C、语句3             D**、语句**4

解析编译器在理解语句3的时候会把它当作返回值类型为Foo的函数声明,b是函数指针,并不是类对象。因此语句4会报错。

  1. 在32位机器上,下列代码中
#pragma pack(2)
class A
{
    int i;
    union U
    {
        char buff[13];
        int i;
    }u;
    void foo() {    }
    typedef char* (*f)(void*);
    enum{red, green, blue} color;
}a;

sizeof(a)的值是()

A、20       B、21       C、22        D、24           E、非以上选项

解析对齐规则是:

1数据成员对齐规则:结构(struct)(或联合(union))的数据成员,第一个数据成员放在offset为0的地方,以后每个数据成员的对齐按照#pragma pack指定的数值和这个数据成员自身长度中,比较小的那个进行。

2、结构(或联合)的整体对齐规则:在数据成员完成各自对齐之后,结构(或联合)本身也要进行对齐,对齐将按照#pragma pack指定的数值和结构(或联合)最大数据成员长度中,比较小的那个进行。

本题中#pragma pack = 2。

第一步根据数据成员对齐:

int i;  **起始offset=0,min(#pragma pack,sizeof(int))=2。满足0%2 = 0 。i存放在offset 0~3的地方。**

union的大小由其中最大的成员表示;min(#pragma pack,sizeof(union))=2。此时offset = 4,满足 4%2 = 0。Union存放在offset 4~16的地方。

成员函数和类型并不会影响类空间大小。

enum枚举类型不论其中枚举数量的多少,大小始终为sizeof(int),32位机就是4。min(#prama pack,sizof(enum)) = 2,此时的offset=17,显然17%2 != 0。因此空一位,enum从offset=18的地方存,存在offset 18~21。此时总体大小22.

第二步整个struct对齐:

struct最大元素大小13,min(#prama pack, max{strcut} ) = 2。整体大小22%2=0。满足条件。

得出最后大小sizeof(a)=22

19 .下面描述中,错误的是()

A、基类定义的public成员在公有继承的派生类中可见,也能在类外被访问 B、基类定义的publicprotected成员在私有继承的派生类中可见,在类外可以被访问 C、基类定义的publicprotected成员在保护继承的派生类中不可见 D、基类定义的protected成员在protected继承的派生类中可见,也能在类外被访问

解析:public成员类内外都可见,protected成员类外不可见,子类可见,private成员只有类本身可见。当继承基类时,使用public继承,基类成员的访问权限不变。使用protected继承,基类的public继承后在子类访问权限变为protected。使用private继承,基类所有访问权限在子类中都视为private。

  1. 当很频繁地对序列中部进行插入和删除操作时,应该选择使用的容器是()

A、vector    Blist     C、deque      D、stack

解析:vector 和deque都支持随机访问,访问每个元素的时间都是常数。因为它们的数据在内存中是连续存放或分段连续存放,像数组一样,知道首地址和偏移就可以定位数据位置。但是在中部插入删除需要大批移动内存中的数据,比如在0-100个数据中插入50,那么就意味着51-100位置的数据统一向后移动。开销很大。Stack严格意义上并不是容器,而是容器适配器,一般用deque实现。List不支持随机访问,内部是双向环状链表,在中间位置插入删除只需修改链表的前后指针即可。

  1. 判断一个单向链表中是否存在环的最佳方法是()

A、两重遍历   B、快慢指针 C、路径记录       D、哈希表辅助

解析:两重遍历,路径记录,哈希表辅助本质上都是记录走过的链表位置,第一需要额外的存储空间,空间复杂度O(n)。第二需要搜索,每次访问一个元素就需要在存储区搜索一次该元素是否存在。哈希表可以降低搜索的时间复杂度,但空间复杂度始终存在。使用快慢指针不需要额外的空间,快慢指针如果相遇,就说明有环。

22、给你1、2、3 这三个数字 可以使用C的各种运算符 你能表示的最大的整数是()

A、23sizeof(1)             B、3«(2«sizeof(1))                    C、sizeof(3)«(sizeof(2)«(sizeof(1)))                    D、(unsigned long)(2-3)*1

-1的二进制形式就是全1表示

解析A **:234 = 24 **

      B  : 2 « 4 = 2^4 = 16     3 « 16 = 3 * 2^16

      C  : 4 « 4 « 4 = 4* 2^4 * 2^4 = 2^10

      D  : sizeof(long)在32位机器上是4字节,-1的十六进制表示为FFFFFFFF,转换成unsigned大小为: 2^32 – 1。