




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、计算机考试公共基础知识,考试内容,基本数据结构与算法 程序设计基础 软件工程基础 数据库设计基础,基本数据结构与算法,数据结构的定义;数据的逻辑结构和存储结构;数据结构的图形表示;线性结构和非线性结构的概念 算法的基本概念;算法复杂度的概念和意义(时间复杂度和空间复杂度) 线性表的定义;线性表的顺序存储结构及其插入与删除运算 栈和队列的定义;栈和队列的顺序存储结构及其基本运算 线性单链表、双向链表与循环链表的结构及其基本运算 树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历 顺序查找与二分法查找算法:基本排序算法(交换类排序、选择类排序、插入类排序),基本数据结构和算法,数
2、据结构概论 算法及其描述 线性表 线性单链表、双向链表与循环链表的结构及其基本运算 栈和队列 树 查找表 基本排序算法,1.数据、数据元素和数据项的概念,数据 客观世界的符号表示,在计算机科学中是指能输入到计算机中并被计算机存储、加工的符号总称。 数据元素 是数据的基本单位。在程序中作为一个整体而加以考虑和处理。也称元素、结点、记录 数据项 数据的不可分割的最小标识单位。,2.数据结构的概念,数据结构是指相互之间存在一种或多种特定关系的数据元素的集合,即数据的组织形式。 数据结构的组成: 逻辑结构:完成数据表示 基本运算:完成数据处理,3.数据的逻辑结构,逻辑结构:数据元素之间的逻辑关系。 逻
3、辑关系:数据元素之间的关联方式。 四种基本逻辑结构 集合:集合中任两个数据元素之间无逻辑关系。 线性结构:数据元素之间存在一对一的关系。 树型结构:分支、层次特性,元素间存在一对多关系 图状结构:最复杂,元素间存在多对多关系 非线性结构中,一个结点可以有多个直接后继,或者有多个直接前驱,或者既有多个直接后继又有多个直接前驱。树型和图状都是非线性结构。,4.数据的存储结构,存储结构(物理结构):数据按逻辑结构规定的关系在计算机存储器中的存放方式。 四种基本的存储方式 顺序存储方式 链式存储方式 索引存储方式 散列存储方式,重点,数据结构的定义 数据的逻辑结构及其图形表示 数据的存储结构 线性结构
4、和非线性结构的概念,基本数据结构和算法,数据结构概论 算法及其描述 线性表 线性单链表、双向链表与循环链表的结构及其基本运算 栈和队列 树 查找表 基本排序算法,1.算法的基本概念,每个算法具有下列五个特性 有穷性 确定性 可行性 输入 输出,2.算法设计的要求,正确性 可读性 健壮性 效率与低存储量需求,3.算法的描述,可以用自然语言,也可以用计算机程序设计语言。,4.算法的时间复杂度和空间复杂度,时间复杂度: 以算法在所有输入下的计算量的最大值作为算法的计算量,这种计算量称为算法的最坏情况时间复杂度。以算法在所有输入下的计算量的加权平均值作为算法的计算量,这种计算量称为算法的平均时间复杂度
5、。 空间复杂度 和时间复杂度类似,但更关心一个算法除输入 数据占用存储空间之外所需的附加存储空间的大小。,重点,算法的基本概念及算法的特性 算法设计的要求 算法复杂度的概念和意义,基本数据结构和算法,数据结构概论 算法及其描述 线性表 线性单链表、双向链表与循环链表的结构及其基本运算 栈和队列 树 查找表 基本排序算法,线性结构与线性表的概念,线性结构: (1)有且只有一个根结点 (2)每一个结点最多有一个前件, 也最多有一个后件 线性表的逻辑结构是线性结构。所含结点的个数称为线性表的长度(表长),表长为0的线性表称为空表。,线性表的顺序存储结构顺序表,顺序表:用一组地址连续的存储单元依次存储
6、线性表的数据元素。 特点:逻辑结构中相邻的结点在存储结构中仍相邻。,插入、删除运算在顺序表上的实现,插入 将结点ai,an各后移一个位置,以便空出第I个位置; 将新结点X置入第I个位置; 表长加1。 删除 结点ai+1,an依次前移一个位置(从而覆盖掉被删结点ai ); 表长减1。,基本数据结构和算法,数据结构概论 算法及其描述 线性表 线性单链表、双向链表与循环链表的结构及其基本运算 栈和队列 树 查找表 基本排序算法,线性表的链式存储结构单链表,基本思想:用指针表示结点间的逻辑关系。 单链表的结点由数据域(data)和指针域(next)组成;指针域用于存放一个指针,指向本结点所含数据元素的
7、直接后继结点。,插入、删除运算在单链表上的实现,插入运算:insert(L,x,i) 在单链表上找到插入位置; 生成一个值为x的新结点; 将新结点链入。 删除运算:Delete(L,i) 找到第I个结点; 从单链表上摘除该结点。,循环链表和双链表,循环链表 同单链表的区别在于其尾结点的链域值不是null,而是一个指向头结点的指针。 判断循环链表是否为空表的条件不是L或L-next是否为空,而是它们是否等于头指针。 双链表 结构:一个数据域和两个指针域(prior域指向直接前驱结点,next域指向直接后继结点) 。 特点:查找结点的前驱和后继都很容易。 p-prior-next=p-next-p
8、rior=p 双链表的插入和删除,重点,线性表的链式存储结构单链表,在单链表上插入与删除结点的操作 双向链表与循环链表的结构 在双向链表中插入与删除结点的基本操作,难点,顺序表和链表的比较 顺序表的主要优点 无需为表示结点间的逻辑关系而增加额外的存储空间; 可以方便地随机存取表中的任一结点。 顺序表的主要缺点 插入和删除运算不方便。 由于顺序表要求占用连续的存储空间,存储分配只能预先进行(静态),因此,当表长变化较大时,难以确定合适的存储规模。,难点,顺序表和链表的比较 链表的特点是用指针表示结点间的逻辑关系。 链表的主要优点 插入和删除运算方便。 链表实现不需要事先估计“容量”,链表占用的存
9、储空间可以随时改变。 链表的主要缺点 为表示结点间的逻辑关系需增加额外的存储空间(指针域)。,基本数据结构和算法,数据结构概论 算法及其描述 线性表 线性单链表、双向链表与循环链表的结构及其基本运算 栈和队列 树 查找表 基本排序算法,栈的定义,栈和队列都是线性结构。 栈是限定在一端进行插入与删除的线性表。 允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。插入、删除操作都在栈顶进行。 栈是按照“先进后出” 或“后进先出” 的原则组织数据的。 在栈中插入一个元素称为入栈运算,从栈中删除一个元素(即删除栈顶元素)称为退栈运算。,例:给定个足够长的栈,若入栈元素的序列为a,b,c,则
10、不_是不可能的出栈序列。 A)bca B)acb C)cab D)bac答案:C,栈的顺序实现,顺序栈的定义及基本概念 栈的顺序存储结构称为顺序栈。顺序栈通常由一个一维数组和一个记录栈顶位置的变量组成。 上溢:当顺序栈的状态为栈满时,如果此时再做进栈运算,由于栈中已无空闲空间,发生“上溢”。 下溢:顺序栈为空栈时,如果做退栈运算,则产生“下溢”。 顺序栈的进栈运算 栈顶下标加1; 将入栈元素放入到新的栈顶下标所指的位置上。 顺序栈的退栈运算 退栈先要将栈顶元素取出,由参数返回,并将栈顶下标减1。,队列的实现,队列是指允许在一端进行插入、而在另一端进行删除的线性表。 允许插入的一端称为队尾,用尾
11、指针(rear)指向队尾元素。 允许删除的一端称为排头(也称队头),用排头指针(front)指向排头元素的前一个位置。 队列又称为“先进先出” 或“后进后出” 的线性表,体现了“先来先服务”的原则。 往队列的队尾插入一个元素称为入队运算,从队列的排头删除一个元素称为退队运算。,队列的顺序实现,顺序队的组织方法,队列的顺序实现,循环队的组织方法及其基本运算 入队操作 sq.rear=(sq.rear+1) % maxsize; sq.datasq.rear=x; 出队操作 sq.front=(sq.front+1) % maxsize; 循环队列的判断队满和队空的方法 队满: (sq.rear+
12、1) % maxsize=sq.front 队空:sq.rear=sq.front 循环队列中包含的元素个数: (sq.rear-sq.front+maxsize) % maxsize,重点,栈的定义 栈顺序存储结构及其基本运算 判定顺序栈栈空与栈满的条件 队列的定义 队列的顺序存储结构及其基本运算 循环队的组织方法、循环队的入队、出队运算和队满、队空的条件,基本数据结构和算法,数据结构概论 算法及其描述 线性表 线性单链表、双向链表与循环链表的结构及其基本运算 栈和队列 树 查找表 基本排序算法,树型结构的基本概念和术语,树的定义 树是n(n=0)个结点的有限集合。在任意一棵非空树中: 有且
13、仅有一个特定的称为根的结点; 当n1时,其余结点分为m个互不相交的非空集合T1、T2,其中每个集合本身又是一棵树,交称为根的子树。,树型结构的基本概念和术语,树型结构的有关术语及其含义 度:树上任一结点所拥有的子树的数目称为该结点的度。 度为0的结点称为叶子或终端结点。度大于0的结点称为非终端结点或分支结点。 一棵树中所有结点的度的最大值称为该树的度。 双亲结点(父结点)、孩子(子结点)、兄弟 层(深度):从根开始算起,根的层数为1,其余结点的层数为其双新的层数加1。一棵树中所有结点层数的最大值称为该树的高度或深度。,二叉树的定义,二叉树是结点的有穷集合,它或者是空集,或者同时满足下述两条件:
14、 非空二叉树只有一个根结点; 每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。 二叉树有五种基本形态。,二叉树的定义,满二叉树 深度为k(K=1),有2k-1个结点(每一层上的结点数都是最大。),二叉树的定义,完全二叉树 二叉树最多只有最后两层有度数小于2的结点,且最下层的结点都集中在该层的最左边的若干位置上。,二叉树的定义,二叉树的基本性质 在二叉树的第k层上,最多有2k1(k1)个结点。 深度为m的二叉树最多有2m1个结点。 在任意一棵二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。 具有n个结点的二叉树,其深度至少为log2n1。,二叉树的顺序存储结构,二叉树的
15、顺序存储的基本思想 按层编号:将一棵树中的所有n个结点按从第一层到最大层、每层从左到右的顺序依次标记为1,2,n。 二叉树的链式存储结构 结点形式为:lchild+data+rchild,二叉树的遍历,含义:按某种次序系统的“访问”二叉树上的所有结点,使得每个结点均被访问一次,而且仅被访问一次。 前序遍历 访问根结点 前序遍历左子树 前序遍历右子树 中序 中序遍历左子树 访问 根结点 中序遍历右子树 后序 后序遍历左子树后序遍历右子树访问根结点。,重点,树的基本概念 二叉树的定义及其性质、满二叉树与完全二叉树 二叉树的存储结构顺序存储与链式存储的实现 二叉树的遍历前序、中序的后序遍历,基本数据
16、结构和算法,数据结构概论 算法及其描述 线性表 线性单链表、双向链表与循环链表的结构及其基本运算 栈和队列 树 查找表 基本排序算法,查找表的基本概念,查找表的基本特点 基本运算包括查找、读表元、插入和删除元素等 静态查找表:查找表一经生成,便只对其进行检索,而不进行修改(插入、删除);或进行了一段时间的检索后集中地进行修改。 动态查找表:检索与修改交叉进行 静态查找表的实现 最简单的实现方法是以顺序表作为存储结构。,查找表的基本概念,顺序查找算法 顺序查找的查找过程 平均查找长度 长度为n的顺序表,在等概率情况下查找成功的平均查找长度为:(n+1)/2;若考虑到查找不成功的情形,则平均查找长
17、度为:3(n+1)/4. 二分查找算法 基本思想:每次将处于查找区间中间位置上的数据元素的键x与给定值K比较,若不等则缩小查找区间,并在新的区间内重复上述过程。,重点,静态查找表的定义 顺序查找的基本思想与算法 二分查找基本思想与算法,基本数据结构和算法,数据结构概论 算法及其描述 线性表 线性单链表、双向链表与循环链表的结构及其基本运算 栈和队列 树 查找表 基本排序算法,排序的基本概念,排序的定义 内部排序与外部排序的概念 内部排序:在排序的整个过程中,数据全部存放在计算机的内存储器中,并且在内存储器中调整记录间的相对位置; 外部排序:数据的主要部分存放在外存储器中,借助内存储器逐步调整记
18、录之间的相对位置。 内部排序算法时间复杂性的度量方法 键值的比较次数 记录的移动次数,插入排序,基本思想 从待排序的记录中任选一个记录(通常是依其存储次序逐一选取),插到已经排好序的那部分记录的正确位置上。 直接插入排序 基本思想:依次将每个记录插入到一个有序的子序列中去。,插入排序,直接插入排序算法的时空性能 正序:比较次数为n-1,移动次数为0,时间复杂度为O(n). 逆序:比较次数为(n+2)(n-1)/2,移动次数为(n-1)(n+4)/2,时间复杂度为O(n2). 直接插入排序是稳定的排序,其平均时间复杂度为O(n2);空间复杂度为O(1)。,交换排序,指在排序过程中,若两个记录的相
19、对位置不符合排好序的要求,则交换位置。 冒泡排序 将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则交换,然后比较第二个记录和第三个记录,该过程称作第一趟冒泡排序,其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡,直到排序结束。 正序:比较次数为n-1,移动次数为0 逆序:比较次数为(n+2)(n-1)/2,移动次数为3n(n-1)/2 冒泡排序是稳定排序,时间复杂度为O(n2) ,空间复杂度为O(1)。,交换排序,快速排序 基本思想:在待排序的n个记录中任取一个记录,以该记录的键值为标准,将所有记录分为两组,使得第一组中各记录的键值均小于等于该键值,第二
20、组中各记录的键值均大于该键值。然后把该记录就排在这两组的中间。此称为一趟快速排序,对所分成的两组分别重复上述方法,直到所有记录都排在适当位置为止。 快速排序是不稳定的。平均时间性能而言,快速排序最佳,时间复杂性为O(nlog2n)。但在最怀情况下,对几乎排好充的输入序列,其效率很低,为O(n2)。对于较小的n值,算法效果不明显;对较大的n值,效果较好。,选择排序,基本方法:从待排序的记录中选择出一个关键字最小(大)的记录,放在已排好序的记录序列之后。 直接选择排序 基本思想:第i趟在n-i+1个记录中选取键值最小的记录作为有序序列的第i个记录。 直接选择排序算法的时、空性能 比较次数:n(n-
21、1)/2 移动次数:正序为0,逆序为3(n-1) 直接选择排序是不稳定的排序,其时间复杂度为O(n2) ,空间复杂度为O(1)。,各种排序方法比较,重点,排序的基本概念,包括:排序的定义、内部排序与外部排序、排序算法时间复杂度的度量 交换类排序冒泡排序和快速排序 选择类排序直接选择排序 插入类排序直接插入排序 常用排序方法的性能比较,例题分析,1.数据的_包括集合、线性结构、树型结构和图状结构四种基本类型。 A.算法描述B.基本运算 C.逻辑结构D.存储结构,答案:C,例题分析,2._中任何两个结点之间都没有逻辑关系。 A.集合B.图状结构 C.树型结构D.线性结构,答案:A,例题分析,3.数
22、据的存储结构包括顺序、_、索引和散列四种基本类型。 A.向量B.数组 C.集合D.链接,答案:D,例题分析,4.计算机算法指的是_。 A.计算方法B.调度方法 C.排序方法D.解决某一问题的有限运算序列,答案:D,例题分析,5.下面_的时间复杂性最好,即执行时间最短。 A.O(n)B. O(nlog2n) C. O(log2n) D. O(n3),答案:C,例题分析,6.把算法的工作量大小和实现算法所需的存储单元多少分别称为算法的 (1) 和 (2) 。 (1)A.可实现性B.时间复杂度 C.困难度D.计算有效性 (2)A.可行性B.高效性 C.可实现性D.空间复杂度,答案:(1)B(2)D,
23、例题分析,7.在一个长度为n的顺序表中,向第I个元素(1=I=n+1)位置插入一个新元素时,需要从后向前依次后移( )个元素。 A.n-iB.i C.n-i-1D.n-i+1,答案:D,例题分析,8.从一个长度为n的顺序表中,删除第I个元素,需要从前向后依次移动( )个元素。 A. iB. n- i C.n-i-1D.n-i+1,答案:B,例题分析,9.对顺序存储的线性表,设其长度为n,在任何位置上插入或删除操作都是等概率的,插入一个元素时平均移动表中的( )个元素。 A.n/2B.(n-1)/2 C.(n+1)/2D.n,答案:A,例题分析,10.在一个长度为n的线性表中顺序查找值为x的元素
24、时,在等概率情况下,查找成功时的平均查找长度( )。 A.n/2B.(n-1)/2 C.(n+1)/2D.n,答案:C,例题分析,11.单链表要求内存中可用存储单元的地址( )。 A.必须是连续的 B.一定是不连续的 C.部分地址必须是连续的 D.可以是连续的,也可以是不连续的。,答案:D,例题分析,12.在单链表中,头指针的作用是( )。 A.方便运算的实现 B.用于标识单链表 C.使单链表中至少有一个结点D.用于标识首结点位置,答案:B,例题分析,13.在一个单链表中,若要删除p指针所指向结点的后继结点,则执行( )。 A.p-next=p B.p=p-next-next C.p-next=p-next-next D.p=p-next;p-next=p-next-next,答案:C,例题分析,14.在一个头指针为ph的单链表中,若要在指针q所指结点的后面插入一个由指针p所指向的结点,则执行( )操作。 A. p-next=q-next ;q=p B. p-next=p-next;q-next=p C. q-next=p-next; p-next=q D. q-next=p-next;p-next=q-next,答案:B,例题分析,15.在循环双链表的p结点之后插入s结点的操作是( )。 A. p-ne
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025个人政治素质自查自评报告
- 厅外调解协议书范本
- 债务转让仲裁协议书范本
- 抢修车辆出售协议书范本
- 小学四年级下学期语文三顾茅庐课件
- 参与旅游环境保护
- 品牌活动策划与执行品牌价值链优化考核试卷
- 热熔粘合技术考核试卷
- 化学试剂在磁性流体磁性颗粒表面活性调控中的应用考核试卷
- 阅读教学实践考核试卷
- 2025年长沙市望城区教育人才引进(28人)笔试备考试题附答案详解(b卷)
- 2025年广元市事业单位继续教育公需科目试题及答案
- 2025河南新乡中和农信延津分公司招聘6人笔试历年参考题库附带答案详解
- 2025新村级后备干部考试题库(附含答案)
- 2025夏秋贵州省旅游产业发展集团有限公司员工招聘115人笔试历年参考题库附带答案详解
- 2025年三明宁化县翠江镇招聘公益性岗位考试笔试试题
- 江苏徐州经济技术开发区教育系统调配教师笔试真题2024
- etc客服电话管理办法
- 系统思维培训
- 食安员考试试题及答案
- DB42T 1049-2015 房产测绘技术规程
评论
0/150
提交评论