编译原理复习题一、是非题1．计算机高级语言翻译成低级语言只有解释一种方式。
(×)3．每个文法都能改写为 LL(1) 文法。
(×)4．算符优先关系表不一定存在对应的优先函数。
(√)5．LR分析方法是自顶向下语法分析方法。
(×)6．“ 用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。
(× )7．一个句型的句柄一定是文法某产生式的右部。
(√)8．仅考虑一个基本块，不能确定一个赋值是否真是无用的。
(√ )9．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。
(× )10．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。
(×)11．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。
(× ) 12．递归下降分析法是自顶向下分析方法。
(√ )13．产生式是用于定义词法成分的一种书写规则。
(×)14．在SLR(1)分析法的名称中，S的含义是简单的。
(√)15．综合属性是用于“ 自上而下” 传递信息。
(× )16．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。
(×)17．程序语言的语言处理程序是一种应用软件。
(×)18．解释程序适用于COBOL 和FORTRAN 语言。
(×)19．一个LL(l)文法一定是无二义的。
(√)20．正规文法产生的语言都可以用上下文无关文法来描述。
(√)21．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。
(×)22．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。
(√)22．逆波兰法表示的表达式亦称后缀式。
(√ )23．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。
(√ )24．数组元素的地址计算与数组的存储方式有关。
中南大学现代远程教育课程考试（考试）复习题及参考答案数据结构(使用教材：余腊生编著，人民邮电出版社出版，《数据结构—基于C++模板类的实现》一、判断题1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
[ ] 2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。
[ ]3．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
[ ] 4．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。
[ ] 5．一个广义表的表尾总是一个广义表。
[ ] 6．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
[ ] 7．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。
[ ] 8．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。
[ ] 9．直接选择排序是一种稳定的排序方法。
[ ] 10．30、闭散列法通常比开散列法时间效率更高。
[ ] 11．有n个结点的不同的二叉树有n!棵。
[ ] 12．直接选择排序是一种不稳定的排序方法。
[ ] 13．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。
[ ] 14．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。
[ ] 15．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。
[ ] 16．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。
在设计再散列函数时，要求计算出的值与表的大小m互质。
[ ] 17．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。
[ ] 18．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。
