算法设计与分析 综合面试之专业综合考核

算法设计与分析 综合面试之专业综合考核

创建于 2025-03-25·更改于 2025-03-25

封面图出处:Irasutoya,版权归原作者みふねたかし所有。

〇、疑似往年真题

不知道哪来的考研复试资料里面的野生题目。不知道是计学、计专还是软工的。

2023

  1. 软件测试(白盒测试、黑盒测试)
    概念 怎么进行白黑测试 某某操作是属于黑还是白 (一个知识点几小问)
  2. 软件危机、表现,原因,解决方法
  3. 关键路径
  4. 死锁和预防死锁
  5. 什么是虚拟存储器
  6. 文件管理
  7. 操作系统临界资源
  8. 操作系统底层原理
  9. 二叉树 b树
  10. 软件工程:什么是可行性分析、说明可行性研究的重要性
  11. 进程状态过程、原语
  12. 存储器,cache
  13. 二叉排序树,平衡二叉树的定义
  14. 数组,链表,二叉排序树的优劣,和应用场景

2022

  1. CSMA/CD 为什么不能用于无线传输
  2. 时间局部性和空间局部性
  3. 7层网络协议
  4. 关系数据库和非关系数据库的区别
  5. 传输层的协议有哪些
  6. 软件测试的方法,黑盒测试和白盒测试

一、数据结构

第2章 线性表

若线性表需要频繁查找,很少进行插入和删除操作,宜采用何种存储结构?

顺序存储结构。

若线性表需要频繁插入和删除,宜采用何种存储结构?

链式存储结构(或答单链表)。

对比数组,链表,二叉排序树的优劣和应用场景

访问效率上,数组是随机访问,时间复杂度为O(1)O(1),链表是顺序访问,时间复杂度为O(n)O(n),二叉排序树是二分查找,时间复杂度为O(logn)O(\log n)
插入和删除效率上,数组需要移动元素,时间复杂度为O(n)O(n),链表只需要修改指针,时间复杂度为O(1)O(1),二叉排序树平均时间复杂度为O(logn)O(\log n)
扩展性上,数组扩展性较差,需要预先分配空间,链表和二叉排序树扩展性较好,可以动态分配空间。

应用场景:

  • 数组:适用于需要频繁访问的场景。
  • 链表:适用于需要频繁插入和删除的场景。
  • 二叉排序树:适用于既需要频繁查找,又需要频繁插入和删除的场景。

第3章 栈、队列和数组

栈和队列的相同点和不同点

相同点:

  • 都是线性结构
  • 都是操作受限的线性表
  • 插入操作都在表尾

不同点:

  • 删除操作的位置不同:栈在表尾进行,队列在表头进行
  • 栈是后进先出(LIFO),队列是先进先出(FIFO)

如何区分循环队列是队空还是队满?

方法一:牺牲一个存储单元。
队空:front=rearfront = rear,队满:front=(rear+1)%maxsizefront = (rear + 1) \% maxsize

方法二:增加一个计数变量sizesize
队空:size=0size = 0,队满:size=maxsizesize = maxsize

第5章 树与二叉树

树的表示法有哪些?

双亲表示法、孩子表示法、孩子兄弟表示法

二叉树,完全二叉树,二叉排序树,平衡二叉树的特点

二叉树:
每个节点最多有两个子节点的树结构,即每个节点的度最大为2。

完全二叉树:
除了最后一层,其他层的节点数都达到最大的二叉树,最后一层的节点都集中在左边。

二叉排序树:
左子树的节点值小于根节点,右子树的节点值大于根节点的二叉树,并且左右子树也分别为二叉排序树。

平衡二叉树:
每个节点的左右子树的高度差不超过1的二叉树,并且左右子树也为平衡二叉树。

为什么会引入线索二叉树?它有什么优势?

在普通二叉树中,许多指针(左孩子、右孩子)实际上是空指针,利用这些空指针存储前驱、后继信息,可以在不使用额外存储空间的情况下实现高效遍历。

什么是带权路径长度?什么是哈夫曼树?哈夫曼树的构造过程?

