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

《计算机二级考试公共基础知识》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机等级考试公共基础知识数计学院卫春芳计算机二级考试公共基础知识大纲数据结构与算法程序设计基础软件工程基础数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30％，是一个不小的比例。第2页计算机二级考试公共基础知识试卷分析章节考试时间数据结构程序设软件工数据库设计基础程基础计基础与算法2007年4月2007年9月2008年4月2008年9月2009年3月2009年9月2010年3月10分12分10分10分10分10分10分2分4分2分2分2分2分0分10分8分8分8分8分8分10分8分6分10分1

2、0分10分10分10分第3页一、基本数据结构与算法算法⒈算法的基本概念2.算法复杂2.算法复杂度的概念和意义数据结构⒈数据结构的概念⒉线性表⒊栈和队列⒋树与二叉树⒌查找技术⒍排序技术对于等级考试，这个部分的考核重点主要在对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概重点主要遍历、），还有排序和查找考试中也经常会涉及到二叉树遍历结点），还有排序和查找考试中也经常会涉及到。44念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。第4页⒈算法的基本概念算法的定义算法是程序设计的核心对解题方案准确而完整的描述称为算法。对解题方案准确而完整的描述称为

3、算法。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，定义明确的规则。通俗点说，就是计算机解题的过计算的方法)在这个过程中，程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(思路(推理实现的算法)还是编写程序(操作实现的算都是在实施某种算法。法)，都是在实施某种算法。个数从大到小进行排序。例：n个数从大到小进行排序。个数从大到小进行排序常用的有冒泡排序、选择排序等。有多种排序方法，常用的有冒泡排序、选择排序等。第5页2.算法的基本特征一个算法应该具有以下五个重要的特征：一个算法应该具有以下五个重要的特征：有穷性确

4、定性输入输出可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成第6页3.算法的表示一个算法的表示需要使用一些语言形式。一个算法的表示需要使用一些语言形式。传统的算法图形法，如“流程图”和N-S图图形法，传统的算法图形法流程图”图目前常用的方法使用伪码描述算法。使用伪码描述算法。目前常用的方法使用伪码描述算

5、法算法与计算机程序算法是一组逻辑步骤算法是一组逻辑步骤程序——用计算机语言描述的算法程序用计算机语言描述的算法问题：输入园的半径，计算园的面积INPUTrS=3.14*r*rPTINTS开始输入R输入RS=3.14*R*R44输出S输出S结束第7页算法举例：个数排序算法举例：n个数排序冒泡排序的方法：冒泡排序的方法：1.扫描整个线性表，逐次对扫描整个线性表，扫描整个线性表相邻的两个元素进行比较，相邻的两个元素进行比较，若为逆序，则交换；若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后；2.除最后一个元素，对剩余除最后一个元素，除最后一个元素的元素重复上述

6、过程，的元素重复上述过程，将次大的数排到表的倒数第二个位置；位置；3.重复上述过程；重复上述过程；重复上述过程对于长度为n的线性表，对于长度为的线性表，冒泡的线性表排序需要对表扫描n-1遍。排序需要对表扫描遍第8页4.算法的两个基本要素：算法的两个基本要素：一是对数据对象的运算和操作；二是算法的控制结构。基本运算和操作算术运算关系运算逻辑运算数据传输控制结构顺序选择循环算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法第9页5.算法评价评价一个算法优劣的主要标准是算法的执行效率和存储需求：评价一个算法优劣的主要标准是算法的执行效率和存储需求：时间复

7、杂度：执行这个算法所需要的计算工作量时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度：执行这个算法所需要的内存空间空间复杂度：执行这个算法所需要的内存空间算法在执行过程中临时占用的存储空间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积简单操作的次数的乘积。中进行简单操作的次数的乘积。44一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用

8、一个算法在