您现在的位置:小学生自学网>> 信息>> 学习电脑

软件基础练习题

作者: 来源: 发布时间:2011年04月01日 点击数:
 

软件基础


操作系统部分(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分)
以下是高级通讯原语SENDRECEIVE不完整的框图。请填充以适当的PV操作,并说明所用信号量的意义和初值。
SEND
                        RECEIVE
       
                       
       
申请一消息区                     3
       
                       
       
消息送消息区                     4
       
                       
       
1                         从消息链上摘下一消息
       
                       
       
消息区挂入消息链                     5
       
                       
       
2                         消息送接收区
       
                       
       V
S2                         释放消息区
       
                       


语言与编译部分(35分)
一、(7分)
把下面不确定的有限自动机化为确定的有限自动机。
图(9410.bmp

二(8分)
有文法 S—〉(L| a
L—
LS | S
给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义),它输出配对括号的个数,如对于句子
a,(aa)),输出是2

三、(15分)
为语言{a^(m)b^(m)|n>m>=0}写三个文法,它们分别是二义文法,LR1)文法和非LR1)且非二义的文法。不必证明所写
文法的正确性,但每个文法的产生式不能超过4个。

四、(5分)
右边是一个FORTRAN 77程序,按语言的语义 CALL SUB
程序的输出结果是什么?在静态存储分配情 CALL SUB
况下,实际的输出结果是什么?两者是否有 END
区别?说明理由。 SUBROUTINE SUB
DATA I/10/
WRITE
** I
I=100
END


程序设计与数据结构部分(35分)
一、(8分)
下面的程序段是合并两条链(FG)为一条链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,打印出集合{01n-1}的所有子集。例如,输出为3时,输出是
{ }
{0}
{1}
{0
1}
{2}
{0
2}
12}
{0
12}

 

计算机原理


一、填空题:(每空1分,共18分)
1
、软件与硬件在-----上可以是等级的,在-----上是不等级的。
2
-----是指虚拟机的指令系统由宿主机的-----解释,而-----则是指目标机的指令系统由宿主机的-----解释。
3
、对于动态MOS存储器,采用-----刷新方式的优点是-----,其缺点是-----
4
、对于一种磁表面记录方式,影响记录密度的主要因素有:(1--------;(2--------和(3--------
5
、紧密耦合多机系统是通过共享-----来实现机间通信的。
6
、在多级存储体系中,虚拟存储器的作用是-----Cache的主要作用是-----
7
、某一个模32多体存储采用低位交*编址,总容量为512kb,按字节寻址,则地址113610进制)的体地址是-----
8
、有16个处理机,编号为015,采用单级互连网联结。当互连函数为PM2-3时,编号为7的处理器应与编号为---的处理器连接。
9
、适于高速数组运算的计算机系统结构主要有---------------
10
、微指令格式的基本类型为----------


二、选择题(每个选择1分,共12分)
1
、异构型多处理机系统的分工方式是:
1)任务分布    2)功能分布
3)功能和任务分布(4)各种资源分布
2
、某台微机显示器的字符显示窗口为8*14点阵,图形方式的分辨率为640*35016种颜色,其显示控制版应为:
1EGA 2VGA 3CGA 4MDA
3
、设要存储一个8*8的矩阵,每个矩阵元素占一个存储字单元,要求能同时访问矩阵的一行、一列或对角线的所有元素,若采用多体交*存储结构,则主存的存储体个数应取:
17 28 39 411
4
RISC为支持过程调用和返回所采用的技术为:
1)重叠寄存器窗口 2CALL/RETURN指令
3)专用硬件堆栈 4)低层次例行程序
5
、设某机共有7条指令,使用频度分别为30%20%20%10%10%5%5%,采用哈夫曼编码时平均操作码码长是:
13.0 22.9 32.6 42.5
6
、流水线控制方式下,下列那种情况是全局性相关:
1)指令相关 2)先写后读相关
3)先读后写相关(4)写写相关
7
、指令复执属于下列那种冗余技术
1)硬件静态冗于 2)动态冗余
3信息冗余 4)时间冗余
8
、具有一个控制部件和多个处理单元的多处理机系统属于下列那种结构?
1SISD 2SIMD 3MISD 4MIMD
9
、核心程序通常用于衡量:
1ALU的性能 2I/O系统的性能(3)主机的性能 4)系统综合性能
10
、向量处理机同标量流水处理机的主要区别在于向量机
1)采用先行控制 2)具有向量数据类型
3)规模更大 4)具有更多通用寄存器
11
CRAY-1对向量处理方式是
1)全并行 2)纵向加工
3)横向加工 4)纵横加工
12
、采用组相连映象的主存,组内页数为8,用单级比较对法实现LRU算法,所需触发器的个数为
18 216 328 456

