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

noip2012简单的数据结构类型应用


Lesson1 NOIP2012国庆初赛培训一
——简单的数据结构类型应用 二维数组,队列,栈,树,图

今天主要内容
? ? ? ? ? ? 简单的数据结构类型应用 二维数组和线性表 队列 栈 树 图

? 哈希表(Hash Table)
马鞍山市成功学校 谷老师讲座

一:线性表表示(一)
? N个数据元素的有限序列(一般用数组表示) ? 存储结构:顺序存储结构、链式存储结构
1
12

2
13

3
15

4
22

5
34

6
38

7
43

8

20
马鞍山市成功学校 谷老师讲座

线性表表示(二)
? 链式存储(不要求掌握,有兴趣可以阅读指针一章)
head

12

13

15

22 ^

L

20 ^

马鞍山市成功学校

谷老师讲座

二维数组
? 二维数组的一个形象比喻—— 多个纵队形成的方块 m * n
二维数组在内存的存 储方式是线性的。 1:按照行存储:即先 存储第一行然后在存 储第二行,那么aij的值应 该是A11+(i-1)*n+j-1

a11 a21 a31 ……

a12 a22 a32 ……

a13 a23 a33 ……

a14 a24 a34 ……

…… …… …… ……

a1n a2n a3n ……

2: 1:按照列存储:即先 存储第一列然后在存 储第二列,那么aij的值应 该是A11+(j-1)*m+i-1 (很好记啊,I,j调换位置 *的值n->m)

am1

am2

am3

am4

……

amn

马鞍山市成功学校 谷老师讲座 思考:如果数组的定义为var num:array[2..n,2..m],要 求AIJ的位置,结果应该是是什么呢!

另外数组地址计算问题
? 题目描述:已知N*(N+1) / 2个数据,按行的顺序存入数 组b[1],b[2],…中。其中第一个下标表示行,第二个下标 表示列。若aij (i>=j ,j=1,2,…,,n)存于b[k]中,问: k,i,j之间的关系如何表示?给定k值,写出能决定相应i,j的 算法。 a1
1

a2
1

a2
2

a3
1

a3
2

a3
3

… …

… …

… …

… …

… … … …

… …

① K=i*(i-1)/2+j ② Read(k); For i:=1 to k do for j:=1 to i do if k=(trunc(I*(I-1)/2)+j) then writeln(k,’对应的i,j为:‘,i,’,’,j)

an
1

an
2

an
3

an
4

an
n
马鞍山市成功学校 谷老师讲座

二:栈的定义
1.栈的定义 栈(stack)是一种只允许在一端进行插入和删除的线性表,它是一种操作 受限的线性表。在表中只允许进行插入和删除的一端称为栈顶(top),另 一端称为栈底(bottom)。栈的插入操作通常称为入栈或进栈(push),而栈的 删除操作则称为出栈或退栈(pop)。当栈中无数据元素时,称为空栈。 根据栈的定义可知,栈顶元素总是最后入栈的,因而是最先出栈;栈底元 素总是最先入栈的,因而也是最后出栈。这种表是按照后进先出(LIFO, last in first out )的原则组织数据的,因此,栈也被称为“后进先出”的线 性表。 图3-3是一个栈的示意图,通常用指针top指示栈顶的位置,用指针bottom 指向栈底。栈顶指针top动态反映栈的当前位置。 入栈 栈顶 top 出栈
an-1
.. .

1 栈底 a bottom马鞍山市成功学校 谷老师讲座 图3-3栈的示意图
0

a


? ? ? ? ? 特殊的线性表 操作特点:后进先出(Last In First Out) 栈顶——表尾 栈底——表头 栈顶指针: 空栈(top=bottom)
D
C B 栈底指针
马鞍山市成功学校 谷老师讲座

指想下一个元素 的存放位置

A

栈 (考题分析)
(1998) 栈S初始状态为空,现有5个元素组成的序 列{1,2,3,4,5},对该序列在栈S上一次进 行如下操作(从序列中的1开始,出栈后不再进 栈):进栈、进栈、进栈、出栈、进栈、出栈、进 栈。问出栈的元素序列是______
(A) {5,4,3,2,1} (B) {2,1} (C) {2,3} (D) {3,4}

