当前位置:首页 >> 学科竞赛 >>

高二信息奥赛《数据结构基础知识》学案


数据结构基础知识
初赛考试时间:10 月 13 日下午 2:30-4:30 初赛前培训时间:本周五(9 月 27 日) 、第六周(10 月 11 日)晚 6:00-8:00(机房) 10 月 13 日上午 8:00-12:00 在机房专题答疑,下午在本校考试。
1. 根据数据元素间关系的基本特征,有四种基本数据结构: 集合:数据元素间除“同属于一个集合”外,无

其它关系。 线性结构:一个对一个,如线性表、栈、队列。 树形结构:一个对多个,如树。 图状结构:多个对多个,如图。 2. 数据的存储结构一般有两种, 用一组物理地址相邻的存储单元来存储数据元素的存储方式称之 为顺序存储结构;借助于动态数据结构来存储数据元素的存储方式称之为链式存储结构。 3. 数组的存储采用的是顺序存储结构,如一维数组和多维数组。按顺序往下存储数据。如图 1 4. 栈结构的特点是“先进后出” ,如图 2 举例说明。 5. 队列结构的特点是“先进先出” ,比如排队买票等,如图 3 举例说明。

Var s:array[1..4,1..10] of integer; 则说明数组 s 是二维的整型数组, 每个元素占 2 字节,假设存储第 一个元素的起始地址为 100, 则它 的存储结构如下: 地址 存储方式 100 102 118 120 178 S[1,1] S[1,2] ?? S[1,10] S[2,1] ?? S[4,10] (图 1)

栈结构就像一个底部封闭 队列结构就像底部不封闭的线 的 线性表,比如进栈元素的 性 顺 表 ,比 如 进 队 列 元 素 的 顺 序 是 序分别为 1、2、3,则 出 栈 元 1、2、3, 则 出 队 列 元 素 的 顺 序 素 的 顺 序 分 别3 是 、2、1,满 也是 1、2、3, 满 足 “ 先 进 先 出 ” 足“先进后出”原则。 的原则。 进栈 出栈 进队列

(图 2)

出队列 (图 3)

6. 树结构:树是 n(n>=0)个结点的有限集。 (1) 任意一棵树,只有一个特定的称为根的结点(如图 4 中的 A) ;当 n>1 时,其余结点 可分为 m(m>0)个互不相交的有限集,其中每一个集合本身又是一棵树,并且称为根 的子树。 (2) 结点拥有的子树数称为结点的度。 (如图 4 中的 B 所拥有的度为 2) (3) 度为 0 的结点称为叶子或终端节点。 (如图 4 中的 H、I、J、K 等都是叶子结点) (4) 度不为 0 的结点称为非终端结点或分支结点。 (5) 结点的层次从根开始定义起,根为第一层,根的分支为第二层,依此类推(如图 4 的 树结构最大层次为 4 层) 。树中结点的最大层次称为树的深度或高度。 (如图 4 的树结 构的深度或高度为 4)

1

(6) 二叉树是一种特殊的树形结构,它的特点是每个结点至多只有两棵子树(即二叉树中 不存在度大于 2 的结点) ,并且二叉树的子树有左右之分,其次序不能任意颠倒,所 以二叉树是由根节点、左子树、右子树三个基本单元构成。 (7) 一棵深度为 k 的二叉树至多只有 2 k-1 个结点,此二叉树称为满二叉树(如图 4 为深 度为 4 的满二叉树) ,最少也有 K 个结点(如图 5 为深度为 4 的最小二叉树) 。可以验 证具有 n 个叶子结点的满二叉树共有 2n-1 个结点(如图 5 的满二叉树) 。 i-1 (8) 在二叉树的第 i 层上至多有 2 个结点。 (9) 树的遍历:按照根节点在访问中的先后位置,我们有三种树的遍历方式。 (当然每次 访问都是左子树在右子树的前面。 ) 先序遍历(先访问根节点,再访问左子树,最后访问右子树) : 如图 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。 由上面三种遍历树结构的方式可知,先序遍历最先访问的是根节点;后序遍历最后访 问的是根节点;由中序遍历的根节点的位置可知,在根节点的左边全部都是根节点的 左子树,在根节点的右边全部都是根节点的右子树。必须掌握,由任意两种树的遍历 结果,能够画出该二叉树,然后根据该二叉树,写出另一种遍历结果。 (10) 哈夫曼树称为最优树,是一类带权路径长度最短的树。
A B D H I J E K F L M N C G
C B A

O

D (图 5)

(图 4)

