封面图出处:Irasutoya,版权归原作者みふねたかし所有。
不知道哪来的考研复试资料里面的野生题目。不知道是计学、计专还是软工的。
顺序存储结构。
链式存储结构(或答单链表)。
访问效率上,数组是随机访问,时间复杂度为,链表是顺序访问,时间复杂度为,二叉排序树是二分查找,时间复杂度为。
插入和删除效率上,数组需要移动元素,时间复杂度为,链表只需要修改指针,时间复杂度为,二叉排序树平均时间复杂度为。
扩展性上,数组扩展性较差,需要预先分配空间,链表和二叉排序树扩展性较好,可以动态分配空间。
应用场景:
相同点:
不同点:
方法一:牺牲一个存储单元。
队空:,队满:。
方法二:增加一个计数变量。
队空:,队满:。
双亲表示法、孩子表示法、孩子兄弟表示法
二叉树:
每个节点最多有两个子节点的树结构,即每个节点的度最大为2。
完全二叉树:
除了最后一层,其他层的节点数都达到最大的二叉树,最后一层的节点都集中在左边。
二叉排序树:
左子树的节点值小于根节点,右子树的节点值大于根节点的二叉树,并且左右子树也分别为二叉排序树。
平衡二叉树:
每个节点的左右子树的高度差不超过1的二叉树,并且左右子树也为平衡二叉树。
在普通二叉树中,许多指针(左孩子、右孩子)实际上是空指针,利用这些空指针存储前驱、后继信息,可以在不使用额外存储空间的情况下实现高效遍历。
带权路径长度WPL指的是树中所有叶子节点的权值 × 其到根节点的路径长度之和。
哈夫曼树是带权路径长度最短的二叉树。
哈夫曼树的构造过程:
邻接矩阵、邻接表、十字链表、邻接多重表
深度优先搜索:
从起点开始,沿着一条路径一直走到底,然后回溯,继续沿着另一条路径走到底,直到所有路径都被探索完。
广度优先搜索:
把起点加入队列,依次访问队列中的顶点,所有未访问过的邻接点进行扩散,直到队列为空。
AOE网是一种带权有向无环图,其中顶点表示事件,边表示活动,边上的权值表示活动所需的时间。
在AOE网中,从起点到终点所经过的总时间最长的一条路径称为关键路径。它决定了整个工程的最短完成时间。
直接定址法、除留余数法
直接定址法:
哈希函数为关键字的线性函数,即 或 ,其中a和b为常数。
除留余数法:
哈希函数为关键字除以某个质数p的余数,即 。
开放定址法、拉链法
开放定址法包括:线性探测法、平方探测法、再散列法等
快速排序:
选择一个基准元素,将数组分成两部分,一部分小于基准元素,一部分大于基准元素,然后递归地对两部分进行排序。
归并排序:
将数组分成两部分,分别进行排序,然后合并成一个有序数组。
插入排序:
类似扑克牌,每次从无序部分选择一个元素,插入到有序部分的合适位置。
希尔排序:
将数组按照一定的间隔进行分组,对每个小组进行插入排序,然后逐步缩小间隔,直到整个数组有序。
选择排序:
每次选择最小的元素,放到已排序部分的末尾。
冒泡排序:
比较数组中每对相邻元素,如果顺序不对,则交换位置。一直到数组结尾,称为一趟排序。
重复这个过程,直到数组有序。
如果一趟排序没有发生交换,则说明数组已经有序,可以提前结束。
堆排序:
稳定的排序算法:
插入排序、冒泡排序、归并排序、基数排序
不稳定的排序算法:
希尔排序、选择排序、堆排序、快速排序
口诀:选艾希,堆攻速(选择排序、希尔排序、堆排序、快速排序)
参考资料:BOK25数据结构精讲课——排序 8-5 排序小结
翻译:将编写的程序全部翻译成另一种语言,然后再执行。
解释:将编写的程序的一条语句翻译执行后,再翻译下一条语句,翻译一句执行一句。
Cache-主存-辅存
Cache-主存:解决CPU和主存速度不匹配的问题;
主存-辅存:解决存储系统的容量问题。
容量上,Cache最小,主存其次,辅存最大。
速度上,Cache最快,主存其次,辅存最慢。
传输单位上,Cache-主存层次以块为单位,主存-辅存层次是页或段。
MAR:存储器地址寄存器。
MDR:存储器数据寄存器。
存储器的最大容量由MAR和MDR的位数共同决定。
高速缓冲存储器,位于CPU和主存之间,由SRAM组成。
分段:
进程的地址空间分成若干个段,每个段的大小可以不同。段的长度可以不连续,段与段之间可以不连续。
分页:
进程的地址空间分成若干个页,每个页的大小相同。页的长度必须连续,页与页之间必须连续。
虚拟存储器从逻辑上对主存进行扩充,使得程序可以使用比物理内存更大的空间。
时间局部性:
如果某个数据最近被访问过,那么它在不久的将来可能会再次被访问。
即,某些数据在短时间内可能被多次访问。
常见于循环结构。
空间局部性:
如果某个数据最近被访问过,那么它附近的数据项在不久的将来也可能被访问。
即,程序访问的内存地址往往是连续的。
常见于顺序结构如数组。
举例:0x12345678
地址从低到高:
大端模式:0x12 0x34 0x56 0x78
符合人类阅读习惯
小端模式:0x78 0x56 0x34 0x12
符合机器阅读习惯
CISC:复杂指令集计算机,指令系统复杂,指令数量多且长度不固定。
RISC:精简指令集计算机,指令系统简单,指令数量少且长度固定。
立即寻址:地址字段即为操作数。
直接寻址:地址字段为操作数的真实地址。
间接寻址:地址字段为操作数地址的地址。
寄存器寻址:地址字段为操作数所在寄存器编号。
寄存器间接寻址:地址字段为寄存器编号,该寄存器存储的是操作数所在存储单元的地址。
相对寻址:操作数地址=PC+偏移量
基址寻址:操作数地址=基址寄存器+偏移量,基址寄存器在程序执行过程中不变,偏移量可变。
变址寻址:操作数地址=变址寄存器+偏移量,变址寄存器在程序执行过程中可变,偏移量不变。
将一个任务分解为几个不同的子阶段,每个阶段在不同的功能部件上并行执行,以便同一时刻能够同时执行多个任务,进而提高系统性能。
五段式流水线:
取指(IF):从存储器中取出指令。
译码(ID):对指令进行译码。
执行(EX):执行指令。
访存(M):访问存储器。
写回(WB):将结果写回存储器。
实际执行过程中,由于某些原因,流水线无法正确按顺序执行后续指令,导致流水线阻塞或停顿。
结构冒险:多条指令在同一时刻争用同一资源。
数据冒险:后续指令需要用到前面指令的计算结果。
控制冒险:遇到跳转指令使PC发生跳转,导致流水线清空。
分时和共享。
分时:同一时刻只允许一个部件使用总线。
共享:总线上可以挂多个部件,都通过该总线进行数据传输。
数据总线、地址总线和控制总线。
数据总线:双向传输,用于各部件之间传输数据。
地址总线:单向传输,用于指明数据总线上传输信息的源地址和目的地址。
控制总线:双向传输,用于协调各部件按序执行。
只需一个首地址,就可连续传输多个数据块,提高数据传输效率。
系统采用一个统一的时钟信号来协调发送方和接受方之间的操作。在一个总线周期内,发送方和接受方完成一次数据传输。
系统没有统一的时钟信号,传送双方通过“握手”机制实现定时控制。可分为不互锁、半互锁和全互锁三种方式。
操作系统是计算机中最基本的系统软件,是用户与计算机硬件之间的桥梁。
它管理整个计算机系统的硬件和软件资源,同时为用户和其他应用程序提供接口。
并发:两个或多个事件在同一时间间隔内发生。
共享:系统中的资源可以被多个并发执行的进程共同使用。
虚拟:把一个物理上的实体变成多个逻辑上的对应物。
异步:程序的执行不是连续的,而是走走停停,以不可预知的速度向前推进。
原语是一种特殊的程序,处于操作系统的底层。
原语具有原子性,要么一气呵成全部完成,要么不执行,执行过程不可被中断 。
中断又称外中断,是指CPU执行指令以外发生了事件,例如IO请求等。
异常又称内中断,是指CPU执行指令期间出现了问题,例如溢出、地址越界、除0错等。
进程是资源分配的基本单位,有独立的地址空间,切换开销大。
线程是CPU调度的基本单位,共享进程的地址空间,切换开销小。
创建态、就绪态、运行态、阻塞态、终止态。
创建 → 就绪:进程被创建,资源已分配,插入就绪队列等待 CPU 调度
就绪 → 运行:进程被调度程序选中,获得 CPU
运行 → 就绪:进程时间片到,让出 CPU 给其他进程
运行 → 阻塞:进程等待 I/O 或其他资源
阻塞 → 就绪:I/O 完成,进程可继续执行
运行 → 终止:进程执行完毕或发生错误
记一个:阻塞态不能直接转换为运行态,需要先转换为就绪态。
先来先服务(FCFS):按照进程到达的顺序来调度。
短作业优先(SJF):选择估计运行时间最短的进程来执行。
高响应比优先(HRRN):根据等待时间与服务时间之间的比值来选择下一个要执行的进程。
时间片轮转(RR):每个进程在CPU上运行一个时间片,时间片轮转调度算法使得每个进程在一定时间内都能被执行。
临界资源是指在同一时刻只允许一个进程使用的资源。对临界资源的访问,必须互斥地进行。
临界区是指访问临界资源的代码段。
死锁是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象。
死锁产生的条件:
处理方法:
死锁预防、死锁避免、死锁检测。
饥饿是进程长时间等待得不到调度,并不代表发生了死锁。
出现饥饿的进程可以是就绪态,死锁状态的进程一定是阻塞态。
内存的分配和回收
地址转换:将逻辑地址转换为物理地址
内存扩充:利用虚拟技术从逻辑上扩充内存
存储保护:让各个进程在各自存储空间内运行,互不干扰
单一连续分配、固定分区分配、动态分区分配
首次适应:按地址递增的顺序排列空闲分区,从头开始找第一个能满足大小的空闲分区。
临近适应:按地址递增的顺序排列空闲分区,从上一次查找结束的位置开始找第一个能满足大小的空闲分区。
最佳适应:按容量递增的顺序排列空闲分区,从头开始找第一个能满足大小的空闲分区。
最坏适应:按容量递减的顺序排列空闲分区,从头开始找第一个能满足大小的空闲分区。
分页、分段、段页式
最佳置换(OPT):暂时无法实现
先进先出(FIFO)
最近最久未使用(LRU)
时钟置换(CLOCK)
背景知识:
- 快表是硬件机构,位于CPU和主存之间;页表位于主存;页表中部分常用页表项缓存在TLB中。
- 快表中没有保存所有的虚页对应的页表项,所以快表不命中就要去查慢表(页表)
- 页表中一定有所有虚页对应的页表项,一定能命中,只是有些页表项有效位为0,即它对应的页不在内存中,需要从外存中调入。
参考资料:BOK25操作系统基础班 3-3 虚拟存储器(OS)
操作系统通过文件系统来对文件进行统一管理。
硬链接:目录项只有文件名和文件的inode号,其他属性都在inode中。
软链接:软链接是一个独立的文件,其内容存储的是目标文件的路径。
先来先服务(FCFS)
最短寻道时间优先(SSTF)
扫描算法(SCAN)
循环扫描算法(CSCAN)
SPOOLing 技术是一种将独占设备改造为共享设备的技术。它利用磁盘作为缓冲区,让 I/O 设备和 CPU 并行工作,提高了系统的吞吐量。
物联网淑惠适用:物理层、数据链路层、网络层、传输层、会话层、表示层、应用层
硬输计网:应用层(合并了最上面三层)、传输层、网际层、网络接口层(合并了最底下两层)
语法:数据与控制信息的格式
语义:需要发出何种控制信息,完成何种动作以及做出何种应答
同步:事件的实现顺序
面向连接服务:通信前双方必须建立连接,数据按序传输,可靠交付。例:TCP
无连接服务:通信双方不需要建立连接,数据传输不可靠。例:UDP
电路交换:在通信前建立一条专用的物理通路,通信过程中始终占用该通路,直到通信结束后才释放。
报文交换:将数据作为一个整体进行存储和转发。
分组交换:将数据分成多个分组,每个分组独立传输,到达目的地后再重新组装。
调制:将数字信号转换为模拟信号
编码:将模拟信号转换为数字信号
CSMA/CD:载波监听多路访问/碰撞检测
发送前侦听,边发送边侦听,一旦出现碰撞马上停止发送,等待一段随机时间后再发送。
CSMA/CA:载波监听多路访问/碰撞避免
发送前先广播,告知其他结点,让其他结点在一段时间内不要发送数据,以免发生碰撞。
长度和空间上:
IPv4:32位,最大可提供个地址,地址空间有限。
IPv6:128位,最大可提供个地址,地址空间无限。
引入IPv6可以解决IPv4地址空间不足的问题。
表示上:
IPv4:点分十进制表示法
IPv6:冒号十六进制表示法
报文格式上:
IPv4:首部固定长度20字节,可变部分是可选的,最大长度为40字节。
IPv6:首部固定长度40字节,没有可变部分。
集线器:广播接收到的数据,工作在物理层,既不能隔离冲突域,也不能隔离广播域。
交换机:基于MAC地址转发MAC帧,工作在数据链路层,可以隔离冲突域,但不能隔离广播域。
路由器:基于IP地址进行路由选择和路由转发,工作在网络层,既能隔离冲突域,也能隔离广播域。
UDP是无连接的协议,发送数据前不需要建立连接,是不可靠传输。
TCP是面向连接的协议,发送数据前要建立连接,提供的是可靠传输。TCP连接的建立需要三次握手,释放需要四次挥手。
三次握手:
四次挥手:
HTTP:超文本传输协议,用于浏览器与服务器之间的数据传输。
FTP:文件传输协议,用于文件的上传和下载。
SMTP:简单邮件传输协议,用于电子邮件的传输。
DNS:域名解析协议,用于把域名映射成为IP地址或把IP地址映射为域名。
设T1和T2是并发执行的事务:
关系数据库:
适用于结构化数据,数据模型固定(基于关系模型),遵循ACID特性,数据一致性强。
非关系数据库:
适用于大规模、动态变化的数据,数据模型灵活,遵循BASE特性,数据一致性弱。
计算机考研复试常问问题 数据结构篇
计算机考研复试常问问题 计算机组成原理篇
计算机考研复试常问问题 操作系统篇
计算机考研复试常问问题 计算机网络篇
计算机考研复试常问问题 数据库篇
版权声明
① 本博客所有原创文章,除非另有特别声明,均采用CC BY-NC-SA 4.0/知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行授权。
② 本博客中,在文章内容之外使用的原创图片、动画、音频等多媒体素材的知识产权归属如下:
(i) 由博客作者独立创作的素材,其知识产权由博客作者单独所有;
(ii) 与他人合作创作的素材,其知识产权由博客作者与原创作者共同所有;
(iii) 对于特定素材,如有不同的版权归属,将在相应位置特别注明。
未经原作者或博客作者的明确授权,任何个人或组织不得在其他场合使用、复制、修改或传播这些素材。