数据结构与算法（B）2018春季 习题(H4、H7).

Presentation on theme: "数据结构与算法（B）2018春季 习题(H4、H7)."— Presentation transcript:

1 数据结构与算法（B）2018春季 习题(H4、H7)

2 H4 线性表 程序若没有按照要求实现，得0分；否则通过所有测试用例得2分， 通过部分测试用例得1分，所有测试用例均不通过得0分
若按照要求实现程序才可以正常得分 代码风格好得风格分1分，否则0分 程序题的最终得分为所有程序题得分*3/8，共3分；风格分为1分。 程序分和风格分合计4分，最终得分为向上取最接近0.5倍数的值。 在提交的作业中，最高得分为4分，最低得分为1分。

3 中缀转前缀 从右到左扫描中缀表达式单词列表 如果单词是一个操作数，则直接添加到前缀表达式列表的末尾
如果单词是一个右括号“)”，则压入opstack栈顶 如果单词是一个左括号“(”，则反复弹出opstack栈顶的操作符，加 入到输出列表末尾， 直到碰到右括号 如果单词是一个操作符“*/+-”，则压入opstack栈顶。但在压入之 前，要比较其与栈顶操作符的优先级，如果栈顶的高于它，就要 反复弹出栈顶操作符，加入到输出列表末尾 ，直到栈顶的操作符 优先级低于它 最后反转输出列表

4 中缀转前缀 可以先把中缀表达式反转，然后将“（”变成“）”，“）”变成“（”， 调用中缀转后缀算法得到一个后缀表达式，然后再反转该后缀表 达式得到所求的前缀表达式

5 中缀转前缀

6 扩展括号匹配算法 先找出所有有效的html标签
维护一个栈，按标签出现顺序遍历所有标签。如果标签是起始标 签，则将该标签入栈；否则将其和栈顶标签匹配。如果能匹配， 则弹出栈顶元素，继续遍历过程，否则算法结束，输出False。标 签遍历完后，若栈中元素个数为0，则说明html标签都可以匹配， 输出True，否则说明html标签无法全部匹配，输出False。

7 扩展括号匹配算法

8 基数排序算法

9 击鼓传花

10 H7 动态规划 若程序的时间复杂度是多项式级，得0分；否则通过所有测试用 例得2分，通过部分测试用例得1分，所有测试用例均不通过得0 分
程序的时间复杂度是多项式级才可以正常得分 代码风格好得风格分1分，否则0分 每道题如果得0分，只要交了，就修正为1分 分数计算公式为所有程序题得分和*3/4，共3分；风格分为1分。 程序分和风格分合计4分，最终得分为向下取最接近0.5倍数的值。 在提交的作业中，最高得分为4分，最低得分为1.5分。

11 博物馆大盗问题 设dp[i+1][j]为从前i个物品中选出总重量不超过j的物品时总价值的 最大值 dp数组的初值都为0
当j < treasure[i][‘w’]时，dp[i+1][j] = dp[i][j] 当j >= treasure[i][‘w’]时，dp[i+1][j] = max(dp[i][j], dp[i][j - treasure[i]['w']] + treasure[i]['v’])

12 博物馆大盗问题 输出选取物品的序号时，可以逆向遍历treasure数组。设j为未使 用的物品重量，i为第i个treasure。当dp[i][j] > dp[i-1][j]时说明选择 了第i-1个物品。对于输入treasure, maxw = [{‘w’:2,‘v’:3}, {‘w’:3,‘v’:4}, {‘w’:4,‘v’:5}] , 7，逆序遍历的顺序为 i\j 1 2 3 4 5 6 7 8 9

13 单词最小编辑距离问题 该问题可以转化为最长公共子序列（LCS，Longest Common Subsequence）问题。该问题的描述如下：
比如abcd和becd是最长公共子序列就是bcd。 求出两个单词的最长公共子序列之后，原单词中不在公共子序列 里的字母需要删除，目标单词中不在公共子序列中的字母需要插 入，而公共子序列中的字母进行复制即可。

14 单词最小编辑距离问题 最长公共子序列问题的求解如下：
设dp[i][j]为s1 s2 …si 和t1 t2 …tj 的最长公共子序列的长度，则s1 s2 …si+1 和t1 t2 …tj+1 的最长公共子序列要么是当si+1 = tj+1 时在公共 子序列后面添加tj+1 ，要么是s1 s2 …si 和t1 t2 …tj+1 的公共子序列， 要么是s1 s2 …si+1 和t1 t2 …tj的公共子序列，因而

15 单词最小编辑距离问题 输出所求的最长公共子序列时，可以逆序遍历dp数组，只有当 dp[i][j] = dp[i-1][j-1]且dp[i][j]!= dp[i-1][j]且dp[i][j]!= dp[i][j-1]的时候 才说明s[i-1]和t[j-1]是公共子序列中的一部分 j\i 1(b) 2(e) 3(c) 4(d) 1(a) 2(b) 1 2 3