版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
《数据构造》考研真題与考研复习1.1知识要點總結一、数据构造的基本概念1.基础概念和术語(1)数据(Data):数据是客观事物的符号表达。在计算机科學中指的是所有能输入到计算机中并被计算机程序处理的符号的總称。(2)数据元素(DataElement):数据元素是数据的基本單位,在程序中一般作為一种整体来進行考虑和处理。(3)数据项(DataItem):数据项是数据的不可分割的最小單位,数据项是對客观事物的某首先的数据描述。一种数据元素可由若干個数据项(DataItem)构成。(4)数据對象(DataObject):数据對象是性质相似的数据元素的集合,是数据的一种子集。如字符集合C={‘A’,’B’,’C’,…}(5)数据构造(DataStructure):数据构造是指互相之间存在一定联络(关系)的数据元素的集合。元素之间的互相联络(关系)称為逻辑构造。2.数据构造的形式定义数据构造的形式定义是一种二元组:DataStructure=(D,S)其中D是数据元素的有限集,S是D上关系的有限集。数据元素之间的关系可以是元素之间自身代表的某种自然关系,也可以是為了处理問題以便而人為定义的关系,這种自然或人為定义的关系称為数据元素之间的逻辑关系,對应的构造称為逻辑构造。3.数据构造的构成数据构造的三個构成部分:(1)逻辑构造数据元素之间的逻辑关系的描述。数据元素之间的逻辑构造有四种基本类型:①集合:构造中的数据除了“同属于一种集合”外,没有其他关系。②线性构造:构造中的数据元素之间存在一對一的关系。③树形构造:构造中的数据元素之间存在一對多的关系。④图形构造或网状构造:构造中的数据元素之间存在多對多的关系。(2)存储构造数据构造在计算机中的实际体現方式,它包括對数据元素的表达和對关系的表达。存储构造重要有:次序存储、链式存储、索引存储和散列存储。①次序存储构造:用数据元素在存储器中的相對位置来表达数据元素之间的逻辑构造。数据元素寄存的地址是持续的。其長处是可以实現随机存取,存储空间小;缺陷是只能使用相邻的一整块存储單元,轻易产生碎片。②链式存储构造:在每一种数据元素中增長一种寄存另一种元素地址的指针,用该指针来表达数据元素之间的逻辑构造。對数据元素寄存的地址与否持续没有规定。其長处是能充足运用所有存储單元;缺陷是每個結點都需要额外的存储空间,且只能实現次序存取。③索引存储构造:在存储元素信息的同步.還建立附加的索引表。索引表中的每一项称為索引项,索引项的一般形式是:(关键字.地址),关键字唯一標识一种元素,地址作為指向元素的指针。其長处是检索速度快;缺陷是需要额外的存储空间来寄存索引表。④散列(或哈希)存储构造:根据元素的关键字通過哈希函数直接计算出该元素的存储地址。其長处是检索速度快,缺陷是也許存在冲突,而处理冲突會增長時空開销。(3)数据操作對数据要進行的运算。【例】下列有关数据存储构造的论述中,對的的是(
)。A.次序存储方式只能用于存储线性构造B.次序存储方式的長处是占用存储空問小,插入、删除等操作效率高C.链表的每個結點中都恰好具有一种指针D.Hash存储的基本思想是由关键詞的值决定数据的存储地址【答案】D查看答案【解析】次序存储方式除了用于存储线性构造外,還能存储数组或完全二叉树等非线性构造,但在插入、删除操作時,由于要移動大量的数据,执行效率低。链表的形式有單链表、双链表和多重链表,除了單链表外,其他链表中的結點需要两個以上的指针。二、抽象数据类型1.数据类型数据类型(DataType):数据类型是一种值的集合和定义在该集合上的一组操作的總称。2.抽象数据类型抽象数据类型(ADT):是指一种数學模型以及定义在该数据模型上的一组操作。ADT的定义仅是一组逻辑特性的描述,与其在计算机内的表达和实現無关。因此,不管ADT内部构造怎样变化,只要其数學特性不变,都不影响其外部使用。ADT的形式化定义是三元组:ADT={D,S,P}。其中:D是数据對象,S是D上的关系集,P是對D的基本操作集。三、算法分析1.算法(1)概念算法(Algorithm):算法是對特定問題求解措施(环节)的一种描述,是指令的有限序列,其中每一条指令表达一种或多种操作。(2)特性算法由五個特性:①有穷性:一种算法必须總是在执行有穷步之後結束,且每一步都在有穷時间内完毕。②确定性:算法中每一条指令必须有确切的含义,不存在二义性,且算法只有一种入口和出口。③可行性:算法描述的操作都可以通過已經实現的基本运算执行有限次来实現。④输入:一种算法有零個或多种输入,這些输入取自于某個特定的對象集合。⑤输出:一种算法有一种或多种输出,這些输出同输入有著某些特定关系的量。(3)评价原则评价一种好的算法有如下几种原则:①對的性:算法应满足详细問題的需求。②可讀性:算法应轻易供人阅讀和交流。可讀性好的算法有助于對算法的理解和修改。③强健性:算法应具有容錯处理。當输入非法或錯误数据時,算法能合适地做出反应或進行处理。④通用性:算法应具有一般性,处理成果對于一般数据集合都成立。⑤效率和存储量需求:效率指的是算法执行的時间;存储量需求指的是执行過程中所需要的最大存储空间。2.效率的度量(1)時间复杂度算法中的基本操作反复执行的次数是問題规模n的某個函数,其時间度量记做T(n)=O(f(n))(其中“O”是指T(n)的数量级),称作算法的渐進時间复杂度,简称時间复杂度。算法的時间复杂度一般用最深层循环内的語句中的原操作的执行频度(反复执行的次数)来表达。常用的時间复杂度的关系:O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)指数時间复杂度关系為:O(2n)<O(n!)<O(nn)有的状况下,算法中基本操作反复执行的次数會随問題的输入数据集的不一样而不一样(2)空间复杂度空间复杂度指的是算法编写成程序後,在计算机中运行時所需存储空间大小的度量。记做:S(n)=O(f(n)),其中n為問題的规模。空间复杂度一般包括三個方面:①指令常数变量所占用的存储空间。②输入数据所占用的存储空间。③辅助存储空间。【例】有如下算法,其時间复杂度為()。A.O(1)B.O(log2n)C.O(n)D.(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2027年寒假开学摸底考试七年级英语练习卷及答案解析
- 贫困患者医疗救助与关爱
- 2027年安徽省中考一模生物最后一卷及答案
- 胎位异常培训专家讲座
- 2027年四川省高考适应性考试政治押题卷(高清版)
- 滚动轴承钢球市场趋势如何?全球滚动轴承钢球销量已达到54.85万吨
- 交通运输部门安全监管人员安全检查执行考核表
- 化工品质检员岗位考核表
- 电力通信网络维护管理方案手册
- 智能家电服务团队管理与培训手册
- 高甘油三酯血症管理专家共识(2025版)
- 体育场馆安全生产管理台账
- 东航校招的在线测评题目2026
- 2026语文新教材 1第24课《我将无我不负人民》
- 2026安徽省考评员培训考试题库及答案
- 凝心聚力共逐梦家校携手启新程
- 2026年度专项行动保密工作排查整治专项行动方案
- 桥梁伸缩缝更换工程施工组织方案
- 混凝土路面拆除及恢复施工方案
- 2026及未来5年中国航空飞行培训行业市场全景调研及前景战略研判报告
- 2025河南洛阳国裕集团招聘6人笔试参考题库附带答案详解(3卷合一版)
评论
0/150
提交评论