网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311.
第二章公共关系的发展 一、名词解释 1.冯谖市义：据《战国策．齐策四》载,冯谖为孟尝君收债于薛,问:"责(债)毕收,以何市而反?"孟尝君曰:"视吾家所寡有者."冯谖至薛召民合券,因悉焚之,民称万岁;回齐后告孟尝君曰:"君家所寡有者以义耳,窃以为君市义."后因以"市义"谓邀买人心,博取正义的名声. 孟尝君虽然心中不悦,认为无此必要,倒也没有责怪他.事情过去不久,齐王听信谗言,让孟尝君交出相印,退隐薛城.孟尝君离京去薛时,百姓出城十里远迎.消息传回京城,齐王深悔自己不察,迎回孟尝君当面致歉.由于冯谖的远见,使孟尝君避免一场政治波折,并得以巩固自己的地位.这叫做‘未雨而绸缪’,留了条后路. 2.徙木立信：商鞅在咸阳南门竖起一根木杆，宣布谁把它搬到北门，就奖赏十两金子，围观者很多，但都不相信；商鞅又把赏金提高到五十两黄金，于是便有一人半信半疑地将它搬到北门，商鞅果真给付了五十两黄金。由于商鞅言而有信，说话算数，因此很快在群众中树立起了自己的威信，为他以后在秦国成功变法奠定了基础。 3.扒粪运动：19世纪末，美国进入垄断资本主义时代，垄断财团占有着社会的绝大部分财富。他们不择手段地榨取剩余价值，肆无忌惮地搜刮民脂民膏。 为了攫取最大利益，他们全然不顾广大民众、广大劳动人民的利益和最起码的社会道德准则。由于经济危机的爆发，不仅广大劳动人民的生活极度艰难，一大批中小企业和资本家也在垄断财团的疯狂兼并活动中惶惶不可终日。 于是，整个社会的阶级矛盾日益激化，各个阶层和集团之间的利益冲突也日益尖锐，整个社会都对工商寡头产生了敌意。在此情况下，终于爆发了以揭露工商业丑恶和阴暗为主题的新闻揭丑运动，史称“扒粪运动”。 二、问答题 1.答：（1）“和为贵”是公共关系管理的总原则和总目标；
一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ）
精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include
习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Le ｏn ｈar ｄ Ｅul ｅr,１7０7 —17８3)提出并解决了该问题。七桥问题就是这样描述的:一个人就是否能在一次步行中穿越哥尼斯堡(现在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经 过一次,图1、７就是这条河以及河上的两个岛 与七座桥的草图。请将该问题的数据模型抽象 出来,并判断此问题就是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1， 一次步行 2， 经过七座桥,且每次只经历过一次 3， 回到起点 该问题无解:能一笔画的图形只有两类:一类就是所有的点都就是偶点。另一类就是只有二个奇点的图形。 2、在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不就是除法而就是减法。请用伪代码描述这个版本的欧几里德算法 １、r=m-n ２、循环直到r=0?2、１ m ＝n ２、２ n=r ２、3 ｒ=ｍ-n ?3 输出m ３.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码与C ++描述。 //采用分治法 /／对数组先进行快速排序 ／/在依次比较相邻的差 #inc ｌud ｅ ＜ｉostream> ｕsin ｇ n ａｍｅs ｐａc ｅ ｓｔd; in ｔ ｐa ｒｔion ｓ(int b[］,ｉnt l ｏw,ｉnt ｈi ｇｈ) { ｉｎt pr ｖｏtkey=b[lo ｗ]; b ［０］＝b[lo ｗ]; 图1、7 七桥问题
ｗｈile (lｏw<ｈigh) ｛ ｗhilｅ(lｏw 算法设计与分析(第2版)-王红梅-胡明-习题 答案 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783） 提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图 1.7是这条河以及河上的两个岛和七座桥的 草图。请将该问题的数据模型抽象出来，并判 断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n 2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C ++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 图1.7 七桥问题 #include 一、单项选择题 1.一个社会组织的领导者必须对本组织的声誉和形象承担（）。 A.直接责任 B.间接责任 C.技术责任 D.经济责任 2.《<中国公共关系职业道德准则>草拟及实施草案》的提出时间是（）。 A.1985年 B.1988年 C.1989年 D.1991年 3.组织的全员公关培训即指对全员进行公关教育，其重点是（）。 A.政治思想教育 B.思想及意识教育 C.公关知识普及教育 D.公关能力教育 4.在公关人员心理素质中，其最基本的要求是（）。 A.热情心理 B.创新心理 C.开放心理 D.自信心理 5.公关人员所应具有的沟通意识实际上可以说是一种（）。 A.环境意识 B.调查意识 C.协调意识 D.信息意识 6.在组织公关部中主要是按照既定的公共关系目标、计划和方案去开展、管理公共传播活动的人员是（）。 A.调查分析人员 B.计划分析人员 C.文秘人员 D.传播人员 7.某人在组织公关部中主要负责评估组织的形象和公关工作的效果，并寻找出现问题的原因。他属于（）。 A.公关文秘人员 B.公关计划人员 C.调查分析人员 D.公关传播人员 8.从管理作用上看，公共关系职能部门在组织总体中扮演（）。 A.边缘的角色 B.核心的角色 C.无足轻重的角色 D.基础的角色 9.公共关系的（）是执行公共关系任务、实现公共关系功能的载体和行为者，即各类社会组织。 A.客体 B.手段 C.对象 D.主体 10.（）的公共关系主体指的是任何有目的、有系统地组织起来，具有特定功能和任务、具有社会行为能力的社会组织。 A.狭义 B.广义 C.微观 D.宏观 11.下列关于公共关系部门的性质说法错误的是（）。 A.公共关系职能的形成是现代组织管理职能演化的结果 B.专门公共关系职能部门的传播与沟通活动的显著特点是分散随机和不系统 C.从工作性质上看，公共关系的职能是传播性、沟通性的 D.公共关系部门的职能目标和业务内容完全不同于其他的职能部门 第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数，程序1-2的while 循环体做了10次，程序1-3的while 循环体做了14141次（14142-2循环） 若考虑其他语句，则没有这么多，可能就601倍。 第二章 32P 2-8.（1）画线语句的执行次数为 log n ????。(log )n O 。划线语句的执行次数应该理解为一格整体。 （2）画线语句的执行次数为 111 (1)(2) 16 j n i i j k n n n ===++= ∑∑∑。3()n O 。 （3 ）画线语句的执行次数为 。O 。 （4）当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++， 当n 为偶数时画线语句的执行次数为2 (2)4 n +。2()n O 。 2-10.（1）当1n ≥时，225825n n n -+≤，所以，可选5c =，01n =。 对于0n n ≥，22 ()5825f n n n n =-+≤，所以，22 582()n n n -+=O 。 （2）当8n ≥时，2222 582524n n n n n -+≥-+≥，所以，可选4c =，08n =。对于0n n ≥， 22()5824f n n n n =-+≥，所以，22582()n n n -+=Ω。 （3）由（1）、（2）可知，取14c =，25c =，08n =，当0n n ≥时，有22212582c n n n c n ≤-+≤，所以 22582()n n n -+=Θ。 2-11. (1) 当3n ≥时，3 log log n n n <<，所以()20log 21f n n n n =+<，3 ()log 2g n n n n =+>。可选21 2 c = ，03n =。对于0n n ≥，()()f n cg n ≤，即()(())f n g n =O 。注意：是f (n )和g (n )的关系。 （2）当4n ≥时，2 log log n n n <<，所以2 2 ()/log f n n n n =<，2 2 ()log g n n n n =≥。可选1c =，04n =。对于0n n ≥，2 ()()f n n cg n <≤，即()(())f n g n =O 。 （3）因为log log(log )()(log ) n n f n n n ==，()/log log 2n g n n n n ==。当4n ≥时，log(log )()n f n n n =≥， Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答： a.将十进制整数转换为二进制整数的算法 输入：一个正整数n 输出：正整数n相应的二进制数 第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步 第三步：将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1]) 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现 在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 3输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。 编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。 #include for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< 模拟试题2 一．填空题(每空格1分，共25分)察看答案1、 纵观公共关系的产生和发展史，可以大致划分为孕育阶段、______ 和______ 三个时期。 答案：职业化阶段学科化阶段 2、 公共关系是近现代商品经济快速发展，______ 和大众传播 带动的信息社会来临的产物。 答案：政治民主化浪潮日益高涨 3、 公共关系学诞生于本世纪20年代，是当时文化背景、______ 、______ 及技术背景等诸方面历史条件综合作用的结果，是时代进步的必然产物。 答案：政治背景经济背景 二、判断题(正确的打“√”，错误的打“X”。每小题1分，共10分) 正确数/总题数/正确率=0/1/0%察看答案 错错误1、公共关系的产生主要是市场经济取代小农经济的结果。 正确错误 三、单项选择题(在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干后的括号 内。每小题1分，共15分) 正确数/总题数/正确率=0/2/0%察看答案 错误B 1、公共关系的产生、发展之线索，可以追溯到久远时期零散的公共关系观念与不成系统的 （） A、公共关系状态 B、公共关系活动 C、人群关系 D、人际关系 错误D 2、民主政治取代专制政治，这是公共关系产生的( )。 A、文化条件 B、历史条件 C、经济条件 D、政治条件 四、多项选择题(在每小题的五个备选答案中选出二个至五个正确答案，并将正确答案的序号填入题干后面的括号内，错选多选，漏选均不得分。每小题1分，共10分) 正确数/总题数/正确率=0/3/0%察看答案 错误 A B D 1、纵观公共关系的产生和发展史，可以大致划分为几个阶段，它们是 ( )。 A、孕育阶段 B、职业化阶段 C、成熟阶段 D、学科化阶段 E、学科化阶段 错误 A B D E 2、公共关系产生所必需的条件是( )。 A、文化条件 B、政治条件 C、军事条件 D、经济条件 E、技术条件 错误 A C 3、在19世纪中叶至20世纪初，公共关系成为一门社会职业，其催化剂是 ( )。 A、"报刊宣传运动 " B、清除污染运动 C、"清垃圾运动" D、大生产运动 E、"文化运动" 五、简答题(每小题5分，共20分) 1、公共关系产生和发展的社会历史条件是什么? 2、公共关系的未来发展将有何新特点？ 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性: 确定性,有穷性,可行性,0个或多个输入,一个或多个输出。 2.算法的复杂性有时间复杂性和空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低。 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解。 6.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法。 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n})。 9.动态规划算法的两个基本要素是最优子结构和重叠子问题。 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质； ②构造最优值的递归关系表达式； ③最优值的算法描述； ④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ②N1={i|ai 算法分析与设计习题集 基础篇 1、算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？ 2、算法的时间复杂度指的是什么？如何表示？ 3、算法的空间复杂度指的是什么？如何表示？ 4、设某一函数定义如下： 编写一个递归函数计算给定x的M（x）的值。 本函数是一个递归函数，其递归出口是： M（x）= x-10x>100 递归体是： M（M（x+11））x ≤100 实现本题功能的递归函数如下： intm ( intx ) { int y; if ( x>100 )return(x-10 ); else { y =m(x+11) ; return (m (y )); } } 5、已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相 同的元素。 本题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，直到最后一个元素。实现本题功能的函数如下： voiddel ( seqlist*a ) { inti=0, j; while ( i ①计算结点总数 int CountNode(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&rooot->rchild==Null) return(1); else { num1=CountNode(root->lchild); num2=CountNode(root->rchild); return(num1+num2+1); } } ②计算叶子总数 int CountLeafs(BinTree *root) { int num1,num2; if(root==Null) return(0); else if(root->lchild==Null&&root->rchild==Null) return(1); else { num1=CountLeafs(root->lchild); num2=CountLeafs(root->rchild); return(num1+num2); } } 分治术 7、有金币15枚，已知其中有一枚是假的，而且它的重量比真币轻。要求用一个天平将假 的金币找出来，试设计一种算法（方案），使在最坏情况下用天平的次数最少。 8、利用分治策略，在n个不同元素中找出第k个最小元素。 9、设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。 （1）每个选手必须与其它n-1选手各赛一次； （2）每个选手一天只能赛一次。 10、已知序列{503，87，512，61，908，170，897，275，652，462}，写一个自底向上的 归并分类算法对该序列作升序排序，写出算法中每一次归并执行的结果。 void Merge(ElemType *r，ElemType *rf，int u，int v，int t) { f or(i=u，j=v，k=u；i 第二章公共关系的起源与发展 教学目的和要求： 通过本章的学习，了解公共关系的产生与发展的历史过程，把握国内外公共关系的现状，剖析公共关系形成和发展的社会历史条件，认识公共关系的社会历史必然性，更好瞻望公共关系的未来发展。 学习方法：以识记为主，领会公共关系作为一门职业和学科在世界范围内产生发展的历史轨迹，把握公共关系发生与发展的三个历史阶段，尤其需要通过阅读，了解公共关系在中国的传播和发展，以及公共关系在中国的未来走势。 第一节公共关系的起源 公共关系作为一种职业和学科，最早产生于美国。但公共关系作为一种客观的社会现象。作为人类一种朴素的思想意识观念，作为人类一种不自觉的社会活动却早已问世了。 一、古代时期-----公共关系思想的萌芽 1.考古学家发现，远在公元前1800年伊拉克原一种农业公告，很有点像现代社会某些农业组织公共关系部的宣传资料。 2.在古希腊，社会对于沟通技术非常重视.有些深谙沟通学问的第一流演说家常常被推为首领。 古罗马独裁者儒略·凯撒的纪实著作(高卢战记)被公共关系同业工会主席李利·比诺称为“第一流的公共关系著作”。 希腊人认为，较强的修辞能力是参与政治过程的基本条件之一，因为政治家与公众之间的桥梁是靠修辞来架筑的。 古希腊哲学家亚里士多德经典著作《修辞学》被西方公共关系学界认为是最早问世的公共关系学的理论书籍。 3．在我国古代的政治活动、外交活动和军事活动中，亦有许多类似于公共关系活动的成功范例。 1)古代的游说活动 2)古代帝王对民意的重视 3)古代商业经济领域的诚信原则“和” 4)古代军事领域“知彼知己，百战不殆” 这里需要强调指出的是，这仅仅是“类似”而已，公共关系作为一种新的社会思想和活动，其源头并不在古代，而在近代的美国。美国19世纪中叶风行的报刊宣传活动，可以说是公共关系的发端时期，其代表人物是巴纳姆（Phines T.Barnum）。 二、巴纳姆时期------现代公共关系的发端 19世纪中叶在美风行的报刊宣传活动，被认为是现代公共关系业的“前身”。当时最有名的代表人物叫巴纳姆，故将公共关系发展史的这一段时期称为巴纳姆时期。 二、简答题： 1.备忘录方法和动态规划算法相比有何异同简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。 7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面 8.贪心算法求解的问题主要具有哪些性质简述之。 9.分治法的基本思想是什么合并排序的基本思想是什么请分别简述之。 10.简述分析贪心算法与动态规划算法的异同。 三、算法编写及算法应用分析题： 1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。 ①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。 ②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。 ③给出上述算法的递归算法。 ④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。 3.已知1()*() i i k k ij r r A a +=，k =1，2，3，4，5，6，r 1=5，r 2=10，r 3=3，r 4=12，r 5=5，r 6=50，r 7=6，求矩阵链积A 1×A 2×A 3×A 4×A 5×A 6的最佳求积顺序（要求给出计算步骤）。 4.根据分枝限界算法基本过程,求解0-1背包问题。 已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n 公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。 6.试用动态规划算法实现下列问题：设A 和B 是两个字符串。我们要用最少的字符操作，将字符串A 转换为字符串B ，这里所说的字符操作包括： ①删除一个字符。 ②插入一个字符。 ③将一个字符改为另一个字符。 请写出该算法。 7.对于下图使用Dijkstra 算法求由顶点a 到顶点h 的最短路径。 8.试写出用分治法对数组A[n]实现快速排序的算法。 9.有n 个活动争用一个活动室。已知活动i 占用的时间区域为[s i ，f i ]，活动i,j 相容的条件是：sj ≥f i ，问题的解表示为(x i | x i =1，2…，n,)，x i 表示顺序为i 的活动编号活动，求一个相容的活动子集，且安排的活动数目最多。 10.设x 1、x 2、x 3是一个三角形的三条边，而且x 1+x 2+x 3=14。请问有多少种不同的三角形给出解答过程。 11.设数组A 有n 个元素，需要找出其中的最大最小值。 ①请给出一个解决方法，并分析其复杂性。 ②把n 个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和 习题1.1 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d 能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 作业一 学号：______ 姓名：________ P135 2. a.为一个分治算法编写伪代码，该算法同时求出一个元素数组的最大元素和 最小元素的值。 解：算法：EXTREMUM(A[],EXTREMUM_MAX, EXTREMUM_MIN) //递归调用EXTREMUM函数来找出数组A[]的最大元素和 最小元素。 //输入：数值数组A[] //输出：最大值EXTREMUM_MAX和最小值EXTREMUM_MIN if() //只有一个元素 EXTREMUM_MAX A[]; EXTREMUM_MIN A[]; else if //有两个元素 if EXTREMUM_MAX; EXTREMUM_MIN; else EXTREMUM_MAX; EXTREMUM_MIN; else EXTREMUM(,EXTREMUM_MAX_01, EXTREMUM_MIN_01); EXTREMUM(,EXTREMUM_MAX_02, EXTREMUM_MIN_02); if EXTREMUM_MAX_01 EXTREMUM_MAX_02 EXTREMUM_MAX = EXTREMUM_MAX_02; If EXTREMUM_MIN_02 EXTREMUM_MIN_01 EXTREMUM_MIN = EXTREMUM_MIN_02; b. 假设,为该算法的键值比较次数建立递推关系式并求解。 解： c.将该算法与解决同样问题的蛮力法做一个比较 蛮力法时间时间复杂度为2n-2，分治算法的为3n/2-2,虽然都属于Θ(n)级别，但是分治算法速度要比蛮力算法快。 5.1.3 a.为一个分治算法编写伪代码，该算法用来计算指数函数a n的值，其中a>0, n 是一个正整数。 //该算法使用分治法来计算a n Pow(a,n) If n = 1 return a else p←pow(a,n/2); If n mod 2 = 1 return p*p*a; else return p*p; b.建立该算法执行的乘法次数的递推关系式并求解 c.将该算法与解决同样问题的蛮力法做一个比较 蛮力法时间复杂度为n，分治法为,分治法速度明显要 高于蛮力法。 常用算法设计方法 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法，然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0； （2）将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0； （3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)；/*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon)；算法设计与分析第2版王红梅胡明习题答案
自考公共关系学第二章练习题
算法设计与分析C++语言描述(陈慧南版)课后答案
算法设计与分析基础课后习题答案
算法设计与分析(第2版)王红梅胡明习题答案
公共关系学试题及参考答案 第二章
算法设计与分析试题与答案
算法分析与设计习题集
公共关系学第二章
算法分析与设计部分含计算的复习题及参考答案
算法设计与分析基础习题参考答案
《算法设计与分析基础(第3版)》部分习题答案
算法设计与分析(详细解析(含源代码)
相关主题
文本预览
