龙书第二章答案Snooze
龙书第二章答案Snooze
CS 431, Assignment 3, Book Questions on Chapter 2
Plus One Other Question
Questions that you need to answer are listed below, and some solutions or partial solutions are also given. The solutions are not presented as the only possible answers, and what is given may not be complete. It may only be a starting point for thinking about a complete, correct answer. Your goal in working the problems should be to come up with a solution, and if in doubt about your answer, compare with what’s gi ven here. In theory, even if your answer is not exactly the same, you should see the sense or understand the direction of the suggestions. If your answer is at odds with what I have suggested you might want to check with me. It is possible that I am off base. It is also possible that you need some things clarified.
Book problems: 2.1, a-c; 2.2, a-e; 2.3; 2.4, a-e, and 2.8. Suggested answers to these questions are given after the following question.
Last problem: There is an additional problem that is not from the book. It is stated here. Implement Java code that will correctly translate infix expressions with + and – (no parentheses and no other operators) to postfix expressions. A problem solution is given in the book in C code, so your task is mainly one of adaptation. A starting point for this problem is posted on the Web page. You may use the file InfixToPostfixCut.java as given and simply add the needed methods. You can also do the problem from scratch if you want to. I think it would be preferable if you left your implementation recursive rather than changing it to a loop, but that is your choice. Hand in a printout of the methods you added along with your answers to the problems listed above.
Starting points for thinking about solutions:
2.1. Consider the following context-free grammar
S → S S + (1)
S → S S * (2)
S → a (3)
a) Show how the string aa+a* can be generated by this grammar.
Production (3) allows you to generate a string S0 which consists of a.
Using S0 as a starting point, production (1) allows you to generate a string S1 which consists of aa+.
Production (3) again allows you to generate a string S2 which consists of a.
Then production (2) allows you to generate a string S3 = S1S2* = aa+a*.
b) Construct a parse tree for this string.
c) What language is generated by this grammar? Justify your answer. Assuming a is an identifier for a numeric value, for example, then the grammar generates a language consisting of all possible arithmetic combinations of a using only the operations + and * and postfix notation. (No particular justification is given. Check to see if you agree.)
2.2. What language is generated by the following grammars? In each case justify your answer. (No justifications are given.)
a) S → 0 S 1 | 0 1
All strings divided evenly between 0’s and 1’s, with the sequence of 0’s coming first and the sequence of 1’s coming second.
b) S → + S S | - S S | a
This is the prefix analog to question 2.1.
c) S → S ( S ) S | ε
This will generate arbitrary sequences of adjacent and nested, matched pairs of parentheses.
d) S → a S b S | b S a S | ε
All possible strings containing equal numbers of a’s and b’s, with the a’s and b’s arranged in no particular order.
e) S → a | S + S | S S | S * | ( S )
I don’t see a pattern to this that I can verbally describe.
2.3. Which of the grammars in Exercise 2.2 are ambiguous?
To show ambiguity it is sufficient to find any single string that can be parsed in more than one way using the grammar. No such strings spring immediately to
mind for the grammars of a through d. (That does not mean that there aren’t any.) However, e is clearly ambiguous. Let the string S + S * be given. Here are two possible parsings:
2.4. Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct. (Correctness is not shown.)
a) Arithmetic expressions in postfix notation.
list → list list + list → list list – list → digit
list → 0 | 1 | 2 | … | 9
b) Left-associative lists of identifiers separated by commas.
list → list, id list → id
c) Right-associative lists of identifiers separated by commas.
list → id, list list → id
d) Arithmetic expressions of integers and identifiers with the four binary operators +, -, *, /.
Add the following rule to the grammar given at the end of section 2.2: factor → identifier
e) Add unary plus and minus to the arithmetic operators of (d).
Add the following rules to the grammar:
factor → +factor
factor → -factor
2.8 Construct a syntax-directed translation scheme that translates arithmetic expressions from postfix notation to infix notation. Give annotated parse trees for the inputs 95-2* and 952*-.
Here is a simple grammar that can serve as a starting point for the solution of the problem:
string → digit string operator
| string digit operator
| digit
digit →0 | 1 | 2 | … | 9
operator → * | / | + | -
Here is an annotated parse tree of the first expression:
The first production applied in forming this tree was: string → string digit operator. Notice that it would have been just as possible to apply the production: string → digit string operator. If that had been done you would have then had to parse the string “5-2”. This result would not parse and it would be necessary to backtrack and choose to apply the other production. At the next level down it doesn’t matter which production is chosen.
In this example there is no choice about which production to apply first. At the second level there is a choice but it doesn’t make a difference. The lack of choice at the first level illustrates clearly how you could tell whether or not the production you have chosen is the correct one, assuming you could look that far ahead: If the string that you have parsed on the right hand side does not end in an operator, then the production choice is not correct. It is also possible to see that if you could specify the order in which productions are tried, you could avoid backtracking. If you always tried to parse using this production first: string string digit operator and tried the other one if that one failed to apply, you would avoid backtracking. But again, such an approach is not allowed. The question of backtracking is discussed on pages 45 and 46 of the book. The upshot of the matter is that this grammar isn’t suitable for predictive parsing.
There is another matter that will require a change in the grammar so that a syntax-directed translation scheme can be devised. At the top of page 39 in the book the term “simple” is defined as it applies to a syntax-directed definition. The requirement is that the order of non-terminals on the right hand side of a production agree with the order of the corresponding symbols generated as the desired output. Other symbols or terminals may come before, between, or after the output for the non-terminals. Under this condition the output can be generated from a depth first traversal of the annotated tree. The problem with the grammar given above is that all of the operators are symbolized using the non-terminal “operator”. However, in the translation from postfix to infix, it is the position of the operator that changes. That means that even though tedious, for practical reasons the productions have to be rewritten with the operator symbols in-line as terminals:
string → digit string *
| digit string /
| digit string +
| digit string –
| string digit *
| string digit /
| string digit +
| string digit –
| digit
digit →0 | 1 | 2 | … | 9
The problem only gets better and better, or worse and worse, depending on your point of view. Postfix notation does not require parentheses. The relative positions of the operands and operators unambiguously determine the order of operations. This means that an arbitrary postfix expression may enforce an order of operations which would not occur naturally in an unparenthesized infix expression. In particular, 95-2* does not translate to 9 – 5 * 2, where the multiplication would be done first. It translates to (9 – 5) * 2. It is not an attractive proposition to try and implement a translation scheme that would only insert parentheses when needed. It is much more convenient to fully parenthesize the infix translation whether needed or not. The unneeded parentheses do not adversely affect the meaning of the arithmetic.
Having said all of the above, here is my suggested syntax-directed translation scheme, that is, a context-free grammar with embedded semantic actions that will generate the infix translation of a postfix input:
string →{print(“(“)} digit {print(“*”)} string * {print(“)”)}
| {print(“(“)} digit {print(“/”)} string / {print(“)”)}
| {print(“(“)} digit {print(“+”)} string + {print(“)”)}
| {print(“(“)} digit {print(“-”)} string - {print(“)”)}
| {print(“(“)} string {print(“*”)} digit * {print(“)”)}
| {print(“(“)} string {print(“/”)} digit / {print(“)”)}
| {print(“(“)} string {print(“+”)} digit + {print(“)”)}
| {print(“(“)} string {print(“-”)} digit - {print(“)”)}
digit →0 {print(“0”)}
| 1 {print(“1”)}
etc.
The parse tree for 95-2* showing semantic actions follows.
And here is the parse tree for 952*- showing semantic actions.
If there are no mistakes in the parse trees, traversing them in depth-first order and executing the print statements as you go should cause the correct, parenthesized, infix translation of the postfix input to be emitted.
高等代数第6章习题参考答案
第六章 线性空间 1.设,N M ?证明：,M N M M N N ==I U 。 证 任取,M ∈α由,N M ?得,N ∈α所以,N M I ∈α即证M N M ∈I 。又因 ,M N M ?I 故M N M =I 。再证第二式，任取M ∈α或,N ∈α但,N M ?因此无论 哪 一种情形，都有,N ∈α此即。但,N M N Y ?所以M N N =U 。 2.证明)()()(L M N M L N M I Y I Y I =，)()()(L M N M L N M Y I Y I Y =。 证 ),(L N M x Y I ∈?则.L N x M x Y ∈∈且在后一情形，于是.L M x N M x I I ∈∈或所以)()(L M N M x I Y I ∈，由此得)()()(L M N M L N M I Y I Y I =。反之，若 )()(L M N M x I Y I ∈，则.L M x N M x I I ∈∈或 在前一情形，,,N x M x ∈∈因此 .L N x Y ∈故得),(L N M x Y I ∈在后一情形，因而,,L x M x ∈∈x N L ∈U ，得 ),(L N M x Y I ∈故),()()(L N M L M N M Y I I Y I ? 于是)()()(L M N M L N M I Y I Y I =。 若x M N L M N L ∈∈∈U I I （），则x ，x 。 在前一情形X x M N ∈U ， X M L ∈U 且，x M N ∈U 因而（）I U （M L ） 。 ,,N L x M N X M L M N M M N M N ∈∈∈∈∈?U U U I U U I U U U U I U I U 在后一情形，x ,x 因而且，即X （M N ）（M L ）所以 （）（M L ）（N L ）故 （L ）=（）（M L ）即证。 3、检验以下集合对于所指的线性运算是否构成实数域上的线性空间： 1） 次数等于n （n ≥1）的实系数多项式的全体，对于多项式的加法和数量乘法； 2） 设A 是一个n ×n 实数矩阵，A 的实系数多项式f （A ）的全体，对于矩阵的加法和数量 乘法； 3） 全体实对称（反对称，上三角）矩阵，对于矩阵的加法和数量乘法； 4） 平面上不平行于某一向量所成的集合，对于向量的加法和数量乘法； 5） 全体实数的二元数列，对于下面定义的运算： 2121211211 12 b a b a a b b a a k k b a ⊕+=+++-1111（a ，）（（，） （）k 。（a ，）=（ka ，kb +
编译原理龙书答案
P532.8 构建一个语法制导翻译模式，将算术表达式从后缀表示翻译成中缀表示。给出输入95-2*和952*-的注释分析树。（仅供参考一定要保证转换后的中缀表达式与原后缀表达式的优先级相同） 1 后缀算术表达式的文法如下： expr →expr expr + | expr expr – | expr expr * | expr expr / |digit digit →0 | 1 | 2 | 3 | … | 9 2 将后缀表达式翻译成中缀表达式的语法制导定义（文法+语义规则）
4 95-2*和952*-的翻译成后缀形式的语义动作与注释分析树。 expr expr expr * print(‘(‘) print(‘)‘) expr expr - 5 9 digit 2 print(‘-’) ‘9’) print(‘5’) print(‘2’) print(‘*’) 95-2*的深度优先遍历语义动作 expr expr expr - print(‘(‘) print(‘)‘) expr expr digit 2 digit 5 digit 9 print(‘*’) ‘5’) print(‘2’) print(‘9’) print(‘-’) 952*-的深度优先遍历语义动作
expr.t=(9-5)*2 expr=(9-5) expr.t=2 * expr.t=9 expr.t=5 - digit.t=5 5 digit.t=9 9 digit.t=2 2 输入为95-2*的注释分析树 expr.t=(9-5*2) expr.t=5*2 expr.t=9 - expr.t=5 expr.t=2 * digit.t=2 2 digit.t=5 5 digit.t=9 9 输入为952*-的注释分析树
第六章作业及答案
第六章作业 一、选择题 1.若不考虑结点的数据信息的组合情况，具有3个结点的树共有种（）形态，而二叉树共有( )种形态。 A.2 B.3 C.4 D.5 2.对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0= ( ) A.n1+1 B.n1+n2 C.n2+1 D.2n1+1 3.已知某非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即 ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为( ) A.G,D,B,A,F,H,C,E B.G,B,D,A,F,H,C,E C.B,D,G,A,F,H,C,E D.B,G,D,A,F,H,C,E 4、具有65个结点的完全二叉树的高度为（）。（根的层次号为1） A．8 B．7 C．6 D．5 5、在有N个叶子结点的哈夫曼树中，其结点总数为（）。 A 不确定 B 2N C 2N+1 D 2N-1 6、以二叉链表作为二叉树存储结构，在有N个结点的二叉链表中，值为非空的链域的个数为（）。 A N-1 B 2N-1 C N+1 D 2N+1 7、树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列 8、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是（） A．39 B.52 C.111 D.119 9、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是（） A．41 B.82 C.113 D.122 二、填空题。 1、对于一个具有N个结点的二叉树，当它为一颗_____ 二叉树时，具有最小高度。 2、对于一颗具有N个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_____ 个，其中_____个用于链接孩子结点，_____ 个空闲着。 3、一颗深度为K的满二叉树的结点总数为_____ ，一颗深度为K的完全二叉树的结点总数的最小值为_____ ，最大值为_____ 。 4、已知一棵二叉树的前序序列为ABDFCE，中序序列为DFBACE，后序序列为 三、应用题。 1、已知一棵树二叉如下，请分别写出按前序、中序、后序遍历时得到的结点序列，并将该二叉树还原成森林。 A B C D E F G H
第六章作业参考标准答案
第六章存货决策 一、单项选择题 1．下列各项中，与经济订货量无关的是（D ）。 A．每日消耗量B．每日供应量 C．储存变动成本D．订货提前期 2．某公司使用材料A，一次订货成本为2000元，每单位采购成本为50元，经济订货批量为2000个，单位资本成本为单位采购成本的10%，全年用量为8000个。该材料单位储存成本中的付现成本是（B ）元。 A．8 B．3 C．4 D．2 3．某商品的再订购点为680件，安全存量为200件，采购间隔日数为12天，假设每年有300个工作日，则年度耗用量为（ C ）件。 A．11000 B．10000 C．12000 D．13000 4.（D ）不是存货的形式。 A．原材料B．在产品 C．产成品D．应收账款 5.在存货决策中，（ B ）可以不考虑。 A．订货成本 B．固定订货成本 C．变动订货成本 D．变动储存成本 6.下列各项中，不属于订货成本的是（ C ）。 A．采购部门的折旧费 B．检验费 C．按存货价值计算的保险费 D．差旅费 7.由于存货数量不能及时满足生产和销售的需要而给企业带来的损失称为 （ B ）。 A．订货成本 B．缺货成本 C．采购成本 D．储存成本 8.在储存成本中，凡总额大小取决于存货数量的多少及储存时间长短的成 本，称为（ C ）。
A．固定储存成本 B．无关成本 C．变动储存成本 D．资本成本 二、多项选择题 1.当采购批量增加时，（ AD ）。 A．变动储存成本增加 B．变动储存成本减少 C．变动订货成本增加 D．变动订货成本减少 2.按存货经济订购批量模型，当订货批量为经济批量时，（ ABCD ）。 A．变动储存成本等于变动订货成本 B．变动储存成本等于最低相关总成本的一半 C．变动订货成本等于最低相关总成本的一半 D．存货相关总成本达到最低 3.计算经济订购批量时，不需用的项目是（ BD ）。 A．全年需要量 B．固定储存成本 C．每次订货成本 D．安全存量 4.在存货经济订购批量基本模型假设前提下确定经济订购批量，下列表述中正确的有（ ABCD ）。 A．随每次订购批量的变动，相关订货成本和相关储存成本两者的变动方向相反 B．相关储存成本的高低与每次订购批量成正比 C．相关订货成本的高低与每次订购批量成反比 D．年相关储存成本与年相关订货成本相等时的订购批量，即为经济订购批量 5.存货过多，会导致（ ABCD ）。 A．占用大量的流动资金 B．增加仓储设施 C．增加储存成本 D．自然损耗额增加 6.在有数量折扣、不允许缺货的情况下，属于订购批量决策相关成本的是（ ACD ）。 A．订货成本 B．缺货成本 C．采购成本 D．储存成本
编译原理龙书课后部分答案(英文版)
1) What is the difference between a compiler and an interpreter? A compiler is a program that can read a program in one language - the source language - and translate it into an equivalent program in another language – the target language and report any errors in the source program that it detects during the translation process. Interpreter directly executes the operations specified in the source program on inputs supplied by the user. 2) What are the advantages of: (a) a compiler over an interpreter a. The machine-language target program produced by a compiler is usually much faster than an interpreter at mapping inputs to outputs. (b) an interpreter over a compiler? b. An interpreter can usually give better error diagnostics than a compiler, because it executes the source program statement by statement. 3) What advantages are there to a language-processing system in which the compiler produces assembly language rather than machine language? The compiler may produce an assembly-language program as its output, because assembly language is easier to produce as output and is easier to debug. 4.2.3 Design grammars for the following languages: a) The set of all strings of 0s and 1s such that every 0 is immediately followed by at least 1. S -> SS | 1 | 01 | 4.3.1 The following is a grammar for the regular expressions over symbols a and b only, using + in place of | for unions, to avoid conflict with the use of vertical bar as meta-symbol in grammars: rexpr -> rexpr + rterm | rterm rterm -> rterm rfactor | rfactor rfactor -> rfactor * | rprimary rprimary -> a | b a) Left factor this grammar. rexpr -> rexpr + rterm | rterm rterm -> rterm rfactor | rfactor rfactor -> rfactor * | rprimary rprimary -> a | b
编译原理第4章作业答案
第四章 习题4.2.1：考虑上下文无关文法： S->S S +|S S *|a 以及串aa + a* (1)给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a* (3)给出这个串的一棵语法分析树 习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|，以避免和文法中作为元符号使用的竖线相混淆： rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 1)对这个文法提取公因子 2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？ 3)提取公因子之后，原文法中消除左递归 4)得到的文法适用于自顶向下的语法分析吗？ 解 1)提取左公因子之后的文法变为 rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法 3)消除左递归后的文法
rexpr -> rterm rexpr’ rexpr’-> + rterm rexpr’|ε rterm-> rfactor rterm’ rterm’-> rfactor rterm’|ε rfactor-> rprimay rfactor’ rfactor’-> *rfactor’|ε rprimary-> a | b 4)该文法无左递归，适合于自顶向下的语法分析 习题4.4.1：为下面的每一个文法设计一个预测分析器，并给出预测分析表。可能要先对文法进行提取左公因子或消除左递归 (3)S->S(S)S|ε (5)S->(L)|a L->L,S|S 解 (3) ①消除该文法的左递归后得到文法 S->S’ S’->(S)SS’|ε ②计算FIRST和FOLLOW集合 FIRST(S)={(,ε} FOLLOW(S)={),$} FIRST(S’)={(,ε} FOLLOW(S’)={),$} ③ (5) ①消除该文法的左递归得到文法 S->(L)|a
第六章作业参考答案
第六章作业参考答案 1．在DSS数字签名标准中，取p=83=2×41+1，q＝41，h＝2，于是g≡22≡4 mod 83，若取x ＝57，则y≡g x≡457＝77 mod 83。在对消息M=56签名时选择k＝23,计算签名并进行验证。解：这里忽略对消息M求杂凑值的处理 计算r＝(g k mod p) mod q＝(423 mod 83) mod 41=51 mod 41=10 k-1mod q=23-1 mod 41=25 s=k-1(M+xr) mod q=25(56+57*10) mod 41=29 所以签名为(r,s)=(10,29) 接收者对签名(r',s')=(10,29)做如下验证： 计算w＝(s')-1 mod q=29-1 mod 41=17 u1＝[M'w] mod q=56*17 mod 41=9 u2＝r'w mod q＝10×17 mod 41＝6 v＝(g u1y u2 mod p) mod q=(49×776 mod 83) mod 41＝10 所以有v＝r'，即验证通过。 2．在DSA签字算法中，参数k泄漏会产生什么后果？ 解：如果攻击者获得了一个有效的签名(r,s)，并且知道了签名中采用的参数k，那么由于在签名方程s=k-1(M+xr) mod q中只有一个未知数，即签名者的秘密钥x，因而攻击者可以求得秘密钥x＝r-1(sk－M) mod q，即参数k的泄漏导致签名秘密钥的泄漏。 4.2. 试述DSA数字签名算法，包括密钥产生、签名算法和验证算法，并给出验证过程正确性证明 参考ppt 4.4. 已知schnorr签名的密钥产生和签名算法，试给出验证方程，并证明其正确性。 参考ppt 5.1.试证DSA签名中两次使用相同的会话密钥k，是不安全的 分别给出对m1和对m2的签名表达式,然后将两个关于s的方程联立,这时如果会话密钥k 相同则可直接解出k和秘密钥x，证明过程可根据此思路进行
编译原理 龙书答案
第四章部分习题解答 Aho：《编译原理技术与工具》书中习题 （Aho）4.1 考虑文法 S →( L ) | a L →L, S | S a)列出终结符、非终结符和开始符号 解： 终结符：(、)、a、， 非终结符：S、L 开始符号：S b)给出下列句子的语法树 i)(a, a) ii)(a, (a, a)) iii)(a, ((a, a), (a, a))) c)构造b)中句子的最左推导 i)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, a) ii)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, (L)) ?(a, (L, S)) ?(a, (S, S)) ?(a, (a, S) ?(a, (a, a)) iii)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, (L)) ?(a, (L, S)) ?(a, (S, S)) ?(a, ((L), S)) ?(a, ((L, S), S)) ?(a, ((S, S), S)) ?(a, ((a, S), S)) ?(a, ((a, a), S)) ?(a, ((a, a), (L))) ?(a, ((a, a), (L, S))) ?(a, ((a, a), (S, S))) ?(a, ((a, a), (a, S))) ?(a, ((a, a), (a, a))) d)构造b)中句子的最右推导
i)S?(L)?(L, S) ?(L, a) ?(S, a) ?(a, a) ii)S?(L)?(L, S) ? (L, (L)) ?(L, (L, S)) ?(L, (L, a)) ?(L, (S, a)) ?(L, (a, a)) ?(S, (a, a)) ?(a, (a, a)) iii)S?(L)?(L, S) ?(L, (L)) ?(L, (L, S)) ?(L, (L, (L))) ?(L, (L, (L, S))) ?(L, (L, (L, a))) ?(L, (L, (S, a))) ?(L, (L, (a, a))) ?(L, (S, (a, a))) ?(L, ((L), (a, a))) ?(L, ((L, S), (a, a))) ?(L, ((L, a), (a, a))) ?(L, ((S, a), (a, a))) ?(L, ((a, a), (S, S))) ?(S, ((a, a), (a, a))) ?(a, ((a, a), (a, a))) e)该文法产生的语言是什么 解：设该文法产生语言（符号串集合）L，则 L = { (A1, A2, …, A n) | n是任意正整数，A i=a，或A i∈L，i是1～n之间的整数} （Aho）4.2考虑文法 S→aSbS | bSaS | ε a)为句子构造两个不同的最左推导，以证明它是二义性的 S?aSbS?abS?abaSbS?ababS?abab S?aSbS?abSaSbS?abaSbS?ababS?abab b)构造abab对应的最右推导 S?aSbS?aSbaSbS?aSbaSb?aSbab?abab S?aSbS?aSb?abSaSb?abSab?abab c)构造abab对应语法树 d)该文法产生什么样的语言？ 解：生成的语言：a、b个数相等的a、b串的集合 （Aho）4.3 考虑文法 bexpr→bexpr or bterm | bterm bterm→bterm and bfactor | bfactor bfactor→not bfactor | ( bexpr ) | true | false a)试为句子not ( true or false)构造分析树 解：
最新微机原理第6章习题参考答案
第6章习题参考答案 1．CPU与外部设备通信为什么要使用接口？ 答： CPU要与外部设备直接通信会存在以下两个方面的问题：首先是速度问题，CPU的运行速度要比外设的处理速度高得多，通常仅使用简单的一条输入/输出指令是无法完成CPU与外设之间的信息交换的；其次，外设的数据和控制线也不可能与CPU直接相连，如一台打印机不能将其数据线与CPU的管脚相连，键盘或者其他外设也是如此，同时外设的数据格式千差万别，也不可能直接与CPU 连接。所以，要完成CPU与外部各通信设备的信息交换，就需要接口电路以解决以上问题。 2. I/O接口有什么用途？ 答： 主要由以下几个方面的用途： a完成地址译码或设备选择，使CPU能与某一指定的外部设备通信。 b状态信息的应答，以协调数据传输之前的准备工作。 c进行中断管理，提供中断信号。 d进行数据格式转换，如正负逻辑转换、串行与并行数据转换。 e进行电平转换，如TTL电平与MOS电平间的转换。 f协调速度，如采用锁存、缓冲、驱动等。 h时序控制，提供实时时钟信号。 3.I/O端口有哪两种寻址方式？各有何优缺点？ 答： I/O端口的寻址方式有存储器映像I/O和I/O映像I/O两种寻址方式。存储器映像I/O 方式是将系统中存储单元和I/O端口的地址统一编址，这样一个I/O端口
地址就是一个存储单元地址，在硬件上没有区别，对I/O端口的访问与存储器的访问相同。其缺点是占用了储存器的地址空间，同时由于存储器地址和I/O 端口在指令形式上没有区别，增加了程序设计的难度。其优点是不需要专门为I/O端口设计电路，可与存储器地址访问硬件混合设计。另一个优点是，由于I/O端口和存储器地址是相同的形式，就可以直接使用与存储器相同的指令，这将会丰富对I/O端口的操作指令。 与存储器映像I/O相反，I/O映像I/O就必须为I/O端口设计专门的硬件电路，其端口地址也是独立于存储器，也有专门的输入/输出指令等其优缺点与存储器映像I/O正好相反。 4.在8086微机系统中有个外设，使用存储器映像的I/O寻址方式该外设地址为01000H。试画出其译码器的连接电路，使其译码器输出满足上述地址要求，译码器使用74LS138芯片。 答： 见图6-1
龙书 第四章课后作业答案
P1774.14 为练习4.3的文法构造一个预测语法分析器 bexpr→bexpr or bterm|bterm bterm→bterm and bfactor | bfactor bfactor→not bfactor|(bexpr)|true |false 解1 非递归方法 1)消除左递归 ①bexpr→bterm A ②A→or bterm A ③A→ε ④bterm→bfactor B ⑤B→and bfactor B ⑥B→ε ⑦bfactor→not bfactor ⑧bfactor→(bexpr) ⑨bfactor→true ⑩bfactor→false 2)求first集与follow集 针对以同一非总结符开头的产生式右部求first集如果该非终结符能产生ε则需要求其follow集 ①bexpr→bterm A first(bterm A)= {not,(,true,false} ②A→or bterm A first(or bterm A)={or} ③A→εfollow(A）=follow(bexpr)= {$, )} ④bterm→bfactor B first(bfactor B)={not,(,true,false} ⑤B→and bfactor B first(and bfactor B)={and} ⑥B→εfollow(B）=follow(bterm)=first(A) 因为first(A)= {or , ε} 包含ε 所以follow(B）=follow(bterm) =first(A)∪follow(A）-{ε}={or, $, )} ⑦bfactor→not bfactor first(not bfactor)={not} ⑧bfactor→(bexpr)first((bexpr))={(} ⑨bfactor→true first(true)={true} ⑩bfactor→false first(false)={false} 表中空白处填error，表示调用错误处理程序 4)根据步骤3）编写预测分析程序 下面给出通用的预测分析算法，具体程序留给同学们根据算法自己完善。 repeat
第六章习题参考答案
习题六 6-1 (1) A; (2) C; (3) B; (4) C; (5) A 6-2 ，黑表笔插入COM，红表笔插入V/Ω（红笔的极性为“+”），将表笔连接在二极管，其读数为二极管正向压降的近似值。 用模拟万用表测量二极管时，万用表内的电池正极与黑色表笔相连；负极与红表笔相连。测试二极管时，将万用表拨至R×1k档，将两表笔连接在二极管两端，然后再调换方向，若一个是高阻，一个是低阻，则证明二极管是好的。当确定了二极管是好的以后就非常容易确定极性，在低阻时，与黑表笔连接的就是二极管正极。 6-3 什么是PN结的击穿现象，击穿有哪两种。击穿是否意味着PN结坏了？为什么？ 答：当PN结加反向电压（P极接电源负极，N极接电源正极）超过一定的时候，反向电流突然急剧增加，这种现象叫做PN结的反向击穿。击穿分为齐纳击穿和雪崩击穿两种，齐纳击穿是由于PN结中的掺杂浓度过高引起的，而雪崩击穿则是由于强电场引起的。PN 结的击穿并不意味着PN结坏了，只要能够控制流过PN结的电流在PN结的允许范围内，不会使PN结过热而烧坏，则PN结的性能是可以恢复正常的，稳压二极管正式利用了二极管的反向特性，才能保证输出电压的稳定。 。 对于图(a)假定D1、D2、D3截止，输出端的电位为-18V，而D1、D2、D3的阳极电位分别是-6V、0V、-6V，因此，理论上D1、D2、D3都能导通，假定D1导通，则输出点的电位为-6V，由于该点电位也是D2的阴极电位，因此D2会导通，一旦D2导通，u O点的电位就为0V，因此，D1、D3的阴极电位为0V，而阳极端为-6V，这样D1、D3必定截止，所以输出电压u o=0V（这就是脉冲数字电路中的或门，0V为高电平，-6V为低电平，只要输入端有一个高电平，输出就为高电平）。 对于图(b)依同样的道理可知：D1、D2、D3的阳极电位都低于+18V，所以三个二极管均 截止，流过R的电流为0，故输出电位u o=18V 试分析图(b)中的三个二极管极性都反过来，输出电压u o=？ 6-5 现有两只稳压二极管，它们的稳定电压分别为5V和9V，正向导通电压为0.7V。试问，若将它们串联相接，则可以得到几种稳压值，各为多少？ 答：有四种不同的稳压值，分别是：14V、5.7V、9.7V、1.4V 6-6 二极管电路如题图6-2所示，判断图中的二极管是导通还是截止，并求出AO两端的电压U AO。
编译原理龙书第六章课后作业答案
6.1 假如有下面的Pascal说明 TYPE atype=ARRAY [0..9,-10..10] OF integer; cell=RECORD a,b:integer END; pcell=↑cell; foo=ARRAY [1..100] OF cell; FUNCTION bar(r:integer;y:cell):pcell; BEGIN……END; 写出atype,cell,pcell,foo和bar的类型表达式。 解答: atype: ARRAY(0..9, ARRAY(-10..10, integer)); cell: RECORD((a× integer)× (b×integer)); pcell: POINTER(cell); 或 : POINTER(RECORD((a ×integer)× (b× integer))); foo: ARRAY(1..100, cell); 或 : ARRAY(1..100, RECORD((a ×integer)× (b× integer))); bar: integer× cell→pcell; 或 : integer× cell→POINTER(RECORD((a×integer) ×(b×integer))); 6.4 假定类型定义如下: TYPE link=↑cell; cell=RECORD info:integer; next: link END; 下面哪些表达式结构等价？哪些名字等价？ （1）Link （2）pointer(cell) （3）pointer(Link) （4）pointer(record(info?integer)?(next ? pointer(cell))) 解答:(1)(2)(4)结构等价，无名字等价。
分析化学第六章 习题参考答案
分析化学第六章习 题参考答案 https://www.sodocs.net/doc/b617486828.html,work Information Technology Company.2020YEAR
第六章 习题参考答案 1 解：C 6H 5NH 3+ —C 6H 5NH 2 Fe(H 2O)63+—Fe(H 2O)5(OH)2+ R-NH 2+CH 2COOH —R-NH 2+CH 2COO -(R-NH-CH 2COOH) 2解：Cu(H 2O)2(OH)2—Cu(H 2O)3(OH)+ R-NHCH 2COO -—R-NHCH 2COOH 4 解：(1) MBE: [K +]=C [HP -]+[H 2P]+[P 2-]=C CBE: [K +]+[H +]=[HP -]+2[P 2-]+[OH -] PBE: [H +]+[H 2P]=[OH -]+[P 2-] (2) MBE: [Na +]=C [NH 3]+[NH 4+]=C [HPO 42-]+[H 2PO 4-]+[H 3PO 4]+[PO 43-]=C CBE: [Na +]+[NH 4+]+[H +]=[OH -]+[H 2PO 4-]+2[HPO 42-]+3[PO 43-] PBE: [H +]+[H 2PO 4-]+2[H 3PO 4]=[OH -]+[NH 3]+[PO 43-] (3) MBE: [NH 3]+[NH 4+]=C [HPO 42-]+[H 2PO 4-]+[H 3PO 4]+[PO 43-]=C CBE: [NH 4+]+[H +]=[OH -]+[H 2PO 4-]+2[HPO 42-]+3[PO 43-] PBE: [H +]+[H 3PO 4]=[OH -]+[NH 3]+[HPO 42-]+2[PO 43-] (4) MBE: [NH 3]+[NH 4+]=C [CN -]+[HCN]=C CBE: [NH 4+]+[H +]=[OH -]+[CN -] PBE: [H +]+[HCN]=[OH -]+[NH 3] (5) MBE: [NH 3]+[NH 4+]=2C [HPO 42-]+[H 2PO 4-]+[H 3PO 4]+[PO 43-]=C CBE: [NH 4+]+[H +]=[OH -]+[H 2PO 4-]+2[HPO 42-]+3[PO 43-] PBE: [H +]+[H 2PO 4-]+2[H 3PO 4]=[OH -]+[NH 3]+[PO 43-] 5 解：(1) HA(浓度为C A )+HB(浓度为C B ) 混合酸溶液的PBE:[H +]=[A -]+[B -]+[OH -] 因混合酸溶液呈酸性，故[OH -]可忽略。 [H +]=[A -]+[B -]= ] [][] [][+++ H HB K H HA K HB HA ∴ [H +]=][][HB K HA K HB HA + （1） 若两种酸都较弱（C A /K HA ?400, C B /K HB ?400），则可忽略其解离的影响，此时：[HA]≈C A ,[HB]≈C B (1)式简化为：[H +]=HB B HA A K C K C + （2） （2）NH 4Cl 105 141 106.5108.1101---?=??==b w a K K K , H 3BO 3 Ka 2 =5.8×10-10 因 C 1/Ka 1?400, C 2/Ka 2?400; 由（2）式得： [H +]=151010101.11.0108.51.0106.5----??=??+??L mol pH=4.96 8解：(1)HF Ka=7.2×10-4 C SP ?Ka =0.050×7.2×10-4=3.6×10-5?10-8 故能用0.10mol?L -1NaOH 直接准确滴定。 滴定反应 HF+ NaOH=NaF + H 2O 计量点时pH 取决于NaF 。
第六章习题参考答案
第六章 MCS-51的定时/计数器 1． 如果采用晶振的频率为3MHz ，定时器/计数器工作方式0、1、2下，其最大的定时时间为多少？ 解答：因为机器周期)(410 312126s f T OSC cy μ=?==， 所以定时器/计数器工作方式0下，其最大定时时间为 )(768.321042261313ms T T C MAX =??=?=-； 同样可以求得方式1下的最大定时时间为262.144ms ；方式2下的最大定时时间为1.024ms 。 2． 定时/计数器用作定时器时，其计数脉冲由谁提供？定时时间与哪些因素有关？ 答：定时/计数器作定时时，其计数脉冲由系统振荡器产生的内部时钟信号12分频后提供。定时时间与时钟频率和定时初值有关。 3． 定时/计数器用作定时器时，对外界计数频率有何限制？ 答：由于确认1次负跳变要花2个机器周期，即24个振荡周期，因此外部输入的计数脉冲的最高频率为系统振荡器频率的1/24。 4．采用定时器/计数器T0对外部脉冲进行计数，每计数100个脉冲后，T0转为定时工作方式。定时1ms 后，又转为计数方式，如此循环不止。假定MCS-51单片机的晶体振荡器的频率为6MHz ，请使用方式1实现，要求编写出程序。
解：定时器/计数器T0在计数和定时工作完成后，均采用中断方式工作。除了第一次计数工作方式设置在主程序完成外，后面的定时或计数工作方式分别在中断程序完成，用一标志位识别下一轮定时器/计数器T0的工作方式。编写程序如下： ORG 0000H LJMP MAIN ORG 000BH LJMP IT0P MAIN: M OV TMOD,#06H ；定时器/计数器T0为计数方式2 MOV TL0,#156 ；计数100个脉冲的初值赋值 MOV TH0,#156 SETB GATE ；打开计数门 SETB TR0 ；启动T0，开始计数 SETB ET0 ；允许T0中断 SETB EA ；CPU开中断 CLR F0 ；设置下一轮为定时方式的标志位 W AIT: AJMP W AIT IT0P: CLR EA ；关中断 JB F0,COUNT ；F0=1，转计数方式设置 MOV TMOD,#00H ；定时器/计数器T0为定时方式0 MOV TH0,#0FEH ；定时1ms初值赋值 MOV TL0,#0CH
编译原理 龙书答案
第五章部分习题解答 Aho：《编译原理技术与工具》书中习题 （Aho）5.3 为下面表达式构造有向无环图，标出结点（子表达式）编号，+是左结合的 a + a + (a + a + a + (a + a + a + a)) 解： （Aho）5.5 设计语法制导定义，实现多项式（包含+和*，如x*(3*x+x*x)）的求导，结果无需化简，如3*x直接翻译为3*1+0*x即可。（思路：(xy)?=x?y+y?x，(x+y)?=x?+y?） 解： 综合属性diff为求导后的表示形式，val为原多项式表示形式 E→E1 + T { E.val = E1.val || “+” || E.val; E.diff = E1.diff || “+” || E.diff; } | T { E.val = T.val; E.diff = T.diff; } T→T1 * F { T.val = T1.val || “*” || F.val; T.diff = “(” || T1.diff || “*” || F.val || “+” || T1.val || “*” || F.diff || “)”; } | F { T.val = F.val; T.diff = F.diff; } F→( E ) { F.val = “(” || E.val || “)”; F.diff = “(” || E.diff || “)”; } | num { F.val = num.val; F.diff = 0; } | x { F.val = “x”; F.diff = 1; } 此题和后面两题均可编写Lex&Yacc程序进行验证。 （Aho）5.4 设计翻译模式，实现将中缀表达式翻译为无多余括号形式 解：所谓“多余括号”，可以理解为： 本该是表达式E，写成了(E)的形式， 本该是项T，写成了(T)的形式， 本该是因式F，写成了(F)的形式，因此，可写出文法和翻译模式： E→( E1 ) { E.s = E1.s; } | E1 + T { E.s = E1.s || …+? || T.s; } | T { E.s = T.s; } T→( T1 ) { T.s = T1.s; } | T1 + F { T.s = T1.s || …*? || F.s; } | F { T.s = F.s; }
【《岳飞》文言文】《岳飞》阅读习题及答案
【《岳飞》文言文】《岳飞》阅读习题及答案 内容简介：岳飞（1103－1142）字鹏举，汉族。北宋相州汤阴县永和乡孝悌里（今河南省安阳市汤阴县菜园镇程岗村）人。中国历史上著名战略家、军事家、民族英雄、抗金名将。 ①二十四个循环往复的季节里有你恒温的季节。你，一身盔甲，令所有的对手溃不成军，一腔热血，开始了民族的觉醒，但你挡得住面前的攻打，却经不起背后的谋杀，一场场腥风血雨的战争，开始了你人生的另一段征程...... ②一块中原大地般宽厚的脊背，针针见血地负起母亲的叮咛与沉雄的神州：“精忠报国！”可你却万万没想到，报国路竟是如此曲折。你把民族正义建立在生命之上换来的却是昏君与秦桧等小人的咄咄逼人的话语，你忠于谁，谁就决定你的生死。朝赐你的财物，午赐你的宅院，暮赐你美女的人，就不定何时便赐你一死，可你忙于出征，忙于布阵，忙于厮杀，便不曾留心天子的夸奖是一种带回钩的暗器，你醉心于把战表化成捷报，更不曾留意金銮殿不露声色地已勾勒出了风波亭的雏形…… ③阴谋出笼，出皇城，十二道金牌，十二个夜叉——将忠良捉拿，昨天的猎人，今天的猎物———你角色的转换过于险陡，就连看惯沉浮的黄河，事先都是毫无预感。手上铐子，脚上镣子，颈上枷子，最重要的是驮在背上那母亲的叮嘱，如今成了要命的包袱。不归路上，当竖着的性命同一柄横着的利刃勃然相遇时，你才知晓《满江红》的写作，是从校场熟悉的枪尖上起笔而却在一块陌生的磨刀石上结束的。
④亭间是佞贼一个人的狞笑，亭外是天下无数人的痛哭，屠刀下落，宏文顿成断章！被喷的夕阳涂制页页血帆，浪浪跄，船蹀躞，黄河倒抽一口凉气，刹那改道…… ⑤滚烫的座右铭，一下子变成冰凉的墓志铭，幸亏那识字也识大体的岳母先行一步，否则她，这白发人该怎样去哭祭那黑发的儿郎啊？“精忠报国”的每个字，本都该活上一百年，一千年，一万年，可这区区三十八度春秋，已蓦然成为构思之外的残简。 ⑥你千百年前的一腔热血，已化作历史的一把冷汗，莫须有的罪名造奇冤！谁让你满怀抱负，浑身功夫，却赶上了一个有重病而无良药的时代。宫殿里，龙书案后昏庸的半径，量得出民间黑暗的周长，这绝对是悲的情节，善良遇上恶毒依旧善良，恶毒遇上善良益发恶毒。肯于为良知执言的，只有暴死的良知，能够给邪恶张目的，还是活着的邪恶。莫以为前朝才有怪胎，罪恶也并非偶然的宫外孕。 ⑦看历史要细心，看现实要耐心，同为军人，二十九岁的项羽自杀了，三十八的岳飞被杀了，我总梦见影影绰绰的亭上，有蚊虫剔牙，有苍蝇打嗝，醒来不由惊问：风波亭在哪？它是一颗悬于神州大梁的苦胆，让有志有为的卧薪者品味，明目明心，以认清忠奸。千百年过去了，岳飞也殁了，在那个臭气熏天的黑暗社会中，岳飞走了，他带着“精忠报国”的志向却不明不白地去了，只有天知道，他应该从容地面对，因为———他终于自由了，他终于摆脱了无能的昏君和歹毒的小人，带着他的志向正流芳千古呢！而如今的我们正沐浴在正义的光环下享受着岳飞将军用生命换来的那份自由啊！
软件工程第6章 课后作业参考答案
第六章 作业题参考答案 3．画出下列伪码程序的程序流程图和盒图： START IF p THEN WHILE q DO f END DO ELSE BLOCK g n END BLOCK END IF STOP 答：（1）流程图如图6-1所示： 图6-1 从伪码变成的程序流程图 （2）该程序的盒图如图6-2所示： 图6-2 从伪码变成的程序盒图
4．下图给出的程序流程图代表一个非结构化的程序，请问： （1）为什么说它是非结构化的？ （2）设计一个等价的结构化程序。 （3）在（2）题的设计中你使用附加的标志变量flag吗？若没用，请再设计一个使用flag 的程序；若用了，再设计一个不用flag的程序。 答：（1）通常所说的结构化程序，是按照狭义的结构程序的定义衡量，符合定义规定的程序。图示的程序的循环控制结构有两个出口，显然不符合狭义的结构程序的定义，因此是非结构化的程序。 （2）使用附加的标志变量flag，至少有两种方法可以把该程序改造为等价的结构化程序，图6-3描绘了等价的结构化程序的盒图。 （a）解法1 （b）解法2 图6-3 与该图等价的结构化程序（用flag） （3）不使用flag把该程序改造为等价的结构化程序的方法如图6-4所示。 图6-4 与该图等价的结构化程序（不用flag） 8．画出下列伪码程序的流图，计算它的环形复杂度。你觉得这个程序的逻辑有什么问题吗？ C EXAMPLE LOOP:DO WHILE X>0 A=B+1 IF A>10 THEN X=A ELSE Y=Z END IF
IF Y<5 THEN PRINT X,Y ELSE IF Y=2 THEN GOTO LOOP ELSE C=3 END IF END IF G=H+R END DO IF F>0 THEN PRINT G ELSE PRINT K END IF STOP 答：（1）该伪码的流程图如图6-8所示： 图6-8 程序流程图