算法的计算量的大小称为算法的

❶ 何谓算法算法有什么性质

算法（algorithm），在数学（算学）和计算机科学之中，为任何一系列良定义的具体计算步骤，常用于计算、数据处理和自动推理。作为一个有效方法，算法被用于计算函数，它包含了一系列定义清晰的指令，并可于有限的时间及空间内清楚的表述出来。

特点：

1、输入：一个算法必须有零个或以上输入量。

2、输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。

3、明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地符合要求或期望，通常要求实际运行结果是确定的。

4、有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。

5、有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

(1)算法的计算量的大小称为算法的扩展阅读：

常用设计模式

完全遍历法和不完全遍历法：在问题的解是有限离散解空间，且可以验证正确性和最优性时，最简单的算法就是把解空间的所有元素完全遍历一遍，逐个检测元素是否是我们要的解。

这是最直接的算法，实现往往最简单。但是当解空间特别庞大时，这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。

1、分治法：把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。

2、动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。

3、贪心算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。

4、简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。

❷ 求2011年九月以及以前的计算机二级考试C语言试题及答案、以及考试内容分析和解题技巧。记住只要C的。

(1)下面叙述正确的是________。
A)算法的执行效率与数据的存储结构无关
B)算法的空间复杂度是指算法程序中指令(或语句)的条数
C)算法的有穷性是指算法必须能在执行有限个步骤之后终止
D)算法的时间复杂度是指执行算法程序所需要的时间
(1)C
知识点:算法的基本概念；算法复杂度的概念和意义(时间复杂度与空间复杂度)
评 析：算法的设计可以避开具体的计算机程序设计语言，但算法的实现必须借助程序设计语言中提供的数据类型及其算法。数据结构和算法是计算机科学的两个重要支柱。它们是一个不可分割的整体。算法在运行过程中需辅助存储空间的大小称为算法的空间复杂度。算法的有穷性是指一个算法必须在执行有限的步骤以后结束。算法的时间复杂度是指执行算法所需要的计算工作量，即算法执行过程中所需要的基本运算次数。
(2)以下数据结构属于非线性数据结构的是________。
A)队列 B)线性表 C)二叉树 D)栈
(2)C
知识点:栈和队列的定义；栈和队列的顺序存储结构及其基本运算
评 析:线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又称后进先出表(Last In First Out)。队列可看作是插入在一端进行，删除在另一端进行的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。在队列中，只能删除队头元素，队列的最后一个元素一定是最新入队的元素。因此队列又称先进先出表(First In First Out)。二叉树的数据结构是树型结构，结构中数据元素之间存在着一对多的关系，因此它是一种非线性数据结构。
(3)在一棵二叉树上第8层的结点数最多是________。
A)8 B)16 C)128 D)256
(3)C
知识点：二叉树的定义及其存储结构
评 析:根据二叉树的性质：二叉树第i(I>1)层上至多有2i-1个结点。得到第8层的结点数最多是128。
(4)下面描述中，不符合结构化程序设计风格的是________。
A)使用顺序、选择和重复(循环)三种基本控制结构表示程序的控制逻辑
B)自顶向下
C)注重提高程序的执行效率
D)限制使用goto语句
(4)C
知识点：结构化程序设计
评 析：结构化程序设计方法的四条原则是：1．自顶向下：2．逐步求精；3．模块化；4．限制使用goto语句。“自顶向下”是说，程序设计时，应先考虑总体，后考虑细节，先考虑全局目标，后考虑局部目标；“逐步求精’’是说，对复杂问题，应设计一些子目标作过渡，逐步细节化；“模块化”是说，一个复杂问题肯定是由若干稍简单的问题构成，解决这个复杂问题的程序，也应对应若干稍简单的问题，分解成若干稍小的部分。
(5)下面概念中，不属于面向对象方法的是________。
A)对象、消息 B)继承、多态 C)类、封装 D)过程调用
(5)D
知识点:面向对象的程序设计方法、对象、方法、属性及继承与多态性
评 析:面向对象方法是一种运用对象、类、封装、继承、多态和消息等概念来构造、测试、重构软件的方法。面向对象方法从对象出发，发展出对象、类、消息、继承等概念。
(6)在结构化方法中，用数据流程图(DFD)作为描述工具的软件开发阶段是________。
A)可行性分析 B)需求分析 C)详细设计 D)程序编码
(6)B
知识点:结构化设计方法
评 析:软件开发阶段包括需求分析、总体设计、详细设计、编码和测试五个阶段。其中需求分析阶段常用的工具是数据流程图和数据字典。
(7)软件生命周期中所花费用最多的阶段是________。
A)详细设计 B)软件编码 C)软件测试 D)软件维护
(7)D
知识点:软件工程基本概念，软件生命周期概念，软件工具与软件开发环境
评 析:软件生命周期分为软件定义、软件开发及软件运行维护3个阶段。本题中详细设计、软件编码和软件测试都属于软件开发阶段；维护是软件生命周期的最后一个阶段，也是持续时间最长，花费代价最大的一个阶段，软件工程学的一个目的就是提高软件的可维护性，降低维护的代价。
(8)数据库系统的核心是________。
A)数据模型 B)DBMS C)软件工具 D)数据库
(8)B
知识点:数据库的基本概念：数据库，数据库管理系统，数据库系统
评 析:数据库管理系统DBMS是数据库系统的核心。DBMS是负责数据库的建立、使用和维护的软件。DBMS建立在操作系统之上，实施对数据库的统一管理和控制。用户使用的各种数据库命令以及应用程序的执行，最终都必须通过DBMS。另外，DBMS还承担着数据库的安全保护工作，按照DBA所规定的要求，保证数据库的完整性和安全性。
(9)下列叙述中正确的是________。
A)数据处理是将信息转化为数据的过程
B)数据库设计是指设计数据库管理系统
C)如果一个关系中的属性或属性组并非该关系的关键字，但它是另一个关系的关键
字，则称其为本关系的外关键字
D)关系中的每列称为元组，一个元组就是一个字段
(9)C
知识点:数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型
评 析：数据处理是指将数据转换成信息的过程，故选项A叙述错误；设计数据库的目的实质上是设计出满足实际应用需求的实际关系模型，故选项B叙述错误；关系中的行称为元组，对应存储文件中的记录，关系中的列称为属性。对应存储文件中的字段，故D选项叙述错误。
(10)下列模式中，_______是用户模式。
A)内模式 B)外模式 C)概念模式 D)逻辑模式
(10)B
知识点：数据库的基本概念：数据库，数据库管理系统，数据库系统
评 析：数据库管理系统的三级模式结构由外模式、模式和内模式组成。外模式，或称子模式，或称用户模式，是指数据库用户所看到的数据结构，是用户看到的数据视图。模式，或称逻辑模式，是数据库中对全体数据的逻辑结构和特性的描述，是所有用户所见到的数据视图的总和。外模式是模式的一部分。内模式，或称存储模式，或称物理模式，是指数据在数据库系统内的存储介质上的表示。即对数据的物理结构和存取方式的描述。
36)算法的时间复杂度是指_______。
A)执行算法程序所需要的时间
B)算法程序的长度
C)算法执行过程中所需要的基本运算次数
D)算法程序中的指令条数
(36)C
知识点：算法复杂度的概念和意义(时问复杂度与空间复杂度)
评析：所谓算法的时间复杂度，是指执行算法所需要的计算工作量。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。
(37)下列叙述中正确的是_______。
A)线性表是线性结构 B)栈与队列是非线性结构
C)线性链表是非线性结构 D)二叉树是线性结构
(37)A
知识点：线性结构与非线性结构的概念
评析：根据数据结构中各数据元素之间相关联关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件： (1)有且只有一个根结点； (2)每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。所以线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。
(38)下面关于完全二叉树的叙述中，错误的是_______。
A)除了最后一层外，每一层上的结点数均达到最大值
B)可能缺少若干个左右叶子结点
C)完全二叉树一般不是满二叉树
D)具有结点的完全二叉树的深度为[log2n]+l
(38)B
知识点：二叉树的定义及其存储结构
评析：这里考察完全二又树与满二叉树的定义及二叉树的性质。满二叉树指除最后一层外每一层上所有结点都有两个子结点的二叉树。完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干子结点(叶子结点)的二叉树。因此选项A是正确的，而选项B是错误的。由定义可知，满二叉树肯定是完全二又树，而完全二又树一般不是满二叉树，因此选项c是正确的叙述。选项D即二又树性质(5)，也是正确的。
(39)结构化程序设计主要强调的是_______。
A)程序的规模 B)程序的易读性
C)程序的执行效率 D)程序的可移植性
(39)B
知识点：结构化程序设计
评析：结构化程序设计主要强调的足结构化程序清晰易读，可理解性好，程序员能够进行逐步求精、程序证明和测试．以保证程序的正确性。
(40)在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是_______。
A)概要设计 B)详细设计 C)可行性分析 D)需求分析
(40)D
知识点：软件工程基本概念，软件生命周期概念，软件工具与软件开发环境
评析：通常，将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。也就是说，软件产品从考虑其概念开始，到该软件产品不能使用为止的整个时期都属于软件生命周期。软件生命周期的主要活动阶段为：
① 可行性研究和计划制定。确定待开发软件系统的开发目标和总的要求，给出它的功能、性能、可靠性以及接口等方面的可行方案，制定完成开发任务的实施计划。
②需求分析。对待开发软件提出的需求进行分析并给出详细定义，即准确地确定软件系统的功能。编写软件规格说明书及初步的用户手册，提交评审。
③软件设计。系统设计人员和程序设计人员应该在反复理解软件需求的基础上，给出软件的结构、模块的划分、功能的分配以及处理流程。
④软件实现。把软件设计转换成计算机可以接受的程序代码。即完成源程序的编码，编写用户手册、操作手册等面向用户的文档，编写单元测试计划。
⑤软件测试。在设计测试用例的基础上，检验软件的各个组成部分。编写测试分析报告。
⑥运行和维护。将已交付的软件投入运行，并存运行使用中不断地维护，根据新提出的需求进行必要而且可能的扩充和删改。
(41)数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是_______。
A)控制流 B)加工 C)数据存储 D)源和潭
(41)A
知识点：结构化分析方法，数据流图，数据字典，软件需求规格说明书
评析：数据流图从数据传递和加工的角度，来刻画数据流从输入到输出的移动变换过程。数据流图中的主要图形元素有：加工(转换)、数据流、存储文件(数据源)、源和潭。
(42)软件需求分析一般应确定的是用户对软件的_______。
A)功能需求 B)非功能需求 C)性能需求 D)功能需求和非功能需求
(42)D
知识点：结构化设计方法
评析：软件需求分析中需要构造一个完全的系统逻辑模型，理解用户提出的每一功能与性能要求，是用户明确自己的任务。因此，需求分析应确定用户对软件的功能需求和非功能需求。
(43)下述关于数据库系统的叙述中正确的是_______。
A)数据库系统减少了数据冗余
B)数据库系统避免了一切冗余
C)数据库系统中数据的一致性是指数据类型的一致
D)数据库系统比文件系统能管理更多的数据
(43)A
知识点：数据库的基本概念：数据库，数据库管理系统，数据库系统
评析：由于数据的集成性使得数据可为多个应JH=j所共享，特别是在网络发达的今天，数据库与网络的结合扩大了数据关系的应用范围。数据的共享自身义可极大地减少数据冗余性，不仅减少了不必要的存储空间，更为重要的是可以避免数据的不一致性。所谓数据的一致性是指在系统中同一数据的不同出现应保持相同的值，而数据的不一致性指的是同一个数据在系统的不同拷贝处有不同的值。
(44)关系表中的每一横行称为一个_______。
A)元组 B)字段 C)属性 D)码
(44)A
知识点：数据库的基本概念：数据库．数据库管理系统，数据库系统
评析：在关系数据库中，关系模型采用二维表来表示，简称“表”。二维表是由表框架及表元组组成。在表框架中，按行可以存放数据，每行数据称为元组。
(45)数据库设计包括两个方面的设计内容，它们是_______。
A)概念设计和逻辑设计 B)模式设计和内模式设计
C)内模式设计和物理设计 D)结构特性设计和行为特性设计
(45)A
知识点：数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略
评析：数据库设计可分为概念设计与逻辑设计。数据库概念设计的目的是分析数据问内存语义关联，在此基础上建立一个数据的抽象模型。数据库逻辑设计的主要工作是将E-R图转换为指定的RDBMS中的关系模型。
(61)字符(char)型数据在微机内存中的存储形式是________。
A)反码 B)补码
C)EBCDIC码 D)ASCII码
(61)D
知识点：字符数据在内存中的存储形式
评析：将一个字符常量放到一个字符变量中，实际上并不是把该字符本身放到内存单元中去，而是将该字符的ASCII码值放到存储单元中。
71)算法的空间复杂度是指_______。
A)算法程序的长度 B)算法程序中的指令条数
C)算法程序所占的存储空间 D)算法执行过程中所需要的存储空间
(71)D
知识点：算法的复杂度
评析：一个算法的空间复杂度，一般是指执行这个算法所需的内存空间。
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。
(72)下列关于栈的叙述中正确的是_______。
A)在栈中只能插入数据 B)在栈中只能删除数据
C)栈是先进先出的线性表 D)栈是先进后出的线性表
(72)D
知识点：栈的输入输出操作
评析：栈是限定在一端进行插入与删除的线性表。
栈是按照“先进后出”的或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。
(73)在深度为5的满二叉树中，叶子结点的个数为_______。
A)32 B)31 C)16 D)15
(73)C
知识点：二叉树的概念
评析：所谓满二叉树是指除最后一层外，每层上的所有结点都有两个子结点。也就是说，在满二又树中，每一层上的结点数都达到最大值，即在满二叉树的第K层上有2k-1个结点，且深度为m的满二叉树有2m个结点。
在满二叉树中，最后一层的结点个数就是叶子结点的个数，本题中深度为5，故叶子结点数为25-1=24==16。
(74)对建立良好的程序设计风格，下面描述正确的是_______。
A)程序应简单、清晰、可读性好 B)符号名的命名要符合语法
C)充分考虑程序的执行效率 D)程序的注释可有可无
(74)A
知识点：程序设计风格
评析：要形成良好的程序设计风格，主要应注重和考虑下述一些因素：符号名的命名应具有一定的实际含义，以便于对程序功能的理解；正确的注释能够帮助读者理解程序；程序编写应优先考虑清晰性，除非对效率有特殊要求，程序编写要做到清晰第一，效率第二。
(75)下面对对象概念描述错误的是_______。
A)任何对象都必须有继承性 B)对象是属性和方法的封装体
C)对象问的通讯靠消息传递 D)操作是对象的动态性属性
(75)A
知识点：对象的概念
评析：对象是由数据和容许的操作组成的封装体，与客观实体有直接的对应关系。对象之间通过传递消息互相联系，以模拟现实世界中不同事物彼此之间的联系。
(76)下面不属于软件工程的3个要素的是_______。
A)工具 B)过程 C)方法 D)环境
(76)D
知识点：软件：[程的要素
评析：软件工程包括3个要素，即方法、工具和过程。
(77)程序流程图(PFD)中的箭头代表的是_______。
A)数据流 B)控制流 C)调用关系 D)组成关系
(77)B
知识点：软件设计工具
评析：程序流程图(PFD)是一种传统的、应用广泛的软件过程设计表示工具，通常也称为程序框图，其箭头代表的是控制流。
(78)在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是_______。
A)数据库系统 B)文件系统 C)人工管理 D)数据项管理
(78)A
知识点：数据管理技术的发展
评析：在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是数据库系统。