7. 图结构:图是由顶点集 V 和边集 E 组成,一般把图 G 记为 G=(V,E) 。 (1) 在图 6 中,边有方向性,我们称之为有向图,有向图的边称之为弧。 在图 7 中,边没有方向性,即边<v1,v2>和<v2,v1>指的是同一条边,我们称之为无向图。 (2) 在有向图中,从某顶点出发的弧的数目称为该顶点的出度,到达某顶点的有向弧的数 目称为该顶点的入度。 (如图 6 的有向图中,顶点 V1 的出度为 2,入度为 1。 ) 在无向图中, 与顶点依附的边的条数称为该顶点的度。 (如图 7 中, 顶点 V1 的度为 2。 ) (3) 完全图定义:如果用 n 表示图中顶点数目,用 e 表示边或者弧的数目,则有: 对于有向图, 具有 n(n-1)条弧的有向图称为有向完全图(任意两个顶点之间都有 2 条有向弧) 对于无向图,具有 n(n-1)/2 条边的无向图称为完全图(任意两个顶点之间都有一条边。 ) (4) 连通图定义:在无向图中,若图中任意两个顶点之间都存在路径,则称该无向图为连 通图。在有向图中,对于任意两个顶点 Vi 和 Vj(Vi≠Vj) ,若从 Vi 到 Vj 和从 Vj 到 Vi 之间均存在路径,则称该有向图为强连通图。

2

(5) 带权图定义:有时图的边往往与具有一定意义的数值有关,我们把这种与图的边相关 的数称为边上的权。权可以表示从一个顶点到另一个顶点的距离、费用或代价等,由 这种带权的边构成的图称为带权图。 (6) 图的遍历方式有两种:深度优先搜索和广度优先搜索。
顶点 V1 弧 V3 V4 V2

V1 V3

V2 边

(图 6 有向图)

V5 V4 3 (图 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=(top+bot)div 2=6,这是一定要 bot 大于 top,接着 进行判断: (1) 如果 x=a[mid],则表示找到; (2) 如果 x<a[mid],则说明待查找数在 top 到 mid-1 之间,改变 bot=mid-1; (3) 如果 x>a[mid],则说明待查找数在 mid+1 到 bot 之间,改变 top=mid+1; 重复以上过程直到已经找到或无法查找为止。 例如查找 41,则只需查找 3 次即可找到。 假设用二分法在有 1000 个数据的有序数组中查找某个数据,则最多只需查找 10 次即可。 (因为 2 10>1000) 9. 关练习习题: (1) A=11001010B,B=00001111B,C=01011100B,则 A∨B∧C=( )B A)01011110 B)00001111 C)01011100 D)11001110 E)11001010 (2) 对给定的整数序列 (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) (3) 一棵 n 个结点的完全二叉树,则二叉树的高度 h 为 A)n/2 C)(log2n)/2 C) [log2n]+1 D)2n-1 (4) 设有一个含有 13 个元素的 Hash 表(0~12),Hash 函数是:H(key)=key % 13,其中% 是求 余数运算。用二次探查法解决冲突,则对于序列(8、31、20、33、18、53、27),则下 列说法正确的是( ) 。A)27 在 1 号格子中 B)33 在 6 号格子中 C)31 在 5 号格子中 D)20 在 7 号格子中 E)18 在 4 号格子中 (5) (第 10 届)某车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。已知某 时该车站站台为空,从这一时刻开始出入记录为: “进出进进出进进进出出进出” 。假 设车辆入站的顺序为 1,2,3??,则车辆出站的顺序为( ) A、1,2,3,4,5 B、1,2,4,5,7 C、1,3,5,4,6 D、1,3,5,6,7 E、1,3,6,5,7

3

(6) (第 10 届)二叉树 T,已知其前序遍历序列为 1 2 4 3 5 7 6,中序遍历序列为 4 2 1 5 7 3 6,其后序遍历序列为( ) 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 (7) (第 10 届)满二叉树的叶节点为 N,则它的节点总数为( ) A、N B、2N C、2N-1 D、2N+1 E、2^N-1 (8) (第 10 届)在下图,从端点( )出发存在一条路径可以遍历图中的每条边一次, 而且仅遍历一次 A B C

