2002年上海华东师范大学编译原理考研真题.doc

发布时间：2022-09-19 发布人：admin 分类：说明书资料大小：1.12M 资料格式：doc 举报版权申诉

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

文本预览

2002 年上海华东师范大学编译原理考研真题一、是非题与选择题（10 分） 1.对任意一个三型文法 G，都存在一个不确定有限状态自动机 M，满足 L(G)=L(M). ( ) 2.对任意一个三型文法 G，都存在一个确定有限状态自动机 M，满足 L（G）=L（M）.（） 3.对任意一个正则表达式 E，都存在一个不确定有限状态自动机 M，满足 L(G)=L(E).( ) 4.对任意一个正则表达式 E，都存在一个确定有限状态自动机 M，满足 L(G)=L(E).( ) 5. 对任意一个二型文法 G，都存在一个不确定下推自动机 M，满足 L（G）=L（M）.（） 6.对任意一个二型文法 G，都存在一个确定下推自动机 M，满足 L（G）=L（M）.（） 7.____不是有限状态自动机的成分。 A.输入字符表 B.输出字符表 C.有限状态集 D.最终状态集 8..____不是编译程序的组成部分。 A.词法分析程序 B.句法分析程序 D.设备管理程序 C.代码生成程序 9.对程序∶ A. call by reference B. B. Call by name C. call by value D.A， B，C 中的二种

E. 都不是 A.0 型 B.1 型 C.2 型 D.3 型

一.多重选择填空题（每小题 3 分，共 30 分。每道小题的都可能有一个以上的正确选项，须选出所有的正确答案，不答不得分，多选、少选或选错都将按比例倒扣。） A. 数组 B.线性表 C. 环形队列 D.拟满树 2. 下列内部排序算法中，（）是稳定的。 A.冒泡排序 B.选择排序 C. 快速排序 D. 插入排序 :E. 合并排序 3.将一棵有序树转换成一棵二叉树时，有序树的根结点的第二棵子树的根结点成为该二叉树时根结点的（）的根结点。 A.左子树 B.左儿子的右子树 C.右子树 D.右儿子的左子树 4.在对一个 5 阶 B 树删除一个键值 K 时，如键值 K 在结点 C 中，C 是叶子层上一层的结点，且 C 不是树根，C 中原有（）个键值，则只需在 C 中删除 K 即可，不必对树作其它调整。 A.1 C.3 B. 2 D.4 E.5 5.下列算法中，（）算法的平均时间复杂性是 0（nlogn）（n 是问题的规模）。 A. 选择排序 B.快速排序 C.模式匹配的 KMP D.Hash 查找 E.二分查找 6.下列二叉数树中，（）是查找树。

7.在一棵有 n 个叶结点的 Huffman 树中，总共有（）个结点。 A. 2n-2 B. 2n-1 C.2n D.2n+1 8.带表头的链表与不带表头的链表相比较，带表头的链表具有（）的特点。 A. 插入算法的时间复杂性较小 B.插入算法的执行时间较短 C.插入算法的 C 程序较复杂 D.所需存储空间较少 9.在 KMP 模式匹配算法中，对模式'abcaabbabcab'用 KMP 算法求得的第 11 个字符（'a'）的失败链接值是（）。 10.设一个有 8 个结点的无向图，其结点分别为 a、b、c、d、e、f、g 和 h，它的邻接矩阵如下，若从结点 a 开始进行深度优先遍历，则下列结点序列中（）是可能得到的结点序列。二.假设有一用单链表实现的线性表 L，L 中的元素都是整数。请编写一 C 函数，将 L 分为两个线性表 L1 和 L2，L1 和 L2，仍以单链表实现，L 保持不变;L1 中的元素由 L 中所有元素值小于其序号的元素构成，且 L1 中的元素的相对次序与 L 中的相应元素的相对次序相同;L2 中的

元素由 L 中所有元素值不小于其序号的元素构成，且 L2 中的元素的相对次序与 L 中的相应元素的相对次序相同。（10 分）三．假定二叉树 T 中，各结点中的值都是整数，且两两互不相等。请编一 C 函数，从 T 的中序和后序（分别存于两整数数组），构造出以标准形式存储的二叉树 T。（10 分）

分享到：

赞收藏

资料库

2002年上海华东师范大学编译原理考研真题.doc

相关推荐

考研

热门标签

最新资料