二级算法是什么意思

① 计算机二级c语言知识点

2017计算机二级c语言知识点精选

计算机二级C语言考试内容是什么?为帮助大家更好备考3月计算机考试，我为大家分享计算机C语言二级考试知识点如下：

第一章 数据结构与算法

1.1 算法

1.算法的基本概念

(1) 概念：算法是指一系列解决问题的清晰指令。

(2) 4个基本特征：可行性、确定性、有穷性、拥有足够的情报。

(3) 两种基本要素：对数据对象的运算和操作、算法的控制结构(运算和操作时问的顺序)。

(4) 设计的基本方法：列举法、归纳法、递推法、递归法、减半递推技术和回溯法。

2.算法的复杂度

(1) 算法的时间复杂度：执行算法所需要的计算工作量。

(2) 算法的空间复杂度：执行算法所需的内存空间。

1.2 数据结构的基本概念

数据结构指相互有关联的数据元素的集合，即数据的组织形式。其中逻辑结构反映数据元素之间逻辑关系;存储结构为数据的逻辑结构在计算机存储空间中的存放形式，有顺序存储、链式存储、索引存储和散列存储4种方式。

数据结构按各元素之间前后件关系的复杂度可划分为：

(1) 线性结构：有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构。

(2) 非线性结构：不满足线性结构的数据结构。

1.3 线性表及其顺序存储结构

1.线性表的基本概念

线性结构又称线性表，线性表是最简单也是最常用的一种数据结构。

2.线性表的顺序存储结构

元素所占的存储空间必须连续。

元素在存储空间的位置是按逻辑顺序存放的。

3.线性表的插入运算

在第i个元素之前插入一个新元素的步骤如下：

步骤一：把原来第n个节点至第i个节点依次往后移一个元素位置。

步骤二：把新节点放在第i个位置上。

步骤三：修正线性表的节点个数。

在最坏情况下，即插入元素在第一个位置，线性表中所有元素均需要移动。

4.线性表的删除运算

删除第i个位置的元素的步骤如下：

步骤一：把第i个元素之后不包括第i个元素的n-i个元素依次前移一个位置;

步骤二：修正线性表的结点个数。

1.4 栈和队列

1.栈及其基本运算

(1) 基本概念：栈是一种特殊的线性表，其插入运算与删除运算都只在线性表的一端进行，也被称为“先进后出”表或“后进先出”表。

栈顶：允许插入与删除的一端。

栈底：栈顶的另一端。

空栈：栈中没有元素的栈。

(2) 特点。

栈顶元素是最后插入和最早被删除的元素。

栈底元素是最早插入和最后被删除的元素。

栈有记忆作用。

在顺序存储结构下，栈的插入和删除运算不需移动表中其他数据元素。

栈顶指针top动态反映了栈中元素的变化情况

(3) 顺序存储和运算：入栈运算、退栈运算和读栈顶运算。

2.队列及其基本运算

(1) 基本概念：队列是指允许在一端进行插入，在另一端进行删除的线性表，又称“先进先出”的线性表。

队尾：允许插入的一端，用尾指针指向队尾元素。

排头：允许删除的一端，用头指针指向头元素的前一位置。

(2) 循环队列及其运算。

所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。

入队运算是指在循环队列的队尾加入一个新元素。

当循环队列非空(s=1)且队尾指针等于队头指针时，说明循环队列已满，不能进行人队运算，这种情况称为“上溢”。

退队运算是指在循环队列的队头位置退出一个元素并赋给指定的变量。首先将队头指针进一，然后将排头指针指向的元素赋给指定的变量。当循环队列为空(s=0)时，不能进行退队运算，这种情况称为“下溢”。

1.5 线性链表

在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。

在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域;另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。

1.6 树和二叉树

1.树的基本概念

树是简单的非线性结构，树中有且仅有一个没有前驱的节点称为“根”，其余节点分成m个互不相交的有限集合T1，T2，…，T}mm，每个集合又是一棵树，称T1，T2，…，T}mm为根结点的子树。

父节点：每一个节点只有一个前件，无前件的节点只有一个，称为树的根结点(简称树的根)。

子节点：每～个节点可以后多个后件，无后件的节点称为叶子节点。

树的度：所有节点最大的度。

树的深度：树的最大层次。

2.二叉树的定义及其基本性质

