计算机二级公共基础知识-[免费下载]

由天下分享时间：2024/10/30 11:01:44 加入收藏我要投稿点赞

空为止。

简单选择排序法在最坏情况下需要比较n(n-1)/2/次。２、堆排序法方法：（1）首先将一个无序序列建成堆。

（2）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调事为堆。反复做第（2）步，真到剩下的子序列为空为止。适用规模较大的线性表，在最坏情况下，堆排序需要比较的次数为O（nlog2n）。习题一一、选择题

1、算法的时间复杂度是指（）

A）执行算法程序所需要的时间 B）算法程序的长度

C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 2、算法的窨复杂度是指（）

A、算法程序的长度 B、算法程序中的指令条数

C、算法程序所占的存储空间 D、算法执行过程中所需要的存储空间 3、下列叙述中正确的是（）

A、线性表是线性结构 B、材与队列是非线性结构 C、线性链表是非线性结构 D、二叉树是线性结构 4、数据的存储结构是指（）

A、数据所占的存储空间量 B、数据的逻辑结构在计算机中的表示 C、数据在计算机中的顺序存储方式 D、存储在外存中的数据 5、下列关于队列的叙述中正确的是（）

A、在队列中只能插入数据 B、在队列中只能删除数据 C、队列是先进先出的线性表 D、队列是先进后出的线性表 6、下列关于栈的叙述中正确的是（）

A、在栈中只能插入数据 B、在栈中只能删除数据 C、栈是先进先出的线性表 D、栈是先进后出的线性表 7、设有下列二叉树：

对此二叉树中序遍历的结果为

A、ABCDEF B、DBEAFC C、ABDECF D、DEBFCA 8、在深度为5的满二叉树中，叶子结点的个数为（）

A、32 B、31 C、16 D、15 9、对长度为 n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（） A、 n+1 B、n C、(n+1)/2 D、n/2

10、设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则T中的叶子结点数为（） A、8 B、7 C、6 D、5 二、填空题

1、在长度为n 的有序线性表中进行二分查找，需要的比较次数为。 2、设一棵完全二叉共有700个结点，则在该二叉树中有个叶子结点。

3、设一棵二叉树中序遍历结果为DBEAFC ，前序遍历结果为ABDECF，则后序遍历结果为。 4、在最坏情况下，冒泡排序的时间复杂度为。

5、在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有个元

第2章程序设计基础 2．1 程序设计方法与风格

就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。

一般来讲。程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是由人来编写的，为了测试和维护程序，往往还要新闻记者和跟踪程序，因此程序设计的风格总体而言应该强调得意和清晰，程序必须是可以理解的。要形成良好的程序设计风格，主要应注重和考虑下述一些因素。 1、源程序文档化

2、源程序文档化应考虑如下几点：

（1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解。

（2）程序注释：下克的注释能够帮助读者理解程序。

（3）礼堂组织：为使程序的结构一目了然，可以在程序中利用空格、空行、缩进待技巧使程序层次清晰。 2、数据说明的方法

在编写程序时，需要注意数据说明的风格，以便使程序中的数据说明更易于理解和维护。一般应注意如下几点：

（1）数据说明的次序规范化鉴于程序理解、新闻记者和维护的需要，使数据说明次序固定，可以使数据的发生容易查找，也有利于测试、排错和维护。

（2）说明语句中变量安排有序化。当一个说明语句说明多个变量时，变量按照字母顺序为好。（3）使用注释来说明复杂数据的结构。 3、语句的结构

程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。一般应注意如下：（1）在一行内只写一条语句；（2）程序编写应优先考虑清晰性；

（3）除非对效率有特殊要求，程序编写要做清晰第一，效率第二；（4）首先要保证程序正确，然后才要求提高速度；（5）避免使用临时变量而使程序的可读性下降；（6）避免不必要的转移；（7）尽可能使用库函数；

（8）避免采用复杂的条件语句；

（9）尽量减少使用“否定”条件的条件语句；（10）数据结构要有利于程序的简化；

（11）要模块化，使模块功能尽可能单一化；

（12）利用住处隐蔽，确保每一个模块的独立性；（13）从数据出发去构造程序；

（14）不要修补不好的程序，要重新编写； 4、输入和输出