D E (9) (第 9 届)一个高度为 h 的二叉树最小元素数目是( )。 A)2h+l B)h C)2h-1 D)2h E)2h-l (10) (第 8 届)一个向量第一个元素的存储地址是 100,每个元素的长度是 2,则第 5 个元素 的地址是( ) A) 110 B) 108 C) 100 D) 109 (11) (第 8 届)在所有排序方法中 ,关键字比较的次数与记录的初始排列次序无关的是 ( ) 。 A) 希尔排序 B) 起泡排序 C) 插入排序 D) 选择排序 (12) (第 7 届)在顺序表(2,5,7,10,14,15,18,23,35,41,52)中,用二分法查找 12, 所需的关键码比较的次数为(C ), 用二分法查找 41, 所需的关键码比较此数为 (B ) 。 A)2 B)3 C)4 D)5 (13) (第 7 届) 若已知一个栈的入栈顺序是 1, 2, 3, ?, n, 其输出序列为 P1, P2, P3, ?, Pn,若 P1 是 n,则 Pi 是( ) A)i B)n-1 C)n-i+1 D)不确定 (14) (第 6 届) 在待排序的数据表已经为有序时, 下列排序算法中花费时间反而多的是 ( ) A.堆排序 B. C.冒泡排序 D.快速排序 (15) (第 6 届)某数列有 1000 个各不相同的单元,由低至高按序排列;现要对该数列进 行二分法检索(binary search) ,在最坏的情况下,需检视( )个单元 A.1000 B.10 C.100 D.500 (16) (第 6 届)线性表若采用链表存贮结构,要求内存中可用存贮单元地址( ) A.必须连续 B.部分地址必须连续 C.一定不连续 D.连续不连续均可 (17) (第 6 届)下列叙述中,正确的是( ) A .线性表的线性存贮结构优于链表存贮结构 B.队列的操作方式是先进后出 C.栈的操作方式是先进先出 D.二维数组是指它的每个数据元素为一个线性表的线性表 问题求解中的数据结构知识试题: (18) (第 9 届)无向图 G 有 16 条边,有 3 个 4 度顶点、4 个 3 度顶点,其余顶点的度均小 于 3,则 G 至少有 个顶点。

4


相关文章:
信息学奥赛基础知识习题(答案版)
信息奥赛基础知识习题(答案版)_六年级其它课程_...(C)输入设备 30.数据和程序是以(B)形式存储在...不同类型的存储器组成了多层次结构的存储器体系,按...
信息学奥赛计算机基础知识复习材料
信息奥赛计算机基础知识复习材料_初中教育_教育专区...四、计算机的主要应用: 1、数值计算: 2、数据和...图 2-1 一、 冯·诺依曼式的计算机体系结构 1、...
初中信息技术奥赛基础知识
初中信息技术奥赛基础知识计算机基础知识第一节计算机的基本常识 1.1 计算机的...结构上以存储器为中心,使用高级语言,应用范围扩大到数据处理 和工业控制; ③第...
信息学奥赛数据结构辅导资料
信息奥赛数据结构辅导资料信息奥赛数据结构辅导资料隐藏>> 目录1、数据结构基础知识………2 2、动态规划………17 3、分支限界………19 4、分治策略………21...
信息学奥赛基础知识习题(答案版)
信息奥赛基础知识习题(答案版 信息奥赛基础知识...结构 (D)所用的程序设计语言 60.RAM 中的信息是...17. 18. 如果将一本 273 万字的《现代汉语词典》...
(信息学奥赛辅导)排列与组合基础知识
(信息奥赛辅导)排列与组合基础知识_学科竞赛_高中...(1<=N<=18)的 N 辆列车顺序进入一个栈式结构...2014年证券考试《投资基金》考前押题卷 证券从业资格...
数据结构基础知识
数据结构基础知识_计算机软件及应用_IT/计算机_专业资料。适用于信息奥赛基础知识 数据结构知识点归纳 数据结构的定义:数据在计算机中的组织。包括逻辑结构( 数据之间...
数据结构基础知识
数据结构基础知识_计算机软件及应用_IT/计算机_专业资料。文章深入浅出介绍了数据结构基础知识 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在 一种...
信息学奥赛辅导资料
信息奥赛辅导资料_IT/计算机_专业资料。信息奥赛辅导资料信息奥赛 辅导资料信息组 目 录 1、数据结构基础知识………2 2、动态规划………17 3、分支限界…...
信息学奥赛辅导资料
信息奥赛 辅导资料信息组 目 录 1、数据结构基础知识………2 2、动态规划…...要想更好地运用计算机来解决实际问题, 仅仅学 习计算机语言而缺乏数据结构知识是...
更多相关标签:
信息学奥赛基础知识 | 小学信息奥赛基础知识 | 键盘基础知识学案 | 高二语文基础知识训练 | 高二个数学基础知识 | 高二语文基础知识 | 高二物理电场复习学案 | 高二期末导数学案 |