2020-8-18

1.20个阿里巴巴B2B技术部的员工被安排为4排，每排5个人，我们任意选其中4人送给他们一人一本《effective c++》，那么我们选出的4人都在不同排的概率为：5^44!16!/20!
解析：
总共就选4个人，所以C(20,4),
这四个人，都是从每一排5个人中选出C(5,1)4
结果54/C(20,4) = 54/(20!/(16!4!)) = 544!*16!/20!

=====================================================================================

2.二分查找，初始为下标为 (0+(n-1))//2

=====================================================================================

3.perl里面声明：open（FILE,mode，file）; 操作的描述，下列哪项不正确？
图片说明
"filepath" 以只读模式打开文件.
">filepath" 以写模式打开文件.
">>filepath" 以追加模式打开文件,写和追加的区别在于写模式将原文件覆盖,而追加模式则在文件末尾处添加内容.
"+>filepath" 以读和写方式打开文件.
"+>>filepath" 以读和追加方式打开文件.

=====================================================================================

4.有一个虚拟存储系统，若进程在内存中占3页（开始时内存为空），若采用先进先出（FIFO）页面淘汰算法，当执行如下访问页号序列后1，2，3，4，5, 1，2，5，1，2，3，4，5，会发生多少缺页？
图片说明
缺页就是，即将访问的不在当前访问中，然后淘汰最早进入的

=====================================================================================

5.文件索引
采用索引这种结构，逻辑上连续的文件可以存放在若干不连续的物理块中，
但对于每个文件，在存储介质中除存储文件本身外，还要求系统另外建立一张索引表。
索引结构既适用于顺序存取，也适用于随机存取，并且访问速度快，文件长度可以动态变化。
索引结构的缺点是由于使用了索引表而增加了存储空间的开销。

=====================================================================================

6.在ASC算法team日常开发中，常常面临一些数据结构的抉择，令人纠结。目前大家在策划一个FBI项目（Fast Binary Indexing），其中用到的词汇有6200条，词汇长度在10-15之间，词汇字符是英文字母，区分大小写。请在下面几个数据结构中选择一个使检索速度最快的：
图片说明
Trie树，又称单词查找树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高

=====================================================================================

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

图片说明

=====================================================================================

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

=====================================================================================

9.在排序方法中，元素比较次数与元素的初始排列无关的是（）
图片来源作者https://www.nowcoder.com/profile/242025553
图片标题

=====================================================================================

10.假设在n进制下，下面的等式成立，n值是（） 567*456=150216
图片说明

=====================================================================================

11.定义一个函数指针，指向的函数有两个int形参并且返回一个函数指针，返回的指针指向一个有一个int形参且返回int的函数？
图片说明

=====================================================================================

12.声明一个指向含有10个元素的数组的指针，其中每个元素是一个函数指针，该函数的返回值是int，参数是int，正确的是（）int((*p)[10]))(int *)

首先题目说要声明一个数组指针, 一般我们想到的数组指针是随便来一个 int(p)[10], 然后又说每个元素是一个函数指针,那么我们随便来一个函数指针 int (pf)(int *) . 然后把(p)[10]作为一个整体替代 pf即int((p)[10]))(int ); 分析: 判断一个复杂式子看最高优先级的,p是一个指针,然后(p)外面是[],所以是数组指针,(p)[10])描述完毕,然后再看外面int()(int *)很明显,这是一个函数指针,所以这个数组中每个元素是函数指针

=====================================================================================

13.

语句3应该为Foo b，但语句3没出错语句4出错了，出错提示request for member 'fun' in 'b', which is of non-class type 'Foo()'。感觉似乎语句3被解释成函数声明了，b成了函数指针，没有成员fun()。

=====================================================================================

14.

首先，#pragma pack(2) 强制设定为2字节对齐

i 4字节
u 一个为13，一个为4，默认为4字节对齐；
union占对齐后数据的最大字节大小，默认为13+3=44=16；
但是，该处强制为2字节对齐，实际为13+1=27=14字节
color 枚举类型的实例 4字节

4+14+4=22字节

=====================================================================================

15.
图片说明

C++ STL 的实现：

1.vector  底层数据结构为数组 ，支持快速随机访问

2.list    底层数据结构为双向链表，支持快速增删

3.deque   底层数据结构为一个***控制器和多个缓冲区，详细见STL源码剖析P146，支持首尾（中间不能）快速增删，也支持随机访问

4.stack   底层一般用23实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

5.queue   底层一般用23实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

6.45是适配器,而不叫容器，因为是对容器的再封装

7.priority_queue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现

8.set       底层数据结构为红黑树，有序，不重复

9.multiset  底层数据结构为红黑树，有序，可重复 

10.map      底层数据结构为红黑树，有序，不重复

11.multimap 底层数据结构为红黑树，有序，可重复

12.hash_set 底层数据结构为hash表，无序，不重复

13.hash_multiset 底层数据结构为hash表，无序，可重复 

14.hash_map      底层数据结构为hash表，无序，不重复

15.hash_multimap 底层数据结构为hash表，无序，可重复

=====================================================================================

16.
图片说明
让快慢指针都从链表表头开始，快指针一次向前移动连个位置，慢指针每次向前移动一个位置。如果快指针到达了NULL，说明不存在环，但如果快指针追上了慢指针，说明存在环。