第一章

---

计算机由五个基本部分组成：运算器、控制器、存储器、输入设备、输出设备
程序的三种基本结构（顺序、选择、循环）

---

1.什么是信息，信息和数据的区别和联系在何处/p>

2.信息有哪些基本属性

3.什么是计算机硬件，什么是计算机软件

4.计算机软件有那几类，试举例说明

第二章

---

知识点
程序=数据结构+算法
数据元素是数据的基本单位，数据项是具有独立含义的最小标识单位。
什么是数据结构据结构是研究数据及数据元素之间关系的一门学科。它包括三个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。
数据的逻辑结构与数据的存储无关，它是独立于计算机的。
通常数据结构分为集合、线性、树形、图四类。
数据的存储结构包括顺序存储结构、链式存储结构、索引存储结构、散列存储结构
算法的特点strong>有穷性，确定性，可行性，输入输出
算法的描述,可以用流程图，自然语言或其他方式如数学语言或约定的符号语言来描述，c语言描述
衡量算法的标准:正确性，可读性，健壮性，效率和存储量需求
算法的时间复杂度是指在计算机上运行时所消耗的时间
算法的空间复杂度是指计算机执行过程中所需要的最大存储空间。
确定算法的时间和空间的方法有事后统计法和事前分析估算法

线性表的顺序存储结构就是将线性表的元素按其逻辑次序依次存放在一组地址连续的存储单元里
存放数据元素的结点至少包括两个域，一个域存放该元素的数据，称为数据域(data)；另一个域存放后继结点在存储器中的地址，称为指针域或链域(next)。这种链式分配的存储结构称为链表。
栈（stack）是限定只能在表的一端进行插入和删除操作的线性表。特点：先进后出（FILO）或后进先出（LIFO）
队列(Queue)是一种先进先出(FIFO，First In First Out)的线性表。
循环队列的问题：无法区分队空和队满的方法，解决方法1.用一个标志位区分2,少用一个存储空间front==rear队空front == (rear+1)% maxsize队满
数组:常用语言都是以行优先顺序存放

树型结构是以分支关系定义的层次结构。
数型结构常用术语
结点：表示树中的元素。
结点的度：一个结点拥有的子树数目。如A结点的度为3，它有三个子树T1、T2和T3。E、F结点的度为0，它们没有子树。
叶子：度为零的结点称叶子或终端结点。
双亲(parent)：一个结点是它的那些子树的根的双亲结点。
孩子(child)：除根结点外每个结点都是其前趋结点的孩子。
兄弟(sibling)：同一个双亲的孩子之间互为兄弟。如A是B、C、D的双亲；B、C、D是A的孩子；B、C、D互为兄弟。
结点的层次：根结点的层数为1，其它任何结点的层数等于它的父结点的层数加1。
树的深度：一棵树中，结点的最大层次值就是树的深度。图3-1中树的深度为4。
森林：森林是m(m≥0)棵互不相交的树的集合。
树的度：一棵树上所有结点的度的最大值就是这棵树的度。
有序树：树中结点在同层中按从左到右有序排列、不能互换的称为有序树，反之，称为无序树。
二叉树的定义：一个二叉树是一个有限结点的集合，该集合或者为空，或由一个根结点和两棵互不相交的被称为该根的左子树和右子树的二叉树组成。
二叉树的存储结构:通常用具有两个指针域的链表作为二叉树的存储结构，其中每个结点由数据域(data)、左指针(Lchild)、右指针(Rchild)组成。
二叉树的性质
性质1：在二叉树中，第i层的结点数最多有 2 i 1 2^{i-1} 2i/span>1(i≥1)个。
性质2：在深度为k的二叉树中结点总数最多有 2 k 2^k 2k–1个。
性质3：任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
特殊形式的二叉树
满二叉树：如果一棵二叉树的深度为k，并且含有2k–1个结点，则称此二叉树为满二叉树。图2-7是一棵深度为4的满二叉树。
完全二叉树:深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号从1到n的结点一一对应时，称之为完全二叉树。
平衡二叉树: 二叉树上任一结点的左子树深度减去右子树深度的差值，称为此结点的平衡因子。若一棵二叉树中，每个结点的平衡因子之绝对值都不大于1，则称这棵二叉树为平衡二叉树。
一般树转换为二叉树的步骤:加线-抹线-旋转
二叉树的遍历：先序遍历，中序遍历，后序遍历
给定N个权值作为N个叶子结点，构造一棵二叉树若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
哈夫曼树的构建方法:https://blog.csdn.net/lee18254290736/article/details/77618201

