2017 IBM 技术笔试题

前言

1、请独立完成所有试题。我们很重视团队协作能力，但我们并不打算通过笔试题来考察^ ^。所以请不要对试题内容进行讨论（试题表意不清的地方可以释疑）。
2、在做题过程中，除了查看附带的参考链接，你可以尽可能地利用搜索引擎查找需要的资料。但请不要直接搜索答案，因为你搜不到。
3、如果你是没有基础的小白，当你看到一堆新名词的时候，不要害怕。这些新知识就是为你量身打造的，只要你付出时间，一定会有收获。
4、注意，只有0-7题计算分数。8-10题为选做题，不计算分数，有余力的同学可以尝试一下。

0、信息编码

（1）编码的奥秘

我们知道，在计算机内部，所有的信息最终都表示为一个二进制的字符串。每一个二进制位（bit）有0和1两种状态，因此八个二进制位就可以组合出256种状态，这被称为一个字节（byte）。也就是说，一个字节一共可以用来表示256种不同的状态，每一个状态对应一个符号，就是256个符号，从00000000到11111111。

上个世纪60年代，美国制定了一套字符编码，对英语字符与二进制位之间的关系，做了统一规定。这被称为ASCII码，一直沿用至今。

比如我需要存储字母A，那么我存入一个数字65(即在计算机中存入二进制(00100001)，这个过程叫做编码(encode)，而我们在读取数据的时候，当遇到65时，我们就让计算机显示字母A，这个过程叫做解码(decode)。

比如字符串"CQU"，通过ASCII就可以编码为三个对应的十进制数：67 81 85，在计算机内以二进制的形式存储为 01000011 01010001 01010101。

（1）现在有三个字节的二进制数据01001001 01000010 01001101，请通过ASCII标准将其解码。

参考资料：
ASCII_百度百科
字符编码笔记：ASCII，Unicode和UTF-8 - 阮一峰的网络日志

（2）简单的加密

加密是保证信息安全的最重要的方式，已知最早使用密码学的人之一是Julius Caesar，他将字母表中的每个字母正向移动三位以加密消息，这属于私钥密码系统的一种。现在我们来定义一种简单的加密系统的加密方式，加密方式如下：

1、将一串字符串转换为三位数的对应ASCII码的值，不足三位在原ASCII码左边加0补全
2、将每一个十进制三位数转换成八位的二进制进行表示，不足八位高位补齐
3、依次将每一个八位二进制的后四位与下一个数字的前四位进行交换，但是如果交换后的数字的十进制值大于等于128，则此交换不执行，继续下一次交换，第一个数字的二进制的前四位和最后一个数字的后四位保持不变
4、将第一个数字标记为十进制序号0，第二个数字十进制序号1，第三个序号2，以此类推
5、将所有的序号为偶数的八位二进制数字提取到前面，序号为奇数放到后面，例如：序号为0，1，2，3，4，5执行该步骤后会变成 0，2，4，1，3，5
6、将每一个八位二进制转换成十进制，之后对照转化成ASCII码

经过上面的6步后我们就可以进行信息的简单保护。当然这个加密系统的加密方式被熟知后进行解码也是相当简单的。
（2）现在有一串按照该方式加密的字符串，请你对其解码：FnIv?vnU

1、古诗鉴赏

小松

【唐】杜荀鹤
自小刺头深草里，而今渐觉出蓬蒿。
时人不识凌云木，直待凌云始道高。

病起书怀

【宋】陆游
病骨支离纱帽宽，孤臣万里客江干。
位卑未敢忘忧国，事定犹须待阖棺。
天地神灵扶庙社，京华父老望和銮。
出师一表通今古，夜半挑灯更细看。

请细读上面两首古诗，描述一下自己对这两首诗的理解，并谈谈感受。

2、冯诺依曼体系结构

计算机的运行需要两个前提:
一是任务描述，即描述计算机所要完成的任务，它以程序(或代码)的方式表述
二是计算机去执行具体的程序

程序是计算机指令的集合，其中每条指令对应计算机的一个基本动作。指令是程序的最小单位(或原子操作)，换句话说，一条指令要么完整地执行、要么完全不执行，计算机无法只执行指令的部分功能。

1946年，冯诺伊曼提出了计算机处理或程序执行的基础模型，图中显示了该模型的基本组成。冯诺伊曼模型包括5个组成部分: 存储器(memory)、运算器(processing unit)、输人(input)、输出 output)、控制器(control unit)。
其中，存储器负责存放程序和数据，控制器负责指令的有序执行。

下面介绍一枚游戏：人力资源机器。在这个游戏中，玩家将扮演一个从基层做起的员工，需要通过指令代码来编写一条条程序，完成每个阶段的任务，最终走上职场巅峰。是不是听起来就很有意思？

请下载该游戏试玩，并尽力挑战后面的关卡！然后尝试作答：
（1）将你最满意的一个程序截图贴到文档中
（2）描述在这个游戏中，输入、输出、存储器、运算器、控制器分别是什么？

参考资料：
《计算机系统概论》 p8, p9, p65
人力资源机器：Human Resource Machine - 知乎专栏

3、算法题：卡片游戏

