(1)ES- Elementary Streams (原始流)，对视频、音频信号及其他数据进行编码压缩后的数据流称为原始流。原始流包括访问单元，比如视频原始流的访问单元就是一副图像的编码数据。
(2) PES- Packetized Elementary Streams (分组的原始流)，原始流形成的分组称为PES分组，是用来传递原始流的一种数据结构
(3)节目是节目元素的集合。节目元素可能是原始流，这些原始流有共同的时间基点，用来做同步显示。
(4)传输流和节目流TS-Transport Stream 翻译为“传输流”PS-Program Stream 翻译为“节目流”PS用来传输和保存一道节目的编码数据或其他数据。PS的组成单位是PES分组。TS用来传输和保存多道节目的编码数据或其他数据，TS的组成单位是节目。PS适用于不容易发生错误的环境，以及涉及到软件处理的应用，典型应用如DVD光盘的文件存储TS适用于容易发生错误的环境，典型应用就是数字电视信号的传输。TS和PS是可以互相转换的，比如从TS中抽取一道节目的内容并产生有效的PS是可能。
(5)传输流分组和PES分组原始流分成很多PES分组，保持串行顺序，一个PES分组只包含一个原始流的编码数据。PES分组长度很大，最大可为64K字节。PES分组分为“分组首部(header)”和“有效负载(payload)”。“有效负载”指跟随在首部字节之后的字节。首部的前4个字节构成分组的起始码，标识了该分组所属原始流的类型和ID号。TS分组也就是传输流数据形成的数据包。每个TS分组长度为188字节，包括“分组首部”和“有效负载，前4个字节是分组首部，包含了这个分组的一些信息。有些情况下需要更多的信息时，需在后面添加“调整字段(adaption field)”。两者之间的关系:PES分组是插入到TS分组中的，每个PES分组首部的第一字节就是TS分组有效负载的第一字节。一个PID值的TS分组只带有来自一个原始流的数据。
(6)PSI 全称Program Specific Information，意为节目专用信息。传输流中是多路节目复用的，那么，怎么知道这些节目在传输流中的位置，区分属于不同节目呢？所以就还需要一些附加信息，这就是PSI。PSI也是插入到TS分组中的，它们的PID是特定值。MPEG-2中规定了4个PSI，包括PAT(节目关联表)，CAT(条件访问表)，PMT(节目映射表)，NIT(网络信息表)，这些PSI包含了进行多路解调和显示节目的必要的和足够的信息。应用中可能包括更多的信息，比如DVB-T中定义了SDT(服务描述表),EIT(环境信息表),BAT(节目组相关表),TDT(时间日期表)等，统称为DVB-SI(服务信息)。PSI的PID是特定的，含PSI的数据包必须周期性的出现在传输流中。
PMT (Program Map Table )节目映射表PMT所在分组的PID由PAT指定，所以要先解出PAT，再解PMT。PMT中包含了属于同一节目的视频、音频和数据原始流的PID。找到了PMT，解多路复用器就可找到一道节目对应的每个原始流的PID，再根据原始流PID，去获取原始流。
PAT (Program Association Table )节目关联表PAT所在分组的PID=0 PAT中列出了传输流中存在的节目流PAT指定了传输流中每个节目对应PMT所在分组的PIDPAT的第一条数据指定了NIT所在分组的PID ，其他数据指定了PMT所在分组的PID。
CAT (Conditional Access Table)条件访问表CAT所在分组的PID=1CAT中列出了条件控制信息(ECM)和条件管理信息(EMM)所在分组的PID。CAT用于节目的加密和解密NIT( N etwork Information Table)网络信息表NIT所在分组的PID由PAT指定NIT提供一组传输流的相关信息，以及于网络自身特性相关的信息，比如网络名称，传输参数(如频率,调制方式等)。NIT一般是解码器内部使用的数据，当然也可以做为EPG的一个显示数据提供给用户做为参考。几种PSI之间的关系，如下图所示：首先PAT中指定了传输流中所存在的节目，及每个节目对应的PMT的PID号。比如Program 1对应的PMT 的PID=22,然后找到PID=22的TS分组，解出PMT，得到这个节目中包含的原始流的PID，再根据原始流的PI
D去找相应的TS分组，获取原始流的数据，然后就可以送入解码器解码了。
数据结构（1）TS分组前面提到，TS分组由188个字节构成，其结构如下：
transport_packet(){
sync_byte // 8
transport_error_indicator //1
payload_unit_start_indicator //1
transport_priority // 1 PI
D //13
transport_scrambling_control // 2
adaptation_field_control //2
continuity_counter //4
if(adaptation_field_control=='10' || adaptation_field_control=='11'){
adaptation_field()
}
if(adaptation_field_control=='01' || adaptation_field_control=='11') {
for (i=0;i data_byte //8 } } } 前面32bit的数据即TS分组首部，它指出了这个分组的属性。 sync_byte同步字节，固定为0x47 ，表示后面的是一个TS分组，当然，后面包中的数据是不会出现0x47的 transport_error_indicator传输错误标志位，一般传输错误的话就不会处理这个包了payload_unit_start_indicator这个位功能有点复杂，字面意思是有效负载的开始标志，根据后面有效负载的内容不同功能也不同，后面用到的时候再说。 transport_priority传输优先级位，1表示高优先级，传输机制可能用到，解码好像用不着。PID这个比较重要，指出了这个包的有效负载数据的类型，告诉我们这个包传输的是什么内容。前面已经叙述过。 transport_scrambling_control加密标志位，表示TS分组有效负载的加密模式。TS分组首部(也就是前面这32bit)是不应被加密的，00表示未加密。 adaption_field_control翻译为“调整字段控制”，表示TS分组首部后面是否跟随有调整字段和有效负载。01仅含有效负载，10仅含调整字段，11含有调整字段和有效负载。为00的话解码器不进行处理。空分组没有调整字段 continuity_counter一个4bit的计数器，范围0-15，具有相同的PID的TS分组传输时每次加1，到15后清0。不过，有些情况下是不计数的。如下：(1)TS分组无有效负载(2)复制的TS分组和原分组这个值一样(3)后面讲到的一个标志discontinuity_indicator为1时adaptation_field()调整字段的处理 data_byte有效负载的剩余部分，可能为PES分组，PSI，或一些自定义的数据。 （2） PAT数据结构如下： program_association_section() { table_id // 8 section_syntax_indicator // 1 '0' // 1 reserved // 2 section_length // 12 transport_stream_id // 16 reserved // 2 version_number // 5 current_next_indicator // 1 section_number // 8 last_section_number // 8 for (i=0; i program_number // 16 reserved // 3 if(program_number == '0') { network_PID // 13 } else { program_map_PID // 13 } } CRC_32 // 32 } table_id固定为0x00 ，标志是该表是PAT section_syntax_indicator段语法标志位，固定为1 section_length表示这个字节后面有用的字节数，包括CRC32。假如后面的字节加上前面的字节数少于188，后面会用0XFF填充。假如这个数值比较大，则PAT会分成几部分来传输。 transport_stream_id该传输流的ID，区别于一个网络中其它多路复用的流。 version_number范围0-31，表示PAT的版本号，标注当前节目的版本．这是个非常有用的参数，当检测到这个字段改变时，说明TS流中的节目已经变化了，程序必须重新搜索节目．current_next_indicator表示发送的PAT是当前有效还是下一个PAT有效。 section_number分段的号码。PAT可能分为多段传输，第一段为00，以后每个分段加1，最多可能有256个分段 last_section_number 最后一个分段的号码 program_number节目号 network_PID 网络信息表（NIT）的PID，网络信息表提供了该物理网络的一些信息，和电视台相关的。节目号为0时对应的PID为network_PID program_map_PID节目映射表的PID，节目号大于0时对应的PID，每个节目对应一个CRC_32CRC32校验码 上面program_number，network_PID，program_map_PID 是循环出现的。program_number 等于0时对应network_PID，program_number等于其它值时对应program_map_PID。 (3)PMT PMT数据结构如下： TS_program_map_section() { table_id // 8 section_syntax_indicator // 1 '0' // 1 reserved // 2 section_length // 12 program_number // 16 reserved // 2 version_number // 5 current_next_indicator // 1 section_number // 8 last_section_number // 8 reserved // 3 PCR_PID // 13 reser ved4 program_info_length // 12 for (i=0; i descriptor() } for (i=0;i stream_type // 8 reserved // 3 elementary_PID // 13 reserved // 4 ES_info_length // 12 for (i=0; i descriptor() } } CRC_32 // 32 } table_id固定为0x02 ，标志是该表是PMT。 section_syntax_indicator section_length version_number current_next_indicator 以上四个字段意思和PAT相同，可参考上面解释 section_number last_section_number 以上两个字段意思和PAT相同，不过值都固定为0 x00，我觉得这样的原因可能是因为PMT不需要有先后顺序，因为先定义哪个节目都是无所谓。 program_number节目号，表示该PMT对应的节目 PCR_PID PCR（节目时钟参考）所在TS分组的PID，根据PID可以去搜索相应的TS分组，解出PCR信息。 program_info_length该节目的信息长度，在此字段之后可能会有一些字节描述该节目的信息 stream_type指示了PID为elementary_PID的PES分组中原始流的类型，比如视频流，音频流等，见后面的表 elementary_PID该节目中包括的视频流，音频流等对应的TS分组的PID ES_info_length该节目相关原始流的描述符的信息长度。stream_type对应的类型： 实用标准文档 文案大全第1章数据结构基础 结构之美无处不在： 说到结构，任何一件事物都有自己的结构，就如可以看得见且触摸得到的课桌、椅子，还有看不见却也存在的化学中的分子、原子。可见，一件事物只要存在，就一定会有自己的结构。一幅画的生成，作家在挥毫泼墨之前，首先要在数尺素绢之上做结构上的统筹规划、谋篇布局。一件衣服的制作，如果在制作之前没有对衣服的袖、领、肩、襟、身等各个部位周密筹划，形成一个合理的结构系统，便无法缝制出合体的衣服。还有教育管理系统的结构、通用技术的学科结构和课堂教学结构等。试想一下，管理大量数据是否也需要用到数据结构呢？ 本章知识要点： 数据结构的基本概念 数据类型和抽象数据类型 算法和算法分析 1.1 数据结构的基本概念 计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算，还是数据处理、过程控制、对文件的存储和检索以及数据库技术等计算机应用，都是对数据进行加工处理的过程。因此，要设计出一个结构良好而且效率较高的程序，必须研究数据的特性、数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。 计算机在发展的初期，其应用围是数值计算，所处理的数据都是整型、实型和布尔型等简单数据，以此为加工、处理对象的程序设计称为数值型程序设计。随着计算技术的发展，计算机逐渐进入到商业、制造业等其他领域，广泛地应用于数据处理和过程控制中。与此相对应，计算机所处理的数据也不再是简单的数值，而是字符串、图形、图像、语音和视频等复杂的数据。这些复杂的数据不仅量大，而且具有一定的结构。例如，一幅图像是一个由简单数值组成的矩阵，一个图形中的几何坐标可以组成表。此外，语言编译过程 《数据结构》基本概念 基本概念 ?数据 数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 ?数据元素 数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 ?数据项 数据项是构成数据元素的不可分割的最小单位。?数据对象 数据对象是具有相同性质的数据元素的集合，是数据的子集。 注意：在不产生混淆的情况下，将数据对象简称为数据。 ?数据结构 数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure = (D, R)，其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 ?数据的逻辑结构 数据的逻辑结构是指数据元素之间逻辑关系的整体。 根据数据元素之间逻辑关系的不同，数据结构分为四类： ⑴集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； ⑵线性结构：数据元素之间存在着一对一的线性关系； ⑶树结构：数据元素之间存在着一对多的层次关系； ⑷图结构：数据元素之间存在着多对多的任意关系。 注意：数据结构分为两类：线性结构和非线性结构。?数据的存储结构 数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。 顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。 链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 ?抽象数据类型 抽象数据类型是一个数据结构以及定义在该结构上 基本概念 数据 数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号 集合。 数据元素数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项 数据项是构成数据元素的不可分割的最小单位。 数据对象数据对象是具有相同性质的数据元素的集合，是数据的子集。注意：在不产生混淆的情况下，将数据对象简称为数据。 数据结构数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure = （D, R），其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 数据的逻辑结构数据的逻辑结构是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同，数据结构分为四类： ⑴ 集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； ⑵ 线性结构：数据元素之间存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在着一对多的层次关系； ⑷ 图结构：数据元素之间存在着多对多的任意关系。 注意：数据结构分为两类：线性结构和非线性结构。 数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。 顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。 链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 抽象数据类型抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。抽象数据类型提供了使用和实现两个不同的视图，实现了封装和信息隐藏。 算法的定义通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。 算法的特性 ⑴ 输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象集合。 ⑵ 输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。 ⑶ 有穷性：一个算法必须总是(对任何合法的输入)在执行有穷步之后结束，且每一步都在有穷时间内完成。 ⑷ 确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。 ⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 线性表的定义 线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度，长度等于零时称为空表。 线性表的逻辑关系 在一个非空表L= (a i, a2, , a n)中，任意一对相邻的数据元素和a i之间(1< i < n)存在序偶 关系(a i-i，a i)，且a i-i称为a i的前驱，a i称为的后继。在这个序列中，a i无前驱，a n无后继，其它每个元素有且仅有一个前驱和一个后继。 顺序表的存储结构定义 用MaxSize 表示数组的长度,顺序表的存储结构定义如下： #define MaxSize i00 typedef struct { ElemType data[MaxSize]; // ElemType 表示不确定的数据类型 int length; //length 表示线性表的长度 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 第4章 1．简述需求分析中现行系统调查、新系统逻辑方案的提出等活动的详细内容、关键问题、主要成果及其描述方法。 系统调查 (1)组织机构的调查 了解组织的机构状况。即各部门的划分及其相互关系、人员配备、业务分工、信息流和物流的关系等等。组织机构状况可以通过组织结构图来反映。所谓组织机构图就是把组织分成若干部分，同时标明行政隶属关系，信息流动关系和其他关系。 (2)业务处理状况调查 为了弄清楚各部门的信息处理工作，哪些与系统建设有关，哪些无关，就必须了解组织的业务流程。系统分析人员应按照业务活动中信息流动过程，逐个调查所有环节的处理业务、处理内容、处理顺序和对处理时间的要求，弄清楚各个环节需要的信息内容、信息来源、去向、处理方法、提供信息的时间和信息形态等。 (3)现行系统的目标、主要功能和用户需求调查 只有充分了解现行系统的目标和功能以及用户需求，才能发现存在的问题，寻找解决问题的途径，也使新系统开发成为可能。 (4)信息流程调查 开发信息系统必须了解信息流程。业务流程虽然在一定程度上表达了信息的流动和存储情况，但仍含有物资、材料等内容。为了用计算机对组织的信息进行控制，必须舍去其他内容，把信息的流动、加工、存储等过程流抽象出来，得出组织中信息流的综合情况。描述这种情况的就是数据流图。 (5)数据及功能分析 有了数据流图后，要对图中所出现的数据和信息的属性进一步分析，包括编制数据词典、数据存储情况分析及使用情况分析。同时还要对数据流图中的各个加工逻辑进行描述。可用的工具有决策树、决策表、结构化语言等。 (6)系统运营环境分析 目前我国许多企业组织的信息系统处于停滞状态的主要原因是系统对环境环境的适 应性而非技术问题。因此，必须对系统的应用环境进行认真地调查分析，充分考虑各种可能发生的变化，以提高系统开发的质量。 新系统逻辑方案的提出 (1) 现行系统的薄弱环节 (2) 新系统的总体功能需求 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 第一章材料的结构 2006-09-16 11:50 第一章材料的结构 重点与难点： 在晶体结构中，最常见的面心立方结构（fcc）、体心立方结构（bcc）、密排六方结构（hcp）、金刚石型结构及氯化钠型结构。内容提要： 在所有固溶体中，原子是由键结合在一起。这些键提供了固体的强度和有关电和热的性质。例如，强键导致高熔点、高弹性系数、较短的原子间距及较低的热膨胀系数。由于原子间的结合键不同，我们经常将材料分为金属、聚合物和陶瓷3类。 在结晶固体中，材料的许多性能都与其内部原子排列有关。因此，必须了解晶体的特征及其描述方法。根据参考轴间夹角和阵点的周期性，可将晶体分为7种晶系，14种晶胞。本章重点介绍了在晶体结构中，最常见的面心立方结构（fcc）、体心立方结构（bcc）、密排六方结构（hcp）、金刚石型结构及氯化钠型结构。务必熟悉晶向、晶面的概念及其表示方法（指数），因为这些指数被用来建立晶体结构和材料性质及行为间的关系。在工程实际中得到广泛应用的是合金。合金是由金属和其它一种或多种元素通过化学键合而成的材料。它与纯金属不同，在一定的外界条件下，具有一定成分的合金其内部不同区域称为相。合金的组织就是由不同的相组成。在其它工程材料 中也有类似情形。尽管各种材料的组织有多种多样，但构成这些组织的相却仅有数种。本章的重点就是介绍这些相的结构类型、形成规律及性能特点，以便认识组织，进而控制和改进材料的性能。学习时应抓住典型例子，以便掌握重要相的结构中原子排列特点、异类原子间结合的基本规律。 按照结构特点，可以把固体中的相大致分为五类。 固溶体及金属化合物这两类相是金属材料中的主要组成相。它们是由金属元素与金属元素、金属元素与非金属元素间相互作用而形成。固溶体的特点是保持了溶剂组元的点阵类型不变。根据溶质原子的分布，固溶体可分为置换固溶体及间隙固溶体。一般来说，固溶体都有一定的成分范围。化合物则既不是溶剂的点阵，也不是溶质的点阵，而是构成了一个新的点阵。虽然化合物通常可以用一个化学式（如AxBy）表示，但有许多化合物，特别是金属与金属间形成的化合物往往或多或少由一定的成分范围。 材料的成分不同其性能也不同。对同一成分的材料也可通过改变内部结构和组织状态的方法，改变其性能，这促进了人们对材料内部结构的研究。组成材料的原子的结构决定了原子的结合方式，按结合方式可将固体材料分为金属、陶瓷和聚合物。根据其原子排列情况，又可将材料分为晶体与非品体两大类。本章首先介绍材料的晶体结构。基本要求： 1.认识材料的3大类别：金属、聚合物和陶瓷及其分类的基础。 2.建立原子结构的特征，了解影响原子大小的各种因素。 数据：是对客观事物的符号表示。 数据元素：是数据的基本单位，也称节点（node）或记录（record）。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。 数据项：有独立含义的数据最小单位，也称域(field)。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 根据数据元素间关系的基本特性，有四种基本数据结构 集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 线性结构：结构中的数据元素之间存在一个对一个的关系。 树形结构：结构中的数据元素之间存在一个对多个的关系。 图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。 逻辑结构：抽象反映数据元素之间的逻辑关系。（算法设计） 物理结构（存储结构）：数据结构在计算机中的表示。（算法实现） 存储结构分为： 顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。 链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。 算法：对特定问题求解步骤的一种描述。 算法的五个重要特性：有穷性，确定性，可行性，输入和输出。 算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。 衡量算法效率的方法：事后统计法和事前分析估算法。 算法执行时间的增长率和f(n) 的增长率相同，则可记作：T (n) = O(f(n))，称T (n) 为算法的(渐近)时间复杂度 算法运行时间的衡量准则：以基本操作在算法中重复执行的次数。 栈：限定仅在表尾进行插入或删除操作线性表。入栈：插入元素的操作；出栈：删除栈顶元素的操作。队列：只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾，删除的一端叫队头。串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目； 空串：零个字符的串；子串：；串中任意个连续的字符组成的子序列；位置：字符在序列中的序号；相等：串的值相等；空格串：由一个或多个空格组成的串，空格串的长度为串中空格字符的个数。存储位置：LOC(i ,j)=LOC(0,0)+(b2*i+j)L 结点:包含一个数据元素及若干指向其子树的分支；结点的度: 结点拥有的子树； 树的度:树中所有结点的度的最大值；叶子结点: 度为零的结点；分支结点: 度大于零的结点 树的深度：树中叶子结点所在的最大层次森林：m棵互不相交的树的集合。 二叉树的性质： 性质1：在二叉树的第i 层上至多有2i-1 个结点。(i≥1) 性质2：深度为k 的二叉树上至多含2k-1 个结点。（k≥1） 性质3: 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为2 的结点， 则必存在关系式：n0 = n2+1。 性质4: 具有n 个结点的完全二叉树的深度为?log2n? +1。 满二叉树：指的是深度为k且含有2k-1个结点的二叉树。 完全二叉树：树中所含的n 个结点和满二叉树中编号为1 至n 的结点一一对应。 路径长度：路径上分支的数目。树的路径长度：树根到每个结点的路径长度之和。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：WPL(T) =∑w k l k 带权路径长度最小的二叉树，称为最优树二叉树或赫夫曼树。 关键路径：路径长度最长的路径。 目录 目录 (1) 第一章绪论 (5) 一、内容提要 (6) 二、学习重点 (6) 三、例题解析 (6) 第二章线性表 (10) 一、内容提要 (10) 二、学习重点 (11) 三、例题解析 (13) 第三章栈和队列 (21) 一、内容提要 (21) 二、学习重点 (22) 三、例题解析 (24) 第四章串 (36) 一、内容提要 (36) 二、学习重点 (37) 三、例题解析 (37) 第五章数组和广义表 (43) 一、内容提要 (43) 二、学习重点 (44) 三、例题解析 (44) 第六章树和二叉树 (48) 一、内容提要 (49) 二、学习重点 (49) 三、例题及分析 (51) 第七章图 (58) 一、内容提要 (58) 二、学习重点 (59) 三、例题解析 (61) 第八章动态存储治理 (70) 一、内容提要 (70) 二、学习重点 (71) 三、例题解析 (71) 第九章查找 (77) 一、内容提要 (77) 二、学习重点 (78) 三、例题解析 (79) 第十章内部排序 (87) 一、内容提要 (87) 二、学习要点 (88) 二、例题解析 (89) 第十一章外部排序 (98) 一、内容提要 (98) 二、学习要点 (99) 三、习题解析 (99) 第十二章文件 (105) 一、内容提要 (105) 二、学习重点 (106) 第一章绪论 一、内容提要 1 数据结构研究的内容。 2 差不多概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型。 3 算法的定义及五个特征。 4 算法描述：类PASCAL语言。 5 算法设计要求。 6 算法分析。 二、学习重点 1 数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。 2 抽象数据类型的定义、表示和实现方法。 3 类PASCAL书写规范，过程（函数）中值参和变参的差不，过程调用规则。 4 用计算语句频度来估算算法的时刻复杂度。 三、例题解析 数据流程图 1.该图由业务流程图转换而来。用以描述数据在系统中的流动情况。 2.目的有二。1,看是否因为我们工作的失误,漏掉了某些数据。2,如果某些数据,从来没有哪个数据处理用到,而且确实没有失误,说明该数据的产生没有意义。 3.组成: 数据处理:名字必须是动词+ 名词。动词是对数据的操作,名词是被操作的数据,如填写密码。有一个唯一的编码。 数据流: 数据存储:数据流的集合,将来很有可能变成数据库。 外部实体:系统之外,又与本系统发生联系的事物。往往是数据的来源或者去向。 4.如何绘制数据流程图: (1根据给出的题意,找出每句的动词+名词,分析该名词是不是数据处理。动词+名词不一定是数据处理,但数据处理一定是动词+名词。分析每个句子中,有几个数据处理,哪些可以省略不写,哪些级别太低,在现在正在画的层次上,不需要些。例如第 6句,动词+名词有信息汇总排序、确定信息等级、形成初始表和上报初始表这4个,但我们上报初始表,可以通过一个数据流的来表示,数据流的名字叫做初始表,数据流的方向代表了上报的方向;而信息汇总排序、确定信息等级我们认为他们是形成初始表的具体过程,故此,这句话,我们整理的数据处理只有一个,那就是形成初始表。并不是说每句话只能有一个数据处理。有一句话有两个甚至以上的数据处理。例如第7句,这里面有两个数据处理,因为是不同对象操作的不同的业务,因此两个都留着。 (2第2步是找出所有的外部实体,外部实体一般数据的来源或者去向。在画外部实体的时候,注意别忘了一些容易忽视的,例如第5句中的文件。 (3第3步是找出主要的数据存储。其实,基本上每一个数据处理,都可能产生一个数据存储,例如提供考试成绩这个数据处理,产生一个考试成绩的数据存储。但一个是为了阅读的清晰,另外数据存储将来可能转换为未来系统的数据库。因此,一般只画主要的。因为这个是奖学金评定的流程,因此,将奖学金的初始表、总名单作为了数据存储,包括档案,在这里,档案其实也可以画成外部实体。因为加入了数据存储,导致原来数据处理之间的数据流断开了,因此,需要重新画数据流。 (4进行优化和检查:每个数据处理,必须有流入的数据流和流出的数据流;每个数据存储,必须有流入的数据流和流出的数据流;每个数据流,至少有一端连接数据处理;父图和子图的数据要平衡;数据流不能交叉。 1.由教学秘书提供各个年级专业的考试成绩; 2.由院系辅导员提供各个同学的德育成绩; 3.由体育委员提供各个同学的早操卡考勤信息; 4.由学生处提供学生的奖励信息; 5.班委根据奖学金评定文件,对上述数据进行审核; 6.审核后,班委将符合条件学生的上述信息汇总排序、确定等级,形成班级奖学金初始表报院系; 第一章数据结构基本概念 1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。 2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。由于目前关于这个问题有许多说法，我们采用了一种最流行的说法，即Coad与Yourdon 给出的定义：面向对象= 对象+ 类+ 继承+ 通信。 要点：* 抽象数据类型的封装性 * 面向对象系统结构的稳定性 * 面向对象方法着眼点在于应用问题所涉及的对象 3、数据结构的抽象层次：理解用对象类表示的各种数据结构 4、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。 要点：* 算法与程序的不同之处需要从算法的特性来解释 * 算法的正确性是最主要的要求 * 算法的可读性是必须考虑的 * 程序的程序步数的计算与算法的事前估计 * 程序的时间代价是指算法的渐进时间复杂性度量 第二章数组 1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储 要点：* 数组元素的存放地址计算 2、顺序表：顺序表的定义、搜索、插入与删除 要点：* 顺序表搜索算法、平均比较次数的计算 * 插入与删除算法、平均移动次数的计算 3、多项式：多项式的定义 4、字符串：字符串的定义及其操作的实现 要点：* 串重载操作的定义与实现 第三章链接表 1、单链表：单链表定义、相应操作的实现、单链表的游标类。 要点：* 单链表的两种定义方式（复合方式与嵌套方式） * 单链表的搜索算法与插入、删除算法 * 单链表的递归与迭代算法 2、循环链表：单链表与循环链表的异同 3、双向链表：双向链表的搜索、插入与删除算法、链表带表头结点的优点 4、多项式的链接表示 第四章栈与队列 数据结构基本概念练习题 1、选择练习题 1）执行下面程序段时，执行S语句的次数为------- for(int I=1;I<=n;I++) for(int j=1;j<=I;j++) S; (A) n^2 (B) n^2/2 (C) n(n+1) (D) n(n+1)/2 答案：D 2）算法是指令的有限序列，其中每一条指令表示一个或多个操作。下列______不属于算法的五个特性之一。 (A) 有一或多个输出(B) 有零或多个输入(C) 有穷性(D) 通俗易懂性 答案：D 3）若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 (A) 顺序表(B) 双链表(C) 带头结点的双循环链表(D) 单循环链表 答案：A 4）下面的叙述正确的是（） (A) 线性表在链式存储时，查找第i个元素的时间同i的值成正比; (B) 线性表在链式存储时，查找第i个元素的时间同i的值无关; (C) 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比; (D) 以上说法都不对. 答案：A 5) 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。 (A) 单链表(B) 顺序表(C) 单向循环链表(D) 双链表 答案：B 6) 在双向链表指针p指向的结点前插入一个指针q指向的结点操作是( )。 (A) p->prior=q;q->next=p;p->prior->next=q;q->prior=q; (B) p->prior=q;p->prior->next=q;q->next=p;q->Prior=p->prior; (C) q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q; (D) q->prior=p->prior;q->next=q;p->prior=q;p->prior=q; 答案：C 7) 设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。 (A) 线性表的顺序存储结构(B) 队列(C) 线性表的链式存储结构(D) 栈 第一章数据结构基本概念 数据：计算机程序所加工处理的描述客观事物的符号表示。 数据元素：数据的基本单位，是数据集合中的一个个体,在计算机程序中通常作为一个整体进行考虑和处理。数据元素可由一个或若干个数据项所组成。 数据项：是具有独立意义的数据的最小单位。 数据对象：性质相同的数据元素的集合,是数据的一个子集。 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。即数据的组织形式。数据元素相互之间的关系称为结构。 四种基本的数据结构是：集合、线性结构、树形结构、和图形结构。 数据结构包括三个方面的内容：逻辑结构、存储结构、基本操作（运算） 数据类型：一个值的集合和定义在这个值集上的一组操作。程序设计语言中对于给定变量的所有可能取值的集合。 抽象数据类型（ADT）：一种数据类型及在这种数据类型上定义的一组操作。包括数据类型的定义和这种数据类型的操作集合。 第二章线性表 线性表是n(n>=0)个数据元素的有限序列，同一线性表中的数据元素必定具有相同特性，即属于同一数据对象，相邻数据元素之间存在序偶关系。n定义为线性表的长度；n为0表示该线性表为空表；数据元素可以是一个数、一个符号或由多个数据项所构成的。 线性表中任一数据元素的存储位置为： s i a LOC a LOC i ? - + =)1 ( ) ( ) ( 1 线性链表是一种动态存储结构，所占用的存储空间是在程序的执行过程中得到的，当线性链表要增加一个结点时，向系统申请一个存储空间，删除结点时要将空间释放。 由线性链表的结点定义，每个结点中均只含有一个指针域，用于指向其后继结点，故也称单链表。 循环链表是线性表的另一种形式的链式存储表示。它的特点是表中最后一个结点的指针域指向头结点，整个链表成为一个由链指针相链接的环，并且可将头指针设成指向最后一个结点（尾指针）。空的循环链表由只含一个自成循环的头结点表示。 若双向链表中的两个链均构成回路，则称为双向循环链表。 第三章栈和队列 栈是限定只能在表的一端（表尾）进行插入和删除操作的线性表；允许插入和删除的一端，称为栈顶(top)； 第1章绪论 内容提要： ◆数据结构研究的内容。 针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。 数据结构涵盖的内容： ◆基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。 数据——所有能被计算机识别、存储和处理的符号的集合。 数据元素——是数据的基本单位，具有完整确定的实际意义。 数据对象——具有相同性质的数据元素的集合，是数据的一个子集。 数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为： Data_Structure=（D, R） 数据类型——是一个值的集合和定义在该值上的一组操作的总称。 抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作， 它由基本的数据类型构成。 ◆算法的定义及五个特征。 算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 算法的基本特性：输入、输出、有穷性、确定性、可行性 ◆算法设计要求。 ①正确性、②可读性、③健壮性、④效率与低存储量需求 ◆算法分析。 时间复杂度、空间复杂度、稳定性 学习重点： ◆数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。 ◆用计算语句频度来估算算法的时间复杂度。 第二章线性表 内容提要： ◆线性表的逻辑结构定义，对线性表定义的操作。 线性表的定义：用数据元素的有限序列表示 ◆线性表的存储结构：顺序存储结构和链式存储结构。 顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。 链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。通过指针来实现！ ◆线性表的操作在两种存储结构中的实现。 数据结构的基本运算：修改、插入、删除、查找、排序 1)修改——通过数组的下标便可访问某个特定元素并修改之。 核心语句: V[i]=x; 顺序表修改操作的时间效率是 O(1) 2) 插入——在线性表的第i个位置前插入一个元素 实现步骤： ①将第n至第i 位的元素向后移动一个位置； ②将要插入的元素写到第i个位置； ③表长加1。 注意：事先应判断: 插入位置i 是否合法?表是否已满? 应当符合条件： 1≤i≤n+1 或 i=[1, n+1] 核心语句： for (j=n; j>=i; j--) a[j+1]=a[ j ]; a[ i ]=x; n++; 插入时的平均移动次数为：n(n+1)/2÷（n+1）＝n/2≈O(n) 3) 删除——删除线性表的第i个位置上的元素 实现步骤： ①将第i+1 至第n 位的元素向前移动一个位置； ②表长减1。 注意：事先需要判断，删除位置i 是否合法? 应当符合条件：1≤i≤n 或 i=[1, n] 核心语句： for ( j=i+1; j<=n; j++ ) a[j-1]=a[j]; n--; 第一章晶体结构 晶体-----内部组成粒子（原子、离子或原子团）在微观上作有规则的周期性重复排列构成的固体。 晶体的通性------所有晶体具有的共通性质，如自限性、最小内能性、锐熔性、均匀性和各向异性、对称性、解理性等。 单晶体和多晶体-----单晶体的内部粒子的周期性排列贯彻始终；多晶体由许多小单晶无规堆砌而成。 基元、格点和空间点阵------基元是晶体结构的基本单元，格点是基元的代表点，空间点阵是晶体结构中等同点（格点）的集合，其类型代表等同点的排列方式。原胞、WS原胞-----在晶体结构中只考虑周期性时所选取的最小重复单元称为原胞；WS原胞即Wigner-Seitz原胞，是一种对称性原胞。 晶胞-----在晶体结构中不仅考虑周期性，同时能反映晶体对称性时所选取的最小重复单元称为晶胞。 原胞基矢和轴矢----原胞基矢是原胞中相交于一点的三个独立方向的最小重复矢量；晶胞基矢是晶胞中相交于一点的三个独立方向的最小重复矢量，通常以晶胞基矢构成晶体坐标系。 布喇菲格子（单式格子）和复式格子------晶体结构中全同原子构成的晶格称为布喇菲格子或单式格子，由两种或两种以上的原子构成的晶格称为复式格子。简单格子和复杂格子（有心化格子）------一个晶胞只含一个格点则称为简单格子，此时格点位于晶胞的八个顶角处；晶胞中含不只一个格点时称为复杂格子，其格点除了位于晶胞的八个顶角处外，还可以位于晶胞的体心（体心格子）、一对面的中心（底心格子）和所有面的中心（面心格子）。 密堆积和配位数-----晶体组成原子视为等径原子时所采取的最紧密堆积方式称为密堆积，晶体中只有六角密积与立方密积两种密堆积方式。晶体中每个原子周围的最近邻原子数称为配位数。由于晶格周期性限制，晶体中的配位数只能取：12，8，6、4、3（二维）和2（一维）。 晶列、晶向（指数）和等效晶列-----晶列是晶体结构中包括无数格点的直线， 第二章晶体的基本概念 z第一节晶体的基本性质 z第二节空间点阵 z第三节整数定律及晶面指数 z第四节晶体投影 晶体研究的早期成就 1690年惠更斯提出：晶体中质点的有序排列导致晶体具有某种多面体外形。 1812年浩羽(R.J.Hauy)提出：晶体是由具有多面体外形的“分子” 成的。 １６６９年，丹麦人斯登诺（Steno,N.1638-1686），１７８３年法国矿物学家爱斯尔（DeI Isle,R.1736-1790）分别在观测各种矿物晶体时发现了晶体的第一个定律──晶面夹角守恒定律。 晶体的对称原理 在１８０５－１８０９年间，德国学者魏斯（Weiss,C.S.1780-1856开始研究晶体外形的对称性 １８３０年德国人赫塞尔（Hessel,J.F.Ch.1796-1872），１８６７年俄国人加多林分别独立地推导出，晶体外形对称元素的一切可能组合方式（也就是晶体宏观对称类型）共有３２种（称为３２种点群） １９世纪４０年代，德国人弗兰根海姆（Frankenheim,M.L.1801-1869）和法国人布拉维（Bravais,A.1811-1863）发展前人的工作，奠定了晶体结构空间点阵理论（即空间格子理论）的基础。弗兰根海姆首次提出晶体内部结构应以点为单位，这些点在三度空间周期性的重复排列。他于１８４２年推出了１５种可能的空间点阵 形式。 布拉维明确地提出了空间格子理论。认为晶体内物质微粒的质心分布在空间格子的平行六面体单位的顶角、面心或体心上，从而它们在三度空间作周期性的重复排列。他于１８４８年指出，弗兰根海姆的１５种空间点阵形式中有两种实质上是相同的，确定了空间点阵的１４种形式 XXX系统结构化概要设计 （文档封面及目录格式与以前作业相同） 1.文档说明(5分) 1.1文档目的 //说明本文档的目的和作用 1.2文档范围 //说明本文档描述的主要内容 1.3读者对象 //说明可能的读者，比如详细设计、编码人员和测试人员 1.4参考文档 //说明编写该文档需要的参考资料，比如《用户需求说明书》和《需求分析规格说明书》等1.5术语与缩写解释 //说明本文档与具体业务无关的技术术语，比如数据流、模块、关系表等 2.项目背景(2分) //说明项目的需求来源以及用户的基本需求，可以参考《用户需求说明书》。 3.需求分析结果(3分) //此章节描述需求分析的分层数据流图 3.1顶层数据流图 //将基于结构化数据流图的《需求分析规格说明书》中顶层数据流图展示出来，无须进行修改（原样拷贝粘贴） 3.2第一层数据流图 3.3第二层数据流图 1. 处理临过期商品子系统 …… 3.n 第n层数据流图 4.基于功能需求的初始功能结构图(50分) //结合以上分层的数据流图，将整个系统对应的数据流图划分成多个功能相对独立的子系统，每个子系统由一个或多个结合紧密的加工组成。比如教科书第100页，从“医院就诊管理系统”的第一层数据流图可以看出，它由三个相对功能独立的子系统组成，分别是挂号子系统、问诊子系统、交费取药子系统。 4.1子系统1 处理临过期商品子系统 4.1.1数据流图(分数占20%) 4.1.2 功能结构图(分数占50%) // 画出对应的功能结构图，主模块名字和子系统名字一致 4.1.3功能模块说明(分数占30%) // 为功能结构图中每一个模块写一份处理说明和一份接口说明，格式如下： 1.模块名字1（与功能结构图中名字相同） (1)处理说明 // 参见教科书155页7.7.1 (2)接口说明 // 参见教科书155页7.7.2，只需要说明入口参数、返回值、下属模块、上级模块2.模块名字2 (1)处理说明 (2)接口说明 …… 4.2子系统2 定价子系统 4.2.1数据流图 第五章数据结构基础概念 本章我们将介绍有关数据结构的基础知识，要求大家熟悉数据结构中常用的名词、术语，掌握基本概念，分清逻辑结构和存储结构的性质；了解线性表的逻辑结构特性及其在计算机中的表示。 掌握线性表的顺序存储结构及其插入和删除操作的基本思想；掌握栈和队列的特点，能根据实际问题正确地选用它们，掌握栈满、栈空、队满、队空的判别方法；熟悉树型结构的描述方法，了解图的术语和概念。 5.1数据结构基本概念 1、数据结构是怎样产生的？ 我们知道计算机已经不仅仅是用于科学计算了，早期的计算机确实主要用于数值处理，用于科学计算，随着计算机技术的飞速发展，计算机的应用范围不断扩大，已不再局限于单纯的数值计算，更多地应用于控制、管理及数据处理等非数值计算的处理工作。 非数值型的问题在我们日常生活中是非常多的，也需要我们使用计算机来处理这些非数值问题。 例如：在城市交通运输中，从A点到B点有很多条道路，每条道路的长度不同，拥挤程度不同，我们要选择一条最快的线路到达目的地，该如何选择？ 再比如：图书馆有成千上万的图书资料，我们该如何进行管理才能使我们可以快速查找到需要的资料。 北京市有上千万的人口，我们应该怎样保存这些人口的资料信息，才能使我们可以快速查找到所需要查找的人。 象这样的问题都是典型的非数值问题。 要用计算机处理这些非数值问题，就为我们提出了一个课题：如何在计算机内部描述这些非数值问题，采用什么样的算法可以快速、有效地完成问题的求解。随着计算机技术的发展，于是就产生了数据结构。 进一步，对于不同的处理对象，要想设计出高质量的程序，就必须研究，如何组织数据和处理数据，根据问题的要求及数据元素之间的特性，确定相应的存储结构和算法，这些都是数据结构研究的内容。 我们可以通过下面的例子来认识数据结构。 电话是我们通讯联络必不可少的工具。如何用计算机来实现自动查询电话号码呢？要求对于给定的任意姓名，如果该人有电话号码，则迅速给出电话号码，否则，给出查找不到该人电话号码的信息。 对于这样的问题，我们可以按照客户向电信局申请电话号码的先后次序建立电话号码表，存储到计算机中。在这种情况下，由于电话号码表是没有任何规律的，查找时只能从第一个号码开始逐一进行，这样的逐一按顺序进行查找效率非常低。为了提高查询的效率，我 数据结构练习题 1. 下列关于数据的逻辑结构的叙述中，__________是不正确的。 A. 数据的逻辑结构是数据间关系的描述 B．数据的逻辑结构不仅反映数据间的逻辑关系，而且反映其在计算机中的存储方式 C．数据的逻辑结构分为线性结构和非线性结构 D．树形结构是典型的非线性结构 答案B 2. 在文件系统中，文件的逻辑块与存储介质上物理块存放顺序一致的物理结构是___________。 A. 顺序结构 B. 链接结构 C. 索引结构 D. B树结构 答案是A 3. 下列关于数据结构基本概念的叙述中，正确的是___________。 A. 数据的逻辑结构分为表结构和树结构 B. 数据的存储结构分为线性结构和非线性结构 C. 数据元素是数据的基本单位 D. 结点是有独立意义的数据最小单位 标准答案是C 4. 下列关于数据元素的叙述中，不正确的是____________。 A. 数据元素是数据的基本单位，即数据集合中的个体 B. 数据元素是有独立含义的数据最小单位 C. 数据元素又称作结点 D. 数据元素又称为记录 标准答案是B。 5. 下列__________不是文件的物理结构。 A. 顺序结构 B. Hash结构 C. 索引结构 D. 流式结构 标准答案为D。 6. 下列关于数据的存储结构的叙述中，正确的是__________。 A.数据的存储结构是数据间关系的抽象描述 B.数据的存储结构是逻辑结构在计算机存储器中的实现 C.数据的存储结构分为线性结构和非线性结构 D.数据的存储结构对数据运算的具体实现没有影响 标准答案是B。 7. 下列___________是数据结构研究的内容。 Ⅰ数据的采集Ⅱ数据的逻辑结构Ⅲ数据的存储实现 Ⅳ数据的传输Ⅴ数据的检索 A. Ⅱ和Ⅳ B. Ⅰ、Ⅱ和Ⅲ C. Ⅱ、Ⅲ和Ⅴ D. Ⅰ、Ⅲ和Ⅴ 标准答案是C 8. 下列关于数据结构基本概念的叙述中，________是不正确的。 A. 数据是采用计算机能够识别、存储和处理的方式，对现实世界的事物进行的描述 B. 数据元素（或称结点、记录等）是数据的基本单位 C. 一个数据元素至少由两个数据项组成 D. 数据项是有独立含义的数据最小单位 一个数据元素可由一个或多个数据项组成，所以选项C是错误的。 9. 下列关于链式存储结构的叙述中，_______________是正确的。 Ⅰ逻辑上相邻的结点物理上不必邻接 Ⅱ每个结点都包含恰好一个指针域 Ⅲ用指针来体现数据元素之间逻辑上的联系 Ⅳ可以通过计算直接确定第i个结点的存储地址 Ⅴ存储密度小于顺序存储结构 A. Ⅰ、Ⅱ和Ⅲ B. Ⅰ、Ⅱ、Ⅲ和Ⅳ C. Ⅱ、Ⅳ和Ⅴ D. Ⅰ、Ⅲ和Ⅴ 标准答案是D。 10. 下列关于数据运算的叙述中，___________是不正确的。 A. 数据运算是数据结构的一个重要方面 B. 数据运算的具体实现在数据的逻辑结构上进行 C. 检索是一种常用的运算 D. 插入是一种常用的运算大数据结构的基本概念
《数据结构》基本概念
《数据结构》基本概念
数据结构复习要点(整理版).docx
数据流图的构成与绘制步骤
数据结构复习提纲(整理)
晶体的基本概念
数据结构概念名词解释大全
数据结构对象的基本概念
数据流程图和系统结构图_详细版本.
数据结构教学中的重点与难点
数据结构基本概念练习题
数据结构基本概念(1)
数据结构知识点全面总结—精华版
固体物理学基础概念
第二章 晶体的基本概念
数据流图与功能结构图
数据结构基础概念
1-数据结构基本概念(带答案)
相关主题
文本预览