二级-公共基础知识之数据结构与算法篇.ppt

《二级-公共基础知识之数据结构与算法篇.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机二级考试C语言公共基础知识之数据结构与算法篇2007年二级C考试大纲－公共基础知识(一)基本要求 1.掌握算法的基本概念。 2.掌握基本数据结构及其操作。 3.掌握基本排序和查找算法。 4.掌握逐步求精的结构化程序设计方法。 5.掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。 6.掌握数据库的基本知识，了解关系数据库的设计。1.数据结构与算法  (1).算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。  (2).数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示(3).

2、线性结构与非线性结构的概念  (4).线性表的定义；线性表的顺序存储结构及其插入与删除运算。(5).栈和队列的定义；栈和队列的顺序存储结构及其基本运算。(6).线性单链表、双向链表与循环链表的结构及其基本运算。(7).树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。(8).顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。(二)考试内容2.程序设计基础  (1).程序设计方法与风格。  (2).结构化程序设计。  (3).面向对象的程序设计方法，对象，方法，属性及继承与多态性。3.

3、软件工程基础  (1).软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。  (2).结构化分析方法，数据流图，数据字典，软件需求规格说明书。  (3).结构化设计方法，总体设计与详细设计。  (4).软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。  (5).程序的调试，静态调试与动态调试。4.数据库设计基础  (1).数据库的基本概念：数据库，数据库管理系统，数据库系统。  (2).数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。  (3).关系代

4、数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。  (4).数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。5.考试方式(1)公共基础的考试方式为笔试，与C语言（VB、VF、Java、Access、VC++）的笔试部分合为一张试卷。公共基础部分全卷的30分。(2)公共基础知识有10道选择题和5道填空题。一.数据结构与算法本章节主要考查算法的基本概念、基本的数据结构及其基本操作、查找和排序算法。本章的内容在历次试题中所占的比例约为11.2%，都是以选择题和填空题的形式出现的。算法的基本概念、数据结

5、构的定义、栈和树几乎是每次必考的知识点；查找和排序基本上每次有一道试题；线性表、队列和线性链表很少单独出题，但经常与其它知识点结合出题。算法是对一个问题求解步骤的一种描述，是求解问题的方法，它是指令的有限序列，其中每条指令表示一个或者多个操作。一般来说，一个算法具有以下5个主要的特征。    （1）有穷性：一个算法（对任何合法的输入）在执行有穷步后能够结束，并且在有限的时间内完成。    （2）确定性：算法中的每一步都有确切的含义。    （3）可行性：算法中的操作能够用已经实现的基本运算执行有限次来实现。    （4）输入：一个

6、算法有零个或者多个输入，零个输入就是算法本身缺定了初始条件。    （5）输出：一个算法有一个或者多个输出，以反映出数据加工的结果。1算法算法的基本要素：（1）是对数据对象的运算和操作；基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。（2）是算法的控制结构。算法的控制结构：顺序结构、选择结构、循环结构。算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。（1）算法时间复杂度是指执行算法所需要的计算工作量。（2）算法空间复杂度是指执行这个算法所需要的内存空间。2数

7、据结构的基本概念数据结构研究的三个方面：数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含：（1）表示数据元素的信息D；（2）表示各数据元素之间的前后件关系R。B＝（D，R）其中B为数据结构数据的存储结构有顺序、链接、索引等。线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。（3）在一个线性结构中插入或删除任何一个节点后还是线性结

8、构非线性结构：不满足线性结构条件的数据结构。3线性表及其顺序存储结构线性表的基本概念线性表是n个元素构成的有限序列（A1，A2，A3……）。表中的每一个数据元素，除了第一个以外，有且只有一个前