---

1.什么是算法，和程序有什么区别br> 算法（algorithm）算法是解决某一特定类型问题的有限运算序列
算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。

2.数据的存储结构有哪些们之间本质的区别/strong>
线性存储结构和链式存储结构
数组静态分配内存，链表动态分配内存；
数组在内存中连续，链表不连续；
数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。

3.试编写算法求一只单链表的长度，并考虑表空的情况

以下两个问题在面试时也会经常碰到，熟记

4.试比较顺序表和链表的优缺点
顺序存储结构
优点
1.随机访问性强
2.查找速度快
缺点
1.插入删除效率低
2.可能浪费内存(在给长度变化较大的线性表预先分配空间时必须按照最大空间分配，使存储空间不能得到充分的利用)
3.内存空间要求高，必须有足够的连续内存空间。
3.表的容量难以扩充

链式存储结构
优点
1.插入删除速度快
2.内存利用率高，不会浪费内存
3.大小没有固定，拓展很灵活。
缺点
查找效率低

5.试比较单向链表和双向链表的优缺点
单向链表：
优点：单向链表增加删除节点简单。
缺点：只能从头到尾遍历。
双向链表：
优点：可以找到前驱和后继，可进可退。
缺点：增加删除节点复杂

6.试说明树和二叉树有何不同何要将一般树转换为二叉树br> 树和二叉树的区别主要是二叉树的结点的子树要区分左子树和右子树
二叉树比树便于处理

一般树转换为二叉树
步骤：
(1) 加线：亲兄弟之间加一连线。
(2)抹线：对于每个结点，除了与它的第一个孩子保持联系外，除去与其它孩子的联系。
(3) 旋转：以树根为轴心，将整棵树顺时针旋转45度。

先序遍历，中序遍历，后序遍历

---

图的相关术语
(1) 图。图G由两个集合V(G)和E(G)所组成，记作G=(V,)。其中，V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。
(2) 有向图。如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用尖括号括起一对顶点表示。
E(G1)= {< V1, V2>，< V1, V3>，< V3, V4>，< V4, V1>}
如其中弧< V1, V2>，称V1为初始点或弧尾，V2为终端点或弧头。
(3) 无向图。如果图中每条边都是顶点的无序对，则称此图为无向图。无向边用圆括号括起的两个相关顶点来表示。
E(G2)= {(V1, V2)，(V1, V3)，(V3, V4)，( V4, V1)}
(4) 子图。设有两个图GA和GB，且满足

在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点(Vi和Vj)之间是否有边或弧相连，则需搜索第i个或第j个链表，因此不及邻接矩阵方便。
对一个图来说，邻接表不是惟一的，它取决于建立邻接表时，结点在每个单链表中的插入策略。另外，对于有向图，其邻接表中第i个单链表的结点个数就是此结点的出度；对于无向图，其邻接表中第i个单链表的结点个数就是此结点的度。

操作系统的发展过程:

操作系统是计算机系统中的一个系统软件，它是这样一些程序模块的集合：它们能够有效地组织和管理计算机系统中的硬件与软件资源，合理地组织计算机工作流程，控制程序的执行，并向用户提供各种服务功能，使用户能够灵活、方便和有效地使用计算机。

操作系统一般分为三种基本类型：
即多道批处理操作系统、分时系统和实时系统。
1多道批处理操作系统
多道：计算机内存中同时可以存放多道作业
批处理：用户与作业之间没有交互作用，用户不能直接控制作业的运行，“脱机操作”
用户作业 外存缓存器 内存执行
用于计算中心等较大型计算机系统，目的是为了充分利用中央处理机及各种设备资源。
2分时系统
多道批处理系统能提高机器资源利用率，但用户不能与机器直接交互，对程序开发带来很大不变。
在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户共享主机中的资源，每个用户都可通过自己的终端以交互方式使用计算机。
将CPU分割成很小的时间片轮流分配给多个用户，时间片分割得很小，如同自己独占一台计算机。
3实时系统
1）实时控制系统
把计算机用于生产过程的控制，要求实时采集现场数据，实时处理数据，进而自动控制执行机构，使某个参数按预定规律变化，以保证产品质量和提高产量。
用于武器的控制，如火炮的自动控制系统，飞机的自动驾驶系统，导弹的制导系统等。
（2）实时信息处理系统
由一台或多台主机通过通信线路连接成百上千个远程终端，计算机接收从远程终端发来的服务请求，根据用户提出的问题，对信息进行检索和处理，并在很短时间内为用户做出正确回答。如：飞机订票系统。

