公共基础知识(删减版辅导班用).pdf

二级公共基础知识 孙勤红 刘粉香 沈凤仙 朱颖雯 朱颖雯2013  考试形式 u无纸化考试，无笔试考试 u一套试题分为：理论题和操作题（以VFP为例） 公共基础知识：10题，10分 理论题 相关语言题目：30题，30分 基本操作：18分 题型 操作题 简单应用：24分 综合应用：18分 朱颖雯2013  目录 v 第1章 数据结构与算法 v 第2章 程序设计基础 v 第3章 软件工程基础 v 第4章 数据库设计基础 朱颖雯2013  第1章 数据结构与算法 1.  概念:是指解题方案的准确而完整的描述。  可行性 确定性 1G=1024MB  2.  特征(4种)：  有穷性 1MB=1024KB  拥有足够的情报 1KB 8bit  算 3.  组成  对数据对象的运算和操作 法 算法的控制结构 ：   内存空间  ： 4.  方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。  ：是指执行算法所需要的计算工作量。 时间复杂度 5.  复杂度 空间复杂度 ：是指执行算法所需要的内存空间。 算法好坏的 注：时间复杂度和空间复杂度之间没有必然的联系 度量 分析算法的目的是：分析算法的效率以求改进。 朱颖雯2013  v 【真题解析】 v 【试题1】算法的时间复杂度是指(  ) (2010春)  A）算法的执行时间  B）算法所处理的数据量  C）算法程序中的语句或指令条数  D）算法在执行过程中所需要的基本 运算次数 v 解析：算法的时间复杂度，是指执行算法所需要的计算工作量，一般采用算法所 执行的基本运算次数来度量，是问题规模的函数。答案为D。 v 【试题2】算法的空间复杂度是指（ ）（2009年秋）。 v  A）算法在执行过程中所需要的计算机存储空间 v  B）算法所处理的数据量 v  C）算法程序中的语句或指令条数 v  D）算法在执行过程中所需要的临时工作单元数 v 解析： 答案 A。算法的空间复杂度是指执行算法所需要的内存空间,包括算法程 序所占空间,输入的初始数据所占空间和执行过程中所需要的额外空间。 朱颖雯2013  v 【试题3】算法的有穷性是指（ ） （2008年春） v  A）算法程序运行的时间是有限的