文档介绍：全国计算机等级考试二级
公共基础知识
基本数据结构与算法
公共基础知识
基本要求 1. 掌握算法的基本概念。 2. 掌握基本数据结构及其操作。 3. 掌握基本排序和查找算法。 4. 掌握逐步求精的结构化程序设计方法。 5. 掌握软件工程的基本方法,具有初步应用相关技术进行软件开发的能力。 6. 掌握数据的基本知识,了解关系数据库的设计
一、数据结构与算法
二、程序设计基础
三、软件工程基础
四、数据库设计基础
数据结构与算法
1. 算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。 2. 数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。 3. 线性表的定义;线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义;栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序)。
计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。就是指解题方案的准确而完备的描述。
一个算法通常由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构。
:可行性,确定性,有穷性,拥有足够的情报。 :算法中对数据的运算和操作
、算法的控制结构。 :列举法、归纳法、递推、递归、减半递推技术、回溯法。 :正确性、可读性、健壮性、效率与低存储量需求
在计算机中,算法是指______。 A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法
C
:指执行算法所需要的计算工作量 :执行这个算法所需要的内存空间
算法的复杂度的表示
时间复杂度:算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(f(n))
表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。
空间复杂度:算法所需存储空间的量度。记作:S(n)=O(f(n))
算法的时间复杂度是指______。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数
下面叙述正确的是______。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令(或语句)的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对
(C)
(C)
算法的空间复杂度是指______。 A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间
算法一般都可以用哪几种控制结构组合而成______。 A. 循环、分支、递归 B. 顺序、循环、嵌套 C. 循环、递归、选择 D. 顺序、选择、循环
算法的复杂度主要包括______复杂度和空间复杂度。
(D)
(D)
答:时间
数据结构:相互之间存在一种或多种特定关系的数据元素的集合
:反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。 :数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构,又称存储结构。常用的存储结构有顺序、链接、索引等存储结构。
数据的逻辑结构在计算机存储空间中的存放形式称为数据的______。
答:存储结构