❸ 1. 算法的计算量的大小称为计算的什么

B.复杂性
所谓算法的计算量大小就是这个算法的时间复杂度

❹ 求下面数据结构试题的答案...

一．

1,复杂性2.线性结构非线性结构

3．可以按序号随机存取4.数据元素

5.后进先出6.n7.只能在队头进行

9.长度1深度1

10-+A*BC/DE

11

12顶点Vp到顶点Vq之间的路径是指定的序列Vp，Vi1，Vi2•••Vim，Vq。

13n（n-2）/214n—1152n—1

17一种存储结构

19可以从表中任意结点开始遍历整个链表；只用一个指向尾结点的指针对链表头、尾进行操作，提高了效率。

20栈是仅限制在表的一端进行插入和删除的运算的线性表，是一种操作受限的线性表。

二．

1算法的时间复杂度和空间复杂度

2.队列

3.

4嵌套集合表示法，广义表表示法，凹入表示法

5.456.S(1)X(1)S(2)S(3)X(3)S(4)X(4)X(2)

7（1）O（nˆ2）

（2）O（nˆ2）

8.

哈夫曼树：

WPL=2*5+4*5+5*4+16*3+8*3+7*3+30=173

9.邻接矩阵：

邻接表：

10.二叉树：

前序：ABCEFD

