下载文档原格式
寻找多数元素算法：●变量设置：变量c: 存储当前子序列的候选多数元素；计数器count：记录变量c中元素在已扫描部分中未被删除的个数，实现对序列元素的删除并控制对子序列的递归。
例：注意：序列扫描完成后，变量c存储有序列的候选多数元素，此时，若序列存在多数元素，则必有count>0且c为该多数元素。
●算法：算法5.9 MAJORITY输入：n个元素的数组A[1..n]。
输出：若A[1..n]存在多数元素，则输出；否则输出none。
c=candidate ( 1 ) // 求A[1..n]中的候选多数元素。
count=0 //以下验证c是否为A[1..n]中的多数元素。
for j=1 to nif A[j]=c then count=count+1end forif count > n/2 then return celse return noneend MAJORITY过程candidate ( m )//求A[m..n]中的候选多数元素并返回。
j=m; c=A[m]; count=1while j<n and count>0j=j+1if A[j]=c then count=count+1else count=count-1 //除去两个不同的元素。
end whileif j=n then return c //此时序列已扫描完毕。
else return candidate ( j+1 )//递归求A[j+1..n]中的候选多数元素。
end candidate●时间复杂性：Θ(n)。
第5章函数和代码复用5.1 函数的基本使用[5.1]: A[5.2]: D[5.3]: 错误。
[5.4]: 合法，因为Python语言是解释执行，即只要在真正调用函数之前定义函数，都可以进行合法调用。
5.2 函数的参数传递[5.5]: 在函数定义时，直接为可选参数指定默认值。
可选参数必须定义在非可选参数后面，可选参数可以有多个。
[5.6]: 在函数定义时，可变参数通过在参数前增加星号（*）实现。
可变数量参数只能在参数列表最后，即它只能有一个。
[5.7]: 返回值是元组类型。
[5.8]: 位置传递：支持可变数量参数，但容易忘记实参的含义；名称传递：不易忘记实参的含义，但不支持可变数量参数。
[5.9]: 如果函数里没有创建同名变量，则可以直接使用，不需global声明。
5.3 模块3：datetime库的使用[5.10]:print( "现在是{0:%Y}年{0:%m}月{0:%d}日{0:%I}:{0:%M}".format(datetime.now()))[5.11]: 答案不限。
举一个例子，输出美式日期格式：print("{0:%I}:{0:%M} {0:%b} {0:%d} {0:%Y}".format(datetime.now()))[5.12]: datetime对象可以直接做加减运算，所以可以用这样的方式给程序计时：1 2 Start = datetime.now() ... # 要计时的代码4 5 6 End = datetime.now() Cost = End – Start Print(Cost)5.4 实例7：七段数码管绘制[5.13]: 相当于C语言中的三目运算符。
[5.14]: 隐藏画笔的turtle形状。
[5.15]: 对应相应的年月日文字输出。
5.5 代码复用和模块化设计[5.16]: 错误，因为”使用函数“是“模块化设计“的必要条件。
第5章递归与广义表一、复习要点本章主要讨论递归过程和广义表。
一个递归的定义可以用递归的过程计算，一个递归的数据结构可以用递归的过程实现它的各种操作，一个递归问题也可以用递归的过程求解。
因此，递归算法的设计是必须掌握的基本功。
递归算法的一般形式：void p ( 参数表) {if( 递归结束条件)可直接求解步骤；基本项else p( 较小的参数);归纳项}在设计递归算法时，可以先考虑在什么条件下可以直接求解。
如果可以直接求解，考虑求解的步骤，设计基本项；如果不能直接求解，考虑是否可以把问题规模缩小求解，设计归纳项，从而给出递归求解的算法。
必须通过多个递归过程的事例，理解递归。
但需要说明的是，递归过程在时间方面是低效的。
广义表是一种表，它的特点是允许表中套表。
因此，它不一定是线性结构。
它可以是复杂的非线性结构，甚至允许递归。
可以用多重链表定义广义表。
在讨论广义表时，特别注意递归在广义表操作实现中的应用。
本章复习的要点：1、基本知识点要求理解递归的概念：什么是递归？递归的定义、递归的数据结构、递归问题以及递归问题的递归求解方法。
理解递归过程的机制与利用递归工作栈实现递归的方法。
通过迷宫问题，理解递归解法，从而掌握利用栈如何实现递归问题的非递归解法。
在广义表方面，要求理解广义表的概念，广义表的几个性质，用图表示广义表的方法，广义表操作的使用，广义表存储结构的实现，广义表的访问算法，以及广义表的递归算法。
2、算法设计求解汉诺塔问题，掌握分治法的解题思路。
求解迷宫问题、八皇后问题，掌握回溯法的解题思路。
对比单链表的递归解法和非递归解法，掌握单向递归问题的迭代解法。
计算广义表结点个数，广义表深度，广义表长度的递归算法。
输出广义表各个原子所在深度的非递归算法。
判断两个广义表相等的递归算法。
广义表的按深度方向遍历和按层次（广度）方向遍历的递归算法。
使用栈的广义表的按深度方向遍历的非递归算法。
递归的广义表的删除算法二、难点与重点1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解链表是递归的数据结构，可用递归过程求解有关链表的问题2、递归实现时栈的应用递归的分层(树形)表示：递归树递归深度(递归树的深度)与递归工作栈的关系单向递归与尾递归的迭代实现3、广义表：广义表定义、长度、深度、表头、表尾用图形表示广义表的存储结构广义表的递归算法，包括复制、求深度、求长度、删除等算法三、教材中习题的解析5-1 已知A[n]为整数数组，试写出实现下列运算的递归算法：(1) 求数组A中的最大整数。
第五章习题解答5.1 设一NDPDA识别由下述CFG定义的语言，试给出这个NDPDA的完整形式描述。
S→SASCS→εA→AaA→bC→DcDD→d5.2 消除下列文法的左递归：① G[A]:A→BX∣CZ∣WB→Ab∣BcC→Ax∣By∣Cp② G[E]:E→ET+∣ET–∣TT→TF*∣TF/FF→(E)∣i③ G[X]:X→Ya∣Zb∣cY→ Zd∣Xe∣fZ→X e∣Yf∣a④ G[A]:A→Ba|Aa|cB→Bb|Ab|d5.3 设文法G[<语句>]：<语句>→<变量>: = <表达式>|if<表达式>then<语句>|if<表达式>then<语句>else<语句> <变量>→i<表达式>→<项>|<表达式>+<项><项>→<因子>|<项>*<因子><因子>→<变量>|′(′<表达式>′)′试构造该文法的递归下降子程序。
5.4 设文法G[E]：E→ TE'E'→ + E∣εT→ FT'T'→ T∣εF→ PF'F'→ *F∣εP→ (E)∣ a∣^①构造该文法的递归下降分析程序；②求该文法的每一个非终结符的FIRST集合和FOLLOW集合；③构造该文法的LL（1）分析表，并判断此文法是否为LL（1）文法。
5.5 设文法G[S]：S→ SbA∣aAB→ SbA→ Bc①将此文法改写为LL（1）文法；②求文法的每一个非终结符的FIRST集合和FOLLOW集合；③构造相应的LL（1）分析表。
5.6 设文法G[S]：S→ aABbcd∣εA→ ASd∣εB→ SAh∣eC∣εC→ Sf∣Cg∣εD→ aBD∣ε①求每一个非终结符的FOLLOW集合；②对每一个非终结符的产生式选择，构造FIRST集合；③该文法是LL（1）文法。
第5章课后习题2．假设一条指令的执行过程分为"取指令"、"分析"和"执行"三段，每一段的时间分别为Dt、2Dt和3Dt。
在下列各种情况下，分别写出连续执行n条指令所需要的时间表达式。
(1) 顺序执行方式。
(2) 仅"取指令"和"执行"重叠。
(3) "取指令"、"分析"和"执行"重叠。
3．用一条5个功能段的浮点加法器流水线计算F＝。
每个功能段的延迟时间均相等，流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。
要求用尽可能短的时间完成计算，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率。
4．设有一个15000条指令的程序在一台时钟速率为25MHz的线性流水线处理机上执行。
假设该指令流水线有5段，并且每个时钟周期发射一条指令。
忽略由于转移指令和无序执行造成的损失。
(1) 用该流水线执行这一程序，并用流过延迟与其相等的一个等效非流水线处理机执行同一程序，将两者加以比较，并计算其加速比。
(2) 该流水线处理机的效率是多少？(3) 计算该流水线的吞吐率。
5．设有5段流水线处理机的预约表如下：(1) 列出禁止等待时间和冲突向量集。
(2) 画出状态转换图，说明不引起流水线冲突的所有可能的启动序列（循环）。
(3) 根据状态图列出所有简单循环。
(4) 从简单循环中找出迫切循环。
(5) 此流水线的最小平均等待时间(MAL)是多少？(6) 使用此流水线时，列出可允许的最小恒定循环。
(7) 该流水线的最大吞吐率是多少？(8) 如果使用最小恒定循环，则吞吐率是多少？1 2 3 4 5 6S1 X XS2 X XS3 XS4 XS5 X X6．下列汇编代码在一台3段流水线处理机上执行，每一段都有冒险(相关)检测和分解。
这三段是取指令、取操作数（根据要求取一个或者多个）和执行（包括写回操作）。
