虚拟存储器的功能由（C）完成。 A、B：（1）页失效；（2）1E5C；（3）2A5C；（4）165C；（5）125C C：（1）硬件；（2）软件；（3）软硬件结合
1）在需求分析阶段，开发人员需要从用户那里获得的最重要的信息是_______。
A．用户要让软件做什么 B．用户能够接受的开发周期 C．用户能够接受的开发费用
D．用户要让软件具有各种结构
2）在度量模块独立程度时，用 衡量不同模块间互相依赖的紧密程度 。 A、耦合 B、内聚 C、信息隐藏 D、局部化
3）在度量模块独立程度时，用 衡量一个模块内部个元素彼此结合的紧密程度。
A、耦合 B、内聚 C、信息隐藏 D、局部化 4）软件开发的结构化分析(SA)方法，常用的描述软件功能需求的工具是_______。
A、系统流程图、程序编码 B、软件流程图、模块说明
C、数据流程图、数据字典 D、业务流程图、处理说明
5) 软件设计分为总体(概要)设计和详细设计两个阶段,下列哪一项是总体设计中的任务？ A) 设计软件结构 B) 制定测试计划C) 设计测试用例 D) 设计算法和数据结构
１）ER 模型可以转换成关系模型。当两个实体间联系是 M:N 联系时,它通常可转换成 个关系模式。
A.2 B.3 C.M+N D.M*N
2)三个模式之间存在下列映射关系，将正确的是 。
A．外模式/内模式 B．外模式/模式 C．模式/模式 D．内模式/外模式 3）已知三个关系：
学生（学号，姓名，性别）
课程（课程编号，课程名称，学时） 成绩（学号，课程编号，分数） 若要列出选修课程名称为“ DB ”，且分数低于 60 的学生姓名和分数，则应使用的关系代数运算有 。
A. 选择、投影、自然连接 B. 选择、投影 C. 选择、自然连接 D. 投影、自然连接
4）若关系模式R的所有候选码均为单个属性，则R最高必达到 。A．1NF B．2NF C．3NF D．4NF 5） 在数据库逻辑设计中,当将E-R图转换为关系模式时,下面的做法哪一个是不正确的?
A) 一个实体类型转换为一个关系模式 B) 一个联系类型转换为一个关系模式
C) 由实体类型转换成的关系模式的主键是该实体类型的主键
D) 由联系类型转换成的关系模式的属性是与该联系类型相关的诸实体类型的属
性的全体
第 6 页 共 10 页
6）在已知教学环境中，一名学生可以选择多门课程，一门课程可以被多名学生选择，这说明学生记录型与课程记录型之间的联系是 。 A）一对一 B）多对多 C）一对多 D）未知 三、判断
1．处理死锁的四种方法中，预防策略是不容许死锁的出现的，而其他三种方法都是容许的。为了预防死锁，系统必须至少产生死锁的四个必要条件之一不成立，例如银行家算法就是预防死锁最有代表性的一个算法。
2、文件的外存分配方式有连续分配、链接分配和索引分配；其中链接结构可以提高文件存储空间的利用率，但不适合文件的随机存取；对物理文件来说，顺序文件必须采用连续分配方式，而链接文件和索引文件可以采用离散分配方式。
3．进程处于就绪状态，是指它正等待着某个事件的发生，这时，即使给它CPU控制权，它也无法执行。
4、若无进程处于运行状态，则就绪队列和等待队列均为空。（ ） 5、银行家算法是防止死锁发生的方法之一。（ ）
6、SPOOLing系统实现设备管理的虚拟技术，即：将独占设备改造为共享设备。它由专门负责I/O的常驻内存的进程以及输入、输出井组成。（ ）
7、虚拟设备是指允许用户程序不必全部装入内存就可以使用系统中的设备。（ ） 8、对顺序文件进行检索时，首先从FCB中读出文件的第一个盘块号；而对索引文件进行检索时，应先从FCB中读出文件索引表的起始地址。（ ）
1）白盒测试时，既要考虑程序的内部逻辑结构又要考虑其外部特性。（ 错 ） 2）软件开发的主要任务是写程序。（ 错 ） 3）测试只能证明程序有错误,不能证明程序没有错误。（ 对 ） 4）软件维护就是改正软件中的错误。（ 错 ）
四、简答
1、一页式系统中，页面的大小为1KB。现有一长度为4KB的用户程序，其4个页面分别被分配在内存的10，14，15和18块中。当程序中的访问地址为2058时，其物理地址是多少？
2、采用可变分区管理存储空间时，若主存中按地址顺序依次有五个空闲区，大小分别为15K、28K、10K、226K、110K。现有五个作业J1到J5，它们所需的主存空间依次是10K、15K、102K、26K、180K。问如果采用首次适应分配算法，能否把这五个作业按J1到J5的次序全部装入主存。使用哪种分配算法装入这五个作业，可使主存的利用率最高？ 3、某采用页式存储管理的系统，接收了一个共7页的作业，作业执行时依次访问的页为：1、2、3、4、2、1、5、6、2、1、2、3、7。当内存块数量为4时，请分别用先进先出（FIFO）调度算法和最近最少使用（LRU）调度算法，计算作业执行过程中会产生多少次缺页中断？写出依次产生缺页中断后应淘汰的页。（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断。要求写出计算过程）
三、应用题（共8题，建议分数为45分）
1、设用于通信的电文由8个字母{Q、T、Z、A、S、W、E、C}组成，各字母在电文中出现的频率依次为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10，请为这8个字母设计哈夫曼编码，并画出建立的哈夫曼树（要求左节点小于右节点）。（8分）。
第 7 页 共 10 页
参考答案： 每个字母的哈夫曼编码为： 1.00 0 1 Q：1010
T：00
0.400.60 Z：10000 0 1 1 A：1001 0 S：11
0.320.280.190.21 W：10001 1 E：01 0 S T E C：1011 0.170.11
0 1 00 1 0.050.060.070.10 0 1
A Q C 0.020.03
Z W 2、定义栈的数据结构为const int maxlen=20; struct seqstack { elemtype stack[maxlen]; int top; };
其中elemtype为入栈元素的数据类型。请你分别用push和pop作为函数名写出进栈和出栈算法（7分）。
参考答案： //入栈
void push(seqstack &s, elemtype x) {
if (s.top == maxlen - 1)
cout<<\ else { s.top++; s.stack[s.top] = x; } }
//出栈
void pop(seqstack &s, elemtype &x) {
if (s.top == 0)
cout<<\ else { x = s.stack[s.top];
1 第 8 页 共 10 页
s.top--; } }
3、一个AOE网络如下，计算完成整个工程至少所需时间，求出关键路径，并计算每个事件的最早开始时间和最迟开始时间（8分）。 a4=3V5 V2 a8=1 a1=3 a3=2 a7=2V1V4 V6 a5=4参考答案：a2=2 Vl (i) 顶点 a6=3V3Ve (i) 0 0 3 2 6 6 8 4 2 6 7 8 关键路径：（V1,V3,V4,V6） 完成整个工程至少所需时间：8天
4、把下列二叉树构造成大根堆，并写出第一趟排序的结果（7分）。
46
55 13
05 17 42 94
70
参考答案：
94
70 17
05 13 46 55
42
6 第 9 页 共 10 页
第一趟排序结果：42，70，17，46，55，05，13，94
5、已知矩阵
?0 2 0 0 4??6 0 8 0 0???，现对该矩阵进行转置（下标从1开始）（8分）。 ?0 10 0 0 0????12 0 0 0 0?（1） 写出其转置前、后的三元组表 （2） 写出NUM向量内容。
（3） 写出POT向量在算法开始前的内容和算法完成后的内容。
参考答案：
（1） 转置前三元组表 转置后三元组表 1 2 2 1 2 6 1 5 4 1 4 12 2 1 6 2 1 2 2 3 8 2 3 10 3 2 10 3 2 8 4 1 12 5 1 4 （2） NUM向量
2 2 1 0 1
（3）POT向量
算法开始前POT向量 算法完成后POT向量 1
3 5 6 6 3 5 6 6 7
第 10 页 共 10 页