　　小明最近宅在家里无聊，于是他发明了一种有趣的游戏，游戏道具是N张叠在一起的卡片，每张卡片上都有一个数字，数字的范围是0~9，游戏规则如下：
　　首先取最上方的卡片放到桌子上，然后每次取最上方的卡片，放到桌子上已有卡片序列的最右边或者最左边。当N张卡片全部都放到桌子上后，桌子上的N张卡片构成了一个数。最后这个数不能有前导0，也就是说最左边的卡片上的数字不能是0。游戏的目标是使这个数最小。
　　现在小明将这N张卡片交给你啦，请描述出你的策略，帮助小明完成游戏。

例如：卡片原本的顺序是3212，能够构成的最小的数就是1232。

4、网络基础

请通过参考资料了解IP、域名、DNS、host之间的关系，并作答：
（1）用你自己的语言简要描述IP、域名和DNS之间的关系（可以使用修辞）

参考资料
IP、域名、DNS、和host

5、了解新技术

请通过参考资料，或自行搜索，根据个人需要大致了解神经网络和机器学习的概念。如果感兴趣，也可以到A Neural Network Playground折腾折腾。

（1）根据你的了解，人工智能、机器学习、神经网络学习三者是什么关系？

斯坦福大学公开课 ：机器学习课程 第1集
（2）观看该视频前13分钟，根据视频内容简明扼要地概括该课程需要有哪些课程的基础？

参考资料：
神经网络入门- 阮一峰的网络日志

6、算法题：酿酒大师

　　贝贝是个酿酒大师，他的酒窖里有n瓶已经放好材料，刚刚保存要发酵的半成品红酒，每瓶都有1升。
　　一天，他来到自己的酒窖，觉得瓶子太多了，很占位置，于是他决定合并一些瓶子里的酒，最终保留不超过k个瓶子。可是贝贝有强迫症，每次他只会选择2个当前含酒量相同的瓶子，把1个瓶子的酒全部倒进另1个里，然后把空瓶丢弃（不能丢弃有酒的瓶子）。
　　显然在某些情况下贝贝无法达到目标，例如n=3，k=1。此时贝贝会重新准备一些新的瓶子（每瓶初始条件下都有1升红酒半成品，且容量足够大），以达到目标。
　　现在贝贝想知道，最少需要买多少新瓶子才能达到目标呢？请写下大致思路。

提示：当某些数字与‘2’有关时，我们可以将其转换为二进制表示，这时，也许你就会豁然开朗，题目将会变得so easy!

7、数据结构

　　数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。SartajSahni在他的《数据结构、算法与应用》一书中称：“数据结构是数据对象，以及存在于该对象的实例合组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（dataobject）定义为“一个数据对象是实例或值的集合”。CliffordA.Shaffer在《数据结构与算法分析》一书中的定义是：“数据结构是ADT（抽象数据类型AbstractDataType）的物理实现。”

　　cyz这个学期学了一门新课程，名叫数据结构与算法分析（C++），以前他也了解过一些数据结构，之前看到队列（queue）这个结构时觉得很有趣，想自己实现这个结构，可他只会下列选项中结构的写法，请问他能够利用下列哪些结构（一个结构可以使用多次）实现一个队列？
　　A.字典map B.链表list C.栈stack D.集合set
　　请查阅相关资料后了解它们各个的结构特性并作出选择，之后简单说明如何实现。
　

*选做题

有余力的同学可以继续尝试选做题^_^　

8、编程语言之C

请观察下面一段代码：

void* _X(void* _element[], int _elementCount, size_t _elementSize)
{
    void* result = malloc(_elementCount * _elementSize);
    if(result == NULL)
        return NULL;
    void* next = result;
    for (int i = 0; i < _elementCount; i++)
    {
        memcpy(next, _element[i], _elementSize);
        next += _elementSize;
    }
    return result;
}

这段代码表面上并没有问题，运行结果也完全正确。
（1） _X函数的功能是干什么？
（2） 这段代码其实是有一个可被攻击的漏洞，你能找出来吗？
（3） 如果你完成了第二问，你能尝试修复这段代码的漏洞吗？

9、编程语言之C++

#include<iostream>
template<typename T> void f1(T&& r){}
void f2(int&& r){}
int main(){
    int && x = 6;
    f1(x);   //line1
    f2(x);   //line2
}

（1）line2的执行是有错误，为什么?
（2）line1的执行是正常的，这又是为什么？

10、编程语言之C♯

public class Dog: Animal {
    public Dog(string name) : base(name) { }
};
public class Animal { 
    public string Name {
        get;
        private set;
    }
    public event EventHandler OnEndEat;
    public Animal(string name) => Name = name;
    public void SetName(string name){
        if (string.IsNullOrEmpty(name))
            throw new Exception("name is not define");
        Name = name;
    }
    public void Eating(string FoodName = "nothing", string time = "12:00"){
        Console.WriteLine($"After eating {FoodName} at {time}");
        OnEndEat?.Invoke(this, EventArgs.Empty);
    }
}
public class EventManagement
{
    private static ______________ _instance;
    public static _______________ Instance{
        get{
            if(_______________)
            {
                ______________________________________
            }
            return _____________;
        }
    }
    public static void Func(Animal animal) => animal.OnEndEat += Animal_OnEndEat;
    private static void Animal_OnEndEat(object sender, EventArgs e)
    { }  //do something
}

（1）请在横线上补全单例模式，同时解释下单例模式在开发中有什么作用？
（2）上述代码用了开发中那些方面的知识？