(1) 二叉树的定义：二叉树是一种非线性结构，是有限的节点集合，该集合为空(空二叉树)或由一个根节点及两棵互不相交的左右二叉子树组成。可分为满二叉树和完全二叉树，其中满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。二叉树具有如下两个特点：

二叉树可为空，空的二叉树无节点，非空二叉树有且只有一个根结点;

每个节点最多可有两棵子树，称为左子树和右子树。

(2) 二叉树的基本性质。

性质1：在二叉树的第k层上至多有2k-1个结点(k≥1)。

性质2：深度为m的二叉树至多有2m-1个结点。

性质3：对任何一棵二叉树，度为0的结点(即叶子结点)总是比度为2的结点多一个。

性质4：具有n个结点的完全二叉树的深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。

3.满二叉树与完全二叉树

(1) 满二叉树：满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。满二叉树在其第i层上有2i-1个结点。

从上面满二叉树定义可知，二叉树的每一层上的结点数必须都达到最大，否则就不是满二叉树。深度为m的满二叉树有2m-1个结点。

(2) 完全二叉树：完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。

如果—棵具有n个结点的深度为k的二叉树，它的每—个结点都与深度为k的满二叉树中编号为1～n的结点——对应。

3.二叉树的存储结构

二叉树通常采用链式存储结构，存储节点由数据域和指针域(左指针域和右指针域)组成。二叉树的链式存储结构也称二叉链表，对满二叉树和完全二叉树可按层次进行顺序存储。

4.二叉树的遍历

二叉树的遍历是指不重复地访问二叉树中所有节点，主要指非空二叉树，对于空二叉树则结束返回。二叉树的遍历包括前序遍历、中序遍历和后序遍历。

(1) 前序遍历。

前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树;并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历描述为：若二叉树为空，则执行空操作;否则①访问根结点;②前序遍历左子树;③前序遍历右子树。

(2) 中序遍历。

中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树;并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。中序遍历描述为：若二叉树为空，则执行空操作;否则①中序遍历左子树;②访问根结点;③中序遍历右子树。

(3) 后序遍历。

后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。后序遍历描述为：若二叉树为空，则执行空操作;否则①后序遍历左子树;②后序遍历右子树;③访问根结点。

1.7 查找技术

(1) 顺序查找：在线性表中查找指定的元素。

(2) 最坏情况下，最后一个元素才是要找的元素，则需要与线性表中所有元素比较，比较次数为n。

(3) 二分查找：二分查找也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制，它要求表必须用顺序存储结构，且表中元素必须按关键字有序(升序或降序均可)排列。对长度为n的有序线性表，在最坏情况下，二分查找法只需比较log2n次。

1.8 排序技术

(1) 交换类排序法。

冒泡排序：通过对待排序序列从后向前或从前向后，依次比较相邻元素的排序码，若发现逆序则交换，使较大的元素逐渐从前部移向后部或较小的元素逐渐从后部移向前部，直到所有元素有序为止。在最坏情况下，对长度为n的线性表排序，冒泡排序需要比较的次数为n(n-1)/2。

快速排序：是迄今为止所有内排序算法中速度最快的一种。它的基本思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元索的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。最坏情况下，即每次划分，只得到一个序列，时间效率为O(n2)。

(2) 插人类排序法。

简单插入排序法：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。在最坏情况下，即初始排序序列是逆序的情况下，比较次数为n(n-1)/2，移动次数为n(n-1)/2。

希尔排序法：先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序。待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直接插入排序。

(3) 选择类排序法。

简单选择排序法：扫描整个线性表。从中选出最小的元素。将它交换到表的最前面;然后对剩下的子表采用同样的方法，直到子表空为止。最坏情况下需要比较n(n-1)/2次。

堆排序的方法：首先将一个无序序列建成堆;然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，将该子序列调整为堆。反复做步骤②，直到剩下的子序列空为止。在最坏情况下，堆排序法需要比较的次数为0(nlog2n)

第二章 程序设计基础

2.1 程序设计方法与风格

(1)设计方法：指设计、编制、调试程序的方法和过程，主要有结构化程序设计方法、软件工程方法和面向对象方法。

(2)设计风格：良好的'设计风格要注重源程序文档化、数据说明方法、语句的结构和输入输出。

2.2 结构化程序设计

1.结构化程序设计的原则

结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。。

(1)自顶向下：即先考虑总体，后考虑细节;先考虑全局目标，后考虑局部目标。

(2)逐步求精：对复杂问题，应设计一些子目标做过渡，逐步细化。

