文档介绍：二级公共基础知识
考试形式
无纸化考试,无笔试考试
一套试题分为:理论题和操作题(以VFP为例)
题型
理论题
公共基础知识:10题,10分
相关语言题目:30题,30分
操作题
基本操作:18分
简单应用:24分
综合应用:18分
目录
第1章数据结构与算法
第2章程序设计基础
第3章软件工程基础
第4章数据库设计基础
第1章数据结构与算法
算法
1. 概念:是指解题方案的准确而完整的描述。
2. 特征(4种):
3. 组成
4. 方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。
5. 复杂度
可行性
确定性
有穷性
拥有足够的情报
对数据对象的运算和操作
算法的控制结构
:是指执行算法所需要的计算工作量。
:是指执行算法所需要的内存空间。
分析算法的目的是:分析算法的效率以求改进。
算法好坏的
度量
时间复杂度
空间复杂度
基本运算次数
:
:
内存空间
1G=1024MB
1MB=1024KB
1KB=8bit
注:时间复杂度和空间复杂度之间没有必然的联系
【真题解析】
【试题1】算法的时间复杂度是指(     ) (2010春) A)算法的执行时间        B)算法所处理的数据量 C)算法程序中的语句或指令条数    D)算法在执行过程中所需要的基本运算次数
解析:算法的时间复杂度,是指执行算法所需要的计算工作量,一般采用算法所执行的基本运算次数来度量,是问题规模的函数。答案为D。
【试题2】算法的空间复杂度是指(     )(2009年秋)。
A)算法在执行过程中所需要的计算机存储空间   
B)算法所处理的数据量
C)算法程序中的语句或指令条数             
D)算法在执行过程中所需要的临时工作单元数
解析: 答案 A。算法的空间复杂度是指执行算法所需要的内存空间,包括算法程序所占空间,输入的初始数据所占空间和执行过程中所需要的额外空间。
【试题3】算法的有穷性是指( )(2008年春)
A)算法程序运行的时间是有限的 B)算法程序所处理的数据是有限的
C)算法程序的长度是有限的 D)算法只能被有限的用户使用
解析:答案为A。算法具有四个特点或要求:确定性、有穷性、能行性、输出。确定性是指每一步运算应该执行何种操作必须是明确的;有穷性是指一个算法在执行有限步的操作后终止;能行性是指算法中有待实现的操作都是可以实现的;输出是指至少产生一个输出。
【试题4】下列叙述中正确的是( )(2007年春) A)算法的效率只与问题的规模有关,而与数据的存储结构无关 B)算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是一一对应的 D)算法的时间复杂度与空间复杂度一定相关
解析:答案为B。算法的效率不仅与问题的规模相关,采用不同的存储结构(顺序、链式)会影响算法的效率,所以A错。数据的逻辑结构有线性、树型、图形等,它们可以采用不同的存储结构,不存在一一对应关系,C错。衡量算法的两大指标时间和空间复杂度仅与算法本身相关,包括算法的思想、数据的存储结构、数据的输入等,D错。
【试题5】下列叙述中正确的是( ) 。(2006年秋) A)一个算法的空间复杂度大,则其空间复杂度也必定大 B)一个算法的空间复杂度大,则其时间复杂度必定小 C)一个算法的时间复杂度大,则其空间复杂度必定小 D)上述三种说法都不对
解析:答案为D。算法的时间和空间复杂度没有直接的关系,它们仅与算法本身相关。
【试题6】下列叙述中正确的是( )(2007年秋)
A)程序执行的效率与数据的存储结构密切相关
B)程序执行的效率只取决于程序的控制结构
C)程序执行的效率只取决于所处理的数据量
D)以上三种说法都不对
解析:答案为A。
【试题7】算法复杂度主要包括时间复杂度和复杂度。(2005年秋)
解析:答案为空间。
【试题8】问题处理方案的正确而完整的描述称为。(2005年春)
解析:答案为算法。
为什么学****数据结构?
———计算机已被广泛用于数据处理。
现实世界中的数据
计算机
存储
应如何组织和存储好?
数据结构
逻辑结构
②存储结构
(物理结构)
③运算
①表示数据元素的信息;
②表示数据元素的前后件关系。
顺序存储结构:存储空间必须连续,且元素之间
一定要有前后件的关系。
链式存储结构:存储空间不一定连续,且各元素
的存储顺序是任意的。
线性表
注:Ⅰ数据的逻辑结构在计算机中的存放形式称为存储结构
Ⅱ一种数据的逻辑结构可以有多种存储结构
Ⅲ每种存储结构其处理数据的效率不同
逻辑结构
①表示数据元素的信息;
②表示数据元素的前后件关系。
举例说明:
春
夏
秋
冬