马鞍山市成功学校

谷老师讲座

三:队列
? 特点:先进先出 ? 允许插入的一端称为队尾(rear),允许删除 的一端称为队头(front)。
出队列 入队列

a1

a2

a3

a4

…… an

FRONT

REAR

马鞍山市成功学校

谷老师讲座

循环队列
FRONT
REAR 2 1 8 7 3 4 5 6

现在栈中存放的元素个数:(R-F+N) mod N
马鞍山市成功学校 谷老师讲座

四:树的概念
? 树(Tree)是n(n>=0)个结点的有限集。在一棵非空树中: (1) 有且仅有一个特定的称为根的结点; (2) 当n>1时其余结点可分为m(m>0)个互不相交的有限集T1,T2...Tm, 其中,每一个集合 本身 又是一棵树, 并且称为根的子树(subtree)例如,在图6.1中,(a)是只 有一个根 结点的树;(b)是有 13个结点的树,其中A是根,其余结点分成三个互不相交 的子树

马鞍山市成功学校

谷老师讲座

一、树的基本术语
1.树的度——也即是宽度,简单地说,就是结点 的分支数。以组成该树各结点中最大的度 作为该树的度,如上图的树,其度为3; 2.树的深度——组成该树各结点的最 大层次,如上图,其深度为4; 3.森林——指若干棵互不相交的树的 集合,如上图,去掉根结点A,其原来的二 棵子树T1、T2、T3的集合{T1,T2,T3}就为 森林; 4.有序树——指树中同层结点从左到 右有次序排列,它们之间的次序不能互换, 这样的树称为有序树,否则称为无序树。 结点的度:结点拥有的子树数。 叶子(终端结点):度为零的结点。 非终端结点(分支结点):度不为零的结点。 树的度:树内各结点的度的最大值。
马鞍山市成功学校 谷老师讲座


? 根、叶子、子树 ? 结点的度:结点拥有的子树数 ? 二叉树(每个节点最多只有两个子节点的树)
层次 A B E F
马鞍山市成功学校

1
D G
谷老师讲座

C

2
3

二叉树
? 特点:每个结点至多只有二棵子树,并且二叉树 的子树有左右之分。 ? 第i层至多有 个结点(i>=1) ? 深度为K的二叉树最多有 个结点(K>=1)

A B D E F

A

C
G D

B E
谷老师讲座

C
F

满二叉树

马鞍山市成功学校

完全二叉树

二叉树的遍历
? 先(根)序遍历 ? 中(根)序遍历 ? 后(根)序遍历 先(根)序遍历 ABDFGCEH 中(根)序遍历 BFDGACHE 后(根)序遍历 FGDBHECA
? ? ? 若左子树非空先访问左子树 访问根节点 若左子树非空先访问左子树
马鞍山市成功学校 谷老师讲座

A B D C E

F

G

H