(3)模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块;

(4)限制使用GOT0语句。

2.结构化程序的基本结构与特点

(1)顺序结构：自始至终严格按照程序中语句的先后顺序逐条执行，是最基本、最普遍的结构形式。

(2)选择结构：又称为分支结构，包括简单选择和多分支选择结构。

(3)重复结构：又称为循环结构，根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段。

结构化程序设计中，应注意事项：

(1)使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。

(2)选用的控制结构只准许有一个人口和一个出口。

(3)程序语言组成容易识别的块，每块只有一个入口和一个出口。

(4)复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现。

(5)语言中所没有的控制结构，应该采用前后一致的方法来模拟。

(6)尽量避免GOT0语句的使用。

2.3 面向对象的程序设计

面向对象方法的本质是主张从客观世界固有的事物出发来构造系统，强调建立的系统能映射问题域。

对象：用来表示客观世界中任何实体，可以是任何有明确边界和意义的东西。

类：具有共同属性、共同方法的对象的集合。

实例：一个具体对象就是其对应分类的一个实例。

消息：实例间传递的信息，它统一了数据流和控制流。

继承：使用已有的类定义作为基础建立新类的定义技术。

多态性：指对象根据所接受的信息而作出动作，同样的信息被不同的对象接收时有不同行动的现象。面向对象程序设计的优点：与人类习惯的思维方法一致、稳定性好、可重用性好、易于开发大型软件产品、可维护性好。

第三章 软件工程基础

3.1 软件工程基本概念

1.软件的定义与特点

(1)定义：软件是指与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档和数据。

(2)特点。

是逻辑实体，有抽象性。

生产没有明显的制作过程。

运行使用期间不存在磨损、老化问题。

开发、运行对计算机系统有依赖性，受计算机系统的限制，导致了软件移植问题。

复杂性较高，成本昂贵。

开发涉及诸多社会因素。

2.软件的分类

软件可分应用软件、系统软件和支撑软件3类。

(1)应用软件是特定应用领域内专用的软件。

(2)系统软件居于计算机系统中最靠近硬件的一层，是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件。

(3)支撑软件介于系统软件和应用软件之间，是支援其它软件的开发与维护的软件。

3.软件危机与软件工程

软件危机指在计算机软件的开发和维护中遇到的一系列严重问题。软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序，包括软件开发技术和软件工程管理。

4.软件生命周期

软件产品从提出、实现、使用维护到停止使用的过程称为软件生命周期。

在国家标准中，软件生命周期划分为8个阶段①软件定义期：包括问题定义、可行性研究和需求分析3个阶段。②软件开发期：包括概要设计、详细设计、实现和测试4个阶段。③运行维护期：即运行维护阶段。

5.软件工程的原则

软件工程的原则包括：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。

3.2 结构化分析方法

需求分析的任务是发现需求、求精、建模和定义需求的过程，可概括为：需求获取、需求分析、编写需求规格说明书和需求评审。

1.常用的分析方法

结构化分析方法：其实质着眼于数据流，自顶向下，逐层分解，建立系统的处理流程。

面向对象分析方法。

2.结构化分析常用工具

结构化分析常用工具包括数据流图、数字字典(核心方法)、判断树和判断表。

(1)数据流图：即DFD图，以图形的方式描绘数据在系统中流动和处理的过程，它只反映系统必须完成的逻辑功能。是一种功能模型。

符号名称作用：

箭头代表数据流，沿箭头方向传送数据的通道

圆或椭圆代表加工，输入数据经加工变换产生输出

双杠代表存储文件，表示处理过程中存放各种数据文件

方框代表源和潭，表示系统和环境的接口

(2)数据字典：结构化分析方法的核心。数据字典是对所有与系统相关的数据元素的一个有组织的列表。以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。

(3)判定树：使用判定树进行描述时，应先从问题定义的文字描述中分清判定的条件和判定的结论，根据描述材料中的连接词找出判定条件之问的从属关系、并列关系、选择关系，根据它们构造判定树。

(4)判定表：与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合引发的，使用判定表比较适宜。

3.软件需求规格说明书

软件需求规格说明书是需求分析阶段的最后成果，是软件开发的重要文档之一。

(1)软件需求规格说明书的作用：①便于用户、开发人员进行理解和交流;②反映出用户问题的结构，可以作为软件开发工作的基础和依据;③作为确认测试和验收的依据。

