《2022年信息学奥赛辅导数据结构基础知识 .pdf》由会员分享，可在线阅读，更多相关《2022年信息学奥赛辅导数据结构基础知识 .pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构基础知识1 根据数据元素间关系的基本特征，有四种基本数据结构：集合：数据元素间除“同属于一个集合”外，无其它关系。线性结构：一个对一个，如线性表、栈、队列。树形结构：一个对多个，如树。图状结构：多个对多个，如图。2 数据的存储结构一般有两种，用一组物理地址相邻的存储单元来存储数据元素的存储方式称之为顺序存储结构；借助于动态数据结构来存储数据元素的存储方式称之为链式存储结构。3 数组的存储一般采用的是顺序存储结构，如一维数组和多维数组。按照顺序往下存储数据。如图1 4 栈结构的特点是“先进后出”，如图 2 举例说明。5 队列结构的特点是“先进先出”，比如排队买票等，如图3 举例说明。Va
2、r s:array1.4,1.10 of integer;则说明数组s是二维的整型数组，每个元素占2 字节，假设存储第一个元素的起始地址为100，则它的存储结构如下：地址存储方式100 S1,1 102 S1,2 118 S1,10 120 S2,1 178 S4,10（图 1）栈 结 构 就 像 一 个 底 部 封 闭线 性 表，比 如 进 栈 元 素 的序 分 别 为 1、2、3，则 出 栈 元素 的 顺 序 分 别 是3、2、1，满足“先进后出”原则。进栈出栈（图 2）队列结构就像底部不封闭的线性表，比如进队列元素的顺序是1、2、3，则出队列元素的顺序也是 1、2、3，满足“先进先出”的
3、原则。进队列出队列（图 3）6 树结构：树是n(n=0)个结点的有限集。（1）任意一棵树，只有一个特定的称为根的结点（如图4 中的 A）；当 n1 时，其余结点可分为 m(m0)个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树。（2）结点拥有的子树数称为结点的度。（如图 4 中的 B 所拥有的度为2）（3）度为 0 的结点称为叶子或终端节点。（如图 4 中的 H、I、J、K 等都是叶子结点）（4）度不为 0 的结点称为非终端结点或分支结点。（5）结点的层次从根开始定义起，根为第一层，根的分支为第二层，依此类推（如图4 的树结构最大层次为4 层）。树中结点的最大层次称为树的深度
4、或高度。（如图 4 的树结构的深度或高度为4）（6）二叉树是一种特殊的树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒，所以二叉树是由根节点、左子树、右子树三个基本单元构成。（7）一棵深度为k 的二叉树至多只有2 k1 个结点，此二叉树称为满二叉树（如图 4 为深度为4 的满二叉树），最少也有K 个结点（如图5 为深度为4 的最小二叉树）。可以验证具有n个叶子结点的满二叉树共有2n1 个结点（如图 5 的满二叉树）。（8）在二叉树的第i 层上至多有2 i1个结点。（9）树的遍历：按照根节点在访问中的先后位置，我们有
5、三种树的遍历方式。（当然每次访问都是左子树在右子树的前面。）先序遍历（先访问根节点，再访问左子树，最后访问右子树）：如图 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。由上面三种遍历树结构的方式可知，先序遍历最先访问的是根节点；后序遍历最后访问的是根节点；由中序遍历的根节点的位置可知，在根节点
6、的左边全部都是根节点的左子树，在根节点的右边全部都是根节点的右子树。必须掌握，由任意两种树的遍历结果，能够画出该二叉树，然后根据该二叉树，写出另一种遍历结果。（10）哈夫曼树称为最优树，是一类带权路径长度最短的树。A B C D E F G H I J K L M N O（图 4）A B C D（图 5）7 图结构：图是由顶点集V 和边集 E 组成，一般把图G 记为 G（V，E）。（1）在图 6 中，边有方向性，我们称之为有向图，有向图的边称之为弧。在图 7 中，边没有方向性，即边 和 指的是同一条边，我们称之为无向图。（2）在有向图中，从某顶点出发的弧的数目称为该顶点的出度，到达某顶点的有向
7、弧的数目称为该顶点的入度。（如图 6 的有向图中，顶点V1 的出度为2，入度为 1。）在无向图中，与顶点依附的边的条数称为该顶点的度。（如图 7 中，顶点V1 的度为 2。）（3）完全图定义：如果用n 表示图中顶点数目，用e 表示边或者弧的数目，则有：对于有向图，具有 n(n-1)条弧的有向图称为有向完全图(任意两个顶点之间都有2条有向弧)对于无向图，具有n(n-1)/2 条边的无向图称为完全图（任意两个顶点之间都有一条边。）（4）连通图定义：在无向图中，若图中任意两个顶点之间都存在路径，则称该无向图为连通图。在有向图中，对于任意两个顶点Vi 和 Vj（ViVj），若从 Vi 到 Vj 和从
8、Vj 到 Vi 之间均存在路径，则称该有向图为强连通图。（5）带权图定义：有时图的边往往与具有一定意义的数值有关，我们把这种与图的边相关的数称为边上的权。权可以表示从一个顶点到另一个顶点的距离、费用或代价等，由这种带权的边构成的图称为带权图。（6）图的遍历方式有两种：深度优先搜索和广度优先搜索。顶点V1 V2 V3 V4（图 6 有向图）弧V1 V2 V43 V5（图 7无 向 图）V3 边8 二分法查找：具体方法见课本P147P148 面。二分法查找（又称折半查找）算法如下：首先需要设三个指示器top、bot、mid，分别指向查找范围的顶部、底部和中间位置。假定有11 个元素的有序数列(2，
9、5，7，10，14，15，18，23，35，41，52)，待查找数为41，则一开始 top1、bot11、mid（topbot）div 26，这是一定要bot 大于 top，接着进行判断：（1）如果 x=amid，则表示找到；（2）如果 xamid，则说明待查找数在mid1 到 bot 之间，改变topmid1；重复以上过程直到已经找到或无法查找为止。例如查找41，则只需查找3 次即可找到。假设用二分法在有1000 个数据的有序数组中查找某个数据，则最多只需查找10 次即可。（因为 2 101000）9 排序：（1）在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是选择排序。（2）
10、在待排序的数据表已经为有序时，快速排序算法花费时间反而多。10 设循环队列中数组的下标范围是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 开始,出栈后不在进栈):进栈,出栈,进栈,进栈,进栈,进栈 ,出栈,进栈,问出栈的元素序
11、列是:_,栈顶指针的值为_ 栈顶元素为:_（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=()BA)01011110 B)00001111 C)01011100 D)110
12、01110 E)11001010（7）对给定的整数序列(54,73,21,35,67,78,63,24,89)进行从小到大的排序时,采用快速排序的第一趟扫描的结果是A)(24,21,35,54,67,78,63,73,89)B)(24,35,21,54,67,78,63,73,89)C)(24,21,35,54,67,63,73,78,89)D)(21,24,35,54,63,67,73,78,89)（8）一棵 n 个结点的完全二叉树,则二叉树的高度h 为A)n/2 C)(log2n)/2 C)log2n+1 D)2n-1（9）设有一个含有13 个元素的Hash表(012),Hash函数是:H
13、(key)=key%13,其中%是求余数运算。用二次探查法解决冲突,则对于序列(、31、20、33、18、53、27),则下列说法正确的是()。A)27 在 1 号格子中B)33 在 6 号格子中C)31 在 5 号格子中D)20 在 7 号格子中E)18 在 4 号格子中（10）13 历届信息学奥赛试题中的数据结构试题：选择题中的数据结构试题：（1）（第 10 届）某车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时该车站站台为空，从这一时刻开始出入记录为：“进出进进出进进进出出进出”。假设车辆入站的顺序为1,2,3，则车辆出站的顺序为（E）A、1，2，3，4，5 B、1，2，4
14、，5，7 C、1，3，5，4，6 D、1，3，5，6，7 E、1，3，6，5，7（2）（第 10 届）二叉树 T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，其后序遍历序列为(B)A、4 2 5 7 6 3 1 B、4 2 7 5 6 3 1 C、4 2 7 5 3 6 1 D、4 7 2 3 5 6 1 E、4 5 2 6 3 7 1（3）（第 10 届）满二叉树的叶节点为N，则它的节点总数为（C）A、N B、2N C、2N-1 D、2N+1 E、2N-1（4）（第 10 届）在下图，从端点（E）出发存在一条路径可以遍历图中的每条边一次，而且仅遍
15、历一次（5）（第 9 届）一个高度为h 的二叉树最小元素数目是(B)。A)2h+l B)h C)2h-1 D)2h E)2h-l（6）（第 9 届）已知队列(13，2，11，34，41，77，5，7，18，26，15)，第一个进入队列的元素是 13，则第五个出队列的元素是(B)。A)5 B)41 C)77 D)13 E)18（7）（第 8 届）一个向量第一个元素的存储地址是100,每个元素的长度是2,则第 5 个元素的地址是(B)A)110 B)108 C)100 D)109（8）（第 8 届）在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是(D)。A)希尔排序B)起泡排序C)插
16、入排序D)选择排序A E D B C（9）（第 7 届）在顺序表(2，5，7，10，14，15，18，23，35，41，52)中，用二分法查找12，所需的关键码比较的次数为(C)，用二分法查找41，所需的关键码比较此数为（B）。A)2 B)3 C)4 D)5（10）（第 7 届）若已知一个栈的入栈顺序是1，2，3，n，其输出序列为P1，P2，P3，Pn，若 P1是 n，则 Pi 是(C)A)i B)n-1 C)n-i+1 D)不确定（11）（第 6 届）设循环队列中数组的下标范围是1n，其头尾指针分别为f 和 r，则其元素个数为（D）A.r-f B.r-f+1 C.(r-f)MODn+1 D.
17、(r-f+n)MODn（12）（第 6 届）在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（D）A.堆排序B.C.冒泡排序D.快速排序（13）（第 6 届）某数列有1000 个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary search），在最坏的情况下，需检视（B）个单元A.1000 B.10 C.100 D.500（14）（第 6 届）已知数组A 中，每个元素AI,J 在存贮时要占3 个字节，设I 从 1变化到 8，J从 1 变化到 10，分配内存时是从地址SA 开始连续按行存贮分配的。试问：A5,8 的起始地址为（A）A.SA+141 B.SA
18、+180 C.SA+222 D.SA+225（15）（第 6 届）线性表若采用链表存贮结构,要求内存中可用存贮单元地址（D）A.必须连续B.部分地址必须连续C.一定不连续D.连续不连续均可（16）（第 6 届）下列叙述中,正确的是（D）A.线性表的线性存贮结构优于链表存贮结构B.队列的操作方式是先进后出C.栈的操作方式是先进先出D.二维数组是指它的每个数据元素为一个线性表的线性表问题求解中的数据结构知识试题：（17）（第 9 届）无向图 G有 16 条边，有 3个 4 度顶点、4 个 3 度顶点，其余顶点的度均小于3，则 G至少有个顶点。（18）（第 8 届）如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5 共五个车厢。其中每个车厢可以向左行走,也可以进入栈S 让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。出口 1 2 3 4 5 S（19）（第 6 届）1.已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。