全国计算机等级考试二级公共基础知识复习.pdf

全国计算机等级考试二级公共基础知识复习题一、选择题（在下列各题的A）、B）、C）、D）四个选项中，只有一个选项是正确的，请将正确选项填涂在答题卡相应位置上。）1.1数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及A）数据的存储结构B）计算方法C）数据映象D）逻辑存储正确答案:A1.2 数据处理的最小单位是A）数据B）数据元素C）数据项D）数据结构正确答案:C1.3 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成A）动态结构和静态结构B）紧凑结构和非紧凑结构C）线性结构和非线性结构D）内部结构和外部结构正确答案:C1.4 数据结构中，与所使用的计算机无关的是数据的A）存储结构B）物理结构C）逻辑结构D）物理和存储结构正确答案:C1.5 在计算机中，算法是指A）加工方法B）解题方案的准确而完整的描述C）排序方法D）查询方法正确答案：B1.6 算法分析的目的是A）找出数据结构的合理性B）找出算法中输入和输出之间的关系C）分析算法的易懂性和可靠性D）分析算法的效率以求改进正确答案:D1.7 算法的时间复杂度是指A）执行算法程序所需要的时间B）算法程序的长度C）算法执行过程中所需要的基本运算次数D）算法程序中的指令条数正确答案:C1.8 算法的空间复杂度是指A）算法程序的长度B）算法程序中的指令条数C）算法程序所占的存储空间D）执行过程中所需要的存储空间正确答案:D1.9 链表不具有的特点是A）不必事先估计存储空间B）可随机访问任一元素C）插入删除不需要移动元素D）所需空间与线性表长度成正比正确答案:B1.10用链表表示线性表的优点是A）便于随机存取B）花费的存储空间较顺序存储少C）便于插入和删除操作D）数据元素的物理顺序与逻辑顺序相同正确答案:C （一）算法1.算法的基本概念算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可终止。1）算法的基本特征（1）可行性由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。如：计算机的数值有效位是有限的，当大数和小数进行运算时，往往会因为有效位数的影响而使小数丢失，因此，在算法设计时，应该考虑到这一点。(2)确定性算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。例如，一个实际的问题，小宝和萍萍共有12个苹果，小宝比萍萍多4 个，请问小宝和萍萍各有几个苹果？这个问题，我们可以立一(x+y=12个方程I 一 二 4 来求解，要 求 x 和 y 的值，公式是正确的，但如何让计算能够进行计算，我们的算法不能把公式直接输进去，而应该设计出解题的步骤和过程。即设计的算法是计算工具所能够正常解决问题的过程。(3)有穷性算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够正常结束。例如，在数学中的无穷级数，在计算机中只能求有限项，即计算的过程是有穷的。(4)拥有足够的情报算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。2)算法的基本要素一是数据对象的运算和操作，二是算法的控制结构。(1)算法中对数据的运算和操作算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。即算法是计算机所能够处理的操作所组成的指令序列。(2)算法的控制结构算法的功能不仅取决于所选用的操作，而且还与各操作之间的顺序有关。在算法中，操作的执行顺序又称算法的控制结构，一般的算法控制结构有三种：顺序结构、选择结构和循环结构。在算法描述是，有相关的工具对这三种结构进行描述，常用的描述工具有：流程图、N-S结构图和算法描述语言等。3)算法设计的基本方法为用计算机解决实际问题而设计的算法，即是计算机算法。通常的算法设计有如下儿种：(1)列举法列举法的基本思想是,根据提出的问题，列举出所有可能的情况,并用问题中给定的条件检验 哪些是满足条件的，哪些是不满足条件的。列举法通常用于解决“是否存在”或“有哪些可能”等问题。例 如，我国古代的趣味数学题：“百钱买百鸡”、“鸡兔同笼”等，均可采用列举法进行解决。使用列举法时，要对问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律。(2)归纳法归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。归纳是一种抽象，即从特殊现象中找出一般规律。但由于在归纳法中不可能对所有的情况进行列举，因此，该方法得到的结论只是一种猜测，还需要进行证明。(3)递推递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。递推的本质也是一种归纳，递推关系式通常是归纳的结果。例如，裴波那契数列，是采用递推的方法解决问题的。(4)递归在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进行求解，而只是当解决了最后的问题那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的方法。递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另一个算法B,而算法B又调用算法A,则此种递归称为间接递归调用。(5)减半递推技术减半递推即将问题的规模减半，然后，重复相同的递推操作。例如，一元二次方程的求解。(6)回溯法有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用无限的列举。对于这类问题，只能采用试探的方法,通过对问题的分析，找出解决问题的线索，然后沿着这个线索进行试探，如果试探成功，就得到问题的解，如果不成功，再逐步同退，换别的路线进行试探。这种方法，即称为回溯法。如人工智能中的机器人下棋。2.算法复杂度算法的复杂度包括时间复杂度和空间复杂度。1)时间复杂度即实现该算法需要的计算工作量。算法的工作量用算法所执行的基本运算次数来计算。同一个问题规模下，如果算法执行所需要的基本次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：算法工作量=f(n)(1)平均性态用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。设 X是某个可能输入中的某个特定输入，p(x)是 X出现的概率，t(x)是算法在输入为X时所执行的基本运算次数，则算法的平均性态定义为：力=XP(X)3Dn表示当规模为n时，算法执行时所有可能输入的集合。(2)最坏情况复杂度指在规模为n时,算法所执行的基本运算的最大次数。它定义为:W(ii)=maxf(x)(-)程序设计方法与风格程序设计方法：主要经过了面向过程的结构化程序设计和面向对象的程序设计方法。程序设计风格，是指编写程序时所表现出来的特点、习惯和逻辑思路。通常，要求程序设计的风格应强调简单和清晰，必须是可以读的，可以理解的。要形成良好的程序设计的风格，应考虑如下因素：1.源程序文档化(1)符号名的命名：符号名的命名要具有一定的实际含义，便于对程序的理解，即通常说的见名思义；(2)程序注释：正确的程序注释能够帮助他人理解程序。注释一般包括序言性注释和功能性注释；(3)视觉组织：为了使程序一目了然，可以对程序的格式进行设置，适当地通过空格、空行、缩进等使程序层次清晰。2.数据说明方法(1)数据说明的次序规范化；(2)说明语句中变量安排有序化；(3)使用注释来说明复杂的数据结构。3.语句的结构(1)在一行内只写一条语句；(2)程序的编写应该优先考虑清晰性；(3)除非对效率有特殊的要求，否则，应做到清晰第一，效率第二；(4)首先保证程序的正确，然后再要求速度；(5)避免使用临时变量使程序的可读性下降;(7)尽量使用库函数，即尽量使用系统提供的资源；(8)避免采用复杂的条件语句；(9)尽量减少使用“否定”条件的条件语句；(1 0)数据结构要有利于程序的简化；(1 1)要模块化，使模块功能尽可能单一化；(1 2)利用信息隐蔽，确保每一个模块的独立性；(1 3)从数据出发去构造程序；(1 4)不要修补不好的程序，要重新编写。4.输入和输出(1)对所有的输入输出数据都要检验数据的合法性；(2)检查输入项的各种重要组合的合理性；(3)输入格式要简单，以使得输入的步骤和操作尽可能简单;(4)输入数据时，应允许自由格式；(5)应允许缺省值；(6)输入一批数据时，最好使用输入结束标志;（7）以交互式输入输出方式进行输入时，要在屏幕上使用提示符明确输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息；（8）当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性;给所有的输出加注释，并设计输出报表格式。（二）结构化程序设计1.结构化程序设计的原则结构化程序设计方法的主要原则：自顶而下、逐步求精，模块化,限制使用g ot o语句。1）自顶而下程序设计时，应先考虑总体，后考虑细节；先考虑全局，后考虑局部目标。即先从最上层总目标开始设计，逐步使问题具体化。2）逐步求精对复杂问题，应设计一些子目标作为过渡，逐步细化。3）模块化一个复杂问题，都是由若干个稍简单的问题构成的。模块化即是将复杂问题进行分解，即将解决问题的总目标分解成若干个分目标，再进一步分解为具体的小目标，把每一个小目标称作一个模块。4）限制使用goto语句goto语句可以提高效率，但对程序的可读性、维护性都造成影响,因此应尽量不用goto语句。2.结构化程序设计的基本结构与特点结构化程序设计是程序设计的先进方法和工具，采用结构化程序设计可以使程序结构良好、易读、易理解、易维护。1）顺序结构顺序结构即是顺序执行的结构，是按照程序语句行的自然顺序，一条一条语句地执行程序。2）选择结构选择结构又称分支结构，它包括简单选择和多分支选择结构。程序的执行是根据给定的条件，选择相应的分支来执行。3）重复结构重复结构又称循环结构，根据给定的条件，决定是否重复执行某一相同的或类似的程序段。利用重复结构可以大量简化程序行。3.结构化程序设计原则和方法的应用1 .使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；2 .选用的控制结构只允许有一个入口和一个出口；3 .程序语句组成容易识别的块，每块只有一个入口和一个出口；4 .复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；5 .语言中所有没有的控制结构，应该采用前后一致的方法来模拟；6 .严格控制g o t。语句的使用：(1)用一个非结构化的程序设计语言去实现一个结构化的构造;(2)若不使用g o t。语句会使功能模糊；(3)在某种可以改善而不是损害程序可读性的情况(-)软件工程基本概念1.软件定义与软件特点1)软件的定义与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。2)软件的特点(1)软件是一种逻辑实体，而不是物理实体，具有抽象性；(2)软件的生产与硬件不同，它没有明显的制作过程；(3)软件在运行、使用期间不存在磨损、老化问题；但为了适应硬件、环境以及需求的变化要进行修改，会导致一些错误的引入，导致软件失效率升高，从而使得软件退化；(4)软件的开发、运行对计算机系统具有依赖性，受到计算机系统的限制，这导致了软件移植的问题；(5)软件复杂性高，成本昂贵。软件开发需要投入大量、高强度的脑力劳动，成本高，风险大；(6)软件开发涉及诸多的社会因素。许多软件的开发和运行涉及软件用户的机构设置，体制问题以及管理方式等，甚至涉及到人们的观念和心理，软件知识产权及法律等问题。3)软件的分类按功能分，可分为：应用软件：为解决特定领域的应用而开发的软件系统软件：是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件支撑软件(或工具软件)：介于系统软件和应用软件之间，协助用户开发软件的工具性软件，包括辅助和支持开发和维护应用软件的工具软件2.软件危机与软件工程1)软件危机泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。它主要表现在：(1)软件需求的增长得不到满足，用户对系统不满意的情况经常发生；(2)软件开发成本和进度无法控制。开发的成本超预算和开发周期的超期经常出现；(3)软件质量难以保证；(4)软件不可维护或维护程度非常低；(5)软件成本不断提高；(6)软件开发生产率的提高赶不上硬件的发展和应用需求的增长。2)软件工程软件工程的定义：是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素：方法、工具和过程。方法：完成软件工程项目的技术手段；工具：支持软件的开发、管理、文档生成；过程：支持软件开发的各个环节的控制、管理。3.软件工程过程与软件生命周期1)软件工程过程软件工程过程把输入转化为输出的一组彼此相关的资源和活动。支持软件工程过程的两方面内涵：(1)软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列软件工程活动。它包括4种基本活动：P软件规格说明。规定软件的功能及其运行时的限制；D软件开发。产生满足规格说明的软件；C软件确认。确认软件能够满足客户提出的要求；A软件演进过程。为满足客户的变更要求，软件必须在使用的过程中演进。（2）使用适当的资源（包括人员、硬软件工具、时间等），为开发软件进行的一组开发活动，在过程结束时将输入（用户要求）转化 为 输 出（软件产品）。软件工程过程是将软件工程的方法和工具综合起来，以达到合理、及时地进行计算机软件开发的目的。2）软件生命周期将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。即软件的生命周期就是软件产品从开始考虑其概念开始，到软件产品不能使用为止的整个时期都属于软件生命周期。一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。这些活动可以有重复，执行时也可以有迭代。生命周期的主要阶段：软件定义软件开发软件维护软件生命周期的主要活动阶段是:(1)可行性研究与计划制定：确定待开发软件系统的开发目标和总的要求，给出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成开发任务的实话计划；(2)需要分析。对待开发软件提出的需求进行分析并给出详细的定义；(3)软件设计。系统设计人员和程序设计人员给出软件的结构、模块的划分、功能的分配以及处理流程；(4)软件实现。把软件设计转换成计算机可以接受的程序代码。即完成源程序的编码，编写用户手册、操作手册等面向用户的文档，编写单元测试计划；(5)软件测试。在设计测试用例的基础上，检验软件的各个组成部分，编写测试分析报告；(6)运行和维护。将已交付的软件投入运行，并在运行使用中不断地维护，根据新提出的需求进行必要且可能的扩充和删改。4.软件工程的目标与原则1)软件工程的目标软件工程的目标：在给定成本、进度的情况下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。软件工程需要达到的基本目标：付出较低的开发成本达到要求的软件功能取得较好的软件性能开发的软件易于移植需要较低的维护费用能按时完成开发，及时交付使用软件工程的理论和技术性研究的内容包括：软件开发技术和软件工程管理。(1)软件开发技术软件开发方法学、开发过程、开发工具和软件工程环境，其主体内容是软件开发方法学。软件开发方法学是根据不同的软件类型，按不同的观点和原则，对软件开发中应遵循的策略、原则、步骤和必须产生的文档资料都做出规定，从而使软件开发能够进入规范化和工程化的阶段。(2)软件工程管理软件工程管理：软件管理学、软件工程经济学、软件心理学等内容。软件工程管理学包括：人员组织、进度安排、质量保证、配置管理、项目计划等。软件工程经济学：是研究软件开发中成本的估算、成本效益分析的方法和技术，用经济学的基本原理事研究软件工程开发中的经济效益问题。软件心理学：从个体心理、人类行为、组织行为和企业文化等角度来研究软件管理和软件工程。(-)数据库系统的基本概念1.数据、数据库、数据库管理系统1)数据数据是指存储在某一种媒体上能够被识别的物理符号，即描述事物的符号记录。数据是有结构的。首先，数据有型与值的区别，型即类型，值是符合指定类型的值。数据的概念在数据处理领域中已经大大地拓宽了。数据不仅包括数字、字母、文字和其他特殊字符组成的文本形式的数据，而且还包括图形、图像、动画、影像、声音等多媒体数据。但是使用最多、最基本的仍然是文字数据。2)数据库数 据 库(DataBase,D B),是存储在计算机存储设备上，结构化的相互关联的数据的集合。它不仅包括描述事物的数据本身，而且还包括相关事物之间的联系。它用综合的方法组织和管理数据，具有较小的数据冗余，可供多个用户共享，具有较高的数据独立性，具有安全机制，能够保证数据的安全、可靠，允许并发地使用数据库，能有效、及时地处理数据，并能保证数据的一致性和完整性。例如，某个学校的相关数据，如学生基本情况、选课情况、学籍管理等所涉及的相关数据的集合。3)数据库管理系统数据库管理系统(DataBase Management System,DBM S)是对数据库进行管理的系统软件，它的职能是有效地组织和存储数据、获取和管理数据，接受和完成用户提出的访问数据的各种请求。同时还能保证数据的安全性、可靠性、完整性、一致性，还要保证数据的高度独立性。数据库管理系统主要功能包括以下几个方面：(1)数据模式定义数据库管理系统负责为数据库构建模式，也为数据库构建其数据框架。(2)数据存取的物理构建数据库管理系统负责为数据模式的物理存取及构建提供有效的存取方法和手段。(3)数据操纵数据库管理系统为用户使用数据库中的数据提供方便，一般提供查询、插入、修改和删除数据的功能，此外，还具有简单的算术运算和统计功能，还具有专长强大的程序控制功能。(4)数据的完整性、安全性定义与检查数据库中的数据具有内存语义上的关联性与一致性，即数据的完整性。数据的完整性是保证数据库中数据正确的必要条件。(5)数据的并发控制与故障恢复数据库是一个集成、共享的数据集合体，它能为多个应用程序服务，因此，当多个应用程序对数据库并发操作时，要保证数据不被破坏。(6)数据的服务数据库管理系统提供了对数据库中数据的多种服务，如数据拷贝、转存、重组、性能监测、分析等。数据库管理系统提供的相应的数据语言包括如下：1)数据定义语言(Data Definition Language,DDL)D用户通过它可以方便地对数据库中的相关内容进行定义。例如，对数据库、表、索引进行定义。2)数据操纵语言(Data Manipulation Language,DML)用户通过它可以实现对数据库的基本操作。例如，对表中数据的查询、插入、删除和修改。3)数据控制语言(Data Control Language,DCL)负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能，包括系统初启程序、文件读写与维护程序、存取路径管理程序、缓冲区管理程序、安全性控制程序、完整性检查程序、并发控制程序、事务管理程序、运行日志管理程序、数据库恢复程序等。目前流行的DBMS均为关系型数据库系统，发ORACLE、Sybase的PowerBuilder及 IBM的DB2、微软件的SQLServer等。还有一些小型的数据库，如 Visual FoxPro和 Access等。4)数据库管理员数据库的管理员(DataBase Administrator,D B A)：对数据库的规划、设计、维护、监视等进行管理。主要工作如下：(1)数据库设计(2)数据库维护(3)改善系统性能，提高系统效率5)数据库系统数据库系统(DataBase System,D B S)由如下几个部分组成：库 应 用 系 丁、/库 管 理 嬴、I(厂噪作系)数据库系统的蛆成数据库(数据)数据库管理系统（软件）数据库管理员（人员）系统平台（硬件平台和软件平台）硬件平台包括：计算机网络软件平台包括：操作系统数据库系统开发工具接口软件第一章数据结构与算法1.1 算法1、算法是指解题方案的准确而完整的描述。换句话说，算法是对特定问题求解步骤的一种描述。*:算法不等于程序，也不等于计算方法。程序的编制不可能优于算法的设计（注释1）。2、算法的基本特征(1)可行性。针对实际问题而设计的算法，执行后能够得到满意的结果。(2)确定性。每一条指令的含义明确，无二义性。并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。(3)有穷性。算法必须在有限的时间内完成。有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。(4)拥有足够的情报。算法中各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这就是算法执行的起点或依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法将无法执行或执行有错。一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。*：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。3、算法复杂度主要包括时间复杂度和空间复杂度。(1)算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。(2)算法空间复杂度是指执行这个算法所需要的内存空间。(注 释1)这是因为：在编写程序时要受到计算机系统运行环境的限制，程序通常还要考虑很多与方法和分析无关的细节问题。1.2数据结构的基本概念1、数据结构是指相互有关联的数据元素的集合。2、数据结构主要研究和讨论以下三个方面的问题：(1)数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。数据的逻辑结构包含：1)表示数据元素的信息；2)表示各数据元素之间的前后件关系(注 释1)。(2)在对数据进行处理时，各数据元素在计算机中的存储关系,即数据的存储结构。数据的存储结构有顺序、链接、索引等。1）顺序存储。它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。2）链接存储。它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。3）索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。*：数据的逻辑结构反映数据元素之间的逻辑关系，数据的存储结 构（也称数据的物理结构）是数据的逻辑结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以采用不同的存储结构，但影响数据处理效率。（3）对各种数据结构进行的运算。3、数据结构的图形表示一个数据结构除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；为了进一步表示各数据元素之间的前后件关系，对 于 关 系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。4、数据结构分为两大类型：线性结构和非线性结构。（1）线 性 结 构（非空的数据结构）条件：1）有且只有一个根结点（注 释2）；2）每一个结点最多有一个前件，也最多有一个后件。*：常见的线性结构有线性表、栈、队列和线性链表等。（2）非线性结构：不满足线性结构条件的数据结构。*：常见的非线性结构有树、二叉树和图等。（注 释1）前后件关系：一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（即直接前驱与直接后继关系）来描述。（注 释2）在数据结构中，没有前件的结点称为根结点。1.3线性表及其顺序存储结构1、线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。线性表是由n（n K）个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。线性表中数据元素的个数称为线性表的长度。线性表可以为空表。*:线性表是一种存储结构，它的存储方式：顺序和链式。2、线性表的顺序存储结构具有两个基本特点：(1)线性表中所有元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。*：由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面，可以通过计算机直接确定第i 个结点的存储地址。3、顺序表的插入、删除运算(学吧学吧独家稿件)(1)顺序表的插入运算：在一般情况下，要在第i (l i n)个元素之前插入一个新元素时，首先要从最后一个(即第n个)元素开始，直到第i 个元素之间共n-i+1 个元素依次向后移动一个位置，移动结束后，第 i 个位置就被空出，然后将新元素插入到第i 项。插入结束后，线性表的长度就增加了 l o*:顺性表的插入运算时需要移动元素，在等概率情况下，平均需要移动n/2 个兀素。(2)顺序表的删除运算：在一般情况下，要删除第i (l i l,则该结点的父结点的编号为I N T(k/2)o 若2kSn,则编号为k的左子结点编号为2k;否则该结点无左子结点（显然也没有右子结点）。若2k+lSn,则编号为k的右子结点编号为2k+l;否则该结点无右子结点。4、二叉树的存储结构在计算机中，二叉树通常采用链式存储结构。与线性链表类彳以，用于存储二叉树中各元素的存储结点也由两部分组成：数据域和指针域。但在二叉树中，由于每一个元素可以有两个后件（即两个子结点），因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域;另一个用于指向该结点的右子结点的存储地址，称为右指针域。*：一般二叉树通常采用链式存储结构，对于满二叉树与完全二叉树来说，可以按层序进行顺序存储（注 释1）o5、二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种:(1)前序遍历(DLR)：若二叉树为空，则结束返回。否则：首先访问根结点，然后遍历左子树，最后遍历右子树;并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。(2)中序遍历(LDR)：若二叉树为空，则结束返回。否则：首先遍历左子树，然后访问根结点，最后遍历右子树;并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。(3)后序遍历(LRD)：若二叉树为空，则结束返回。否则：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。注 释1：这样，不仅节省了存储空间，又能方便地确定每一个结点的父结点与左右子结点的位置，但顺序存储结构对于一般的二叉树不适用。1.7查找技术查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。查找结果：(查找成功：找到；查找不成功：没找到。)平均查找长度：查找过程中关键字和给定值比较的平均次数。1、顺序查找基本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。在平均情况下，利用顺序查找法在线性表中查找一个元素，大约要与线性表中一半的元素进行比较，最坏情况下需要比较n次。顺序查找一个具有n个元素的线性表，其平均复杂度为O（n）。下列两种情况下只能采用顺序查找：1）如果线性表是无序表（即表中的元素是无序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。2、二分法查找思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。查找过程：1）若 中 间 项（中间项mid=（n-l）/2,m id的值四舍五入取整）的值等于x,则说明已查到;2）若x小于中间项的值，则在线性表的前半部分查找;3）若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。*：二分法查找只适用于顺序存储的线性表，且表中元素必须按关键字有序（升序）排 列（注 释1）o对于无序线性表和线性表的链式存储结构只能用顺序查找。在长度为n的有序线性表中进行二分法查找，其时间复杂度为O（log2n）。注 释1:允许相邻元素值相等。1.8排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列，即是将无序的记录序列调整为有序记录序列的一种操作。1、交换类排序法（方法：冒泡排序，快速排序）。2、插入类排序法（方法：简单插入排序，希尔排序）。3、选择类排序法（方法：简单选择排序，堆排序）。总结：各种排序法比较:卖则1#序方法国太思恐时间复东度交柒交泡持序*瞄元素比较，不满足条件时交柒快速挎序选择基准元素，通过交柒，划分成两个子序列O(n k )n)抽入突简单插入排序待持序的元素看成为一个有序表和一个无序表，将无序表中元素茹入到有序表中希尔排序分割成若干个子序列分别进行直接独入持序0(。透绛类简单选择排序指整个线性表，从中选出最小的元素，将它交轶到表的量而面堆排序逸建堆，然后将堆顶元素与城中最后一个元素交换，再调整为堆O(n k n)本章应考点拨：本章内容在笔试中会出现5-6个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10分。2.1程序设计风格程序设计的风格主要强调：“清晰第一，效率第二”（注 释1）。主要应注重和考虑下述一些因素：（1）源程序文档化。1）符号名的命名。符号名能反映它所代表的实际东西，应有一定的实际含义。2）程序的注释。分为序言性注释和功能性注释。序言性注释：位于程序开头部分，包括程序标题、程序功能说明、主要算法、接口说明、程序位置、开发简历、程序设计者、复审者、复审日期及修改日期等。功能性注释：嵌在源程序体之中，用于描述其后的语句或程序的主要功能。3）视觉组织。利用空格、空行、缩进等技巧使程序层次清晰。（2）数据说明。1）数据说明的次序规范化；2）说明语句中变量安排有序化；3）使用注释来说明复杂数据的结构。（3）语句的结构。1）在一行内只写一条语句；2）程序编写应优先考虑清晰性；3）程序编写要做到清晰第一，效率第二；4）在保证程序正确的基础上再要求提高效率；5）避免使用临时变量而使程序的可读性下降；6）避免不必要的转移；7）尽量使用库函数；8）避免采用复杂的条件语句;9）尽量减少使用“否定”条件语句；10）数据结构要有利于程序的简化；11）要模块化，使模块功能尽可能单一化；12）利用信息隐蔽（注释2）,确保每一个模块的独立性；13）从数据出发去构造程序；14）不要修补不好的程序，要重新编写。（4）输入和输出。1）对输入数据检验数据的合法性；2）检查输入项的各种重要组合的合法性；3）输入格式要简单，使得输入的步骤和操作尽可能简单;4）输入数据时，应允许使用自由格式；5）应允许缺省值；6）输入一批数据时，最好使用输入结束标志;7）在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息；8）当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。注 释 1：“清晰第一，效率第二”是当今主导的程序设计风格。注 释 2：信息隐蔽是指采用封装技术，将程序模块的实施细节隐藏起来，使模块接口尽量简单。即指在设计和确定模块时，使得一个模块内包含的信息（过程或数据），对于不需要这些信息的其它模块来说，是不能访问的。2.2 结构化程序设计（面向过程的程序设计方法）1、结构化程序设计方法的主要原则可以概括为：自顶向下，逐步求精，模块化，限制使用g o t。语句。（1）自顶向下。程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节,先从最上层总目标开始设计，逐步使问题具体化。（2）逐步求精。对复杂问题，应设计一些子目标作过渡，逐步细化。(3)模块化。一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。(4)限制使用goto语句。2、结构化程序的基本结构：顺序结构，选择结构，重复结构。1)顺序结构。一种简单的程序设计，即按照程序语句行的自然顺序，一条语句一条语句地执行程序，它是最基本、最常用的结构。2)选择结构。又称分支结构，包括简单选择和多分支选择结构,可根据条件，判断应该选择哪一条分支来执行相应的语句序列。3)重复结构。又称循环结构，可根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段。仅仅使用顺序、选择和循环三种基本控制结构就足以表达各种其他形式结构，从而实现任何单入口/单出口的程序。2.3面向对象的程序设计客观世界中任何一个事物都可以被看成是一个对象，面向对象方法的本质就是主张从客观世界固有的事物出发来构造系统，提倡人们在现实生活中常用的思维来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域。也就是说，系统中的对象及对象之间的关系能够如实地反映问题域中固有的事物及其关系。面向对象方法的主要优点：(1)与人类习惯的思维方法一致；(2)稳定性好；(3)可 重 用(注 释1)性好；(4)易于开发大型软件产品；(5)可维护性好。*：面向对象的程序设计主要考虑的是提高软件的可重用性。对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。面向对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。对象是属性和方法的封装体。属性即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。操作描述了对象执行的功能，操作也称为方法或服务。操作是对象的动态属性。*:一个对象由对象名、属性和操作三部分组成。对象的基本特点：标识惟一性，分类性，多态性，封装性，模块独立性好。(1)标识惟一性。指对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分。(2)分类性。指可以将具有相同属性的操作的对象抽象成类。(3)多态性。指同一个操作可以是不同对象的行为。(4)封装性。从外面看只能看到对象的外部特性，即只需知道数据的取值范围和可以对该数据施加的操作，根本无需知道数据的具体结构以及实现操作的算法。对象的内部，即处理能力的实行和内部状态，对外是不可见的。从外面不能直接使用对象的处理能力，也不能直接修改其内部状态，对象的内部状态只能由其自身改变。*：信息隐蔽是通过对象的封装性来实现的。(5)模块独立性好。对象是面向对象的软件的基本模块，它是由数据及可以对这些数据施加的操作所组成的统一体，而且对象是以数据为中心的，操作围绕对其数据所需做的处理来设置，没有无关的操作。从模块的独立性考虑，对象内部各种元素彼此结合得很紧密，内聚性强。类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。消息是一个实例与另一个实例之间传递的信息。消息的组成包括：（1）接收消息的对象的名称；（2）消息标识符，也称消息名；（3）零个或多个参数。*：在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送消息。继承是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重继承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。*：类的继承性是类之间共享属性和操作的机制，它提高了软件的可重用性。多态性是