计算机考博试题计算理论及答案
- 格式：doc
- 大小：200.80 KB
- 文档页数：14
下载文档原格式
合集下载
计算机博士试题及答案
计算机博士试题及答案第一部分：计算机基础知识问题1：请解释什么是计算机网络，并列举几个常见的网络协议。
答案：计算机网络是指连接在一起的计算机系统，通过共享资源和信息传输来实现数据交换和通信的网络系统。
常见的网络协议包括TCP/IP协议、HTTP协议、FTP协议和SMTP协议等。
问题2：请解释什么是操作系统，并列举几个常见的操作系统。
答案：操作系统是指管理和控制计算机硬件与软件资源，为用户提供各种服务和程序运行环境的系统软件。
常见的操作系统包括Windows、macOS、Linux和Android等。
问题3：请解释什么是数据库，并列举几个常见的数据库管理系统。
答案：数据库是指按照特定数据模型组织、存储和管理数据的系统。
常见的数据库管理系统包括Oracle、MySQL、SQL Server和PostgreSQL等。
第二部分：计算机网络与通信问题4：请解释什么是IP地址，并说明IPv4和IPv6的区别。
答案：IP地址是指用于在计算机网络中唯一标识一个主机或网络接口的数字标识。
IPv4是目前广泛使用的IP地址版本，采用32位地址，约有42亿个可用地址。
IPv6是新一代IP地址版本，采用128位地址，具有更大的地址空间，可提供更多的地址。
问题5：请解释什么是HTTP协议，并说明与HTTPS的区别。
答案：HTTP协议是指超文本传输协议，用于在计算机网络中传输超文本及其相关中的客户端和服务器之间的通信。
HTTPS是在HTTP 协议基础上加入了SSL/TLS加密传输机制，提供了更安全的通信。
区别在于HTTPS使用了加密技术，可以保护数据传输的安全性。
问题6：请解释什么是TCP/IP协议，并说明它的工作原理。
答案：TCP/IP协议是指传输控制协议/因特网协议，是计算机网络中广泛使用的一套协议。
它将数据分割成一系列的数据包，在网络中进行传输，并利用IP地址对数据包进行寻址和路由。
TCP/IP协议基于客户端-服务器模式，通过三次握手的方式确保可靠的数据传输。
计算机博士面试试题及答案
计算机博士面试试题及答案一、数据结构与算法1. 请解释什么是时间复杂度和空间复杂度，并给出一个例子。
时间复杂度是对算法运行时间的度量，表示随着输入规模的增长，算法运行所需时间的增长速度。
通常用大O表示法来表示时间复杂度。
空间复杂度是对算法所需存储空间的度量，表示随着输入规模的增长，算法所需的额外存储空间的增长量。
也通常用大O表示法来表示空间复杂度。
例如，对于一个数组的线性查找算法，最坏情况下需要遍历整个数组，时间复杂度是O(n)，其中n是数组的大小。
而空间复杂度为O(1)，因为只需要额外一个变量来存储查找结果。
2. 解释以下数据结构：栈、队列和链表。
栈是一种后进先出（LIFO）的数据结构，只允许在栈的顶部进行操作。
可以使用数组或链表来实现栈。
队列是一种先进先出（FIFO）的数据结构，只允许在队列的一端插入元素，在另一端删除元素。
同样，可以使用数组或链表来实现队列。
链表是一种由多个节点组成的数据结构，每个节点包含数据和指向下一个节点的指针。
链表可以分为单向链表和双向链表，分别只有一个指针和两个指针。
3. 请解释深度优先搜索（DFS）和广度优先搜索（BFS）算法，并比较它们的应用场景。
深度优先搜索是一种用于遍历或搜索树或图的算法，从根节点开始，递归地访问节点的所有子节点，直到到达叶子节点。
然后回溯到上一层节点，继续访问其他的子节点。
广度优先搜索是一种用于遍历或搜索树或图的算法，从根节点开始，依次访问根节点的所有相邻节点，然后再依次访问这些相邻节点的相邻节点，直到访问完所有节点。
深度优先搜索通常适用于解决路径问题，例如迷宫求解、拓扑排序等。
广度优先搜索通常适用于解决最短路径问题，例如寻找最短路径、社交网络中的人际关系等。
二、操作系统和网络1. 解释进程和线程的区别。
进程是一个正在执行的程序的实例，具有独立的内存空间和系统资源，是程序的执行单位。
每个进程都有自己的地址空间和指令执行序列。
线程是进程中的一条执行路径，是轻量级的执行单位。
全国计算机科学理论考试题及解答
全国计算机科学理论考试题及解答一、选择题（每题5分，共25分）1. 计算机科学的分支不包括以下哪个领域？A. 算法理论B. 人工智能C. 计算机体系结构D. 文学评论答案：D2. 下列哪种数据结构的时间复杂度最高为O(1)？A. 链表B. 数组C. 树D. 图答案：B3. 在计算机网络中，哪一层负责数据包的最终交付？A. 物理层B. 数据链路层C. 网络层D. 传输层答案：D4. Java中的String类下列哪个方法是用来判断字符串是否为空？A. isEmpty()B. isBlank()C. isEmpty()D. isNull()答案：B5. 下列哪种编程范式主要用于降低程序复杂度？A. 面向对象编程B. 过程式编程C. 函数式编程D. 逻辑编程答案：C二、填空题（每题5分，共25分）1. 在计算机科学中，算法的时间复杂度常用大O符号表示为___O(n^2)___。
答案：大O2. 关系型数据库中，SQL语言用于执行数据的___CRUD___操作。
答案：增删改查3. 深度学习中的___CNN___常用于图像识别任务。
答案：卷积神经网络4. 操作系统中的进程管理主要负责进程的创建、调度和___同步___。
答案：同步5. 给定一个长度为n的数组，冒泡排序的最坏时间复杂度为___O(n^2)_。
答案：O三、简答题（每题10分，共30分）1. 什么是图灵机？简述其作用和意义。
答案：图灵机是由英国数学家阿兰·图灵提出的一种抽象计算模型，用于研究计算理论和可计算性。
图灵机由一个读写头、一个无限长的纸带、一个有限状态集合和一个转移函数组成。
它能在纸带上读写符号，并根据转移函数进行状态转换。
图灵机的提出为计算机科学的发展奠定了基础，是现代计算机的理论基础。
2. 什么是TCP协议？它在计算机网络中扮演什么角色？答案：TCP（传输控制协议）是一种面向连接的、可靠的传输层通信协议。
它主要用于在网络中传输数据，确保数据的可靠性和顺序性。
计算机考博试题及答案
计算机考博试题及答案一、选择题（每题2分，共20分）1. 在计算机科学中，冯·诺依曼体系结构的主要特点是______。
A. 程序存储B. 程序控制C. 程序执行D. 程序设计答案：A2. 以下哪项不是操作系统的主要功能？A. 进程管理B. 存储管理C. 文件管理D. 网络通信答案：D3. 在关系数据库中，用于从数据库表中检索数据的SQL语句是______。
A. CREATEB. UPDATEC. SELECTD. DELETE答案：C4. 下列哪个选项不是计算机网络的拓扑结构？A. 星型B. 环型C. 总线型D. 树型答案：D5. 在计算机组成原理中，CPU的主要组成部分不包括______。
A. 控制单元B. 算术逻辑单元C. 存储器D. 输入输出设备答案：D6. 以下哪个算法不是排序算法？A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序答案：C7. 在计算机安全领域，以下哪项措施不是防止病毒的？A. 安装防病毒软件B. 定期更新操作系统C. 使用防火墙D. 定期格式化硬盘答案：D8. 以下哪种编程语言不是面向对象的？A. JavaB. C++C. PythonD. C答案：D9. 在数据结构中，栈（Stack）是一种______的数据结构。
A. 线性B. 非线性C. 顺序D. 链式答案：A10. 以下哪个选项不是云计算服务的类型？A. IaaSB. PaaSC. SaaSD. DaaS答案：D二、填空题（每题2分，共20分）1. 在计算机组成原理中，______是计算机硬件与软件之间的接口。
答案：指令集2. 操作系统的______功能允许多个用户或多个程序共享计算机资源。
答案：多任务3. 在数据库设计中，______是用来表示实体间联系的。
答案：关系4. 计算机网络中的______协议是用于数据传输的协议。
答案：TCP/IP5. 在操作系统中，______是一种用于分配CPU时间的技术。
计算机考博试题及答案
计算机考博试题及答案1. 数据结构与算法1.1 平衡二叉树平衡二叉树，也称为AVL树，是一种特殊的二叉搜索树，它的左右子树的高度差不超过1。
请说明如何插入和删除节点以保持平衡。
答案：当向平衡二叉树中插入一个节点时，需要按照二叉搜索树的规则找到对应的位置。
插入节点后，如果破坏了平衡二叉树的平衡性，则需要进行相应的调整。
插入节点后，从插入节点到根节点的路径上的所有节点的平衡因子需要更新，并沿着路径向上检查，如果某个节点的平衡因子超过了1或小于-1，则需要进行旋转操作来恢复平衡。
当删除一个节点时，同样需要按照二叉搜索树的规则找到对应的位置，并将该节点删除。
删除节点后，同样需要从删除节点到根节点的路径上的所有节点的平衡因子进行更新，并进行相应的旋转操作来恢复平衡。
1.2 Dijkstra算法Dijkstra算法是一种用于求解加权有向图中单源最短路径问题的算法。
请简要介绍Dijkstra算法的原理及步骤。
答案：Dijkstra算法的原理是，通过不断找出当前距离源点最近的顶点，并更新其他顶点的距离和路径，最终得到源点到其他所有顶点的最短路径。
步骤如下：1) 初始化：将源点设置为当前顶点，将源点到其他顶点的距离初始化为无穷大，将源点到自身的距离初始化为0。
2) 循环：在未遍历的顶点中，选择当前距离源点最近的顶点作为当前顶点。
3) 更新：计算当前顶点的邻居顶点经过当前顶点到达源点的距离，若经过当前顶点到达邻居顶点的距离比已知的距离更短，则更新邻居顶点的距离和路径。
4) 标记：将当前顶点标记为已遍历。
5) 终止条件：当所有顶点都被标记为已遍历时，算法终止。
2. 操作系统2.1 进程和线程的区别进程和线程是操作系统中的两个重要概念，请简要说明它们的区别。
答案：进程是操作系统资源分配的基本单位，每个进程都拥有独立的内存空间和系统资源，进程之间通过进程间通信(IPC)来进行数据交换。
而线程是进程中的执行单元，每个进程可以包含多个线程，线程共享进程的内存空间和系统资源，线程之间可以直接访问共享的内存数据。
计算机博士试题及答案
计算机博士试题及答案一、选择题（每题2分，共20分）1. 在计算机科学中，用于表示数据的最小单位是：A. 字节B. 位C. 字D. 段答案：B2. 下列哪个不是操作系统的功能？A. 进程管理B. 文件管理C. 网络通信D. 数据加密答案：D3. 在数据库管理系统中，用于存储数据的逻辑结构是：A. 表B. 索引C. 视图D. 存储过程答案：A4. 以下哪种网络拓扑结构不是星型结构？A. 总线型B. 环形C. 树型D. 网状型答案：A5. 在软件开发过程中，需求分析阶段的主要任务是：A. 编写代码B. 设计数据库C. 确定软件功能D. 测试软件答案：C6. 以下哪个不是计算机硬件的组成部分？A. 中央处理器B. 存储器C. 操作系统D. 输入设备答案：C7. 在计算机系统中，用于表示二进制数的单位是：A. 位B. 字节C. 字D. 段答案：A8. 下列哪种编程语言不是面向对象的？A. JavaB. C++C. PythonD. C答案：D9. 在计算机网络中，用于在不同网络之间转发数据包的设备是：A. 路由器B. 交换机C. 集线器D. 网关答案：A10. 在计算机科学中，用于表示文件大小的单位是：A. 字节B. 位C. 千字节D. 兆字节答案：A二、填空题（每空1分，共20分）1. 在计算机系统中，CPU是______的缩写，它负责解释和执行存储在内存中的指令。
答案：中央处理器2. 计算机病毒是一种______，它能够自我复制并传播到其他计算机系统。
答案：恶意软件3. 在HTML中，用于定义网页标题的标签是______。
答案：<title>4. 在关系数据库中，用于创建表的SQL语句是______。
答案：CREATE TABLE5. 计算机的存储设备分为______存储和______存储。
答案：随机访问存储；顺序访问存储6. 在编程中，______是一种用于存储数据和程序的永久性存储设备。
计算机博士考核试题及答案
计算机博士考核试题及答案考核试题：1. 请解释什么是计算机网络，并列举其主要组成部分。
2. 请阐述数据库管理系统的基本原理和功能。
3. 解释什么是多线程和并发，并提供适用的例子。
4. 请解释什么是数据挖掘，并列举常用的数据挖掘算法。
5. 请解释什么是人工智能，并提供应用场景。
答案：1. 计算机网络是指在不同地理位置上的计算机和设备通过通信线路连接在一起，以实现数据和资源的共享。
主要组成部分包括计算机、通信链路、网络协议、网络设备和应用软件等。
2. 数据库管理系统（DBMS）是一种用于管理和组织数据的软件系统。
其基本原理是使用结构化方式存储数据，并提供了数据的查询、插入、更新和删除等功能。
DBMS还负责控制数据的一致性和安全性，以及提供数据备份和恢复等功能。
3. 多线程是指在一个程序中同时运行多个线程，每个线程执行相对独立的任务。
并发指的是在同一时间段内，系统能够处理多个任务。
例如，一个下载器程序可以使用多线程实现同时下载多个文件，这样可以提高下载效率。
4. 数据挖掘是从大量的数据中提取有用的信息和模式的过程。
常用的数据挖掘算法包括聚类分析、分类分析、关联规则挖掘和异常检测等。
聚类分析用于将数据划分为不同的簇群；分类分析用于将数据分为不同的类别；关联规则挖掘用于发现数据之间的关联关系；异常检测用于检测和识别异常数据。
5. 人工智能是模拟人类智能的一种技术与方法，其目标是使计算机具备理解、学习和决策等能力。
人工智能在各个领域都有广泛的应用，例如自动驾驶、语音识别和机器翻译等。
华中科技大学计算机学院博士入学考试真题
华科大200×年计算机系统结构博士生入学考题一、判断题(选择一个最佳的答案, 每题3分,共１８分)红色标注答案供参考1. 测量计算机对事务处理的性能，所用的测试基准程序（Benchmark）应该是：(a)Whetstone; (b) SPECint; (c)TPC-C;(d) SPECfp2.从汇编语言程序员的角度看, 下列哪个是不透明的:(a)cache; (b) 数据通路的宽度;(c) 虚拟存储器;(d)流水线3.某个应用程序运行所需要的最少存储空间为320页，每页32KBytes。
某计算机实际物理内存为256MBytes, 但250Mbytes的内存已被其它程序占用，硬盘的容量为40GBytes, 操作系统为该程序分配的虚拟内存地址空间应该是：(a) 6MBytes; (b) 10MBytes;(c) 256MBytes; (d)40GBytes4.某个由多处理器构成的服务器中, 每个处理器都有自己的存储器, 但所有存储器都统一编址, 这种结构属于:(a)UMA (b)NUMA (c)SMP (d)CLUSTER5. 某计算机采用了超标量流水线技术, 其指令级并行度为8（即平均每个时钟周期完成8条指令的执行）, 若已知该机采用了两条流水线, 其机器超流水线周期为: (a) 2个时钟周期; (b) 1个时钟周期; (c) 1/2个时钟周期; (d) 1/4个时钟周期;6.一台由8个磁盘构成的磁盘阵列，其冗余校验信息在某个磁盘中，所属的RAID 级别是：(a) RAID0；(b) RAID1; (c)RAID3; (d) RAID5.二、问答题：(10分)1．RISC机和CISC机相比，提高性能的基本原理是什么?在指令条数（增加），CPI（减少）和时钟频率（）等方面，它提高性能的关键点在什么地方?(4分)2．机群系统和多台计算机组成的局域网有什么区别?（３分）3．SIMD和向量机（Vector）的异同点是什么？（３分）三、计算题（４９分）（１）（８分) 一个程序有40%的部分可以并行化，若采用多个CPU的办法来加速可并行化部分，而总程序运行时间由于多CPU的原因由原来单CPU的120秒缩短为80秒，试问至少要用几个CPU?解：设要x个，则120/80＝1/(0.4/x+0.6) 得x＝6（２）（１２分）某一存储子系统包括SCSI控制器和一个磁盘。
博士面试理论知识题库
博士面试理论知识题库1. 引言本文档为博士面试理论知识题库，旨在帮助准备博士面试的候选人更好地准备和应对面试中的理论知识考察。
该题库包含了多个领域的理论知识问题，涵盖了计算机科学、数学、物理等多个学科领域。
2. 计算机科学2.1 算法与数据结构1.请简要介绍常用的排序算法，并给出它们的时间复杂度。
2.什么是二叉搜索树？请解释其基本性质和操作。
3.请解释动态规划算法的基本思想，并给出一个动态规划问题的例子。
2.2 计算机网络1.请解释TCP/IP协议栈的各个层次及其功能。
2.请解释HTTP协议的工作原理，并简要介绍GET和POST方法的区别。
3.请解释什么是网络拥塞，并举例说明如何解决网络拥塞问题。
2.3 数据库1.请解释关系型数据库和非关系型数据库的区别，并给出各自的优缺点。
2.请解释什么是数据库事务，并举例说明事务的ACID特性。
3.请简要介绍SQL语言的基本语法和常用操作。
3. 数学3.1 线性代数1.请解释什么是向量和矩阵，并介绍它们的基本运算法则。
2.请解释什么是特征值和特征向量，并简要介绍它们在线性代数中的应用。
3.请解释线性相关和线性无关的概念，并给出判断线性相关性的方法。
3.2 概率论与数理统计1.请解释什么是概率和条件概率，并简要介绍它们的计算方法。
2.请解释什么是随机变量和概率密度函数，并给出几个常见的概率分布模型。
3.请解释什么是假设检验，并简要介绍其基本步骤。
3.3 微积分1.请解释什么是导数和积分，并介绍它们的基本性质和运算法则。
2.请解释什么是极限，并给出几个常见的极限计算方法。
3.请解释什么是泰勒展开，并简要介绍它在数学和物理中的应用。
4. 物理4.1 经典力学1.请解释牛顿第一、二、三定律，并简要介绍它们的应用。
2.请解释什么是动量和角动量，并介绍它们的守恒定律。
3.请解释什么是万有引力定律，并简要介绍它在天体运动中的应用。
4.2 电磁学1.请解释电荷、电场和电势的概念，并介绍它们之间的关系。
计算机基础理论试题库及参考答案
计算机基础理论试题库及参考答案一、选择题（每题2分，共40分）1. 计算机硬件系统主要包括哪些部件？A. 控制器、运算器、存储器、输入设备B. 控制器、运算器、存储器、输出设备C. 控制器、运算器、存储器、输入/输出设备D. 控制器、运算器、中央处理器、输入/输出设备答案：B解析：计算机硬件系统主要包括五大部件：控制器、运算器、存储器、输入设备和输出设备。
2. 下面哪个不是计算机软件的组成部分？A. 系统软件B. 应用软件C. 编译软件D. 机器语言答案：D解析：计算机软件分为系统软件和应用软件两大类。
编译软件属于系统软件的一种，而机器语言是计算机硬件可以直接执行的指令集，不属于软件。
3. 计算机的运算速度通常用哪个单位来衡量？A. MIPSB. GHzC. KBD. MB答案：A解析：运算速度通常用每秒执行百万条指令（MIPS）来衡量。
二、填空题（每题2分，共20分）1. 计算机网络中，TCP/IP协议是________协议。
答案：传输控制/互联网协议2. 在计算机系统中，内存的作用是________。
答案：存储正在执行的程序和数据3. 计算机的输出设备主要包括________和________。
答案：显示器、打印机三、判断题（每题2分，共20分）1. 计算机的中央处理器（CPU）是计算机的核心部件。
（）答案：正确2. 计算机的硬盘存储器是一种外存设备。
（）答案：正确3. 计算机的软件系统不包括编译器。
（）答案：错误解析：编译器属于系统软件的一部分。
四、简答题（每题10分，共30分）1. 简述计算机的工作原理。
答案：计算机的工作原理基于存储程序和程序控制的概念。
用户通过输入设备将程序和数据输入计算机，程序存储在内存中。
当计算机启动时，控制器从内存中取出第一条指令执行，然后根据指令的要求从内存中取出下一条指令，如此循环，直到程序执行完毕。
2. 简述计算机网络的分类。
答案：计算机网络可以根据覆盖范围、传输介质、拓扑结构等多种方式分类。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
计算理论字母表：一个有穷的符号集合。
字母表上的字符串是该字母表中的符号的有穷序列。
一个字符串的长度是它作为序列的长度。
连接反转Kleene星号L* ，连接L中0个或多个字符串得到的所有字符串的集合。
有穷自动机：描述能力和资源极其有限的计算机模型。
有穷自动机是一个5元组M=(K,∑,?,s,F),其中1）K是一个有穷的集合，称为状态集2）∑是一个有穷的集合，称为字母表3）?是从KX∑→K的函数，称为转移函数4）s∈K是初始状态5）F?K是接收状态集M接收的语言是M接收的所有字符串的集合，记作L(M).对于每一台非确定型有穷自动机，有一台等价的确定型有穷自动机有穷自动机接受的语言在并、连接、Kleene星号、补、交运算下是封闭的。
每一台非确定型有穷自动机都等价于某一台确定型有穷自动机。
一个语言是正则的当且仅当它被有穷自动机接受。
正则表达式：称R是一个正则表达式，如果R是1）a，这里a是字母表∑中的一个元素。
2）?，只包含一个字符串空串的语言3）?，不包含任何字符串的语言4)(R1∪R2),这里R1和R2是正则表达式5）(R10R2),这里R1和R2是正则表达式6）(R1*),这里R1*是正则表达式一个语言是正则的当且仅当可以用正则表达式描述。
2000年4月1、根据图灵机理论,说明现代计算机系统的理论基础。
1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为《论数字计算在决断难题中的应用》。
在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(Turing Machine)的设想。
“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。
这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。
（中间那个大盒子），内部状态（盒子上的方块，比如A,B,E,H），另外，还有一个程序对这个盒子进行控制。
这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。
工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。
控制器可以在带上左右移动，它带有一个读写出一个你期待的结果。
这一理论奠定了整个现代计算机的理论基础。
“图灵机”更在电脑史上与“冯·诺依曼机”齐名，被永远载入计算机的发展史中。
图灵机在理论上能模拟现代数字计算机的一切运算,可视为现代数字计算机的数学模型。
实际上,一切可计算函数都等价于图灵机可计算函数,而图灵机可计算函数类又等价于一般递归函数类。
2、说明按乔姆斯基分类，语言、文法、自动机的关系乔姆斯基将语言定义为，按一定规律构成的句子或符号串string的有限的或无限的集合，记为L。
数目有限的规则叫文法，记为G。
刻画某类语言的有效手段是文法和自动机。
文法与自动机的关系:形式文法是从生成的角度来描述语言的,而自动机是从识别的角度来描述语言的.文法和自动机是形式语言理论的基本内容。
对某种语言来说,如果存在一个该语言的生成过程,就一定存在一个对于它的识别过程.就描述语言来讲,形式语言和自动机是统一的.文法在形式上定义为四元组：G＝（VN,VT,S,P）,VN是非终极符号，VT是终极符号，S是VN中的初始符号，P是重写规则。
✍文法是定义语言的一个数学模型，而自动机可看作是语言的识别系统。
✍对于一个文法产生的语言，可以构造相应自动机接受该语言：一个自动机接受的语言，可以构造对应的文法产生该语言。
一定类型的自动机和某种类型的文法具有等价性。
2、乔姆斯基根据转换规则将文法分作4类。
每类文法的生成能力与相应的语言自动机（识别语言的装置）的识别能力等价，即4类文法分别与4种语言自动机对应：类型文法自动机0型无限制文法图灵机1型上下文有关文法线性有界自动机2型上下文无关文法后进先出自动机3型有限状态的正则文法有限自动机最常见文法的分类系统是诺姆·乔姆斯基于1956年发展的乔姆斯基谱系，这个分类谱系把所有的文法分成四类型：无限制文法、上下文相关文法、上下文无关文法和正规文法。
四类文法对应的语言类分别是递归可枚举语言、上下文相关语言、上下文无关语言和正规语言。
这四种文法类型依次拥有越来越严的产生式规则，同时文法所能表达的言也越来越少。
尽管表达能力比无限文法和上下文相关文法要弱，但由于高效率的实现，四类文法中最重要的上下文无关文法和正规文法。
例如对下文无关语言存在算法可以生成高效的LL 分析器和LR 分析器。
3、证明HALT(X R,X)不是可计算的。
4、（1）、证明递归集都是递归可枚举集。
（2）、举例属于递归可枚举集但不是递归集的集合，并证明之。
5、（1）、证明L＝{(a,b)*|a,b的个数相同}为上下文无关语言。
（2）、并证明其不是正则的。
P56假设L是正则的，则根据在交下的封闭性，L∩a*b*也是封闭的，而后者正好是L1={ a i b i:i ≧0},假设L1是正则的，则存在满足泵引理的整数n。
考虑字符串w= a n b n∈L。
根据定理可以写成w=xyz使得|xy|≦n，且y≠e，即y=a i，其中i＞0.但是xz= a n-i b n?L，与定理矛盾。
2000年10月1、（1）给出图灵机的格局、计算及图灵机μ计算函数f的精确定义。
(2 ) 对图灵机模型而言，church论题是什么？（3）当x是完全平方时值为3x，否则为3x+1证明其是原始递归函数。
2、证明φ（X，X）是不可计算的。
3、证明L={ambn|m,n>0,m≠n}是上下文无关的，但不是正则的。
利用上下文无关语言在并、连接、Kleene星号下是封闭的。
正则语言在交运算下封闭。
4、A为有穷字母表，L是A*的无穷子集，（1）证明存在无穷序列ω0,ω1,ω2…，它由L的所有字组成，每个字恰好在其中只出现一次。
（2）是否存在从L构造序列ω0,ω1,ω2…,的算法（即i由计算ωi），为什么？2001年4月1、（1）当x是完全平方时值为2x，否则为2x+1证明其是原始递归函数。
（2）对图灵机模型而言，church论题是什么？（3）通用图灵机的描述。
2、（1）用有穷自动机构造正则语言，以a2b结尾的字符串组成的正则语言L （2）L={a3n bn |n>0}为上下文无关,但不是正则。
3、A为字母表，L为A*上任意的语言。
阐述其乔姆斯基层次及用可计算性表述它们的关系。
4、证明不存在可计算函数h(x)，使φ(x,x)↓时h(x,x)= φ(x,x)+a,a∈N,φ(x,y)是编号为y输入为x时的程序。
2001年10月1、{a，b}上递归枚举语言是否可数？证明2、L={a，b，c数目相同的语言}是否CFL（上下文无关）？证明p95证：不是上下文无关的。
假设L是上下文无关的，则它与正则语言a* b*c*的交也是上下文无关的。
令L1={a n b n c n:n≧0}假设L1是上下文无关语言。
取常数p，ω＝a p b p c p,∣ω∣＝3p≥p将ω写成ω＝uvxyz使得v或y不是空串且uv i xy i z∈L1I=0,1,2……其中∣xy∣≥1 且∣xuy∣≤p. 有两种可能他们都导致矛盾。
如果vy中a、b、c三个符号都出现，则v和y中必有一个至少含有abc中的两个符号。
于是uv2xy2z中abc的排列顺序不对，有的b在a前或c在a或b前。
如果vy中只出现a、b、c中的一个或两个符号，则uv2xy2z 中a、b、c的个数不相等。
∴与L1是上下文无关语言假设矛盾。
综上，L不是2型语言。
3、被2，3整除的非负整数的十进制表示的集合是否正则。
∑={1，2，……9}，L?∑*，令L1是非负整数十进制表示的集合，容易看到L1=0∪{1，2，……9}∑*，由于L1是用正则表达式表示的，故它是一个正则语言。
令L2是可以被2整除的非负整数的十进制表示的集合。
L2正好是以0，2，4，6，8结尾的L1的成员组成的集合，即L2=L1∩∑*{0，2，4，6，8}，根据正则语言在交运算下封闭原则，故L2也是一个正则语言。
令是可以被3整除的非负整数的十进制表示的集合.一个数可以被3整除当且仅当它的数字之和可以被3整除。
构造一台有穷自动机，用它的有穷控制器保存输入数字的模3和。
L3是这台有穷自动机接受的语言与L1的交。
最后L=L2∪L3，它一定是个正则语言。
4、NonSelfAccepting是否递归集合2002年4月1．能被5整除的字符串是正则集吗2．用图灵机表示下列字符串。
Φ，e，*3．s->ss, s->asb, s->abs, 证明由s推得的字符串不可能以abb开头。
（可能记忆有误，具体形式就是这样）。
4 证明不是所有的递归可枚举集都是递归的。
定理：语言不是递归的；所以，递归语言类是递归可枚举语言类的真子集。
2002年10月1、什么是计算？计算理论研究的内容和意义是什么？为什么要使用计算的抽象模型？2、请写出一个正则表达式，描述下面的语言：在字母表{0,1}上，不包含00子串且以1结尾。
4、语言L={a n:n是素数}是不是正则语言，是不是上下文无关的？5、一个succ(n+1)的组合Turing机描述，说出它的作用。
P1276、什么是Turing机的停机问题？它是可判定的么？为什么？H={“M”“w”：Turing机M在输入w上停机}，ATM ＝{<M, ω>|M是一个TM，且M接受ω}证明：假设ATM是可判定的，下面将由之导出矛盾。
设H是ATM的判定器。
令M是一个TM，ω是一个串。
在输入<M, ω>上，如果M 接受ω，则H就停机且接受ω；如果M不接受ω，则H也会停机，但拒绝ω。
换句话说，H是一个TM使得：接受如果M接受ωH(<M, ω>)= 拒绝如果M不接受ω现在来构造一个新的图灵机D，它以H作为子程序。
当M被输入它自己的描述<M>是，TM D就调用H，以了解M将做什么。
一旦得到这个信息，D就反着做，即：如果M接受，它就拒绝；如果M不接受，它就接受。
下面是D的描述。
D＝”对于输入<M>，其中M是一个TM：1) 在输入<M,<M>>上运行H。
2) 输出H输出的相反结论，即，如果H接受，就拒绝；如果H拒绝，就接受。
”总而言之，接受如果M不接受<M> D(<M>)=拒绝如果M接受<M>当以D的描述<D>作为输入来运行D自身时，结果会怎样呢？我们得到：接受如果D不接受<M> D(<D>)= 拒绝如果D接受<M>不论D做什么，它都被迫相反地做，这显然是一个矛盾。
所以，TM D和TM H都不存在。
它是不可判定的。