408 | 【2009年】计算机统考真题 自用回顾知识点整理
选择题
T4：DS —— 平衡二叉树定义：任意结点的左、右子树高度差的绝对值不超过1
T7： 无向连通图
边数大于顶点个数减1 （错。树）
T8： B树及其基本操作、B+树的基本概念（RBT）
B树（多路平衡查找树）
B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。
一棵m阶B树或为空树，或为满足如下特性的m叉树：
具有n个关键字的m阶B树，应有n+1个叶节点。
B树的插入和删除
B+树（类似多级分块查找）
在图形上的显著区别：B+树有一个个单独的叶子结点（包含数据信息）
B树和B+树_ZJE_ANDY的博客-CSDN博客
T9：堆排序
T10：排序算法
- 冒泡排序和选择排序，每一趟都能确定一个元素的最终位置。
- 插入排序在每趟排序后都能确定前面的若干元素有序。
- 归并排序，第一趟排序结束后就可以得到若干个有序子序列。
T13：CO —— IEEE754
T17：CISC与RISC
T18：CPU流水线时钟周期应以最长的执行时间为准。
T20：总线性能指标
- 总线周期/总线的传输周期：一次总线操作所需时间，包括申请阶段、寻址阶段、传输阶段、结束阶段。注意，它不等同于时钟周期。
- 总线时钟周期/CPU时钟周期/机器时钟周期：都是时钟周期，只是说法不同而已。
- 总线的工作频率：总线周期的倒数。
- 主频/总线的时钟频率：时钟周期的倒数。
- 总线宽度：数据总线的位数。
- 总线带宽：总线的数据传输率，通常是每秒传送的字节数。总线工作频率 × （总线宽度 * 8）
- 总线复用：一种信号线在不同的时间传输不同的信息，因此可以使用较少的线传输更多的信息，节约空间和成本。
- 信号线数：3种总线数之和。
- 总线最主要的性能指标：总线带宽=总线宽度*总线工作频率
T22：OS —— 中断的分类
T27：内存分配保护措施
T28：文件物理结构
T31：文件共享 硬链接和软链接
硬链接（基于索引结点的共享方式）
文件目录中只设置文件名和相应索引结点指针
owner、count
软链接（利用符号链实现文件共享）
LINK类型文件，根据路径名进行读
只有文件主才拥有指向索引结点的指针，其他共享用户仅有路径名
T34：CN —— 物理层 ——奈奎斯特定理与香农定理
T35：数据链路层 —— 流量控制 滑动窗口 后退N帧协议
T36：数据链路层 —— 以太网交换机进行转发决策时使用的PDU地址是 目的物理地址。
以太网交换机的最高层为数据链路层（除三层交换机外)，而IP地址属于TCP/IP体系的网际层，选项B和D被排除。
不要被物理地址中的“物理”二字所误导，误认为物理地址属于网络体系结构的物理层。
物理地址属于数据链路层。物理地址又称为硬件地址、MAC地址。
以太网交换机转发PDU(协议数据单元，对于以太网来说就是帧)时，当然要依据PDU所要去的地址（也就是帧的目的物理地址)来转发PDU。选项A正确。
以太网交换机收到PDU后，进行自学习，记录PDU的源物理地址以及进入交换机的端口号。选项C错误。
T39：TCP拥塞控制
T40：FTP文件传输 使用TCP协议
仅 控制连接与数据连接（控制信息带外传送）
是否使用TCP 20 端口建立数据连接与传输模式有关
主动方式使用TCP20端口（服务器端）
被动方式由服务器和客户端自行协商决定（端口>1024）
连接时：先控制、后数据
断开时：先数据、后控制
解答题
T43：CO 中断与DMA方式计算题
某计算机的CPU主频为500MHz，CPI为5(即执行每条指令平均需5个时钟周期)。假定某外设的数据传输率为0.5MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。
1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少?
2)当该外设的数据传输率达到5MB*s时，改用DMA方式传送数据。假定每次DMA传送块大小为5000B,且DMA预处理和后处理的总开销为500个时钟周期，则CPU用于该外设I/O的时间占整个CPU时间的百分比是多少?(假设DMA与CPU之间没有访存冲突)
