《计算机2级C语言笔试部分分为数据结构软件工程数据库面向程序设计很详细92076》由会员分享，可在线阅读，更多相关《计算机2级C语言笔试部分分为数据结构软件工程数据库面向程序设计很详细92076（28页珍藏版）》请在金锄头文库上搜索。
1、路就在你脚下，只要走，就能到达远方。 二级C语言公共基础知识之数据结构考点1算法的复杂度1 .算法的基本概念算法的基本特征：可行性、确定性、有穷性、输入（可为0）、输出（不能为0）2 算法复杂度包括时间复杂度和空间复杂度名称描述时间复杂度是指执行算法所需要的计算工作量空间复杂度是指执行这个算法所需要的内存空间考点2逻辑结构和存储结构1 逻辑结构2 存储结构考点3线性结构和非线性结构根据数据结构中各数据元素之间前后件关系的复杂程度一般将数据结构分为两大类型：线性结构和非线性结构如果一个非空的数据结构满足下列两个条件：（1 ）有且只有一个根结点；（2）每一个结点最多有一个前件也最多有一个后件则称该
2、数据结构为线性结构线性结构又称线性表在一个线性结构中插入或删除任何一个结点后还应是线性结构栈、队列、串等都线性结构如果一个数据结构不是线性结构则称之为非线性结构数组、广义表、树和图等数据结构都是非线性结构考点4栈1 .栈的基本概念栈（stack ）是一种特殊的线性表是限定只在一端进行插入和删除的线性表在栈中一端是封闭的既不允许进行插入元素也不允许删除元素；另一端是开口的允许插入和删除元素通常称插入、删除的这一端为栈顶另一端为栈底当表中没有元素时称为空栈栈顶元素总是后被插入的元素从而也是最先被删除的元素；栈底元素总是最先被插入的元素从而也是最后才能被删除的元素先进后出”或”后进先出”2 栈的顺序
3、存储及其运算栈的基本运算有三种：入栈、退栈和读栈顶元素（1）入栈运算：入栈运算是指在栈顶位置插入一个新元素（2 ）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量（3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量 考点5队列1. 队列的基本概念队列是只允许在一端进行删除在另一端进行插入的顺序表通常将允许删除的这一端称为队头允许插入的这一端称为队尾当表中没有元素时称为空队列队列的修改是依照先进先出的原则进行的因此队列也称为先进先出的线性表或者后进后出的线性表例如：火车进遂道最先进遂道的是火车头最后是火车尾而火车出遂道的时候也是火车头先出最后出的是火车尾若有队列：Q = （ q1q2q
4、n）那么q1为队头元素（排头元素）qn为队尾元素队列中的元素是按照 q1q2qn的顺序进入的退出队列也只能按照这个次序依次退出即只有在q1q2qn-1都退队之后qn才能退出队列因最先进入队列的元素将最先出队所以队列具有先进先出的特性体现先来先服务”的原则队头元素q1是最先被插入的元素也是最先被删除的元素队尾元素qn是最后被插入的元素也是最后被删除的元素先进先出”入队运算为往队列队尾插入一个数据元素退队运算为从队列的队头删除一个数据元素考点6链表在链式存储方式中要求每个结点由两部分组成：一部分用于存放数据元素值 称为数据域另一部分用于存放指针称为指针域其中指针用于指向该结点的前一个或后一个结点（
5、即前件或后件） 链式存储方式既可用于表示线性结构也可用于表示非线性结构（1 ）线性链表线性表的链式存储结构称为线性链表在某些使用中对线性链表中的每个结点设置两个指针一个称为左指针用以指向其前件结点；另一个称为右指针用以指向其后件结点这样的表称为双向链表在线性链表中各数据元素结点的存储空间可以是不连续的且各数据元素的存储顺序和逻辑顺序可以不一致在线性链表中进行插入和删除 不需要移动链表中的元素（2 ）带链的栈栈也是线性表也可以采用链式存储结构带链的栈可以用来收集计算机存储空间中所有空闲的存储结点 这种带链的栈称为可利用栈考点7二叉树及其基本性质1、二叉树及其基本概念二叉树是一种很有用的非线性结构
6、具有以下两个特点： 非空二叉树只有一个根结点； 每一个结点最多有两棵子树且分别称为该结点的左子树和右子树在二叉树中每一个结点的度最大为 2即所有子树（左子树或右子树）也均为二叉树 另外二叉树中的每个结点的子树被明显地分为左子树和右子树 在二叉树中一个结点可以只有左子树而没有右子树也可以只有右子树而没有左子树当一个结点既没有左子树也没有右子树时该结点即为叶子结点父结点（根）在树结构中每一个结点只有一个前件称为父结点没有前件的结点只有一个称为树的根结点简称树的根例如在图1-1中结点A是树的根结点子结点和叶子结点在树结构中每一个结点可以有多个后件称为该结点的子结点没有后件的结点称为叶子结点例如在图1
7、-1中结点DEF均为叶子结点度在树结构中一个结点所拥有的后件的个数称为该结点的度所有结点中最大的度称为树的度例如在图1-1中根结点A和结点B的度为2结点C的度为1叶子结点DEF的度为0所以该树的度为2深度定义一棵树的根结点所在的层次为1其他结点所在的层次等于它的父结点所在的层次加1树的最大层次称为树的深度例如在图1-1中根结点A在第1层结点BC在第2层结点DEF在第3层该树的深度为3子树在树中以某结点的一个子结点为根构成的树称为该结点的一棵子树2、二叉树基本性质二叉树具有以下几个性质：性质1:在二叉树的第 k层上最多有2k-1 （k 1 ）个结点；性质2：深度为m的二叉树最多有2m-1个结点；
8、性质3:在任意一棵二叉树中度为0的结点（即叶子结点）总是比度为 2的结点多一个性质4：具有n个结点的二叉树 其深度至少为Iog2n +1 其中Iog2n 表示取Iog2n的整数部分3、满二叉树和完全二叉树满二叉树是指这样的一种二叉树：除最后一层外每一层上的所有结点都有两个子结点在满二叉树中每一层上的结点数都达到最大值即在满二叉树的第 k层上有2k-1个结点且深度为m的满二叉树有2m- 1个结点 完全二叉树是指这样的二叉树：除最后一层外 每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点 对于完全二叉树来说叶子结点只可能在层次最大的两层上出现：对于任何一个结点 若其右分支下的子孙结点
9、的最大层次为p则其左分支下的子孙结点的最大层次或为p或为p+1完全二叉树具有以下两个性质：性质5:具有n个结点的完全二叉树的深度为Iog2n +1性质6:设完全二叉树共有 n个结点如果从根结点开始 按层次（每一层从左到右）用自然数 12n给结点进行编号 则对于编号为k (k=12 n)的结点有以下结论： 若k=1则该结点为根结点它没有父结点；若 k1则该结点的父结点编号为INT( k/2 ) 若2kw n则编号为k的结点的左子结点编号为 2k;否则该结点无左子结点(显然也没有右子结点) 若2k+1w n则编号为k的结点的右子结点编号为 2k+1 ;否则该结点无右子结点考点8二叉树的遍历在遍历二
10、叉树的过程中一般先遍历左子树再遍历右子树在先左后右的原则下根据访问根结点的次序二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历(1) 前序遍历：先访问根结点、然后遍历左子树最后遍历右子树；并且在遍历左、右子树时仍然先访问根结点然后遍历左子树最后遍历右子树ABDECF(2) 中序遍历：先遍历左子树、然后访问根结点最后遍历右子树；并且在遍历左、右子树时仍然先遍历左子树然后访问根结点最后遍历右子树DBEAF（3）后序遍历：先遍历左子树、然后遍历右子树最后访问根结点；并且在遍历左、右子树时仍然先遍历左子树然后遍历右子树最后访问根结点DEBFCA考点9顺序查找查找是指在一个给定的数据结构中查找某个指定
11、的元素从线性表的第一个元素开始依次将线性表中的元素和被查找的元素相比较若相等则表示查找成功；若线性表中所有的元素都和被查找元素进行了比较但都不相等 则表示查找失败例如在一维数组21462499577786中查找数据元素98首先从第1个元素21开始进行比较和要查找的数据不相等接着和第2个元素46进行比较以此类推当进行到和第4个元素比较时它们相等所以查找成功如果查找数据元素 100则整个线性表扫描完毕仍未找到和100相等的元素表示线性表中没有要查找的元素在下列两种情况下也只能采用顺序查找：（1）如果线性表为无序表则不管是顺序存储结构还是链式存储结构只能用顺序查找（2）即使是有序线性表如果采用链式存
12、储结构也只能用顺序查找考点10二分法查找二分法查找0也称拆半查找是一种高效的查找方法能使用二分法查找的线性表必须满足两个条件：用顺序存储结构；线性表是有序表在本书中为了简化问题而更方便讨论有序是特指元素按非递减排列即从小到大排列但允许相邻元素相等下一节排序中有序的含义也是如此顺序查找法每一次比较只将查找范围减少1而二分法查找每比较一次可将查找范围减少为原来的一半效率大大提高对于长度为n的有序线性表在最坏情况下二分法查找只需比较Iog2n次而顺序查找需要比较 n次考点11排序冒泡排序法和快速排序法都属于交换类排序法（1）冒泡排序法首先从表头开始往后扫描线性表逐次比较相邻两个元素的大小若前面的元素
13、大于后面的元素则将它们互换不断地将两个相邻元素中的大者往后移动最后最大者到了线性表的最后然后从后到前扫描剩下的线性表逐次比较相邻两个元素的大小若后面的元素小于前面的元素则将它们互换不断地将两个相邻元素中的小者往前移动最后最小者到了线性表的最前面对剩下的线性表重复上述过程直到剩下的线性表变空为止此时已经排好序在最坏的情况下冒泡排序需要比较次数为 n (n 1) /2(2) 快速排序法任取待排序序列中的某个元素作为基准(一般取第一个元素)通过一趟排序将待排元素分为左右两个子序列左子序列元素的排序码均小于或等于基准元素的排序码右子序列的排序码则大于基准元素的排序码然后分别对两个子序列继续进行排序直至
14、整个序列有序二级C语言公共基础知识之软件工程考点1软件工程基本概念1 .软件定义和软件特点软件指的是计算机系统中和硬件相互依存的另一部分包括程序、数据和相关文档的完整集合程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令 序列数据是使程序能正常操纵信息的数据结构文档是和程序的开发、维护和使用有关的图文资料可见软件由两部分组成：(1) 机器可执行的程序和数据；(2 )机器不可执行的和软件开发、运行、维护、使用等有关的文档根据使用目标的不同软件可分使用软件、系统软件和支撑软件(或工具软件)名称描述使用软件为解决特定领域的使用而开发的软件系统软件计算机管理自身资源提高计算机使用效率并为计算机用户提供各
