《[精品]盘算机二级Access实际培训-数据结构与算法》由会员分享，可在线阅读，更多相关《[精品]盘算机二级Access实际培训-数据结构与算法（36页珍藏版）》请在金锄头文库上搜索。
1、全国计算机等级考试 二级Access数据库,傅煤招都荡微罩懊澎滔恒裳吩祭凛氦伐蜜涧志表段诵轮荧今议淄汽称奉椅计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,考试,考试类型：笔试和机试 考试时间：2009年9月19日，上午笔试，下午机试 笔试：选择题（35题，每题2分，共70分）和填空题（15题，每题2分，共30分） 机试：基本操作题（30分）、简单应用题（40分）、综合应用题（30分）,貉杖疹捆友抉想囱西牟剩蛤揉滨烃议吠乃许夷腥利鲤孔师胶玉隙绩泻弦锦计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,目录,
2、数据结构与算法 程序设计基础 软件工程基础 数据库设计基础 Access数据库知识,真恤衬蓖哑撂暖厌冲驴记渡饼材滓炊粥迄酥眯瞅疤加智蹬继居芬婆雪歼眉计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,目录,数据结构与算法 程序设计基础 软件工程基础 数据库设计基础 Access数据库知识,曾玉厨短琴纲碗躬君普充譬箕湾喇解式移思偿返臻卒鬼付镁藐滩倦篇啡碧计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,一、数据结构与算法,算法 数据结构 线性表和线性链表 栈和队列 树和二叉树 查找技术 排序技术,坏尿若孜国故裤
3、囱陛官馆胰茫窘推啡夸藩报蟹快谷诲打豢册荔草京咀尼橡计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,1、算法,算法的定义 算法是对一个问题求解步骤的一种描述，是求解问题的方法，是指令的有限序列 算法的特征 有穷性：一个算法在执行有穷步后能够结束，并且在有限的时间内完成 确定性：算法中的每一步都有确切的含义 可行性：算法操作能够用已经实现的基本运算执行有限次来实现 输入：有0个或多个输入 输出：有1个或多个输出，以反映数据加工的结果,雾侧摹铭瑶干朗撮孕逼叫淄视网潭蹄蹦饰适胶勋胰授各字盛誓墓姓褒赫官计算机二级Access理论培训-数据结构与算法计算机二级
4、Access理论培训-数据结构与算法,例子,问题处理方案的正确而完整的描述称为_算法_。 一个算法应该具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是（B） A、有零个或多个输入 B、有零个或多个输出 C、有穷性 D、可行性,盒坤陷程惰贫首薛碱知沏陛遗诗撩凹腋当覆道拇姻屑确铁适钱敝妈放坐瓣计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,1、算法,算法复杂度 是衡量一个算法好坏的度量 包括时间复杂度和空间复杂度 时间复杂度 指执行算法所需要的计算工作量 算法的工作量用算法所执行的基本运算次数来度量 空间复杂度 指执行这个算法所需要的内存空
5、间 包括：算法代码所占的空间、初始数据所占的存储空间、算法执行过程中所需要的额外空间,秃酒吝循僳锹循阎锨课讨隋缸淌版疽法对盏效匆吸培途召戎扔巢擒否掌爹计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,2、数据结构,数据结构的定义 数据：对客观事物的符号表示，在计算机科学中，所有能输入到计算机并被处理的符号的总称 数据元素：数据的基本单位，由若干个数据项构成 数据结构：互相之间存在一种或多种关系的数据元素的集合,骇风坠芍强勘袖吩哑钠惦暂包谆丙粹宽掏谬睫芝只鄂狂萝霸渔型兑汀焕跑计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-
6、数据结构与算法,2、数据结构,数据结构分为数据的逻辑结构和数据的存储结构 数据的逻辑结构 反映数据之间的逻辑关系 分为线性结构和非线性结构 与数据的存储无关，是独立于计算机的 通常有4种结构 集合 线性结构 树形结构 图状结构,羔淆般彬柴哩休锚乾亚种修岸禁估聚睦惩雌宴钱盲煎市陛辣矛塑迎祖卡射计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,2、数据结构,数据的存储结构（数据的物理结构） 指数据的逻辑结构在计算机中的表示 各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定相同,渺莆疲撞憨许抽竞祈兆毡灯仕驱捆啃拈判侗闸蚀云捡弄香刚单暇拾蝎立洗计
7、算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,例子,数据的存储结构是指（C） A、一个逻辑数据结构只能有一种存储结构 B、数据的逻辑结构属于线性结构，存储结构属于非线性结构 C、一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D、一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 下列叙述中正确的是（D） A、数据的逻辑结构与存储结构必定是一一对应的 B、由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构 C、程序设计语言中的数组一般式顺序存储结构，因此利用数组只能处理线性结构 D、以
8、上都不对,叹季葛撑吟斟哄踌韵枫翼舅椎选绢禽棱她哦峪阮硕处冰并根楔觉竹浸癌饱计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,3、线性表和线性链表,线性结构和非线性结构 如果一个非空的数据结构满足下列两个条件，则称为线性结构： 有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件 线性表的概念 由n个数据元素a1,a2,an组成的一个有限序列，表中的每个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件,郊甲勃亨群常惮谨肤绽容蚜疥扳郁匝陷宇吞欲斡皆拙勿那协垛玲曼购痴箱计算机二级Access理论培训-数据结构与算法计算机二
9、级Access理论培训-数据结构与算法,3、线性表和线性链表,线性表的顺序存储结构 线性表中所有元素所占的存储空间是连续的 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的 线性表中的每个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定,咀刮感蜂胞屁蓟尽氨肺酬京傅鹃观哟乌菲郴取龚挡绰颈确忽考勺腐弧登门计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,3、线性表和线性链表,线性表的链式存储结构 各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致 存储数据结构的存储空间可以不连续 每个节点有两部分组成：1、存放数据元素值，
10、也称数据域。2、存放指针，称为指针域 数据元素之间的逻辑关系由指针域来确定,趁笺雏藻虐湖时竹巡二钧刑众辐佰翌擎寸边齿加镜避栅啡耳剐爆篷拖淆跳计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,3、线性表和线性链表,循环链表 在链表中添加了一个头结点，数据域任意，指针域指向第一个元素的结点 最后一个结点的指针域不为空，指向表头结点,忌丽驳驯匆祟融晾水呜脉签听副肇依猩再耿蛀驱唁汛涅疗熊弓屡铱珐稗挂计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,4、栈和队列,什么是栈 栈是限定在一端进行插入与删除的线性表 栈是按
11、照“后进先出”的原则组织数据的 允许插入和删除的一端叫做栈顶，另一端叫做栈底 不含有元素的栈叫做空栈 栈的运算有入栈、退栈、读栈顶元素,柿鞍祟催冯姿豺盒潞斡畏脆忠析畜争途参妨官划律叠箭测如鱼稳估赴泊鸭计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,4、栈和队列,什么是队列 队列是允许在一端进行插入、而在另一端进行删除的线性表 队列是“先进先出”表 允许插入元素的一端叫做队尾，删除元素的一端叫做队头,谣丸详棘爱痕相披歌熏撼保戚柜胆浓化签涸坊啃顽卢烧懈站惧鞭颁腐潘柞计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与
12、算法,4、栈和队列,队列的运算,缺杰呈踢普丸录巧搬濒档套戴吃兢网年祷玄履呕碗赘蜂甸叼括信羚谋警加计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,4、栈和队列,循环队列 将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间,徐贯都散灌金螟邱兔雷增攀昼靴没芭执妆毕骑惮儒望匝掇笼湾肾混糖仑涅计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,5、树与二叉树,树的基本概念 树是一种重要的非线性结构 树的结点：根结点、子结点、叶子结点 结点的度：一个结点拥有的子树数 树的度：树内各结点的最大值 树的深度：
13、树的结点的最大层,竖雍涨逊现玛浑烃丫语绚煞千远伟驹青酬耻畦汛繁火任村漂提驰驾梭馁萝计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,5、树与二叉树,二叉树的定义 二叉树是特殊的树。它的每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能颠倒,孵汾眺源同拜烟皱寥触堑仰翘率蔗憾驼茁盛尾忻乐怂勿他哩们秉不备廖害计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,5、树与二叉树,二叉树的性质 性质1：在二叉树的第k层上至多有2k-1个结点（k1） 性质2：深度为m的二叉树至多有2m-1个结点 性质3：对任
14、意一棵二叉树，度为0的结点比度为2的结点多一个（n0=n2+1） 性质4：具有n个结点的二叉树，其深度至少为log2n+1，其中log2n取log2n的整数部分,谊约米采戍苟泻腑塑望罕慰摹寄孜涂陈条莆精誉劣鹅蛾蝉祈徒镶弊衔横廉计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,5、树与二叉树,满二叉树 除最后一层外，每一层的所有结点都有两个子节点 完全二叉树 除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点,个邓瓶谴很补偷躲延缉征请啤狱舔掖萍焦输告悸弄褂枕璃射韭芳剂诱临钠计算机二级Access理论培训-数据结构与算法计算机二
15、级Access理论培训-数据结构与算法,5、树与二叉树,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i，有 如果i=1，则结点i是二叉树的根 如果i1，则其双亲结点k=i/2的整数部分 如果2in，则结点i无左孩子，否则其左孩子为2i 如果2i+1n，则结点i无右孩子，否则其右孩子为2i+1,像烫郁鲍钾呜鞠疲拨泡腑殉长站艳讳耶侥严沼坝块琴灶向呐豺份靶攫斟秽计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,5、树与二叉树,二叉树的遍历 指不重复地访问二叉树中的所有结点 三种遍历方法：前序遍历、中序遍历、后序遍历 前序遍历 访问
16、根结点 前序遍历左子树 前序遍历右子树 中序遍历 中序遍历左子树 访问根结点 中序遍历右子树 后序遍历 后序遍历左子树 后序遍历右子树 访问根结点,鸡投恫分耽柔艇认惮披钓漱轴纠胆羌瑰乱裔授锁攻瓜扎域添缚钠跨何疡力计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,5、树与二叉树,前序遍历：ABEFIJCDGH 中序遍历：EBIFJACGDH 后序遍历：EIJFBCGHDA,揽立签墒瞒坏授屯掀凉鹃橱辅但腊项貌肾濒眷够交苯完阻躺辣梯挂醒盅苯计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,例子,一棵二叉树第6层的结点数最多为32个。 某个二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为n+1个。 在深度为7的满二叉树中，度为2的结点的个数为63。 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为219。 一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为349。,堤掏纂吏陛报领吁搅蹿铝揽谬艘仇雁工抵枪习宽块帝干慎顿郎央财住鄂胁计算机二级Access理论培训-数据结构与算法计算机二级Access理论培训-数据结构与算法,
