南航829计算机专业基础考研真题与解析

"南航829计算机专业基础2013到2018年真题，涵盖了数据结构和操作系统两大部分，主要测试考生对二叉树性质、哈希表、最短路径算法、矩阵转置、链表操作、二叉树高度计算以及操作系统基本概念的理解和应用。" 这份资料是南京航空航天大学计算机专业考研的历年真题，包括2013年至2018年的试题。试题分为数据结构和操作系统两个部分，总分150分。下面我们分别来看这两部分的主要知识点。 **数据结构部分**： 1. **二叉树性质**： - 性质3涉及到度为2的结点数（有两个孩子的结点）与度为0的结点数（叶子结点）的关系。在任何一棵二叉树中，度为2的结点数总是比叶子结点数少1。 - 性质4是关于完全二叉树高度的计算，N个节点的完全二叉树的高度h满足2^(h-1) <= N < 2^h，所以高度h可以通过log2(N+1)向上取整得到。 2. **哈希表**： - 哈希函数H(key)=Key%10用于将关键字映射到长度为10的哈希表中，使用二次探测再散列法解决冲突。这意味着如果哈希函数产生的位置已有元素，会按2的倍数（2, 4, 6, ...）寻找下一个空位置，直到找到为止。 3. **Dijkstra算法**： - 这是一种用于查找图中两点之间最短路径的算法，从起点V1出发，逐步扩展最短路径。描述了每一步的状态，即每次选择当前未访问节点中距离源点最短的节点并更新其相邻节点的距离。 4. **稀疏矩阵转置**： - 稀疏矩阵用三元组顺序表存储，转置过程涉及到行和列的交换，这里需要描述如何高效地实现这一转换。 5. **链表操作**： - 要求通过合并两个递增有序链表A和B来得到它们的交集，并形成一个新的递减有序链表。这需要利用双指针法和条件判断来实现。 **操作系统部分**： 1. **线程与进程**： - 线程是程序执行的最小单位，而进程是系统分配资源的基本单位。线程引入的原因主要是提高并发性和减少资源开销，线程间的切换比进程更快，且同一进程内的线程共享内存空间。 2. **通道**： - 通道是用于实现I/O设备和存储器之间直接数据传输的硬件机构，交叉连接允许多个设备同时传输数据，提高了I/O效率。 3. **缓冲区**： - 操作系统引入缓冲是为了平滑I/O操作，减少CPU等待I/O的时间，提高系统效率，也可以减少数据丢失的风险。 4. **文件的物理结构**： - 文件的物理结构包括顺序结构、链接结构、索引结构等，不同的结构适用于不同的场景，例如顺序结构适合连续存储，链接结构适合动态增长，索引结构便于随机访问。 5. **资源调度问题**： - 类似于读者-写者问题，描述了并发访问的同步问题，需要通过信号量或其他同步机制来确保正确性。 这些题目覆盖了计算机科学的基础知识点，对于准备考研的学生来说，是检验和巩固理论知识的好材料。通过这些题目，可以深入理解数据结构与操作系统的原理及其在实际问题中的应用。