软件基础
操作系统部分（30分）
一、填充（每空一分，共14分）
1、采用单级文件目录的主要缺点是存在_______________问题。
2、在单道程序运行环境下，常用的作业调度算法有__________、__________、和__________。
3、特权指令是只能由_________________使用的指令。
4、存储器的保护机制（硬件）有___________保护和_________保护。
5、预防死锁中的预先分配法和标准（有序）分配法，它们分别破坏了产生死锁必要条件中的_____________条件和_____________条件。 6、在段式虚拟存储管理中，段表设置“改变位”的目的是为了___________________________________。
7、进程有三种基本状态，即[1]______________状态，[2]___________状态，[3]___________状态。当进程又[1]演变为[2]或[3]时，就会引起__________。 二、判断。（每题1分，共5分） 1、（ ）有了动态重定位机构，作业地址空间的代码就可以原封不变的装入到给定的内存中。
2、（ ）任一时刻，若有执行状态的进程，就一定有就绪状态的进程。 3、（ ）文件系统中，设置OPEN操作的目的是为了将文件复制到内存中。 4、（ ）临界段是不可中断的程序。
5、（ ）作业的提交状态进入后备状态的过程是由作业调度程序完成的。 三、（5分）
分页式存储管理与分段式存储管理的主要区别是什么？ 四、（6分）
以下是高级通讯原语SEND和RECEIVE不完整的框图。请填充以适当的P、V操作，并说明所用信号量的意义和初值。
SEND： RECEIVE： ↓ ↓
申请一消息区 （3） ↓ ↓
消息送消息区 （4） ↓ ↓
（1） 从消息链上摘下一消息 ↓ ↓
消息区挂入消息链 （5） ↓ ↓
（2） 消息送接收区 ↓ ↓
V（S2） 释放消息区 ↓ ↓
语言与编译部分（35分） 一、（7分）
把下面不确定的有限自动机化为确定的有限自动机。 图（9410.bmp） 二（8分）
有文法 S—〉（L）| a L—〉L，S | S
给此文法配上语义动作子程序（或者说为此文法写一个语法制导定义），它输出配对括号的个数，如对于句子 （a，（a，a）），输出是2。 三、（15分）
为语言{a^(m)b^(m)|n>m>=0}写三个文法，它们分别是二义文法，LR（1）文法和非LR（1）且非二义的文法。不必证明所写
文法的正确性，但每个文法的产生式不能超过4个。 四、（5分）
右边是一个FORTRAN 77程序，按语言的语义 CALL SUB 程序的输出结果是什么？在静态存储分配情 CALL SUB 况下，实际的输出结果是什么？两者是否有 END 区别？说明理由。 SUBROUTINE SUB DATA I/10/
WRITE（*，*） I I=100 END
程序设计与数据结构部分（35分）
一、（8分）
下面的程序段是合并两条链（F和G）为一条链F的过程。作为参数的两条链都是按结点上NUMBER值的由大到小链接。
合并后新链仍按此方式链接。请填写下述空框，使程序正确工作。 type pointer= ^ node;
node =record number:integer; next :pointer end;
procedure combine(var f:pointer; g:pointer); var h,p : pointer;
begin new(h); h^. next :nil; p:=h;
while (f<> nil) and (g<> nil) do if f^. number >=g^.number then begin
p^.next:=__A__; P:=__B___; __C__ end
else begin
p^. next:=__D____; P:=___E___; ____F__
end;
if f=nil then __G__; if g=nil then __H__; f:=h^.next ; dispose(h) end;
二、（12分）
如果一个数列中的某一段（至少有两个元素）的各元素值均相同，则称之为等值数列段。等值数列段中元素的个数 叫做等值数列段的长度。
现有由N个元素组成的整数数列A，编一程序求A中长度最大的所有等值数列段的始末位置，如果没有等值数列段，则 输出特殊标志。 三、（15分）
编一个程序，对输出的任意正整数N，打印出集合{0，1，„，n-1}的所有子集。例如，输出为3时，输出是 { } {0} {1} {0，1} {2} {0，2} {1，2} {0，1，2}
程序设计
一、下面关于程序设计风格的叙述，那些是正确的？那些是错误的？（10分） 1、编写程序是，应使用括号以改善表达式的清晰度。 2、应当尽可能对程序代码进行优化。
3、在程序设计中，不要进行浮点数相等的比较。 4、应尽可能多的输出中间结果。
5、不要使用数据类型来对数据值进行防范。
6、要用计数方法而不是用文件结束符来控制输入的结束。 7、使用有意义的标识符。
8、结构化程序设计语言中没有GOTO语句。
9、一般而言，语言的级别越高，用它编出的程序越短。 10、PASCAL是一种自由格式的弱类型语言。 二、填空：（10分）
1、FORTRAN程序中，变量的作用域以______为单位，PASCAL程序的作用域遵守_____规则。
2、赋值语句A：=A+1左边的A代表_________ 含义，右边的A代表_________含义。
3、高级程序设计语言的语句分为_________ 和____________ 二种。
4、在查找算法中，顺序查找的平均查找长度ASL为________；折半查找的ASL为___________；而二叉排存树查找记录时，最坏下的情况ASL为__________；在二叉平衡排存树上插入一个结点后,最坏情况需要_______次旋转才能保持平衡。
三、选择填空：（10分）
1、存贮稀疏图的数据结构常有的是 。
[1]邻接矩阵 [2]三元组 [3]邻接表 [4]十字链表
2、内部排序多个关键字的文件，最坏情况下最快的排列方法是_____,相应的时间复杂度为______,该算法是的稳定性__________.
[1]快速排序 [2]插入排序 [3]归并排序 [4]简单选择排序 [5]O(nlog2(n)) [6]O(n^2) [7]O(n^2log2(n)) [8]O(n) [9]稳定 [10]不稳定 3、倒排文件包含若干个倒排表，倒排表的内容是_____________. [1]一个关键字值和关键字的记录地址； [2]一个属性值和该属性的一个记录地址； [3]一个属性值和该属性的全部属性地址；
[4]多个关键字值和它们对应的某个记录的地址。
4、设T为哈夫曼最优树，具有5个叶结点，树T的高度最高可以是__________. [1] 1，[2] 2，[3] 3，[4] 4，[5] 5，[6] 6
5、对正确的AOE网络图而言，必须是____,AOE中某边权值应当是_____,权值为0的边则表示______.
[A]，[1]完全图；[2]哈密顿图；[3]无环图；[4]强连通图 [B]，[1]实数；[2]正整数；[3]正数；[4]非负数
[C]，[1]为决策而增加的活动；[2]为计算方便而增加的活动；[3]表示活动间的时间顺序关系；[4]该活动为关键活动。
6、假定有K个关键字互为同义词，若用线性探测法把这K个关键字插入表中，至少需要____次探测。
[1]K-1 [2]K [3]K+1 [4]K（K+1）/2
四、（10分）设图G有N个顶点，G的邻接矩阵A定义为： A[I，J]= 1 // 如果存在I到J的边 0 //否则
G的传递闭色矩阵A+定义为
A+[I，J]=1 // 如果存在I到J的路径 0 // 否则
（1〈 I， J〈 N）
本算法框图的功能是求A的传递闭色A+，试填充[1]~[5]使之成为完整的算法。 图中PATH和A均为N*N的布尔矩阵。
答案：[1]__________________ [2]________________ [3]__________________ [4]________________ [5]__________________
五、阅读如下子程序，回答下列问题：（10分）
1、当数组B的值为（1，1，1，1，2，2，3，3，3，3，3，4，4，）时，此子程序的输出结果是什么？
2、次子程序的功能是什么？ „„
type m=array[0..n] of integer; procedure count (b:m);
var i,l : integer; begin
i:=1; l:=1;
while (i<=n) do begin
if (b[i]=b[i-l]) then l:=l+1; i:=i+1; end
write (l) end;
六、阅读如下程序，并填充[A]~[E]，使之成为一个完整的程序。（10分） 本程序输入一个给定的正整数N，打印出所有不超过N的，其平方为回文的数。 回文是指字符串两半的字符左右对称，例如1，22，121，4224等均是回文。 程序：
program palindrome(input,output); const max=1000;
var n,m,i,j,s:integer;
d: array [1..max] of integer; begin read(n);
for m:=1 to n do begin
______A________ j:=0;
while ____B______ do begin j:=j+1;
d[j]:= s mod 10; ______C_________ end; i:=1;
while (d[i]=d[j] and ______D______ do begin
i:=i+1; j:=j-1; end;
if ____E____ then write (m) end end.
答案：[A]________________ [B]__________________ [C]________________ [D]__________________ [E]________________
七、编写一个子程序，对于给定的正整数N和M（N〈M），打印出所有满足条件I1+I2+„+IN = M的正整数序列
I1，I2，„IN，其中I1〉I2〉„IN。例如N=4，M=8时，打印结果如下： （10分）
5 1 1 1 4 2 1 1 3 3 1 1 3 2 2 1 2 2 2 2
八、设二叉树用二叉链表表示，试写一算法输出其嵌套括号表示。例如下面图示的二叉树，其输出形式为A（B（，D），C） （15分）
计算机原理
一、填空题：（每空1分，共18分）
1、软件与硬件在_____上可以是等级的，在_____上是不等级的。 2、_____是指虚拟机的指令系统由宿主机的_____解释，而_____则是指目标机的指令系统由宿主机的_____解释。
3、对于动态MOS存储器，采用_____刷新方式的优点是_____，其缺点是_____。 4、对于一种磁表面记录方式，影响记录密度的主要因素有：（1）________；（2）________和（3）________。
5、紧密耦合多机系统是通过共享_____来实现机间通信的。 6、在多级存储体系中，虚拟存储器的作用是_____，Cache的主要作用是_____。
7、某一个模32多体存储采用低位交*编址，总容量为512kb，按字节寻址，则 地址1136（10进制）的体地址是_____。
8、有16个处理机，编号为0至15，采用单级互连网联结。当互连函数为PM2-3时，编号为7的处理器应与编号为---的处理器连接。
9、适于高速数组运算的计算机系统结构主要有_____、_____和_____。 10、微指令格式的基本类型为_____和_____。
二、选择题（每个选择1分，共12分） 1、异构型多处理机系统的分工方式是：
（1）任务分布 （2）功能分布 （3）功能和任务分布 （4）各种资源分布 2、某台微机显示器的字符显示窗口为8*14点阵，图形方式的分辨率为640*350，16种颜色，其显示控制版应为：
（1）EGA （2）VGA （3）CGA （4）MDA
3、设要存储一个8*8的矩阵，每个矩阵元素占一个存储字单元，要求能同时访问矩阵的一行、一列或对角线的所有元素，若采用多体交叉存储结构，则主存的存储体个数应取：
（1）7 （2）8 （3）9 （4）11
4、RISC为支持过程调用和返回所采用的技术为：
1.重叠寄存器窗口 2.CALL/RETURN指令3.专用硬件堆栈4.低层次例行程序 5、设某机共有7条指令，使用频度分别为30%、20%、20%、10%、10%、5%、5%，采用哈夫曼编码时平均操作码码长是： （1）3.0 （2）2.9 （3）2.6 （4）2.5
6、流水线控制方式下，下列那种情况是全局性相关：
（1）指令相关 （2）先写后读相关（3）先读后写相关（4）写—写相关
7、指令复执属于下列那种冗余技术？
（1）硬件静态冗于 （2）动态冗余（3）信息冗余 （4）时间冗余
8、具有一个控制部件和多个处理单元的多处理机系统属于下列那种结构？ （1）SISD （2）SIMD （3）MISD （4）MIMD 9、核心程序通常用于衡量：
（1）ALU的性能 （2）I/O系统的性能（3）主机的性能 （4）系统综合性能 10、向量处理机同标量流水处理机的主要区别在于向量机
（1）采用先行控制 (2)具有向量数据类型(3)规模更大(4)具有更多通用寄存器 11、CRAY-1对向量处理方式是
（1）全并行 （2）纵向加工（3）横向加工 （4）纵横加工
12、采用组相连映象的主存，组内页数为8，用单级比较对法实现LRU算法，所需触发器的个数为
（1）8 （2）16 （3）28 （4）56
三、分析计算题：
1、用流程图形式表示中断的全过程。（10分）
2、用下图所示的同步可预置16进制计数器和与非门构造一个255分频器。 （10分）
3、根据反码的定义和有模运算原理说明为什么反码运算中需要循环进位？6分 4、Intel8086 是分段访问存储器的，试回答：
（1）8086有那几种存储段，各自的主要用途如何？（2）某存储单元的段基址为348AH，偏置（位移址）为4214H，该单元的物理地址是多少？
5、CPU的结构可以设计成单总线、双总线、或三总线的。试画出一个由输入总线、寄存器总线和CPU输出总线构成的三总线CPU的数据通路结构框图，并标明 CPU与IR、MAR和MDR的连接。要求该CPU含有一个ALU、二个多路器、一个移 位器、一组状态器和一组通用寄存器。（12分）
6、设下图所示的浮点乘法流水线的乘积可直接返回输入断或暂存于相应缓冲寄存器中。现欲在最短时间内计算E=A*B*C*D ，试完成（1）画出计算E的时空图，计算出该流水线的吞吐率和效率；（2）进一步提高该流水线的吞吐率可采用什么措施？画出采用该措施后计算E的时空图，并计算吞吐率和效率（12分）（图9431.bmp）
7、某字节多路通道连接六台外设D0、D1、D2、D3、D4、D5，其数据传输率分 别为100、50、40、25、20、10kb/s，该通道的工作周期为4μs，试问： （1）该通道的速率能否满足这六台外设传输数据的需求？why？
（2）若速率越大的外设其请求相应的优先级越高，当这六台外设同时发出请求
时，需要多长时间才能处理完D3的第一次请求？
部分参考答案
一、1、功能，效率2、模拟，指令系统，仿真，微程序3、分散，没有死区，降低了存储器的访问速度4、是否有退磁区（空隙），读出是否有多余的信号，是否有自同步能力5、内存6、增加容量，提高速度7、168、15 9、向量处理机，阵列处理机10、垂直型微指令，水平型微指令 二、2、1、4、1、3、1、4、2、3、2、4、3
因篇幅问题不能全部显示，请点此查看更多更全内容