数据结构和程序设计

《数据结构和程序设计》由会员分享，可在线阅读，更多相关《数据结构和程序设计（170页珍藏版）》请在金锄头文库上搜索。

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

2、多），出错的可能越小。3、算法的基本要素一个算法通常有二种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。 （1）对数据对象的运算和操作基本运算和操作有以下四类：算术运算、逻辑运算、关系运算和数据传输（赋值、输入、输出）。 （2）算法的控制结构算法的控制结构一般可分为顺序、选择、循环三种基本结构。4、算法设计的基本方法计算机解题的过程实际上是实施某种算法，称计算机算法。 （1）列举法列举法是指根据提出的问题，列举所有可能的情况，然后，进行处理。 （2）归纳法通过列举少量的特殊情况，经过分析，找出一般关系 （3）递推从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果 （4）

3、递归将一个复杂的问题归结为若干个较简单的问题，直到最简单的问题解决 （5）减半递推技术 （6）回溯法就是对问题分而治之。 5、算法复杂度算法复杂度主要包括时间和空间复杂度。 （1）时间复杂度是指算法基本运算的次数。（不是指运算的时间）（2）空间复杂度执行这个算法所需要的内存空间。包括程序所占的空间、输入的初始数据所占的空间、运算时所需的空间。算法的时间复杂度是指A）执行算法程序所需要的时间 B）算法程序的长度C）算法执行过程中所需要的基 本运算次数 D）算法程序中的指令条数 算法的空间复杂度是指A）算法程序的长度 B）算法程序中的指令条数C）算法程序所占的存储空间 D）算法执行过程中所需要的

4、存储空间 第2节：数据结构的基本概念 大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。数据结构主要研究三个方面的问题： （1）数据的逻辑结构：数据集合众各数据元素间所固有的逻辑关系 （2）数据的存储结构（物理结构）：各数据元素在计算机中的存储关系 （3）对各种数据结构进行的运算。以上问题的主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占的计算机存储空间。1、什么是数据结构实例：无序表的顺序查找与有序表的对分查找35 16 78 85 43 29 3

5、3 21 54 4616 21 29 33 35 43 46 54 78 85数据元素在表中的表列 顺序对查找效率是有很 大的影响。1、什么是数据结构数据结构是指反映数据元素之间关系的数据元素集合的表示。学号姓名性别计算机 200501张三女80 200503李四男70 200513王五女50成绩单在上表中，查找给定学号的某学生的情况 时很方便的。但要查找计算机成绩在75分 以上的情况时，则需要从头到尾扫描。为 了便于查找成绩，可以进行重新组织数据结构是指相互有关联的数据元素的集 合1、什么是数据结构（1）数据结构的逻辑结构数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。 （2）数据的存

6、储结构数据的逻辑结构在计算机存储空间的存放形式称为数据的存储结构（也称数据的物理结构）下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储 结构 B）数据的逻辑结构属于线性结构，存 储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储 结构，且各种存储结构不影响数据处理的 效率 D）一个逻辑数据结构可以有多种存储 结构，且各种存储结构影响数据处理的效 率 数据的存储结构是指 A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储 方式 D）数据的逻辑结构中计算机中 的表示 2、数据结构的图形表示父亲儿子女儿d1d2d3名词解释： （1）结点 （2）前件结点 （3）

7、后件结点 （4）根结点 （5）终结点在数据结构中，与所使用 的计算机无关的数据结构 是（ ）A 逻辑 B 存储C 逻辑和存储D 物理2、数据结构的图形表示父亲儿子女儿d1d2d3名词解释： （1）结点 （2）前件结点 （3）后件结点 （4）根结点 （5）终结点春夏秋冬3、线性结构和非线性结构如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。根据数据元素之间前后件关系的复杂程度，将数据结构分为这两类什么是线性结构？线性必须满足以下二个条件： （1）有且只有一个根结点。（2）每个结点最多有一个前件，也最多一个后件。d1d2d3春夏秋冬在数据结构中，从逻辑上可以把数 据结构分成（

8、）A 动态结构和静态结构B 紧凑结构和非紧凑结构C 线性结构和非线性结构D 内部结构和外部结构第3节、线性表和顺序存储结构1、线性表的基本概念线性表由一组数据元素组成。线性表是一种线性结构。非空线性表有如下结构牲： （1）有且只有一个根结点（2）有且只有一个终结节点（3）除以上二结点外，每个结点有且只有一个前件，也有且只有一个后件。d1d2d3春夏秋冬姓名性别数学英语张三女7070李四男6590王五女68802、线性表的顺序存储结构线性表顺序存储具有如下特点 （1）线性表中所有元素所占的存储空间是连续的。 （2）数据元素在存储空间中是按逻辑顺序依次存放的。姓名数学英语张三7070李四6590王