(2)软件需求规格说明书的内容：①概述;②数据描述;③功能描述;④性能描述;⑤参考文献;⑥附录。

(3)软件需求规格说明书的特点：①正确性;②无歧义性;③完整性;④可验证性;⑤一致性;⑥可理解性;⑦可修改性;⑧可追踪性。

3.3 结构化设计方法

1.软件设计的基本概念和方法

软件没计是一个把软件需求转换为软件表示的过程。

(1)基本原理：抽象、模块化、信息隐藏、模块独立性(度量标准：耦合性和内聚性，高耦合、低内聚)。

(2)基本思想：将软件设计成由相对独立、单一功能的模块组成的结构。

2.概要设计

(1)4个任务：设计软件系统结构、数据结构及数据库设计、编写概要设计文档、概要设计文档评审。

(2)面向数据流的设计方法：数据流图的信息分为交换流和事物流，结构形式有交换型和事务型。

3.详细设计的工具

详细设计的工具包括：

图形工具：程序流程图、N-S、PAD、HIPO。

表格工具：判定表。

语言工具：PDL(伪码)。

3.4 软件测试

1.目的

为了发现错误而执行程序的过程。

2.准则

所有测试应追溯到用户需求。

严格执行测试计划，排除测试的随意性。

充分注意测试中的群集现象。

程序员应避免检查自己的程序。

穷举测试不可能。

妥善保存设计计划、测试用例、出错统计和最终分析报告。

3.软件测试技术和方法

软件测试的方法按是否需要执行被测软件的角度，可分为静态测试和动态测试，按功能分为白盒测试和黑盒测试。

(1)白盒测试：根据程序的内部逻辑设计测试用例，主要方法有逻辑覆盖测试、基本路径测试等。

(2)黑盒测试：根据规格说明书的功能来设计测试用例，主要诊断方法有等价划分法、边界值分析法、错误推测法、因果图法等，主要用于软件确认测试。

4.软件测试的实施

软件测试是保证软件质量的重要手段，软件测试是一个过程，其测试流程是该过程规定的程序，目的是使软件测试工作系统化。

软件测试过程分4个步骤，即单元测试、集成测试、验收测试和系统测试。

单元测试是对软件设计的最小单位——模块(程序单元)进行正确性检验测试。

单元测试的目的是发现各模块内部可能存在的各种错误。

单元测试的依据是详细的设计说明书和源程序。

单元测试的技术可以采用静态分析和动态测试。

3.5 程序的调试

(1)任务：诊断和改正程序中的错误。

(2)调试方法：强行排错法、回溯法和原因排除法。

第四章 数据库设计基础

4.1 数据库系统的基本概念

(1) 数据(Data)：描述事物的符号记录。

(2) 数据库(DataBase)：长期存储在计算机内的、有组织的、可共享的数据集合。

(3) 数据库管理系统的概念

数据库管理系统(DataBase Management System，DBMS)是数据库的机构，它是一种系统软件，负责数据库中的数据组织、数据操作、数据维护、数据控制及保护和数据服务等。为完成以上6个功能，DBMS提供了相应的数据语言;数据定义语言(负责数据的模式定义与数据的物理存取构建);数据操纵语言(负责数据的操纵);数据控制语言(负责数据完整性、安全性的定义)。数据库管理系统是数据库系统的核心，它位于用户和操作系统之间，从软件分类的角度来说，属于系统软件。

(4) 数据库技术发展经历了3个阶段。

人工管理阶段→文件系统阶段→数据库系统阶段

(5) 数据库系统的特点：集成性、高共享性、低冗余性、数据独立性、数据统一管理与控制等。

(6) 数据库系统的内部机构体系：三级模式(概念模式、内模式、外模式)和二级映射(外模式/概念模式的映射、概念模式/内模式的映射)构成了数据库系统内部的抽象结构体系。

4.2 数据模型

数据模型是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，描述的内容有数据结构、数据操作和数据约束。有3个层次：概念数据模型、逻辑数据模型和物理数据模型。

(1) E—R模型：提供了表示实体、属性和联系的方法。实体间联系有“一对一”、“一对多”和“多对多”。

(2) E-R模型用E-R图来表示。

(3) 层次模型：利用树形结构表示实体及其之问联系。其中节点是实体，树枝是联系，从上到下是一对多关系。

(4) 网状模型：用网状结构表示实体及其之间联系。是层次模型的扩展。网络模型以记录型为节点，反映现实中较为复杂的事物联系。

