842真题笔记

数据结构

• 快速排序选取最终位置中间的元素最快、有序时做最多的比较次数
• 直接选择和二分插入比较次数与初始排列无关
• 两个降幂排列的一元多项式相加，总比较次数是O(M+N)
• 一颗有n个关键字的m阶b树中查找，最多读盘
• 1+1+2+1+2+3……==n(n+1)(n+2)/6
• 选择最坏情况下排序最快，且最节约内存的算法——堆排序
• 递归汉诺塔2^n-1

软件工程

• 确认测试属于需求验证环节
• 程序编码属于软件构造过程
• 视图4+1模型
• Editor适合作为XmlEditor的父类
• 项目启动不属于软件项目管理活动
• 敏捷过程以人为核心驱动、瀑布模型是文档驱动
• 需求是否正确：操作员应该在2个小时完成车辆加油（错，软件不能对人作出限制）
• 用例图是软件详细设计文档中不需要描述的
• LSP要求继承关系必须实现多态
• 软件程序设计时，最为重要的代码质量是易读性

操作系统

• 设备驱动程序负责把用户提交的逻辑I/O请求转化为物理I/O操作的启动和执行
• Unix系统中，文件的索引结构存放在inode节点中
• OPT以后最久未使用、LRU最近最久未使用
• 银行家算法破坏循环等待
• Linux系统中的stab分配器，采用伙伴系统内存管理方式
• 操作系统教科书中，解决进程互斥和同步问题的基本机制：信号量、临界区、消息传递
• 实时系统进程调度采用抢占式高优先级
• solaris的多线程实现方式是混合式
• 虚拟技术包括
  • 多道程序设计技术，虚拟CPU，提高CPU资源利用率
  • 交换技术，虚拟内存，中级调度，平衡负载调度
  • SPOOLING技术，虚拟设备，提高设备利用率
• 死锁的原因：系统资源不足和进程推进顺序不当
• 文件系统和文件目录的主要作用都是实现对文件的按名存取
• 从逻辑结构来划分，文件可以分为两种形式：有结构的记录式文件、无结构的流式文件
• 死锁定理是用来检测死锁
• 磁盘的读写单位是扇区
• 操作系统的抽象：方便管理和调度
  • 进程是对CPU的抽象
  • 虚存是对内存的抽象
  • 文件是对设备的抽象

计算机网络

• 二层交换机的工作机制
• NAT的作用和工作原理
• 网状拓扑结构的可靠性高、总线建网容易、星型集中控制
• ACL：访问控制列表
• N个节点的星型拓扑结构中，有N-1条物理链路
• IOS镜像不能从NVRAM下载
• 被选为某个网段转发流量的交换机端口称为指定端口
• STP端口状态：阻塞、监听、学习、转发、禁止，没有传输
• 哪条语句禁止对10.10.1.0/24的访问
• 最低逻辑接口地址不能作为路由器ID号
• LCP：PPP上传输的链路层协议；NCP：PPP上传输的网络层协议
• STP（生成树协议）用来解决广播风暴问题
• 无线局域网标准IEEE802.11g规定最大速率54Mbps
• STP中，根交换机是根据最小的交换机ID来选择的
• CSMA/CD协议是非确定性协议