中序：BEFCDA

后序：FEDCBA

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

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

❻ 实现算法所存储的单元多少和算法的工作量大小分别称为算法的什么

这需要进行位操作,必较麻烦的,
在学习程序语言和进行程序设计的时候，交换两个变量的值是经常要使用的。通常我们的做法是（尤其是在学习阶段）：定义一个新的变量，借助它完成交换。代码如下：
int a,b;
a=10; b=15;
int t;
t=a; a=b; b=t;
这种算法易于理解，特别适合帮助初学者了解计算机程序的特点，是赋值语句的经典应用。在实际软件开发当中，此算法简单明了，不会产生歧义，便于程序员之间的交流，一般情况下碰到交换变量值的问题，都应采用此算法（以下称为标准算法）。

上面的算法最大的缺点就是需要借助一个临时变量。那么不借助临时变量可以实现交换吗？答案是肯定的！这里我们可以用三种算法来实现：1）算术运算；2）指针地址操作；3）位运算。

1） 算术运算
简单来说，就是通过普通的+和-运算来实现。代码如下：
int a,b;
a=10;b=12;
a=b-a; //a=2;b=12
b=b-a; //a=2;b=10
a=b+a; //a=10;b=10
通过以上运算，a和b中的值就进行了交换。表面上看起来很简单，但是不容易想到，尤其是在习惯标准算法之后。
它的原理是：把a、b看做数轴上的点，围绕两点间的距离来进行计算。
具体过程：第一句“a=b-a”求出ab两点的距离，并且将其保存在a中；第二句“b=b-a”求出a到原点的距离（b到原点的距离与ab两点距离之差），并且将其保存在b中；第三句“a=b+a”求出b到原点的距离（a到原点距离与ab两点距离之和），并且将其保存在a中。完成交换。
此算法与标准算法相比，多了三个计算的过程，但是没有借助临时变量。（以下称为算术算法）

