资源描述
第 1 页 共 5 页闽 南 师 范 大 学 2018 年硕士研究生入学考试试题考试科目：计算机专业基础注意事项：1、本卷满分为 150 分，考试时间为 3 小时；2、本卷属试题卷，另有答题纸，答案一律写在答题纸上，写在该试卷或草稿纸上均无效；3、必须用蓝黑钢笔或签字笔答题，其他均无效。计算机操作系统一、单项选择题（每小题 1 分，共 10 分）( ) 1、操作系统是对 进行管理的软件。A、硬件 B、软件 C、计算机资源 D、应用程序( ) 2、在单处理机系统中实现并发技术后， 。A、进程在一个时间段内并行运行，CPU 与外设间并行工作。B、进程在一个时刻点上并行运行，CPU 与外设间并行工作.C、进程在一个时间段内并行运行，CPU 与外设间串行工作.D、进程在一个时刻点上并行运行，CPU 与外设间串行工作.（ ）3、计算机系统在执行 时，会自动从目态变换到管态。A. P 操作 BV 操作 C系统调用 DI/O 指令（ ）4、某系统中有 3 个并发进程，都需要 4 个同类资源。试问该系统不会产生死锁的最少资源总数应该是 。A9 B10 C11 D12（ ） 5、若信号量 S 初值为 2，当前值为 1，则表示有 个进程在与S 相关的队列上等待。A0 B1 C2 D3（ ） 6、以下 不可以提供虚存。A、 可变分区存储管理 B、页式存储管理C、 段式存储管理 D、段页式存储管理（ ） 7、以下 不是设备管理使用的数据结构。AJCB B.DCT C.COCT D. CHCT第 2 页 共 5 页（ ）8、假设一个扇区大小为 512B，1 块=1 扇区，FAT16 可以管理的磁盘空间大小为 A.32MB B.64MB C.128MB D.512MB（ ）9、用户可以通过调用 文件操作，来归还文件的使用权。A建立 B打开 C关闭 D删除（ ）10、 在设备管理中,通常采用主设备号和次设备号来表示一台机器,主设备号和次设备号分别表示 。A 设备类型和内部标识符 B. 设备驱动程序及参数C 设备名字及其类型 D. 设备名字及参数二、应用题（每小题 15 分，共 60 分）1、桌子上有一只盘子，每次只能放入一只水果，爸爸专门往盘子里放苹果，妈妈专门往盘子里放橘子，一个儿子专门吃盘子里的橘子，一个女儿专门等吃盘子里的苹果，用信号量实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。2、设有一组作业，它们的到达时间和所需 CPU 时间如下所示。作业号 到达时间 所需 CPU 时间1 9:00 70 分钟2 9:40 30 分钟3 9:50 10 分钟4 10:10 5 分钟分别采用先来先服务和短作业优先作业调度算法。试问它们的调度顺序、作业周转时间以及平均周转时间各是什么？3、在某个请求分页管理系统中，假设某进程的页表内容如下所示页号 页框（Page Frame）号 有效位（存在位）0 120H 11 - 02 850H 1页面大小为 4KB，一次内存的访问时间是 200ns，一次快表（TLB）的访问第 3 页 共 5 页时间是 20ns，处理一次缺页的平均时间为 910 ns（己含更新 TLB 和页表的时间） ，进程的驻留集大小固定为二页，采用最近最久未使用置换算法（LRU）和局部置换策略。假设TLB 初始为空；地址转换时先访问TLB，若 TLB 未命中，再访问页表（忽略访问页表之后的 TLB 更新时间） ；有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2345H、1876H、258FH，请问：a依次访问上述三个虚地址，各需多少时间？给出计算过程。b基于上述访问序列，虚地址 1876H 的物理地址是多少？请说明理由。4、假设某文件系统的硬盘空间为 500MB，盘块大小为 1KB，采用显示链接分配，请回答以下问题：(1)其 FAT 表（文件分配表）需占用多少存储空间？(2)如果文件 A 占用硬盘的盘块号依次为 120、130、145、135、125 共五个盘块，请画图示意文件 A 的 FCB 与 FAT 表的关系以及 FAT 表中各盘块间的链接情况。数据结构一、填空题（每题 2 分，共 20 分）1、已知一无向图 G=（V，E） ，其中 V=a,b,c,d,e,f E=(a,b),(d,e), (b,c),(a,f),(a,d)现用某一种图遍历方法从顶点 a 开始遍历图，得到的序列为 abfdce，则采用的是_遍历方法。 2、在循环队列中，若 front 与 rear 分别表示队头元素和队尾的位置，则判断循环队列空的条件是_。 3、中序遍历结果为 DBEAFC，一棵二叉树的前序遍历结果为 ABDECF，则后序遍历结果为_。 第 4 页 共 5 页4、在一个无向图中，所有顶点的度数之和等于所有边数_倍。5、具有 10 个叶结点的二叉树中有_个度为 2 的结点。 6、对于队列操作数据的原则是_。 7、假定一组记录的排序码为（46，79，56，38，40，80） ，对其进行快速排序的一次划分的结果_。 8、广义表 A=( a, ( b, c ( d, e, f ) ) )的长度是_。 9、对具有 15 个关键字的关键字序列进行顺序查找时，查找成功的平均查找长度_。 10、在链表中进行删除操作和_操作的效率高于顺序表。 二、应用题（每题 15 分，共 45 分）1、给定如下无向带权连通图 G, 从顶点 v0 开始，使用普里姆(Prim)算法，求 G 的最小生成树 T。请回答下列问题。v1v4v3v6v021 52 011 01 6v2v591 03（1） （9 分）画出最小生成树 T。（2） （6 分）计算 T 中各边权值之和。2、若有一个无向图，1 2543第 5 页 共 5 页（1） （7 分）画出该无向图的邻接矩阵；（2） （8 分）画出该无向图的邻接表。 3、设哈希表的地址范围 017，哈希函数为 H(k)=k MOD 16。k 为关键字，用线性探测法处理冲突，输入关键字序列:(10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49)。画出哈希表的示意图;若查找关键字 63，需要依次与哪些关键字进行比较？若查找关键字 60，需要依次与哪些关键字比较？三、算法设计题（15 分）下面给出二叉树的结点定义：typedef struct nodeint data;struct node *lchild, *rchild; BinTnode;typedef BinTNode BinTree;请编写函数 SearchXNum，计算任意二叉树 T 中其数据域的值大于或等于 x的结点的个数并返回该值。函数原型如下：int searchXNum(BinTree *T, int x);（以下空白）
展开阅读全文