无论是批处理的输入和输出方式，还是交互式的输入和输出方式，在设计和编程时都应该考虑如下原则：（1）对所有的输入数据都要检验数据的合法性；（2）检查输入项的各种重要组合的合理性；

（3）输入格式要简单，以使得输入的步骤和操作尽可能简单；（4）输入数据时，应允许使用自由格式；（5）应允许缺省值；

（6）输入一批数据时，最好使用输入结束标志；

（7）在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中的输入结束时，应在屏幕上给出状态信息。

（8）当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输入出加注释，并设计输出报表格式。 2．2结构化程序设计

一、结构化程序设计的原则

结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。

1、自顶向下：程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标。不要一开始就过多追求众多的细节，先从最上层总目标开始设计，逐步使问题具体化。

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

3、模块化：一个复杂问题，肯定是由若干稍简单的问题构成。模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。 4、限制使用goto语句使用goto语句经实验证实：（1）滥用GOTO语句确实有害，应昼避免；

（2）完全避免使用GOTO语句也并非是个明智的方法，有些地方使用GOTO语句，会使程序流程更清楚、效率更高；（3）争论的焦点不应该放在是否取消GOTO语句，而应该放在用什么样的程序结构上。其中最关键的是，肯定以提高程序清晰性为目标的结构化方法。二、结构化程序的基本结构与特点

1、顺序结构：顺序结构是简单的程序设计，它是最基本、最常用的结构，所谓顺序执行，就是按照程序语句行的自然顺序，一条语句一条语句地执行程序程序。

2、选择结构：选择结构又称为分支结构，它包括简单选择和多分支选择结构，这种结构可以根据设定的条件，判断应该选择哪一条分支来执行相应的语句序列。

3、重复结构：重复结构又称为循环结构，它根据给定的条件，判断是否需要重复执行某一相同的或类似的程序段，利用重复结构可简化大量的程序行。分为两类：一是先判断后执行，一是先执行后判断。优点：一是程序易于理解、使用和维护。二是编程工作的效率，降低软件开发成本。三、结构化程序设计原则和方法的应用要注意把握如下要素：

1、使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑。 2、选用的控制结构只准许有一个入口和一个出口；

3、程序语句组成容易识别的块，每块只有一个入口和一个出口； 4、复杂结构应该嵌套的基本控制结构进行组合嵌套来实现； 5、语言中所没有的控制结构，应该采用前后一致的方法来模拟； 6、严格控制GOTO语句的使用。其意思是指：

（1）用一个非结构化的程序设计语言去实现一个结构化的构造；（2）若不使用GOTO语句会使功能模糊；

（3）在某种可以改善而不损害程序可读性的情况下。 2．3面向对象的程序设计一、关于面向对象方法

面向对象方法的本质，就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域，也就是说，系统中的对象以及对象之间的关系能够如实地反映问题域中固有事物及其关系。

优点：1、与人类习惯的思维方法一致

面向对象方法和技术以对象为核心。对象是由数据和容许的操作组成的封装体，与客观实体有直接的关系。对象之间通过传递消息互相联系，以模拟现实世界中不同事物彼此之间的联系。

面向对象的设计方法与传统的面向过程的方法有本质不同，这种方法的基本原理是：使用现实世界的概念抽象地思考问题从而自然地解决问题。它强调模拟现实世界中的概念而不强调算法，它鼓励开发者在软件开发的绝大部分过程中都用应用领域的要领去思考。 2、稳定性好 3、可重用性好

软件重用是指在不同的软件开发过程中重复作用相同或相似软件元素的过程。重用是提高软件生产率的最主要的方法。 4、易于开发大型软件产品 5、可维护性好

（1）用面向对象的方法开发的软件稳定性比较好（2）用面向对象的方法开发的软件比较容易修改；（3）用面向对象的方法开发的软件比较容易理解。（4）易于测试和调试。

二、面向对象方法的基本概念 1、对象（object）

对象是面向对象方法中最基本的概念。对象可以用来表示客观世界中的任何实体，也就是说，应用领域中有意义的、与所要解决的问题有关系的任何事物都可以作为对象，它既可以是具体的物理实体的抽象，也可以是人为的概念，或者是任何有明确边界的意义的东西。总之，对象是对问题域中某个实体的抽象，设立某个对象就反映软件系统保存有关它的信息并具有与它进行交互的能力。