操作系统的功能和特征
1、操作系统的功能

操作系统的特性:并发性,共享性,不确定性

存储管理

存储器管理分为实存储器管理和虚拟存储器管理。
存储器的分级结构:三级，高速缓存（cpu可访问），内存（cpu可访问），外存
用户的程序在运行时应存放在主存中，以便处理机访问。但是由于主存容量有限，所以把那些不马上使用的程序、数据放在外部存储器(又称次级存储)中。当用到时再把它们读入主存。

存储管理功能

实存管理
虚拟存储管理
逻辑地址→虚拟地址 虚拟地址空间
主存地址→实在地址 实在地址空间
程序和数据所在的虚拟地址必须放入主存的实在地址中才能运行。因此要建立虚拟地址和实在地址的对应关系，这种地址转换由动态地址映象机构来实现。
1.分页存储管理
系统以页架为单位把内存分配给各作业，每个作业占有的内存无须连续，而且作业的所有页面也不一定同时都要装入内存。
2.分段存储管理

段
按模块分配存储空间，一个程序一般由若干个标准或非标准程序模块组成，分段管理把每个模块的地址空间称为段。每个段规定一个段号，每个段的地址空间都从“0”开始。
3.段页式存储管理
段页式管理是分页和分段管理结合的结果。

处理器管理
1.作业、程序与进程
作业是用户在一次算题过程中或一个事务处理中要求计算机系统所做工作的集合。
进程可以看作程序的一次执行，即是在指定内存区域中的一组指令序列的执行过程。
进程与程序的区别
区别：a.进程是程序的执行，是动态概念，程序是一组指令的集合，是静态概念。
b. 进程有生命过程的，进程的诞生(创建)和死亡(撤销)，而程序没有，因此进程的存在是暂时的，程序的存在是永久的。

存储器管理目的：选择哪一个作业进入内存；如何在进程间分配处理器
处理器管理，又称为处理器调度，一般分为两级：
作业调度，又称高级调度或宏观调度。
功能：根据某调度原则，选取某些作业进入内存，为它们分配必要的资源，建立相应的进程，并当作业完成后做好一切善后工作。
进程调度又称为低级调度或微观调度。
功能：按照某种调度原则，实现处理器在各进程间的转换。

系统为每个进程建立一个进程控制块（PCB）。
PCB是进程存在的唯一标志。
PCB中的信息分为：
说明信息：进程名、优先数、当前状态；
保留信息：保留该进程由运行状态转入阻塞或就绪状态时当时各寄存器的内容，便于该进程重新进入运行时恢复当时各寄存器状况。
处理机的数目一般总是少于进程数，在单处理机系统中，只有一个进程可真正获得处理。

原语是机器指令的延伸，是用若干条机器指令构成的，用以完成特定功能的一段程序。为保证操作的正确性，原语在执行期间是不可分割的。
用于进程控制的原语有：
(1) 创建进程原语 (2) 撤消进程原语 (3) 挂起进程原语 (4) 激活进程原语

多道程序并发运行出现的问题
对资源的共享问题
相关进程间的制约问题
进程间的通信问题
进程的死锁问题

1.进程的同步与互斥
进程的“同步”是指两个事件的发生存在某种时序上的关系，如果系统中有若干个进程要共同完成某一任务，那么它们之间必须协调配合，这种进程间的协调配合就称为进程的同步
进程“互斥”是当进程要求共享系统中某些硬件或软件资源，而这些资源却又要求排他性使用时，这样往往引起由于多个进程竞争同一资源使运行结果出现问题。为了防止发生这种情况，必须把多个进程使用同一资源的过程“分离”开来，也就是互斥的使用该类资源。
2.解决同步与互斥的工具
信号量(P-V操作)

2.进程通信
负责进程之间的信息交换称为进程通信 (各进程为了保持联系而交换信息)。P-V操作也是一种通信方式,但只适合传递少量信息,效率较低,称为低级通信方式.除此之外还有较高效率,传递大批数据的高级通信方式.
(1)直接通信 一个进程直接发送一个消息给接收进程
(2)间接通信 进程不把消息直接发给接收者进程，而把消息放在某个双方共知的信箱中。