带权路径长度WPL指的是树中所有叶子节点的权值 × 其到根节点的路径长度之和。
哈夫曼树是带权路径长度最短的二叉树。

哈夫曼树的构造过程:

  1. 将所有的权值视为单独的节点,形成一个森林。
  2. 每次从森林中选取两个具有最小权值的节点,作为新二叉树的左右子节点,并将它们的权值之和作为新树的根节点权值。
  3. 重复步骤2,直到森林中只剩下一棵树,这棵树就是哈夫曼树。

第6章 图

图的存储方式

邻接矩阵、邻接表、十字链表、邻接多重表

深度优先和广度优先搜索的算法思想

深度优先搜索:
从起点开始,沿着一条路径一直走到底,然后回溯,继续沿着另一条路径走到底,直到所有路径都被探索完。

广度优先搜索:
把起点加入队列,依次访问队列中的顶点,所有未访问过的邻接点进行扩散,直到队列为空。

什么是关键路径

AOE网是一种带权有向无环图,其中顶点表示事件,边表示活动,边上的权值表示活动所需的时间。
在AOE网中,从起点到终点所经过的总时间最长的一条路径称为关键路径。它决定了整个工程的最短完成时间。

第7章 查找

列举一些哈希函数的构造方法

直接定址法、除留余数法

直接定址法:
哈希函数为关键字的线性函数,即 H(key)=keyH(key) = keyH(key)=akey+bH(key) = a * key + b,其中a和b为常数。

除留余数法:
哈希函数为关键字除以某个质数p的余数,即 H(key)=key%pH(key) = key \% p

哈希表处理冲突的方法

开放定址法、拉链法
开放定址法包括:线性探测法、平方探测法、再散列法等

第8章 排序

各种排序算法思想(默认按从小到大排)

快速排序:
选择一个基准元素,将数组分成两部分,一部分小于基准元素,一部分大于基准元素,然后递归地对两部分进行排序。

归并排序:
将数组分成两部分,分别进行排序,然后合并成一个有序数组。

插入排序:
类似扑克牌,每次从无序部分选择一个元素,插入到有序部分的合适位置。

希尔排序:
将数组按照一定的间隔进行分组,对每个小组进行插入排序,然后逐步缩小间隔,直到整个数组有序。

选择排序:
每次选择最小的元素,放到已排序部分的末尾。

冒泡排序:
比较数组中每对相邻元素,如果顺序不对,则交换位置。一直到数组结尾,称为一趟排序。
重复这个过程,直到数组有序。
如果一趟排序没有发生交换,则说明数组已经有序,可以提前结束。

堆排序:

  1. 将数组构建成一个堆
  2. 将堆顶元素与最后一个元素交换
  3. 调整堆
  4. 重复交换和调整,直到整个数组有序

哪些排序算法是稳定的?哪些是不稳定的?

稳定的排序算法:
插入排序、冒泡排序、归并排序、基数排序

不稳定的排序算法:
希尔排序、选择排序、堆排序、快速排序
口诀:择排序、尔排序、排序、快排序)
参考资料:BOK25数据结构精讲课——排序 8-5 排序小结

二、计算机组成原理

第1章 计算机系统概述

冯诺依曼机的主要特点

  1. 五大部件:运算器、控制器、存储器、输入设备、输出设备。
  2. 指令和数据均用二进制表示,以同等地位存储在存储器中。
  3. 指令由操作码和地址码组成。
  4. 指令在存储器中顺序存储。

什么是翻译,什么是解释

翻译:将编写的程序全部翻译成另一种语言,然后再执行。
解释:将编写的程序的一条语句翻译执行后,再翻译下一条语句,翻译一句执行一句。

第2章 数据的表示和运算

第3章 存储系统

三级存储体系的构成,并对比Cache-主存和主存-辅存层次之间的区别

Cache-主存-辅存

Cache-主存:解决CPU和主存速度不匹配的问题;
主存-辅存:解决存储系统的容量问题。

容量上,Cache最小,主存其次,辅存最大。
速度上,Cache最快,主存其次,辅存最慢。
传输单位上,Cache-主存层次以块为单位,主存-辅存层次是页或段。

什么是MAR,什么是MDR

