408的四门科目不谈最重要的数据结构与算法，其他的比如OS的进程管理和内存管理，计网中老生常谈的TCP/IP模型，计组中数据的表示等等，每一个都是一名合格的程序员应该重点掌握的内容。

所以F1a;虽然你不一定考研，但跟着做题加深理解总没错的 ✔

每天都会更新2~3篇直到追上进度（上次一天更了10篇），欢迎关注我或者我的专栏。

习题来源于@王道微博

解析都是我自己写的，如有问题或错漏烦请评论告知。

🔑数据结构

设有6个结点的无向图，该图至少应有____条边才能确保是一个连通图。（中国科学院大学2012）

A. 5
B. 6
C. 7
D. 11

答案及解析

答案：D

🔊 连通图是指任意两个结点之间都有一个路径相连，只要有连线能相通就好。如果任意两个顶点之间都存在边，则称该无向图为完全无向图。

可能有的人上来就选A了，O-O-O-O-O-O，显然6个点最少5条边就可以了，但是题上说确保是一个连通图。

确保的话是考虑最极端的情况，即5个顶点构成一个完全无向图，再连上第6个顶点才是连通图，有：

C 5 2 + 1 = 5 ∗ 4 2 ∗ 1 + 1 = 11 C_5^2 + 1 = frac{5*4}{2*1} +1 = 11 C52​+@H_406_93@1=2∗15∗4​+1=11

如果边数小于11，当5个顶点构成完全无向图时，该图并不是一个连通图，故选D。

📠计算机网络

下面关于提供虚电路服务的网络的论述中哪个是不正确的____（北京邮电大学2011）

A. 每个分组都有完整的目的地址
B. 需要建立连接
C. 属于同一条虚电路的分组按照同一路由进行转发
D. 可靠通信由网络来保证

答案及解析

答案：A

🔊 虚电路服务：在分组发送之前，要求发送方与接收方之间建立一条逻辑上相连的虚电路，以此固定虚电路所对应的物理路径。

有以下特点：

• 必须要建立连接，保证分组有序到达。
• 目的地址仅在建立连接阶段使用，之后每个分组使用长度较短的虚电路号，故选A。
• 属于同一条虚电路的分组按照同一路由进行转发。
• 所有经过故障节点的虚电路均不能正常工作，可靠性由网络保证。
• 由网络或用户主机负责差错处理以及流量控制。

🏆计算机组成原理

挂接在总线上的多个部件___（北京科技大学2014）

A. 只能分时向总线发送数据并只能分时从总线接收数据
B. 只能分时向总线发送数据但可同时从总线接收数据
C. 可同时向总线发送数据，并同时从总线接收数据
D. 可同时向总线发送数据，但只能分时从总线接收数据

答案及解析

答案：B

🔊 总线是一组能为多个部件分时共享的公共信息传送线路。

分时是指同一时刻只允许有一个部件向总线发送信息，如果出现两个或两个以上部件同时向总线发送信息，势必导致信号冲突。

共享是指总线上可以挂接多个部件，各个部件之间相互交换的信息都可以通过这组公共线路传送，在同一时刻，允许多个部件同时从总线上接收相同的信息。

💻操作系统

___算法产生的缺页率最小，但不是实用的页面淘汰算法（北京航空航天大学2015）

A. FIFO
B. OPT
C. LRU
D. clock

答案及解析

答案：B

🔊 最佳OPT(Optimal)置换算法，其淘汰的是以后不再使用或是很长时间内不再使用的页面，以保证缺页率最小。

然而这是不可能实现的，因为人目前无法预知哪些页面不会用到，所以OPT算法更多的是用来评价其他算法。