C++ 笔试题整理一

迈不过友情╰ 2022-08-04 15:50 239阅读 0赞

**1、下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的是（）**  
A、插入排序 B、堆排序 C、冒泡排序 D、快速排序

答案: A

(插入排序：最优时间复杂度O(n)最差时间复杂度O(n^2)平均时间复杂度O(n^2)  
冒泡排序：最优时间复杂度O(n)最差时间复杂度O(n^2)平均时间复杂度O(n^2)  
快速排序：最优时间复杂度O(nlogn)最差时间复杂度O(n^2)平均时间复杂度O(nlogn)  
堆排序：最优时间复杂度O(nlogn)最差时间复杂度O(nlogn)平均时间复杂度O(nlogn))

**2、以下关于Cache的叙述中，正确的是（）**  
A、CPU中的Cache容量应大于CPU之外的Cache容量  
B、Cache的设计思想是在合理成本下提高命中率  
C、Cache的设计目标是容量尽可能与主存容量相等  
D、在容量确定的情况下，替换算法的时间复杂度是影响Cache命中率的关键因素

答案:B  
Cache（高速缓冲器）容量小于主存，但速度快于主存，慢于CPU，相当于CPU和主存间的一个缓冲器，Cache中存放最近使用过的内存内容（基于最近使用过的内容很可能被再次使用的原理）。若CPU寻访的内容在Cache中存放，则优先从Cache中读取，称为命中，否则称为脱靶，脱靶只能从主存中读取内容了。当Cache存储满的时候，用替换算法清理掉不用的内容，保留下最新或最常使用的内容，称为替换。Cache设计目标是提高命中率。替换算法确实是影响Cache命中率，但还有Cache容量、存储单元大小、组数多少、地址比较方法、写操作方法等都会影响Cache命中率。

**3、随着IP网络的发展，为了节省可分配的注册IP地址，有一些地址被拿出来用于私有IP地址，以下不属于私有IP地址范围的是（）**  
A、10.6.207.84 B、172.23.30.28 C、172.32.50.80 D、192.168.1.100

答案C  
私有IP地址范围：  
A: 10.0.0.0~10.255.255.255 即10.0.0.0/8  
B:172.16.0.0~172.31.255.255即172.16.0.0/12  
C:192.168.0.0~192.168.255.255 即192.168.0.0/16

这些地址是不会被Internet分配的，它们在Internet上也不会被路由，虽然它们不能直接和Internet网连接，但通过技术手段仍旧可以和 Internet通讯（NAT技术）。我们可以根据需要来选择适当的地址类，在内部局域网中将这些地址像公用IP地址一样地使用。在Internet上，有些不需要与 Internet通讯的设备，如打印机、可管理集线器等也可以使用这些地址，以节省IP地址资源。

**4、表达式“X=A+B\*（C–D）/E”的后缀表示形式可以为（）**  
A、XAB+CDE/-\*=  
B、XA+BC-DE/\*=  
C、XABCD-\*E/+=  
D、XABCDE+\*/=

答案 C  
一个中缀式到其他式子的转换方法~~  
这里我给出一个中缀表达式~  
a+b\*c-(d+e)  
第一步：按照运算符的优先级对所有的运算单位加括号~  
式子变成拉：((a+(b\*c))-(d+e))  
第二步：转换前缀与后缀表达式  
前缀：把运算符号移动到对应的括号前面  
则变成拉：-( +(a \*(bc)) +(de))  
把括号去掉：-+a\*bc+de 前缀式子出现  
后缀：把运算符号移动到对应的括号后面  
则变成拉：((a(bc)\* )- (de)+ )-  
把括号去掉：abc\*-de+- 后缀式子出现  
发现没有，前缀式，后缀式是不需要用括号来进行优先级的确定的。

**5、TCP/IP模型的体系结构中，ICMP协议属于（ ）。**  
A 应用层  
B 网络层  
C 数据链路层  
D 传输层

答案 B  
应用层协议：FTP、Telnet、HTTP、DNS  
传输层：TCP、UDP  
网络层：IP、ARP、ICMP

**6、下列描述的不是链表的优点是（ ）**  
A 逻辑上相邻的结点物理上不必邻接  
B 插进、删除运算操纵方便，不必移动结点  
C 所需存储空间比线性表节省  
D 无需事先估计存储空间的大小  
答案：C  
由于链表有指针域还有数据域，没有线性表省。

**8、设无向图的顶点个数为n，则该图最多有（ ）条边。**  
A n-1  
B n(n-1)/2  
C n2  
D n(n+1)/2  
答案 B  
任意两个点之间都有连线。  
如果是连通图的话，线至少为n-1