(5) 关系模型：采用二维表(由表框架和表的元组组成)来表示，可进行数据查询、增加、删除及修改操作。关系模型允许定义“实体完整性”、“参照完整性”和“用户定义的完整性”三种约束。

键(码)：二维表中唯一能标识元组的最小属性集。

候选键(候选码)：二维表中可能有的多个键。

主键：被选取的一个使用的键。

4.3 关系代数

(1) 关系代数的基本运算：投影、选择、笛卡尔积。

(2) 关系代数的扩充运算：交、连接与自然连接、除。

4.4 数据库设计与管理

1.数据库设计概述

基本思想：过程迭代和逐步求精。

方法：面向数据的方法和面向过程的方法。

设计过程：需求分析→概念设计→逻辑设计→物理设计→编码→测试→运行→进→步修改。

2.数据库设计的需求分析

需求收集和分析是数据库设计的第一阶段，常用结构化分析方法(自顶向下、逐层分解)和面向对象的方法，主要工作有绘制数据流程图、数据分析、功能分析、确定功能处理模块和数据间关系。

数据字典：包括数据项、数据结构、数据流、数据存储和处理过程，是对系统中数据的详尽描述。

3.数据库的设计

(1) 数据库的概念设计：分析数据问内在的语义关联，以建立数据的抽象模型。

(2) 数据库的逻辑设计：从E-R图向关系模型转换，逻辑模式规范化，关系视图设计可以根据用户需求随时创建。实体转换为元组，属性转换为关系的属性，联系转换为关系。

(3) 数据库的物理设计：是数据在物理设备上的存储结构与存取方法，目的是对数据库内部物理结构作出调整并选择合理的存取路径，以提高速度和存储空间。

4.数据库管理

数据库管理包括数据库的建立、数据库的调整、数据库的重组、数据库的安全性与完整性控制、数据库故障恢复和数据库的监控。

② 计算机二级二叉树算法

1、二叉树的概念

二叉树是一种特殊的树形结构，每个结点最多只有两棵子树，且有左右之分不能互换，因此，二叉树有五种不同的形态。

2、二叉树的性质