面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。

对象可以做的操作表示它的动态行为，在面向对象分析和面向对象设计中，通常把对象的操作也称为方法或服务。属性即对象所包含的信息，它在设计对象时确定，一般只能通过挂靠对象的操作来改变。

操作描述了对象执行的功能，若通过消息传递，还可以为其他对象使用。操作的过程对外是封闭的，即用户只能看到这一操作实施后的结果。这相当于事先已经设计好的各种过程，只需要调用就可以了，用户不必去关心这一过程是如何编写的。事实上，这个过程已经封装在对象中，用户也看不到。对的这一特性即是对象的封装性。对象有如下一些基本特点：

（1）标识惟一性。指对象是可区分的，并且由对象有的内在本质来区分，而不是通过描述来区分。（2）分类性。指可以将具有相同属性的操作的对象抽象成类。

（3）多太性。指同一个操作可以是不同对象的行为。

（4）封装性。从外面看只能看到对象的外部特性，即只需知道数据的取值范围和可以对该数据施加的操作，根本无需知道数据的具体结构以及实现操作的算法。对象的内部，即处理能力的实行和内部状态，对外是不可见的。从外面不能直接使用对象的处理能力，也不能直接修改其内部状态，对象的内部状态只能由其自身改变。

（5）模块独立性好。对象是面向对象的软件的基本模块，它是由数据及可以对这些数据施加的操作所组成的统一体，而且对象是以数据为中心的，操作围绕对其数据所需做的处理来设置，没有无关的操作从模块的独立性考虑，对象内部各种元素彼此结合得很紧密，内聚性强。 2、类（Class）和实例(Instance)

将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法的对象的集合。所以，类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。

要注意的是，当使用“对象”这个术语时，既可以指一个具体的对象，也可以泛指一般的对象，但是，当使用“实例”这个术语时，必然是指一个具体的对象。例如：Integer是一个整数类，它描述了所有整数的性质。因此任何整数都是整数类的对象，而一个具体的整数“123”是类Integer的实例。

由类的定义可知，类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。 3、消息（Message）

面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。消息是一个实例与另一个实例之间传递信息，它请示对象执行某一处理或回答某一要求的信息，它统一了数据流的控制流。消息的使用类似于函数调用，消息中指定了某一个实例，一个操作名和一个参数表（可空）。接收消息的实例执行消息中指定的操作，并将形式参数数与参数表中相应的值结合起来。消息传递过程中，由发送消息的对象（发送对象）的触发操作产生输出结果，作为消息传送至接受消息的对象（接受对象），引发接受消息的对象一系列的操作。所传送的消息实质上是接受对象所具有的操作/方法名称，有时还包括相应参数。

消息中只包含传递者的要求，它告诉接受者需要做哪些处理，但并不指示接受者应该怎样完成这些处理。消息完全由接受者解释，接受者独立决定采用什么方式完成所需的处理，发送者对接受者不起任何控制作用。一个对象能够接受不同形式、不同内容的多个消息；相同形式的消息可以送往不同的对象，不同的对象对于形式相同的消息可以有不同的解释，能够做出不同的反映。一个对象可以同时往多个对象传递信息，两个对象也可以同时向某个对象传递消息。例如，一个汽车对象具有“行驶”这项操作，那么要让汽车以时速50公里行驶的话，需传递给汽车对象“行驶”及“时速50公里”的消息。

通常，一个消息由下述三部分组成：（1）接收消息的对象的名称；（2）消息标识符（也称为消息名）；（3）零个或多个参数。 4、继承（Inheritance）

继承是面向对象的方法的一个主要特征。继承是使用己有的类定义作为基础建立新类的定义技术。已有的类可当作基类来引用，则新类相应地可当作派生类来引用。

广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。

面向对象软件技术的许多强有力的功能和突出的优点，都来源于把类组成一个层次结构的系统：一个类的上层可以有父类，下层可以有子类。这种层次结构系统的一个重要性质是继承性，一个类直接继承其父类的描述（数据和操作）或特性，子类自动地共享基类中定义的数据和方法。继承具有传递性，如果类C继承类B，类B继承类A，则类C继承类A。因此一个类实际上继承了它上层的全部基类的特性，也就是说，属于某类的对象除了具有该类所定义的特性外，还具有该类上层全部基类定义的特性。

