湖南大学计算理论引论期末试题计算理论引论

2022年湖南大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e 的运算是（）。

A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、下述文件中适合于磁带存储的是（）。

A.顺序文件B.索引文件C.哈希文件D.多关键字文件3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列选项中，不能构成折半查找中关键字比较序列的是（）。

计算理论期末练习题（2015）复习重点1、集合序列元组函数关系图串：字母表中符号的有穷序列语⾔:是字符串的集合2、DFA、NFA、NFA到DFA的转换，DFA、NFA的形式化五元组表达3、正则表达式、正则表达式和NFA之间的转换、利⽤泵引理证明不是正则语⾔4、上下⽂⽆关⽂法下推⾃动机乔姆斯基范式（基本概念）CFG到下推⾃动机的转换从右⾄左压⼊栈中5、利⽤泵引理证明不是上下⽂⽆关语⾔6、图灵机、图灵可识别语⾔：接受、拒绝、循环判定器：对所有输⼊都停机的图灵机，永不循环。

图灵可判定语⾔：能让图灵机停机的语⾔，接受或者拒绝要求可以做简单的判定性证明（例如：A DFA、A CFG、HALT-TM、E TM）7、可归约性。

要求可以利⽤规约，完成简单的定理证明。

计算理论练习题1、画出识别下述语⾔的DFA 状态图，其中，字母表为{0,1}。

1）{w|w 从1开始且以0结束}；2）{w|w含有⾄少3个1}；3）{w|w含有⼦串0101}；q1的0⾃循环处考虑004）{w|w的长度不⼩于3，并且第3个符号为0}；5）{w|w从0开始且长度为奇数}；6）{w | w是除11和111以外的任何字符}；7）{w | w不含⼦串110}；2、写出下述语⾔的正则表达式。

1）{w|w不含⼦串110}；(0∪10)*1*2）{w|w的长度不超过5}；ε∪∑∪∑∑∪∑∑∑∪∑∑∑∑∪∑∑∑∑∑3）{w|w是除11和111外的任意串}；ε∪0∑*∪10 ∑*∪110 ∑*∪111 ∑∑*包含11或111的串仍属于题设4）{w|w的奇数位均为1}；(1Σ)*(ε? 1)前⼀个括号为串长为偶数，加后⼀个则奇偶都可以5）{w|w含有⾄少2个0，并且⾄多含1个1}。

0*(00?010?001?100) 0*确保两个0⼀定在，并且最多1个1，不能在外⾯，即有可能为空3、利⽤泵引理证明下述语⾔不是正则的。

1）A1={0n1n2n|n≥0};证明：假设A1是正则的。

计算理论习题答案计算理论，也称为理论计算机科学，是研究算法和计算过程的数学理论基础的学科。

以下是一些计算理论习题的答案示例：1. 确定性图灵机（Deterministic Turing Machine, DTM）：- 习题：证明一个确定性图灵机可以模拟任何其他确定性图灵机。

- 答案：确定性图灵机可以读取输入，根据当前状态和读取到的符号，按照预定的转移规则移动磁带头并改变状态。

要模拟另一台确定性图灵机，只需要将被模拟机的状态转移表编码为模拟机的转移规则即可。

2. 非确定性图灵机（Nondeterministic Turing Machine, NTM）：- 习题：证明非确定性图灵机比确定性图灵机更强大。

- 答案：非确定性图灵机可以在多个可能的转移中选择，这使得它能够解决一些确定性图灵机无法解决的问题，例如哈密顿回路问题。

此外，任何确定性图灵机都可以被一个非确定性图灵机模拟，但反之则不成立。

3. 可计算性（Computability）：- 习题：证明某个特定的函数是可计算的。

- 答案：要证明一个函数是可计算的，需要展示一个算法或图灵机，它对于该函数的任何输入都能在有限步骤内给出输出。

例如，一个简单的加法函数f(x, y) = x + y是可计算的，因为它可以通过迭代或递归来实现。

4. 不可解问题（Undecidable Problems）：- 习题：解释停机问题（Halting Problem）为什么是不可解的。

- 答案：停机问题是不可解的，因为它涉及到预测一个图灵机是否会在有限步骤内停止。

如果存在一个算法能够解决停机问题，那么我们可以构造一个悖论，即一个图灵机可以模拟自身并决定自己是否会停止，这会导致自指的悖论。

5. 复杂性类（Complexity Classes）：- 习题：区分P类问题和NP类问题。

- 答案：P类问题是指可以在多项式时间内解决的问题，而NP类问题是指可以在多项式时间内验证一个解的问题。

