中科大软件学院复试面试指南

### 中科大软件学院复试面试知识点解析 #### 一、数据结构与算法 **1. 时间复杂度** - **定义**: 描述算法运行时所需时间的增长速度与输入规模之间的关系。 - **常见类型**: O(1)常数时间、O(n)线性时间、O(log n)对数时间、O(n^2)平方时间等。 - **应用场景**: 评估算法效率，选择最适合当前需求的算法。 **2. 各种排序的时间复杂度和性能比较** - **冒泡排序**: O(n^2)，稳定，简单实现。 - **快速排序**: 平均O(n log n)，最坏情况O(n^2)，不稳定，高效。 - **堆排序**: O(n log n)，不稳定，适用于大数据集。 - **插入排序**: O(n^2)，稳定，适用于小数据集。 - **归并排序**: O(n log n)，稳定，适合处理大量数据。 **3. 堆排序与快速排序的区别** - **堆排序**: 基于完全二叉树的数据结构，通过构建和调整堆来排序。 - **快速排序**: 使用分治策略，选择基准值将数组分为两部分，递归排序。 - **不同点**: 快速排序更依赖于好的基准选择，而堆排序的稳定性不受输入数据影响。 **4. 循环队列的顺序表示中为何要空一个位置** - 目的是为了区分队满和队空的状态，避免出现“假溢出”现象。 - 比如，若队列容量为n，则实际可用的空间为n-1。 **5. 二叉查找树（BST）原理** - **定义**: 每个节点的值都大于其左子树中的任意节点的值，小于其右子树中的任意节点的值。 - **应用**: 支持高效的插入、删除和查找操作。 - **平衡问题**: 需要注意保持树的平衡以确保O(log n)的操作时间。 **6. 排序算法最优的时间复杂度** - **O(n log n)**: 快速排序、归并排序等通常能达到这种复杂度。 **7. 哈夫曼树** - **定义**: 一种带权路径长度最短的二叉树。 - **应用场景**: 文件压缩，构建最优前缀编码。 **8. 哈希冲突及其解决方法** - **冲突**: 当两个不同的键映射到同一个槽时发生。 - **解决方法**: 开放地址法（线性探测、二次探测、双重散列）、链地址法。 **9. 深度、广度搜索** - **深度优先搜索** (DFS): 沿着图的深度遍历直到遇到叶子节点或无法继续为止。 - **广度优先搜索** (BFS): 从根节点开始，依次访问所有相邻节点。 - **应用**: 图的遍历、迷宫求解、网络爬虫等。 **10. 图的深度优先遍历序列是否唯一** - **不唯一**，取决于起始节点的选择和遍历顺序。 **11. 迪杰斯克拉算法** - **定义**: 用于解决带权图中的单源最短路径问题。 - **步骤**: 从起点开始，逐步扩展到其他顶点，并更新最短距离。 **12. 链表查询某个元素的平均时间复杂度** - **O(n)**，因为可能需要遍历整个链表。 **13. 图的存储方式** - **邻接矩阵**: 空间复杂度较高，但查询速度快。 - **邻接表**: 节省空间，便于增删节点。 - **十字链表**: 结合了邻接矩阵和邻接表的优点。 **14. 图的深度遍历是否唯一** - **不唯一**，取决于起始节点和遍历顺序。 **15. 图相关概念** - **顶点** (Vertex): 图的基本单位。 - **边** (Edge): 连接两个顶点的线段。 - **路径** (Path): 由顶点和边组成的序列。 - **环** (Cycle): 封闭路径。 **16. 连通图的概念** - **定义**: 无向图中任意两个顶点之间都存在路径；对于有向图，如果每对顶点之间都存在双向路径则称为强连通图。 **17. 最小生成树** - **定义**: 包含所有顶点且总权重最小的树。 - **算法**: Prim算法、Kruskal算法。 **18. n个节点的图的最小生成树有几个节点，几条边** - **节点数**: n - **边数**: n-1 **19. 平衡二叉树** - **定义**: 任意节点的左右子树高度差不超过1。 - **示例**: AVL树、红黑树。 **20. 二叉树的存储** - **顺序存储**: 使用数组，方便查找但不利于插入和删除。 - **链式存储**: 使用指针，灵活但占用额外空间。 **21. 单链表就地逆置** - **定义**: 不额外使用空间，仅改变链表节点指针方向。 **22. 查找方法总结** - **顺序查找**: O(n) - **二分查找**: O(log n)，要求有序。 - **哈希查找**: 平均O(1)，需考虑冲突。 **23. m阶的B-树与m阶的B+树的主要区别** - **B-树**: 所有节点都存储数据，适用于多级索引。 - **B+树**: 叶节点存储数据，非叶节点仅包含索引，适用于文件系统。 **24. 折半查找** - **适用范围**: 已排序的数组。 - **时间复杂度**: O(log n)。 **25. 计算机与计算器的区别** - **计算机**: 具有更强大的处理能力、可编程性和多功能性。 - **计算器**: 主要用于简单的数值计算。 #### 二、操作系统与计算机组成原理 **26. 线程/进程空间** - **进程**: 操作系统资源分配的基本单位，包含多个线程。 - **线程**: 进程内的执行单元，共享进程资源。 **27. 硬实时和软实时** - **硬实时**: 对响应时间有严格要求，超时会导致严重后果。 - **软实时**: 对响应时间有一定要求，但可以接受一定程度的延迟。 **28. 进程与程序的区别** - **程序**: 存储在磁盘上的指令集合。 - **进程**: 正在运行的程序实例。 **29. 进程与线程的区别** - **进程**: 包含一个或多个线程，每个进程都有独立的地址空间。 - **线程**: 属于同一进程，共享相同的地址空间。 **30. 微内核** - **定义**: 只提供基本服务，大部分功能通过用户空间的服务完成。 - **优点**: 提高系统的灵活性和安全性。 **31. call和return的具体工作** - **call**: 调用函数，保存返回地址。 - **return**: 返回调用者，恢复现场。 **32. DMA与中断的区别** - **DMA (Direct Memory Access)**: 数据传输无需CPU干预，直接由硬件完成。 - **中断**: CPU暂停当前任务处理外部事件。 **33. 硬中断与软中断的区别** - **硬中断**: 来自硬件设备的中断请求。 - **软中断**: 由软件触发，用于特定功能的处理。 **34. 内存** - **定义**: 计算机中用于存储数据和指令的部件。 - **类型**: RAM (随机存取存储器) 和 ROM (只读存储器)。 **35. 页面置换算法** - **最近最少使用算法** (LRU): 替换最近最少使用的页面。 - **先进先出算法** (FIFO): 替换最早进入内存的页面。 - **最优替换算法** (OPT): 理论上最佳，但在实际中难以实现。 **36. 操作系统中的磁盘调度算法** - **先来先服务** (FCFS): 按请求顺序服务。 - **最短寻道时间优先** (SSTF): 寻找离当前磁头位置最近的磁道。 - **扫描算法** (SCAN): 类似电梯移动。 **37. 操作系统中的信号量** - **定义**: 用于同步进程的机制。 - **用途**: 控制进程对共享资源的访问。 **38. P、V操作** - **P操作**: 减少信号量的值，若为负则进程阻塞。 - **V操作**: 增加信号量的值，若有进程因该信号量阻塞则唤醒之。 **39. 操作系统** - **定义**: 管理计算机硬件与软件资源的程序集合。 - **功能**: 进程管理、内存管理、文件系统管理等。 **40. 系统调用过程** - 用户程序通过系统调用接口请求操作系统服务。 - 操作系统切换到内核态执行相应操作。 **41. 虚拟存储器** - **定义**: 扩展有限的物理内存空间，允许程序访问比实际内存更大的地址空间。 - **技术**: 分页、分段、段页式。 **42. 存储器管理的功能** - **内存分配与回收**: 动态分配和释放内存。 - **内存保护**: 防止非法访问。 - **地址映射**: 将逻辑地址映射到物理地址。 **43. TLB (Translation Lookaside Buffer)** - **定义**: 缓存虚拟地址到物理地址的映射表项，提高地址转换速度。 **44. 程序连接方式** - **静态连接**: 在程序执行前完成。 - **动态连接**: 在程序加载或执行时进行。 **45. 程序的装入方式** - **绝对装入**: 将目标程序按地址定位方式装入内存。 - **可重定位装入**: 允许程序在内存中移动位置。 - **动态运行时装入**: 加载时不指定内存地址，运行时确定。 **46. 交换技术与覆盖技术的区别** - **交换技术**: 整体交换进程的内存块。 - **覆盖技术**: 在程序的不同阶段覆盖不同的代码段。 **47. 内存连续分配管理方式** - **单一连续区**: 用于简单的批处理系统。 - **固定分区**: 将内存划分为多个固定大小的区域。 - **动态分区**: 根据进程大小动态分配。 **48. 动态分区分配算法** - **首次适应算法** (FF): 选择第一个足够大的空闲分区。 - **最佳适应算法** (BF): 选择最小能满足要求的空闲分区。 - **循环首次适应算法** (CFF): 类似FF，但循环扫描空闲列表。 **49. 拼接技术** - **定义**: 通过移动内存中的空闲分区来消除外部碎片。 **51. 内部碎片与外部碎片** - **内部碎片**: 分配给进程的实际内存大于所需的最小内存。 - **外部碎片**: 许多小空闲分区无法被利用。 **52. 常用存储保护方法** - **基址寄存器和限长寄存器**: 控制进程访问内存的范围。 - **环保护**: 限制不同级别的进程访问权限。 **53. 连续分区分配与非连续分区分配** - **连续分区**: 进程占据连续的内存空间。 - **非连续分区**: 进程分散存储，如页式和段式管理。 **54. 页面与块或物理块** - **页面**: 逻辑内存的基本单位。 - **块或物理块**: 物理内存的基本单位。 **55. 页表及其作用** - **定义**: 记录页面到物理块映射关系的表格。 - **作用**: 支持虚拟内存管理。 **56. 段寄存器** - **定义**: 用于记录段的起始地址和长度。 **57. 进程线程树图** - **定义**: 用于表示进程与线程之间层次关系的图形。 **58. 作业与进程的区别** - **作业**: 用户提交的任务，包括程序和数据。 - **进程**: 作业执行的实体。 **59. 进程的三种状态及其转换** - **就绪状态**: 等待CPU资源。 - **执行状态**: 正在使用CPU。 - **阻塞状态**: 等待I/O操作或其他条件。 - **转换**: 由操作系统调度器根据事件触发。 **60. 进程调度算法** - **先来先服务** (FCFS): 按照进程到达的先后顺序进行调度。 - **短进程优先** (SPN): 优先执行短进程。 - **最高响应比优先** (HRRN): 结合等待时间和运行时间的比率。 **61. 死锁** - **定义**: 多个进程互相等待对方持有的资源，形成无限期等待的状态。 - **必要条件**: 互斥、占有且等待、不可抢占、循环等待。 **62. 分页与分段的区别** - **分页**: 固定大小的页面，主要用于内存管理。 - **分段**: 变大小的段，支持逻辑结构划分。 **63. 死锁及其原因** - **原因**: 上述必要条件的存在。 **64. 银行家算法** - **定义**: 一种用于预防死锁的算法。 - **步骤**: 检查系统是否有安全序列，即所有进程都能顺利完成。 **65. RAID** - **定义**: 独立磁盘冗余阵列，用于提高存储系统的可靠性和性能。 - **类型**: RAID 0 (条带化)、RAID 1 (镜像)、RAID 5 (条带化+奇偶校验)。 **66. 数据库分级与ER图** - **数据库分级**: 根据数据的重要性和使用频率进行分类。 - **ER图**: 实体-联系图，用于描述数据模型。 **67. 数据库的三级模式结构** - **外模式**: 用户视角的数据结构。 - **模式**: 数据库整体的逻辑结构。 - **内模式**: 物理存储结构。 **68. 视图在数据库的层级** - **视图**: 外模式的一部分，提供特定角度的数据视图。 **69. 数据库的两级映像** - **外模式/模式映像**: 保证外模式与模式的一致性。 - **模式/内模式映像**: 保证模式与内模式的一致性。 **70. 数据库设计的阶段** - **需求分析**: 确定系统需要解决的问题。 - **概念设计**: 使用ER模型建立概念模型。 - **逻辑设计**: 转换ER模型为关系模型。 - **物理设计**: 优化关系模型以适应实际硬件环境。 **71. 数据模型** - **层次模型**: 使用树形结构组织数据。 - **网状模型**: 使用图形结构。 - **关系模型**: 使用二维表表示实体及实体间的关系。 **72. 数据库中的主码** - **定义**: 用于唯一标识一个元组的属性或属性组。 **73. 关系操作** - **选择**: 从关系中选择满足条件的元组。 - **投影**: 从关系中选择某些属性列。 - **联接**: 组合两个关系的元组。 **74. 数据库表的分级** - **通常没有明确的分级**，可根据重要性、访问频率等因素进行分类。 **75. 事务及其特征** - **原子性** (Atomicity): 事务被视为一个不可分割的工作单位。 - **一致性** (Consistency): 事务执行前后数据库必须处于一致状态。 - **隔离性** (Isolation): 事务相互之间不会影响。 - **持久性** (Durability): 一旦事务提交，其结果就是永久的。 **76. 数据库操纵语言、定义语言、查询语言和控制语言** - **操纵语言**: 如INSERT、UPDATE、DELETE。 - **定义语言**: 如CREATE、DROP、ALTER。 - **查询语言**: 如SELECT。 - **控制语言**: 如GRANT、REVOKE。 **77. 数据库中防止死锁的方法** - **避免死锁**: 银行家算法。 - **检测死锁**: 定期检查系统是否存在死锁状态。 - **解除死锁**: 终止一部分进程以打破循环等待。 **78. 并发控制保证事务的特性** - **并发控制**: 用于确保事务的原子性、一致性、隔离性和持久性。 - **锁定协议**: 通过对数据项加锁来实现。