计算理论导引--研究生考试试卷格式

2018年全国硕士研究生入学统一考试计算机学科专业基础综合试卷一、单项选择题：140小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

b5E2RGbCAP 1．已知程序如下：ints(int n>{ return (n<=0> ? 0 : s(n-1> +n。

}void main(>{ cout<< s(1>。

}程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main(>->S(1>->S(0> B．S(0>->S(1>->main(>p1EanqFDPwC．main(>->S(0>->S(1> D．S(1>->S(0>->main(>DXDiTa9E3d【参考答案】 D【考查知识点】栈的基本概念和函数调用的原理。

2．先序序列为a,b,c,d的不同二叉树的个数是A．13B．14C．15D．16【参考答案】 C【考查知识点】二叉树的基本概念。

3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和 24，10，7B．24，10，5和24，12，7C．24，10，10和 24，14，11 D．24，10，5和 24，14，6【参考答案】 C【考查知识点】哈夫曼树的原理。

4．现在有一颗无重复关键字的平衡二叉树<AVL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是RTCrpUDGiTA．根节点的度一定为2B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树【参考答案】 B【考查知识点】树的中序遍历和AVL树的基本概念。

5．设有向图G=(V,E>，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是5PCzVD7HxAA．2 B．3 C．4 D．5【参考答案】 D【考查知识点】图的深度优先遍历。

2018年硕士研究生统一入学考试《信号与系统》第一部分考试说明一、考试性质信号与系统是信息学院通信与信息系统、信号与信息处理、电子与通信工程学科硕士研究生入学考试的专业基础课。

考试对象为参加东北大学计算机科学与工程学院2018年全国硕士研究生入学考试的准考考生。

二、考试形式与试卷结构（一）答卷方式：闭卷，笔试（二）答题时间：180分钟（三）考试题型及比例基本概念解释15%选择填空 25%计算题30%应用题 30%（四）参考书目郑君里、应启珩、杨为理《信号与系统》 (第三版) 上、下册高等教育出版社 2011.03第二部分考查要点（一）基本概念1、信号的描述、分类和典型示例2、阶跃信号与冲激信号3、信号的分解4、系统的模型及分类（二）连续时间系统的时域分析1、微分方程式的建立与求解2、零输入响应和零状态响应3、冲激响应与阶跃响应4、卷积5、卷积的性质（三）连续时间系统的频域分析1、周期信号的傅立叶分解2、典型周期信号的傅立叶级数3、傅立叶变换4、典型非周期信号的傅立叶变换5、冲激函数和阶跃函数傅立叶变换6、傅立叶变换的基本性质7、卷积特性8、周期信号的傅立叶变换9、抽样信号的傅立叶变换10、抽样定理（四）拉普拉斯变换、连续时间系统的S域分析1、拉普拉斯变换的定义、收敛域2、拉普拉斯变换的性质3、拉普拉斯反变换4、用拉普拉斯变换分析电路、S域元件模型5、系统函数H(s)6、由系统函数的零极点分布决定时域特性7、由系统函数零极点分布决定濒响特性8、连续系统稳定性9、双边拉氏变换10、拉氏变换与付氏变换的关系（五）付里叶变换应用于通信系统1、利用系统函数H(jw)求响应2、无失真传输3、理想低通滤波器4、调制与解调（六）离散系统时域分析1、离散时间信号2、离散时间系统数学模型－差分方程3、常系数线性差分方程的求解4、离散时间系统的单位样值响应5、离散时间系统卷积和（七）Z变换、离散时间系统的Z域分析1、Z变换的定义、典型序列的Z变换2、Z变换的收敛域3、反Z变换4、Z变换的基本性质5、Z变换与拉拉氏变换的关系6、利用Z变换解差分方程7、离散系统函数H(Z)。

2019年全国硕士研究生招生考试佛山科学技术学院自命题考试科目考试大纲（科目名称：物理化学科目代码：804）一、考查目标本考试大纲适用于报考佛山科学技术学院材料科学与工程专业的硕士研究生入学考试。

该科目主要考查考生对与材料科学与工程相关的物理化学基本知识的掌握程度，以判别考生是否具备从事科研工作的能力和发展潜力。

考生应系统复习本课程考察范围的内容，重点掌握基本概念和基本原理，并具有一定的综合运用所学知识分析和解决实际问题的能力。

二、考试形式与试卷结构1、考试方式：书面笔答。

2、卷面总分：150分。

3、考试时间：180分钟。

4、试卷主要题型可能有：是非题、选择题、简答题、计算题、综合题。

三、考查范围（一）热力学第一定律及应用1、热力学第一定律2、可逆过程及可逆体积功的计算3、恒容热、恒压热及焓4、热容及恒容变温过程、恒压变温过程热的计算5、气体可逆膨胀、压缩过程，理想气体绝热过程及绝热可逆过程方程6、标准摩尔反应焓7、化学反应热的计算、标准摩尔生成焓和标准摩尔燃烧焓8、化学反应热与温度的关系考试要求：掌握热力学主要基本概念，如体系、环境、功、热、状态函数等。

掌握热力学第一定律和内能的概念及热力学第一定律的数学表达式；熟练应用热力学第一定律计算理想气体在等温、等压、绝热过程中的△U、△H、Q和W。

熟练应用生成焓、燃烧焓计算反应热。

掌握赫斯定律。

了解摩尔定压热容和摩尔定容热容的概念。

（二）热力学第二定律1、自发过程特征、热力学第二定律的经典表述及本质2、熵的定义、克劳修斯不等式、熵增原理、及熵判据3、环境熵变、理想气体PVT变化熵变4、亥姆霍兹自由能、吉布斯自由能函数的定义、物理意义和变化值的计算，变化的方向和平衡条件5、热力学基本方程和麦克斯韦关系式6、单组分体系的两相平衡——热力学对单组分体系的应用考试要求：掌握热力学第二定律的意义、热力学第二定律与卡诺定理的联系。

理解克劳修斯不等式。

掌握热力学函数U、H、S、F、G的定义及其物理意义。

>>1251 2019年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题 一、单项选择题：1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合试题要求。

1.设n 是描述问题规模的非负整数，下列程序段的时间复杂度是x=0；while(n>=(x+1)*（x+1))x=x+1； A.O (log n ) B.O (n 1/2) C.O (n ) D.O (n 2)2.若将一棵树T 转化为对应的二叉树BT ，则下列对BT 的遍历中，其遍历序列与T 的后根遍历序列相同的是A.先序遍历B.中序遍历C.后序遍历D.按层遍历3.对n 个互不相同的符号进行哈大曼编码。

若生成的哈夫曼树共有115个结点．则n的值是A.56 B.57 C.58 D.604.在任意一棵非空平衡二叉树(AVL 树)T 1中，删除某结点v 之后形成平衡二叉树T 2，再将v 插入T 2形成平衡二叉树T 3。

下列关于T 1与T 3的叙述中，正确的星I.若v 是T 1的叶结点，则T 1与T 3可能不相同 Ⅱ.若v 不是T 1的叶结点．则T 1与T 3一定不相同 Ⅲ.若v 不是T 1的叶结点，则T 1与与T 3一定相同 A.仅I B.仅Ⅱ C.仅I 、Ⅱ D.仅I 、Ⅲ5.下图所示的AOE 网表示一项包含8个活动的工程。

活动d 的最早开始时问和最迟开始时间分别是126<<A.3和7B.12和I2C.12和14D.15和156.用有向无环图描述表达式(x+y)*((x+y)／x)，需要的顶点个数至少是A.5B.6C.8D.97.选择一个排序算法时,除算法的时空效率外，下列因素中，还需要考虑的是I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性Ⅳ.数据的初始状态A.仅ⅢB.仅I、ⅡC.仅Ⅱ、ⅢIVD.I、Ⅱ、Ⅲ.IV8.现有长度为11且初始为空的散列表HT，散列函数是H(key)=key％7，采用线性探查(线性探测再散列)法解央冲突。

东华大学2017~2018学年第一学期研究生期末考试试题考试学院：计算机考试专业：计算机科学与技术考试课程名称：计算理论导引与算法复杂性一、单项选择题（每空2分，本题共20分）1.关于集合S中的元素x，（）的说法是正确的。

A、x⊆SB、x可能是一个集合C、x在S中的顺序不能改变D、（x,x）∉S⨯S2.关于函数f，（）的说法是正确的。

A、f的值域一定是可数的B、f的定义域和值域的交集一定是空集C、f的值域不可能为{TRUE,FALSE}D、f的定义域可以是元组的集合3.关于正则语言R，（）的说法是正确的。

A、R是上下文无关的B、R是不能用正则表达式来描述的C、R是可以违反泵引理的D、R是图灵可识别但不可判定的4.关于乔姆斯基范式，（）的说法是错误的。

A、规则的右部可以是变量与终结符构成的串B、左部是起始变量的规则，其右部可以是εC、任意一个上下文无关文法都可以转化为乔姆斯基范式形式D、终结符一定单独出现在规则的右部5.关于下推自动机PDA，（）的说法是正确的。

A、PDA可以识别上下文无关语言B、PDA是DFA的一种特例C、PDA识别的语言NFA也能识别D、PDA的存储容量与GNFA相同6.关于图灵机M，（）的说法是正确的。

A、M一定是可停机的B、M识别的语言一定是可判定的C、M可以不识别任何语言D、M的存储容量比PDA大7.关于图灵不可识别语言L，（）的说法是错误的。

A、没有图灵机可识别LB、没有PDA可识别LC、L不能用正则表达式来描述D、目前L是否存在还是个未解之谜8.关于图灵不可判定语言L，（）的说法是错误的。

A、如果L是图灵可识别，那么，L一定是图灵不可识别的B、L一定是图灵可识别的C、如果L是图灵不可识别的，那么，L有可能是图灵可识别的D、如果L是图灵不可识别的，那么，L有可能是图灵不可识别的9.关于属于NP类的语言L，（）的说法是正确的。

A、L有可能属于P类B、L不能多项式时间规约到某个NP-complete语言C、如果NP类中所有语言都能多项式时间规约到L，那么，L是NP-hardD、L不可能是NP-complete10．关于PSPACE-hard语言L，（）的说法是正确的。

2019年全国硕士研究生招生考试佛山科学技术学院自命题考试科目考试大纲（科目名称：物理光学科目代码：803）一、考查目标物理光学是佛山科学技术学院光学工程研究生入学考试科目之一。

本科目的考试内容为物理光学中的干涉、衍射和偏振。

要求考生：（1）理解和掌握光波干涉、衍射和偏振的基本概念、原理、定律；（2）具备一定的分析问题和解决问题的能力；（3）具备一定的逻辑推理能力。

二、考试形式与试卷结构（一）试卷成绩及考试时间本试卷满分为150分，考试时间180分钟。

（二）答题方式答题方式为闭卷、笔试。

（三）试卷内容结构光的干涉60分光的衍射50分光的偏振40分光的干涉内容所占分值为：1.波动的独立性、叠加性和相干性15分左右2．单色波叠加所形成的干涉图样，10分左右3．分波面双光束干涉，5分左右4．等倾干涉和等厚干涉，20分左右5.迈克尔逊干涉仪,10分左右光的衍射部分内容所占分值为：1.惠更斯-菲涅尔原理，10分左右2．菲涅尔衍射，10分左右3．夫琅禾费单缝衍射，15分左右4．夫琅禾费圆孔衍射，5分左右5．平面衍射光栅，10分左右光的偏振部分内容所占分值为：1.自然光与偏振光，5分左右2.线偏振光与部分偏振光，15分左右3.单轴晶体的双折射现象，10分左右4.椭圆偏振光和圆偏振光，10分左右（四）试卷题型结构1.填空题：10小题，共20分2.简答题：10小题，共100分3.计算题：3小题，共30分（说明：以上题型及分值分配仅作参考，根据需要可作调整）三、考查范围一．光的干涉：1.波动的独立性、叠加性和相干性（1）电磁波的传播速度和折射率（2）光的强度（3）机械波的独立性和叠加性2.由单色波叠加所形成的干涉图样（1）相位差和光程差（2）干涉图样的形成3.分波面双光束干涉获得稳定干涉图样的条件4．分振幅薄膜干涉（1）等倾干涉（2）等厚干涉5.迈克尔逊干涉仪二．光的衍射：1.惠更斯-菲涅尔原理（1）光的衍射现象（2）惠更斯原理（3）惠更斯-菲涅尔原理2．菲涅尔衍射（1）菲涅尔半波带（2）合振幅的计算3．夫琅禾费单缝衍射（1）夫琅禾费衍射实验装置和衍射图样的特点（2）衍射图样的光强分布（3）单缝衍射图样的特点4．夫琅禾费圆孔衍射（1）夫琅禾费圆孔衍射图样特点5．平面衍射光栅（1）光栅衍射的强度分布（2）光栅方程三．光的偏振：1.自然光与偏振光（1）光的偏振性（2）自然光和偏振光2.线偏振光与部分偏振光（1）马吕斯定律（2）反射光的偏振态（3）透射光的偏振态3.单轴晶体的双折射现像（1）双折射现象（2）光轴、主平面与主截面（3）O光和e光的相对光强4.椭圆偏振光和圆偏振光（1）椭圆偏振光和圆偏振光的描述（2）椭圆偏振光和圆偏振光的获得。

2015年全国硕士研究生入学统一考试计算机学科专业基础综合试题一、单项选择题：140小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

1．已知程序如下：int s(int n){ return (n<=0) ? 0 : s(n-1) +n; }void main(){ cout<< s(1); }程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main()->S(1)->S(0) B．S(0)->S(1)->main()C．m ain()->S(0)->S(1) D．S(1)->S(0)->main()2．先序序列为a,b,c,d的不同二叉树的个数是A．13 B．14 C．15 D．163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和24，10，7 B．24，10，5和24，12，7C．24，10，10和24，14，11 D．24，10，5和24，14，64．现在有一颗无重复关键字的平衡二叉树（A VL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是A．根节点的度一定为2 B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树5．设有向图G=(V,E)，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A．2 B．3 C．4 D．56．求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（kruskal）算法第二次选中但不是普里姆（Prim）算法（从V4开始）第2次选中的边是A．(V1,V3) B．(V1,V4) C．(V2,V3) D．(V3,V4)7．下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508．已知字符串S为“abaabaabacacaabaabcc”. 模式串t为“abaabc”, 采用KMP算法进行匹配，第一次出现“失配”(s[i] != t[i]) 时，i=j=5,则下次开始匹配时，i和j的值分别是A．i=1，j=0 B．i=5，j=0 C．i=5，j=2 D．i=6，j=29．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是A．直接插入排序B．起泡排序C．基数排序D．快速排序10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是A．1 B．2 C．3 D．411．希尔排序的组内排序采用的是（）A．直接插入排序B．折半插入排序 C．快速排序D．归并排序12．计算机硬件能够直接执行的是（）Ⅰ．机器语言程序Ⅱ．汇编语言程序Ⅲ．硬件描述语言程序A．仅ⅠB．仅ⅠⅡC．仅ⅠⅢD．ⅠⅡⅢ13．由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（）A．-126 B．-125 C．-32 D．-314．下列有关浮点数加减运算的叙述中，正确的是（）Ⅰ. 对阶操作不会引起阶码上溢或下溢Ⅱ. 右规和尾数舍入都可能引起阶码上溢Ⅲ. 左规时可能引起阶码下溢Ⅳ. 尾数溢出时结果不一定溢出A．仅ⅡⅢB．仅ⅠⅡⅣC．仅ⅠⅢⅣD．ⅠⅡⅢⅣ15．假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（Write Back）方式，则能存放4K字数据的Cache 的总容量的位数至少是（）A．146k B．147K C．148K D．158K16．假定编译器将赋值语句“x=x+3;”转换为指令”add xaddt, 3”，其中xaddt是x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB，且Cache使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（）A．0 B．1 C．2 D．317．下列存储器中，在工作期间需要周期性刷新的是（）A．SRAM B．SDRAM C．ROM D．FLASH18．某计算机使用4体交叉存储器，假定在存储器总线上出现的主存地址（十进制）序列为8005，8006，8007，8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲突的地址对是（）A．8004、8008 B．8002、8007 C．8001、8008 D．8000、800419．下列有关总线定时的叙述中，错误的是（）A．异步通信方式中，全互锁协议最慢B．异步通信方式中，非互锁协议的可靠性最差C．同步通信方式中，同步时钟信号可由多设备提供D．半同步通信方式中，握手信号的采样由同步时钟控制20．若磁盘转速为7200转/分，平均寻道时间为8ms,每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是( )A．B．C．D．21．在采用中断I/O方式控制打印输出的情况下，CPU和打印控制接口中的I/O端口之间交换的信息不可能是( )A．打印字符B．主存地址C．设备状态D．控制命令22．内部异常(内中断)可分为故障(fault)、陷阱(trap)和终止(abort)三类。

一、单项选择题（每空2分，本题共20分）1．集合A DFA={<B,w>|B是DFA，w是串，B接受w}可用来（A）。

A、描述“DFA B 是否接受输入w”这一问题B、解决“P=NP？”问题C、计算语言A DFA时间复杂度D、计算语言A DFA的空间复杂度2．一个集合在条件（ D ）下是可数的。

A、该集合为无限集合B、组成该集合的元素是实数C、该集合的规模大于自然数集合的规模D、该集合是一个有限的集合3．对于一个语言（ D ）的说法是正确的。

A、它是一个序列B、它是一个简单串或复杂串C、在集合并运算下它是封闭的D、不是所有的语言都能被图灵机识别4．如果A≤m B且B是可判定的，则（A）。

A、A也是可判定的B、A不一定是可判定C、A是不可判定的D、A可判定否与B无关5．若一个图灵机M时间复杂度为2n3+6n+7。

则其渐进时间复杂度为( C ）。

A、O(2n3+6n+7)B、O(2n3+6n)C、O(n3)D、o(n3)6. 时间复杂性类TIME(t(n))是（ C ）。

A、时间复杂度为t(n)的图灵机集合B、时间复杂度为O(t(n))的图灵机集合C、由O(t(n))时间的图灵机判定的所有语言的集合D、由o(t(n))时间的图灵机判定的所有语言的集合7．当(A）时，P=NP。

A、语言B是NP完全的且B∈PB、计算速度快到一定峰值时C、计算机内存达到无限D、计算机性价比很高时8. 如果A是NP-完全的，则( C )。

A、一定存在一个B∈NP且B不能多项式时间规约到AB、A不一定属于NPC、A一定属于NPD、若A∈P，则P≠NP9. 对于SAT问题（ C ）的说法是对的。

A、SAT问题不能用线性空间算法解决B、SAT∉PSPACEC、SAT∈PSPACED、SAT∉NP10．如果B是PSPACE完全的，则（C）。

A、B∉NPSPACEB、B∈PC、B∈PSPACED、B一定是NP完全的二、综合应用题(10分+10分+10分+10分+10分,本题共50分)1.将一个DFA与一个正则表达式是否等价问题用一个语言来描述，然后，证明该语言是1可判定的。

定义概念题目：第三章：1. 图灵机：是一种精确的通用计算机模型，能模拟实际计算机的所有计算行为，它的核心是转移函数δ，它说明了机器如何从一个格局走到下一个格局。

对于图灵机，δ的形式如下：Q×Γ→Q×Γ{L,R},图灵机是一个7元组（Q，∑，Γ，δ，q 0,q accept,q reject）.其中Q，∑，Γ都是有穷集合，并且1）Q是状态集；2）∑是输入字母表，不包括特殊空白符号凵，3）Γ是带字母表，其中凵∈Г，∑∈Г4）δ2. 格局：图灵机的计算过程中，当前状态，当前内容和读写头当前位置组合在一起。

例如：1011q701111：当前状态q7，当前读写头位置在第二个0上。

定义3.2 如果一个语言能被某一个图灵机识别，则称该语言是图灵可识别的（递归可枚举语言）定义3.2 如果一个语言能被某一个图灵机判定，则称该语言是图灵可判定的简称可判定的（递归语言）3.图灵机的变形：多带图灵机、非确定型图灵机、枚举器。

每个4.枚举器：他是图灵机的一种变形，是带有打印机的图灵机，图灵机把打印机当作输出设备，从而可以打印串，每当图灵机想在打印序列中增加一个串时，就把此串送到打印机。

一个语言是图灵可识别的，当且仅当有枚举器枚举它。

5.图灵机的术语：形式化描述，实现描述，高水平描述。

第四章：1.可判定的语言有：（A DFA、A NFA、A REX、E DFA、EQ DFA 是正则语言）、（A CFG、E CFG 是上下无关语言）❶每个上下文无关语言都是可判定的。

2.不可判定的语言有:：EQ CFG、A TM 、停机问题、HALT TM 、E TM、REGULAR TM 、EQ TM 、 E LBA 、ALL CFG 、PCPA TM =｛<M,ω>｜M是TM，ω是串，M接受ω｝是不可判定的。

证明：假设证A TM 是可判定的，下面将由之导出矛盾。

设H是A TM 的判定器。

令M是一个TM，ω是一个串。

8.1 证明对于任意函数f:N N，其中f(n)n，不论用单带TM模型还是用两带只读输入TM模型，所定义的空间复杂性类SPACE(f(n))总是相同的。

证明：为区别，记单带TM模型在f(n)空间内能判定的语言类为SPACE1(f(n)), 而记双带只读输入TM模型在f(n)空间内能判定的语言类为SPACE2(f(n))。

该题要证明的是SPACE1(f(n))＝SPACE2(f(n))。

首先SPACE1(f(n))SPACE2(f(n))。

这是因为设A SPACE1(f(n))，且设M设在f(n)空间内判定A的单带TM，如下构造双带TM只读输入TM N。

N=“对于输入串w：1)将w复制到工作带上。

2)在工作带上模拟M，直到停机。

3)若M接受，则接受；否则，拒绝。

”N在f(n)空间内运行，L(N)=L(M)=A，所以A SPACE2(f(n))。

首先SPACE2(f(n))SPACE1(f(n))。

设A SPACE2(f(n))，且N 为在f(n)空间内判定A的双带只读输入TM。

按照用单带TM模拟多带TM的常规方式构造M：M＝“对于输入串w：1)初始化工作带为＃w1’w2…w n#’.其中以’标记N的两个读写头。

2)模拟N运行直到停机。

每一步模拟，要两次扫描带子。

第一次扫描确定读写头下符号，第二次扫描根据N的转移函数完成改写和移动读写头的工作。

3)若N接受，则接受；否则，拒绝。

”L(M)=L(N)=A。

由于f(n)n，M的运行空间是f(n)+n+2＝O(f(n))。

8.3 考虑广义地理学游戏，其中起始节点就是又无源箭头指入的节点。

选手I有必胜策略吗？选手II呢？给出理由。

1 2 34 5 6I II I II I Winner2 3 6 I4 5 6 II由表上来看选手II有必胜策略I2II4(不能选3)I5II6(不能选2)I。

8.4 证明PSPACE在并、补和星号运算下封闭。

证明：(1) 并：对任意L1, L2PSPACE，设有n a空间图灵机M1和n b空间图灵机M2判定它们，且c=max{a,b}。

解放军电子工程学院****年攻读硕士学位硕士入学考试试卷考试科目：《数据构造》（75分）一、选择题：（每题2分，共20分）1．构成数据旳基本单位是（）。

(A) 数据项(B) 数据类型( C) 数据元素(D)数据变量2．设输入序列为1、2、3、4、5、6，则通过栈旳作用后可以得到旳输出序列为（B ）。

(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，33．在二叉排序树中插入一种关键字值旳平均时间复杂度为（）。

(A) O(n) (B) O(log2n) (C) O(nlog2n) (D) O(n2) 4．设某棵二叉树中只有度数为0和度数为2旳结点，且度数为0旳结点数为n，则这棵二叉中共有（）个结点。

(A) 2n (B) n+l (C) 2n-1 (D) 2n+l5．在下列排序算法中稳定旳排序算法为（）。

(A) 直接插入排序(B) shell排序(C) 堆排序(D) 迅速排序6．设无向图G中有n个顶点e条边，则其对应旳邻接表中旳表头结点和表结点旳个数分别为（）。

(A) n，e (B) e，n (C) 2n，e (D) n，2e7．若数组S[1..n]作为两个栈S1和S2旳存储空间，对任何一种栈，只有当[1．．n]全满时才不能进行进栈操作。

为这两个栈分派空间旳最佳方案是( )。

(A) S1旳栈底位置为0，S2旳栈底位置为n+l(B) S1旳栈底位置为0，S2旳栈底位置为n/2(C) S1旳栈底位置为1，S2旳栈底位置为n(D) S1旳栈底位置为1，S2旳栈底位置为l8．下面有关线性表旳论述中，错误旳是哪一种？（）(A)线性表采用次序存储，必须占用一片持续旳存储单元。

(B)线性表采用次序存储，便于进行插入和删除操作。

(C)线性表采用链接存储，不必占用一片持续旳存储单元。

(D)线性表采用链接存储，便于插入和删除操作。

9．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。

2017年最新计算机专业硕士研究生入学试题（组成原理）北京邮电大学硕士研究生入学考试试题北京邮电大学 97 年硕士研究生入学试题1．已知：[Y]补=Y0.Y1Y2…Y n求证：[-Y]补=Y0.Y1Y2…Y n+2-n证明：若 Y为正值则依定义有：Y=[Y]补=Y0.Y1Y2…Y n[-Y]补=2+[-Y]=2+（-Y0.Y1Y2…Y n）=2-Y0.Y1Y2…Y n=Y0.Y1Y2…Y n+2-n若 Y为负值则依定义有：Y=2-[Y]补=2-Y0.Y1Y2…Y n[-Y]补=Y=2-Y0.Y1Y2…Y n=Y0.Y1Y2…Y n+2-n所以命题成立。

2．已知：X= - 0.1011*2-010Y= + 0.1101*2-011用变形补码求 X-Y=？依题意： [M X]补 = 11.0101 [E X]补 = 11.110[M Y]补 = 00.1101 [E Y]补 = 11.101 解：（1）对阶ΔE = [E X]补- [E Y]补 = 11.110- 11.101=00.001>0[E(X-Y)]补 = [E Y]补+ΔE = 11.110[M Y]补' = 00.01101（2）尾数相减[M(X-Y)]补 = [M X]补- [M Y]补' =11.0101 -00.01101=10.11101（3）规格化[M(X-Y)]补' =11.011101 [E(X-Y)]补' =11.111 （4）0舍1入处理[M(X-Y)]补' =11.0111（5）判别溢出[E(X-Y)]补' =11.101 无溢出所以：X-Y= - 0.1001*2-0013. 某机CPU可提供16条地址线，8条数据线，1条控制线（R/W），R/W = 1表示读，R/W = 0表示写。

现用存储器总容量为8KB。

拟采用2K*4位的RAM芯片。

（1）画出CPU与RAM之间的连接图。

5.1 证明EQ CFG 是不可判定的。

解：只须证明ALL CFG ≤m EQ CFG 即可。

构造CFG G 1，使L(G 1)=∑*。

设计从ALL CFG 到EQ CFG 的归约函数如下： F=“对于输入＜G ＞，其中G 是CFG ：1）输出＜G ,G 1＞。

”若＜G ＞ALL CFG ，则<G ,G 1>EQ CFG 。

若＜G ＞ALL CFG ，则<G , G 1>EQ CFG 。

F 将ALL CFG 归约到EQ CFG 即ALL CFG ≤m EQ CFG∵ALL CFG 是不可判定的，∴EQ CFG 是不可判定的。

5.2证明EQ CFG 是补图灵可识别的。

证明：注意到A CFG ={<G,w>|G 是能派生串w 的CFG}是可判定的。

构造如下TM ： F=“输入<G ,H>，其中G ,H 是CFG ，1) 对于字符串S 1, S 2,，重复如下步骤。

2) 检测S i 是否可以由G 和H 派生。

3) 若G 和H 中有一个能派生w ，而另一个不能，则接受。

”F 识别EQ CFG 的补。

5.3 略。

5.4 如果A m B 且B 是正则语言，这是否蕴涵着A 也是正则语言？为什么？ 解：否。

例如：对非正则语言A={0n 1n |n 0}和正则语言B={0}，可以构造一个可计算函数f 使得：f(w)=⎩⎨⎧≠=n n nn 10w 1,10w 0, 于是w A f(w)B,故A m B 。

5.5 证明A TM 不可映射规约到E TM 。

证明：反证法假设A TM m E TM ， 则有TM m TM E A ≤。

而A TM 的补不是图灵可识别的，从而可知E TM 的补也不是图灵可识别的。

下面构造一个识别E TM 的补的图灵机S ：S=“输入<M>，M 是TM,1) 对i=1,2,…重复下一步。

2) 对S 1,S 2,…,S i 模拟M 运行i 步，若有接受，则接受。

中国科学院大学2020年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机专业综合考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。

2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

3．试卷共16道大题，每题15分，共240分，考生可以任意选择其中10道大题回答，并在答题纸的该题答案前标明“选做本题”。

4．如果选做的题目多于10道，则判卷将按照所选做试题的题号顺序选择前10道大题计分，后续所做视为无效考试内容。

第一部分：《数据结构》第一题，简答题，共15分（1）请给出下列程序的时间复杂度（n>0）。

（2分）void func(int n) {int i,j;for(i=1,j=0; j<=n; j=j+i) i++;}（2）现有一个线性表的应用，线性表的元素总数不确定，其主要的操作是插入元素、删除表尾元素、查找表尾结点和查找指定结点的前驱结点，那么请问用怎样的数据结构比较好？请给出理由和该数据结构的C语言定义。

（3分）（3）若循环队列存储在数组A[0..m]，头指针Front指向当前队头元素，尾指针Rear指向当前队尾元素的下一个位置，那么当前实际存储有多少队列元素？现有元素x需要入队，请写出元素入队的语句。

（3分）科目名称：计算机专业综合第1页共6页（4）用如下数据结构存储广义表：typedef enum {ATOM, LIST} ElemTag;typedef struct GLNode {ElemTag tag;union {AtomType atom;struct {struct GLNode *hp, *tp;} ptr;}} *Glist;那么，对于广义表X=(A,((),(B,C)),(D,E))，给出其存储结构图，并利用Head、Tail 操作分离出元素E。

（3分）（5）现在需要从5000个元素组成的序列中，用最快的速度挑出前10个最大的元素。

计算理论考研题目及答案### 计算理论考研题目及答案#### 题目一：确定性有限自动机（DFA）的定义和性质问题描述：给定一个确定性有限自动机（DFA）M，其状态集合为Q={q0, q1, q2}，字母表为Σ={a, b}，转换函数为δ，初始状态为q0，接受状态集合为F={q1, q2}。

请根据以下转换函数定义，判断字符串"aba"是否被M接受。

转换函数定义如下：- δ(q0, a) = q1- δ(q0, b) = q0- δ(q1, a) = q2- δ(q1, b) = q1- δ(q2, a) = q2- δ(q2, b) = q0答案：首先，根据转换函数，我们从初始状态q0开始，逐个读取字符串"aba"中的字符：1. 读取字符'a'，应用转换函数δ(q0, a)，状态变为q1。

2. 继续读取字符'b'，应用转换函数δ(q1, b)，状态变为q1。

3. 最后读取字符'a'，应用转换函数δ(q1, a)，状态变为q2。

由于状态q2是接受状态，因此字符串"aba"被DFA M接受。

#### 题目二：图灵机的停机问题问题描述：考虑一个图灵机T，其输入为一个二进制字符串。

请证明图灵机T是否能够解决以下问题：给定一个二进制字符串，判断该字符串是否能够被T在有限步内停机。

答案：这个问题是著名的停机问题，它是一个不可解问题。

根据图灵的停机问题的不可解性定理，不存在一个通用的算法来判断任意给定的图灵机和输入字符串是否停机。

因此，不能构造一个图灵机来判断所有图灵机的停机问题。

#### 题目三：P vs NP问题问题描述：简述P vs NP问题，并给出一个NP完全问题的例子。

答案：P vs NP问题是计算理论中的一个核心问题，它询问：所有那些可以快速验证解的问题（NP问题），是否也能快速找到解（即是否属于P类问题）。

研究生计算机选修课（课程论文及课程设计类）期末考试要求及办法根据《西南大学研究生课程教学管理规定》，积极响应“以学生为中心，以创新为主题，注重在实践中培养研究生的创新能力，全面提升人才培养质量”的教学理念，现拟订研究生计算机选修课期末考试考核要求及办法。

研究生计算机选修课期末考试由如下三部分组成：1、平时成绩。

主要考察其平时的学习情况，包括课堂练习、课堂发言、讨论课、课外作业、出勤率等。

要求要有相应记录。

2、单元实验。

主要考察学生的课程实践能力。

要求每个学生在课程学习过程中完成1个以上实验项目，每个实验项目可包括多个实验题目。

由教师给出相应的实验任务书，学生需要写实验报告（见第5-12页，“实验报告封面”(第5页)与“实验报告须知”(第6页)双面打印）。

3、上机考试。

主要考察学生的课程理论与实践能力。

各部分具体所占比例由任课教师根据课程性质确定，但上机考试比例一般不得少于50%。

学生按照要求完成后必须装订，其顺序为：“西南大学研究生课程考试答卷纸”、各项得分及总分（见第2-3页）（以上两项双面打印）、目录（见第4页）,再按目录内容装订。

西南大学研究生课程考试答卷纸考试科目计算机应用基础院、所、中心化学与化工学专业或专业领域分析化学研究方向生化分析级别2012级学年2012-2013学年学期下学期姓名王红学号1124类别②全日制硕士（①全日制博士②全日制硕士③教育硕士④高师硕士⑤工程硕士⑥农推硕士⑦兽医硕士⑧进修)2013年 6 月 1 日研究生院(筹)制备注：1、成绩评定以百分制或等级制评分，每份试卷均应标明课程类别（①必修课②选修课③同等学力补修课）与考核方式（①闭卷笔试②口试③开卷笔试④课程论文）。

2、①平时成绩：主要考察其平时的学习情况，包括课堂练习、课堂发言、讨论课、课外作业、出勤率等。

要求要有相应记录。

②单元实验：主要考察学生的课程实践能力。

要求每个学生在课程学习过程中完成1个以上实验项目，每个实验项目可包括多个实验题目。