2） 指针地址操作
因为对地址的操作实际上进行的是整数运算，比如：两个地址相减得到一个整数，表示两个变量在内存中的储存位置隔了多少个字节；地址和一个整数相加即“a+10”表示以a为基地址的在a后10个a类数据单元的地址。所以理论上可以通过和算术算法类似的运算来完成地址的交换，从而达到交换变量的目的。即：
int *a,*b; //假设
*a=new int(10);
*b=new int(20); //&a=0x00001000h,&b=0x00001200h
a=(int*)(b-a); //&a=0x00000200h,&b=0x00001200h
b=(int*)(b-a); //&a=0x00000200h,&b=0x00001000h
a=(int*)(b+int(a)); //&a=0x00001200h,&b=0x00001000h
通过以上运算a、b的地址真的已经完成了交换，且a指向了原先b指向的值，b指向原先a指向的值了吗？上面的代码可以通过编译，但是执行结果却令人匪夷所思！原因何在？
首先必须了解，操作系统把内存分为几个区域：系统代码/数据区、应用程序代码/数据区、堆栈区、全局数据区等等。在编译源程序时，常量、全局变量等都放入全局数据区，局部变量、动态变量则放入堆栈区。这样当算法执行到“a=(int*)(b-a)”时，a的值并不是0x00000200h，而是要加上变量a所在内存区的基地址，实际的结果是：0x008f0200h，其中0x008f即为基地址，0200即为a在该内存区的位移。它是由编译器自动添加的。因此导致以后的地址计算均不正确，使得a,b指向所在区的其他内存单元。再次，地址运算不能出现负数，即当a的地址大于b的地址时，b-a<0，系统自动采用补码的形式表示负的位移，由此会产生错误，导致与前面同样的结果。
有办法解决吗？当然！以下是改进的算法：
if(a<b)
{
a=(int*)(b-a);
b=(int*)(b-(int(a)&0x0000ffff));
a=(int*)(b+(int(a)&0x0000ffff));
}
else
{
b=(int*)(a-b);
a=(int*)(a-(int(b)&0x0000ffff));
b=(int*)(a+(int(b)&0x0000ffff));
}
算法做的最大改进就是采用位运算中的与运算“int(a)&0x0000ffff”，因为地址中高16位为段地址，后16位为位移地址，将它和0x0000ffff进行与运算后，段地址被屏蔽，只保留位移地址。这样就原始算法吻合，从而得到正确的结果。
此算法同样没有使用第三变量就完成了值的交换，与算术算法比较它显得不好理解，但是它有它的优点即在交换很大的数据类型时，它的执行速度比算术算法快。因为它交换的时地址，而变量值在内存中是没有移动过的。（以下称为地址算法）

