超星 - 算法分析与设计模拟测试 - 查题吧

简答题

(8分）阅读“算法5”，分析算法的功能，并给出一个例子，展示算法的运行过程。算法5：MergeSort (int A[]，int low，int high){if(low

查看答案

简答题

（8分）给定5种字符a,b,c,d,e及它们出现的频率0.45,0.25,0.15,0.10,0.05，选择一种编码方法，求这5个字符的编码方案。（1）描述所用的编码方法（4分）（2）给出5个字符的编码（2分）（3）求该编码方案的平均码长（2分）

简答题

（12分）给定序列X={E,F,G,A, B,E}和Y={E,B, D, F,A, G}，求它们的最长公共子序列。（1）写出所用的求解方法（2分）（2）描述该方法求解的步骤（4分）（3）给出求解过程（4分）（4）给出求解结果（2分）

简答题

（15分）0-1背包问题：给定n个物品，1个背包，背包容量为W，n个物品的重量和价值分别为：(wi,vi)i=1,2,3,...,n。物品不能分割，请设计一算法，求解在不超过背包容量的前提下，怎么装能够使得装入的物品总价值最大。（1）给出选用的算法策略（2分）（2）写出该算法策略的思想（4分）（3）写出存储0-1背包问题的输入、输出所用的数据结构（2分）（4）给出求解问题的算法步骤（可以选择自然语言、伪码、流程图、程序设计语言中的任何一种形式描述）（7分）

简答题

（15分）最优装载问题：给定n个箱子，其重量为wi（i=1,2,3,...,n)），某艘船的载重量为C，船的体积不受限制，在不超过船的载重量的前提下，设计一算法，将尽量多的箱子装到船上。（1）给出选用的算法策略（2分）（2）写出该算法策略的思想（4分）（3）写出存储最优装载问题的输入、输出所用的数据结构（2分）（4）给出求解问题的算法步骤（可以选择自然语言、伪码、流程图、程序设计语言中的任何一种形式描述）（7分）

1