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

全国计算机等级考试二级公共基础知识复习题一、选择题（在下列各题的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考试大正式启用新域名233.com（一）算法1．算法的基本概念算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可终止。1）算法的基本特征（1）可行性由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。如：计算机的数值有效位是有限的，当大数和小数进行运算时，往往会因为有效位数的影响而使小数丢失，因此，在算法设计时，应该考虑到这一点。（2）确定性算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。例如，一个实际的问题，小宝和萍萍共有12个苹果，小宝比萍萍多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时所执行的基本运算次数，则算法的平均性态定义为：Dn表示当规模为n时，算法执行时所有可能输入的集合。（2）最坏情况复杂度指在规模为n时，算法所执行的基本运算的最大次数。它定义为：（一）程序设计方法与风格程序设计方法：主要经过了面向过程的结构化程序设计和面向对象的程序设计方法。程序设计风格，是指编写程序时所表现出来的特点、习惯和逻辑思路。通常，要求程序设计的风格应强调简单和清晰，必须是可以读的，可以理解的。要形成良好的程序设计的风格，应考虑如下因素：1．源程序文档化（1）符号名的命名：符号名的命名要具有一定的实际含义，便于对程序的理解，即通常说的见名思义；（2）程序注释：正确的程序注释能够帮助他人理解程序。注释一般包括序言性注释和功能性注释；（3）视觉组织：为了使程序一目了然，可以对程序的格式进行设置，适当地通过空格、空行、缩进等使程序层次清晰。2．数据说明方法（1）数据说明的次序规范化；（2）说明语句中变量安排有序化；（3）使用注释来说明复杂的数据结构。3．语句的结构（1）在一行内只写一条语句；（2）程序的编写应该优先考虑清晰性；（3）除非对效率有特殊的要求，否则，应做到清晰第一，效率第二；（4）首先保证程序的正确，然后再要求速度；（5）避免使用临时变量使程序的可读性下降；（7）尽量使用库函数，即尽量使用系统提供的资源；（8）避免采用复杂的条件语句；（9）尽量减少使用“否定”条件的条件语句；（10）数据结构要有利于程序的简化；（11）要模块化，使模块功能尽可能单一化；（12）利用信息隐蔽，确保每一个模块的独立性；（13）从数据出发去构造程序；（14）不要修补不好的程序，要重新编写。4．输入和输出（1）对所有的输入输出数据都要检验数据的合法性；（2）检查输入项的各种重要组合的合理性；（3）输入格式要简单，以使得输入的步骤和操作尽可能简单；（4）输入数据时，应允许自由格式；（5）应允许缺省值；（6）输入一批数据时，最好使用输入结束标志；（7）以交互式输入输出方式进行输入时，要在屏幕上使用提示符明确输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息；（8）当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。（二）结构化程序设计1．结构化程序设计的原则结构化程序设计方法的主要原则：自顶而下、逐步求精，模块化，限制使用goto语句。1）自顶而下程序设计时，应先考虑总体，后考虑细节；先考虑全局，后考虑局部目标。即先从最上层总目标开始设计，逐步使问题具体化。2）逐步求精对复杂问题，应设计一些子目标作为过渡，逐步细化。3）模块化一个复杂问题，都是由若干个稍简单的问题构成的。模块化即是将复杂问题进行分解，即将解决问题的总目标分解成若干个分目标，再进一步分解为具体的小目标，把每一个小目标称作一个模块。4）限制使用goto语句goto语句可以提高效率，但对程序的可读性、维护性都造成影响，因此应尽量不用goto语句。2．结构化程序设计的基本结构与特点结构化程序设计是程序设计的先进方法和工具，采用结构化程序设计可以使程序结构良好、易读、易理解、易维护。1）顺序结构顺序结构即是顺序执行的结构，是按照程序语句行的自然顺序，一条一条语句地执行程序。2）选择结构选择结构又称分支结构，它包括简单选择和多分支选择结构。程序的执行是根据给定的条件，选择相应的分支来执行。3）重复结构重复结构又称循环结构，根据给定的条件，决定是否重复执行某一相同的或类似的程序段。利用重复结构可以大量简化程序行。3．结构化程序设计原则和方法的应用1．使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；2．选用的控制结构只允许有一个入口和一个出口；3．程序语句组成容易识别的块，每块只有一个入口和一个出口；4．复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；5．语言中所有没有的控制结构，应该采用前后一致的方法来模拟；6．严格控制goto语句的使用：（1）用一个非结构化的程序设计语言去实现一个结构化的构造；（2）若不使用goto语句会使功能模糊；（3）在某种可以改善而不是损害程序可读性的情况（一）软件工程基本概念1．软件定义与软件特点1）软件的定义与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。2）软件的特点（1）软件是一种逻辑实体，而不是物理实体，具有抽象性；（2）软件的生产与硬件不同，它没有明显的制作过程；（3）软件在运行、使用期间不存在磨损、老化问题；但为了适应硬件、环境以及需求的变化要进行修改，会导致一些错误的引入，导致软件失效率升高，从而使得软件退化；（4）软件的开发、运行对计算机系统具有依赖性，受到计算机系统的限制，这导致了软件移植的问题；（5）软件复杂性高，成本昂贵。软件开发需要投入大量、高强度的脑力劳动，成本高，风险大；（6）软件开发涉及诸多的社会因素。许多软件的开发和运行涉及软件用户的机构设置，体制问题以及管理方式等，甚至涉及到人们的观念和心理，软件知识产权及法律等问题。3）软件的分类按功能分，可分为：应用软件：为解决特定领域的应用而开发的软件系统软件：是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件支撑软件（或工具软件）：介于系统软件和应用软件之间，协助用户开发软件的工具性软件，包括辅助和支持开发和维护应用软件的工具软件2．软件危机与软件工程1）软件危机泛指在计算机软件的开发和维护过程中