MAR:存储器地址寄存器。
MDR:存储器数据寄存器。
存储器的最大容量由MAR和MDR的位数共同决定。

什么是Cache

高速缓冲存储器,位于CPU和主存之间,由SRAM组成。

Cache替换算法

  1. 随机替换(Random)
  2. 先进先出(FIFO)
  3. 最近最少使用(LRU)

Cache和主存的映射方式

  1. 直接映射:主存中的块只能装入Cache中的唯一位置。
  2. 全相联映射:主存中的块可以装入Cache中的任意位置。
  3. 组相联映射:将Cache分成若干大小相同的组,组间采用直接映射,组内采用全相联映射。

分页和分段存储管理的区别

分段:
进程的地址空间分成若干个段,每个段的大小可以不同。段的长度可以不连续,段与段之间可以不连续。

分页:
进程的地址空间分成若干个页,每个页的大小相同。页的长度必须连续,页与页之间必须连续。

什么是虚拟存储器

虚拟存储器从逻辑上对主存进行扩充,使得程序可以使用比物理内存更大的空间。

什么是局部性原理(时间局部性和空间局部性)

时间局部性:
如果某个数据最近被访问过,那么在不久的将来可能会再次被访问
即,某些数据在短时间内可能被多次访问。
常见于循环结构。

空间局部性:
如果某个数据最近被访问过,那么它附近的数据项在不久的将来也可能被访问
即,程序访问的内存地址往往是连续的。
常见于顺序结构如数组。

第4章 指令系统

大端模式和小端模式

举例:0x12345678

地址从低到高:
大端模式:0x12 0x34 0x56 0x78 符合人类阅读习惯
小端模式:0x78 0x56 0x34 0x12 符合机器阅读习惯

什么是 CISC 和 RISC

CISC:复杂指令集计算机,指令系统复杂,指令数量多且长度不固定。
RISC:精简指令集计算机,指令系统简单,指令数量少且长度固定。

寻址方式(立即寻址/直接寻址/间接寻址/寄存器寻址/寄存器间接寻址/相对寻址/基址寻址/变址寻址)

立即寻址:地址字段即为操作数。
直接寻址:地址字段为操作数的真实地址。
间接寻址:地址字段为操作数地址的地址。
寄存器寻址:地址字段为操作数所在寄存器编号。
寄存器间接寻址:地址字段为寄存器编号,该寄存器存储的是操作数所在存储单元的地址。

相对寻址:操作数地址=PC+偏移量
基址寻址:操作数地址=基址寄存器+偏移量,基址寄存器在程序执行过程中不变,偏移量可变。
变址寻址:操作数地址=变址寄存器+偏移量,变址寄存器在程序执行过程中可变,偏移量不变。

第5章 中央处理器

什么是指令流水线,五段式流水线的各阶段

将一个任务分解为几个不同的子阶段,每个阶段在不同的功能部件上并行执行,以便同一时刻能够同时执行多个任务,进而提高系统性能。

五段式流水线:
取指(IF):从存储器中取出指令。
译码(ID):对指令进行译码。
执行(EX):执行指令。
访存(M):访问存储器。
写回(WB):将结果写回存储器。

什么是流水线冒险

实际执行过程中,由于某些原因,流水线无法正确按顺序执行后续指令,导致流水线阻塞或停顿。

结构冒险:多条指令在同一时刻争用同一资源。
数据冒险:后续指令需要用到前面指令的计算结果。
控制冒险:遇到跳转指令使PC发生跳转,导致流水线清空。

第6章 总线

总线的两大特征

分时和共享。
分时:同一时刻只允许一个部件使用总线。
共享:总线上可以挂多个部件,都通过该总线进行数据传输。

总线的分类(记一个按传输信息分类)

数据总线、地址总线和控制总线。
数据总线:双向传输,用于各部件之间传输数据。
地址总线:单向传输,用于指明数据总线上传输信息的源地址和目的地址。
控制总线:双向传输,用于协调各部件按序执行。

突发传输

只需一个首地址,就可连续传输多个数据块,提高数据传输效率。

同步定时方式

系统采用一个统一的时钟信号来协调发送方和接受方之间的操作。在一个总线周期内,发送方和接受方完成一次数据传输。