3） 位运算
通过异或运算也能实现变量的交换，这也许是最为神奇的，请看以下代码：
int a=10,b=12; //a=1010^b=1100;
a=a^b; //a=0110^b=1100;
b=a^b; //a=0110^b=1010;
a=a^b; //a=1100=12;b=1010;
此算法能够实现是由异或运算的特点决定的，通过异或运算能够使数据中的某些位翻转，其他位不变。这就意味着任意一个数与任意一个给定的值连续异或两次，值不变。
即：a^b^b=a。将a=a^b代入b=a^b则得b=a^b^b=a;同理可以得到a=b^a^a=b;轻松完成交换。

以上三个算法均实现了不借助其他变量来完成两个变量值的交换，相比较而言算术算法和位算法计算量相当，地址算法中计算较复杂，却可以很轻松的实现大类型（比如自定义的类或结构）的交换，而前两种只能进行整形数据的交换（理论上重载“^”运算符，也可以实现任意结构的交换）。

介绍这三种算法并不是要应用到实践当中，而是为了探讨技术，展示程序设计的魅力。从中可以看出，数学中的小技巧对程序设计而言具有相当的影响力，运用得当会有意想不到的神奇效果。而从实际的软件开发看，标准算法无疑是最好的，能够解决任意类型的交换问题。

