搜索
我闻第1页公共基础知识资料第一章数据结构与算法【考点1】算法的基本概念算法：是指一组有穷的指令集，是解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法。算法的基本特征：确定性，算法中每一步骤都必须有明确定义，不允许有多义性；有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止；可行性，算法原则上能够精确地执行；拥有足够的情报。算法的组成要素：一个算法由数据对象的运算和操作以及其控制结构这两部分组成。算法的基本运算和操作：算术运算，逻辑运算，关系运算，数据传输。算法的基本控制结构：顺序，选择，循环。算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术。【考点2】算法的复杂度算法效率的度量——算法的复杂度：时间复杂度和空间复杂度。算法时间复杂度：指执行算法所需要的计算工作量。通常，一个算法所用的时间包括编译时间和运行时间。算法空间复杂度：指执行这个算法所需要的内存空间。包括算法程序所占的空间，输入的初始数据所占的空间，算法执行过程中所需的额外空间。空间复杂度和时间复杂度并不相关。【考点3】数据结构的基本概念数据：数据是客观事物的符号表示，是能输入到计算机中并被计算程序识别和处理的符号的总称，如文档，声音，视频等。数据元素：数据元素是数据的基本单位。数据对象：数据对象是性质相同的数据元素的集合。数据结构：是指由某一数据对象中所有数据成员之间的关系组成的集合。【考点4】逻辑结构和存储结构我闻第2页数据结构可分为数据的逻辑结构和存储结构。数据的逻辑结构是对数据元素之间的逻辑关系的描述，与数据的存储无关，是面向问题的，是独立于计算机的。它包括数据对象和数据对象之间的关系。数据的存储结构也称为数据的物理结构，是数据在计算机中的存放的方式，是面向计算机的，它包括数据元素的存储方式和关系的存储方式。线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。元素ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)*k，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。顺序表的运算：查找、插入、删除。【考点7】线性链表线性链表是线性表的链式存储结构，数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：(1)用于存储数据元素值，称为数据域；(2)用于存放指针，称为指针域，用于指向前一个或后一个结点。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。线性单链表中，HEAD称为头指针，HEAD=NULL（或0）称为空表。双向链表有两个指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。循环链表：循环链表与单链表的不同的是它的最后一个结点的指针域存放的事指向第一个结点的指针而单链表存放的是空指针。我闻第3页线性链表的基本运算：查找、插入、删除。【考点8】栈1、栈的基本概念栈是一种特殊的线性表，只允许在表的一端进行插入和删除的线性表；插入，删除的一端为栈顶，另一端为栈底；当表中没有元素时为空栈。栈是一种后进先出（或先进后出LastInFirstOut）的线性表。栈具有记忆功能。栈的实例：火车调度，子弹夹。2、栈的存储结构顺序存储结构：用一组地址连续的存储单元即一维数组来存储；链式存储：用线性链表来存储；3、栈的基本运算(1)入栈运算，在栈顶位置插入元素；(2)退栈运算，删除元素(取出栈顶元素并赋给一个指定的变量)；(3)读栈顶元素，将栈顶元素赋给一个指定的变量，此时指针无变化。【考点9】队列1.队列的基本概念队列是一种特殊的线性表，只允许在表的一端插入，在另一端删除，允许插入的一端是队尾（rear），允许删除的一端为队头（front）；当表中没有元素是空队列；队列是一种先进先出的线性表。(FIFO)2、队列的存储结构顺序存储：一维数组。链式存储：线性链表。3、队列的运算:(1)入队运算：从队尾插入一个元素；(2)退队运算：从队头删除一个元素。队列的顺序存储结构一般采用循环队列的形式。循环队列s=0表示队列为空；我闻第4页s=1且front=rear表示队满。计算循环队列的元素个数：“尾指针减头指针”，若为负数，再加其容量即可。【考点10】树的基本概念树是一种非线性结构，是n个结点的有限集。当n=0时为空树，n0时为非空树。a.结点的度：结点所拥有的子树的个数。b.叶子结点：度为0的结点。c.分支结点：除叶子结点以外的结点。d.结点的层次：根结点在第一层，同一层上左右结点的子结点在下一层。e.树的深度：所处层次最大的那个结点的层次。f.树的度：树中所有结点的度的最大值。【考点11】二叉树及其基本性质1、二叉树的概念二叉树是一种特殊的树形结构，每个结点最多只有两棵子树，且有左右之分不能互换。二叉树有五种不同的形态。2、二叉树的性质性质1在二叉树的第k层上，最多有2k-1(k≥1）个结点。性质2深度为m的二叉树最多有2m-1个结点。性质3在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。性质4具有n个结点的二叉树，其深度不小于[log2n]+1,其中[log2n]表示为log2n的整数部分。3、二叉树的存储结构需了解。【考点12】满二叉树与完全二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m－1个结点。完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。满二叉树是完全二叉树，而完全二叉树一般不是满二叉树。【考点13】完全二叉树的性质性质1具有n个结点的完全二叉树的深度为[log2n]+1。我闻第5页性质2完全二叉树中度为1的结点数为0或1。【考点14】二叉树的遍历前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。【考点15】顺序查找顺序查找是从表的一端开始，依次扫描表中的各个元素，并与所要查找的数进行比较。在下列两种情况下也只能采用顺序查找：（1）如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。【考点16】二分查找二分查找的条件：（1）用顺序存储结构；(2)线性表是有序表。查找的步骤也可能会考。对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。【考点17】排序1、交换排序（1）冒泡排序法，在最坏的情况下，冒泡排序需要比较次数为n(n－1)/2。（2）快速排序法，在最坏的情况下，快速排序需要比较次数为n(n－1)/2。2、插入类排序法：（1）简单插入排序法，最坏情况需要n(n-1)/2次比较；（2）希尔排序法，最坏情况需要O(n1.5)次比较。（大写O是算法复杂度的表示方法）3、选择类排序法：（1）简单选择排序法，最坏情况需要n(n-1)/2次比较；（2）堆排序法，最坏情况需要O(nlog2n)次比较。我闻第6页相比以上几种(除希尔排序法外)，堆排序法的时间复杂度最小。第二章程序设计基础【考点1】程序设计方法与风格形成良好的程序设计风格需注意：1、源程序文档化；2、数据说明的方法；3、语句的结构；4、输入和输出。注释分序言性注释和功能性注释。语句结构清晰第一、效率第二。【考点2】结构化程序设计方法的四条原则自顶向下，逐步求精，模块化，限制使用goto语句。属性：即对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变。类：是具有相似属性与操作的一组对象。类是关于对象性质的描述。类是对象的抽象，对象是其对应类的一个实例。【考点7】消息及其组成消息：是一个实例与另一个实例之间传递的信息。对象间的通信靠消息传递。它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。消息的组成包括：(1)接收消息的对象的名称；(2)消息标识符，也称消息名；(3)零个或多个参数。【考点8】继承和多态继承：是使用已有的类定义作为基础建立新类的定义技术，广义指能够直接获得已有的性质和特征，而不必重复定义他们。继承具有传递性，一个类实际上继承了它上层的全部基类的特性。继承分单继承和多重继承。单继承指一个类只允许有一个父类，即类等级为树形结构；多重继承指一个类允许有多个父类。我闻第7页多态性：是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。第三章软件工程基础【考点1】软件定义与软件特点软件指的是计算机系统中与硬件相互依存的另一部分，包括程序、数据和相关文档的完整集合。程序：软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列。数据：使程序能正常操纵信息的数据结构；文档：与程序的开发、维护和使用有关的图文资料；软件的特点：a.软件是一种逻辑实体，具有抽象性；b.软件的生产与硬件不同，它没有明显的制作过程；c.软件在运行、使用期间不存在磨损、老化问题；d.软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题；e.软件复杂性高，成本昂贵；f.软件开发涉及诸多的社会因素。根据应用目标的不同，软件可分应用软件、系统软件和支撑软件（或工具软件）。①应用软件：为解决特定领域的应用而开发的软件，如办公自动化软件；②系统软件：计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件，如操作系统；③支撑软件（或工具软件）：支撑软件是介于两者之间，协助用户开发软件的工具性软件。【考点2】软件的生命周期软件生命周期是指软件产品从提出、实现、使用维护到停止使用退役的整个过程。可分为软件定义，软件开发及软件维护3个阶段。软件生命周期中，能够准确确定软件系统必须做什么和必须具备哪些功能的阶段是：需求分析。我闻第8页【考点3】软件危机和软件工程的概念软件危机泛指在计算机软件的开发和维护过程中遇到的一系列严重的问题，集中表现在成本，质量，生产效率等几个方面。所谓软件工程是指采用工程的概念、原理、技术和方法指导软件的开发与维护。是建立并使用完善的工程化原则，以较经济的手段获得，能在实际机器上有效运行的可靠软件的一系列方法；软件工程的主要思想强调在软件开发过程中需要应用工程化原则。软件工程的核心思想是把软件当作一个工程产品来处理。软件工程包括3个要素：方法，工具和过程方法：方法是完成软件工程项目的技术手段工具：工具支持软件的开发、管理、文档生成过程：过程支持软件开发的各个环节的控制、管理。【考点4】软件工程过程软件工程过程是把软件转化为输出的一组彼此相关的资源活动，包含4种基本活动：（1）P(plan)——软件规格说明；（2）D(do)——软件开发；（3）C(check)——软件确认；（4）A(action)——软件演进。【考点5】软件开发技术和软件工程管理①软件工程的理论和技术性研究的内容主要包括软件开发技术和软件工程管理。软件开发技术包括软件开发方法学、开发过程、开发工具和软件工程环境，其主体内容是软件开发方法学。②软件开发方法包括分析方法，设计方法和程序设计方法。③软件工程管理包括软件管理学，软件工程经济学，软件心理学等。④软件管理学包括人员组织，进度安排，质量保证，配置管理，项目计划等。软件工程经济学是研究软件开发中成本的估算，成本效益的方法和技术。【考点6】软件工程的原则软件工程的原则：抽象，信息隐蔽，模块化，局部化，确定性，一致性，完备性，可验证性。【考点7】需求