全国计算机等级考试二级公共基础知识

全国计算机等级考试National Computer Rank Examination

+

全国计算机等级考试National Computer Rank Examination

第一部分 公共基础知识

二级公共基础知识考试内容

全国计算机等级考试National Computer Rank Examination

数据结构和算法 程 序 设 计 基 础 软 件 工 程

数据库设计基础

全国计算机等级考试

二级公共基础知识

二级公共基础知识考试方式

全国计算机等级考试National Computer Rank Examination

1、二级公共基础知识不单独考试，与其他二 级科目组合在一起，作为二级科目考核内容的 一部分。公共基础部分占全卷的20分。 2、公共基础知识考查方式为选择题共20道。

全国计算机等级考试

二级公共基础知识

二级公共基础知识学习方法

全国计算机等级考试National Computer Rank Examination

理解基本概念

多做练习 适当记忆一些名词 与所学程序设计语言结合起来理解

全国计算机等级考试

二级公共基础知识

第一章 数据结构和算法

本章知识要点算法的定义 算法 算法的特征

全国计算机等级考试National Computer Rank Examination

算法的基本要素算法复杂度 数据结构的定义 逻辑结构 和 物理结构 数据结构 线性结构 和 非线性结构顺序表、链表、堆栈 队列、循环队列、树全国计算机等级考试 二级公共基础知识 7

一、算法

全国计算机等级考试National Computer Rank Examination

算法是解决方案(一系列步骤)的准确而完整的描述。算法不等于程序，也不等于计算方法。

算法的特性： (1)有穷性：算法必须在有限的次数内完成。 (2)确定性：算法的每一步必须是明确的。 (3)可行性：算法的每一步必须是可以实现的。 (4)拥有足够的情报：算法必须有一定的输入和输出。

全国计算机等级考试

二级公共基础知识

一、算法

全国计算机等级考试National Computer Rank Examination

算法的基本要素： (1)对数据对象的运算和操作： A .算术运算 B .逻辑运算 C .关系运算 D .数据传输 (2)算法的控制结构： A .顺序结构 B .选择结构 C .循环结构

全国计算机等级考试

二级公共基础知识

全国计算机等级考试

一、算法

National Computer Rank Examination

算法的复杂度：衡量算法优劣的量。 (1)时间复杂度：算法的时间耗费。 A .算法中基本操作重复执行次数和算法执行时间 同步增长，称作算法的时间复杂度。 B .算法中基本操作重复执行次数和问题规模有关， 是问题规模的函数。 C .算法的时间复杂度是指执行算法所需要的计算工 作量。 (2)空间复杂度：执行算法所需要的内存空间。

全国计算机等级考试

二级公共基础知识

全国计

算机等级考试

一、算法例题 1、算法的基本特征是可行性、确定性、

National Computer Rank Examination

有穷性

和拥有足够的情报。

2、算法具有4个特性，以下选项中不属于算法特性的是( B ) A) 有穷性 B) 简洁性 C) 可行性 D) 确定性3、算法的时间复杂度是指( B) 算法程序的长度 C) 算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数 4、算法的空间复杂度是指( A) 算法程序的长度 C) 算法程序所占的存储空间全国计算机等级考试

C )

A) 执行算法程序所需要的时间

D ) B) 算法程序中的指令条数 D) 执行过程中所需要的存储空间11

二级公共基础知识

一、算法5、在计算机中，算法是指( A) 加工方法 C) 排序方法

全国计算机等级考试National Computer Rank Examination

B ) B) 解题方案的准确而完整的描述 D) 查询方法

6、下列叙述中正确的是(

B ) A) 算法的效率只与问题的规模有关，而与数据的存储结构无关。B) 算法的时间复杂度是指执行算法所需要的计算工作量。 C) 数据的逻辑结构与存储结构是一一对应的。 D) 算法的时间复杂度与空间复杂度一定相关。

全国计算机等级考试

二级公共基础知识

二、数据结构

全国计算机等级考试National Computer Rank Examination

数据结构是相互之间存在一种或多种特定关系的数据元 素的集合。

数据数据结构主要研究两方面的问题： (1)数据本身。 (2)数据之间的前后件关系。 数据本身

结构

数据之间的 前后件关系

数据结构表示为：DS={D,S} 例：D={春，夏，秋，冬} S={(春,夏),(夏,秋),(秋,冬),(冬,春)}全国计算机等级考试 二级公共基础知识 13

全国计算机等级考试

二、数据结构数据的结构分为：

National Computer Rank Examination

(1)物理结构：数据在计算机存储介质中真正存储的结构，

也被称为“存储结构”(2)逻辑结构：人们所理解的数据之间的结构(即“关 系”),可以用图示的方法绘画出来的数据之间的结构。 例：一个班由35名同学，他们的座位牌号就是物理结构， 一次考试的排名是逻辑结构。 注意：逻辑结构和物理结构没有必然的联系，也不一定是 一一对应的。全国计算机等级考试 二级公共基础知识 14

全国计算机等级考试

二、数据结构数据的结构分为： (1)线性结构：

National Computer Rank Examination

非空数据结构同时满足以下两个条件就是线性结构：A .有且仅有一个根结点； B .除头结点和尾结点外，任何结点有且仅有一个前件 和一个后件。 (2)非线性结构：除了线性结构都是非线性结构。

全国计算机等级考试

二级公共基础知识

全国计算机等级考试

二、数

据结构

National Computer Rank Examination

全国计算机等级考试二级公共基础知识要求掌握的数据结构共有以下六种：

线性表线 性 结 构 堆栈 队列

物理结构和逻辑结构相同 物理结构和逻辑结构相同

物理结构和逻辑结构相同物理结构和逻辑结构相同 物理结构和逻辑结构不相同

循环队列 线性链表

非线性结构 树和二叉树 物理结构和逻辑结构不相同

全国计算机等级考试

二级公共基础知识