❼ 45+19-29简便方法

先加后减。45+19-29运用加减运算法则进行相应的运算的，先加后减，45+19-29得35，算法的计算量大小称为算法的，算法的计算量大小称为算法的复杂性。

❽ 跪求数据结构答案，请高手来解小弟燃眉之急，万分感谢。。。。。。

参考 31.胖子道：“这个太容易了，哎，胖爷我真是天赋异禀，和你们这些凡夫俗子怎么样都有差距，我告诉你你听好了，杀敌一个，自损三千，是香蕉和大象的战斗。”

❾ 算法时间复杂度指的是什么

时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐进的，亦即考察输入值大小趋近无穷时的情况。

空间复杂性介绍

空间复杂性是指计算所需的存储单元数量。隶属于计算复杂性（计算复杂性由空间复杂性和时间复杂性两部分组成）。算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源量称为时间复杂性，需要空间资源的量成为空间复杂性。

一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。

❿ 什么是时间复杂度、空间复杂度

1、时间复杂度是指执行算法所需要的计算工作量。

时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

2、空间复杂度是指执行这个算法所需要的内存空间。

空间复杂度需要考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。

空间复杂度也就是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2)，空间复杂度是O(1) 。

(10)算法的计算量的大小称为算法的扩展阅读：

时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；相反的当追求一个较好的空间复杂度时，就可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。

因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。