【习题课】第1-3章

《【习题课】第1-3章》由会员分享，可在线阅读，更多相关《【习题课】第1-3章（62页珍藏版）》请在金锄头文库上搜索。

1、 第1 3章习题 作业1 5 试用ADL语言编写一个算法 判断任一整数n是否为素数 考察知识点 判断素数素数 大于1的自然数中 除了1和此整数自身外 不能被其他自然数整除的数 判断 对于指定的n 如果 2 n 1 内的整数都不能整除n 则n为素数 ADL语言写算法算法证明很难 可以使用边界条件和特殊数据 人工模拟算法执行过程 完成情况 思想 基本正确 对素数定义的理解 1 算法 特殊情况处理 n 1 算法输出 ADL语言的使用 运算符号 MOD 模 DIV 除数 除 取整 sqrt fabs 输入输出参数 设置返回值 中间用 分隔 条件语句 ifthenelse fori 1tonstep1

2、i i 1 赋值语句 参考答案 算法S n flag 判断整数n是否为素数 将结果保存到变量flag S1 n 1 IF n 1 THEN flag false RETURN S2 初始化 i 2 flag true S3 求余判断 WHILE i n 1 DO IF nMODi 0THEN flag false RETURN i i 1 正确性验证 假定n 7 模拟执行过程 对i 2 3 4 5 6时 分别判断 7modi 的取值是否为0 改进 n 1 n 2 n1 2 n a b a 2 b n 2 a b n 2 a n1 2 b n1 2 a n1 2 b 参考答案2 算法S n fl

3、ag 判断整数n是否为素数 将结果保存到变量flag S1 n 1 IF n 1 THEN flag false RETURN S2 初始化 i 2 flag true S3 求余判断 WHILE i n 2 DO IF nMODi 0THEN flag false RETURN i i 1 作业1 8 若A n amnm a1n a0是关于n的m次多项式 证明A n O nm 设f n 和g n 是正整数集到正实数集的函数 称f n 是O g n 当且仅当存在正常数C和n0 使得对任意的n n0 有f n Cg n 完成情况 令n0 1 C am a1 a0 amnm a1n a0 Cnm注

4、意 当ai 0时 aini ainm不一定成立 证明 对于所有的n 1 有 A n i 0 maini i 0 m ai ni nm i 0 m ai ni m nm i 0 m ai 令C i 0 m ai 有A n Cnm所以 A n O nm 参考答案 作业1 11 证明对正整数n 3 算法BS的元素比较次数T n 5n 3 2 已知 0n 1T n 1n 2T n 2 T n 2 2n 2 考察知识点 数学归纳法基础归纳 n c 初值 时 命题是正确的 归纳步骤 如果n k 1时 命题成立 则n k时 命题也成立 完成情况 利用结论T n 3n 2 2 需要注意前提条件 当n是2的幂时

5、 由n k反推n k 1时的情况 0n 1T n 1n 2T n 2 T n 2 2n 2 n 3时 T 3 T 1 T 2 2 3 5 3 3 2 3 命题成立 假设n k 1 2 k 1 2 即k k 1 2 k 1 2 所以 T k 1 2 5 k 1 2 3 2 1 T k 1 2 5 k 1 2 3 2 2 T k 1 T k 1 2 T k 1 2 2 5 k 1 2 3 2 5 k 1 2 3 2 2 5 k 1 2 k 1 2 3 2 k 1 k 1 2 k 1 2 5 k 1 3 2综上 命题得证 作业1 12 给出算法BS的非递归算法 并说明算法最多需要多大的辅助空间 算法

6、SM A n max min SM1 初始化 max min A 1 SM2 比较 FORI 2TOnDO 求最大和最小元素 IFA I maxTHENmax A I IFA I minTHENmin A I BS算法 算法BS A i j fmax fmin 在数组A的第i个元素到第j个元素之间寻找最大和最 小元素 已知i j BS1 递归出口 IFi jTHEN fmax fmin A i RETURN IFi j 1THEN IFA i A j THEN fmax A j fmin A i ELSE fmax A i fmin A j RETURN BS2 取中值 mid i j 2 B

7、S3 递归调用 BS A i mid gmax gmin BS A mid 1 j hmax hmin BS4 合并 fmax max gmax hmax fmin min gmin hmin 完成情况 做的很少SM方法 没有体现分治思想 依次对比邻近的两个元素 找到较大较小者 不断更新全局最大最小值 依次对比 用数组存放每对的最大最小值 两个栈分别存放当前起始和终止元素下标 一个栈存储中间值 另一个存放最大最小值 没法确定起始和终止元素的下标 辅助空间 因为采用某种特殊结构 而增加占用的空间 占用空间 算法运行所需要的空间 方法3 数组 方法4 栈 方法4 基本思想 创建两个栈 一个存放起始

8、元素的下标 一个存放终止元素的下标 每次从栈中弹出一对下标 若两者相等或相差为1 则找到最大最小值 否则找到中间下标 形成两对新的下标 压入栈内 示例 数组A 3 9 21 15 8 19 1 6 初始 压入起始和结束下标1和6 循环 弹出元素1和6 两者不相等 相差不为1 取中值 1 6 2 3 形成两对新的下标 1 3 和 4 6 压入栈 弹出4和6 两者不相等 相差不为1 取中值 4 6 2 5 形成两对新的下标 4 5 和 6 6 压入栈内 1 3 4 6 1 3 4 5 6 6 A 3 9 21 15 8 19 1 3 4 5 6 6 弹出 6 6 相等 元素值为19 则fmax m

