《考研真题：广东暨南大学2022年[计算机基础综合]考试真题》由会员分享，可在线阅读，更多相关《考研真题：广东暨南大学2022年[计算机基础综合]考试真题（9页珍藏版）》请在金锄头文库上搜索。
1、考研真题：暨南大学 2022 年计算机基础综合考试真题考研真题：暨南大学 2022 年计算机基础综合考试真题第一部分数据结构第一部分数据结构一、单项选择题一、单项选择题1.含有 m 个结点的二叉树链式存储结构中空指针的个数为()。A2mBm-1Cm+1Dm2.下列排序算法中元素的移动次数和关键字的初始排列次序无关的是()。A.快速排序B.插入排序C.选择排序D.希尔排序3.一个栈的进栈序列是 abcde，则栈的输出序列不可能的是()。AabcdeBedcbaCdecbaDdceab4.需要的辅助空间最多的排序算法为()。A.归并排序B.快速排序C.基数排序D.堆排序5.哈希表的平均查找长度说法
2、错误的是()。A.与处理冲突方法有关而与表的长度无关B.与选用的哈希函数有关C.与哈希表的饱和程度有关D.与表中填入的记录数有关6.有 n 个顶点、e 条边且使用了邻接表存储的有向图进行深度优先遍历，其算法的时间复杂度是()。A.O（n+e）B.O（n2）C.O（n+2e）D.O（n*e）7.已知一个长度为 11 的顺序表，其元素按关键字有序排列，若采用折半查找查找一个其中不存存在的元素，则关键字的比较次数最多是()。A3B4C5D68.一棵完全二叉树上有 3001 个结点，其中叶子结点的个数是()。A.1500B.1501C.1000D.10019.若一棵二叉树度为 2 的结点有 18 个，
3、度为 1 的结点有 10 个，则度为 0 的结点个数是()。A.46B.28C.19D.1710.m 阶 B-树是一棵()。A.m 叉排序树B.m-1 叉平衡排序树C.m 叉平衡排序树D.m+1 叉平衡排序树二、填空题二、填空题1.已知一棵二叉树的中序遍历序列为GDHBAECIF，后序遍历序列为GHDBEIFCA，那么先序遍历序序列为。2.若某记录的关键字序列是（491，77，572，16，996，101，863，258，689，325），以第一个关键字为枢轴，写出采用快速排序算法第一趟排序的结果。3.将对称矩阵 A88的下三角部分逐行存储到起始地址为 2000 的内存单元中，已知每个元素占
4、4 个单元，假设第一个元素是 A00，则 A46的地址是。4.在顺序表中插入一个元素，需要平均移动表中一半元素，具体移动元素的个数与有关。5.在哈希查找方法中，要解决两方面的问题，它们是和。6.循环队列中，Q.rear=Q.front表示循环队列空，表示循环队列满的条件是。三、简答题三、简答题1.将下面的森林转换为二叉树（3 分），并给出该二叉树的中序线索链表（4 分）。2.设 Huffman 编码的长度不超过 4，若已对两个字符编码为 01 和 11，则最多还可以对多少个字符编码，为什么？(7 分）3.假设图的顶点是 A、B、C、D、E，请根据下面的邻接矩阵画出相应的有向图（3 分），然后画
5、出图的邻接表和逆邻接表（4 分）。0101000001100010100000110四、编写算法四、编写算法1.试编写一个算法完成下面的功能：对于输入的任意一个非负十进制整数，输出与其等值的八进制数。（10 分）2.试编写一个算法，在有向图 G 中，判定从顶点 Vi 到顶点 Vj 是否有通路。（10分）ABCDEFGH第二部分操作系统第二部分操作系统五、判断题五、判断题1.系统调用中的被调用程序运行在系统态。2.银行家算法采用了死锁预防的方法。3.文件系统采用树形目录结构可以节省内存空间。4.虚存管理允许用户程序大于主存容量，而且还可以提高系统的吞吐量。5.SPOOLing 系统实现了设备的独
6、立性。6.分时系统的时间片越小，用户的满意度就越高。7.管程每次只允许一个进程进入。8.操作系统既可看作虚拟机，也可看作资源管理器。9.在作业调度时，采用最高响应比优先的作业调度算法可以得到最短的作业平均周转时间。10.并行程序设计中，使用信号量比使用管程更能保证程序的正确性。六、填空题六、填空题1.对于速率为 9.6KB/s 的数据通信而言，如果设置一个具有 8 位的缓冲寄存器，则 CPU 中断时间和响应时间分别大约为（1）、（2）。2.如果计算机连接了三个同类型的激光打印机及五个同类型的喷墨打印机，需要安装的驱动程序数目是（3）。3.在具有 n 个进程的系统中，允许 m 个进程(nm1)同
7、时进入它们的临界区，其信号量 S 的值的变化范围是（4），处于等待状态的进程数最多有（5）个。4.动态分区的（6）算法可以使内存中的空闲分区分布得更均匀。5.UNIX 的目录项由文件名和（7）构成。6.若干事件在同一时间间隔内发生称为（8）。7.虚拟存储器具有（9）、（10）和虚拟性三大特征。七、单选题七、单选题1.请求调页系统中，如下算法中，()淘汰自上次访问以来经历时间最长的页面。A.FIFOB.OPTC.NRUD.LRU2.下列进程调度算法中，()可能会出现进程长期得不到调度的情况。A.静态优先权法B.抢占式调度中采用动态优先权法C.分时处理中的时间片轮转调度算法D.非抢占式调度中采用
8、FIFO 算法3.分时系统中，CPU 进程切换需要 3ms，为使得 100 个用户均能在 1 秒内得到响应，可以选择的时间片是()。A.2msB.50msC.10msD.7ms4.磁盘的 I/O 控制主要采取()方式。A.程序 I/OB.中断C.DMAD.SPOOLing5.系统产生死锁是指()。A.系统发生重大故障B.若干进程同时处于阻塞状态C.请求的资源数大于系统提供的资源数D.若干进程等待被其他进程所占用而又不可能被释放的资源6.通道又称 I/O 处理机，它用于实现()之间的信息传输。A.CPU 与外存B.CPU 与外设C.内存与外存D.内存与外设7.下面叙述正确的是()。A.程序段是进
9、程存在的唯一标志B.系统通过 PCB 来控制和管理进程，用户可以从 PCB 中读出与本身运行状态相关的信息C.当进程有执行状态变为就绪状态时，CPU 现场信息必须被保存在 PCB 中D.当进程申请 CPU 得不到满足时，它将处于阻塞状态8.在没有快表的情况下，分页系统要访问()次内存。A.1B.2C.3D.49.计算机操作系统中，若 WAIT、SIGNAL 操作的信号量 S 初值为 3，当前值为-4，则表示当前有()个等待信号量 S 的进程。A.1B.2C.3D.410.有 10 个进程共享 5 个打印机，若信号量 S 的当前值是-2，则当前有()个进程提出了打印请求？A.10B.7C.5D.
10、2八、简答题八、简答题1.什么是文件目录、目录文件，各起什么作用？2.多级树形目录的文件系统，怎样才能提高查找文件的速度?3.多线程系统与传统多进程系统相比有哪些优点？4.分页存储管理和分段存储管理的主要区别有哪些？5.用伪代码或文字描述 fork()系统调用是如何创建进程的。九、应用题九、应用题1.某类 Unix 系统采用成组链接法来管理磁盘的空闲空间，目前磁盘的状态图如下（10 分）：（1）该磁盘中目前还有多少个空闲盘块？(4 分)（2）给出该系统的磁盘块分配及回收算法（流程图或描述）。（6 分）2.分析下面给出的表达式的并行性，并用信号量机制实现该表达式的并行计算。（10 分）（3*a*b+4）/(c+d)(ef)(ef)