继承分为单继承与多重继承。单继承是指，一个类只允许有一个父类，即类等级为树形结构。多重继承是指，一个类允许有多个父类。多重继承的类可以组合多个父类的性质构成所需要的性质。因此，功能更强，使用更方便；便是，使用多重继承时要注意避免二义性。继承性的优点是，相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余信息，提高软件的可重用性，便于软件个性维护。此外，继承性便利用户在开发新的应用系统时不必完全从零开始，可以继承原有的相似系统的功能或者从类库中选取需要的类，再派生出新的类以实现所需要的功能。 5、多太性（Polymorphism）

对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。在面向对象的软件技术中，多态性是指类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。多态性机制不仅增加了面向对象软件系统的灵活性，进一步减少了信息冗余，而且显著地提高了软件的可重用性和可扩充性。当扩充系统功能增加新的实体类型时，只需派生出与新实体类相应的新的子类，完全无需修改原有的程序代码，甚至不需要重新编译原有的程序。利用多态性，用户能够发送一般形式的消息，而将所有的实现细节都留给接受消息的对象。

第3章软件工程基础 3．1软件工程基本概念一、软件定义与软件特点

计算机软件是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。基中，程序是软件开发人员根据用户需求开发的用程序设计语言描述的、适合计算机执行的指令（语句）序列。数据是使程序能正常操纵信息的数据结构。文档是与程序开发、

维护和使用有关的图文资料。可见软件由两部分组成：一是机器可执行的程序和数据；二是机器不可执行的，与软件开发、运行、维护、使用等有关的文档。

国标（GB）中对计算机软件的定义为：与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。

软件在开发、生产、维护和使用等方面与计算机硬件相比存在明显的差异。深入理解软件的定义需要了解软件的特点：（1）软件是一种逻辑实体，而不是物理实体具有抽象性。

（2）软件的生产与硬件不同，它没有明显的制作过程。一旦研制开发成功，可以大量拷贝同一内容的副本。所以对软件的控制，必须着重在软件开发方面下功夫。

（3）软件在运行、使用期间不存在磨损、老化问题。

（4）软件的开发运行对计算机系统具有依赖性，受计算机系统的限制这导致了软件移植的问题。（5）软件复杂性高，成本昂贵。（6）软件开发涉及诸多的社会因素。

软件按功能可以分为：应用软件、系统软件、支撑软件（或工具软件）。应用软件是为解决特定领域的应用而开发的软件。系统软件是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件。支撑软件是介于系统软件和应用软件之间，协助用户开发软件的工具性软件，包括辅助和支持开发和维护应用软件的工具软件。二、软件危机与软件工程

软件工程概念的出现源自软件危机。

所谓有软件危机四伏是泛指在计算机软件开发和维护过程中所遇到的严重问题。实际上，几科所有的软件都不同程度地存在这些问题。

随着计算机技术的发展和应用领域的扩大，计算机硬件性能/价格比和质量稳步提高，软件规模越来越大，复杂程度不断增加，软件成本逐年上升，质量没有可靠的保证，软件已成为计算机科学发展的“瓶颈”。具体地说，在软件开发和维护过程中，软件危机主要表现在：

（1）软件需求的增长得不到满足。用户对系统不满意的情况经常发生。

（2）软件开发成本和进度无法控制。开发成本超出预算，开发周期大大超过规定日期的情况经常发生。（3）软件质量难以保证。

（4）软件不可维护或护程度非常低。（5）软件的成本不断提高。

（6）软件开发生产率的提高赶不上硬件的发展和应用需求的增长。总之，可以将软件危机归结为成本、质量、生产率等问题。

软件工程就是试图用工程、科学和数学的大批量与方法研制、维护计算机软件的有关技术及管理方法。

关于软件工程的定义，国标（GB）中指出，软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具文档、实践标准的工序。

1993年IEEE(Institute of Electrical &Electronic Engineers ，电气和电子工程师学会)给出了一个更加综合的定义：“将系统化的、规范的、可度量的方法应用于软件的开发、运行和维护的过程，即将工程化应用于软件中”。

软件工程包括3个要素：即方法、工具和过程。方法是完成软件工程项目的技术手段；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制、管理。

软件工程的核心思想是把软件产品看作是一个工程产品来处理。