选择题
在形式语言中，方法G是一个四元组G=(VN，Vr，P，Z),其中VN为(1)。若方法G的产生式集P为： (1)Z→Bc (2)Z→Zc (3)B→Ab (4)B→Bb (5)A→Aa (6)A→a 则文法G是(2)文法，识别G的自动机为(3)。对于G来说，(4)为文法G可接受的字符串，(5)为文法G不可接受的字符串。
(1)
A.状态标志符
B.开始符
C.语句集
D.非终结符集合
(2)
A.短语
B.上下文有关
C.上下文无关
D.正则
(3)
A.图灵机
B.下推自动机
C.有穷状态自动机
D.线性界限自动机
(4)
A.aaabc
B.acbb
C.acbcab
D.acbbca
(5)
A.abbcc
B.acbc
C.aaabc
D.aabbccc
自底向上的估计法的特点是(6)
(6)
A.简单、工作量小、误差大
B.精度高，但缺少子任务(模块)间的联系
C.估算较精确，但区分类比较困难
D.复杂、不可行，一般不采用此种方法，但这种副作用可以通过详细的设计文档加以控制
以下属于选择类排序法的是(7)
(7)
A.堆栈排序法
B.插入排序法
C.冒泡排序法
D.快速排序法
下列对关系的叙述中(8)不正确的
(8)
A.关系中的每个属性是不可分解的
B.在关系中元组的顺序是无关紧要的
C.任意的一个二维表都是一个关系
D.在关系中任意两个元组不能完全相同
对于“指针”和“链”，下面的说法正确的是，(9)
(9)
A.它们是数据物理组织的两种形式
B.它们是数据逻辑组织的两种形式
C.它们是数据物理组织的两种基本工具
D.它们是数据逻辑组织的两种基本工具
甲、乙同为生产锂电池的厂家。甲得知乙研制出改进锂电池质量的技术戾窍后，遂以不正当方式获取了该技术，并加以利用。甲厂侵害了乙厂的(10)
(10)
A.技术秘密权
B.专利权
C.专利申请权
D.经营信息权
参考答案：
1—5 D，D，C，A，B 形式语言首先于1956年由Chomsky进行描述。该理论讨论了语言与文法的数学理论，按照对文法规则的不同定义形式，对语言和文法进行了分类。一般来说，Chomsky文法是一个四元组G=(VN,Vr,P,Z),其中VN为非终结符集合，Vr为由终结符组成的字母表集合，P是穷非空的重写规则集合，Z是识别符号。文法G对应的语言是能从该文法的识别符号产生的那些终结符号串(句子)组成的集合。
简单来说，对于文法的分类分为4类：
O型文法也称短语结构文法可以由图灵机识别。
1型文法也乐上下文有关文法，可以由线性界限自动机识别。
2型文法也称上下文无关文法，可以由下谁自动机识别。
3型文法也称正则文法可以由有穷状态自动机识别。
具体的文法定义可以参照编译原理中的相关概念。
某种文法可以接受的句子经过简单推理即可。
6、B 自底向上的估计法：这种方法的主要思想是把待开发的软件细分，直到每一个子任务都已经明确所需要的开发工作量，然后把它们加起来，得到软件开发的总工作量。这是一种常见的估算方法。它的优点是估算各个部分的准确性高。缺点是缺少各项子任务之间相互间的联系。
7、A 排序是数据处理中经常使用的一种重要运算。包括插入排序，交换排序，选择排序，分配排序等。选择排序的基本方法是：每步从待排序的记录中选出排序码最小的记录，顺序入在已排序的记录序列的最后，直到全部排完。通常包括，直接选择排序，树形选择排序和堆栈选择排序。
8、C 本题考查关系的基本概念。通常来说，一组域的笛卡儿积可以表示为一个二维表。表中的行对应一个元组，表中的每列对应一个域。而关系则是笛卡儿积的子集，换而言之，关系必须是满足一定意义的二维表。关系通常来说要满足几条基本性质，其中，列也就是属性顺序无所谓，但是必须是不可以分解的，元组也就是行的顺序无所谓但不能完全相同，分是必须取原子值等等。
9、D “指针”和“链”是数据逻辑组织的两种基本工具。
10、A 由题可知甲厂侵害了乙雨季的技术秘密权
