- 1、本文档共11页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
PAGE2
算法与数据结构C语言描述(第三版)
第1章绪论
1、解释以下概念:逻辑结构,存储结构,操作,数据结构,数据结构的表示,数据结构的实现,抽象数据类型,算法,算法的时间代价,算法的空间代价,大O表示法,贪心法,回溯法,分治法。
答:
逻辑结构(数学模型):
=1\*GB3①指数据元素之间地逻辑关系。
=2\*GB3②具体解释:指数学模型(集合,表,树,和图)之间的关系。
=3\*GB3③描述方式:B=K,R,K是节点的有穷集合,R是K上的一个关系。
存储结构(物理结构):
数据的逻辑结构在计算机存储器中的映射(或表示)。
(3)操作(行为):
指抽象数据类型关心的的各种行为在不同的存储结构上的具体算法(或程序)。
(4)数据结构:
=1\*GB3①传统观念:数据结构是计算机中表示(存储)的、具有一定逻辑关系和行为特征的一组数据。
②根据面向对象的观点:数据结构是抽象数据类型的物理实现。
(5)数据结构的表示:
(6)数据结构的实现:
(7)抽象数据类型:
(8)算法:
是由有穷规则构成(为解决某一类问题)的运算序列。
-算法可以有若干输入(初始值或条件)。
-算法通常又有若干个输出(计算结果)。
-算法应该具有有穷性。一个算法必须在执行了有穷步之后结束。
-算法应该具有确定性。算法的每一步,必须有确切的定义。
-算法应该有可行性。算法中国的每个动作,原则上都是能够有机器或人准确完成的。
(9)算法的时间代价:
(10)算法的空间代价:
(11)大O表示法:
-更关注算法复杂性的量级。
-若存在正常数c和n0,当问题的规模n=c*f(n),则说改算法的时间(或空间)代价为O(f(n))
(12)贪心法:
当追求的目标是一个问题的最优解是,设法把整个问题的求解工作分成若干步来完成。在其中的每一个阶段都选择都选择从局部来看是最优的方案,以期望通过各个阶段的局部最有选择达到整体的最优。
例如:着色问题:先用一种颜色尽可能多的节点上色,然后用另一种颜色在为着色节点中尽可能多的节点上色,如此反复直到所有节点都着色为止;
(13)回溯法
有一些问题,需要通过彻底搜索所有的情况寻找一个满足某些预定条件的最优解。由于彻底搜索的运算量非常大,所以采用一步一步向前试探,当有多重选择是可以任意选择一种,只要目前可行就继续向前,一旦发现失败或问题就后退,回到上一步重新选择,借助于回溯技巧和中间增加判断,这样常常可以大大地减少搜索的时间。
-常见的迷宫问题以及八皇后问题都可以用回溯方法来解决。
(14)分治法
把一个规模较大的问题分成两个或多个较小的与原问题相似的子问题。首先对子问题进行求解,然后设法把子问题进行求解,即对问题分而治之。如果一个问题的规模仍然比较大,不能很容易的求解,就可以对这个子问题重复地应用分治策略。
-二分法检索就是用分治法策略的典型例子。
2、理解以下关系:
答:
算法与数据结构的关系:
=1\*GB3①算法+数据结构=程序
=2\*GB3②程序就是在数据的某些特定的结构和表示的基础上对于算法的描述。
=3\*GB3③算法与数据结构是程序设计中相辅相成、不可分割的两个方面。
数据结构与抽象数据类型的关系:
算法和数据结构问题的求解关系:
3.为整数定义一个抽象数据类型。它包含整数的常见运算,每一个运算对应一个函数,由它的输入/输出定义。
4.什么叫数据结构?试举一个简单的例子说明。
答:=1\*GB3①传统的概念:数据结构是计算机中表示(存储)的、具有一定逻辑关系和行为特征的一组数据。
=2\*GB3②根据面向对象的观点:数据结构是抽象的数据类型的物理实现。
5.从逻辑上可以把数据结构分成哪几类?
答:(1)给定B=K,R,若K1,K2∈R,则称K1为K2的前驱,K2为K1的后继。没有前驱的结点为开始结点,没有后继结点为终端结点。
(2)根据R的特点可以将数据结构分为以下三类:
=1\*GB3①线性结构:K中每个结点最多只有一个前驱和一个后继;
=2\*GB3②树形结构:K中每个结点做多有一个前驱,单可以有多个后继;
=3\*GB3③复杂结构:K中节点的前驱、后继结点的个数都不做限制;
=4\*GB3④集合结构:当R为空集时,K中结点间没有约束关系;
7.将下列复杂度由小到大重新排序:
A、2n B、n!
C、n5 D、10000
E、n*log?n
【答】DECAB
8.将下列复杂度由小到大重新排序:
A.n*log2(n)?? B.n?+?n2?+?n3
C.24 D.n0.5
【答】24
您可能关注的文档
- 3-化粪池安装报验单.doc
- 工程材料进场报验单.doc
- 无机化学与分析南京大学出版社第3章答案.ppt
- 无限极中医养生理念与产品使用1.ppt
- A04工程材料设备进场报验单.doc
- 六年级下册数学习题课件-第5课时--生活中的“促销”问题-习题课件-人教版.ppt
- 工程报验单(路床).doc
- 外研版必修三模块三知识点.ppt
- 《教育学导论》第一章教育.ppt
- 粉喷桩(原铁路)报验单.doc
- 浙江金华市公共资源交易中心永康市分中心编外人员招考聘用笔试历年典型考题及考点研判与答案详解.docx
- 浙江宁波慈溪市政协办公室招考聘用编外工作人员笔试历年典型考题及考点研判与答案详解.docx
- 浙江金华永康市西溪镇人民政府招考聘用笔试历年典型考题及考点研判与答案详解.docx
- 福建南平市公安局建阳分局招考聘用辅警笔试历年典型考题及考点研判与答案详解.docx
- 浙江嘉兴海盐县武原街道基层残疾人工作专职委员(公益岗位)招考聘用笔试历年典型考题及考点研判与答案详解.docx
- 浙江宁波知识产权保护中心招考聘用工作人员笔试历年典型考题及考点研判与答案详解.docx
- 浙江杭州建德市面向2024届普通高校毕业生招考聘用教师(第二批)16人笔试历年典型考题及考点研判与答案详解.docx
- 浙江省台州中学面向2024届普通高校毕业生招考聘用教师12人笔试历年典型考题及考点研判与答案详解.docx
- 湖北师范大学体育学院专任教师招考聘用笔试历年典型考题及考点研判与答案详解.docx
- 重庆市南岸区教育事业单位面向2024届高校毕业生招考聘用114人笔试历年典型考题及考点研判与答案详解.docx
文档评论(0)