2016年硕士研究生入学考试考试科目：820计算机专业基础

注意：所有答案必须写在答题卡上。在试卷或草稿纸上书写无效。

055-79000一、填空(10分，每空2分)。如果信号量S的初始值是4，并且当前有6个进程在等待信号量S，则当前信号量S的值是。

一个系统有11台打印机，x个进程共享这台打印机，每个进程请求最多使用3台打印机，所以这个系统不会发生死锁的最大x值是。

虚拟存储管理系统是基于程序理论的。

为了满足用264个地址空间运行的作业，采用多级分页存储管理，假设页大小为4KB，页表中每个页表项需要占用8个字节。那么，为了满足系统的分页存储管理，至少要采用页表。

一个文件系统的文件控制块占用64B，单个磁盘块大小1KB，采用一级目录结构。假设文件目录中有3200个目录条目，搜索一个文件平均需要访问二级磁盘。

二、选择题(14分，每题2分)1。如果下面的指令已经加载到指令寄存器中，那么在执行时，是()不能使CPU从用户模式变为内核模式。

A.R1 R0分区；(R0)/(R1)R0

B.INT n；产生软中断

C.不是R0；寄存器R0的内容被求反。

D.MOV R0，地址；将该地址的内存数据放入寄存器R0

2.在下列进程调度算法中，无进程饥饿的调度算法是()。

A.先来先服务b .反馈调度算法

C.短进程优先级d .基于静态优先级调度算法

3.资源的有序分配策略是打破僵局的()条件。

A.互斥b .请求和保持

C.非剥夺d .循环等待

4.在分段存储管理系统中，如果不考虑快表，要得到一条指令或数据，至少需要()次访问内存。

0 @ 166.com6 .下列文件物理结构中，()适合随机存取，易于文件扩展。

Ken1@166.com，简答(4题，共21分)PCB的主要存储内容是什么？为什么PCB是工艺存在的唯一标志？(6分)

什么是虚拟内存？如何实现页面虚拟内存？(5分)

什么是设备的独立性，应该如何实现？(5分)

文件物理结构是指一个文件在外存中的存储组织形式，那么什么是文件的混合索引结构呢？它的主要优点是什么？(5分)

四。分析计算题(2题，共30分)某计算机采用段页式虚拟内存。已知的虚拟地址是32位，按字节寻址。每个段最多可以有2K页，页大小为16KB，物理主存容量为512MB。请回答以下问题：(10分)

虚拟内存的容量是多少？

给出逻辑地址结构并解释原因。

计算逻辑地址0X4EB9FDE3的段号、页码和偏移值(最终计算结果必须用十六进制表示)。

n个生产者进程和M个消费者进程共享大小为K的缓冲区，遵循以下规则：

进程必须以互斥的方式访问缓冲区；

对于放入缓冲区的每一段数据，所有消费者都必须接收一次；

当缓冲区满了，生产者必须阻止它；

当缓冲区为空时，使用者必须阻塞它。

请用P和V运算实现同步过程，并解释信号量的含义。(20分)

055-79001一、填空题(共10题，每题1分，共10分)顺序表采用存取法，线性链表采用存取法。

深度为d (d 1)的完全二叉树最少包含个节点，最多包含个节点。

由三个节点组成的二叉树有不同的形状。三个元素依次堆叠。有几种可能的堆叠顺序。

无向连通图g包含n个节点和e条边。求G的最小生成树时间用Prim算法的复杂度为，时间用Kruskal算法的复杂度为。

快速排序一般情况下时间，复杂度为，空间复杂度为。

二。选择题(共10题，每题2分，共20分)

1.为了防止假溢出，循环队列采用模运算折叠空间，解决了判断队列头指针和队列尾指针是否指向一个单元的问题。下列()选项不是常见的解决方案。

A.牺牲一个存储空间b .设置一个计数器c .设置一个布尔变量d .重新配置一个指针。

2.下列选项中，不属于规则矩阵的是()。