异步定时方式

系统没有统一的时钟信号,传送双方通过“握手”机制实现定时控制。可分为不互锁、半互锁和全互锁三种方式。

第7章 输入输出系统

主机与外围设备之间信息传送的控制方式

  1. 程序查询方式
  2. 程序中断方式
  3. 直接存储器存取(DMA)方式
  4. 通道方式

三、操作系统

第1章 操作系统概述

什么是操作系统

操作系统是计算机中最基本的系统软件,是用户与计算机硬件之间的桥梁。
它管理整个计算机系统的硬件和软件资源,同时为用户和其他应用程序提供接口。

操作系统的特征

并发:两个或多个事件在同一时间间隔内发生。
共享:系统中的资源可以被多个并发执行的进程共同使用。
虚拟:把一个物理上的实体变成多个逻辑上的对应物。
异步:程序的执行不是连续的,而是走走停停,以不可预知的速度向前推进。

什么是原语?

原语是一种特殊的程序,处于操作系统的底层。
原语具有原子性,要么一气呵成全部完成,要么不执行,执行过程不可被中断 。

什么是中断和异常,有何区别

中断又称外中断,是指CPU执行指令以外发生了事件,例如IO请求等。
异常又称内中断,是指CPU执行指令期间出现了问题,例如溢出、地址越界、除0错等。

第2章 进程与线程

进程与线程的区别

进程是资源分配的基本单位,有独立的地址空间,切换开销大。
线程是CPU调度的基本单位,共享进程的地址空间,切换开销小。

进程的生命周期(进程的五种状态)

创建态、就绪态、运行态、阻塞态、终止态。

创建 → 就绪:进程被创建,资源已分配,插入就绪队列等待 CPU 调度
就绪 → 运行:进程被调度程序选中,获得 CPU
运行 → 就绪:进程时间片到,让出 CPU 给其他进程
运行 → 阻塞:进程等待 I/O 或其他资源
阻塞 → 就绪:I/O 完成,进程可继续执行
运行 → 终止:进程执行完毕或发生错误

记一个:阻塞态不能直接转换为运行态,需要先转换为就绪态。

进程的调度算法

先来先服务(FCFS):按照进程到达的顺序来调度。
短作业优先(SJF):选择估计运行时间最短的进程来执行。
高响应比优先(HRRN):根据等待时间与服务时间之间的比值来选择下一个要执行的进程。
时间片轮转(RR):每个进程在CPU上运行一个时间片,时间片轮转调度算法使得每个进程在一定时间内都能被执行。

什么是临界资源和临界区

临界资源是指在同一时刻只允许一个进程使用的资源。对临界资源的访问,必须互斥地进行。
临界区是指访问临界资源的代码段。

什么是死锁,死锁产生的条件,处理方法

死锁是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象。

死锁产生的条件:

  1. 互斥使用:一个资源只能被一个进程使用。
  2. 请求与保持:进程至少已经持有一个资源,但在等待获取额外资源时,不释放已占有的资源。
  3. 不可抢占(不可剥夺):进程已获得的资源,在未使用完之前,不能强行剥夺。
  4. 循环等待:资源分配图中存在环路。

处理方法:
死锁预防、死锁避免、死锁检测。

饥饿和死锁有什么区别

饥饿是进程长时间等待得不到调度,并不代表发生了死锁。
出现饥饿的进程可以是就绪态,死锁状态的进程一定是阻塞态。

第3章 内存管理

内存管理的主要功能

内存的分配和回收
地址转换:将逻辑地址转换为物理地址
内存扩充:利用虚拟技术从逻辑上扩充内存
存储保护:让各个进程在各自存储空间内运行,互不干扰

内存的连续分配管理方式

单一连续分配、固定分区分配、动态分区分配

动态分区分配的四种算法?

首次适应:按地址递增的顺序排列空闲分区,从头开始找第一个能满足大小的空闲分区。
临近适应:按地址递增的顺序排列空闲分区,从上一次查找结束的位置开始找第一个能满足大小的空闲分区。
最佳适应:按容量递增的顺序排列空闲分区,从头开始找第一个能满足大小的空闲分区。
最坏适应:按容量递减的顺序排列空闲分区,从头开始找第一个能满足大小的空闲分区。

