全国计算机等级考试2级教程

章节摘录

版权页：   插图：   1.2.1什么是数据结构 计算机已被广泛用于数据处理。实际问题中的各数据元素之间总是相互关联的。所谓数据处理，是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。在数据处理领域中，建立数学模型有时并不十分重要，事实上，许多实际问题是无法表示成数学模型的。人们最感兴趣的是知道数据集合中各数据元素之间存在什么关系，应如何组织它们，即如何表示所需要处理的数据元素。 下面通过两个实例来说明对同一批数据用不同的表示方法后，对处理效率的影响。 例1.3无序表的顺序查找与有序表的对分查找。 图1.1是两个子表。从图中可以看出，在这两个子表中所存放的数据元素是相同的，但它们在表中存放的顺序是不同的。在图1.1（a）所示的表中，数据元素的存放顺序是没有规则的；而在图1.1（b）所示的表中，数据元素是按从小到大的顺序存放的。我们称前者为无序表，后者为有序表。 下面讨论在这两种表中进行查找的问题。 首先讨论在图1.1（a）所示的无序表中进行查找。由于在图1.1（a）表中数据元素的存放顺序没有一定的规则，因此，要在这个表中查找某个数时，只能从第一个元素开始，逐个将表中的元素与被查数进行比较，直到表中的某个元素与被查数相等（即查找成功）或者表中所有元素与被查数都进行了比较且都不相等（即查找失败）为止。这种查找方法称为顺序查找。显然，在顺序查找中，如果被查找数在表的前部，则需要比较的次数就少；但如果被查找数在表的后部，则需要比较的次数就多。特别是当被查找数刚好是表中的第一个元素时（如被查数为35），只需要比较一次就查找成功；但当被查数刚好是表中最后一个元素（如被查数为46）或表中根本就没有被查数时（如被查数为67），则需要与表中所有的元素进行比较，在这种情况下，当表很犬时，顺序查找是很费时间的。虽然顺序查找法的效率比较低，但由于图1.1（a）为无序表，没有更好的查找方法，只能用顺序查找。

内容概要

徐士良，清华大学电子工程系教授。曾担任全国高等院校计算机基础教育研究会理事、学术委员会副主任任，全国计算机等级考试委员会委员。至今已正式出版著作、教材40余部，多部教材被评为部级优秀教材一等奖、北京市高等教育精品教材、普通高等教育“十一五”国家级规划教材。

书籍目录

第1章 数据结构与算法

1.1 算法

1.1.1 算法的基本概念

1.1.2 算法复杂度

1.2 数据结构的基本概念

1.2.1 什么是数据结构

1.2.2 数据结构的图形表示

1.2.3 线性结构与非线性结构

1.3 线性表及其顺序存储结构

1.3.1 线性表的基本概念

1.3.2 线性表的顺序存储结构

1.3.3 顺序表的插入运算

1.3.4 顺序表的删俑

1.4 栈和队列

1.4.1 栈及其基本运算

1.4.2 队列及其基本运算

1.5 线性链表

1.5.1 线性链表的基本概念

1.5.2 线性链表的基本预案算

1.5.3 循环链表及其基本预案算

1.6 树与二叉树

1.6.1 树的基本概念

1.6.2 二叉树及其基本性质

1.6.3 二叉树的存储结构

1.6.4 二叉树的遍历

1.7 查找技术

1.7.1 顺序查找

1.7.2 二分法查找

1.8 排序技术

1.8.1 交换类排序法

1.8.2 插人类排序法

1.8.3 选择类排序法

习题1

第2章 程序设计基础

2.1 程序设计方法与风格

2.2 结构化程序设计

2.2.1 结构化程序设计的原则

2.2.2 结构化程序的基本结构与特点

2.2.3 结构化程序设计原则和方法的应用

2.3 面向对象的程序设计

2.3.1 关于面向对象方法

2.3.2 面向对象方法的基本概念

习题2

第3章 软件工程基础

3.1 软件工程与软件生命周期

3.1.1 软件定义与软件特点

3.1.2 软件危机与软件工程

3.1.3 软件工程过程与软件生命周期

3.1.4 软件工程的目标与原则

3.1.5 软件开发工具与软件开发环境

3.2 结构化分析方法

3.2.2 结构化分析方法

3.2.3 软件需求规格说明书

3.3 结构化设计方法

3.3.1 软件设计的基本概念

3.3.2 概要设计

3.3.3 详细设计

3.4 软件测试

3.4.1 软件测试的目的

3.4.2 软件测试的准则

3.4.3 软件测试技术与方法综述

3.4.4 软件测试的实施

3.5 程序的调试

3.5.1 基本概念

3.5.2 软件调试方法

习题3

第4章 数据库设计基础

4.1 数据库系统的基本概念

4.1.1 数据、数据库、数据库管理系统

4.1.2 数据库系统的发展

4.1.3 数据库系统的基本特点

4.1.4 数据库系统的内部结构体系

4.2 数据模型

4.2.1 数据模型的基本概念

4.2.2 E-R模型

4.2.3 层次模型

4.2.4 网状模型

4.2.5 关系模型

4.3 关系代数

4.4 数据库设计与管理

4.4.1 数据库设计概述

4.4.2 数据库设计的需求分析

4.4.3 数据库概念设计

4.4.4 数据库的逻辑设计

4.4.5 数据库的物理设计

4.4.6 数据库管理

习题4

附录1 全国计算机等级考试二级公共基础知识考试大纲（2013年版）

附录2 全国计算机等级考试二级公共基础知识样卷及参考答案

附录3 习题参考答案

编辑推荐

《全国计算机等级考试2级教程:公共基础知识(2013年版)》不仅是应试者必备的自学和辅导材料，也可以作为一般院校相应课程的教材或自学参考书。

作者简介

《全国计算机等级考试2级教程:公共基础知识(2013年版)》是根据教育部考试中心颁布的《全国计算机等级考试二级公共基础知识考试大纲（2013年版）》的要求，在2012年版基础上修订而成。主要内容包括：数据结构与算法，程序设计基础，软件工程基础，数据库设计基础。

---

 全国计算机等级考试2级教程下载

---