计算机软件技术基础复习题.doc

计算机软件技术基础复习题一、基本概念1、在操作系统中，进程是资源分配、调度和管理的最小单位。2、进程在运行过程中有3种基本状态，它们是运行态、就绪态和等待待态3、计算机系统的层次结构中，位于硬件系统之外的所有层次统称为虚拟机。4、操作系统向用户提供了3种类型界面，分别是命令界面、程序界面和图形界面。5、进程与程序的根本区别在于静态与动态的特点。6、存储器间接寻址方式指令中给出的是操作数地址所在的存储地址，CPU需要访问内存两次才能获得操作数。7、操作系统中引入多道程序设计的目的是提高设备利用率。8、引入缓冲的主要目的是改善CPU和I/O设备之间速度不匹配的情况。9、I/O通道方式的数据交换方式是存储设备与I/O设备直接交换信息而不经过CPU来完成。10、CPU输出数据的速度远远高于打印机的打印速度，可以采用缓冲技术解决这一矛盾。 11、采用页式存储管理不会产生内存碎片。12、冯诺依曼计算机工作方式的基本特点是按地址访问并顺序执行。13、计算机主频的周期是指时钟周期。 14、存储周期是指存储器进行连续读写操作所允许的最短时间间隔。 15、CPU输出数据的速度远远高于打印机的打印速度，可以采用缓冲技术解决这一矛盾。16、提供支持程序浮动的寻址方式是相对寻址。17、计算机的外围设备是指除了CPU和内存以外的其它设备。18、在主存和CPU之间增加Cache的目的是解决主存和CPU之间速度不匹配的问题。19、操作系统的功能包括处理机管理、存储管理、文件管理和设备管理，20、现在主要采用总线结构作为计算机硬件之间的连接方式。21、一般的程序设计语言的定义都涉及语法、语义和语用三个方面。其中描述如何用语言基本符号组成程序中各个语法成分的一组规则称为语法。对程序中各个语法成分含义的描述称为语义。涉及语言符号及其使用者之间关系的内容称为语用。 22、程序设计语言一般分为低级语言和高级语言两大类。其中低级语言又称为面向机器的语言。高级语言又称为通用程序语言。23、计算机软件开发技术的发展，经历了面向机器的编程、面向过程的软件开发、面向对象的软件开发和面向组件的软件开发等若干阶段。24、程序设计方法的分类，按设计技术大致可以分为：结构化程序设计方法、面向对象程序设计方法、组件化程序设计方法、分布式程序设计方法和嵌入式程序设计方法等。25、DFA的含义是确定的有穷自动机，确定的意思是指状态变迁函数的每次转向的状态是唯一的。26、乔姆斯基(Chomsky)把文法分成四种类型，其中2型文法又称为上下文无关文法，3型文法又称为正则或正规文法。27、编译方式与解释方式的根本区别在于是否生成目标代码。28、编译程序的工作一般分为以下过程：词法分析 语法分析 语义分析 中间代码生成 目标代码生成 代码优化。29、动态存储分配时，可以采用的分配方法有栈式存储分配和堆存储分配。30、在自底向上语法制导翻译中，带有语义信息的语法树随着归约动作自底向上建立起来的，在这一过程中，句柄归约和语义动作调用的关系是同时动作。31、文法的二义性和语言的二义性是两个不同的概念。32、在属性文法的翻译中，若为文法符号设置属性变量时，如果该属性的值是沿语法树自底向上给出，则为它设置综合属性。33、自顶向下的分析是以文法的开始符号为树根，采用最左推导方法，逐步地为输入符号串自上而下地构造一棵语法树。34、在属性文法的翻译中，若为文法符号设置属性变量时，如果该属性的值是沿语法树自上而下给出，则为它设置继承属性。35、一个上下文无关文法称为是LL(1)文法，当且仅当同一非终结符的各个产生式的可选集互不相交。36、路由器技术的核心内容是提高路由器性能的方法。37、典型的局域网可以看成三部分构成，网络服务器、工作站和通信设备。38、在数据传输过程中，经常要增加一位来校验数据传输的正确性，该位称为奇偶校验位。39、在网络的拓扑结构中，中心结点的故障对星型拓扑结构危害最大。40、1000 BASE-T标准，使用5类非屏蔽双绞线，双绞线长度可达到100m。41、所有IP地址都由国际组织NIC负责统一分配，其中ENIC负责欧洲地区；APNIC负责亚太地区；lnterNIC负责美国及其他地区。42、关于POP3说法是，电子邮件客户端应用程序从邮件服务器接收邮件时使用的协议。43、集线器运行在OSI的物理层和链路层。路由器运行在OSI的网络层。44、在网络的拓扑结构中，常见的有星型拓扑结构、环形拓扑结构 、树型拓扑结构和网状拓扑结构。45、因特网的域名体系代表实际物理连接。46、虚拟企业的技术平台一般采用企业内部网（Intranet）。47、从网络拓扑结构上说CSMA/CD与Token Bus是针对总线拓扑结构的局域网设计的。48、计算机网络发展的奠基石是美国的ARPANET网络。 49、关于防火墙的功能是，可以检查进出内部网络的通信量；可以使用应用网关在应用层上建立协议过滤和转发功能；可以使用过滤技术在网络层对数据包进行选择。50、建立计算机网络的主要目的是实现计算机资源的共享。二、简答题1、操作系统的概念及功能。操作系统：操作系统是系统软件，它管理计算机的资源并提高各种资源的使用效率，控制程序的正常执行，为用户提供一个友好界面，方便用户使用。操作系统的功能：实现处理机管理、存储管理、设备管理、文件管理并为用户提供使用接口。2试叙述Spooling系统的基本思想。在硬盘中开辟两个缓冲区；输入井和输出井；只要输入井中有空闲空间，就可以不断地把作业送入输入井；只要内存中有空闲空间，就可以从输入井中调若干作业进入内存运行；运行结果不是直接送输出设备，而是送入输出井；只要输出设备空闲，就可以从输出井中取出结果输出。从而实现了输入、运行与输出的并行工作。3进程的几种基本状态及其转换。进程有三种基本状态：就绪态、运行态和等待态；就绪态 因调度 运行态运行态 发生某一事件 等待态运行态 时间片到 就绪态等待态 事件已经发生 就绪态（或画图p46图3.5）4 CISC指令集结构的缺点。CISC指令集结构的缺点是：大部分指令使用频率较低，无论是硬件还是软件上都造成很大浪费。指令系统的复杂性带来了计算机体系结构的复杂，增加了成本且易产生错误。指令系统的复杂性使VLSI（大规模集成电路）的设计变得复杂。由于指令系统的复杂，使得运行速度变慢。由于指令系统的不均衡性（指令长度的种类多，指令周期不同等。），不利于采用先进技术来提高系统性能。5、简单说明RISC指令集结构的设计原则。RISC指令集结构的设计原则是：指令集中只保留使用频率高的指令和常用指令。保证指令系统的均衡性。即指令尽可能简单，最好在一个机器周期内完成，指令最好等长，或限制长度的种类。指令的操作尽可能在寄存器内完成任务。以简单有效的方式支持现代编程技术，如增加对高级语言的支持。6、解释什么是主存的访问时间、存储周期、存储器频宽、存储器带宽和存储器宽度？访问时间：主存储器从接到访问请求到信息被读到数据总线上所需的时间。存储周期：连续两次访问请求之间的最小时间间隔。存储器频宽：存储器被连续访问时，每秒钟传送信息的位数。存储器带宽：存储器每个时钟周期传送的字节数。存储器宽度：一次可以访问的字节数。7、解释什么是指令周期、机器周期（CPU周期）和时钟周期？它们之间有什么关系？指令周期：取出并执行一条指令所需的时间。包括取指、分析和执行所需的全部时间。机器周期：指令周期可划分为几个阶段，每个阶段所需的时间。通常指取指时间。时钟周期：又称节拍周期，是处理操作的最基本单位。它们之间的关系：一个指令周期包含若干个机器周期，一个机器周期包含若干时钟周期。8、某虚拟存储器的用户空间共有32个页，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号分别为5、10、4、7。试回答：写出逻辑地址和物理地址的格式；虚拟地址0A5CH对应的物理地址是多少？画图表示该虚拟地址映射到物理地址的变换过程。 逻辑：页号5位，页内10位 物理：块号4位，块内10位125CH9、一个460字的程序，其内存访问序列为10、11、104、170、73、309、185、245、246、434、458、364。假定页面大小为100个字，内存中有200个字供该程序使用。回答下列问题：给出页面访问序列（例如，此题前5个页面访问序列为0、0、1、1、0、.）；采用先进先出的页面替换算法，其缺页次数是多少？采用最近最少使用的页面替换算法，其缺页次数是多少？0、0、1、1、0、3、1、2、2、4、4、36次7次10、若某计算机数据线、地址线都是8bit，有一条相对寻址的无条件转移指令存于主存的20H单元中，指令给出的位移量D=00010101B，设该指令占用2个字节。问：取该指令时PC的内容该指令执行结束时PC的内容取该指令时PC的内容是：20H该指令执行结束时PC的内容是：(PC)+2+D=00100000+00000010+00010101=00110111B=37H11、计算机系统中总线结构的概念及优点。总线：所谓总线就是指若干信号线的集合，由这些信号线组成在两个以上部件间传送信息的公共通路。用途：沟通计算机系统中各部件的信息传递，并使不同厂商提供的产品能互换组合。优点：便于故障诊断和维修，便于模块化结构设计、简化了系统设计，便于系统的扩展和升级，便于生产各种兼容的软硬件。12、举例说明计算机编译程序和解释程序。编译程序就是一个语言翻译程序。它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序。源语言通常是一个高级语言，如FORTRAN，C 或Pascal。目标语言通常是一个低级语言,如汇编或机器语言。这里，高级语言FORTRAN，C 或Pascal的编译器就是编译程序。还有一种高级语言翻译程序，从源程序的编译到执行只有一个阶段解释执行阶段，它同时处理源程序和数据按源程序中语句的动态顺序，逐句地进行分析解释，并立即予以执行，这种翻译程序称为解释程序。最常见的高级语言BASIC就是在解释环境下运行的。在解释方式下，最终并不生成目标程序，这是编译方式与解释方式的根本区别。13、简述组件化的软件开发技术的活动过程。组件化的软件开发技术的活动过程是： （1）收集组件这一活动是指对从本地或远程资源可获得的组件进行仔细分析，从中发现并收集对自己有用的组件。（2）改善组件质量 这一活动是指在仔细分析组件的文档或详细说明书的基础之上，与组件开发商和用户进行必要的讨论，并在不同的环境设置下运行组件，发现组件中可能存在的不足之处，并加以改进，使之达到改善组件质量的目的。 （3）使组件能相互适应这一活动是指通过编写一些简单的程序作为用户需求与组件产生的相应动作之间的缓冲区，这个缓冲区可给组件提供缺省的信息，减少不希望发生的动作，实现互操作。（4）组装组件这一活动是指通过一些通用的基础设施，对组件仓库中的组件进行集成，组装出软件，由组件组装的系统容易重新组合以满足新的需求。14、路由器与交换机的区别路由器的一个作用是连通不同的网络，另一个作用是选择信息传送的线路。 路由器与交换机的区别体现在以下四个方面：（1）工作层次不同。交换机工作在OSI的第二层(数据链路层)，它的工作原理比较简单，路由器工作在OSI的第三层(网络层)，可以得到更多的协议信息，路由器可以做出更加智能的转发决策。（2）数据转发所依据的对象不同。交换机是利用物理地址或者MAC地址来确定转发数据的目的地址。而路由器则是利用不同网络的IP地址来确定数据转发的地址。（3）传统的交换机只能分割冲突域，不能分割广播域；而路由器可以分割广播域。（4）路由器提供了防火墙的服务，它仅仅转发特定地址的数据包，不传送不支持路由协议的数据包传送和未知目标网络数据包的传送，从而可以防止广播风暴。15、网关的主要功能及分类。网关的主要功能是计算路由和跨越可见的局域网的最初边界，传输分组数据。因此它被看作是通往Internet的大门。主要有3类网关：协议网关、应用网关和安全网关。它们之间惟一的共同特性就是网关作为两个不同区域、地区或系统间的中介所起的功能是相同的。 协议网关常用在使用不同协议的网络间进行协议转换。应用网关是在两种不同格式问翻译数据的系统。 安全网关是一些技术的混合，这些技术很重要，而且互不相同，并足以代表它们各自的类别，这些技术的范围可从协议层的过滤到相当复杂的应用层过滤。16、TCP/IP参考模型的应用层协议名称及功能。应用层包含所有的高层协议(应用层协议)。如网络终端协议Telnet：允许一台计算机上的用户登录到远程计算机上并进行操作；文件传输协议FTP：用于文件传输；简单邮件传输协议SMTP：用于电子邮件系统进行邮件的发送；简单网络管理协议SNMP：用于网络的管理(如网络设备的配置与管理)；超文本传输协议HTTP：用于WWW服务，浏览网页。17、TCP/IP参考模型的各层名称及功能。TCP/IP参考模型将网络划分为四个层次：主机一网络层，互联层，传输层和应用层。（1）主机一网络层 主机一网络层包含了OSl参考模型中的物理层和数据链路层，也叫网络接口层或网络存取层，是TCPIP参考模型的最底层，负责通过网络发送和接收IP数据包。 （2）互联层 互联层是整个体系结构的关键部分，使主机可以把分组发往任何网络并到达目的主机，与OSI/RM参考模型的网络层一样，这一层主要处理路由选择、流量控制和网络拥塞。 （3）传输层 TCP/IP参考模型中传输层的主要功能是在网络中的源主机与目的主机的对等实体间建立基于会话的端到端连接。 （4）应用层 由于没有需要，所以TCPIP参考模型没有表示层和会话层，传输层之上便是应用层。18、网桥的作用及分类。网桥是一个局域网与另一个局域网之间建立连接的桥梁。网桥属于网络层的一种设备，它的作用是扩展网络和通信手段，在各种传输介质中转发数据信号，扩展网络的距离，同时又有选择地将有地址的信号从一个传输介质发送到另一个传输介质，并能有效地限制两个介质系统中无关紧要的通信。网桥可分为本地网桥和远程网桥。本地网桥是指在传输介质允许长度范围内互联网络的网桥；远程网桥是指连接的距离超过网络的常规范围时使用的远程桥，通过远程桥互联的局域网将成为城域网或广域网。如果使用远程网桥，则远程桥必须成对出现。19、以太网技术的优缺点。 优点：使用最为广泛，协议简单，站点接入与安装很方便，在低负载时基本没有时延。 缺点：发送时延的不确定，不适合实时性；网络负载加重，网络效率就下降很多，无忧先级；确保正确信号检测，限制了站间的最大距离；发送数据前，要进行冲突检测，发送时世要监听，最小帧长64字节；大量使用模拟部件。20、给出下述文法所对应的正规式：S0A|1BA1S|1B0S|0把后两个产生式代入第一个产生式有：S=01|01SS=10|10S有:S=01S|10S|01|10=(01|10)S|(01|10)=(01|10)*(01|10)即:(01|10)*(01|10)为所求的正规式。三、分析与设计1、银行家算法中，有A、B、C、D四种资源，五个进程，考虑如下的资源分配状态，其中AL为可用资源向量，U为各进程已占用资源矩阵，N为各进程尚需资源矩阵： A B C D A B C DA L= (1,6,2,2) 0 0 3 2 p1 1 0 0 0 p2U = 1 3 5 4 p3 0 3 3 2 p4 0 0 1 4 p5 0 0 1 2 p1 1 7 5 0 p2N = 2 3 5 6 p3 0 6 5 2 p4 0 6 5 6 p5回答下列问题：简单叙述什么是银行家算法，为什么它可以避免产生死锁？该状态是安全状态吗？为什么？如果进程P3提出资源请求（1，2，2，1），能否立即给予满足？（要求给出计算过程、各资源矩阵的变化情况）当某一进程申请一组资源时，要先测试系统是否安全？如果安全则可以分配，否则不予分配。测试的方法是：是否能找到一个安全序列，保证在任一时刻系统所剩资源至少满足一个进程的最大需求。如能找到则系统安全，可以分配，否则系统不安全，不予分配。此时存在一个安全序列：P1-P4-P5-P2-P3,故系统是安全的。若P3提出请求（1，2，2，1）因为 （1，2，2，1）（2，3，5，6） （1，2，2，1）=0（2）1n0m1m0n|n,m=0（1）所求文法为GS=(S,A,a,b,P,S),其中P为：SAAAaAb|（2）所求文法为GS=(S,A,0,1,P,S),其中P为：S1S0|AA0A1|8、已知NFA=（x,y,z,0,1,M,x,z）其中：M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x, M(y,1)=,M(z,1)=y,构造相应的DFA。xy0z010010根据题意有NFA图如下下表由子集法将NFA转换为DFA：II0 = -closure(MoveTo(I,0)I1 = -closure(MoveTo(I,1)AxBzAxBzCx,zDyCx,zCx,zEx,yDyEx,yEx,yFx,y,zAxFx,y,zFx,y,zEx,y01100BCEF00DA11019、对下面的文法G：ETE/E/+E|TFT/T/T|FPF/F/*F/|P(E)|a|b|(1) 证明该文法是LL(1)文法。(2) 构造它的预测分析表。（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(E/)=+,FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,;FIRST(T/)=FIRST(T)=(,a,b,;FIRST(F)=FIRST(P)=(,a,b,;FIRST(F/)=FIRST(P)=*,;FIRST(P)=(,a,b,;FOLLOW集合有：FOLLOW(E)=),#;FOLLOW(E/)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(E/)FOLLOW(E)=+,),#;/不包含FOLLOW(T/)=FOLLOW(T)=FIRST(E/)FOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T/)FOLLOW(T)=(,a,b,+,),#;/不包含FOLLOW(F/)=FOLLOW(F)=FIRST(T/)FOLLOW(T)=(,a,b,+,),#;FOLLOW(P)=FIRST(F/)FOLLOW(F)=*,(,a,b,+,),#;/不包含各产生式的SELECT集合有：SELECT(ETE/)=FIRST(T)=(,a,b,;SELECT(E/+E)=+;SELECT(E/)=FOLLOW(E/)=),#SELECT(TFT/)=FIRST(F)=(,a,b,;SELECT(T/T)=FIRST(T)=(,a,b,;SELECT(T/)=FOLLOW(T/)=+,),#;SELECT(FPF/)=FIRST(P)=(,a,b,;SELECT(F/*F/)=*;SELECT(F/)=FOLLOW(F/)=(,a,b,+,),#;SELECT(P(E)=(SELECT(Pa)=aSELECT(Pb)=bSELECT(P)=可见，相同左部产生式的SELECT集的交集均为空，所以文法GE是LL(1)文法。(2)构造它的预测分析表。文法GE的预测分析表如下：+*()ab#ETE/TE/TE/TE/E/+ETFT/FT/FT/FT/T/TTTTFPF/PF/PF/PF/F/*F/P(E)ab10、构造下述文法GS的自动机：SA0AA0|S1|0该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？由于该文法的产生式SA0，AA0|S1中没有字符集VT的输入，所以不是确定的自动机。要将其他确定化，必须先用代入法得到它对应的正规式。（2分）把SA0代入产生式AS1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。代入SA0有该文法的正规式：0(0|01)*0，（3分）所以，改写该文法为确定的自动机为：（2分）0WX0Z00Y1由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化：下表由子集法将NFA转换为DFA：（3分）100CBA011、令文法GE为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。可为E+T*F构造一棵语法树（见下图），所以它是句型。EE + TT * F从语法树中容易看出，E+T*F的短语有：T*F是句型E+T*F的相对于T的短语，也是相对于规则TT*F的直接短语。E+T*F是句型E+T*F的相对于E的短语。句型E+T*F的句柄（最左直接短语）是T*F。四、单选题测试1、若P、V操作的信号量S的初值为2，当前值为-1，则等待进程的数目是（ ）。A.0 B. 1 C. 2 D. 32、采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是（ ）。A. 224 B. 216 C. 28 D. 2323、如果有3个进程共享4个同类资源，为使这3个进程不陷入死锁，每个进程至多需要这类资源数是（ ）。A. 1 B. 2 C. 3 D. 44、若RAM中每个存储单元是16位，则下面所述正确的是（ ）。 A、地址线是16位 B、地址线与16无关 C、地址线与16与有关 D、地址线不得少于16位5、在相对寻址方式中，若指令中地址码是X，则操作数的地址是（ ）。A、X B、（PC）+X C、X+段基址 D、变址寄存器+X6、一个进程被唤醒，其含义是（ ）。A. 该进程重新占有了CPU B. 该进程的优先权变为最大C. 该进程的PCB移至等待队列首 D. 该进程变为就绪状态7、在下列文件的物理结构中，不利于文件长度动态增长的是（ ）。A. 顺序结构 B. 链接结构 C. 索引结构 D. HASH结构8、在通常的语法分析方法中，特别适用于表达式的分析方法是（ ）A. LR分析法 B. 算符优先分析法 C. 递归下降分析法 D. LL(1)分析法9、对于下列一串汇编指令：MOV AX，A；ADD AX，B；MOV T，AX，对应的四元式为（ ）A.（+，T，A，B） B.（+，T，B，A） C.（+，B，