logo资料库

浙江省三级数据库等级考试资料大合集.docx

发布时间：2022-06-05 发布人：admin 分类：说明书 资料大小：0.81M 资料格式：docx 举报 版权申诉
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
资料共19页，剩余部分请下载后查看
    数据结构基础 1） 数据结构的基本概念及有关术语： 数据是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种 符号集合的统称。 表示一个事物的一组数据称为一个数据元素，数据元素是数据的基本单位。它可以是一 个不可分割的原子项，也可以由多个数据项组成。 数据类型是指一个类型和定义在这个类型上的操作集合。 数据结构（data structure）指数据元素之间存在的关系 数据的逻辑结构是指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合 上的若干关系来表示，常被称为数据结构。 根据数据元素之间逻辑关系的不同数学特性，数据结构可分为三种：线性结构、树结构 和图，其中树结构和图又称为非线性结构。P2 数据元素及其关系在计算机中的存储表示或实现称为数据的存储结构，也称为物理结构。 数据的逻辑结构从逻辑关系角度观察数据，与数据的存储无关，是独立与计算机的。而 数据的存储结构是逻辑结构在计算机内存中的实现，是依赖于计算机的。 数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。 数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种 算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。 算法分析主要包含时间代价和空间代价两个方面。 时间代价就是当问题的规模以某种单位由 1 增至 n 时，解决该问题的算法实现运行时所 消耗的时间，也以某种单位由 f(1)增至 f(n)，则称该算法的时间代价为 f(n)。 空间代价就是当问题的规模以某种单位由 1 增至 n 时，解决该问题的算法实现运行时所 消耗的空间，也以某种单位由 g(1)增至 g(n)，则称该算法的空间代价为 g(n)。 算法的时间及空间复杂性 度量算法的时间效率 算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂 度来度量算法的时间效率。T(n)=O(f(n)) 度量算法的空间效率 空间复杂度指算法在执行时为解决问题所需要的额外内存空间，不包括输入数据所占用 的存储空间。 S(n)=O(f(n)) 2） 基本数据结构及其操作： 线性表是由 n(n>=0)个类型相同的数据元素 a0,a1,…,a(n-1)组成的有限序列。P36 线性表的逻辑结构： 其中，元素 ai 的数据类型可以是整数、浮点数、字符或类；n 是线性表的元素个数，称 为线性长度。若 n=0,则为空表；若 n>0,ai(0
    插入、删除操作 单链表的插入操作： 1 空表插入/头插入 if(head==null) head=new Node(x,null); //空表插入 else { Nodeq= new Node(x,null); //头插入 q.next=head; head=q; } 2 中间插入/尾插入 Nodeq= new Node(x,null); q.next=p.next; p.next=q; 单链表的删除操作： 3 头删除 head = head.next; 4 中间/尾删除 if (p.next!=null) p.next = p.next.next; 双链表的插入操作： q = new DLinkNode(x); q.prev = p.prev; q.next = p; p.prev.next = q; p.prev = q; 双链表的删除操作： p.prev.next = p.next; if (p.next!=null) (p.next).prev = p.prev; 3） 数组是一种数据结构，数据元素具有相同的数据类型。 数组逻辑结构与存储结构的关系：数组采用的是顺序存储结构，即使用一组连续的内存 单元依次存放线性表的数据元素，元素在内存的物理存放次序与它们在线性表中的逻辑 次序相同，即元素 ai 与其前驱 a(i-1)及后继 a(i+1)的存储位置相邻。所以数组的存储 结构表现其存储结构。 4） 栈是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。允许操作的一 段称为栈顶，不允许操作的一端称为栈底。栈中插入元素的操作称为入栈，删除元素的 操作称为出栈。没有元素的栈称为空栈。栈的插入和删除只允许在栈顶进行，每次入栈 即成为当前栈顶元素，每次出栈元素总是最后一个入栈元素，因此栈也称为后进先出表。 逻辑结构
    存储结构 采用顺序存储结构的栈称为顺序栈，采用链式存储结构的栈称为链式栈。 进栈、出栈操作：链式栈使用单链表即可，不需要使用循环链表或双链表，并且头结点 的作用不明显。采用不带头结点的单链表实现栈。单链表的第一个结点为站定结点，设 top 指向栈顶结点，入栈操作是在当前栈顶结点之前插入新结点；出栈操作是删除栈顶 结点并返回栈顶元素值，再使 top 指向新的栈顶结点。 5） 队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。允许入队的一 端称为队尾，允许出队的一端称为队头。向队列中插入元素的过程成为入队，删除元素 的过程成为出队。没有元素的队列称为空队列。由于插入和删除操作分别在队尾和队头 进行，最先入队的元素总是最先出队，因此队列也称为先进先出表。 逻辑结构 存储结构 采用顺序存储结构的栈称为顺序队列，采用链式存储结构的栈称为链式队列。 循环队列：如果循环使用顺序队列的连续存储单元，则将顺序队列设计成在逻辑上首尾 相接的循环结构，称为顺序循环队列。 进队、出队操作：以不带头结点的单链表实现链式队列。设指针 front 和 rear 分别指 向队头和队尾结点，入队操作将结点链在队尾结点之后，并使 front 指向新的队尾结点； 出队操作，当队列不空时，取得队头结点值，删除该节点，并使 front 指向后续结点。 6） 二叉树是 n（n>=0）个结点组成的有限集合，n=0 时称为空二叉树；n>0 的二叉树由一个 根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。二叉树也是递归 定义的。 二叉树的性质 性质 1：若根结点的层次为 1，则二叉树第 i层最多有 2i1 （i≥1）个结点。 性质 2：在高度为 k的二叉树中，最多有 2k1 个结点（k≥0）。 性质 3：设一棵二叉树的叶子结点数为 n0，2 度结点数为 n2， 则 n0=n2+1。 性 质 4 ： 一 棵 具 有 n 个 结 点 的 完 全 二 叉 树 ， 其 高 度 。 性质 5：一棵具有 n 个结点的完全二叉树，对序号为 i（0≤i ＜n）的结点，有： 1 若 i=0，则 i为根结点，无父母结点；若 i>0， 则 i的父母结点序号为。 2 若 2i+1＜n，则 i的左孩子结点序号为 2i+1；否 则 i无左孩子。 3 若 2i+2＜n，则 i的右孩子结点序号为 2i+2；否 则 i无右孩子。 二叉树的存储结构 1. 二叉树的顺序存储结构
    顺序存储结构仅适用于完全二叉树跟满二叉树。 2. 二叉树的链式存储结构 二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问 一次。虽然二叉树是非线性结构，但遍历二叉树访问结点的次序是线性的，而且访问的 规则和次序不止一种。二叉树的遍历规则有孩子优先和兄弟优先。 孩子优先： 先根次序：访问根结点，遍历左子树，遍历右子树。 中根次序：遍历左子树，访问根结点，遍历右子树。 后根次序：遍历左子树，遍历右子树，访问根结点 二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：（1） 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空， 则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序 树。 哈夫曼树 定义为带权外路径长度最短的二叉树 路径长度：从根结点到所有结点的路径长度之和
    (a)、(b)、（c）、(d)的路径长度为 1x2+2x2+3x2=12 外路径长度：从根结点到所有叶子结点的路径长度之和 从根到 X 结点的带权路径长度是 X 结点的权值与从根到 X 结点路径长度的乘积。所有叶子结 (a)、(b)、（c）、(d)的外路径长度为 2+3x2+1=9 点的带权路径长度之和称为二叉树的带权外路径长度。 二叉树的带权外路径长度 WPL  n 1   w l i i ( ) i  0 7） 检索方法： （P259）顺序查找算法描述为：从线性表的一端开始，依次将每个元素的关键字与给定 值进行比较，若有相等者，则查找成功；否则比较继续，直到比较完所有元素，仍未有 相等者，则查找不成功，给出结果信息。平均查找长度为（n+1）/2,查找一个元素的平 均比较次数为 n，查找失败需比较 n+1 次，时间复杂度为 O(n)。 查找成功的平均查找长度： ASL 成功  ( cp ) i i  n   i 1  1 n n   i 1 i  1 n   ( nn 2 )1  1 n  2  nO )(
    查找失败的平均查找长度： ASL 不成功  n   i 1  cp ( ) i i  n   i 1 ( 1 n  nOnn )(   ) （P262）二分查找又叫折半查找，时间复杂度为 O(log2n)。 折半查找算法分析 8） 排序方法： 直接插入排序总的关键码比较次数为 n^2/4，总的记录移动个数也约为 n^2/4；二分法 插入排序关键码比较次数为 O(nlog2n),记录移动个数为 O(n^2)；shell 排序法的关键码
    比较次数和记录移动个数均为 n^1.3 左右。冒泡排序的最坏时间复杂度为 O(n2),最好的 时间复杂度为 O(n)，算法的平均时间复杂度为 O(n2)。快速排序的最坏时间为 O(n^2)， 平均时间复杂度为(nlgn)。 插入排序：每趟将一个元素，按其关键字大小插入到它前面已排序的子序列中，使得插 入后的子序列仍是排序的，依此重复，直到全部元素插入完毕。 直接插入排序 数据序列已排序（最好情况）的时间复杂度为 O（n） 数据序列反序排列（最坏情况）的时间复杂度为 O（n 的平方） 数据序列随机排列的时间复杂度为 O（n 的平方） 折半插入排序 希尔排序
    交换排序 冒泡排序的基本思想是：比较相邻两个元素的关键字值，如果反序，则交换。若按升序 排序，每趟将被扫描的数据序列中的最大元素交换到最后位置，就像气泡从水里冒出来 一样。
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料