2023学年完整公开课版数据结构

constsize=100;varna,nb,i,j,k:integer;a,b:array[1..size]ofinteger;begin

readln(na);fori:=1tonadoread(a[i]);readln(nb);fori:=1tonbdoread(b[i]);i:=1;j:=1;while(i<=na)and(j<=nb)dobeginifa[i]<=b[j]thenbeginwrite(a[i],'');inc(i);endelsebeginwrite(b[j],'');inc(j);end;end;ifi<=nathenfork:=itonadowrite(a[k],'');ifj<=nbthenfork:=jtonbdowrite(b[k],'');end.输入5135794261014输出：__________2010读程序第二题数据结构初步（一）2012赛前知识点梳理信息学奥赛学什么?程序(Programming)数据结构(DataStructure)算法(Algorithm)Programming=DataStructure+Algorithm什么是数据结构数据(data)

是对客观事物的符号的表示。例如数值、图像、声音都属于数据的范畴。数据元素(dataelement)

是数据的基本单位数据结构（datastructure）是相互之间存在一种或多种特定关系的数据元素的集合。数据结构（DataStructure）一般包括以下三方面内容：①数据的逻辑结构（LogicalStructure）：数据元素之间的相互联系②数据的存储结构StorageStructure）：数据元素及其关系在计算机存储器内的表示；数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。③数据的运算，即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。例子：数组数据：a[1],a[2],…,a[n]关系：前驱/后继操作：随机存取，插入，删除…表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（ImmediatePredecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（ImmediateSuccessor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"马二"所在结点的直接前趋结点和直接后继结点分别是"丁一"和"张三"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。所处理的数据一般都存在着某种内在的、特殊的关系。这种数据本身以及它们之间的相互之间的逻辑关系叫数据的逻辑结构。逻辑结构数据的逻辑结构分类（1）线性结构线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表是一个典型的线性结构。数组、栈、串、队列等都是线性结构。（2）非线性结构非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。树和图等数据结构都是非线性结构。数据类型：初等类型如：整型、实型、布尔型、字符型、指针型

组合类型指构造类型如集合、数组、记录也叫物理学结构，是数据的逻辑结构在计算机中的存储方式。方法主要有顺序与链式。顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系，物理存储结构中相邻。

链式存储结构:在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系，物理存储结构中不一定相邻。

（3）索引存储方法（该方法通常在储存结点信息的同时，还建立附加的索引表4）散列存储方法根据结点的关键字直接计算出该结点的存储地址

存储结构线性表的顺序存储结构,也称为顺序表。它是线性表的一种最简单的存储结构。其存储方式为：在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度和线性表中一个元素所需要的存储字节数的乘积，然后让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。数据元素之间前趋与后继关系体现在存放位置的前后关系上。数据元素的位置确定1000a0a1a2anFori:=1to10doread(a[i])一维数组第一个元素的存储起始地址是100，每个元素的长度是2，则第5个元素的起始地址是（）。A．110B.108C.100D.109Ba1a2a4a3a5总结规律：得出前面的元素个数很重要1,11,21,31,42,12,22,32,410,110,210,310,4……3,13,23,33,4二维数组a[i,j]一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。二维数组的顺序存储结构有两种：2×3数组存储（a）逻辑状态（b）以行为主序（c）以列为主序已知数组中A中，每个元素A（i，j）在存贮时要占3个字节，设i从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A（5，8）的起始地址为（）(NOIP6)

A.SA+141

B.SA+180

C.SA+222

D.SA+225A1,11,21,31,102,12,22,32,108,18,28,38,10……3,13,23,33,10…………vara:array[1..10,1..4]ofinteger;各元素前后左右的关系i,j1,11,21,31,42,12,22,32,410,110,210,310,4……3,13,23,33,4SA存贮时要占3个字节(i-1)*nh+(j-1)个如何按列呢？a11a12a13a14……a1na21a22a23a24……a2na31a32a33a34……a3n………………………………am1am2am3am4……amn二维数组在内存的存储方式是线性的。

1：按照行存储：即先存储第一行然后在存储第二行，那么aij的值应该是a11+（i-1)*n+j-1

2:1：按照列存储：即先存储第一列然后在存储第二列，那么aij的值应该是a11+（j-1)*m+i-1推广到一般的二维数组A[C1-D1][C2-D2],A[i][j]存储地址计算公式：

以行为序：首地址+（（i-C1）*（D2-C2+1）+（j-C2））*L

以列为序：首地址+（（j-C2）*（D1-C1+1）+（i-C1））*LL表示所占内存队队列的基础知识队列(Queue)是一种特殊的线性表。它是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表进队出队F（队首）R（队尾）A1A2A3A4……Ai

到医院看病排队挂号排队在学校食堂就餐排队买饭队列的概念队头队尾入队队列是一种只允许在表的一端（称为队尾）进行插入，在另一端（称为对头）进行删除的线性表。队尾a1队尾a2队尾a3出队队头i:=0;j:=0;Whilej<3dobegininc(j)read(a[j]);end;出队：Inc（i）队伍长度：Len:=j-i队列的概念队列是一种只允许在表的一端（称为队尾）进行插入，在另一端（称为对头）进行删除的线性表。与我们生活中的排队非常相似先排队的先离开晚排队的晚离开

不允许插队

不允许中途离队因此，队列也称先进先出(FIFO)历届初比赛题(选)(9tg)已知队列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是()。

A)5B)41C)77D)13E)18队列的进队和出队：frontrear空队列frontrearA,B,C,D进队ABCDfrontrearA,B出队CDfrontrearE,F,G进队CDEFCDEFGfrontrearH进队,溢出产生假溢出原因：被删除元素的空间在该元素删除后永远用不到。大家思考一下，进队与出队两个变量如何变化？01234012340123401234567frontBCDrear一般情况AC01234567队满frontrearCDEFABG01234567rear空队列frontC01234567队满(正确)frontrearCDEFAB在循环队列中，永远会空一个位置，是为了辨别队满还是队空。G循环队列(CircularQueue)队头、队尾指针加1，可用取模(余数)运算实现。队头指针进1:front=(front+1)modmaxsize;出队队尾指针进1:rear=(rear+1)modmaxsize;入队队列初始化：front=rear=0;队空条件：front==rear;队满条件：(rear+1)modmaxsize==front;

01234567循环队列frontrear