9、五6880张三 70 70李四65 90王五68 80线性表的顺序存储结构是一种 随机存取的存储结构 。可随机 访问任意一个结点3、线性表的插入运算2597143、线性表的插入运算2597143、线性表的插入运算2597143、线性表的插入运算2597143、线性表的插入运算214597结论：如果在线性表的末尾进行，即 在第n个元素之后插入新元素，则只 要增加一个元素即可，不需要移动元 素如果要在线性表的第1个元素之前插 入，则需要移动表中所有的元素。在一般情况下，如果在第i个元素之 前进行，则第i个元素之后的所有元 素都必须移动。在平均情况下，需要移动表中一半的 元素。因此算法的平均时间复杂

10、度为O(n).4、线性表的删除运算2145974、线性表的删除运算25974、线性表的删除运算25974、线性表的删除运算25974、线性表的删除运算2597注意：如果为线性表开辟的存储空间 已经满了，不能再插入元素，否则会 造成“上溢”错误如果删除第n个元素，则不需要移动 表中的元素；如果删除第1个元素， 则需要移动表中所有的元素。在一般 情况下，若要删除第i个元素，则原来 第i个元素之后的所有元素都必须依次 往前移动一个位置。平均要移动表中一半的元素。算法的平均时间复杂度为O(n).总结：在线性表顺序存储的情况下，要插入或 删除一个元素，其效率都是很低的，特别是在 线性表比较大的情况下更为

11、突出，由于数据元 素的移动而消耗较多的处理时间。线性表的顺序存储结构对于小线性表或者元素 不常变动的线性表来说是合适的，因为顺序存 储结构比较简单。对线性表，在下列情况下应当采用链表表示的是（）A） 经常需要随机地存取元素B）经常需要进行插入和删除操作C）表中元素需要占据一片连续的存储空间D）表中元素的个数不变第4节：栈和队列1、栈及其运算栈是限定在一端进行插入与删除的线性表。入栈原则：先进后出，后进选出。5 9 7栈顶栈底6 41、栈及其运算栈是限定在一端进行插入与删除的线性表4 5 9 7栈顶栈底61、栈及其运算栈是限定在一端进行插入与删除的线性表6 4 5 9 7栈顶栈底1、栈及其运算栈

12、是限定在一端进行插入与删除的线性表6 4 5 9 7栈顶栈底1、栈及其运算栈是限定在一端进行插入与删除的线性表4 5 9 7栈顶栈底1、栈及其运算栈是限定在一端进行插入与删除的线性表5 9 7栈顶栈底1、栈及其运算栈是限定在一端进行插入与删除的线性表5 9 7栈顶栈底下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另 一端删除元素 下列关于栈的描述中错误的 是 A）栈是先进后出的线性表 B）栈只能顺序存储 C）栈具有记忆作用 D）对栈的插入与删除操

13、作 中，不需要改变栈底指针 实例1： 栈底至栈顶依次存放元素A、B、C、D， E在第五个元素E入栈前，栈中元素可以出栈，则 出栈序列可能是_。A. ABCEDB. DBCEAC. CDABED. DCBEAD C B A实例：若进栈序列为1，2，3，4，进栈过程中可以出栈，则下列 不可能的一个出栈序列是（ ）A） 1，4，3，2 B） 2，3，4，1C）3，1，4，2 D）3，4，2，1若进栈序列是1，2，3，4，假定进栈和出栈可以穿插进行，则可 能的出栈序列是（）A）2，4，1，3 B）3，1，4，2C）3，4，1，2 D）1，2，3，4以下不是栈的基本运算的是（）A） 删除栈顶元素 B）删

14、除栈底元素C）判断栈是否为空 D）将栈置为空栈若已知一个栈的进栈序列是1，2，3n，其输出序列是 p1,p2,p3pn,若p1=3,则p2为（ ）A）可能是2 B）一定是2C）可能是1 D）不确定2、队列及其运算什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则DCBA frontrear2、队列及其运算什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则EDCBA frontrear2、队列及其运算什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则FEDCB Af

15、rontrear2、队列及其运算什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则FEDCBfrontrear2、队列及其运算什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则FEDCfrontrear2、队列及其运算什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则FEDCfrontrear栈和队列的共同点是（ ）A）都是先进先出 B）都是后进先出C）只允许在端点处插入和删除元素D）没有共同点一个队列的入队序列是1，2，3，4， 则队列的输出序列是A）4，3，2，1 B）1，2，3，4C）1，4，3，2 D）3，2，4，12、队列及其运算什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则FEDfrontrear下列叙述中正确的是A）线性表是线性结构 B）栈与队列是非线性结构C）线性链表是非线性结构 D）二叉树是线性结构 下列关于队列的叙述中正确的是A）在队列中只能插入数据 B）在队列中只能删除数据C）队列是先进先出的线性表 D）队列是先进后出的线性表 按照“后进先出”原则组织数据的数据结构是A）队列 B）栈C）双向链表 D）二叉树第5节：线性