计算机软件技术基础复习题
计算机软件技术基础复习题
一、基本概念
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位
②125CH
③
9、一个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、3
②6次
③7次
10、若某计算机数据线、地址线都是8bit，有一条相对寻址的无条件转移指令存于主存的
20H单元中，指令给出的位移量D=00010101B，设该指令占用2个字节。
问：①取该指令时PC的内容
②该指令执行结束时PC的内容
①取该指令时PC的内容是：20H
②该指令执行结束时PC的内容是：
(PC)+2+D=00100000+00000010+00010101=00110111B=37H
11、计算机系统中总线结构的概念及优点。
总线：所谓总线就是指若干信号线的集合，由这些信号线组成在两个以上部件间传送信息的公共通路。
用途：沟通计算机系统中各部件的信息传递，并使不同厂商提供的产品能互换组合。
优点：便于故障诊断和维修，便于模块化结构设计、简化了系统设计，便于系统的扩展和升级，便于生产各种兼容的软硬件。
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参考模型中的物理层和数据链路层，也叫网络接口层或网络存取层，是TCP／IP参考模型的最底层，负责通过网络发送和接收IP数据包。
（2）互联层
互联层是整个体系结构的关键部分，使主机可以把分组发往任何网络并到达目的主机，与OSI/RM参考模型的网络层一样，这一层主要处理路由选择、流量控制和网络拥塞。
（3）传输层
TCP/IP参考模型中传输层的主要功能是在网络中的源主机与目的主机的对等实体间建立基于会话的端到端连接。
（4）应用层
由于没有需要，所以TCP／IP参考模型没有表示层和会话层，传输层之上便是应用层。
18、网桥的作用及分类。
网桥是一个局域网与另一个局域网之间建立连接的桥梁。网桥属于网络层的一种设备，它的作用是扩展网络和通信手段，在各种传输介质中转发数据信号，扩展网络的距离，同时又有选择地将有地址的信号从一个传输介质发送到另一个传输介质，并能有效地限制两个介
质系统中无关紧要的通信。
网桥可分为本地网桥和远程网桥。本地网桥是指在传输介质允许长度范围内互联网络的网桥；远程网桥是指连接的距离超过网络的常规范围时使用的远程桥，通过远程桥互联的局域网将成为城域网或广域网。如果使用远程网桥，则远程桥必须成对出现。
19、以太网技术的优缺点。
优点：使用最为广泛，协议简单，站点接入与安装很方便，在低负载时基本没有时延。
缺点：发送时延的不确定，不适合实时性；网络负载加重，网络效率就下降很多，无忧先级；确保正确信号检测，限制了站间的最大距离；发送数据前，要进行冲突检测，发送时世要监听，最小帧长64字节；大量使用模拟部件。
20、给出下述文法所对应的正规式：
S→0A|1B
A→1S|1
B→0S|0
把后两个产生式代入第一个产生式有：
S=01|01S
S=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 D
A L= (1,6,2,2)
0 0 3 2 p1
1 0 0 0 p2
U = 1 3 5 4 p3
0 3 3 2 p4
0 0 1 4 p5
0 0 1 2 p1
1 7 5 0 p2
N = 2 3 5 6 p3
0 6 5 2 p4
6 5 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）<（1，6，2，2）
故可假设将资源分配给P3，修改相应的数据结构，此时资源分配情况如下：
AL=（0，4，0，1）
0 0 3 2 p1 0 0 1 2 p1
1 0 0 0 p
2 1 7 5 0 p2
U = 2 5 7 5 p3 N= 1 1 3 5 p3
0 3 3 2 p4 0 6 5 2 p4
0 0 1 4 p5 0 6 5 6 p5
此时用安全性算法检查系统是否安全, 可用资源AL=（0，4，0，1）已不能满足任何进程的需要,故系统处于不安全状态,故不能将资源分配给P3。
2、某计算机的存储系统由cache、主存和磁盘组成。在cache中访问一个字需20ns，把一个字从主存装入cache需60ns，把一个字从磁盘调入主存需12ns。Cache的命中率是0.9，主存的命中率是0.6。
问：此系统访问一个字的平均存取时间是多少？（以ns为单位）
因为cache的命中率是0.9，所以90%的字的平均存取时间是0.9*20ns=18ns
因为主存的命中率是0.6，所以有0.6*0.1的数据要从主存装入cache，再从cache中存取，其平均存取时间是0.6*0.1*(60ns+20ns)=4.8ns
有0.4*0.1的数据要从磁盘调入主存，再调入cache进行存取，其平均存取时间是0.4*0.1*(12ns+60ns+20ns)=3.68ns
此系统访问一个字的平均存取时间是18ns+4.8ns+3.68ns=26.48ns
3、设有下面的程序段
FIRST DB 89H,0ADH,12H
SECOND DB 90H,0BAH,84H
MOV CX,3
CLC
MOV SI,0
ADDER: MOV AL,SECOND[SI]
ADC FIRST [SI],AL
INC SI
LOOP ADDER
问：①逐条解释各条指令的作用
②该程序段完成什么功能？运行结束后，FIRST与SECOND单元中存放的数据是什么？
①FIRST DB 89H,0ADH,12H ；单元FIRST中存放三字节数12AD89H SECOND DB 90H,0BAH,84H ；单元SECOND中存放三字节数84BA90H MOV CX,3 ；3送入计数器CX
CLC ；进位清0
MOV SI,0 ；0送入源址变址寄存器SI
ADDER: MOV AL,SECOND[SI] ；SECOND+[SI]单元中的数据送AL
ADC FIRST [SI],AL ；AL中的内容加上FIRST +[SI] 中的内容送入FIRST +[SI]中
INC SI ；SI加1
LOOP ADDER ；CX减1后不为0时转到ADDER，CX为0退出②该程序段完成两个三字节数的加法运算。
运行结束后，FIRST中为两个三字节数的和：976819H
SECOND中的数据不变：84BA90H
4、设有4个进程R1、R2、W1、W2，共享可以存放一个数的缓冲区B。进程R1把来自键
盘的一个数存入缓冲区B，供进程W1打印输出；进程R2每次从磁盘上读一个数存入缓冲区B，供进程W2打印输出。
回答问题：
①给出应设置的信号量及其初值，说明其含义。
②用P、V操作来描述4个进程之间的同步、互斥关系。
①empty表示缓冲区的容量，初值为1；
mutex为R1和R2之间的互斥信号量，初值为1；
sa 为R1与W1之间的同步信号量，表示缓冲区中有来自键盘的一个数,初值为0；
sb 为R2与W2之间的同步信号量，表示缓冲区中有来自磁盘的一个数,初值为0。
②Process R1 Process R2 Process W1 Process W2
P(empty) P(empty) P(sa) P(sb)
P(mutex) P(mutex); 取R1放入的数取R2放入的数
把来自键盘的一个把来自键盘的一个V(empty); V(empty);
数存入缓冲区B 数存入缓冲区B
V(mutex); V(mutex);
V(sa); V(sb);
5、某机字长32位，按字节编址。现有10个数据依次存入主存，其长度分别是字节、半字、双字、单字、字节、单字、双字、半字、单字、字节。请设计一种既节省存储空间，又能保证任何长度的数据都能在单个存储周期内完成读写的存储方式，画出主存中数据存放的示意图。
采用边界对齐的方法存放这10个数据，数据存放的示意图如下：
字节半字
双字
单字字节
单字
双字
半字单字
字节
6、磁盘的每个磁道分成7个块，现有一文件共有7个记录，依次为：A、B、C、D、E、F、G，存放在某一磁道上，每个记录的大小与块的大小相等，设磁盘的转速为21ms/转，每读出一块后需要2ms的处理时间，忽略其它辅助时间。
问：
①如果顺序存放这些记录并顺序读取，处理该文件需要多少时间？
②如果要顺序读取该文件，记录如何存放处理时间最短？计算此时读取、处理该文件
所需的时间。
读出1个记录的时间为：21/7=3(ms)
①顺序存放这7个记录时，读出并处理共需7*(3ms+2ms)=35ms
第1个记录没有延迟，其余每个记录延迟19ms ，6个记录共延迟6*19ms=114ms 顺序读取并处理这7个记录共用114ms+35ms=149ms
此时读出并处理这7个记录仍需7*(3ms+2ms)=35ms
第1个记录没有延迟，其余每个记录延迟1ms ，6个记录共延迟6*1ms=6ms 顺序读取并处理这7个记录共用6ms+35ms=41ms 7、给出生成下述语言的上下文无关文法：
（1）{a n b n a m b m
|n,m>=0}
（2）{1n 0m 1m 0n
|n,m>=0}
（1）所求文法为G[S]=({S,A},{a,b},P,S),其中P 为： S →AA A →aAb|ε
（2）所求文法为G[S]=({S,A},{0,1},P,S),其中P 为： S →1S0|A
A →0A1|ε
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 。
根据题意有NFA
0 1
1
9、对下面的文法G ：
E →TE
/
E /
→+E|ε T →FT
/
T /
→T|ε F →PF /
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(E →TE /
)=FIRST(T)={(,a,b,^}; SELECT(E /
→+E)={+};
SELECT(E /
→ε)=FOLLOW(E /
)={),#} SELECT(T →FT /
)=FIRST(F)={(,a,b,^}; SELECT(T /
→T)=FIRST(T)={(,a,b,^}; SELECT(T /
→ε)=FOLLOW(T /
)={+,),#}; SELECT(F →PF /
)=FIRST(P)={(,a,b,^};
1
SELECT(F/→*F/)={*};
SELECT(F/→ε)=FOLLOW(F/)={(,a,b,^,+,),#};
SELECT(P→(E))={(}
SELECT(P→a)={a}
SELECT(P→b)={b}
SELECT(P→^)={^}
可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。
(2)构造它的预测分析表。
文法G[E]的预测分析表如下：
10、构造下述文法G[S]的自动机：
S→A0
A→A0|S1|0
该自动机是确定的吗？若不确定，则对它确定化。该自动机相应的语言是什么？
由于该文法的产生式S→A0，A→A0|S1中没有字符集V T的输入，所以不是确定的自动机。要将其他确定化，必须先用代入法得到它对应的正规式。（2分）
把S→A0代入产生式A→S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。代入S→A0有该文法的正规式：0(0|01)*0，（3分）
所以，改写该文法为确定的自动机为：（2分）
由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化：
下表由子集法将NFA转换为DFA：（3分）
11、令文法G[E]为：
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
可为E+T*F构造一棵语法树（见下图），所以它是句型。
E
E + T
T * F
从语法树中容易看出，E+T*F的短语有：
T*F是句型E+T*F的相对于T的短语，也是相对于规则T→T*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. 3
2、采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最
大长度是（）。
A. 224
B. 216
C. 28
D. 232
3、如果有3个进程共享4个同类资源，为使这3个进程不陷入死锁，每个进程至多需要这类资源数是（）。
A. 1
B. 2
C. 3
D. 4
4、若RAM中每个存储单元是16位，则下面所述正确的是（）。
A、地址线是16位
B、地址线与16无关
C、地址线与16与有关
D、地址线不得少于16位
5、在相对寻址方式中，若指令中地址码是X，则操作数的地址是（）。
A、X
B、（PC）+X
C、X+段基址
D、变址寄存器+X
6、一个进程被唤醒，其含义是（）。
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，A，T）
D.（+，A，B，T）
10、在编译中产生语法树是为了（）
A. 词法分析
B.语法分析
C. 语义分析
D. 产生目标代码
11、如果符号串α是从开始符号推导出来的，即S′α则称α是一个( )
A. 句型
B. 短语
C. 句柄
D. 句子
12、有一文法G：⑴Z→Be ⑵A→Ae|e ⑶B→Af ⑷D→f，则FOLLOW（Z）=（）
A. {e，f，#}
B. {e，#}
C. {#}
D. {f，#}
13、下列有关网络拓扑结构的概念，正确的是（）
A. 网络拓扑结构是指网络节点间的分布形式
B. 树型结构的缺点是，当需要增加新的工作站时成本较高
C. 目前局域网中最普遍采用的拓扑结构是总线型结构
D. 树型结构的线路复杂，网络管理比较困难
14、下面关于FDDI的说法，不正确的是（）
A. 采用单令牌方式
B. 物理子层采用双极归零编码
C. 为提高系统的可靠性，采用双环结构
D. 一种高性能的光纤令牌环网，它的数据传输速率为100 Mbps
15、关于防火墙的功能，下面叙述错误的是( )
A. 防火墙可以检查进出内部网络的通信量
B. 防火墙可以使用应用网关在应用层上建立协议过滤和转发功能
C. 防火墙可以使用过滤技术在网络层对数据包进行选择
D. 防火墙可以阻止来自内部的威胁和攻击
16、Internet模型的网络层，负责下列哪一个功能( )
A. 格式化报文
B. 为数据选择通过网络的路由
C. 定义连接到介质的特征
D. 提供远程文件访问能力
17、下列哪项不是局域网性能的主要技术要素（）
A. 网络拓扑结构
B. 传输介质
C. 介质访问控制方法
D. 网络操作系统
18、关于计算机接入Internet，错误的说法是（）
A.要实现计算机与Internet的连接，必须使用调制解调器
B. 通过DDN专线直接与Internet相连，成本及费用较高
C. 可以将计算机直接连入已与Internet相连的局域网上
D. 有的手机可以直接与Internet相连
19、下面哪一个描述了计算机网络体系结构中的分层概念( )
A. 保持网络灵活且易于修改
B. 所有的网络体系结构都用相同的层次名称和功能
C. 把相关的网络功能组合在一层中
D. A和C
20、关于计算机网络的基本特征，不正确的是（）
A.在计算机网络中采用了分组交换技术
B. 建立计算机网络的主要目的是实现计算机资源的共享
C. 互连的计算机是分布在不同地理位置的多台独立的计算机
D. 连网的计算机之间的通信必须遵循共同的网络协议
软件技术基础试题及答案
软件技术基础试题及答案
软件技术基础 系班级姓名成绩 得分评卷 人一、填空题（每空1分，共25分） 1.数据结构作为一门学科，主要研究数据 的、存储结构以及 三方面内容。 2.当对一个线性表经常进行插入或删除操作时，则 宜采用存储结构；而经常进行的是访问操作，而很少进行插入或删除操作时，则宜采用存储结构。 3.在线性结构中，首结点有个前驱结点， 其余每个结点有且只有个前驱结点。4.限定在表的一端进行插入，在表的另一端进行删 除的线性表称为；限定在表的一端进行插入和删除运算的线性表称为。 5.一个8阶的下三角矩阵B按行优先顺序压缩存储 第2页，共19页
6. 第3页，共19页
7. 8.操作系统通过记载、跟 踪、控制进程的执行，它是进程存在的唯一标志。 作业调度程序是从处于状态的作业中选取一个作业并把它装入主存。 12A.软件生命周期瀑布模型一般可分为问题分析、、、 和软件维护五个阶段。 , 得分评卷 人二、选择题（每小题1分，共10分）下列语句正确的是（）。 A. int *p=&x; B. int *p=x; C. int p=&x; D. int *p=*x; 2. int a[ ]={1,2,3,4,5},b[5],*p; 则下列语句中不 正确的语句是（）。 A. p=b+1; B.p=&a[3]; C. p=a; D.b=a; 3. 设有以下说明语句 struct node{ int a；float b；}；struct node node1,node2,*pnode; 则下列语句中正确是（）。 A. node1=node2； B. 第4页，共19页
软件技术基础模拟试题及参考答案
软件技术基础模拟试题（第二十次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1、数据元素是数据的基本单位，数据项是数据的最小单位。（） 2、栈是特殊的线性表，须用一组地址连续的存储单元来存储其元素。（） 3、引入虚拟存储技术后，逻辑内存总容量是由地址总线的位置确定的。（） 4、编译程序是一种常用应用软件。（） 5、顺序文件和链接文件的长度都可以动态变化。（） 6、在文件系统中采用目录管理文件。（） 7、允许多用户在其终端上同时交互地使用计算机的操作系统称为实时系统。（） 8、程序、数据、和进程控制块是构成一个进程的三要素。（） 9、黑盒测试时，既要考虑程序的内部逻辑结构又要考虑其外部特性。（） 10、软件的总体设计和详细设计都要用PAD图形工具。（） (参考答案：1~10：ABABB ABABB) 二、单项选择题：（每小题1分，共5分） 1、允许用户把若干作业提交计算机系统集中处理的操作系统称为（）。 A分时操作系统B实时操作系统C网络操作系统D批处理操作系统2、分配到必要资源并获得了处理机时的进程的状态称为（）。 A就绪状态B执行状态C等待状态D阻塞状态 3、利用通道技术可以在（）之间直接交换数据。 A内存与CPU B CPU与外设C内存与外设D内存、CPU和外设三者4、以下的准则中哪个不是软件设计的准则（）。 A编程语言选择准则B信息屏蔽准则 C结构化和模块化准则D抽象准则 5、有一数列：97657613294958经过一趟排序后得到： 65971376294958请问使用的是何种排序方法？（） A简单插入排序B冒泡排序C2路归并排序D快速排序 (参考答案：DBCAC) 软件技术基础模拟试题（第十九次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1、在目前，用于保证软件质量的主要手段是进行软件测试。（） 2、使用DMA方式传送数据期间不需要CPU干预。（） 3、线性顺序队列会产生“假溢出”，而线性循环队列则不会。（） 4、对同一种算法，用高级语言编写的程序比用低级语言编写的程序运行速度快。（） 5、在线性表中，数据的存储方式有顺序和链接两种。（） 6、进程由程序块、文件控件块和数据块三部分组成。（） 7、在面向对象的程序设计中，派生类只能从一个基类产生。（） 8、操作系统是用户和硬件的接口。（） 9、个人计算机中可配置的最大内存容量受地址总线位数的限制。（） 10、软件维护中最困难的问题是软件配置不全。（） (参考答案：1~10：A、A、A、B、A、B、A、A、A、B) 二、单项选择题：（每小题1分，共5分）
软件技术基础模拟题
《软件技术基础》模拟题 一、填空题 1. 软件工程的传统途径是_____________方法学。 2. 一般说来，软件生命周期由_____________、软件开发和软件维护三个时期组成。 3. _______________的目的就是用最小的代价在尽可能短的时间内确定该软件项目是否能够开发，是否值得去开发。 4. 数据流图描述系统的_____________模型。 5. 数据字典的用途是作为_____________阶段的工具。 6. 在可行性研究以后，如果确认开发一个新的软件系统是必要的而且是可能的，那么就进入___________阶段。 7. ER模型中包含“实体”、“联系”和“_____________”三个基本成分。 8. 结构化分析方法是面向_____________进行需求分析的方法。 9. _____________是对一个软件结构内不同模块之间互联程度的度量。 10. _____________标志一个模块内各个元素彼此结合的紧密程度，它是信息隐蔽和局部化概念的自然扩展。 11. 面向数据流的设计方法把信息流映射成软件结构，信息流的类型决定了映射的方法。信息流有变换流和_____________两种类型。 12. 衡量模块独立性的两个定性的度量标准是内聚性和_________。 13. 在详细设计阶段，经常采用的工具有程序流程图、盒图、_________。 14. Jackson图不仅可表示程序结构，还可表示_________。 15. 20世纪70年代中期出现了“面向数据结构”的设计方法，其中有代表性的是Jackson方法和_________方法。 16. 面向对象有三个基本要素，它们是抽象、封装性和________。 17. 所谓对象模型就是表示静态的、________的系统的“数据”性质。 18. 维护的副作用有编码副作用、数据副作用和________副作用。 19. 软件测试是为了__________而执行程序的过程。 20. 白盒测试是结构测试，黑盒测试是________测试。 二选择 1. 研究开发资源的有效性是进行_______可行性研究的一方面。 A. 经济 B. 技术 C. 操作 D. 社会 2. 软件生命周期中时间最长的阶段是______阶段。 A. 需求分析 B. 详细设计 C. 测试 D. 维护 3. 瀑布模型是一种_________。
多媒体技术基础复习试题(含答案)
一、填空 1、多媒体的英文是multimedia，Virtual Reality的含义是虚拟现实。 2、Windows95(98)系统中播放声音的软件有：CD播放器、媒体播放机和录音机。 3、文本、声音、图形、图像和动画等信息的载体中的两个或多个的组合构成了多 媒体。 4、图形也称矢量图，是由诸如直线、曲线、圆或曲面等几何图形（称 为图形）形成的从点、线、面到三维空间的黑白或彩色几何图。 5、音频有时也泛称声音，包括语音说明、背景音乐和效果音响。 6、计算机中保存声音文件的格式有多种，常用的有：波形音频文件（WAV）和 数字音频文件（MIDI）。 7、波形音频文件是真实声音数字化后的数据文件。 8、数字音频文件又称乐器数字接口，是以一系列指令来表示声音的，可看成 是声音的符号表示。 9、多媒体系统可分成6个层次：多媒体外围设备、多媒体计算机硬件系 统、多媒体核心系统、媒体制作平台与工具、创作/编辑软件、 应用系统。 10、构建一个多媒体系统，硬件是基础，软件是灵魂。 11、多媒体外围设备包括：音频、视频等多种媒体的输入/输出设备和装置，通 讯（网络）传输设备及装置。 12、多媒体计算机硬件系统，包括多媒体计算机主机系统（MPC）及各种外围设 备的接口部件。 13、多媒体核心系统，其实质就是多媒体操作系统，也包括设备的驱动程序。 14、媒体制作平台与工具，就是多媒体素材准备工具。 15、多媒体编辑与创作系统，该层是开发多媒体应用系统的平台或环境，可以 实现各种媒体的综合利用。 16、多媒体关键技术一般分成二类：多媒体应用所涉及的关键技术、研制多媒 体计算机系统本身要解决的关键技术。 17、研制多媒体计算机系统要解决的关键技术包括：多媒体数据压缩技术、 多媒体专用芯片技术、多媒体输入/输出技术、多媒体存储技术、 多媒体系统软件技术。 18、多媒体应用涉及的关键技术包括：多媒体素材采集/制作技术、多媒体应 用程序开发技术、多媒体创作工具及开发环境、多媒体界面设计与人 机交互技术、多媒体网络通讯技术、虚拟现实技术。 19、目前常用的压缩编码方法分为两类：无损压缩法（或冗余压缩法/熵编码）和有 损压缩法（或熵压缩法）。 20、多媒体通讯是多媒体技术和通讯技术结合的产物，它将计算机的交互 性、通讯的分布性和广播、电视的真实性融为一体。如普通电话到可视电 话。 21、现有的通讯网络包括：电话网、计算机局域网、综合业务数字网、宽 带综合业务数字网、有线电视网等。
软件技术基础模拟试题
软件技术基础模拟试题（第二十四次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1. 顺序表和线性链表的物理存贮形式都是顺序存贮。( 1 ) 2. 数据类型是某种程序设计语言中已实现的数据结构。( 2 ) 3. 如果通过软件测试没有发现错误，则说明软件是完全正确的。( 3 ) 4. 快速原型模型可以有效地适应用户需求的动态变化。( 4 ) 5. 不同进程之间的动作在时间上不能重叠。( 5 ) 6. 分区式存储管理能够进行存储空间共享。( 6 ) 7. 链接文件和索引文件都可以非连续存放。( 7 ) 8. 中断处理一般分为中断响应和中断处理两个步骤。前者由软件实施，后者主要由硬件实施。( 8 ) 9. 在C++语言中，“重载”表达了最简单的多态性。( 9 ) 10.进程调度根据一定的调度算法，从等待队列中挑选出合适的进程。( 10 ) (参考答案：1~10：ABBAB BABAB ) 二、单项选择题：（每小题1分，共5分） 1. 在数据结构中，一个存储结点存放一个（11 ）。 11 (A) 数据项(B) 数据元素(C) 数据结构(D) 数据类型 2. 把逻辑地址转变为存储的物理地址的过程称作（12 ）。 12 (A) 编译(B) 连接(C) 运行(D) 重定位 3. SPOOLing技术可以实现设备的（13 ）分配。 13 (A) 虚拟(B) 共享(C) 独占(D) 物理 4. 允许用户把若干作业提交计算机系统集中处理的操作系统称为（14 ）。 14 (A) 分时操作系统(B) 实时操作系统 (C) 网络操作系统(D) 批处理操作系统 5. 进程从运行状态进入就绪状态的原因可能是（15 ）。 15 (A) 被选中占有处理机(B) 时间片用完 (C) 等待的事件已发生(D) 等待某一事件 (参考答案：BBADB) 软件技术基础模拟试题（第二十三次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1. 数据在计算机内在中的表示是指数据的存储结构。( 1 ) 2. 能影响中断响应次序的技术是中断优先级和中断屏蔽。( 2 ) 3. 链表可以随机访问任意一个结点，而顺序表则不能。( 3 ) 4. 作业与进程的主要区别是前者是由用户提交，后者是由系统自动生成。( 4 ) 5. Windows、OS/2、Linux微机操作系统都是多用户多任务操作系统。( 5 ) 6. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关，是独立于计算机的。 ( 6 ) 7. 流式文件和记录式文件都以字符为基本单位进行存取。( 7 ) 8. 不定长文件是指字段的长度不固定。( 8 ) 9. 软件工程的三要素包括方法、工具和环境。( 9 ) 10.软件结构是以指令为基础而组成的一种控制层次结构。( 10 ) (参考答案：1~10：AABAB ABBBB) 二、单项选择题：（每小题1分，共5分） 1. 若进栈序列为1,2,3,4，且进栈过程中可以出栈，则不可能出栈的序列是 ( 11 ). 11 (A) 1,4,3,2 (B) 2,3,4,1 (C) 3,1,4,2 (D) 3,4,2,1
软件技术基础试题(含答案)
《操作系统》 选择题： （bs30）1. 分页式存储管理的主要特点是（B）。 (A) 要求作业全部同时装入内存(B) 不要求作业装入到内存的连续区域 (C) 要求扩充外存容量(D) 不要求处理缺页中断 （bs30）2. 进程从运行状态进入就绪状态的原因可能是（D）。 (A) 被选中占有处理机(B) 等待某一事件(C) 等待的事件已发生(D) 时间片用完 （bs30）3. 多道程序设计是指（D）。 (A) 在实时系统中并发运行多个程序(B) 在分布系统工程中同一时刻运行多个程序 (C) 在一台处理机上同一时刻运行多个程序(D) 在一台处理机上并发运行多个程序 （bs29）2. 进程从运行状态进入就绪状态的原因可能是（ A ）。 (A) 时间片用完(B) 等待某一事件(C) 等待的事件已发生(D) 被选中占有处理机（bs29）4. 以下（D）不是实时操作系统的特点。 (A) 高可靠性(B) 及时响应(C) 高效性(D) 通用性 （bs28）3. 任何两个并发进程之间（ A ）。 (A) 可能存在同步或互斥关系(B) 一定存在同步关系 (C) 一定彼此独立无关(D) 一定存在互斥关系 （bs28）4. 以下的哪个特征不是分时操作系统的主要特征（B）。 (A) 分时性(B) 独占性(C) 交互性(D) 多路性 （bs27）2. 以下（D）不是实时操作系统的特点。 (A) 高可靠性(B) 及时响应(C) 中断管理(D) 独立性 （bs27）3. 若当前进程因时间片用完而让出处理机时，该进程应转变为（B）状态。 (A) 运行(B) 就绪(C) 等待(D) 完成 （bs26）3. 在多道程序设计系统中，处于后备状态的作业要经过（D）调度后才能真正执行。 (A) 作业调度(B) 作业调度和设备调度(C) 进程调度(D) 作业调度和进程调度 （bs25）1. 把高级语言的源程序翻译成二进制代码的过程称为：（A）。 (A) 编译(B) 连接(C) 运行(D) 重定位 （bs25）2. 把逻辑地址转变为内存的物理地址的过程称作（D）。 (A) 地址分配(B) 地址连接(C) 地址调用(D) 地址变换 （bs25）4. 在操作系统中，进程最基本的特征是（A）。 (A) 动态性和并发性(B) 顺序性和可再现性 (C) 与程序的对应性(D) 执行过程的封闭性 （bs24）2. 把逻辑地址转变为存储的物理地址的过程称作（D）。 (A) 编译(B) 连接(C) 运行(D) 重定位 （bs24）3. SPOOLing技术可以实现设备的（B）分配。 (A) 虚拟(B) 共享(C) 独占(D) 物理 （bs24）4. 允许用户把若干作业提交计算机系统集中处理的操作系统称为（D）。 (A) 分时操作系统(B) 实时操作系统 (C) 网络操作系统(D) 批处理操作系统 （bs24）5. 进程从运行状态进入就绪状态的原因可能是（B）。 (A) 被选中占有处理机(B) 时间片用完 (C) 等待的事件已发生(D) 等待某一事件 （bs23）2. 任何两个并发进程之间( D) (A) 一定存在互斥关系(B) 一定存在同步关系 (C) 一定彼此独立无关(D) 可能存在同步或互斥关系
VB软件技术基础模拟题及参考答案
软件技术基础模拟试题（第二十次省统考） 1、是非判断题（正确选填A，错误选填B）（每小题1分，共10 分） 1、数据元素是数据的基本单位，数据项是数据的最小单位。（ ） 2、栈是特殊的线性表，须用一组地址连续的存储单元来存储其元素。（ ） 3、引入虚拟存储技术后，逻辑内存总容量是由地址总线的位置确定的。（ ） 4、编译程序是一种常用应用软件。（ ） 5、顺序文件和链接文件的长度都可以动态变化。（ ） 6、在文件系统中采用目录管理文件。（ ） 7、允许多用户在其终端上同时交互地使用计算机的操作系统称为实时系统。（ ） 8、程序、数据、和进程控制块是构成一个进程的三要素。（ ） 9、黑盒测试时，既要考虑程序的内部逻辑结构又要考虑其外部特性。（ ） 10、软件的总体设计和详细设计都要用PAD图形工具。（ ） (参考答案：1~10：ABABB ABABB) 2、单项选择题：（每小题1分，共5分） 1、允许用户把若干作业提交计算机系统集中处理的操作系统称为 （ ）。 A 分时操作系统 B 实时操作系统 C 网络操作系统 D 批处理操作系统 2、分配到必要资源并获得了处理机时的进程的状态称为（ ）。 A 就绪状态 B 执行状态 C 等待状态 D 阻塞状态3、利用通道技术可以在（ ）之间直接交换数据。 A 内存与CPU B CPU与外设 C 内存与外设 D 内存、CPU和外设三者 4、以下的准则中哪个不是软件设计的准则（ ）。 A 编程语言选择准则 B 信息屏蔽准则 C 结构化和模块化准则 D 抽象准则 5、有一数列：97 65 76 13 29 49 58 经过一趟排序后得到： 65 97 13 76 29 49 58 请问使用的是何种排序方法？（ ） A 简单插入排序 B 冒泡排序 C 2路归并排序 D 快速排序 (参考答案：DBCAC )
软件技术基础复习题集
《软件技术基础》复习题 一、填空题（每空1分，共20分） 1、当今计算机基本都以原理为基础，其五大功能部件为； 2、使用汇编语言（或者高级语言）写出的程序称为；将以上程序翻译成机器语言的程序称为；经过翻译转换后能由计算机直接执行的机器指令程序称为； 3、从计算机系统角度来看，Windows XP属于软件；Office 2003属于软件； 4、数据结构是研究的一门学科；它包括三方面的容：、、； 5、数据在存储器中的存储有四种基本的映像方法，它们是：、、、； 6、对于数据的插入、删除等操作，堆栈式结构遵循的原则，而队式结构遵循的原则； 7、设s[1，…，max]为一个顺序结构栈，变量top指示栈顶位置，栈为空的条件是，栈为满的条件是。 8、具有100个结点的完全二叉树的深度为。 9、有n个叶子结点的哈夫曼树中，总结点数是。 10、3个结点可以构成棵不同形态的树。 11、从资源分配的角度看P.V操作，P操作意味着向系统资源，而V操作意味着向系统资源。 12、设某进程的访问页面走向为1，3，1，2，4，页架数为3，按FIFO页面替换算法，当访问到4号页面时，应淘汰号页面。 13、DBMS就是它是位于和之间的一层管理软件。 14、数据独立性又可分为和。 15、现实世界的事物反映到人的头脑中经过思维加工成数据，这一过程要经过三个领域，它们依次是、和。 16、关系代数运算中，专门的关系运算有、和。 17、一个作业从进入系统到运行结束，一般要经历、、、 4种状态。 18、进程的基本状态是、和。
19、存储分配策略分为、和三种。 20、文件的存取方法有和。 二、单项选择题（每题2分，共20分） 1、算法指的是（） A计算机程序B解决问题的计算方法 C排序方法D解决问题的有限运算序列 2、数据的存储结构包括顺序、、散列和（）4种基本类型 A索引B数组C集合D向量 3、执行下面程序段时，S语句的执行次数为（）。 for(int i=1;i<=n;i++) for(int j=1,j<=i;j++) S; A.n(n-1)/2 B.n(n+1)/2 C.n2/2 D.n 4、在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。 A.(n+1)/2 B.n/2 C.n D.n+1 5、一个栈输入序列为1，2，3，4，5，则下列序列中不可能是栈的输出序列是（）。 （A）1 2 3 4 5 （B）5 4 3 2 1 （C）2 3 4 5 1 （D）4 1 2 3 5 6、有64个结点的完全二叉树深度为（） （A）8 （B）7 （C）6 （D）5 7、在有n个结点的二叉链表中，值为非空的域的个数为（）。 （A）n-1 （B）2n-1 （C）n+1 （D）2n+1 8、在操作系统中P.V操作是一种（）。 （A）机器指令（B）系统调用命令 （C）作业控制命令（D）低级进程通信原语 9、把作业地址空间中的逻辑地址变为存中物理地址称为（）。 （A）加载（B）重定位（C）物理化（D）逻辑化10、文件系统使用（）组织文件。 （A）堆栈（B）指针（C）目录（D）路径 11、在操作系统中死锁的出现是因为（）。 (A)计算机系统发生重大故障
软件技术基础试题及答案
软件技术基础 系班级姓名成绩得分评卷人 一、填空题（每空1分，共25分） 1.数据结构作为一门学科，主要研究数据的、存储结构以及 三方面内容。 2.当对一个线性表经常进行插入或删除操作时，则宜采用存储结构；而经常进 行的是访问操作，而很少进行插入或删除操作时，则宜采用存储结构。 3.在线性结构中，首结点有个前驱结点，其余每个结点有且只有个前驱结点。 4.限定在表的一端进行插入，在表的另一端进行删除的线性表称为；限定在表 的一端进行插入和删除运算的线性表称为。 5.一个8阶的下三角矩阵B按行优先顺序压缩存储在一维数组中，则数组的大小应设 为。 6.按照二叉树的定义，具有3个结点的二叉树形态有种；具有65个结点的完全二叉 树其深度为; 深度为10的完全二叉树最多有个结点 7.在长度为n的顺序表的第i个位置上插入一个元素，元素的移动次数为；删除 第i个元素时，需要从前向后依次前移个元素。(1≤i≤n+1) 8. 顺序存储结构的循环队列中，设front 和rear分别为队头和队尾指示器，该队列中能存放的 最大元素的个数为M AX-1，则判断队列为满的条件为，而判断队列为空的条件是。 9. 设D={A，B，C，D，E}，R={
和软件维护五个阶段。 , 得分评卷人 二、选择题（每小题1分，共10分） 1. 已知：int x; 下列语句正确的是（）。 A. int *p=&x; B. int *p=x; C. int p=&x; D. int *p=*x; 2. int a[ ]={1,2,3,4,5},b[5],*p; 则下列语句中不正确的语句是（）。 A. p=b+1; B.p=&a[3]; C. p=a; D.b=a; 3. 设有以下说明语句 struct node{ int a；float b；}； struct node node1,node2,*pnode; 则下列语句中正确是（）。 A. node1=node2； B. pnode.a=10； C. return (node1+node2)； D. scanf(“%d %f”,node1); 4. 线性链表不具有的特点是（）。 A. 可随机访问任一个结点B．不必事先估计所需存储空间大小 C. 插入与删除时不必移动元素D．所需空间与线性表长度成正比 5. 若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。 A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2 6. 有向图的邻接表中，顶点Vi的出度是（）。 A. 依附于Vi的弧数 B.Vi链表中的邻接结点个数 C. Vi在表结点中出现的次数 D. Vi度的一半 7. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A．空或只有一个结点B．深度等于其结点数 C．任一分支结点均无左子树D．任一分支结点均无右子树
软件技术基础考试复习题(含答案)
1、计算机系统与软件的关系：软件是计算机系统的一部分，体现了计算机应用能力与水平 2、软件的三层含义？个体含义：特指具体的软件；整体含义：个体含义的全体；学科含义：软件理论、 方法与技术所组成的学科。 3、软件特性：抽象性、知识性、复杂性、复用性。 4、软件分类？软件理论：算法理论与数据理论；软件系统：应用软件、支撑软件与系统软件；软件开发： 软件工程。 第二章 5、算法是一类问题过程的一种求解方法，该方法可用一组有序的计算机步骤或过程表示。 6、算法不是程序，算法高于程序。算法是程序的框架与灵魂，而程序是算法的实现。 7、算法的五大特征：能行性、确定性、有穷性、输入、输出。 8、算法的两大基本要素？算法的操作：四种基本操作（算法、逻辑、比较、传输）；算法的控制：三种基 本控制（顺序、选择、循环）。 9、四种常用的算法设计方法？枚举法：穷举所有可能的方法；递归法：自己调用自己的方法；分治法： 将问题分解成若干的方法；回溯法：试探性的求解方法。 10、算法的评价：算法的正确性；算法的时间效率分析；算法的空间效率分析。 11、算法的时间效率分析，用T（n）=O（f（n））表示,常用六种：常用阶O（l）；对数阶O（log2n）；线性阶O（n）；线性对数阶O（n log2n）.；平方阶（立方或K方阶）O（n2），O（n3），O（n k）；指数阶O （2n）。 12、六个完整算法表示：算法名、算法输入、算法输出、算法流程、算法正确性、算法分析 第三章 13、数据是按一定规则组织的符号串，并被识别。 14、数据是由数据结构与数据值组成。 15、数据的三个结构层次？客观世界：事物与事物之间的关联；逻辑世界：数据逻辑结构与逻辑值；物理世界：数据物理结构与物理值。 16、数据元素是命名的数据单位。 17、数据操作：数据操作的总称。 18、数据操作分为？数据值操作：定位、读及增加、删除、修改操作；数据结构操作：创建、删除、查询、修改操作。 19、数据结构：以（狭义）数据结构为核心所构成的数据与数据操纵的结合体，也广义结构。 20、数据的五个特征？时间角度分析：挥发性/持久性数据；使用广度分析：私有/共享数据；数据值性质分析：标量/集合量数据；数据量：大量/小量/海量数据；管理角度分析：严格/松散/不管理数据。 21、数据按特性分类？依赖型数据：不独立，依赖程序的数据；独立型数据：独立的数据组织、数据库数据；半独立数据：属操作系统、文件数据。 22、三类数据的不同使用方式？依赖型数据：程序直接调用；独立型数据：通过外部接口与程序关联；半独立型数据：通过内部接口与程序关联。 第四章 23、数据元素的概念：数据结构中不可以再分的基本数据单位。 24、数据的逻辑结构：从应用问题角度组织数据结构或用户数据视图；主要有线性结构、树和图三种结构。 25、数据的物理结构：数据在计算机存储器上存储结构；主要有顺序和链式存储结构。 26、线性表：数据元素只有后继关系的数据结构；顺序存储结构存储的线性表称为顺序表；链式存储结构存储的线性表称为链表；链表又有单链表、环链表和双向链表等。相关算法主要有插入、删除和查找。27、栈：是限制插入和删除只在同一端进行的线性表，也称为后进先出表；顺序存储结构的栈称为顺序栈；链式存储结构的栈称为链表；相关算法主要有压栈、弹栈和读栈等。 28、队列：是限制插入在一端、删除在另一端进行的线性表；顺序存储结构的队列称为顺序队列；首尾相
2020年春季考试《计算机软件技术基础(1)》在线考核试题_13.doc
1.有一函数Function F(ByVal a As Integer, ByVal b As Integer) As Integer,()在调用时将发生错误。 A.Call F(1, 2) B.Y = F(F(2, 3), 4) C.Z = F(2.3, 5) D.X = F(3) 【参考答案】: D 2.表达式1.5 + 3 \ 2 > 2 Or 7 Mod 3 < 4 的运算结果是()。 A.True B.0 C.1 D.False 【参考答案】: A 3.结构化程序设计所规定的三种基本控制结构是(?)。 A.输入、处理、输出 B.树形、网形、环形 C.顺序、选择、循环 D. 主程序、子程序、函数 【参考答案】: C 4.int(198.555*100+0.5)/100的值()。 A.是198 B.是199.6 C.是198.56 D.是200 【参考答案】: C 5.加载窗体时触发的事件是( )。 A.Click B.Load C.Gotfocus D.DoubleClick 【参考答案】: B 6.下面叙述不正确的是()。 A.一个控件只能有一个事件处理过程 B.用户与应用交互可以触发事 件 C.Visual https://www.wendangku.net/doc/971298763.html, 是集成了事件驱动的编程模型 D.即使用户与应用程序不进行交互，有些事件也可能发生 【参考答案】: A
7.设X=lO,y=7,表达式x\6+y*3的值为()。 A.24 B.22 C.25 D.0 【参考答案】: B 8.鼠标的移动触发()事件。 A.Click B.Mousedown C.MouseUp D.MouseMove 【参考答案】: D 9.在https://www.wendangku.net/doc/971298763.html,窗体第一次显示之前,下列()窗体事件发生。 A.Activated B.GotFocus C.Click D.Load 【参考答案】: D 10.文本框的( )属性用于设置或返回文本框中的文本内容。 A.Text B.(名称) C.Caption https://www.wendangku.net/doc/971298763.html, 【参考答案】: A 11.已知A$="12345678",则表达式Val(Mid(A, 1, 4) + Mid(A, 4, 2))的值为 ()。 A.123456 B.123445 C.8 D.6 【参考答案】: B 12.DrawArc方法绘制的图形是()。 A.圆 B.椭圆 C.弧 D.扇形 【参考答案】: C
《计算机软件技术基础》试题答案
《计算机软件技术基础》试题 1.线性表的链式存储结构与顺序存储结构相比优点是 CD 。 A. 所有的操作算法实现简单 B. 便于随机存取 C. 便于插入和删除 D. 便于利用零散的存储器空间 2.线性表是具有n 个 C 的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 E. 信息项 3.若长度为n 的线性表采用顺序存储结构，在其第I 个位置插入一个新元素的算法的时间复杂度为 C 。（1≤I ≤n+1） A. O(0) B. O(1) C. O(n) D. O(n 2 ) 4.设A 是一个线性表(a 1,a 2,…,a n )，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 B ，平均每删除一个元素需要移动的元素个数为 A ；若元素插在a i 与a i+1之间(0≤I ≤n-1)的概率为 ) 1() (2+-n n i n ，则平均每插入一个 元素所要移动的元素个数为 C ； A. 21 -n B. 2n C. 3 12+n D. 4 13+n 5.下列函数中，按它们在∞→n 时的无穷大阶数，最大的是 D 。 A. log n B. nlog n C. 2n/2 D. n!
6.将下图所示的s所指结点加到p所指的结点之后，其语句应为： D 。 A. s->next=p+1; p->next=s; B. (*p).next=s; (*s).next=(*p).next; C. s->next=p->next; p->next=s->next; D. s->next=p->next; p->next=s; 7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是 A 。 A. n B. 2n-1 C. n-1 D. 2n 8.下面的程序段是合并两个无头结点链表(ha和 hb)为一个无头结点链表ha的过程，作为参数的两个链表都是按结点的data域由大到小链接的。合并后新链表的结点仍按此方式链接。请填写下述空框，使程序能正确运行。 1. #define NULL 0 typedef struct node{ int data; struct node *next; }node, linklisttype; void combine(linklisttype *ha, linklisttype *hb){ linklisttype *h, *p; h = (linklisttype *)malloc(sizeof(linklisttype)); h->next = NULL; p = h;
大学计算机软件技术基础考试技术复习题
线性表采用链式存储时，结点的存储地址（）A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 由两个栈共享一个向量空间的好处是：（）A．减少存取时间，降低下溢发生的机率 B．节省存储空间，降低上溢发生的机率 C．减少存取时间，降低上溢发生的机率 D．节省存储空间，降低下溢发生的机率 对应的稀疏矩阵是（） A. 0806 7000 0000 5040 0000 - - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? B. 0806 7000 5040 0000 0300 - - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? C. 0806 0000 0200 5040 0000 - - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? D. 0806 0000 7000 5040 0300 - - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( ) A．4 B．5 C．6 D．7 一棵含18个结点的二叉树的高度至少为( C ) A.3 B.4 C.5 D.6 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( D ) A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 无向图中一个顶点的度是指图中( B ) A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数 C.通过该顶点的回路数 D.与该顶点连通的顶点数 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为( B ) A.21 B.23 C.41 D.62 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) A．e B．2e C．n2－e D．n2－2e 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
中国石油大学软件技术基础_复习题
线性表的习题 1．下述哪一条是顺序存储结构的优点？ A．插入运算方便 B．可方便地用于各种逻辑结构的存储表示 C．存储密度大 D．删除运算方便 2．下面关于线性表的叙述中，错误的是： A．线性表采用顺序存储，必须占用一片连续的存储单元 B．线性表采用顺序存储，便于进行插入和删除操作 C．线性表采用链式存储，不必占用一片连续的存储单元 D．线性表采用链式存储，便于插入和删除操作。 3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_______存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 4．链表不具有的特点是： A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 5．在n个节点的线性表的数组实现中，算法的时间复杂度是O(1) 的操作是： A．访问第i个结点和求第i个结点的直接前驱 B．在第i个节点后插入一个新节点 O(n) C．删除第i个节点 O(n) D．以上都不对 6．在一个以h为头的单循环链表中，p指针指向链尾的条件是： A．p->next==h B．p->next==null C．p->next->next==h D．p->data==-1 7．在非空双向循环链表中q所指的结点前插入一个由p所指的链结点的过程依次为：rlink(p)←q; llink(p)←llink(q);llink(q)←p;___________ A．rlink(q)←p; B．rlink(llink(q))←p; C．rlink(llink(p))←p;
计算机软件基础试题
《软件技术基础》试题库 课程名称：软件技术基础 适用专业：软件技术、计算机应用、网络、信息等计算机相关专业第一章概述 第二章数据结构 一、单项选择题 1．若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动_______个数据元素。( ) A. n-i B. n+i C. n-i-1 D. n-i+1 答案：A 2．在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行________。( ) A. link(s)←link(p)，link(p)←s B. link(q)←s，link(s)←p C. link(p)←link(s)，link(s)←p D. link(p)←s，link(s)←q 答案：B 3．高度为h(h>0) 的二叉树最少有________个结点。（） A. h B. h-1 C. h+1 D. 2h 答案：A 4．n个顶点的带权无向连通图的最小生成树包含________ 个顶点。（） A.n-1 B.n C.n/2 D.n+1 答案：B
5．采用拉链法解决冲突的散列表中，查找的平均查找长度( )。 A. 直接与关键字个数有关 B. 直接与装填因子a 有关 C. 直接与表的容量有关 D. 直接与散列函数有关 答案：D 6．树型结构最适合用来描述( ) A.有序的数据元素 B.无序的数据元素 C.数据元素之间的具有层次关系的数据 D.数据元素之间没有关系的数据 答案：C 7．若二叉树中度为2的结点有15个，度为1的结点有10个_______个叶结点。( ) A.25 B.10 C.16 D.41 答案：C 8．若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有______个结点。( ) A.32 B.33 C.34 D.25 答案：C 9．若某完全二叉树的深度为h，则该完全二叉树中至少有______个结点。( ) A.2h B.2h-1 C.2h-2 D.2h-1+1 答案：C 10．在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该( ) A.只有左子树上的所有结点 B.只有左子树上的部分结点 C.只有右子树上的所有结点 D.只有右子树上的部分结点 答案：A 11．下面关于哈夫曼树的说法，不正确的是( ) A.对应于一组权值构造出的哈夫曼树一般不是唯一的 B.哈夫曼树具有最小带权路径长度
软件技术基础复习题
一、填空 1、 软件。 2、 输出特性是算法的五大基本特征。 3 4、 成。 5、 6、 7、 8oracle 9、MFC是 的形式封装了windows的API。 年代结构化编程语言尚未风行时表达算法的设计工具。 14 15、空间复杂度是度量算法所需存储空间的大小，一个2×3的矩阵，其空间复杂度为 16 二、选择 1、若让元素1、 2、 3、4依此进栈，则这次出栈的次序不可能出现的情况是D A 3214 B2143 C 4321 D1423 2、一棵深度为5的完全二叉树中的结点最多为B个 A30 B31 C32 D33 3、在一个单链表中，若要在指针q所指结点的后面删除一个由指针p所指向的结点，则执行A操作 A q→next=p→next ；free（p） B p→next= q→next；free（p） C q→next= p→next；p→next=q； D p→next= q→next；q→next=p 4、在排序法中，每次从待排序序列中取出最小的一个元素，将其放入主排序序列中的方法称为A A 选择排序B快速排序C插入排序D 冒泡排序 5、在软件工程中，只根据程序功能说明而不关心程序内部逻辑的方法，称为B测试 A 白箱B黑箱C 红箱D 综合 6下列文件类型不属于图像媒体文件格式的是A A .MP3 B .bmp C .jpg D .tif 7、软件开发的过程模型中，其各个阶段如同多级瀑布，层层下流，一次完成的过程模型是A
A 瀑布模型 B 原型模型 C 螺旋模型D构建组装模型 8、图的数据元素之间的关系是B A 一对一 B 一对多 C 多对多 D 都不是 9、已知一个顺序存储的线性表，设每个节点需要占m个存储单元，若第一个结点的地址为ad，则第i个结点的地址为A A ad+（i-1）*m B ad+i*m C ad-i*m D ad+（i+1）*m 10、真彩色图像是指24位彩色图 11、数据库的访问技术是通过标准接口来实现的，下列不是常用接口的是A A EOF B ADO C OLEDB DODBC 12、SQL按功能可分为四大部分，其中下面哪一动词用来实现数据操作功能的？A A、SELECT B、CREATE C、INSERT D、GRANT 13、下列不属于音频媒体格式的是bmp 14、下列哪一项不是安德斯海尔斯伯格的主要工作。主持C++开发工作 15、在一个任意二叉树中若有n0个叶子结点，n2个长度为2的结点，则n0和n2之间的关系是 16、若一个顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是108无向图请移步百度百科。不谢。 三、简答 1、数据结构的三要素是什么？ 答：数据元素、逻辑结构、存储结构 2、简述数据库的三级模式结构和两级映像功能。 数据库系统的三级模式结构是指数据库系统由外模式，模式，内模式三级构成，两级映像是指外模式/模式映像，模式/内模式映像，这两层映像保证了数据库系统中的数据能具有较高的逻辑独立性和物理独立性。 3、什么是多媒体？多媒体技术包括哪些技术？ 答：多媒体就是通过计算机技术把文字、图形、图像、音频、视频等信息表示元素集成起来而形成的一种新的数字化信息媒体。包括音频技术、视频技术、图像技术、存储技术。 4、传统意义上的软件可分为几类？简述软件和程序的区别。 答：传统意义上的软件可分为系统软件和应用软件。程序是指为了完成某项或几项任务而被开发并运行在操作系统上的。而软件是指程序与与其相关的文档或从属物的集合，一般视程序为软件的一部分。 5、主要的编译过程包括哪些？简要分析其任务。(标记) 数据结构: 分析和综合时所用的主要数据结构，包括符号表、常数表和中间语言程序 分析部分: 源程序的分析是经过词法分析、语法分析和语义分析三个步骤实现的 综合部分: 综合阶段必须根据符号表和中间语言程序产生出目标程序，其主要工作包括代码优化、存储分配和代码生成 结构: 编译过程分为分析和综合两个部分，并进一步划分为词法分析、语法分析、语义分析、代码优化、存储分配和代码生成等六个相继的逻辑步骤 6、已知一组数据｛49，38，65，97，76，13，27，53｝，试写出其各走向冒泡排序过程，并详细阐述一趟排序过程。 #include"stdio.h" int a[]={49,38,65,97,76,13,27,59}; main() {int i,j,k,temp; for(i=0;i