中序遍历的程序
Procedure (I,j:integer){I表示层数,j表示第几个节点} Begin If i<n then{如果非根节点} begin procedure(i+1,2*i-1);{遍历左子树} write(a[I,j]; {遍历子树节点} procedure (i+1,2*i); {遍历右子树} end; end.;
马鞍山市成功学校 谷老师讲座

例题分析
? 给出一棵二叉树的中序遍历:DBGEACHFI 与后序遍历:DGEBHIFCA ,画出此二叉树。
A
B D G E H C F I
思考过程 先在后序中找到最后面的节点A,那我们 知道这棵树的根目录是A,A将中序的遍 历分成两个部分前面部分“DBGE”是左子 树的中序遍历,后面部分“CHFI”是右子 树的中序遍列,在后序遍历中找到这两个 字符串中最先出现的字符,那就是左子树 和右子树的根节点,再在中序遍历中划分 …..
谷老师讲座

马鞍山市成功学校

五:图

无向图

有向图
A
C A C

D

B
E
马鞍山市成功学校

D

B
E

谷老师讲座

图的存储结构——邻接矩阵
? 邻接矩阵(二维数组)
1 0 1 0 1 2 1 0 1 0 3 1 0 0 1 4 0 0 0 0 5 0 1 1 0
1 4

1 2 3 4

2

3
5

5 0 0 0 0 0
马鞍山市成功学校 谷老师讲座

"遍历"是指从图的某个点出发,沿着与之相连的边访问图中的每个 一次且仅一次。基本方法有两种:深度优先遍历和广度优先遍历。 深度优先和广度优先遍历,与前面所说的树的深度与广度优先遍历 是类似的:比下图中,如果从点V1出发,那么: 深度优先遍历各点的顺序为:v1,v2,v4,v7,v5,v3,v6, v8。 广度优先遍历各点的顺序为:v1,v2,v3,v4,v5,v6,v7, v8。
马鞍山市成功学校 谷老师讲座

五:哈希表(Hash Table)
1:设有一个含有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号格子中

马鞍山市成功学校

谷老师讲座

哈希表
有一个含有13个元素的Hash表(O~12),Hash 函数是:H(key)=key % 13,其中%是求余数 运算。用线性探查法解决冲突,则对于序列(2、 8、31、20、19、18、53、27),18应放在第 几号格中( B ) 。 A) 5 B) 9 C) 4 D) 0

马鞍山市成功学校

谷老师讲座

学生练习题一(2004)
利用今天学习的知识解决下列问题
1:二叉树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 2:满二叉树的叶结点个数为N,则它的结点总数为( )。 A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1 ? 某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。已知某时刻 该车站状态为空,从这一时刻开始的出入记录为:“进,出,进,进,出,进, 进,进,出,出,进,出”。假设车辆入站的顺序为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

?

学生练习题二(2004)
3:某大学计算机专业的必修课及其先修课程如下表所示:

请你判断下列课程安排方案哪个是不合理的( )。
A. C0, C6, C7, C1, C2, C3, C4, C5 C. C0, C1, C6, C7, C2, C3, C4, C5 E. C0, C1, C2, C3, C6, C7, C5, C4 B. C0, C1, C2, C3, C4, C6, C7, C5 D. C0, C1, C6, C7, C5, C2, C3, C4

马鞍山市成功学校

谷老师讲座

二.问题求解 (每题5分,共10分)2004
? 一个家具公司生产桌子和椅子。现在有113个单位的木 材。每张桌子要使用20个单位的木材,售价是30元; 每张椅子要使用16个单位的木材,售价是20元。使用 已有的木材生产桌椅(不一定要把木材用光),最多 可以卖 元钱。 75名儿童到游乐场去玩。他们可以骑旋转木马,坐滑 行铁道,乘宇宙飞船。已知其中20人这三种东西都玩 过,55人至少玩过其中的两种。若每样乘坐一次的费 用是5元,游乐场总共收入700,可知有 名儿童没 有玩过其中任何一种。
马鞍山市成功学校 谷老师讲座

?

问题求解 (每题5分,共10分)2004
? 编号为1到13的纸牌顺时针排成一圈,有人从编号为1 的牌从数字1开始顺时针数下去,1、2、3、…、20、 21、…,一圈又一圈。问:当数到数字N时,所在纸牌 的编号为多少?

马鞍山市成功学校

谷老师讲座


