NCRE公共基础知识概要.ppt

  1. 1、本文档共130页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
NCRE公共基础知识概要

公共基础知识 主要内容 算法与数据结构 程序设计基础 软件工程基础 数据库设计基础 算法与数据结构 算法的概念、基本特征、基本要素 算法复杂度(时间、空间) 数据结构的概念(逻辑结构、存储结构) 数据结构的图形表示 线性结构和非线性结构 线性结构(数组、栈、队列、线性链表) 非线性结构(二叉树) 查找技术(顺序查找、二分查找) 排序技术(交换类排序 插入类排序 选择类排序) 2. 算法复杂度 空间复杂度:执行算法所占用的临时存储空间。 时间复杂度:设算法解决的问题的规模为n, 运行时间关于问题规模n的一个相对的数量级 就称为该算法的时间复杂度,记为: 0⑴,0(n),0(n2)等。 [2007.9] 下列叙述中正确的是( ) A)数据的逻辑结构与存储结构必定是一一 对应的。 B)由于计算机存储空间是向量式的存储结构, 因此,数据的存储结构一定是线性结构。 C)程序设计语言中的数组一般是顺序存储 结构,因此,利用数组只能处理线性结构。 D)以上三种说法都不对。 (三)线性表及其顺序存储结构 1. 基本概念 线性表由一组数据元素构成,数据元素的位置 只取决于自己的序号,元素之间的相对位置是 线性的。(有限且有序) 在复杂线性表中,由若干项数据元素组成的数 据元素称为记录,而由多个记录构成的线性表 又称为文件。 2. 线性表的结构特征: (1)有且只有一个根结点a1,它无前件。 (2)有且只有一个终端结点an,它无后件。 (3)除根结点与终端结点外,其他所有结点 有且只有一个前件,也有且只有一个后件。 (4)结点个数n称为线性表的长度,当n=0 时,称为空表。 线性表的常见存储方式: 顺序存储结构 链式存储结构 常见线性表: 顺序存储结构的顺序表 链式存储结构的线性链表 入栈运算:从当前栈顶部插入一个新元素。 具体操作:将栈顶指针加1,再将元素插入 到指针所指的位置。 出栈运算:从当前栈顶部取出栈顶元素。 具体操作:将当前栈顶元素取出,再将栈顶 指针减1。 说明: 1)栈顶用TOP表示,栈底用BOTTOM表示。 2)TOP=0,表示空栈;TOP=Maxsize,表示栈满。 3)栈顶会随着入栈和出栈操作不断变化。 顺序队列为空:Front=Rear 顺序队列满: Front= -1,Rear=Maxsize-1 假溢出: 队列的存储区中还有空间,但是却无法继续 做入队操作的现象。 解决方法: 1)所有元素整体平移 2)循环队列 2.2 循环队列 定义:在逻辑上将顺序队列想象成为一个首尾 相连的圆环。 Front指针:指向队头元素的前一个位置 Rear指针:指向队尾元素的位置 存储空间的编号:从0到Maxsize -1 基本操作:入队,出队 循环队列常用判别和计算公式: 设循环队列的存储空间为m ①队列为空:front=rear ②队列满:front=(rear +1) mod m ③出队:front=(front +1) mod m ④入队:rear=(rear -1) mod m ⑤元素个数= (m-front+rear) mod m 或 元素个数=rear-front (rearfront) 元素个数=m-front+rear (rearfront) 完全二叉树的性质: 性质5:具有n个结点的完全二叉树的深度为: k=[log2n]+1 ([log2n]为log2n的值取整) 性质6:设完全二叉树有n个结点。且从根结点 开始从左至右依次用自然数编号。对于编号为 k的结点有如下讨论: 若k=1,则结点是根结点; 若k1,则该结点的父结点编号为INT(k/2)。 插入排序具体算法步骤如下: 1)从第一个元素开始,该元素可以认为已经被排序 2)取出下一个元素,在已经排序的元素序列中从后向前扫描 3)如果该元素(已排序)大于新元素,将该元素移到下一位置 4)重复步骤3,直到找到已排序的元素小于或者等于新元素的位置 5)将新元素插入到该位置中 重复步骤2~5 希尔排序(递减增量排序算法) 基本思想: 是对插入排序的一种改进。 先取一个小于n的整数d1作为第一个增量,把文 件的全部记录分成d1个组。所有距离为d1的倍 数的记录放在同一个组中。先在各组内进行直接 插入排序;然后,取第二个增量d2d1重复上述 的分组和排序,直至所取的增量dt=1,即所有记 录放在同一组中进行直接插入排序为止。 该方法实质上是一种分组插入方法。 堆排序 基本思想: 将数据元素用完全二叉树表示。通过比较二 叉树中根结点和它的左右儿子结点的大小, 调整二叉树,使根结点的值大于左右儿子结 点

文档评论(0)

yaocen + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档