《office2级知识点剖析》由会员分享,可在线阅读,更多相关《office2级知识点剖析(46页珍藏版)》请在金锄头文库上搜索。
1、(1)算法的时间复杂度是指算法在计算机内执行时所需时间的度量;与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。(2)时间复杂度是指一个算法执行时间的相对度量;空间复杂度是指算法在运行过程中临时占用所需存储空间大小的度量。人们都希望选择一个既省存储空间、又省执行时间的算法。然而,有时为了加快算法的运行速度,不得不增加空间开销;有时为了能有效地存储算法和数据,又不得不牺牲运行时间。时间和空间的效率往往是一对矛盾体,很难做到两全。但是,这不适用于所有的情况,也就是说时间复杂度和空间复杂度之间虽然经常矛盾,但是二者不存在必然的联系。(3)数据处理的最小单位是数据项;由若干数据项
2、组成数据元素;数据是指能够被计算机识别、存储和加工处理的信息载体;数据结构是指数据之间的相互关系和数据运算。(4)一般来说,一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接、索引等。而采用不同的存储结构,其数据处理的效率是不同的。(5)数据结构概念一般包括数据的逻辑结构、存储结构及数据上的运算集合等。数据的逻辑结构只抽象地反映数据元素之间的逻辑关系,而不管它在计算机中的存储形式。(6)数据结构作为计算机的一门学科,主要研究和讨论以下三个方面的问题: 数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; 在对数据进行处理时,各数据元素在计算机中的存储关系,即数
3、据的存储结构; 对各种数据结构进行的运算。(7)根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件: 有且只有一个根结点; 每一个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构,又称线性表。所以线性表、栈与队列、线性链表都是线性结构,而二叉树是非线性结构。(8)线性表可以为空表;第一个元素没有直接前件,最后一个元素没有直接后件;线性表的定义中,元素的排列并没有规定大小顺序。(9)如果一个非空的数据结构满足下列两个条件:第一,有且只有一个根结点;第二,每一个结点最多有一个前件,也最多有一个后件
4、,则称该数据结构为线性结构。线性结构又称线性表。(10)顺序存储结构中,数据元素存放在一组地址连续的存储单元中,每个数据元素地址可通过公式LOC(ai)=LOC(a1)+(i-1)L计算得到,从而实现了随机存取。对于链式存储结构,要对某结点进行存取,都得从链的头指针指向的结点开始,这是一种顺序存取的存储结构。(11)栈是限定在一端进行插入与删除的线性表。栈是按照“先进后出”的或“后进先出”的原则组织数据的,因此,栈也被称为“先进后出”表或“后进先出”表。(12)本题考查的是栈。栈是一种特殊的线性表,线性表可以顺序存储,也可以链式存储,而栈是一种线性表,也可以采用链式存储结构。(13)本题主要考
5、查对于栈的理解。栈是限定在一端进行插入与删除的线性表。在栈中,允许插入与删除的一端称为栈顶,而不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素,从而也是最先能被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素,即栈是按照“先进后出”或“后进先出”的原则组织数据的。(14)和线性表类似,栈也有两种存储方法,一是顺序栈,二是链式栈。栈的顺序存储结构是利用一组地址连续的存储单元一次存储自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素的位置,由于栈的操作是线性表操作的特例,相对而言,链式栈的操作更易于实现。(16)栈操作原则上“后进先出”,栈底至栈顶依次存放元
6、素A、B、C、D,则表明这4个元素中D是最后进栈,B、C处于中间,A最早进栈,所以出栈时一定是先出D,再出C,最后出A。(17)队列是一种操作受限的线性表。它只允许在线性表的一端进行插入操作,另一端进行删除操作。其中,允许插入的一端称为队尾(rear),允许删除的一端称为队首(front)。队列具有先进先出的特点,它是按“先进先出”的原则组织数据的。(18)考查栈和队列概念的掌握。栈和队列都是一种特殊的操作受限的线性表,只允许在端点处进行插入和删除。二者的区别是:栈只允许在表的一端进行插入或删除操作,是一种“后进先出”的线性表;而队列只允许在表的一端进行插入操作,在另一端进行删除操作,是一种“
7、先进先出”的线性表。(19)本题考查的是线性单链表、双向链表与循环链表的结构及其基本运算。在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。 (20)链式存储结构克服了顺序存储结构的缺点:它的结点空间可以动态申请和释放;它的数据元素的逻辑次序靠结点的指针来指示,不需要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。(21)将题中所述的树用图形表示即可得到叶子结点的数目,另外还可用公式n0=1n2+2n3+3n4+1来计算,其中n0表示叶子结点;1n2中的n2表示度为2的结点。此题中度
8、为1的结点有4个;度为2的结点有2个;度为3的结点有1个;度为4的结点有1个,计算过程如下:n0=1n2+2n3+3n4+1n0=12+21+31+1n0=8(23)本题考查了二叉树的基本概念。在二叉树中,叶子节点的度是1;当该二叉树为空树时,根节点的度为0;为非空树时,根节点的度最大为2。(24)本题考查二叉树的遍历。所谓二叉树的前序遍历(DLR)是指在访问根结点、遍历左子树与遍历右子树这3者中,首先访问根结点,然后遍历左子树,最后遍历右子树,并且,在遍历左右子树时,上述规则同样适用,即“根左右”,故该二叉树的前序遍历结果为“ATBZXCYP”。(25)前序遍历的第一个结点a为树的根结点;中
9、序遍历中a的左边的结点为a的左子树,a右边的结点为a的右子树;再分别对a的左右子树进行上述两步处理,直到每个结点都找到正确的位置。(26)对有序线性表进行顺序查找,首先用被查找的数据和线性表的第一个数据元素进行比较,若相等,则查找成功;否则,继续进行比较,即和线性表的第二个数据元素进行比较。同样,若相等,则查找成功;否则,继续进行比较。依次类推,直到在线性表中查找到该数据或查找到线性表的最后一个元素,算法才结束。因此,在长度为64的有序线性表中进行顺序查找,最坏的情况下需要比较64次。(27)二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大,但允
10、许相邻元素值相等)的。 (28)从平均时间性能而言,快速排序最佳,其所需时间最少,但快速排序在最坏情况下的时间性能不如堆排序和归并排序。当序列中的记录基本有序或元素个数较少时,冒泡排序和简单选择排序为最佳排序方法。 程序设计基础(1)结构化程序设计方法的主要原则是:自顶向下,逐步求精,模块化,限制使用goto语句。可复用性是指软件元素不加修改和稍加修改可在不同的软件开发过程中重复使用的性质。软件可复用性是软件工程追求的目标之一,是提高软件生产效率的最主要方法。面向对象的程序设计具有可复用性的优点。(2)滥用goto 语句将使程序流程无规律,可读性差,;注解行有利于对程序的理解,不应减少或取消,
11、;程序的长短要依照实际情况而论,而不是越短越好。(3)本题考查了程序的基本结构。程序由一些基本结构组成。任何一个大型的程序都由3种基本结构组成,由这些基本结构构成一个结构化的程序。这3种基本结构为:顺序结构、选择结构和循环结构。(4)结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化及限制使用goto语句,总的来说可使程序结构良好、易读、易理解、易维护。(5)面向对象的设计方法与传统的面向过程的方法有本质不同,它的基本原理是,使用现实世界的概念抽象地思考问题从而自然地解决问题。它强调模拟现实世界中的概念而不强调算法,它鼓励开发者在软件开发的绝大部分中都用应用领域的概念去思考。(6
12、)面向对象的世界是通过对象与对象间彼此的相互合作来推动的,对象间的这种相互合作需要一个机制协助进行,这样的机制称为消息。消息是一个实例与另一个实例之间传递的信息,它请求对象执行某一处理或回答某一要求的信息,它统一了数据流和控制流。(7)面向对象程序设计方法并不强调自顶向下的构造程序,而常常是自底向上的,而自顶向下、逐步求精是结构化程序设计的特点。(8)面向对象思想中的三个主要特征是:封装性、继承性和多态性。(9)面向对象程序由若干个对象构成;结构化程序由数据和相应算法构成。(10)对象是由数据和容许的操作组成的封装体,与客观实体有直接的对应关系,对象之间通过传递消息互相联系,从而模拟现实世界中
13、不同事物彼此之间的联系, (11)对象的基本特点:标识唯一性、分类性、多态性、封装性和模块独立性。(12)在面向对象程序设计中所使用的对象,其数据和操作是作为平等伙伴出现的。因此,对象具有很强的自含性,此外,对象所固有的封装性,使得对象之间不相互影响。(13)面向对象方法是一种运用对象、类、封装、继承、多态和消息等概念来构造、测试、重构软件的方法。面向对象方法从对象出发,发展出对象、类、消息、继承等概念。软件工程基础(1)本题考查软件的定义。软件是计算机系统中与硬件相互依存的另一部分,它包括程序、相关数据及其说明文档的总和。(2)软件工程学是研究软件开发和维护的普遍原理与技术的一门工程学科。所
14、谓软件工程是指采用工程的概念、原理、技术和方法指导软件的开发与维护。软件工程学的主要研究对象包括软件开发与维护的技术、方法、工具和管理等方面。(3)软件工程包括3个要素,即方法、工具和过程。(4)软件工程概念的出现源自于软件危机。为了消除软件危机,通过认真研究解决软件危机的方法,认识到软件工程是使计算机软件走向工程科学的途径,逐步形成了软件工程的概念。(5)本题考核软件维护的概念。维护是软件生命周期的最后一个阶段,也是持续时间最长、付出代价最大的阶段。在软件交付使用后,还需要进行维护。软件维护通常有以下四类:为纠正使用中出现的错误而进行的改正性维护;为适应环境变化而进行的适应性维护;为改进原有
15、软件而进行的完善性维护;为将来的可维护和可靠而进行的预防性维护。软件维护不仅包括程序代码的维护,还包括文档的维护。(6)软件生命周期分为软件定义、软件开发及软件运行维护3个阶段。本题中,详细设计、软件编码和软件测试都属于软件开发阶段;维护是软件生命周期的最后一个阶段,也是持续时间最长、花费代价最大的一个阶段,软件工程学的一个目的就是提高软件的可维护性,降低维护的代价。(7)通常将软件产品从提出、实现、使用维护到停止使用的过程称为软件生命周期。它可以分为软件定义、软件开发及软件运行维护3个阶段。(8)软件生命周期由软件定义、软件开发和软件维护3个时期组成。软件开发时期是具体设计和实现在前一时期定
16、义的软件,它通常由下面五个阶段组成:概要设计、详细设计、编写代码、组装测试和确认测试。(9)通常,将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。也就是说,软件产品从考虑其概念开始,到该软件产品不能使用为止的整个时期都属于软件生命周期。软件生命周期的主要活动阶段为: 可行性研究和计划制定。确定待开发软件系统的开发目标和总的要求,给出它的功能、性能、可靠性以及接口等方面的可能方案,制定完成开发任务的实施计划。 需求分析。对待开发软件提出的需求进行分析并给出详细定义,即准确地确定软件系统的功能。编写软件规格说明书及初步的用户手册,提交评审。 软件设计。系统设计人员和程序设计人员应该在反复理解软件需求的基础上,给出软件的结构、模块的划分、功能的分配以及处理流程。