9、ax fmax 19 19 fmin min fmin 19 19 弹出 4 5 相差为1 元素值为15和8 则fmax max 19 15 8 19 fmin min 19 15 8 8 1 3 参考答案 算法f A i j fmax fmin f1 初始化 fmax fmin A i Lstackleft Lstackright 存储起始和终止下标left push i right push j f2 求最大 最小值 While left IsEmpty DO l left pop r right pop IFl rTHEN 相等 fmax max fmax A l fmin min fm

10、in A l ELSE IFr l 1 相差为1THEN fmax max fmax A l A r fmin min fmin A l A r ELSE mid i j 2 left push l left push mid 1 right push mid Right push r 辅助空间 栈 n n 2 n 2 n 4 n 4 1 log2n 作业2 1 编写算法Reverse A n 将顺序存储的线性表A a1 a2 an 转换为A an a2 a1 要求转换过程中使用尽可能少的辅助空间 关键点 限制辅助空间的使用如果没有这个限制 则可以有多种方法 辅助数组 双下标同时向中间移动 分

11、析 只需从线性表的第一个数据元素开始 将第i个数据元素与第n i 1个数据元素相交换即可 i的变化范围是1到 n 2 参考答案 算法Reverse A n A Reverse1 元素互换 FORi 1TO n 2 DOA i A n i 1 作业2 8 在单链表类SLIST中添加一个成员函数 将单链表中元素的次序完全颠倒 利用堆栈 从表头删除 插入表尾 不推荐 换数据域的取值 p1和p2向中间移动 更换数据域的取值 head p1 p2 方法4 思想 从左向右 依次更换邻近结点的指针方向 初始设置 第一个元素需要被放到表尾 指向空指针 p1 null p2 next head 第一个元素 he

12、ad p2 2 p3 3 4 5 p1 null p1 1 p2 6 P3 next p2 next P2 P1 反转P1 P2 P2 P3 参考答案 算法Reverse head head 将指针head所指向的链表倒置 RV1 空链表和1个节点链表 IF next head NULL RETURN RV2 指针初始化 P1 P2分别指向两个连续的节点P1 NULL P2 next head RV3 反转链表 WHILE P2 NULL DO P3 next p2 next P2 P1 反转节点指针P1 P2 P2 P3 移动3个指针 RV4 head指向反转链表 next head P1

13、p1 p2 作业2 11 已知线性表中的元素以data值递增有序排列 并以单链表做存储结构 试写一高效的算法 删除表中所有值大于mink且小于maxk的元素 同时释放被删结点空间 并分析算法的时间复杂度 链表是有序的 找到区间特殊情况的处理 表为空 元素都大于maxk 第一个元素大于maxk 元素都小于mink 最后一个元素小于mink 主要思想 找到大于mink的第一个元素 删除操作 直至元素大于maxk 时间复杂度 比较为基本运算最好 空 元素都大于maxk 找不到 O 1 最坏 元素都小于mink 找不到 元素都小于maxk O n 算法LD L mink maxk LD1 特殊情况 I

14、Fmink maxkTHEN RETURN LD2 初始化 p head prev p p next p LD3 找 WHILE p NULLANDdata p maxk DO IF data p mink THEN prev p p next p 向后移动ELSE next prev next p q p p next p AVAIL q 删除qRETURN prev head p P prev p 作业2 17 对于顺序堆栈和链式堆栈s 分别编写函数SelectItem Stack s intn 要求在堆栈中查找元素n在栈中第一次出现的位置 并将该位置元素移至栈顶 同时其他元素次序不变 注

15、意 用int匹配堆栈的模板 基本思想 取栈顶元素 若不匹配 则进行弹栈操作 找到 或无法找到 后恢复原来的元素次序 关键点 记录弹出的顺序 后弹出的元素能够先被压回原来的栈 因此需要使用一个辅助堆栈 示例 n 51 51 12 10 51 7 3 7 51 51 12 10 3 7 7 3 51 参考答案 intSelectItem Stack 栈非空且当前元素不等于n if s isEmpty s Pop flag true 弹出nwhile temp isEmpty 将辅助栈中元素压入原栈 s Push temp Pop if flag thens Push n elseloc 1 ret

16、urnloc 因为找到元素而跳出循环 作业2 25 编写并实现双端队列类 双端队列是可进行如下操作的线性表 1 push item item插入到队列的前端 2 pop item 删除前端元素且赋给item 3 inject item item插入尾端 4 eject item 删除尾端元素且赋给item 结点结构SLNode 数据域和指针域 类成员 队首和队尾的SLNode类型指针 指示元素个数的整型变量 Push item插入队列前端 若空 则加入一个以item为数据域的结点 元素个数为1 否则 temp记录原队首指针front 创建以item为数据域的新结点 作为新的队首 赋值给front front的指针域指向temp 元素个数加1 Pop 删除前端元素 并赋值item 若空 则错误 否则 temp记录原队首指针front 队首后移 即front next front 返回temp的数据域 删除temp结点 元素个数减1 若大小为零 则队尾指针rear赋值为NULL Inject item插入队尾 若空 则加入一个以item为数据域的结点 元素个数为1 否则 创建以item为数