相关文章:
noip2012简单的数据结构类型应用_图文.ppt
noip2012简单的数据结构类型应用 - noip2012初赛赛前集训第一讲(
noip2012数据结构培训_图文.ppt
noip2012数据结构培训 - NOIP2012国庆初赛培训 简单的数据结构类型应用 二维数组,队列,栈,树,图 今天主要内容 ? ? ? ? ? ? 简单的数据结构类型应用 二维...
NOIP中常用的数据结构_图文.ppt
此时根据x和y的大小分类讨论 不妨设x<y(反之对称) 堆 2、删除最小值 将x...noip2012简单的数据结构... 27页 1下载券 NOIP 初赛复习(数据结构... ...
Pascal简单的数据结构类型应用_图文.ppt
Pascal简单的数据结构类型应用 - 第七天 简单的数据结构类型应用 二维
数据结构(2012-noip)_图文.ppt
数据结构(2012-noip) - 数据结构专题 赖国 福建师大附中 提纲 ? 简单数据结构的变种与高级应用 栈 队列 ? 高级数据结构入门 并查集 堆 散列...
noip2012_解析_图文.ppt
noip2012_解析_计算机软件及应用_IT/计算机_专业资料...虽然题目 最简单,但并不意味这并不需要思考。也许...(mod)、及 高级数据结构(classroom)等 也是必不可...
NOIP中常用的数据结构_图文.ppt
此时根据x和y的大小分类讨论 不妨设x<y(反之对称) 堆 2、删除最小值 将x...noip2012简单的数据结构... 27页 1下载券 NOIP 初赛复习(数据结构... ...
2012年数据结构期末考试题及答案.pdf
2012数据结构期末考试题及答案 一、选择题 1....插入、删除操作更简单 B.可以进行随机访问 C.可以...的中缀形式为 A+B *CD/E,后缀形式为 ABC *...
noip2012 解析_图文.ppt
noip2012 day 1 01 vigenere p1431 02 03 game ...徐王子浩《贪心策略在排序中的应用》 Drive p...(mod)、及 高级数据结构(classroom)等 也是必不可...
数据结构实验指导书2012(精).doc
数据结构实验指导书2012(精) - 数据结构实验指导书 信息科学与技术学院 2012 年 9 月 实验一线性表的基本操作 一、实验目的 1、熟悉 C 或 VC++语言上机环境...
NOIP2012提高组 C++.pdf
(!used[j]) ① ; for (i = m; i >= 1; i--) CCF NOIP2012 初赛 提高组 C++ 11 } } } } (新壳栈)小 Z 设计了一种新的数据结构“新壳栈”...
2012数据结构课程设计-帅.doc
2012数据结构课程设计-帅_工学_高等教育_教育专区。...乘法和除法模块 5 七、总结通过本次应用 C 语言...//Polyn 为结点指针类型 void Insert(Polyn p,Polyn...
NOIP2012提高组 C.pdf
NOIP2012提高组 C_电子/电路_工程科技_专业资料。...那它一定是 NP 类问题 如果一个问题不存在多项式...(新壳栈)小 Z 设计了一种新的数据结构“新壳栈...
NOIP2012普及组初赛及答案_C_.pdf
NOIP2012普及组初赛及答案_C__从业资格考试_资格...直到最后的子问题可以简单地直接求解。而原问题的解...人们研究生物体的结构、功能和工作原理,并将 这些...
NOIP2012 提高组初赛答案.doc
NOIP2012 提高组初赛答案_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载 | 举报文档 NOIP2012 提高组初赛答案_学科竞赛_高中教育_教育专区。NOIP2012 ...
NOIP2012 初赛提高组C++试题及答案.pdf
NOIP2012 初赛提高组C++试题及答案_IT认证_资格考试...那它一定是 NP 类问题 如果一个问题不存在多项式...(新壳栈)小 Z 设计了一种新的数据结构“新壳栈...
NOIP2012初赛提高组Pascal试题.pdf
NOIP2012初赛提高组Pascal试题_学科竞赛_高中教育_...那它一定是 NP 类问题 如果一个问题不存在多项式...2. (新壳栈)小 Z 设计了一种新的数据结构“新...
数据结构课程设计题目(2012).doc
2012数据结构课程设计题目一、文章编辑(限 1 人...输出形式: (1)分行输出用户输入的各行字符; (2)...十一、哈希表应用【问题描述】 利用哈希表进行存储。...
NOIP2012提高组day1.pdf
全国信息学奥林匹克联赛(NOIP2012)复赛 提高组 day...题目类型 Vigenère 密码 vigenere vigenere vigenere....【数据说明】 对于 100%的数据,输入的密钥的长度不...
noip20123题解.doc
noip20123题解_计算机软件及应用_IT/计算机_专业资料。F(i, j)
更多相关标签: