下载文档原格式
数据结构1第1章：绪论数据结构与算法第 1章绪论数据结构与算法Data Structures and Algorithm教学安排：讲课学时：44 实验学时：12,课程设计：18+1周考核要求：期末考试占60%,实验成绩占30% ,平时作业占10% 本学期上课时间：1-12周,周二5-6节，周四5-6节. 致知24 考课试程时间：14周设计：7-15周2021秋Slide. 1 - 1理论系列数据结构与算法第一学期第二学期工科数析Ⅰ 代数与几何工科数析Ⅱ 离散数学系统系列计算机导论数字逻辑计算机组成技术数据结构与算法工具系列第1 章绪论程序设计语言 C++语言程序设计实践 Java语言工程系列管理系列其他课程军训大学外语体育政治大学外语体育计算机职业道德交流技巧 IT企业管理第三学期Linux操作系统*市场营销软件工程概论合同法概率论与数理统计操作系统数据结构与算法课程设计数据库系统面向对象技术与UML马哲英语限选体育第四学期.Net J2EE 系统分析与设计财务管理英语限选体育英语口语运筹学数据库系统课程设计计算机网络编译原理软件开发实践用户界面设计面向服务的计算技术服务学概论软件开发过程管理软件项目管理中文信息处理软件质量保证与测试商务谈判知识产权法嵌入式操作系统第五学期方向课第六学期多核程序设计计算机安全概论英语限选英语口语算法设计与分析方向软件外包开发技术*2)服务学与企业信息化软件工程综合课程设计 3)多媒体与信息处理IT企业创业管理英语限选1)网络通信与信息安全4)嵌入式系统与软件第七学期第八学期毕业设计2021秋Slide. 1 - 2数据结构与算法第 1章绪论物联网专业2021秋Slide. 1 - 3数据结构与算法第 1章绪论教材数据结构与算法(第4版)编著廖明宏郭福顺张岩李秀坤高等教育出版社2021秋Slide. 1 - 4数据结构与算法第 1章绪论参考资料数据结构严尉敏吴伟民编著清华大学出版社2021秋Slide. 1 - 5数据结构与算法第 1章绪论引进教材Data Structures and Program Design in C++数据结构与程序设计――C++语言描述(影印版) Robert L. Kurse, Alexandeer J. Ryba ISBN 7-04-010039-8/TP.691 P7362021秋Slide. 1 - 6数据结构与算法第 1章绪论教材比较2021秋Slide. 1 - 7数据结构与算法第 1章绪论主要内容1.1 数据结构研究对象1.2 数据结构发展概况 1.3 抽象数据型(ADT)1.4 数据结构与程序设计1.5 算法描述与算法分析2021秋Slide. 1 - 8数据结构与算法第 1章绪论1.1 数据结构研究对象◆计算机科学：信息在计算机内使用数据来表示, 研究信息表示和信息处理。
一、填空题01、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的(关系和运算)等的学科。
02、数据结构被形式地定义为(D,R)，其中D是(数据元素)的有限集合，R是D上的(关系)有限集合。
03、数据结构包括数据的(逻辑结构)、数据的(存储结构)和数据的(运算)这三个方面的内容。
04、数据结构按逻辑结构可分为两大类，它们分别是(线性结构)和(非线性结构)。
05、线性结构中元素之间存在(一对一)关系，树形结构中元素之间存在(一对多)关系，图形结构中元素之间存在(多对多)关系。
06、在线性结构中，第一个结点(没有)前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点(没有)后续结点，其余每个结点有且只有1个后续结点。
07、在树形结构中，树根结点没有(前驱)结点，其余每个结点有且只有(1)个前驱结点；叶子结点没有(后续)结点，其余每个结点的后续结点数可以(任意多个)。
08、在图形结构中，每个结点的前驱结点数和后续结点数可以(任意多个)。
09、数据的存储结构可用四种基本的存储方法表示，它们分别是(顺序)、(链式)、(索引)、(散列)。
10、对于给定的n个元素，可以构造出的逻辑结构有(集合)、(线性结构)、(树形结构)、(图状结构)四种。
11、数据的运算最常用的有5种，它们分别是(插入)、(删除)、(修改)、(查找)、(排序)。
12、一个算法的效率可分为(时间)效率和(空间)效率。
13、数据结构中评价算法的两个重要指标是算法的(时间复杂度)和(空间复杂度)。
14、一个数据结构在计算机中的(映射)称为存储结构。
15、算法的五个重要特性是(有穷性)、(确定性)、(可行性)、输入、输出。
16、已知如下程序段for (i=n; i>=1; i--) //语句1{ x++; //语句2for (j=n; j>=i; j--) //语句3y++; //语句4}语句 1 执行的频度为(n+1)；语句2执行的频度为(n)；语句3执行的频度为(n(n+3)/2)；语句4执行的频度为(n(n+1)/2)。
数据结构各章概要第一章概论数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，可以由若干个数据项组成。
数据项是具有独立含义的最小标识单位。
************************************************************数据结构的定义：·逻辑结构：从逻辑结构上描述数据，独立于计算机。
·线性结构：一对一关系。
·非线性结构：一对多关系，多对多关系。
·存储结构：是逻辑结构用计算机语言的实现。
·顺序存储结构：如数组。
·链式存储结构：如链表。
·索引存储结构：·稠密索引：每个结点都有索引项。
·稀疏索引：每组结点都有索引项。
·散列存储结构：如散列表。
·数据运算。
·对数据的操作。
定义在逻辑结构上，每种逻辑结构都有一个运算集合。
·常用的有：检索、插入、删除、更新、排序。
************************************************************数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
·原子类型：由语言提供。
·结构类型：由用户借助于描述机制定义，是导出类型。
抽象数据类型ADT：·是抽象数据的组织和与之的操作。
相当于在概念层上描述问题。
·优点是将数据和操作封装在一起实现了信息隐藏。
************************************************************程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。
算法取决于数据结构。
************************************************************算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。
第一章概论自测题答案姓名班级一、填空题（每空1分，共33分）1. 一个计算机系统包括硬件系统和软件系统两大部分。
2. 一台计算机中全部程序的集合，称为这台计算机的软件资源/（系统）。
3. 计算机软件可以分为系统软件和应用软件两大类。
科学计算程序包属于应用软件，诊断程序属于系统软件（工具）。
4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是汇编语言。
5. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。
6. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。
7. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。
8. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。
9. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
10．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。
11. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。
12. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。
13．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。
14. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。
15. 一个算法的效率可分为时间效率和空间效率。
16. 〖00年省统考〗任何一个C程序都由一个主函数和若干个被调用的其它函数组成。
17. 【00年省统考题】变量一经说明，就确定该变量的取值范围（即存储单元）及确定变量所允许的运算。
二、单项选择题（每小题1分，共15分）（ B ） 1. 通常所说的主机是指∶A) CPU B) CPU和内存C) CPU、内存与外存D) CPU、内存与硬盘（ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶A) ACSII码B) BCD码C)二进制D)十六进制（D）3. 软件与程序的区别是∶A)程序价格便宜、软件价格昂贵；B)程序是用户自己编写的，而软件是由厂家提供的；C) 程序是用高级语言编写的，而软件是由机器语言编写的；D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。
数据结构重点知识点第一章概论1. 数据是信息的载体。
2. 数据元素是数据的基本单位。
3. 一个数据元素可以由若干个数据项组成。
4. 数据结构指的是数据之间的相互关系，即数据的组织形式。
5. 数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算①数据元素之间的逻辑关系，也称数据的逻辑结构，数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。
数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。
③数据的运算，即对数据施加的操作。
最常用的检索、插入、删除、更新、排序等。
6. 数据的逻辑结构分类: 线性结构和非线性结构①线性结构：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表是一个典型的线性结构。
栈、队列、串等都是线性结构。
②非线性结构：一个结点可能有多个直接前趋和直接后继。
数组、广义表、树和图等数据结构都是非线性结构。
7.数据的四种基本存储方法: 顺序存储方法、链接存储方法、索引存储方法、散列存储方法（1）顺序存储方法：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
通常借助程序语言的数组描述。
（2）链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。
通常借助于程序语言的指针类型描述。
（3）索引存储方法：该方法通常在储存结点信息的同时，还建立附加的索引表。
索引表由若干索引项组成。
若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引，稠密索引中索引项的地址指示结点所在的存储位置。
若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引稀疏索引中索引项的地址指示一组结点的起始存储位置。
索引项的一般形式是：(关键字、地址)关键字是能唯一标识一个结点的那些数据项。