内存的非连续分配管理方式

分页、分段、段页式

页面置换算法

最佳置换(OPT):暂时无法实现
先进先出(FIFO)
最近最久未使用(LRU)
时钟置换(CLOCK)

地址转换过程(虚拟地址转换为物理地址)

背景知识:

  1. 快表是硬件机构,位于CPU和主存之间;页表位于主存;页表中部分常用页表项缓存在TLB中。
  2. 快表中没有保存所有的虚页对应的页表项,所以快表不命中就要去查慢表(页表)
  3. 页表中一定有所有虚页对应的页表项,一定能命中,只是有些页表项有效位为0,即它对应的页不在内存中,需要从外存中调入。
  1. CPU首先查找TLB。如果命中,直接形成物理地址;否则,进入页表查找过程。
  2. CPU接着查找页表。如果页表项有效位为1,则形成物理地址,并加载到TLB中;如果有效位为0,发生缺页中断,进入外存查找过程。
  3. CPU接着查找外存,从外存中找到缺页,调入到内存,修改页表,更新TLB。

参考资料:BOK25操作系统基础班 3-3 虚拟存储器(OS)

第4章 文件管理

操作系统如何管理文件/什么是文件系统

操作系统通过文件系统来对文件进行统一管理。

  1. 管理磁盘空间分配,包括连续分配、链接分配、索引分配。
  2. 管理文件控制块FCB、索引节点inode及文件目录结构。
  3. 管理文件的打开、读写、关闭等操作,提供统一的系统调用接口。

区分硬链接和软链接

硬链接:目录项只有文件名和文件的inode号,其他属性都在inode中。
软链接:软链接是一个独立的文件,其内容存储的是目标文件的路径。

第5章 输入/输出(I/O)管理

磁盘调度算法

先来先服务(FCFS)
最短寻道时间优先(SSTF)
扫描算法(SCAN)
循环扫描算法(CSCAN)

什么是 SPOOLing 技术/假脱机技术

SPOOLing 技术是一种将独占设备改造为共享设备的技术。它利用磁盘作为缓冲区,让 I/O 设备和 CPU 并行工作,提高了系统的吞吐量。

四、计算机网络

第1章 计算机网络体系结构

OSI七层协议

物联网淑惠适用:物理层、数据链路层、网络层、传输层、会话层、表示层、应用层

TCP/IP四层协议

硬输计网:应用层(合并了最上面三层)、传输层、网际层、网络接口层(合并了最底下两层)

计算机网络协议的组成

语法:数据与控制信息的格式
语义:需要发出何种控制信息,完成何种动作以及做出何种应答
同步:事件的实现顺序

面向连接服务和无连接服务

面向连接服务:通信前双方必须建立连接,数据按序传输,可靠交付。例:TCP
无连接服务:通信双方不需要建立连接,数据传输不可靠。例:UDP

第2章 物理层

电路交换、报文交换、分组交换

电路交换:在通信前建立一条专用的物理通路,通信过程中始终占用该通路,直到通信结束后才释放。
报文交换:将数据作为一个整体进行存储和转发。
分组交换:将数据分成多个分组,每个分组独立传输,到达目的地后再重新组装。

调制和编码

调制:将数字信号转换为模拟信号
编码:将模拟信号转换为数字信号

第3章 数据链路层

解释CSMA/CD和CSMA/CA协议

CSMA/CD:载波监听多路访问/碰撞检测
发送前侦听,边发送边侦听,一旦出现碰撞马上停止发送,等待一段随机时间后再发送。

CSMA/CA:载波监听多路访问/碰撞避免
发送前先广播,告知其他结点,让其他结点在一段时间内不要发送数据,以免发生碰撞。

CSMA/CD为什么不能用于无线传输

  1. 无线介质中难以检测碰撞
  2. 无线介质中信号的波动范围广,检测到的不一定是碰撞,也有可能是变形的信号,检测误差大

第4章 网络层

对比 IPv4 和 IPv6,为什么要引入IPv6

