数据结构考点解析(最终版).ppt

数据结构 考点解析 湖北科技学院计算机学院 陈博 数据结构考点解析 概述 第一章知识点 第二章知识点 第三章知识点 第四章知识点 第五章知识点 第六章知识点 考试的要求 考试主要从两个方面进行考查：知识和技能。 知识方面 从数据结构的结构定义和使用，以及存储表示和操作的实现两个层次，系统地考查： 掌握常用的基本数据结构（包括顺序表、链接表、栈与队列、数组、二叉树、堆、树与森林、图、查找结构、索引结构、散列结构）及其不同的实现。 2) 掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法。 技能方面 系统地掌握基本数据结构的设计方法; 掌握选择结构的方法和算法设计的思考方式及技巧； 提高分析问题和解决问题的能力。 第一章知识点解析 本章“线性表”的知识点有 5 个： 线性表的定义和特点：由数据元素组成，惟一直接前驱与后继。 线性表的基本操作：查找、定位、遍历、插入、删除。 线性表的存储表示：顺序存储、链表存储。 循环链表和双向链表：定义和基本运算。 线性表的应用：掌握使用线性表基本操作实现应用算法 线性表的定义和特点 问题1. 如果一个元素集合中每个元素都有1个且仅有1个直接前驱和1个直接后继，它是线性表吗？ 解析：答案“否”，该元素集合是一个回路（环）。 引伸：循环链表是一个“环”，它符合线性表的定义吗？问题的关键是：线性表是逻辑结构，线性表和非线性表是从逻辑上划分的。而循环链表是存储结构，是线性表的一种特殊的表示，是线性链表的一种扩展。它在形态上有线性的特征，在行为上有线性表的循序访问的特点。 问题2. 如果一个元素集合有一个元素仅有 1 个直接后继而没有直接前驱，另一个元素仅有 1 个直接前驱而没有直接后继，其他每个元素都仅有 1 个直接前驱和 1 个直接后继，但其中各个元素可能数据类型不同，该元素集合是线性表吗？ 解析：答案“是”，它符合线性表的定义和特性，只要把元素定义为Union类型即可。因为线性表的定义只规定了元素间的关系及每个表元素是原子类型，并未规定每个表元素的类型必须相同。Union是一种等价类型，它允许不同类型数据共享同一存储空间，可保证每个表元素所占空间相同。 线性表的基本操作 问题3. 我们可以为线性表定义查找、插入、删除等操作吗？它们如何实现？ 解析：可以为线性表定义这些操作，也可以在程序中直接使用这些操作。但它们的实现与线性表选用何种存储结构有关。在定义了线性表的存储表示之后，必须为相关操作定义它们的实现代码。具体的线性表实例一定与某一存储表示相联系，因此，要使用相应的基于该存储结构实现的操作。 线性表的存储表示 问题4. 线性表的顺序存储表示是一维数组吗？ 解析：答案“否”，应是顺序表，其区别在顺序表中元素是相继连续存放的。而一维数组只能有两个操作“按下标存”“按下标取”，它不一定是相继存放，不适宜存储顺序的、连续的序列元素。 问题5. 想要以O(1)的时间代价存取第 i 个表元素，线性表应采用顺序表还是单链表？ 解析：“顺序表”，因为单链表只能顺序地逐个访问，顺序表可以直接访问第 i 个元素。 问题6. 为了统一空链表和非空链表的操作，简化链表的插入删除操作，需要给链表增加点什么？ 解析：“增加表头结点”。 问题7. 在何种场合选用顺序表？链表呢？ 解析：从时间角度来看，需要经常查看不需经常增删的场合使用顺序表，因它可直接存取，但增删要大量移动存储块；反之，选择链表，因它在增删元素时不需移动存储，修改指针即可，但只能顺序访问，存取速度慢。从空间角度来看，顺序表存储密度（有效存储/总存储）高，空间利用率好；链表存储密度较低，空间利用率差一些。 循环链表和双向链表 问题8. 想要以O(1)的时间代价把两个链表连接起来可采用何种链表结构？ 解析：“循环链表”，若设两个循环链表头指针为p和q，用r = p-link;p-link = q-link; q-link = r; 即可把这两个连接起来。 问题9. 想要判断一个带表头结点的循环链表L是否为空，应采用何种语句？ 解析： “L-link==L”。空表还需保留一个表头结点，它的下一个结点还是它自己。 问题10. 想要以O(1)的时间代价访问第 i 个表元素的直接前驱和／或直接后继，应采用何种链表结构？ 解析：“双向链表”。只要事先定位于该表结点，通过该结点的前驱指针和后继指针，直接能够找到该元素的直接前驱或直接后继。 第二章知识点解析 本章“栈、队列与数组”的知识点有 8 个： 栈和队列的定义及其特点 栈的存储表示及其基本运算的实现 队列的存储表示及其基本运算的实现 栈的应用 队列的应用 多维数组 特殊矩阵 稀疏矩阵 栈和队列的定义及其特点 问题1. 元素1, 2, 3, 4依次进栈，可能的出栈序