三、分析计算题:
1
、用流程图形式表示中断的全过程。(10分)
2
、用下图所示的同步可预置16进制计数器和与非门构造一个255分频器。
10分)


3
、根据反码的定义和有模运算原理说明为什么在反码运算中需要循环进位?
6分)
4
Intel8086 是分段访问存储器的,试回答:
18086有那几种存储段,各自的主要用途如何?
2)某存储单元的段基址为348AH,偏置(位移址)为4214H,该单元的物理地
址是多少?
5
CPU的结构可以设计成单总线、双总线、或三总线的。试画出一个由输入总线
、寄存器总线和CPU输出总线构成的三总线CPU的数据通路结构框图,并标明
CPU
IRMARMDR的连接。要求该CPU含有一个ALU、二个多路器、一个移
位器、一组状态器和一组通用寄存器。(12分)
6
、设下图所示的浮点乘法流水线的乘积可直接返回输入断或暂存于相应缓冲寄存
器中。现欲在最短时间内计算E=A*B*C*D ,试完成
1)画出计算E的时空图,计算出该流水线的吞吐率和效率;
2)进一步提高该流水线的吞吐率可采用什么措施?画出采用该措施后计算E
时空图,并计算吞吐率和效率
12分)(图9431.bmp
7
、某字节多路通道连接六台外设D0D1D2D3D4D5,其数据传输率分
别为1005040252010kb/s,该通道的工作周期为4μs,试问:
1)该通道的速率能否满足这六台外设传输数据的需求?why
2)若速率越大的外设其请求相应的优先级越高,当这六台外设同时发出请求时
,需要多长时间才能处理完D3的第一次请求?

部分参考答案
一、
1
、功能,效率
2
、模拟,指令系统,仿真,微程序
3
、分散,没有死区,降低了存储器的访问速度
4
、是否有退磁区(空隙),读出是否有多余的信号,是否有自同步能力
5
、内存
6
、增加容量,提高速度
7
16
8
15
9
、向量处理机,阵列处理机
10
、垂直型微指令,水平型微指令

二、214131423243

程序设计  


一、下面关于程序设计风格的叙述,那些是正确的?那些是错误的?(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分)设图GN个顶点,G的邻接矩阵A定义为:
A[I
J]= 1 // 如果存在IJ的边
0 //
否则
G
的传递闭色矩阵A+定义为
A+[I
J]=1 // 如果存在IJ的路径
0 //
否则
1 I J N
本算法框图的功能是求A的传递闭色A+,试填充[1]~[5]使之成为完整的算法。
图中PATHA均为N*N的布尔矩阵。
答案:[1]__________________ [2]________________ [3]__________________ [4]________________ [5]__________________

五、阅读如下子程序,回答下列问题:(10分)
1
、当数组B的值为(1111223333344,)时,此子程序的输出结果是什么?
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的,其平方为回文的数。
回文是指字符串两半的字符左右对称,例如1221214224等均是回文。
程序:
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]________________

七、编写一个子程序,对于给定的正整数NMNM),打印出所有满足条件I1+I2+…+IN = M的正整数序列
I1
I2…IN,其中I1I2…IN。例如N=4M=8时,打印结果如下: 10分)
5 1 1 1
4 2 1 1
3 3 1 1
3 2 2 1
2 2 2 2

八、设二*树用二*链表表示,试写一算法输出其嵌套括号表示。例如下面图示的二*树,其输出形式为AB(,D),C 15分)

 

 

 

中科院计算技术研究所1995年硕士生入学试题 程序设计


.选择
1.
一棵深度为6的平衡二*,其每个非终端结点的平衡因子均为1,则该树共有__个终端结点.(2)
a.14
b.16
c.18
d.20
e.22
f.24

2.一个有18条边的非连通无向图,至少应有__个结点.(2)
a.6
b.7
c.8
d.9
e.10
f.11

3.一棵124个叶结点的完全二*,最多有__个结点.
a.247
b.248
c.249
d.250
e.251(2
)

4.按锦标赛排序的方法,决定出8位运动员之间的名次顺序排列,至少需编排__场次的比赛.(考虑最坏)
a.13
b.14
c.15
d.16
e.17
(2
)

