计算机二级公共基础知识复习资料.docx

《计算机二级公共基础知识复习资料.docx》由会员分享，可在线阅读，更多相关《计算机二级公共基础知识复习资料.docx（17页珍藏版）》请在第一文库网上搜索。

1、二级公共基础知识总结第一章数据结构及算法1.1算法算法：是指解题方案的精确而完整的描述。算法不等于程序,也不等于计算机方法。程序的编制不可能优于算法的设计。算法的基本特征：(1)可行性算法原则上能够精确地执行。(2)确定性算法中每一步骤都必需有明确定义，不允许有模棱两可的说明，不允许有多义性。(3)有穷性算法必需能在有限的时间内做完，即能在执行有限个步骤后终止。(4)拥有足够的情报。算法的基本要素：一是对数据对象的运算和操作；二是算法的限制结构。指令系统:一个计算机系统能执行的全部指令的集合。算法的基本运算包括：算术运算，逻辑运算，关系运算,数据传输。算法的限制结构：依次结构，选择结构，循环结

2、构。算法基本设计方法：列举法，归纳法，递推，递归，减斗递推技术，回溯法。算法效率的度量一一算法困难度：时间困难度和空间困难度。算法时间困难度是指执行算法所须要的计算工作量。通常，一个算法所用的时间包括编译时间和运行时间。算法空间困难度是指执行这个算法所须要的内存空间。包括算法程序所占的空间，输入的初始数据所占的空间，算法执行过程中所需的额外空间。空间困难度和时间困难度并不相关。12数据结构的基本基本概念数据：数据是客观事物的符号表示，是能输入到计算机中并被计算程序识别和处理的符号的总称，如文档，声音，视频等。数据元素：数据元素是数据的基本单位。数据对象：数据对象是性质相同的数据元素的集合。数据

3、结构：是指由某一数据对象中全部数据成员之间的关系组成的集合。数据结构可分为数据的逻辑结构和存储结构。数据的逻辑结构是对数据元素之间的逻辑关系的描述，及数据的存储无关，是面对问题的，是独立于计算机的。它包括数据对象和数据对象之间的关系。数据的存储结构也称为数据的物理结构，是数据在计算机中的存放的方式，是面对计算机的，它包括数据元素的存储方式和关系的存储方式。数据存储结构和逻辑结构的关系：一种数据的逻辑结构可以表示成多种存储结构即数据的逻辑结构和存储结构不肯定一一对应。常见的存储结构有：依次，链接，索引等。采纳不同的存储结构其数据处理的效率是不同的。线性结构条件，（一个非空数据结构）：（1）有H只

4、有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满意线性结构条件的数据结构。线性表，栈，队列，线性链表是线性结构，树，二叉树为非线性结构。13线性表及线性链表线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在困难线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。非空线性表的结构特征：（1）且只有一个根结点a1,它无前件；（2）有且只有一个终端结点an,它无后件；（3）除根结点及终端结点外，其他全部结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。

5、线性表的依次存储结构具有以下两个基本特点：（1）线性表中全部元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑依次依次存放的。元素ai的存储地址为：ADR（ai）=ADR（a1）+（i-1）k,DR（a1）为第一个元素的地址，k代表每个元素占的字节数。依次表的运算：查找，插入，删除。线性链表是线性表的链式存储结构，数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。线性链表不能随机存储。结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。链式存储结构中，存储数据结构的存储空间可以不

6、连续,各数据结点的存储依次及数据元素之间的逻辑关系可以不一样，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构。线性链表分为单链表，双向链表和循环链表三种类型。线性单链表，HEAD称为头指针，HEAd=NU11（或0）称为空表。数据域指针域数据域指针域A数据域指针域1DR1DR图2双链表的结构1DR循环链表:循环链表与单链表的不同的是它的最后一个结点的指针域存放的事指向第一个结点的指针而单链表存放的是空指针.图3循环琏表的结构图1单链表的结构双向链表有两个指针：左指针（1Imk）指向前件结点，右指针（R1mk）指向后件结点.线性链表的基本运算

7、：查找、插入、删除.1.4栈和队列栈是一种特别的线性表，只允许在表的一端进行插入及删除的线性表，允许插入及删除的一端称为栈顶，不允许插入及删除的另一端称为栈底。栈依据“先进后出（F11o）或“后进先出（1IFo）组织数据，栈具有记忆功能。用top表示栈顶位置,用bottom表示栈底。栈的存储方式有依次存储的链式存储工栈的实例：子弹夹栈的基本运算:（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。队列是一种特别的线性表，只允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，fron1指针指向队

8、头。队列是“先进先出（F1FO）或“后进后出（111o）的线性表。队列的存储结构依次存储：一维数组。链式存储：线性链表。队列的实例：火车进隧道队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。队列的依次存储结构一般类纳队列循环的形式。循环队列：S=O表示队列空，S=I且front=rear表示队列满1.5树及二叉树树是一种简单的非线性结构,全部元素之间具有明显的层次特性。树的基本概念：结点：每个结点都包含数据项和若干个指向其子树的分支。如左图所示的树中有7个结点。结点的度：结点所拥有的子树棵数。如左图，根结点A的度为3。结点的层次：根结点在第一层，同一层上左右

