电子科技大学
2014年攻读硕士学位研究生入学考试试题
考试科目：820计算机专业基础
注：所有答案必须写在答题纸上，写在试卷或草稿纸上均无效。
《计算机操作系统》
一、填空题（10分，每空2分）
1.现有3个同时到达的作业J1、J2和J3,它们的执行时间分别为Tl、T2和T3,且2020高考成绩什么时候公布T1<T3<T2。 若这三个作业在同一台处理器上以单道方式运行，则平均周转时间最小的执行顺序是
2.若一个信号暈的初值是5,经过多次P、V操作以后，其值变为则此时等待进入临 界区的进稈数目是—。
3.某基木分页存储管理系统具有快表，内存访问时间为2^,检索快表的时间为0.5J.LS'. 若快表的命中率为80%,且忽略快表更新时间，则有效访问时间是_
4.在段页式存储管理系统中，若不考虑快表，为获得一条指令或数据，至少需要访问   
次内存。
5.某虚拟存储器中的用户空间共有32湖北医疗卫生人才网个页面，每页1KB,主存l6KBo假设某时刻系统为
用户的第0、1、2、3页分别分配的物理块为5、10、4、7,则虚拟地址0A6F对应的物 理地址是    （请使用十九进制表示）。
二、选择题（14分，每题2分）
1.现代操作系统中最基本的两个特征是（）。
A.共享和不确定    B.并发和虚拟
C.并发和共享
D.虚拟和不确定
2.引入多道稈序技术的前提条件Z—是系统具有（）o
公务员录用体检表模板
A.分时功能
C.多CPU技术
3.操作系统是根据（
A.进程的基木状态
C.进程的优先级
B.中断功能
D. SPOOLing 技术
）来对并发执行的进程进行控制和管理的。
B.进程调度算法
D.进程控制块
4 •在段页式存储管理系统中，地址映射表是（）
A.每个进程一张段表，一张页表。
B.每个进程一张段表，每个段一张页表。
c.每个进程的每个段-•张段表，一•张页表。
D.每个进稈的每个段一张段表，多张页表。
5. 为使虚拟存储管理系统具有良好的性能，应用程序应具备的特征是（）<>
A.程序模块化程度高，由许多小模块纽成
B.程序应具备良好的局部性特征
C.稈序的I/O操作较少
D.程序实际大小应小于实际物理内存容量
6.（    ）的慕木含义是指应用程序独立于具体便用的物理设备
A.设备独立性    B.设备共享性
C.可扩展性    D.    SPOOLing li术
7. 从用户的角度看，文件系统主要是实现（    ）
A.数据存储    B.数据保护
C.数据共享    D.按名存取
三、    分析计算题（30分）
】•某操作系统的文件系统采用混合索引分配方式，索引节点中包含文件的物理结构数组 iaddr[10]o其中前7项iaddr[0]~iaddr[6]为直接地址,讪毗7卜iaddr⑹为一次间接地址， iaddr[9]为一次间接地址。系统盘块的大小为4KB,磁盘的每个扇区大小也为4KB。描述 磁盘块的数据项需要4个字节，JC中1个字节标示磁盘分区，3个字节标示物埋块。请冋 答一下问题：
（1）    该文件系统支持的单个文件的最大程度是多少？（8分〉
（2）    若某文件A的索引节点信息已位于内存，但其它信息均在磁盘。现在需要访问文件 A中第i个字节的数据，列举出所有可能的磁盘访问次数，并说明原因。（6分）
2.3个进程卩0、Pl、P2互斥使用一个仅包含[个单元的缓冲区。P0陕西省高考成绩查询时间每次用produce（）生成1 个止整数，并用put（）送入缓冲区。对于缓冲区中的每个数据，P1用考研计算机真题gctl（）®（出一次并用 compute 1（）计算其平方值，P2用gei2（）取出一次并用compute2（）计算其立方值。请用信号 量机制实现进程P0、Pl、P2之间的同步口互斥关系，并说明所定义信号量的含义，要求 用伪代码描述。（16分）
四、    简答题（21分）
1.在存储器管理中，什么是重定位？为什么要引入重定位技术？（5分）
2.在分页存储管理系统中，页表的主要作用是什么？现代大多数计算机系统都支持非常 大的逻辑地址空间（2池〜2^）,这给页表设计带來了什么样的新问题，应如何解决。（5 分）
3.以从I/O设备读入数据为例，诸用流程图方式说明程序I/O、DMA传输控制的处理过 程。（6分）
4.在哲学家就餐问题中,如果将先童起左边筷子的哲学家成为左撇子,而将先拿起右边 筷了的哲学家称为右撇了。在同时仔在左撇了和右撇了•的前提下，我们安排哲学家随 意就座。请问是否可能产生死锁，为什么？ （5分〉
《数据结构》
一、    填空题（共10分，每空1分）
1.一个“好”的算法应考虑达到以下日标：正确性、可读性、健壮性、    0
2.广义表（（），（a）, （b, （c, d）, f））的深度是    。
3.遍历二叉树实质上是对一个非线性结构进行    操作。
4.对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法复杂度
是    O
5.若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有    棵树。
6.求图的最小生成树有两种算法，    算法适合于求边稀疏的图的最小生成树。
7.最短路径迪杰斯特拉（Dijkstra）算法的复杂度    。
& 二义树上有一个结点的平衡因子的绝对值大于    ,则该二叉树就是不平衡的。
9.哈希表的地址区间为0-8,哈希函数为H （K） =K mod 9。采用线性探测法处理冲突，并
将关键字序列（12,21,43, 5, 39）依次存储到哈希表中，则元素39存放在哈希表中的地 址是    o
10.    排序算法不需要进行记录关键字间的比较。
二、    单选题（共20分，每题2分）
1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采 用（）存储方式最节省运算时间。
A.单链表 B.仅有头指针的单循环链表
C.双链表 D.仅有尾指针的单循环链表
2.下述哪一条是链式存储结构的优点？（    ）
A.存储密度大    B.插入、删除运算方便
C.存储单元连续D.随机存取第i个元素方便
3.一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是（    ）。
A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 14 5 D. 1 5 4 3 2
4.最大容量为n的循环队列，队尾指针是rear,队头绘front,则队满的条件是（    ）。
A. （rear+1） MOD n=front    B. rear-front
C. rear+l=front    【）.（rear-1） MOI） n=front
5.若一棵二叉树具有20个度为2的结点，10个度为1的结点，则度为0的结点个数是（）
A. 10    B. 11    C. 21    D. 30
6.一义树的第i层上最多有（    ）结点。
A. i    B. 2i_,-l    C. 2-1    D. 2_
7.-棵非空的二义树的先序遍历序列与后序遍历序列正好相反，则该二义树一定是（    ）
A.完全二义树B.只有一个节点C.高度等于其节点数D.二叉排序树
& 对图进行广度优先搜索遍历类似于一叉树的（）算法。
A.先序遍历    中序遍历C.后序遍历D.层次遍历
10.有一组数据(43,21,52,60,12,15)利用快速排序,以第一个元素为基准得到一次划分结 果为(    )0
A. (15,21,12,43, 52, 60)    B. (15,12,21,43,52, 60)
C.    (12, 15,21,43, 60, 52)    D. (15,21,12,43, 60, 52)
3.简答题（30分，每题6分）
1.画出算术表达式（a+b）*（c-d） - （e/f+g）转换的二叉树。
2.若通信系统中只可能出现5种字符A、B、C、D和E,其概率分别为0.12、0.15、0.19、
0.21和0.33,    （1）试设计赫夫曼编码；（2）画岀相应的赫夫曼树。
3.给出下图G的（1）邻接表表示图：（2）并根据画出的邻接表，以顶点1为根，画出深
度优先生成树。
4.输入一个正整数序列（45,14,11,52,63,3乙56,24）, （1）按此次序构造一颗二叉排序树：（2） 如果删除52, ifflj出删除后的二义树结构。
5.堆排序的基木思想是什么？其优点是什么？
四、算法题（招50岁左右宿舍管理员15分，共2题）
1.设计一个算法，逆序单链表中的数据。（5分）
2.采用一义链表的“储结构，分别每出统计一义树的叶了结点个数和树岛的函数，并分别 分析时间复杂度。（10分）