3.死锁
(1)死锁的原因和必要条件
死锁的定义：死锁是指计算机系统中进程所处的一种状态。即在系统中的一组进程，由于竞争资源而永远阻塞，称此时进程处于死锁状态
死锁产生的原因
系统资源不足
进程推进的顺序不当
死锁的必要条件
互 斥：所涉及的资源是非共享的
占有等待：进程在等待新资源时，继续占用已分配到的资源
不可剥夺：一个进程占有的资源不能被别的进程强行抢占
循环等待：一个进程获得的资源同时被另一个进程所请求，从而形成一个进程的循环链
解决死锁的方法：
死锁的预防
死锁的避免
死锁的检测和恢复

死锁定理：
系统在某一状态下死锁的充要条件是当且仅当某一状态下的进程－资源图是不可完全化简的。

死锁的恢复
资源剥夺法：强制性地从系统中撤消某些进程，并剥夺它们的资源给剩下的进程使用。这样被撤消进程前面已完成的工作全部损失了。
撤消进程法：使用一个有效的挂起和解除挂起机构来挂起一些进程，从挂起进程那里抢占资源以解除死锁。

设备管理
1.设备管理的功能
设备管理的功能是按用户需求制定分配和使用设备的策略，为I/O操作的进程分配一条传输信息的通路，最大限度的实行并行操作。
要求达到的目标是：(1)方便性(2)设备独立性(3)并行性(4)有效性与均衡性

2设备的简单分类
按设备的使用性质分:
独享设备
共享设备
虚拟设备
3.通道与中断
(1)循环测试I/O方式
(2)程序中断方式
(3)通道I/O方式

文件管理
文件的分类：

1. 按用途分：系统文件,库文件,用户文件
   (2) 按存取权限分：可执行、只读、读写、不保护
   文件结构和存取方式
   文件的逻辑结构
   从用户的角度看到的文件面貌，也就是文件的记录结构。
   (1) 顺序结构：一个逻辑文件的信息依次存于辅存的若干连续的物理块中。操作系统的用户接口
   (2) 链接(或串联)结构
   (3)索引结构(索引顺序结构)

操作系统的用户接口
程序一级的接口：在应用程序中以函数调用的方式来享用系统服务。
作业控制方面的接口：是用户在操作系统界面上以命令方式来操作和控制计算机的手段。
几种常用的操作系统接口：
Unix操作系统接口，shell外壳，实现用户与操作系统的交互。
DOS操作系统接口，为用户提供的界面主要是命令形式，通过命令用户与操作系统交互。
Windows系列操作系统接口，图形用户接口，界面友好，便于用户的使用。

---

1.操作系统的基本功能是什么包括哪些基本部分br> (1)处理器管理
(2)存储管理
(3)设备管理
(4)文件管理
(5)用户接口
构成部分:
(1)对CPU的使用进行管理的进程调度程序
(2)对内存分配进行管理的内存管理程序
(3)对输入输出设备进行管理的驱动程序
(4)对外存中信息进行管理的文件系统

2.试着说明虚拟机的概念及实现方法
在裸机外面每增加一个软件层之后就会编程一台功能更强的 机器，我们通常把这种计算机系统成为虚拟机
虚拟机的实现方法：在裸机上装上操作系统对机器进行首次拓展，再在操作系统的的基础上增加其他软件，这样就可以实现”虚拟机”

3.解释名空间，作业地址空间和存储空间的关系以及逻辑地址和物理地址的区别
存放源程序的空间称为名空间。
当汇编或编译程序将源程序转换成目标程序，一个目标程序所占有的地址范围成为地址空间，这些地址的编号是相对于起始地址而定的，一般定起始位零，称为逻辑地址或相对地址。
存储空间是指当目标程序装入主存后占用的一系列物理单元的集合，这些单元编号称为物理地址或绝对地址。

4.什么是重定位态重定位和动态重定位的区别是什么举一例说明
当用户程序要调入内存时，必须把相对地址转换为绝对地址。同时要包括对程序中与地址油管的指令进行修改，这一过程称为重定位。
静态重定位是在程序装入时进行，一般通过处理机中一对界地址寄存器来实现。
动态重定位是在程序执行过程中进行的，当处理器访问主存指令时由动态变换机构自动进行地址转换。

5.存储管理的功能是什么什么要引入虚拟存储器的概念存的容量由什么决定br> 存储管理的功能主要有:内存分配，地址转换，存储保护和内存扩充
虚拟存储器能提供给用户一个比实际内存大得多的存储空间，使用户在编制程序时可以不必考虑存储空间的限制。
虚存的容量受两个条件的约束：指令中地址场长度的限制，外存储器容量的限制。

6.处理器管理主要是解决什么问题br> 在大型通用系统中，可能数百个批处理作业

来源：star-air