计算机二级C语言(公共基础知识基本数据结构与算法)

全国计算机等级考试二级

公共基础知识 基本数据结构与算法

公共基础知识基本要求 1. 掌握算法的基本概念。 2. 掌握基本数据结构及其操作。 3. 掌握基本排序和查找算法。 4. 掌握逐步求精的结构化程序设计方法。 5. 掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。 6. 掌握数据的基本知识，了解关系数据库的设计

一、数据结构与算法 二、程序设计基础 三、软件工程基础 四、数据库设计基础

数据结构与算法1. 算法的基本概念；算法复杂度的概念和意义(时间复杂度与空 间复杂度)。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图 形表示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、 中序和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法(交换类排序，选 择类排序，插入类排序)。

一.算法的基本概念 计算机解题的过程实际上是在实施某种算法，这

种算法称为计算机算法。就是指解题方案的准确 而完备的描述。 一个算法通常由两种基本要素组成：一是对数据 对象的运算和操作，二是算法的控制结构。 1.算法的基本特征：可行性，确定性，有穷性， 拥有足够的情报。 2.算法的基本要素：算法中对数据的运算和操作 、算法的控制结构。 3.算法设计的基本方法：列举法、归纳法、递推、 递归、减半递推技术、回溯法。 4.算法设计的要求：正确性、可读性、健壮性、 效率与低存储量需求

C 在计算机中，算法是指______。A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法

二.算法的复杂度

1.算法的时间复杂度：指执行算法所需要的计算 工作量 2.算法的空间复杂度：执行这个算法所需要的内 存空间 算法的复杂度的表示 时间复杂度：算法中基本操作重复执行的次数是 问题规模n的某个函数f(n),算法的时间量度记 作T(n)=O(f(n)) 表示随问题规模n的增大，算法执行时间的增长 率和f(n)的增长率相同，称作算法的渐近时间复 杂度，简称时间复杂度。 空间复杂度：算法所需存储空间的量度。记作： S(n)=O(f(n))

算法的时间复杂度是指______。

(C) A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数(C)

下面叙述正确的是______。

A. 算法的执

行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令(或 语句)的条数 C. 算法的有穷性是指算法必须能在执行有限个 步骤之后终止 D. 以上三种描述都不对

算法的空间复杂度是指______。 (D) A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间 算法一般都可以用哪几种控制结构组合而成 (D) ______。 A. 循环、分支、递归 B. 顺序、循环、嵌套 C. 循环、递归、选择 D. 顺序、选择、循环 算法的复杂度主要包括______复杂度和空间复 杂度。 答：时间

三.数据结构的定义

数据结构：相互之间存在一种或多种特定关系的

数据元素的集合 1.数据的逻辑结构：反映数据元素之间的关系的 数据元素集合的表示。数据的逻辑结构包括集合、 线形结构、树形结构和图形结构四种。 2.数据的存储结构：数据的逻辑结构在计算机存 储空间中的存放形式称为数据的物理结构，又称 存储结构。常用的存储结构有顺序、链接、索引 等存储结构。

数据的逻辑结构在计算机存储空间中的存放形式

称为数据的______。 答：存储结构

(B) 数据的存储结构是指______。

A. 数据所占的存储空间量 B. 数据的逻辑结构在计算机中的表示 C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据

四.数据结构的图形表示：

在数据结构中，没有前件的结点称为根结点；没 有后件的结点成为终端结点。插入和删除是对数 据结构的两种基本运算。还有查找、分类、合并、 分解、复制和修改等。 (1)集合：松散的关系。 (2)线性结构:一对一 (3)树形结构:一对多 (4)图状结构:多对多

五.线性结构和非线性结构

根据数据结构中各数据元素之间前后件关系的复 杂程度，一般将数据结构分为两大类型：线性结 构和非线性结构。 线性结构：非空数据结构满足：有且只有一个根 结点；每个结点最多有一个前件，最多只有一个 后件。 非线性结构：如果一个数据结构不是线性结构， 称之为非线性结构。 常见的线性结构：线性表、栈、队列 常见的非线性结构：树、图 注意：链表也属于线性表，所以也是线性结构

六.线性表的定义

线性表是n 个元素构成的有限序列(A1,A2, A3……)。表中的每一个数据元素，除了第一个 以外，有且只有一个前件。除了最后一个以外有 且只有一个后件。即线性表是一个空表，或可以 表示为(a1,a2,……an), 其中ai(I=1,2,……n) 是属于数据对象的元素，通常也称其为线性表中 的一个结点。 非空线性表有如下一些特征： (1)有且只有一个根结点a1,它无

前件； (2)有且只有一个终端结点an,它无后件； (3)除根结点与终端结点外，其他所有结点有 且只有一个前件，也有且只有一个后件。线性表 中结点的个数n称为线性表的长度。当n=0时称为 空表。

七.线性表的顺序存储结构

线性表的顺序表指的是用一组地址连续的存储单 元依次存储线性表的数据元素。 线性表的顺序存储结构具备如下两个基本特征： 1.线性表中的所有元素所占的存储空间是连续的； 2.线性表中各数据元素在存储空间中是按逻辑顺 序依次存放的。 即线性表逻辑上相邻、物理也相邻，则已知第一 个元素首地址和每个元素所占字节数，则可求出 任一个元素首地址。

顺序存储方法是把逻辑上相邻的结点存储在物理

位置______的存储单元中。 答：相邻

假设线性表的每个元素需占用K个存储单元，并以所占 的第一个单元的存储地址作为数据元素的存储位置。则 线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i 个数据元素的存储位置LOC(ai)之间满足下列关系: LOC(ai+1)=LOC(ai)+K LOC(ai)=LOC(a1)+(i-1)*K ① 其中，LOC(a1)是线性表的第一个数据元素a1的存储位 置，通常称做线性表的起始位置或基地址。 因为在顺序存储结构中，每个数据元素地址可以通过公 式①计算得到，所以线性表的顺序存储结构是随机存取 的存储结构。 在线性表的顺序存储结构下，可以对线性表做以下运算： 插入、删除、查找、排序、分解、合并、复制、逆转

八.顺序表的插入运算

线性表的插入运算是指在表的第I个位置上，插 入一个新结点x,使长度为n的线性表 (a1,a2 …ai…an)变成长度为n+1的线性表 (a1,a2…x,ai…an). 该算法的时间主要花费在循环的结点后移语句上， 执行次数是n-I+1。 当I=n+1,最好情况，时间复杂度o(1) 当I=1, 最 坏情况，时间复杂度o(n) 算法的平均时间复杂度为o(n)

九.顺序表的删除运算

线性表的删除运算是指在表的第I个位置上，删 除一个新结点x,使长度为n的线性表 (a1,a2 …ai…an)变成长度为n-1的线性表 (a1,a2…ai-1,ai+1…an). 当I=n,时间复杂度o(1),当I=1,时间复杂度o(n) , 平均时间复杂度为o(n)