性质1 在二叉树的第k层上，最多有2^(k-1)(k≥1）个结点。

性质2 深度为m的二叉树最多有2^m-1个结点。

性质3 在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。

性质4 具有n个结点的二叉树，其深度不小于[log2n]+1,其中[log2n]表示为log2n的整数部分。

③ 计算机二级算法

这正经文章写的都太繁复了。可行性就是说能不能运行，就是这么简单的意思。它的举例过于抽象，可以换一个说法：比如你想用计算机里的画图画圆，先按住鼠标然后画圈就能成，先画圈后按住鼠标就不成。由此说明一个软件事务并不是做完了每一步就算是成功，先后顺序（也就是算法）是会影响到可行性的。

④ 计算机二级数据结构与算法知识点

一、数据结构

（1）数据结构的基本概念

1、数据：数据是客观事物的符号表示，是能输入到计算机中并被计算程序识别和处理的符号的总称，如文档，声音，视频等。

2、数据元素：数据元素是数据的基本单位。

3、数据对象：数据对象是性质相同的数据元素的集合。

4、数据结构：是指由某一数据对象中所有数据成员之间的关系组成的集合。

（2）逻辑结构和存储结构

1、数据结构可分为数据的逻辑结构和存储结构。

1）数据的逻辑结构是对数据元素之间的逻辑关系的描述，与数据的存储无关，是面向问题的，是独立于计算机的。它包括数据对象和数据对象之间的关系。

2）数据的存储结构也称为数据的物理结构，是数据在计算机中的存放的方式，是面向计算机的，它包括数据元素的存储方式和关系的存储方式。

2、存储结构和逻辑结构的关系：一种数据的逻辑结构可以表示成多种存储结构即数据的逻辑结构和存储结构不一定一一对应。

3、常见的存储结构有：顺序，链接，索引等。采用不同的存储结构其数据处理的效率是不同的。

⑤ 计算机二级选择题干货（五）——数据结构和算法

1、线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又称后进先出表（Last In First Out）；队列可看作是插入在一端进行，删除在另一端进行的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。在队列中，只能删除队头元素，队列的最后一个元素一定是最新入队的元素。因此队列又称先进先出表（First In First Out）。

2、栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种"后进先出"的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种"先进先出"的线性表。

3、栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又称先进后出表（FILO-First In Last Out）。线性表可以顺序存储，也可以链式存储，而栈是一种线性表，也可以采用链式存储结构。

4、栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种"后进先出"的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种"先进先出"的线性表。

5、在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化

top=0表示栈空，top=50表示栈满。入栈操作首先将top加1，然后将新元素插入到top指针指向的位置；退栈操作首先将top指针指向的元素赋给一个指定的变量，然后将top减1。栈顶指针top动态反映了栈中元素的变化情况。

6、栈是一种先进后出的线性表，栈实际上也是线性表，只不过是一种特殊的线性表。队列是指允许在一端进行插入、而在另一端进行删除的线性表，队列是一种"先进先出"或"后进后出"的线性表

队列是指允许在一端进行插入、而在另一端进行删除的线性表。它又称为"先进先出"或"后进后出"的线性表，体现了"先来先服务"的原则。

7、带链的队列也是线性链表，在线性链表中指向线性表中的第一个结点的指针称为头指针，头指针为NULL或0时称为空表，指向队尾元素的指针称为尾指针。队列在队尾插入元素，称为入队运算；在队头删除元素，称为退队运算。带链队列在开辟存储空间时，可以按照存储空间地址增大的方向开辟，也可以按照存储空间地址减少的方向开辟。

8、所谓循环队列，就是将队列存储空间的最后一个位置绕到第1个位置，形成逻辑上的环状空间，供队列循环使用。所以循环队列还是属于线性结构。循环队列的头指针front指向队列的第一个元素的前一位置，队尾指针rear指向队列的最后一个元素，循环队列的动态变化需要头尾指针共同反映循环队列的长度是：(sq.rear-sq.front+maxsize)%maxsize，所以循环队列的长度是由队头和队尾指针共同决定的

 在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。

 循环队列主要有两种基本运算：入队运算与退队运算。每进行一次入队运算，队尾指针就进一。每进行一次退队运算，排头指针就进一。当rear或front的值等于队列的长度+1时，就将rear或front的值置为1。一般情况下，rear大于front，因为入队的元素肯定比出队的元素多。特殊的情况是rear到达数组的上限之后又从数组的低端开始，此时，rear是小于front的。

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在实际应用中，队列的顺序存储结构一般采用循环队列的形式。因此，循环队列不是队列的一种链式存储结构。循环队列是一种存储结构，因此循环队列是一种物理结构，而不是逻辑结构。循环队列是队列的顺序存储结构，因此循环队列是线性结构。

9、循环队列不同于循环链表，循环队列是顺序存储结构，循环链表是链式存储结构。双向链表是链式存储结构，其中每个结点都有左指针和右指针，不同于二叉树结点的左子树指针和右子树指针。非线性结构和线性结构是数据的逻辑结构，顺序和链式是数据的存储结构，例如二叉树是非线性结构，也可以按照层序进行顺序存储。

10、非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后驱。常见的非线性结构有：树（二叉树等），图（网等）。

11、由于二叉树的存储结构中每一个存储结点有两个指针域，因此，二叉树的链式存储结构也称为二叉链表，二叉链表属于非线性结构。

12、遍历是指不重复的访问所有结点。线性单链表每个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点。双向链表中的每个结点设置两个指针，左指针指向其前件结点，右指针指向其后件结点。循环链表中增加了一个表头结点，循环链表中的所有结点的指针构成了一个环状链。二叉链表即二叉树的链式存储结构，每个存储结点有两个指针域，左指针域指向该结点的左子结点的存储地址，右指针域指向该结点的右子结点的存储地址。

13、线性表的顺序存储结构具有两个基本特点：（1）线性表中所有元素所占的存储空间是连续的;（2）线性表中各元素在存储空间中是按逻辑顺序依次存放的。

14、循环链表具有以下两个特点：(1)在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。(2)循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。

15、在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。

16、根据二叉树的性质：二叉树第i（i≥1）层上至多有2i-1个结点。

17、所谓满二叉树是指这样的一种二叉树：除最后一层外，每层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第K层上有2K-1个结点，且深度为m的满二叉树有2m个结点。

18、在任意一颗树中，结点总数=总分支数目+1

19、二叉树的性质：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。本题中度为2的结点数为n，故叶子结点数为n+1个。

二叉树的性质：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。

20、在用完全二叉树表示堆，树中所有非叶子结点值均不小于其左右子树的根结点值，因此，堆顶元素必为序列的n个元素中的最大项。

21、作为一个算法，一般应具有以下几个基本特征。

 可行性

 确定性

 有穷性

拥有足够的情报

22、计算机算法是指解题方案的准确而完整的描述

算法的有穷性，是指算法必须在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。

23、希尔排序法的基本思想是：将整个无序序列分割成若干小的子序列分别进行插入排序。所以希尔排序法属于插入类排序，但它对简单插入排序做了很大的改进。

24、快速排序的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续进行排序，以达到整个序列有序；插入排序的基本操作是指将无序序列中的各元素依次插入到已经有序的线性表中，从而得到一个新的序列；选择排序的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置），然后对剩下的子表采用同样的方法，直到表空为止；归并排序是将两个或两个以上的有序表组合成一个新的有序表。

25、在单链表中，增加头结点的目的是______。

头结点不仅标识了表中首结点的位置，而且根据单链表（包含头结点）的结构，只要掌握了表头，就能够访问整个链表，因此增加头结点目的是为了便于运算的实现。

26、算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。

27、算法是指解题方案的准确而完整的描述。但算法不等于程序，也不等于计算方法。当然，程序也可以作为算法的一种描述，但程序通常还需要考虑很多与方法和分析无关的细节问题，这是因为在编写程序时要受到计算机系统运行环境的限制。通常，程序的编制不可能优于算法的设计。作为一个算法，一般应具有可行性、确定性、有穷性、拥有足够情报四个基本特征。因此设计算法时不仅仅要考虑结果的可靠性，即不仅考虑算法结果的可行性，还要考虑步骤的确定性，时间和步骤的有穷性等。因此，算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。

28、一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。因此设计算法时不仅需要考虑数据结构的设计，还要考虑数据的操作和运算及各操作之间的执行顺序。

29、在有向图中，若任意两个顶点都连通，则称该图是强连通图，这样的有向图的形状是环状，因而至少应有n条边。

30、当数据表A中每个元素距其最终位置不远，说明数据表A按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少。

31、数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。

32、假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较次数为n(n-1)/2。快速排序法的最坏情况比较次数也是n(n-1)/2

（1）冒泡排序法：是一种最简单的交换类排序法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要比较的次数为n(n-1)/2次。

 （2）简单插入排序法：在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-1)/2次比较。

 （3）简单选择排序法：对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。简单选择排序法在最坏情况下需要比较n(n-1)/2次。

 （4）堆排序法：堆排序的方法为：①首先将一个无序序列建成堆。②然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。在最坏情况下，堆排序需要比较的次数为。

 假设线性表的长度为16，那么冒泡排序、直接插入排序、简单选择排序都需要比较120次，而堆排序需要比较64次。