A.三角矩阵b .对称矩阵c .对角矩阵d .稀疏矩阵

3.下列选项中，符合前缀码要求的是()。

A.{0，1}B. {0，01，001，0001}C. {10，010，110，101}D. {01，10，1001，0110}

4.下列关于霍夫曼树的说法不正确的是()。

哈夫曼树也叫最优二叉树。

Huffman树是一种具有最短加权路径的二叉树。

如果哈夫曼树的左右子树任意交换，哈夫曼树仍然是哈夫曼树。

为一组给定的输入值生成的霍夫曼树的深度被确定。

5.深度优先搜索和广度优先搜索中无向图的共同特征是()

a，都是递归算法；b、必须都用栈；c，都是遍历算法；d、搜索结果是唯一的。

6.对于AOE网络，如果其关键路径存在，则必是()。

A.最长路径b .最短路径c .拓扑排序序列d .唯一路径

7.拓扑排序解决的问题是()。

a .遍历有向图；b .计算有向图的回路数。

c .判断有向图是否有环；d，提示一个有向图。

8.给定广义表GL=((a，b)，(c，D，e)，(f，g))，定义表头函数为h()，表尾函数为t()，那么从GL中取出数据元素D的操作是()。

A.H(T(T(H(GL))))b . H(T(H(GL)))c . H(T(H(T(GL))))d . H(T(H(H(GL))))

9.将序列(2，4，6，8，10，12，14，16，18，20)切成两半，找到元素14，需要依次比较()。

A.10、18、14B。10，16，14C。10，18，12，14D。10, 16, 12, 14

10.以下哪种排序算法不能保证一趟行程后至少有一个元素落在最终位置是()。

A.冒泡排序b .希尔排序c .快速排序d .简单选择排序

三。简答题(共6题，每题5分，共30分)1。设计一个尽可能高效的策略使单循环链表成为队列，并给出入队和出队的复杂度时间。

2.输入数据序列为(5，1，9，3，7)。请根据输入顺序构造一棵排序二叉树，并画出它的中序线索。

3.输入数据序列是(10，30，40，20，15，25)。请根据输入的顺序构造一棵平衡二叉树。给出添加每个节点后平衡二叉树的调整结果。

4.给定输入关键字的顺序为(13，14，15，16，17，5，4，3，2，1)，根据哈希函数建立哈希表，使用公共溢出区方法解决冲突。已知哈希函数为Hash(key)=key MOD 11，哈希表长度为11，溢出表长度为5。请画出哈希表和溢出表，计算搜索成功时的平均搜索长度ASL(等概率)。

5.七个数据记录被称为(7，6，5，4，3，2，1)。调整成小顶堆，给出筛选流程。

6.Floyd算法解决了所有源最短路径问题。下面给出由四个顶点组成的有向图的邻接矩阵Dist[4][4]和路径矩阵Path[4][4]。在约定Dist中，表示不可达，而-1表示路径中没有前驱。请计算并给出每次迭代的结果。(请将答案抄写在答题卡上)

距离(-1)距离(0)距离(1)距离(2)距离(3)

	0	1	2	3	0123	0123	0123	0123
0	0	1	4
1		0	2	5
2			0	1
3	2			0

Path(-1)路径(0)路径(1)路径(2)路径(3)

Ken3@166.com四世。算法题(共2题，共15分)1。设置要存储在一维数组int array[n]中的小数位数N3m和M 1的顺序表，它包含以下元素

(a1，a2，am，b1，b2，bm，c1，c2，cm).请用编译计算的方法把上述顺序表改成(c1，c2，cm，bm，b2，b1，a1，a2，am)，要求是时间，复杂度和空间复杂度尽可能最低。C，C和Java都可以作为编程语言。(8分)

2.二叉树存储在二叉链表结构中。请写一个算法，求一个二叉树根节点左右子树之间距离最远的叶节点之间的距离。C，C和Java都可以作为编程语言。(7分)

(注：本文由辛徐老师整理。如果需要无损PDF版本，可以加群下载。)