闽南师范大学2018年硕士研究生入学考试试题
考试科目:计算机专业基础(B)
注意事项:
1、本卷满分为150分,考试时间为3小时;
2、本卷属试题卷,另有答题纸,答案一律写在答题纸上,写在该试卷或草稿纸上均无效;
3、必须用蓝黑钢笔或签字笔答题,其他均无效。
******************************************
计算机操作系统
一、单项选择题(每小题1分,共10分)
1、操作系统是对( )进行管理的软件。
A、硬件 B、软件 C、计算机资源 D、应用程序
2、在单处理机系统中实现并发技术后,( )。
A、进程在一个时间段内并行运行,CPU与外设间并行工作。
B、进程在一个时刻点上并行运行,CPU与外设间并行工作.
C、进程在一个时间段内并行运行,CPU与外设间串行工作.
D、进程在一个时刻点上并行运行,CPU与外设间串行工作.
3、计算机系统在执行( )时,会自动从目态变换到管态。
A. P操作 B.V操作 C.系统调用 D.I/O指令
4、某系统中有3个并发进程,都需要4个同类资源。试问该系统不会产生死锁的最少资源总数应该是( )。
A.9 B.10 C.11 D.12
5、若信号量S初值为2,当前值为1,则表示有( )个进程在与S相关的队列上等待。
A.0 B.1 C.2 D.3
6、以下( )不可以提供虚存。
A、 可变分区存储管理 B、页式存储管理
C、 段式存储管理 D、段页式存储管理
7、以下( )不是设备管理使用的数据结构。
A.JCB B.DCT C.COCT D. CHCT
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、在某个请求分页管理系统中,假设某进程的页表内容如下所示有效位(存在位)
0 120H 1
1 ---- 0
2 850H 1
页面大小为4KB,一次内存的访问时间是200ns,一次快表(TLB)的访问时间是20ns,处理一次缺页的平均时间为 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、具有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。请回答下列问题。
(1)(9分)画出最小生成树T。
(2)(6分)计算T中各边权值之和。
2、若有一个无向图,
(1)(7分)画出该无向图的邻接矩阵;
(2)(8分)画出该无向图的邻接表。
3、设哈希表的地址范围0~17,哈希函数为H(k)=k MOD 16。k为关键字,用线性探测法处理冲突,输入关键字序列:(10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49)。画出哈希表的示意图;若查找关键字63,需要依次与哪些关键字进行比较?若查找关键字60,需要依次与哪些关键字比较?
三、算法设计题(15分)
下面给出二叉树的结点定义:
typedef struct node
{
int data;
struct node *lchild, *rchild;
} BinTnode;
typedef BinTNode BinTree;
请编写函数SearchXNum,计算任意二叉树T中其数据域的值大于或等于x的结点的个数并返回该值。函数原型如下:
int searchXNum(BinTree *T, int x);
(以下空白)