电子科技大学
2010年春季软件工程硕士研究生入学试题
考试科目：302软件基础
注意：所有答案必须写在答题纸上，做在试卷或草稿纸上无效
《操作系统》部分
一、选择题（共10分，每小题1分）
1. 在循环首次适应算法中，空闲区按（ ）顺序链成空闲区链。
A、 空闲区大小递增 B、空闲区大小递减
C、 空闲区地址大小递增 D、空闲区地址大小递减
2. 建立多级目录的目的是（ ）
A、便于文件的保护 B、便于关闭文件
C、解决文件的重名与共享 D、便于提高系统的效率
3. 下列的进程状态转换中，( )转换是不可能发生的。
A、运行— 就绪 B、运行一等待
C、等待—运行 D、等待一就绪
4.很好地解决了“零头”问题的存储管理方法是（ ）。
A、段式存储管理 B、页式存储管理
C、可变式分区管理 D、多重分区管理
5. 从理论上，计算机系统的虚拟存储空间的大小是由（ ）确定的。
A、 计算机地址结构
B、 硬盘容量
C、 内存容量
D、内存和硬盘容量之和；
6. 某页式管理系统中，地址寄存器的低10位表示页内地址，则页面大小为（ ）
A、1024字节 B、2048K C、512字节 D、512K
7. 在各种进程调度算法中，若所有进程同时到达，则平均等待时间最短的是（ ）
A、FIFS B、最高响应比高者优先 C、短进程优先 D、高优先级
8. 系统产生“抖动”现象的主要原因是由（ ）引起的 。
A、 交换的信息量过大
B、 频繁的缺页中断
C、 内存容量不足
D、请求页式管理方案
9. 下列叙述中正确的是（ ）。
A、在索引顺序文件的最后添加新的记录时，必须复制整个文件。
B、多级目录结构中，对文件的访问是通过路径名和用户目录名来进行的。
C、索引顺序文件既能够顺序访问，又能够随机访问。
D、索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。
10. 在多道程序系统中，处理机的分配由（ ）完成。
A、 进程调度 B、作业调度
C、P．V操作 D、设备分配程序
二、判断正误题，正确者打√，错误者打×，并改正错误（共10分，每小题1分）
1.进程执行唤醒原语以后，该进程由就绪状态转入执行状态。 （ ）
2. 虚拟段式存储管理中，若逻辑地址的段内地址大于段表中该段的段长，则发生地址越界中断。（ ）
3. 从物理概念上讲，信号量值大于零表示阻塞进程数，小于零的绝对值表示可用资源数。 （ ）
4. 一个物理硬盘可以分成多个逻辑硬盘分区进行面向用户文件系统的管理。 ( )
5..磁盘是共享设备，所以允许多个进程同时在存储空间中进行访问。 （ ）
6. P操作和V操作都是进程模块，所以必须成对出现。 （ ）
7.作业由后备状态转变为运行状态是由进程调度程序完成的。 （ ）
8. 文件的逻辑结构是指文件在存储空间的分配方式。 （ ）
9. 实现虚拟存贮技术主要的硬件支持是DMA技术及大容量的辅存如硬盘。 （ ）
10. 系统调用是操作系统和用户进程的接口，库函数也是操作系统和用户的接口。 ( )
三、简答题（共20分，每小题10分）
1. 虚拟存储器的基本特征是什么?画出请求分页系统的页表结构,并说明哪些字段与缺页中断有关?哪些字段与页面置换算法有关?有何关系?
2. 什么动态重定位？举例说明动态重定位的应用。
四、（10分）下面是生产者与消费者进程的算法描述，请分析生产者进程与消费者进程中，两个P操作和两个V操作是否可以交换？为什么？
Var mutex，empty，full：semaphore :=1, n , 0；
buffer：array [0 . .n-1] of message;
in, out : integer:= 0, 0；
Begin
parbegin
Producer： consumer：
begin begin
repeat repeat
buffer(in):=m; m:=buffer(out);
in:=(in+1) mod n; out:=(out+1) mod n;
until false until false
end; end;
parend
End
《数据结构》部分
五、 单项选择题（共20分，每小题2分）
1. 链表不具备的特点是（ ）。
A、可随机访问任一元素； B、插入删除不需要移动元素；
C、不必事先预分存储空间； D、所需空间与线性表长度成正比；
2 若线性表最常用的操作是在最后一个元素之后插入一个结点和删除最后一个结点，则采用（ ）存储方式节省时间。
A、单链表； B、双向链表；
C、单循环链表； D、带头结点的双循环链表；
3. 设无向图G有n个顶点m条边，则其邻接表中表结点数是（ ）
A、n B、2n C、m D、2m
4. 设满二叉树的深度为k，现采用顺序表示法存储该满二叉树，每个结点占L个存储单元，则共占（ ）个单元。
A、k B、2 k*L C、（2 k -1）*L D、（2 k +1）*L
5. 广义表A=((x,(a,b)),(x,(a,b),y)),则运算head(head(tail(A)))为( ).
A、x B、(( )) C、空表 D、(a)
6. 已知二叉树中叶结点数为50，仅有一个孩子的结点数为30，则总结点数为（ ）
A、81； B、129； C、110； D、130；
7. 若表R再排序前已经按关键字值递增排列，则（ ）算法的比较次数最少。
A、直接插入排序；B、快速排序； C、归并排序； D、选择排序；
8. 对二叉排序树得到的关键字升序序列的遍历是（ ）
A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历
9. 在有向图的邻接表中，顶点Vi在表结点中出现的次数是顶点Vi的（ ）。
A、度 B、入度 C、出度 D、依附于顶点Vi的弧数
10. 如图所示，C节点的度为（ ），树的度为（ ）。
A、1 B、 2 C、3 D、4
六、 简答题（共15分，每小题5分）
1. 说明线性表的顺序结构和链式结构各自的优缺点。
2. 简述数据结构中树和二叉树有什么不同。
3. 有ABC三个元素，已知它们的入栈顺序为ABC，现给定栈空间为只能存放两个元素，利用此栈，写出可能的调度出栈序列？
七、 (15分）对于如图所示的二叉树，写出分别按先序、中序、后序遍历的次序。