9、结点的子结点在下一层。如左图，根结点A在第一层，B,C,D在第二层，E,F,G在第三层。树的深度：所处层次最大的那个结点的层次称为树的深度。如左图，树的深度为3。树的度：树中全部结点的度的最大值就是树的度。如左图，树的度为3。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。二叉树是一种特别的树形结构，每个结点最多只有两棵子树，且有左右之分不能互换。二叉树的特点：(1)非空二叉树只有一个根结点；(2)每一个结点最多有两棵子树，且分别称为该结点的左子树及右子树。二叉树的基本

10、性质:(1)在二叉树的第k层上，最多有2i(kN1)个结点；(2)深度为m的二叉树最多有2-1个结点;(3)度为O的结点(即叶子结点)总是比度为2的结点多一个；(4)具有n个结点的二叉树，其深度至少为Iog2n+1,其中1og2T表示取1og211的整数部分；(5)具有n个结点的完全二叉树的深度为1。豳口+1；(6)设完全二叉树共有n个结点。假如从根结点开始,按层序(每一层从左到右)用自然数1,2,.n给结点进行编号(k=1,2.n),有以下结论：若k=1则该结点为根结点，它没有父结点;若k1,则该结点的父结点编号为INT（k2）;若2kWn,则编号为k的结点的左子结点编号为2k；否则该结点无

11、左子结点（也无右子结点）；若2k+1Wn,则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。满二叉树是指除最终一层外，每一层上的全部结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2mT个结点。完全二叉树是指除最终一层外，每一层上的结点数均达到最大值，在最终一层上只缺少右边的若干结点。二叉树存储结构采纳链式存储结构，对于满二叉树及完全二叉树可以按层序进行依次存储。二叉树的遍历：（重点）A图4二叉树的遍历前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树.前序遍历图5可得：ABCDFHEG

12、。中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在漏历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。中序遍历图5可得：BAFHDCGE.后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点.后序遍历图5可得：BHFDGECA1I1.6查找技术依次查找的运用状况：(1)线性表为无序表；(2)表采纳链式存储结构。二分法查找只适用于依次存储的有序表,对于长度为n的有序线性表，最坏状况只需比较1og2次，而依次查找须要比较n次。1. 8查找及排序技术依次查找是从表的一端开始，依次扫描表中的各

13、个元素，并及所要查找的数进行比较。在下列两种状况下也只能采纳依次查找：(1)假如线性表为无序表，则不管是依次存储结构还是链式存储结构,只能用依次查找。(2)即使是有序线性表，假如采纳链式存储结构，也只能用依次查找。二分查找的条件：(1)用依次存储结构(2)线性表是有序表。对于长度为n的有序线性表，在最坏状况下，二分法查找只需比较Iogzn次，而依次查找须要比较n次。排序是指将一个无序序列整理成按值非递减依次排列的有序序列。1,交换排序(1)冒泡排序法，在最坏的状况下，冒泡排序须要比较次数为n(n-1)2(2)快速排序法，在最坏的状况下，快速排序须要比较次数为n(n-1)22,插入类排序法：(1

14、)简单插入排序法，最坏状况须要n(n-1)/2次比较；(2)希尔排序法，最坏状况须要OS-)次比较。(大写0是算法困难度的表示方法)3,选择类排序法：（1）简单选择排序法，最坏状况须要n（nT）2次比较；（2）堆排序法，最坏状况须要0（n1o4）次比较。相比以上几种（除希尔排序法外），堆排序法的时间困难度最小。本章应考点拨:本章内容在笔试中会出现5-6个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10分。第二章程序设计基础2. 1程序设计设计方法和风格如何形成良好的程序设计风格1,源程序文档化；2,数据说明的方法；3,语句的结构；4,输入和输出。注释分序言性注释和功能性注释

15、，语句结构清楚第一，效率第二。2. 2结构化程序设计结构化程序设计方法的四条原则是：1自顶向下;2.逐步求精；3.模块化；4.限制运用goto语句。结构化程序的基本结构和特点：（1）依次结构：一种简单的程序设计，最基本，最常用的结构；（2）选择结构：又称分支结构，包括简单选择和多分支选择结构，可依据条件，推断应当选择哪一条分支来执行相应的语句序列；（3）循环结构：又称重复结构，可依据给定条件，推断是否须要重复执行某一相同程序段。结构化程序设计的特点：只有一个入口和出口。3. 3面对对象的程序设计面对对象的程序设计：以60年代末挪威奥斯陆大学和挪威计算机中心研制的SIMU1A语言为标记。面对对象的程序设计以对象为核心，强调对象的抽象性，封装性，继承性和多态性。面对对象方法的优点:（1）及人类习惯的思维方法一样；（2）稳定性好；（3）可重用性好；（4）易于开发大型软件产品；（5）可维护性好。对象是面对对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。面对对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的信息，操作描述了对象执行的功能，是对象的动态属性，操作也称为方法或服务。对象的基本特点：（1）标识惟一性