还在更新，敬请期待
🔥暨南大学计算机848报考信息汇总仓库 仓库内有20年真题答案 https://github.com/zhanjuex/JNU_848
🔥🔥 II 真题答案与解析848的20已公开，21、22和23已经写完。 有内容缺失或者疑问可以评论1035775998@qq.com。
往年830答案： https://pan.baidu.com/s/18o4SU5GRkiJKO1YuxzwIBQ?pwd=zvxb
🔥🔥 III 往年真题与大纲848和830真题资料： https://pan.baidu.com/s/1WIoN8cmML0rSJcihb7wwtQ?pwd=769g
🍒 前言建议把往年的830和848都做了。
🍒 2023年 848真题答案与解析🍊 选择题
🍋 一、单项选择题 操作系统： 1 - 5 C B B C D 6 - 10 C A B C B
🍒 2020年 848真题答案与解析数据结构
答案给出的页数都来自于《严书》电子版。因为没有正确答案，所以给所的答案并不完全正确，自己做的时候要保持质疑的态度。如果有校正会及时更新。您如果发现错误，可以在底下评论。有内容缺失或者疑问可以在下面评论找。
🍊 数据结构🍋 单项选择题
答案： 1 - 5 C C D C D 6 - 10 A B B C C
解析：
🍋 填空题
答案： 1. ABDGHCEFI 2. 325 77 258 16 101 494 863 996 689 572 3. 2100 4. 插入元素在表中的位置 5. 如何构造哈希函数 如何解决冲突 6. Q.front == (Q.rear + 1) % MAXSIZE
解析：
🍋 简答题
🍋 算法题
试编写一个算法完成下面的功能：对于输入的任意一个非负十进制整数，输出与其等值的八进制数。（10分）严书P48 
严书P169 深度遍历和广度遍历都可以。 深度遍历 
访问该顶点后，查找visited[j]。 
同样也要查找visited[j]。
🍋 判断题
答案： 1 - 5 √ × × √ × 6 – 10 × √ √ × × 解析：
🍋 填空题
0.1ms 0.0125ms2[m - n, m] n-m循环首次适应指向该文件的索引结点指针并发多次性 对换性
2. P145 3. P58 4. P88 
5. P148 
7. P109 
以上都是书上内容，辅导真的要好好看！
🍋 单选题
答案： 1 - 5 D A D C D 6 - 10 D C B D B 解析：
🍋 简答题
3. 
🍋 应用题
前言
🍋算法思想建立新的头结点minusHead。
扫描原链表的负结点，将其抽出后利用尾插法接到minusHead的链表中。
遍历完原链表后，将minusHead后的链表接在tail后，返回minusHead->next。
🍋代码 LNode* Sort(LinkList Head) {LNode* minusHead = new LNode();LinkList minus = minusHead;LNode *p = Head->next, *tail = Head;while(p){if (p->data >= 0){tail = p;p = p->next;}else{minus->next = p;minus = p;tail->next = p->next;p = p->next;}}tail->next = minusHead->next;minus->next = nullptr;// 避免陷入死循环return minusHead->next;} 🍊3.2 操作系统第二题 🍋步骤先把题干信息看全
互斥：叫号机。 同步：客人等待就柜台叫号，否则等待。 变量：排队序号，等待人数，窗口号。
题目不难，但是要求有点多，根据考场临城情况，我实现了两个版本，一个能基本拿分，一个基本满分。
🍋代码版本一： 易想版，最快时间拿分。
semaphore call = 1,service = n, wait = 0;int no = 0, num = 0;client() {while (1) {// 叫号机p(call);// 序号和排队人数print("%d %d\n",++no, no - num);v(call);// 令柜台程序运行v(wait)p(service);接受服务;}}teller() {while(1) {p(wait);++num;print("%d %d\n",no, 窗口号);提供服务;v(service(窗口号));}}版本二： 悠闲版，就要满分。
🍒 2023 真题第一部分 客观题
一、 单项选择题(第1-20题，每小题1分，第21-30题，每小题2分，1-10题为操作系统部分，11-20题为数据结构部分，21-30题为C语言程序设计部分) 1-10操作系统部分
下列关于管道（Pipe）通信的叙述中，正确的是( )。 A.一个管道可实现双向数据传输 B.管道的容量仅受磁盘容量大小限制 C.进程对管道进行读操作和写操作都可能被阻塞 D.一个管道只能有一个读进程或一个写进程对其操作避免死锁的一个著名的算法是( )。 A.先入先出法 B.银行家算法 C.优先级算法 D.资源按序分配法在9个生产者，6个消费者共享容量为8的缓冲区的生产者-消费者问题中，互斥使用缓冲区的信号量S的初始值为（ ）。 A.8 B.1 C.9 D.6一种既有利于短小作业又兼顾到长作业的作业调度算法是（ ）。 A.先来先服务 B.轮转 C.最高响应比优先 D.均衡调度分布式操作系统与网络操作系统本质上的不同在于（ ）。 A.实现各台计算机之间的通信 B.共享网络中的资源 C.满足较大规模的应用 D.系统中若干台计算机相互协作完成同一任务假定磁盘块的大小为1K，对于1.2MB的软盘，FAT需占用（ ）的存储空间 A. 1KB B. 1.5KB C. 1.8KB D. 2.4KB关于线程以下的说法正确的是（ ）。 A.同一进程中各线程可以共享进程的主存空间 B.同一进程中多线程不能独立执行 C.线程是资源分配的独立单位 D.线程是就是进程的另外一个称呼正在运行的进程需要向外设上输出数据，此时进程状态从（ ）。 A.等待态变为就绪态 B.运行态变为等待态 C.就绪态变为运行态 D.运行态变为就绪态有10个并发进程，每个进程对资源的最大需求数是3，当这10个进程共享m个资源时，m值最小取（ ）时不会发生死锁。 A. 3 B. 20 C. 30 D. 10当分时系统用户数为200个，对每个用户的响应时间为1s，时间片最大值是（ ）。 A. 5ms B. 10ms C. 200ms D. 0.1s 11-20数据结构部分若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ）。 A.单链表 B.仅有头指针的单循环链表 C.双向链表 D.仅有尾指针的单循环链表循环链表的主要优点是（ ）。 A. 不再需要头指针 B. 已知某结点位置后能容易找到其直接前驱 C. 在进行插入、删除操作时能保证链表不断开 D. 从表中任一结点出发都能扫描整个链表将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为35的结点的左孩子编号为（ ）。 A. 34 B. 36 C. 70 D. 71按照二叉树的定义，具有3个结点的二叉树有（ ）种。 A. 3 B. 4 C. 5 D. 6任何一个无向连通图的最小生成树（ ）。 A. 只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在深度优先遍历类似于二叉树的（ ）。 A先序遍历 B中序遍历 C后序遍历 D层次遍历表达式a*(b+c)-d的后缀表达式是（ ）。 A. abcd± B. abc+d- C. abc+d- D.-+*abcd如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是 （ ）。 A.G肯定不是完全图 B.G中一定有回路 C.G一定不是连通图 D.G有2个连通分量算法的时间复杂度不是O(nlogn)的算法是（ ）。 A、快速排序 B.归并排序 C.堆排序 D.基数排序用邻接表表示图进行广度优先遍历时，通常采用（ ）来实现算法。 A.栈 B.队列 C.树 D.图二、判断题(每小题1分，正确的写True，错误的写False，1-10题为操作系统部分，11-20题为数据结构部分，21-30题为C语言程序设计部分) 1-10 操作系统部分
根据死锁定理，资源分配图中存在环路，就一定会产生死锁。虚拟存储器的容量是由用户和辅存所决定的。阻塞队列可能包含系统进程。只要破坏产生死锁的四个必要条件中的其中一个就可以预防死锁的发生。优化文件物理块的分布可显著地减少寻道时间，因此能有效地提高磁盘I/O的速度。字符设备指的是只能存取文本符号的设备。在用于同步时，信号量的初值设为负数表示缺少的资源个数。分时系统的时间片越小，响应速度越快，因此用户的满意度就越高。在内存利用率方面，分页存储管理比分段存储管理更高些。 10.任何手段都无法实现计算机系统资源之间的互换。 11-20 数据结构部分在一棵二叉树中，中序遍历的第一个结点，是二叉树的最左下结点。顺序表查找指的是在顺序存储结构上进行查找。已知一颗二叉树的先序序列和后序序列，一定能构造出该树。在一棵树中，堂兄弟的双亲是兄弟关系。不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。一个图按广度优先遍历的结果是唯一的。由树转化为二叉树，该二叉树的右子树不一定为空。无向图的邻接矩阵是对称的，因此可只存储矩阵的下三角阵。三、填空题（第1-10空，每空1分，第11-15空，每空2分，1-9题为操作系统部分，10-14题为数据结构部分） 1-9 操作系统部分
为实现CPU与外部设备的并行工作, 系统必须引入（1）作为硬件基础。在磁盘调度策略中有可能使I/O请求无限期等待的调度算法是（2） 。在（3）的作业调度算法中，当各个作业等待时间相同时，运行时间短的作业将得到优先调度；当各个作业要求运行的时间相同时，等待时间长的作业得到优先调度。UNIX的文件系统空闲空间的管理采用的是（4）法。同步机制要遵循的四条规则分别是空闲让进、忙则等待、 （5） 及让权等待。文件的三种物理结构是：顺序结构、（6） 、索引结构。分时系统的特点是：（7） 、交互性、独占性和及时性。虚拟存储器的特征是： （8） 、多次性、对换性和虚拟性。n个进程共享m个同类资源(n≥m≥1,设信号量初值S=m)，S的值可能的变化范围是 （9） ，处于等待状态的进程数最多有（10）个。 10-14 数据结构部分 10．一组记录的排序码为(45，35，71，51，20，26，61，12)，则利用快速排序的方法，以第一个记录为基准得到的第一次划分结果为 （11） 。 11．在折半查找中，要求待查找的关键字序列必须 （12） ，这样才能进行查找操作。 12．设二叉树中度为0的结点数为30，度为1的结点数为20，则该二叉树中总共有 （13） 个结点数。 13．设矩阵是一个N×N对称矩阵，将其下三角部分按行序存放在一维数组中，对下三角部分中任一元素Aij(i>=j)，在一维数组中的下标位置k与i和j的关系为 （14） 。 14．在N个结点的线索二叉树中线索的数目为 （15） 。第二部分 操作系统主观题
四、 举例说明什么是实时系统中的优先级反转(或倒转)。(5分) 五、 试比较内存管理和外存管理的异同点。(5分) 六、 简述设备驱动程序的主要功能。(5分) 七、 采取哪些措施才能提高文件检索的速度。(5分) 八、fork为创建进程的系统调用，下面的程序创建多少个子进程? 输出多少个A和B? (5分) int main(void) { int i; for(i=0; idata ); if (!T->Lchild && !T->Rchild ) PrintStack(S); else { F ( T->Lchild, S ); F( T->Rchild, S ); } Pop(S); } } 十四、假设表中关键字序列为（41，36，58，12，79，25），将关键字依次插入一棵初始为空的二叉排序树，然后删除结点41。（1）画出二叉排序树的生成过程；（2）画出删除结点41后的二叉排序树。(6分) 十五、假设二叉树采用二叉链表存储结构，试编写一个非递归算法，输出中序遍历序列中第k个结点的数据值。(8分) 十六、试编写一个算法，在链式存储结构上实现直接插入排序算法。(8分) 十七、若矩阵Amn中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设二维数组存储矩阵Amn，试编写求出矩阵中所有马鞍点的算法。(8分)
🍒 2020年真题第一部分 数据结构（75分） 一、 单项选择题(每题2分，共20分)
含有m个结点的二叉树链式存储结构中空指针的个数为 ( )。 A．2m B．m-1 C．m+1 D．m下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。 A. 快速排序 B. 插入排序 C. 选择排序 D. 希尔排序一个栈的进栈序列是a b c d e，则栈的输出序列不可能的是（ ）。 A．a b c d e B．e d c b a C．d e c b a D．d c e a b需要的辅助空间最多的排序算法为（ ）。 A. 归并排序 B. 快速排序 C. 基数排序 D. 堆排序哈希表的平均查找长度说法错误的是 ( )。 A. 与处理冲突方法有关而与表的长度无关 B. 与选用的哈希函数有关 C. 与哈希表的饱和程度有关 D. 与表中填入的记录数有关有n个顶点 、e条边且使用了邻接表存储的有向图进行深度优先遍历，其算法的时间复杂度是（ ）。 A. O（n+e） B. O（n2） C. O（n+2e） D. O（n*e）已知一个长度为11的顺序表，其元素按关键字有序排列，若采用折半查找查找一个其中不存存在的元素，则关键字的比较次数最多是（ ）。 A．3 B．4 C．5 D．6一棵完全二叉树上有3001个结点，其中叶子结点的个数是（ ）。 A. 1500 B.1501 C. 1000 D.1001若一棵二叉树度为2的结点有18个，度为1的结点有10个，则度为0的结点个数是（ ）。 A. 46 B. 28 C. 19 D. 17m阶B-树是一棵（ ）。 A .m叉排序树 B. m-1叉平衡排序树 C. m叉平衡排序树 D. m+1叉平衡排序树二、 填空题(每空2分，共14分)
已知一棵二叉树的中序遍历序列为GDHBAECIF，后序遍历序列为GHDBEIFCA，那么先序遍历序序列为 。若某记录的关键字序列是（491，77，572，16，996，101，863，258，689，325），以第一个关键字为枢轴，写出采用快速排序算法第一趟排序的结果 。3. 将对称矩阵A[8][8]的下三角部分逐行存储到起始地址为2000的内存单元中，已知每个元素占4个单元，假设第一个元素是A[0][0]，则A[4][6]的地址是 。在顺序表中插入一个元素，需要平均移动表中一半元素，具体移动元素的个数与 有关。 5.在哈希查找方法中，要解决两方面的问题，它们是 和 。循环队列中，Q.rear == Q.front表示循环队列空，表示循环队列满的条件是 。三、 简答题（共3小题，每题7分，共21分）
将下面的森林转换为二叉树（3分），并给出该二叉树的中序线索链表（4分）。
2. 设Huffman编码的长度不超过4，若已对两个字符编码为01和11，则最多还可以对多少个字符编码，为什么？(7分） 假设图的顶点是A、B、C、D、E，请根据下面的邻接矩阵画出相应的有向图（3分），然后画出图的邻接表和逆邻接表（4分）。 
四、 编写算法（共2小题，每题10分，共20分）
试编写一个算法完成下面的功能：对于输入的任意一个非负十进制整数，输出与其等值的八进制数。（10分）
试编写一个算法，在有向图G中，判定从顶点Vi到顶点Vj是否有通路。（10分）
第二部分 操作系统（75分） 五、 判断题(每小题1分，共10分，正确的打√，错误的打×)
系统调用中的被调用程序运行在系统态。银行家算法采用了死锁预防的方法。文件系统采用树形目录结构可以节省内存空间。虚存管理允许用户程序大于主存容量，而且还可以提高系统的吞吐量。SPOOLing系统实现了设备的独立性。分时系统的时间片越小，用户的满意度就越高。管程每次只允许一个进程进入。操作系统既可看作虚拟机，也可看作资源管理器。在作业调度时，采用最高响应比优先的作业调度算法可以得到最短的作业平均周转时间。并行程序设计中，使用信号量比使用管程更能保证程序的正确性。六、 填空题 (每小题1分，共10分)
对于速率为9.6KB/s的数据通信而言，如果设置一个具有8位的缓冲寄存器，则CPU中断时间和响应时间分别大约为 （1） 、 （2） 。如果计算机连接了三个同类型的激光打印机及五个同类型的喷墨打印机，需要安装的驱动程序数目是 （3） 。在具有n个进程的系统中，允许m个进程(n≥m≥1)同时进入它们的临界区，其信号量S的值的变化范围是 （4） ，处于等待状态的进程数最多有 （5） 个。动态分区的 （6） 算法可以使内存中的空闲分区分布得更均匀。UNIX的目录项由文件名和 （7） 构成。若干事件在同一时间间隔内发生称为 （8） 。虚拟存储器具有 （9） 、 （10） 和虚拟性三大特征。七、 单选题(每小题1分，共10分)
请求调页系统中，如下算法中，( ) 淘汰自上次访问以来经历时间最长的页面。 A. FIFO B. OPT C. NRU D. LRU下列进程调度算法中，( ) 可能会出现进程长期得不到调度的情况。 A. 静态优先权法 B. 抢占式调度中采用动态优先权法 C. 分时处理中的时间片轮转调度算法 D. 非抢占式调度中采用FIFO算法分时系统中，CPU进程切换需要3ms，为使得100个用户均能在1秒内得到响应，可以选择的时间片是（ ）。 A. 2ms B. 50 ms C. 10ms D. 7 ms磁盘的I/O控制主要采取( ) 方式。 A. 程序I/O B. 中断 C. DMA D. SPOOLing系统产生死锁是指( ) 。 A. 系统发生重大故障 B. 若干进程同时处于阻塞状态 C. 请求的资源数大于系统提供的资源数 D. 若干进程等待被其他进程所占用而又不可能被释放的资源通道又称I/O处理机，它用于实现( ) 之间的信息传输。 A. CPU与外存 B. CPU与外设 C. 内存与外存 D. 内存与外设下面叙述正确的是( ) 。 A. 程序段是进程存在的唯一标志 B. 系统通过PCB来控制和管理进程，用户可以从PCB中读出与本身运行状态相关的信息 C. 当进程有执行状态变为就绪状态时，CPU现场信息必须被保存在PCB中 D. 当进程申请CPU得不到满足时，它将处于阻塞状态在没有快表的情况下，分页系统要访问( )次内存。 A. 1 B. 2 C .3 D. 4计算机操作系统中，若WAIT、SIGNAL操作的信号量S初值为3，当前值为-4，则表示当前有( ) 个等待信号量S的进程。 A. 1 B. 2 C. 3 D. 4有10个进程共享5个打印机，若信号量S的当前值是-2，则当前有( )个进程提出了打印请求？ A. 10 B. 7 C. 5 D. 2八、 简答题(每小题5分，共25分)
什么是文件目录、目录文件，各起什么作用？多级树形目录的文件系统，怎样才能提高查找文件的速度?多线程系统与传统多进程系统相比有哪些优点？分页存储管理和分段存储管理的主要区别有哪些？用伪代码或文字描述fork()系统调用是如何创建进程的。九、 应用题(每小题10分，共20分)
某类Unix系统采用成组