《信息学奥赛辅导数据结构基础知识.docx》由会员分享，可在线阅读，更多相关《信息学奥赛辅导数据结构基础知识.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -数据结构基础学问1 依据数据元素间关系的基本特点，有四种基本数据结构： 集合：数据元素间除“同属于一个集合”外，无其它关系。线性结构：一个对一个，如线性表、栈、队列。树形结构：一个对多个，如树。图状结构：多个对多个，如图。2 数据的储备结构一般有两种，用一组物理的址相邻的储备单元来储备数据元素的储备方式称之为次序储备结构 。借助于动态数据结构来储备数据元素的储备方式称之为链式储备结构。3 数组的储备一般采纳的是次序储备结构，如一维数组和多维数组。依据次序往下储备数据。如图14 栈结构的特点是“先进后出”，
2、如图 2 举例说明。5 队列结构的特点是“先进先出”，比如排队买票等，如图3 举例说明。可编辑资料 - - - 欢迎下载精品名师归纳总结Var s:array1.4,1.10 of integer; 就说明数组s 是二维的整型数组，每个元素占2 字节，假设储备第栈 结 构 就 像 一 个 底 部 封 闭队列结构就像底部不封闭的线线 性 表 ， 比 如 进 栈 元 素 的性表，比如进队列元素的次序是序 分 别 为1、2、3，就 出 栈 元1、2、3，就出队列元素的次序可编辑资料 - - - 欢迎下载精品名师归纳总结一个元素的起始的址为100，就它的储备结构如下：的址储备方式100S1,1102S
3、1,2118S1,10120S2,1178S4,10（图 1）素 的 顺 序 分 别3是、2、1，满足“先进后出”原就。进栈出栈（图 2）也是 1、2、3，满意“先进先出”的原就。进队列出队列（图 3）可编辑资料 - - - 欢迎下载精品名师归纳总结6 树结构：树是nn=0 个结点的有限集。（ 1）任意一棵树，只有一个特定的称为根的结点（如图4 中的 A ）。当 n1 时，其余结点可分为 mm0 个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树。（ 2）结点拥有的子树数称为结点的度。（如图 4 中的 B 所拥有的度为2）（ 3）度为 0 的结点称为叶子或终端节点。（如图 4
4、中的 H 、I 、J、K 等都是叶子结点）（ 4）度不为 0 的结点称为非终端结点或分支结点。（ 5）结点的层次从根开头定义起，根为第一层，根的分支为其次层，依此类推（如图4 的树结构最大层次为4 层）。树中结点的最大层次称为树的深度或高度。（如图 4 的树结构的深度或高度为4）（ 6）二叉树是一种特别的树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒，所以二叉树是由根节点、左子树、右子树三个基本单元构成。（ 7）一棵深度为k 的二叉树至多只有2 k 1 个结点 ，此二叉树称为满二叉树（如图 4 为深度为可编辑资料
5、 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -4 的满二叉树） ，最少也有K 个结点（如图5 为深度为4 的最小二叉树） 。 可以验证具有n个叶子结点的满二叉树共有2n 1 个结点 （如图 5 的满二叉树） 。（ 8）在二叉树的第i 层上至多有2 i1 个结点 。（ 9）树的遍历：依据根节点在拜访中的先后位置，我们有三种树的遍历方式。（当然每次拜访都是左子树在右子
6、树的前面。）先序遍历（先拜访根节点，再拜访左子树，最终拜访右子树）：如图 4 的先序遍历为：A、 B、D、H 、I 、E、J、K 、C、F、L 、M 、G、N、O。中序遍历（先拜访左子树，再拜访根节点，最终拜访右子树）：如图 4 的中序遍历为：H、 D、 I、B、J、 E、K 、A 、L 、F、M 、C、N、G、O。后序遍历（先拜访左子树，再拜访右子树，最终拜访根节点）：如图 4 的后序遍历为：H、 I、D、J、 K、 E、B 、L 、M 、F、N 、O、G、C、A 。由上面三种遍历树结构的方式可知，先序遍历最先拜访的是根节点。后序遍历最终拜访的是根节点。由中序遍历的根节点的位置可知，在根节点
7、的左边全部都是根节点的左子树，在根节点的右边全部都是根节点的右子树。必需把握，由任意两种树的遍历结果，能够画出该二叉树，然后依据该二叉树，写出另一种遍历结果。（ 10） 哈夫曼树称为最优树，是一类带权路径长度最短的树。AABCBDEFGCHIJKLMNOD（图 4）（图 5）7 图结构：图是由顶点集V 和边集 E 组成，一般把图G 记为 G（ V ， E）。（ 1）在图 6 中，边有方向性，我们称之为有向图，有向图的边称之为弧。在图 7 中，边没有方向性，即边 和 指的是同一条边，我们称之为无向图。（ 2）在有向图中，从某顶点动身的弧的数目称为该顶点的出度，到达某顶点的有向弧的数目称为该顶点的
8、入度。 （如图 6 的有向图中，顶点V1 的出度为2，入度为 1。）在无向图中，与顶点依附的边的条数称为该顶点的度。（如图 7 中，顶点V1 的度为 2。）（ 3）完全图定义：假如用n 表示图中顶点数目，用e 表示边或者弧的数目，就有：对于有向图， 具有 nn-1 条弧的有向图称为有向完全图任意两个顶点之间都有2 条有向弧 对于无向图，具有nn-1/2 条边的无向图称为完全图（任意两个顶点之间都有一条边。）（ 4）连通图定义： 在无向图中， 如图中任意两个顶点之间都存在路径，就称该无向图为连通图。在有向图中，对于任意两个顶点Vi 和 Vj （Vi Vj ），如从 Vi 到 Vj 和从 Vj 到
9、 Vi 之间均存在路径，就称该有向图为强连通图。（ 5） 带权图定义：有时图的边往往与具有肯定意义的数值有关，我们把这种与图的边相关的数称为边上的权。权可以表示从一个顶点到另一个顶点的距离、费用或代价等，由这种带权的边构成的图称为带权图。（ 6）图的遍历方式有两种：深度优先搜寻和广度优先搜寻。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 -
10、- - 欢迎下载精品名师归纳总结顶点V1V2弧V1V2V3边可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结V3V4（图 6有向图）V4V53（图 7无 向 图 ）可编辑资料 - - - 欢迎下载精品名师归纳总结8 二分法查找：详细方法见课本P147 P148 面。二分法查找（又称折半查找）算法如下：第一需要设三个指示器top、bot、mid ，分别指向查找范畴的顶部、底部和中间位置。假定有11 个元素的有序数列2，5， 7， 10， 14，15， 18，23， 35， 41， 52，待查找数为41，就一开 始 top 1、 bot 11、mid
11、 （ top bot） div 2 6，这是肯定要bot 大于 top，接着进行判定：（ 1）假如 x=amid，就表示找到。（ 2）假如 xamid，就说明待查找数在mid 1 到 bot 之间，转变top mid 1。重复以上过程直到已经找到或无法查找为止。例如查找41，就只需查找3 次即可找到。假设用二分法在有1000 个数据的有序数组中查找某个数据，就最多只需查找10 次即可。（因为 2 101000）9 排序：（ 1）在全部排序方法中,关键字比较的次数与记录的初始排列次序无关的是挑选排序。（ 2）在待排序的数据表已经为有序时，快速排序算法花费时间反而多。10 设循环队列中数组的下标范
12、畴是1n，其头尾指针分别为f 和 r ，就其元素个数为r-f+n MODn。11 哈希表：12 相关练习习题：（ 1）数组 A30.100,20.100以行优先的方式储备, 每个元素占8 个字节 , 且已知 A40 ,30的的址为 2000, 就 A60,90的的址为 :假如以列优先储备, 就为 : （ 2）设栈 S 的初始状态为空, 现有 6 个元素组成的序列1,3,5,7,9,11,对该序列在S 栈上依次进行如下操作 从序列中的1 开头 , 出栈后不在进栈: 进栈 , 出栈 , 进栈 , 进栈 ,进栈 , 进栈 ,出栈 , 进栈 , 问出栈的元素序列是: ,栈顶指针的值为 栈顶元素为: （
13、 3）把中缀表达式写成后缀及前缀表达式可编辑资料 - - - 欢迎下载精品名师归纳总结1） P+Q*A-B/C+D/E-F-G后: 2） A-C*D+B/E*D/A后: （ 4）依据后缀表达式, 写出前缀及中缀表达式ABC/DE+GH-/*+前: 备注：以上这两题实际上考查了数据结构中的表达式树前: 前: 中: 可编辑资料 - - - 欢迎下载精品名师归纳总结（ 5）给出一棵二叉树的中序遍历:DBGEACHFI与后序遍历 :DGEBHIFCA,画出此二叉树（ 6）A=11001010B,B=00001111B,C=01011100B, 就 ABC= B A01011110 B00001111
14、C01011100D11001110 E11001010（ 7）对给定的整数序列54,73,21,35,67,78,63,24,89进行从小到大的排序时, 采纳快速排序的第一趟扫描的结果是可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -A24,21,35,54,67, 78,63,73,89B24,35,21,54,67, 78,63,73,89C24,2
15、1,35,54,67, 63,73,78,89D21,24,35,54,63, 67,73,78,89（ 8）一棵 n 个结点的完全二叉树, 就二叉树的高度h 为An/2Clog2n/2C log2n+1D2n-1（ 9） 设有一个含有 13 个元素的 Hash 表012,Hash 函数是 :Hkey=key %13, 其中 % 是求余数运算。用二次探查法解决冲突 , 就对于序列 、 31、20、33、18、53、27, 就以下说法正确 的 是 。A27 在 1 号格子中B33 在 6 号格子中C31 在 5 号格子中D20 在 7 号格子中E18 在 4 号格子中（ 10）13 历届信息学奥
16、赛试题中的数据结构试题： 挑选题中的数据结构试题：（ 1）（第 10 届）某车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时该站的次序为1,2,3，就车辆出站的次序为（E）A 、1，2， 3， 4，5B、 1， 2，4， 5， 7C、1， 3，5， 4， 6D、1，3， 5， 6，7E、1， 3，6， 5， 7（第 10 届）二叉树 T，已知其前序遍历序列为1 2 4 3 5 7 6 ，中序遍历序列为车站站台为空，从这一时刻开头出入记录为：“进出进进出进进进出出进出”。假设车辆入可编辑资料 - - - 欢迎下载精品名师归纳总结（ 2）其后序遍历序列为 B A 、4 2 5 7 6
17、 3 1B、 4 2 7 5 6 3 1C、4 2 7 5 3 6 1D、4 7 2 3 5 6 1E、4 5 2 6 3 7 14 2 1 5 7 3 6 ，可编辑资料 - - - 欢迎下载精品名师归纳总结（ 3）（第 10 届）满二叉树的叶节点为N，就它的节点总数为（C ）A 、NB 、2NC、 2N-1D、2N+1E、2N-1（ 4）（第 10 届）在下图，从端点（E ）动身存在一条路径可以遍历图中的每条边一次，而且仅遍历一次ABCED（ 5）（第 9 届）一个高度为h 的二叉树最小元素数目是 B 。A) 2h+lBhC2h-1D2hE2h-l（ 6）（第 9 届）已知队列 13，2，
18、11，34， 41， 77， 5，7，18，26， 15，第一个进入队列的元素是 13，就第五个出队列的元素是B 。A5B41C77D13E18（ 7）（第 8 届）一个向量第一个元素的储备的址是100,每个元素的长度是2,就第 5 个元素的的址是 BA 110B 108C 100D 109（ 8）（第 8 届）在全部排序方法中,关键字比较的次数与记录的初始排列次序无关的是 D 。A希尔排序B起泡排序C 插入排序D挑选排序可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 5 页 - - - - - - - - - -可编辑
19、资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -（ 9）（第 7 届）在次序表 2， 5， 7，10， 14， 15， 18， 23， 35， 41，52中，用二分法查找12， 所需的关键码比较的次数为C ，用二分法查找41，所需的关键码比较此数为（B ） 。A2B3C4D5（ 10） （第 7 届）如已知一个栈的入栈次序是1，2，3， n，其输出序列为P1，P2，P3，Pn，如 P1 是 n，就 Pi 是C AiBn-1Cn-i+1D不确定（ 11） （第 6 届）设循环队列中数组的下标范畴是1 n，其头尾指针分别为f 和
20、r，就其元素个数为（D）A.r-fB.r-f+1C.r-fMODn+1D.r-f+nMODn（ 12） （第 6 届）在待排序的数据表已经为有序时，以下排序算法中花费时间反而多的是（D）A. 堆排序B.C.冒泡排序D. 快速排序（ 13） （第 6 届）某数列有1000 个各不相同的单元，由低至高按序排列。现要对该数列进行二分法检索（ binary search ），在最坏的情形下，需检视（B）个单元A.1000B.10C.100D.500（ 14） （第 6 届）已知数组A 中，每个元素AI,J 在存贮时要占3 个字节，设I 从 1 变化到 8，J从 1 变化到 10，安排内存时是从的址SA
21、 开头连续按行存贮安排的。试问：A5,8 的起始的址为（A）A.SA+141B.SA+180C.SA+222D.SA+225（ 15） （第 6 届）线性表如采纳链表存贮结构,要求内存中可用存贮单元的址（D）A. 必需连续B. 部分的址必需连续C.肯定不连续D. 连续不连续均可（ 16） （第 6 届）以下表达中,正确选项（D）A .线性表的线性存贮结构优于链表存贮结构B.队列的操作方式是先进后出C.栈的操作方式是先进先出D.二维数组是指它的每个数据元素为一个线性表的线性表问题求解中的数据结构学问试题：（ 17） （第 9 届）无向图 G有 16 条边， 有 3 个 4 度顶点、 4 个 3
22、度顶点， 其余顶点的度均小于3， 就 G至少有个顶点。（ 18） （第 8 届）如下图 ,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5 共五个车厢。 其中每个车厢可以向左行走,也可以进入栈S 让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出全部可能的到达出口的车厢排列总数不必给出每种排列。出口12345S（ 19） （第 6 届） 1.已知，按中序遍历二叉树的结果为：abc问：有多少种不同形状的二叉树可以得到这一遍历结果，并画出这些二叉树。可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 5 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载