C语⾔开发云计算,2021武汉噢易云计算CC++开发⼯程师线下
笔试题
2014年阿⾥巴巴笔试题
⼀、选择题
11.
n从1开始，每个操作可以选择对n加1或者对n加倍。若想获得整数1011，最少需要多少个操作
答案为16 同样按照奇数-1，偶数/2逆推
1011 1010 505 504 252 126 63 62 31 30 15 14 7 6 3 2
12.在c++程序中，如果⼀个整型变量频繁使⽤，最好将他定义为()
如果⼀个变量被频繁使⽤，需保存在寄存器中，因为寄存器的速度要⽐内存快的许多。在早期的编译器中需要⼿动定义为register型，但是后来编译器可以⾃动将调⽤次数多的变量放⼊寄存器中。
auto: 给变量动态分配内存，默认的分配类型。⼀般不需要⼿动声明了；
static：静态分配内存。变量在整个作⽤域内是全局变量。
extern : 声明为外部变量；在函数的外部定义变量；
13.考虑⼀个特殊的hash函数h，能将任⼀字符串hash成⼀个整数k，其概率P(k)=2^(-k),k=1,2,…,∞。对⼀个未知⼤⼩的字符串集合S中的每⼀个元素取hash值所组成的集合为h(S)。若h(S)中最⼤的元素Maxh(S)=10，那么S的⼤⼩的期望是()
hash函数问题，好家伙看不懂
16.结构体对齐问题
// 对齐原则：每⼀成员需对齐为后⼀成员类型的倍数
// 补齐原则：最终⼤⼩补齐为成员类型最⼤值的倍数
structA
{
inta;    // 4
shortb;  // (4) + 2 = 6 下⼀元素为 int，需对齐为 4 的倍数， 6 + (2) = 8
intc;    // (8) + 4 = (12)
chard;    // (12) + 1 = 13， 需补齐为 4 的倍数，13 + (3) = 16
};
structB
{
inta;    // 4
shortb;  // (4) + 2 = 6，下⼀成员为 char 类型，不考虑对齐
charc;    // (6) + 1 = 7，下⼀成员为 int 类型，需对其为 4 的倍数，7 + (1) = 8
intd;    // (8) + 4 = 12，已是 4 的倍数
}
17.TCP和UDP
TCP的⾯向连接指对话之前需要先建⽴⼀个会话，⽽UDP⽆连接直接发送消息
再补充⼀个有确认和⽆确认，有确认⽆确认与有连接⽆连接没有必然联系。有⽆确认区别主要在消息发送出去之后。
UDP的传输效率⽐TPC⾼，因为不需要确认接收端是否收到，不⽤浪费等待的时间
20.mac地址
21.两个线程执⾏语句问题
按照语句是按照先后的执⾏顺序，但是线程之间先执⾏哪个语句就不确定，按照可能性，写出了⼏种可能性:
(1)r1=0,r2=1(2)r1=1,r2=1;(3)r1=1,r2=0; ⽽不可能出现两个都为0的情况
22.堆和栈的说明
***动态存储⽅式----->动态存储区
栈：由编译器⾃动分配释放，存放函数的参数值，局部变量等值。其操作⽅式类似于数据结构中的栈。
会存放函数的返回地址、参数和局部变量
堆：⼀般由程序员分配释放，  若程序员不释放，程序结束时可能由OS回收。注意它与数据结构中的堆是两回事，分配⽅式倒是类似于链表，呵呵。
查看后续更加具体的栈和堆的区别[1]
**静态存储⽅式----->静态存储区---------静态区/全局区
常量、常变量(const 变量)、静态变量、全局变量
栈(satck)：由系统⾃动分配
程序运⾏时由编译器⾃动分配的⼀块连续的内容，存放函数的参数值，局部变量的值等。 例如，声明在函数中⼀个局部变量int b；系统⾃动在栈中为b开辟空间。
程序结束时由编译器⾃动释放
栈由系统⾃动分配，程序员⽆法控制
只要栈的剩余空间⼤于所申请空间，系统将为程序提供内存，否则将报异常提⽰栈溢出。
存取⽅式，先进后出
堆(heap):
在内存开辟另⼀块不连续的存储区域。⼀般由程序员分配释放，
若程序员不释放，程序结束时由系统回收
⾸先应该知道操作系统有⼀个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻第⼀个空间⼤于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序。
需程序员⾃⼰申请(调⽤malloc,realloc,calloc)，并指明⼤⼩，并由程序员进⾏释放。容易产⽣memory leak.
23.排序算法的时间复杂度
排序⽅法
时间复杂度(平均)
时间复杂度(最坏)
时间复杂度(最好)
空间复杂度稳定性
复杂性
直接插⼊排序O(n2)
O(n2)
O(n)
O(1)
稳定
简单
希尔排序
O(nlog2n)
O(n2)
O(n1.3)
O(1)
不稳定
较复杂
直接选择排序O(n2)
O(n2)
O(n2)
O(1)
不稳定
简单
O(nlog2n)
O(nlog2n)
O(nlog2n)
O(1)
不稳定
较复杂
冒泡排序
O(n2)
O(n2)
O(n)
O(1)
稳定
简单
快速排序
O(nlog2n)
O(n2)
O(nlog2n)
O(nlog2n)
不稳定
较复杂
归并排序
O(nlog2n)
O(nlog2n)
O(nlog2n)
O(n)
稳定
较复杂
基数排序
O(d(n+r))
O(d(n+r))
O(d(n+r))
O(n+r)
稳定
较复杂
24.假定函数rand_k会随机返回⼀个[1，k]之间的整数(k＞=2)，并且每个整数值出现的⼏率相等。已知⽬前有rand_7的实现，请问通过调⽤rand_7和四则运算函数，并适当增加逻辑判断和循环等控制逻辑，下列函数可以实现的有______。
rand_7*7 = 7,14,21,28,35,42,49=A
rank_7 = 1,2,3,4,5,6,7=B
A,B任取⼀个元素求和，这个和出现概率都相同1/7*1/7.
因此rand_7*7 + rank_7 = [8,56]的每个元素是等概率的
rand_7*7 + rank_7 -7= [1,49]的每个元素是等概率的
所以：
int rand_k(){ n=50; while(n>k)n= rand_7*7 + rank_7 -7;return n;}/* 删去所有⼤于k的数字 */
但是rand_7*8这种⽅式就得不到均匀分布了  ， 因此rank_1,...rank_49均可实现，也只能实现这49中情况。
三、填空题
27.以下程序的输出结果是____2,4_____________
int a[5] = {1, 2, 3, 4, 5};
int *ptr=(int *)(&a+1); //主要是这⼀句，&a是整个数组的地址，+1就是让ptr指向a[5]这个内存位置
printf("%d, %d/n", *(a+1), *(ptr-2)); 指向下⼀个数组⼤⼩内存的位置，因为是⼀位数组，所以指向的是下⼀个数组元素第⼀个的地
址，ptr-2 就是减去两个元素个数的地址位置
可以去了解指针数组
28.LRU页⾯置换算法
需要看书，⼀共4页物理内存，
⾸先序列是1234
1243 3命中后 对序列重新排序
1432 2命中
1324 4命中
3241 1命中
2415 物理页数不够删除3，因为3使⽤评率最低
4156 删除2
1567 删除4
1576 6命中
5763 删除1
答案为5763
29.三个球，红黄⽩，求颜⾊各部相同的概率，少算了两个rww，ryy
rrr
rry
rrw
ryr
rwr
ryw
rwy
rww
ryy
每个球是九种，⼀共27种可能性，颜⾊不全相同的概率为 (27-3)/27 3种全相同，约分后为 8/9
c语言的冒泡排序算法malloc()、calloc()、realloc() 的区别  暂时记录在这⾥
堆是使⽤malloc()、calloc()、realloc()等函数动态分配的，⽽使⽤alloca()函数可以动态分配栈的内存空间，释放的时候由编译器⾃⼰释放字符串匹配，链表基础操作

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。