33、对于长度为n的线性表，在最坏的情况下，快速排序所需要的比较次数为n(n-1)/2；冒泡排序所需要的比较次数为n(n-1)/2；直接插入排序所需要的比较次数为n(n-1)/2；堆排序所需要的比较次数为。

34、在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高；但如果被查找的元素是线性表中的最后一个元素，或者被查找的元素根本就不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。所以对长度为n的线性表进行顺序查找，在最坏情况下需要比较n次。

35、二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。

二分法检索要求线性表结点按关键值排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功；否则根据比较结果确定下一步在表的前半部分或后半部分继续进行。二分法检索的效率比较高，设线性表有n个元素，则最多的检索次数为大于log2n(2为底数)的最小整数，最少的检索次数为1。

36、一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。

37、顺序存储结构就是用一组地址连续的存储单元依次存储该线性表中的各个元素，链式存储结构中各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。两者都可以存储线性的、有序的逻辑结构，顺序结构使用的是连续物理空间，链式结构可以使用零散的物理空间存储，链式结构更灵活，不存在谁节约空间的说法

38、顺序存储结构中，数据元素存放在一组地址连续的存储单元中，每个数据元素地址可通过公式LOC(ai)=LOC(a1)+(i-1)L计算得到，从而实现了随机存取。对于链式存储结构，要对某结点进行存取，都得从链的头指针指向的结点开始，这是一种顺序存取的存储结构。

39、链式存储结构克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。

40、线性表的顺序存储结构的存储空间只用于存放结点数据，而链式存储结构的存储空间不仅要存放结点数据，还要存放数据的指针，所以线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构