5.已知Head(Tail([Head(S),Head(Tail(Tail(S))]))广义表满足上式,S___.
a.[[a,b],b,a]
b.[[b,a],[a],[b]]
c.[[a],[a,b],[b]]
d.[b,[a],[a,b]]
e.[[a],[b],[b,a]]
f.[[b],[b,a],[a]]
(
其中,方括号表示广义表,圆括号表示函数,Head()表示取广义表的头部)(2)

6.在下列三种次序的线索二*树中,___对查找指定结点在该次序下的后继效果较差.(2)
a.
前序线索树 b.中序线索树 c.后序线索树

7.由二*树的前序和后序遍历序列___唯一地确定这棵二*.(2)
a.
b. 不能

8.在下列两种求图的最小生成树的算法中,__算法最适合于求边稀疏的网的最小生成树(2)
a.Prim b.Kruskal

9.下列无向图的存储结构中,在对无向图的边进行操作时,(如删除一条边)___存储结构更为适合.
a.
邻接表
b.
邻接多重表.

10.在下述几种树当中,__可以表示静态查找表.
a.
次优查找树;
b.
*排序树;
c.B-

d.
平衡二*

11
(1).
在文件局部有序或文件长度较小的情况下,最优内部排序的方法是_A__.
(2).
快速排序在最坏的情况下,时间复杂度是_B__,_C__的性能差;
(3)
就平均时间而言,_D__最佳.
A.: (1)
直接插入排序 (2)起泡排序 (3)简单选择排序;
B.: (1)O(nlog(n)) (2)O(n^2) 3.O(n^3)
C.: (1)
堆排序 (2)起泡排序 (3)选择排序.
D.:(1)
堆排序 (2)快速排序 (3) 归并排序.

12.一程序规定的职能是"输入三个整数作为三边的边长构成三角形,判别是等腰三角形,等边三角形,或是一般三角形.再做计算..."若用等价类划分方法对该程序作功能测试,至少应对该程序的输入数据考虑_A_个等价类,其中包括_B_个有效等价类和_C_个无效等价类.
A.___B.___C.___
(1)3; (2)5; (3)7; (4)12; (5)15; (6) 18; (7)21; (8)25; (9)33; (10)40;

13.设二*树如图所示:

1.
给出先序遍历的结点,访问顺序________.
2.
给出中序遍历的结点,访问顺序________.
3.
给出后序遍历的结点,访问顺序________.
4.
若用二*链表作为存储结构,将出现多少个空指针域?__
(
共四分)

14.下列函数
function calc(x,y :integer): integer;
begin
if y=1 then calc:=x
else calc:=calc(x,y-1)+x
end;
a,b
均为正整数, calc(a,b)=___.
(1).a*(b-1)
(2).a*b
(3)a+b
(4)a+a

15.程序段
read(a,b);
c:=3.0*a+b;
if c=0 then a:=1
else a:=1.0+1.0/c+1.0/b;
保证该程序段运行不出错的必要条件是:___
(1).b>0;
(2).a>0 and b>0;
(3).b!=0;
(4).b!=0 and c!=0;

.程序改错与填空:
1.
指出下列程序段中的错误位置,对错误编号说明理由:
程序段1:(8)
Label 1:
const max=50;
type day={Mon,Tue,Wed,Thu,Fri,Sat,Sun};
var date:day;
N:integer;
begin
a: N:=N-ord('0');
b: for date:=Mon to Sun do
N:=ord(succ(date))-1
c
: for n:=1 to 10 do
begin
......
1:
语句;
end;
......
goto 1;
......
end.
:__________________________.

程序段二.(8)
Program type(input,output);
var R:real;
Procedure print(var x:integer,y:real);
var z:real;
Procedure sum(x:integer; y:real);
var k:real;
begin
z:=x+y;
   k:=3*z;
x:=x+y;
end;{sum}
begin
sum(x,y);
writeln(x,y,z,k);
end;{print}
begin
readln(R);
print(15,R);
print(R,R)
end.{main progam}

2.阅读下列程序,填空使之成为一个完整的程序:
该程序输出N个元素的全排列.
程序:
program pic(input,output);
const n=10;
var A:array[1..n] of integer;
i,k:integer;
procedure output1;
begin
for i:=1 to n do
write(A[i]:3);
writeln;
end{output1}
procedure permute(k:integer);
var i,t:integer;
begin
if k=1 then output1
else begin
________;
for i:=1 to ___do
begin
T:=A[k];
A[k]:=A[i];
       A[i]:=T;
       ____________;
       T:=_________;
       ____________;
end;
end;
end;{permute}
begin
K:=n;
for i:=1 to k do A[i]:=i;
permute(k);
end.


.编程题:(语言任选)
1.(15
)编写程序将一个循环队列的内容倒置,该循环队列存储在一个数组A[1..n]
,例如图a中为倒置前的队列,b中为倒置后的队列.要求倒置后的队列从数组的第一个元素开始,整个程序的运行时间为O(n).

2.设计一个程序,使输入的句子按如下方式改造后输出:
(1).
单词之间只留一个空格作间隔;
(2).
句子结束后必须紧跟句号;
(3).
如果把句子的单词从左到右依次编号为1,2,3...,则对于第奇数个单词,只要直接复制就行了,而对于第偶数个单词,应按反序打印.