第三章 上下文无关语言与下推自动机a. {w | w 至少含有3个1} S →A1A1A1A A →0A|1A|εb. {w | w 以相同的符号开始和结束}S →0A0|1A1 A →0A|1A|εc. {w | w 的长度为奇数}0, ε→ε0,ε→ε 0,ε→ε1,ε→ε0,ε→εS →0A|1A A →0B|1B|ε B →0A|1Ad.{w | w 的长度为奇数且正中间的符号为0} S →0S0|1S1|0S1|1S0|0e.{w | wS →A1AA →0A1|1A0|1A|AA|εf.{w | w=w R }S →0S0|1S1|1|0g.空集 S →S3.6 给出产生下述语言的上下文无关文法： a ． 字母表{a,b}上a 的个数是b 的个数的两倍的所有字符串组成的集合。

S →bSaSaS|aSbSaS|aSaSbS|εb ．语言{a n b n |n ≥0}的补集。

见问题3.25中的CFG: S →aSb|bY|Ta T →aT|bT|εc ．{w#x | w, x ∈{0,1}*且w R 是x 的子串}。

S →UV0,ε→0,0→0,ε→1,0→0,1→0,ε→0,0→U→0U0|1U1|WW→W1|W0|#V→0V|1V|εd．{x1#x2#⋯#x k|k≥1, 每一个x i∈{a,b}* , 且存在i和j使得x i＝x j R}。

S→UVWU→A|εA→aA|bA|#A|#V→aVa|bVb|#B|#B→aB|bB|#B|#W→B|ε3.14解：添加新起始变元S0, 去掉B→εS0→A S0→AA→BAB|B|εA→BAB|AB|BA|B|εB→00|εB→00去掉A→ε, 去掉A→BS0→A S0→AA→BAB|AB|BA|B|BB A→BAB|AB|BA|00|BBB→00 B→00去掉S0→A, 添加新变元S0→BAB|AB|BA|00|BB S0→VB|AB|BA|UU|BBA→BAB|AB|BA|00|BB A→VB|AB|BA|UU|BBB→00 B→UUV→BAU→03.15 证明上下文无关语言类在并,连接和星号三种正则运算下封闭---答案。

第 1 页（共3页）A. 端到端流量控制（flow control）B. 可靠的逐跳（hop-by-hop）通信C. 成帧（framing）D. 路由（routing）10. 节点A采用CRC发送比特流111010到节点B，假设生成器产生的比特模式（bit pattern）为111，并由此可计算得到CRC校验和。

那么附带CRC校验和后，节点A最终发往节点B的比特流是___ __。

11.引入自治系统后，可以将路由协议分为___ ___和___ __两种类型。

12.TCP/IP参考模型的层次结构为___ ___、___ __、___ ___和___ __。

13.节点时延包括处理时延、转发时延、___ ___和___ ___四种。

14. WWW上的每一个网页(Home Page)都有一个独立的地址，这些地址称为_______。

15.TCP通过调节来进行流量控制。

二．简答题（4个题，每题5分，共20分）1、试从多个方面比较电路交换和分组交换的主要优缺点。

2、请描述构建应用程序中的客户机服务器模式（C/S）与P2P模式的区别。

3、交换机和路由器都采用存储和转发（store-and-forward）的设计。

简述它们构建转发表（forwarding table）的过程有何不同？4、描述并比较CSMA/CD和CSMA/CA机制？三．综合题（6个题，每题10分，共60分）1.请按照(a)(b)两种情况填充下图：（a）采用Go-Back-N协议，其窗口大小为4。

假设第2个包丢失，请在图上补充完剩下的事件直到发送方收到数据包2的确认。

（b）将Go-Back-N协议换成Selective Repeat 协议，完成同样的工作。

2、如下图的一个子网，主机A 在网络1中 ( MTU=1500),主机 B 在网络3中 ( MTU=1500).假设一个payload大小为1400 bytes的数据报要通过网络2(MTU=440)从主机A发往主机B，试问：(1) 当数据报到达路由器R1会发生什么操作,为什么?(2) 当这个分组通过网络2时，请分别计算每个IP分片发生变化的相应首部字段的值?(3) 这些分片将在何处被重组?3.假设节点A和节点B通过以太网LAN进行连接，且采用CSMA/CD进行通信。

一、解答题1.机器调度问题。

问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。

每件任务的开始时间为s i，完成时间为f i，s i<f i 。

[s i，f i]为处理任务i 的时间围。

两个任务i，j重叠指两个任务的时间围区间有重叠，而并非指i，j的起点或终点重合。

例如：区间[1，4]与区间[2，4]重叠，而与[4，7]不重叠。

一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。

因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。

最优分配是指使用的机器最少的可行分配方案。

问题实例：若任务占用的时间围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法）画出工作在对应的机器上的分配情况。

3. 单源最短路径的求解。

问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。

另外，还给定V中的一个顶点，称为源。

现在要计算从源到所有其它各顶点的最短路长度。

这里路的长度是指路上各边权之和。

这个问题通常称为单源最短路径问题。

解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。

请将此过程填入下表中。

110030maxint10-{1}初始dist[5]dist[4]dist[3]dist[2]uS迭代7. 最长公共子序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。

用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。

其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。

当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。

故此时C[i][j]=0。

其它情况下，由最优子结构性质可建立递归关系如下：00,0 [][][1][1]1,0;max{[][1],[1][]},0;i ji ji jc i j c i j i j x yc i j c i j i j x y⎧==⎪=--+>=⎨⎪-->≠⎩在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。

2022年湖南大学计算机科学与技术专业《计算机系统结构》科目期末试卷A（有答案）一、选择题1、块冲突概率最高的Cache地址映象方式是( )A.段相联B.组相联C.直接D.全相联2、计算机系统结构不包括（）A.主存速度B.机器工作状态C.信息保护D.数据表示3、外部设备打印机适合于连接到( )。

A.数组多路通道B.字节多路通道C.选择通道D.任意一种通道4、（）属于MIMD系统结构。

A.各处理单元同时受同一个控制单元的管理B.各处理单元同时接受同一个控制单元送来的指令C.松耦合多处理机和多计算机D.阵列处理机5、与全相联映象相比，组相联映象的优点是( )A.目录表小B.块冲突概率低C.命中率高D.主存利用率高6、从计算机系统结构上讲，机器语言程序员所看到的机器属性是（）A.计算机软件所要完成的功能B.计算机硬件的全部组成C.编程要用到的硬件组织D.计算机各部件的硬件实现。

7、下列说法中不正确的是（）A.软件设计费用比软件重复生产费用高B.硬件功能只需实现一次，而软件功能可能要多次重复实现C.硬件的生产费用比软件的生产费用高D.硬件的设计费用比软件的设计费用低8、直接执行微指令的是( )A.汇编程序B.编译程序C.硬件D.微指令程序9、非线性流水线是指( )A.一次运算中使用流水线中的多个功能段B.一次运算中要多次使用流水线中的某些功能段C.流水线中某些功能段在各次运算中的作用不同D.流水线的各个功能段在各种运算中有不同的组合10、微指令由（）直接执行。

A.微指令程序B.硬件C.汇编程序D.编译程序11、目前，MO由（）实现，M1用（）实现，M2至M5大多用（）实现。

A.软件，固件，硬件B.固件，软件，硬件C.硬件，软件，固件D.硬件，固件，软件12、计算机系统多级层次中，从下层到上层，各级相对顺序正确的应当是（）。

A.汇编语言机器级，操作系统机器级，高级语言机器级B.微程序机器级，传统机器语言机器级，汇编语言机器级C.传统机器语言机器级，高级语言机器级，汇编语言机器级D.汇编语言机器级，应用语言机器级，高级语言机器级13、系列机软件应做到( )。

湖南大学课程考试试卷课程名称： 计算理论引论 ；试卷编号： ；考试时间：120分钟一 单选或填空题（10*3 = 30％） 下列叙述正确的是（ ） A.如果DFA 不接受任何字符串，则该机器识别的语言为{ε}. B.如果DFA 不接受任何字符串，则该机器识别的语言为φ. C.一个DFA 可以没有起始状态. D.一个DFA 的起始状态不能和接受状态相同. 2.下述（目前为止）肯定不正确的是（ ） A ．NP P ⊆ B. P NP ⊆ C.SAT 是NP 完全的 D.SAT 是NP 难的 3.下图中,存在的最大团顶点数为____ A.1 B.3 C.4 D.5 4.识别语言{0n 1n | n ≥ 0}的文法为__________5.下述表达不正确的是（ ）A.所有的RL 均是CFLB.所有的RL 均是图灵可判定的C.所有的CFL 均是图灵可判定的D.若语言A 是图灵可判定的,则A 和A 不全是图灵可识别的6.背包问题:max: p 1x 1+p 2x 2+…+p n x nSt: w 1x 1+w 2x 2+…w n x n <m (x i = 0或1)用动态规划在O (nm )时间解决，背包问题属于____问题.A. PB. NPC.NP 完全7.若判断某语言A 的多带图灵机所花费的时间为n +log n ,则判定问题A 的时间复杂度为（ ）A. O (n )B. O (log n )C.O (2n )D.O (n 2)8.若有A ≤ m B ,则下述叙述正确的是（ ）A.若B 可判定，则A 也可判定B.若B 可判定，则A 也不可判定C.若B 不可识别,则A 也不可识别D.A 和B 间的可判定性不存在任何关系9.若图灵机的当前格局为uaq i bv ,其状态转移函数为),,(),(L c q b q j i =δ,则下一格局为_______.10.若一个关系是自反,对称和传递的,则该关系为_____关系.二 DFA 的形式描述为({q 1,q 2,q 3,q 4},{u,d}, δ, q 3,{ q 3}),其中δ在下表中给出.试. (13%)三 (10%) 将下述公式转换为乔氏范氏S→AA | 0A→SS | 1四给出产生语言A={a i b i c k| i≥0,k≥0}的上下文无关文法，并判断其是否歧义.(10%)五证明：若A和A均为图灵可识别的，则A为图灵可判定的.(10%)六判断下述公式的可满足性，并说明原因.(13%)(x∨y)∧(x∨y)∧(x∨y)七令CONNECTED={<G>|G是连通的无向图},证明：CONNECTED P.(7%) 八证明：上下文无关文法（或语言）在交运算下不封闭.(7%)。