线索二叉树:在有 n 个节点的二叉树的且 llink - rlink 法存储表示中,必定有 n+1 个空指针域
16、哈夫曼树:一类带权路径长度最短的树。树的带权路径长度为树中所有叶子节点的带权路径长度之和
WPL。
17、查找:
(1)顺序查找:平均查找长度为(n +1 )/2 次,时间复杂度为 O(n)
(2)二分法查找:线性表节点必须按关键码值排序,且线性表是以顺序存储方式存储的。查找成功比较次
数 log
2
n,查找失败比较次数 log
2
n+1
(3)分块查找:先是块间查找,然后块内查找。
(4)散列表(哈希表 Hash)的存储和查找:处理冲突的方法:开地址法(线性探测法)、拉链法等
负载因子(装填因子)=表实际存储的结点个数/表的最大能存储结点个数(即表长)
二叉排序树:每个结点左子树的所有关键码值都小于该结点关键码值,右子树所有结点关键码值都大于该
结点关键码值。对称周游二叉排序树,得到一个有序序列,时间复杂度 O(log
2
n)
B 树和 B+树:M 阶树,每个结点至多有 M-1 个关键码,至少有 M/2(取上界)-1 个关键码。B 树适合随机查
找,不适合顺序查找。B+树适合顺序查找。
18、排序
直接插人排序、希尔排序、直接选择排序、堆排序、起泡排序、快速排序等排序算法要了解。
直接选择排序、希尔排序、快速排序和堆排序是不稳定排序,其他排序为稳定排序
第三章 操作系统
1、操作系统概念:一是管理系统中的各种资源;二是给用户提供一个友好的界面。
2、操作系统包括以下 3 个基本特征:并发性、共享性、随机性。
3、功能:进程管理、存储管理、作业管理、文件管理、设备管理
4、操作系统类型
(1)批处理操作系统:成批、多道,交互性不强。系统目标:提高资源利用率、作业吞吐量和作业流程自
动化。
(2)分时操作系统:多路、交互性、独立性、及时性
(3)实时系统(实时控制、实时信息处理):及时、可靠
(4)嵌入式操作系统:高可靠性、实时性、占资源少、智能化、易连接、低成本等。
5、操作系统与用户的接口:程序级接口:系统调用命令组成。操作级接口:提供操作命令
6、操作系统的硬件环境(CPU、存储体系、中断系统、I/O 控制和时钟)
(1)CPU:CPU 状态:管态(CPU 执行操作系统程序)和目态(CPU 执行用户程序)
目态到管态的转变的唯一途径是中断,通过修改程序状态字实现管态和目态的转换
(2)中断机制:
中断的实现需要硬件和软件结合完成。中断类型:强迫性中断和自愿性中断。
强迫性中断:不期望或不可预料的中断.如:输入输出中断、硬件故障中断、时钟中断、程序性中断。
自愿性中断:程序有意安排的访管指令或系统调用。
中断向量:中断处理程序的入口地址及运行环境(程序状态字 PSW)
中断优先级由硬件规定,中断屏蔽由程序状态字的中断屏蔽位决定。通过中断屏蔽可以调整中断事
件的响应次序
(3)定时装置:定时装置硬件时钟通常分为两类:即绝对时钟和相对时钟。
CPU 对外部设备的控制方式:
4 / 19