数据结构和程序设计

《数据结构和程序设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章：数据结构与算法考核知识点：算法的基本概念数据结构的基本概念线性表的定义栈和队列线性链表树的基本概念查找技术排序技术第一章：数据结构与算法第一节：算法1、定义所谓算法是指解题方案的准确而完整的描述。2、算法的基本牲（1）可行性:同一个算法在不同的计算机上应得到相同的结果（2）确定性。是指算法中的每一步都必须是有明确的定义，不允许有模棱两可的解释，也不允许有多义性。（3）有穷性。是指必须能在执行有限步骤之后终止。（4）拥有足够的情报。一个算法执行的结果总是与输入的数据有关，不同的输入有不同的结果。当输入不足或输入错误时，算法

2、可能就无法执行。当算法拥有足够多的情报时（考虑的输入可能性越多），出错的可能越小。3、算法的基本要素一个算法通常有二种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。（1）对数据对象的运算和操作基本运算和操作有以下四类：算术运算、逻辑运算、关系运算和数据传输（赋值、输入、输出）。（2）算法的控制结构算法的控制结构一般可分为顺序、选择、循环三种基本结构。4、算法设计的基本方法计算机解题的过程实际上是实施某种算法，称计算机算法。（1）列举法列举法是指根据提出的问题，列举所有可能的情况，然后，进行处理。（2）归纳法通过列

3、举少量的特殊情况，经过分析，找出一般关系（3）递推从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果（4）递归将一个复杂的问题归结为若干个较简单的问题，直到最简单的问题解决（5）减半递推技术（6）回溯法就是对问题分而治之。5、算法复杂度算法复杂度主要包括时间和空间复杂度。（1）时间复杂度是指算法基本运算的次数。（不是指运算的时间）（2）空间复杂度执行这个算法所需要的内存空间。包括程序所占的空间、输入的初始数据所占的空间、运算时所需的空间。算法的时间复杂度是指A）执行算法程序所需要的时间B）算法程序的长度C）算法执行过程中

4、所需要的基本运算次数D）算法程序中的指令条数算法的空间复杂度是指A）算法程序的长度B）算法程序中的指令条数C）算法程序所占的存储空间D）算法执行过程中所需要的存储空间第2节：数据结构的基本概念大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。数据结构主要研究三个方面的问题：（1）数据的逻辑结构：数据集合众各数据元素间所固有的逻辑关系（2）数据的存储结构（物理结构）：各数据元素在计算机中的存储关系（3）对各种数据结构进行的运算。以上问题的主要目的是为了提高数据处理的效率

5、。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占的计算机存储空间。1、什么是数据结构实例：无序表的顺序查找与有序表的对分查找3516788543293321544616212933354346547885数据元素在表中的表列顺序对查找效率是有很大的影响。1、什么是数据结构数据结构是指反映数据元素之间关系的数据元素集合的表示。学号姓名性别计算机200501张三女80200503李四男70200513王五女50成绩单在上表中，查找给定学号的某学生的情况时很方便的。但要查找计算机成绩

6、在75分以上的情况时，则需要从头到尾扫描。为了便于查找成绩，可以进行重新组织数据结构是指相互有关联的数据元素的集合1、什么是数据结构（1）数据结构的逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。（2）数据的存储结构数据的逻辑结构在计算机存储空间的存放形式称为数据的存储结构（也称数据的物理结构）下列叙述中正确的是A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以

7、有多种存储结构，且各种存储结构影响数据处理的效率数据的存储结构是指A）存储在外存中的数据B）数据所占的存储空间量C）数据在计算机中的顺序存储方式D）数据的逻辑结构中计算机中的表示2、数据结构的图形表示父亲儿子女儿d1d2d3名词解释：（1）结点（2）前件结点（3）后件结点（4）根结点（5）终结点在数据结构中，与所使用的计算机无关的数据结构是（）A逻辑B存储C逻辑和存储D物理2、数据结构的图形表示父亲儿子女儿d1d2d3名词解释：（1）结点（2）前件结点（3）后件结点（4）根结点（5）终结点春夏秋冬3、线性结构和非线性结构如果在一

8、个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。根据数据元素之间前后件关系的复杂程度，将数据结构分为这两类什么是线性结构？线性必须满足以下二个条件：（1）有且只有一个根结点。（2）每个结点最多有一个前件，也最多一个后件。d1d2d3春夏秋冬在数据结