长度和空间上:
IPv4:32位,最大可提供2322^{32}个地址,地址空间有限。
IPv6:128位,最大可提供21282^{128}个地址,地址空间无限。
引入IPv6可以解决IPv4地址空间不足的问题。

表示上:
IPv4:点分十进制表示法
IPv6:冒号十六进制表示法

报文格式上:
IPv4:首部固定长度20字节,可变部分是可选的,最大长度为40字节。
IPv6:首部固定长度40字节,没有可变部分。

对比集线器/交换机/路由器

集线器:广播接收到的数据,工作在物理层,既不能隔离冲突域,也不能隔离广播域。
交换机:基于MAC地址转发MAC帧,工作在数据链路层,可以隔离冲突域,但不能隔离广播域。
路由器:基于IP地址进行路由选择和路由转发,工作在网络层,既能隔离冲突域,也能隔离广播域。

第5章 传输层

解释 TCP 和 UDP

UDP是无连接的协议,发送数据前不需要建立连接,是不可靠传输。
TCP是面向连接的协议,发送数据前要建立连接,提供的是可靠传输。TCP连接的建立需要三次握手,释放需要四次挥手。

三次握手:

  1. 客户端发送SYN
  2. 服务器发送SYN+ACK
  3. 客户端发送ACK,连接建立

四次挥手:

  1. 客户端发送FIN
  2. 服务器发送ACK,并传送剩余数据
  3. 服务器发送FIN
  4. 客户端发送ACK,等待2MSL后,连接释放

第6章 应用层

列举一些应用层的协议

HTTP:超文本传输协议,用于浏览器与服务器之间的数据传输。
FTP:文件传输协议,用于文件的上传和下载。
SMTP:简单邮件传输协议,用于电子邮件的传输。
DNS:域名解析协议,用于把域名映射成为IP地址或把IP地址映射为域名。

五、数据库

事务的特性,什么是ACID特性

  1. 原子性(Atomicity):事务中的所有操作要么全部执行成功,要么全部执行失败,不能只执行其中的一部分。
  2. 一致性(Consistency):事务执行前后,数据库的状态必须保持一致。
  3. 隔离性(Isolation):在事务执行过程中,其他事务不能看到该事务未提交的数据。
  4. 持久性(Durability):一旦事务提交,其结果必须永久保存,即使系统崩溃或重启。

并发一致性问题

设T1和T2是并发执行的事务:

  1. 丢失修改:T1和T2都对同一数据进行修改,T1先修改,T2随后修改,T2的修改覆盖了T1的修改。
  2. 读脏数据:T1修改了数据,T2读取了T1修改后的数据,但T1又撤销了修改(回滚),此时T2读取的数据无效。
  3. 不可重复读:T1读取数据后,T2修改了数据,T1再次读取这个数据时,读到的与第一次读取的不一致。
  4. 幻影读:T1读取一个范围内的数据,T2随后在该范围内插入了数据,T1再次读取这个范围内的数据时,和第一次读的结果不同。

关系数据库和非关系数据库的区别

关系数据库:
适用于结构化数据,数据模型固定(基于关系模型),遵循ACID特性,数据一致性强。

非关系数据库:
适用于大规模、动态变化的数据,数据模型灵活,遵循BASE特性,数据一致性弱。

参考资料

计算机考研复试常问问题 数据结构篇
计算机考研复试常问问题 计算机组成原理篇
计算机考研复试常问问题 操作系统篇
计算机考研复试常问问题 计算机网络篇
计算机考研复试常问问题 数据库篇

fin

版权声明

① 本博客所有原创文章,除非另有特别声明,均采用CC BY-NC-SA 4.0/知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行授权。

② 本博客中,在文章内容之外使用的原创图片、动画、音频等多媒体素材的知识产权归属如下:
(i) 由博客作者独立创作的素材,其知识产权由博客作者单独所有;
(ii) 与他人合作创作的素材,其知识产权由博客作者与原创作者共同所有;
(iii) 对于特定素材,如有不同的版权归属,将在相应位置特别注明。
未经原作者或博客作者的明确授权,任何个人或组织不得在其他场合使用、复制、修改或传播这些素材。