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

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

《计算机操作系统》一、填空题（10 分，每空 2 分）

若信号量S 的初值为4，当前有6 个进程在等待信号量S，则当前信号量S 的值为 。

某系统中共有 11 台打印机，X 个进程共享此打印机，每个进程最多请求使用 3 台打印机，则该系统中不会发生死锁的最大X 值是 。

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

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

某文件系统的文件控制块占 64B，单个盘块大小为 1KB，采用一级目录结构。假设文件目录中有 3200 个目录项，则查找一个文件平均需要访问 次磁盘。

二、选择题（14 分，每题 2 分）

1.若下列指令已装入指令寄存器，执行时不可能导致 CPU 从用户态变为内核态的是（）。

A．DIV R0，R1；(R0)/(R1)→R0

B．INT n；产生软中断

C．NOT R0；寄存器 R0 的内容取非

D．MOV R0,addr；把地址处的内存数据放入寄存器 R0 中

2.在下列进程调度算法中，不存在进程饥饿现象的调度算法是（）。

A．先来先服务B．反馈调度算法

C．短进程优先D．基于静态优先级调度算法

3.资源的有序分配策略是为了破坏死锁产生的（）条件。

A．互斥B．请求和保持

C．非剥夺D．循环等待

4.在段式存储管理系统中，若不考虑快表，为获得一条指令或数据，至少需要访问（） 次内存。

A．1

B．2

C．3

D．4

5.在设备管理中，不属于 I/O 控制方式的是（

）。

A．程序查询方式

B．中断驱动方式

C．DMA 方式

D．重定位方式

6.下列文件物理结构中，适合随机访问且易于文件扩展的是（）。

A．哈希文件

B．索引文件

C．链式结构文件

D．连续结构文件

7.设置当前工作目录的主要作用是（

）。

A．加快文件的读/写速度

B．加快文件的检索速度

C．节省外存空间

D．节省内存空间

三、简答题（4 题，共 21 分）

PCB 的主要存储内容是什么？为什么说PCB 是进程存在的唯一标志？（6 分）

什么是虚拟存储器？如何实现页式虚拟存储器？（5 分）

什么是设备的独立性，应如何实现？（5 分）

文件物理结构是指一个文件在外存上的存储组织形式，那么何谓文件的混合索引结构？ 其主要优点是什么？（5 分）

四、分析计算题（2 题，共 30 分）

某计算机采用段页式虚拟存储器，已知虚拟地址为 32 位，按字节编址，每个段最多可以有 2K 页，页大小为 16KB，物理主存容量为 512MB。请回答以下问题：（10 分）

虚拟存储器的容量是多少？

给出逻辑地址结构并说明理由。

计算逻辑地址 0X4EB9FDE3 的段号，段内页号及页内偏移值（最后计算结果须用十六进制表示）。

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

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

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

缓冲区满时，生产者必须阻塞；

缓冲区空时，消费者必须阻塞。

请用P、V 操作实现其同步过程，须说明信号量含义。（20 分）

《数据结构》一、填空题(共 10 空，每空 1 分，共 10 分)

顺序表采用的是 存取方式，线性链表采用的是 存取方式。

深度为d,(d  1) 的完全二叉树至少含有 个节点，至多含有 个节点。

3 个节点构成的二叉树有 种不同形状。3 个元素依次入栈可能的出栈序列有 种。

无向连通图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.下列关于哈夫曼树的论述不正确的是()。

哈夫曼树又被称为最优二叉树

哈夫曼树是带权路径最短的二叉树

一棵哈夫曼树任意交换左右子树仍然是一棵哈弗曼树

对给定的输入数值集合所生成的哈夫曼树深度是确定的

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 项数据记录为(7, 6, 5, 4, 3, 2, 1)。将它调整成为小顶堆，给出筛选过程。

6.全源最短路径问题采用 Floyd 算法进行求解。下面给出了一个由 4 个顶点构成的有向图邻接矩阵 Dist[4][4]和路径矩阵 Path[4][4]。约定 Dist 中用∞表示不能到达，Path 中用-1 表示没有前驱的情况。请计算并给出每一次迭代的结果。(请将答案誊写在答题纸上)

Dist(-1) Dist(0) Dist(1) Dist(2) Dist(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) Path(0) Path(1) Path(2) Path(3)

0

1

2

3

0123

0123

0123

0123

0

-1

0

0

-1

1

-1

-1

1

1

2

-1

-1

-1

2

3

3

-1

-1

-1

四、算法题(共 2 题，共 15 分)

1.设规模 n  3m, m  1的顺序表存储在一维数组 int array[n]中，它含有的元素为

(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无损版本，可以加群下载。）