41、在进行顺序查找过程中，如果线性表中的第1个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高；但如果被查找的元素是线性表中的最后一个元素，或者被查找的元素根本就不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行较，这是顺序查找的最坏情况。所以对长度为n的线性表进行顺序查找，在最坏情况下需要比较n次

42、对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较 次，而顺序查找需要比较n次。二分法查找只适用于顺序存储的有序表，如果采用链式存储结构，也只能用顺序查找,所以，对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n

43、根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。

44、如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。

45、有一个以上根结点的数据结构肯定是非线性结构，循环链表、双向链表是线性结构；线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。

46、在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构

47、线性表的链式存储结构称为线性链表，为了适应线性表的链式存储结构，计算机存储空间被划分为一个一个小块，每一小块占若干字节，通常称这些小块为存储结点。每一个存储结点分为两部分：一部分用于存储数据元素的值，称为数据域；另一部分用于存放下一个数据元素的存储序号，即指向后件的结点，称为指针域。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。为了要在线性链表中插入一个新元素，首先要给该元素分配一个新结点，以便用于存储该元素的值，然后将存放新元素值的结点链接到线性表中指定的位置。在线性链表的插入过程中不发生数据无素移动的现象，只需改变有关结点的指针即可，从而提高了插入的效率。为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点放回到可利用栈。在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删元素所在结点的前一个结点的指针域即可。因此，进行插入与删除时，不需要移动表中的元素。

48、在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为3种：前序遍历、中序遍历和后序遍历。

前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

后序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点；并且遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

二叉树的中序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

49、链表有线性链表，也有非线性链表。线性链表和二叉树链表的结点都有两个指针域，前者是线性结构，后者是非线性结构。线性单链表中的结点只有一个指针，叶子结点一般是对树结构而言，树结构是非线性结构，不是线性表。

50、算法的复杂度主要包括时间复杂度和空间复杂度：算法在运行过程中需辅助存储空间的大小称为算法的空间复杂度；算法的时间复杂度是指执行算法所需要的计算工作量，即算法执行过程中所需要的基本运算次数，为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。二者没有直接关系。

51、一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间相对于问题规模来说是常数，则称该算法是原地(in place)工作的。

52、我们通常用时间复杂度和空间复杂度来衡量算法效率，算法的时间复杂度是指执行算法所需要的计算工作量；算法所执行的基本运算次数与问题的规模有关，而一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间；一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。

所谓算法的时间复杂度，是指执行算法所需要的计算工作量。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。

53、子程序调用是一种层次关系，子程序调用功能模块，调用功能模块的个数也不确定，可以是一个，也可以是多个。二叉树是一种很有用的非线性结构，二叉树不同于树形结构。二叉树具有以下两个特点：①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。选项D规定每个结点只能有两个后件。在子程序调用中，调用的功能模块可以是多个，可以调用超过两个功能模块。

54、结构图的深度表示控制的层数结构图的深度表示控制的层数

55、数据结构是指反映数据元素之间关系的数据元素集合的表示。更通俗地说，数据结构是指带有结构的数据元素的集合。所谓结构实际上就是指数据元素之间的前后件关系。线性结构与非线性结构都可以是空的数据结构。一个空的数据结构究竟是属于线性结构还是属于非线性结构，还要根据具体情况来确定。如果对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。

⑥ 算法是什么意思

算法，从字面意义上解释，就是用于计算的方法，通过该这种方法可以达到预期的计算结果。目前，被广泛认可的算法专业咐渣敏定义是：算法是模型分析的一组可行的，确定的，有穷的规则。通俗的说，算法也可以理解为一个解题梁陆步骤，有一些基本运算和规定的顺序构成。但是从计算机程序设计的角度看，算法由一系列求解问题的指令构成，能根据规范的输入，在有限的时间内获得有效的输出衡枝结果。算法代表了用系统的方法来描述解决问题的一种策略机制。

完成同一件事的不同的算法完成的时间和占用的资源可能并不相同，这就牵扯到效率的问题。算法的基本任务是针对一个具体的问题，找到一个高效的处理方法，从而完成任务。而这就是我们的责任了。

算法的五个特征：

一个典型的算法一般都可以抽象出5个特征：

有穷性：算法的指令或者步骤的执行次数和时间都是有限的。

确切性：算法的指令或步骤都有明确的定义。

输入：有相应的输入条件来刻画运算对象的初始情况。

输出：一个算应有明确的结果输出。

可行性：算法的执行步骤必须是可行的。