计算机等级二级公共基础知识

公共基础知识一、基本数据结构与算法。二、程序设计基础。三、软件工程基础。四、数据库设计基础。第一部分数据结构与算法5-7个题（10-14分）考试大纲:一.基本要求:1.掌握算法的基本概念2.掌握基本数据结构及其操作3.掌握基本排序和查找算法二.考试内容:1.算法的基本概念;算法复杂度的概念和意义(时间复杂度和空间复杂度)2.数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念3.线性表的定义;线性表的顺序存储结构及其插入与删除运算4.栈和队列的定义;栈和队列的顺序存储结构及其基本运算5.线性单链表、双向链表与循环链表的结构及其基本运算6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）考点一、算法（P1）一.算法的基本概念▲所谓算法是指解题方案的准确而完善的描述。1.算法的基本特征①可行性：是否可行。②确定性：指算法中的每一个步骤必须有明确定义，不允许有模棱两可的解释，也不允许有多义性。③有穷性：指算法必须在有限的时间内做完，即算法必须能在执行有限个步骤后终止。④拥有足够的情报：收集的输入信息等。2.算法的基本要素一个算法通常由两种要素组成：一是对数据对象的运算和操作，二是算法的控制结构。（1）算法中对数据的运算和操作（指令）（P2）算术运算：加、减、乘、除逻辑运算：与、或、非关系运算：大于、小于、等于、不等于数据传输：赋值、输入、输出（2）算法的控制结构（P3）一个算法一般都可以用顺序、选择、循环三种基本控制结构组成。描述算法的工具有：传统流程图、N-S结构化流程图、算法描述语言。传统流程图、N-S结构化流程图、算法描述语言。条件语句序列1语句序列2ENDIF后面的语句真假条件语句序列1ENDIF后面的语句a=0?yesno输入a,b,cb^2-4acdeltab0?delta0?YesNo方程有一个根方程无意义方程有二个实根方程有二个虚根输出方程的根noyes3.算法设计的基本方法①列举法②归纳法③递推法④递归法⑤减半递推技术二.算法的复杂度▲（P5）算法的复杂度主要包括:时间复杂度和空间复杂度.1.算法的时间复杂度:指执行算法所需要的计算工作量.工作量可以用算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数．即算法的工作量=f(n)其中n是问题的规模.可以用平均性态和最坏情况复杂性两种方法.2.算法的空间复杂度:指执行这个算法所需要的内存空间.包括算法程序所占的空间、输入的初始数据所占的存储空以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及基本种数据结构所需要的附加存储空间（例如，在链式结构中，除了存储数据本身外，还需要存储链接信息）。考点二、数据结构的基本概念（P7）数据结构学科主要研究如下三个方面的内容:①数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构.②在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构.③对各种数据结构进行的运算.数据结构学科的研究目的:提高数据处理的效率.主要包括:①数据处理速度.②尽量节省在数据处理过程中所占用的计算机存储空间.一.数据结构的定义:指相互关联的数据元素的集合.1.数据处理:指对数据集合中的各元素以各种方式进行运算.(插入,删除,查找,更改等)2.数据元素:在数据处理领域中,每一个需要处理的对象都可以抽象为数据元素.3.数据结构:是指反映数据元素之间关系的数据元素集合的表示.一个数据结构应包括两方面的信息:一是表示数据元素的信息,二是表示各数据元素之间的前后件关系.①数据的逻辑结构（P11）:指反映数据元素之间逻辑关系的数据结构.它包含两个要素:一是数据元素的集合,通常记为D,二是D上的关系,它反映了D中各数据元素之间的前后件关系,通常记为R,形式表示为:B=(D,R)其中B表示数据结构为了反映D中各数据元素之间的前后件关系,一般用二元组来表示.例如,假设a与b是D中的两个数据,则二元组(a,b)表示a是b的前件,b是a的后件.这样,在D中的每两个元素之间的关系都可以用这种二元组来表示.例:一年四季的数据结构可以表示成:B=(D,R)D={春，夏，秋，冬}R={（春,夏）,（夏,秋）,（秋,冬）}②数据的存储结构（P12）:指数据的逻辑结构在计算机存储空间中的存放形式.也称为物理结构.一般来说,一种数据的逻辑结构根据需要表示成多种存储结构,常用存储结构有顺序,链接,索引等.各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的,而且一般也不可能相同.（P13）二.数据结构的图形表示一个数据结构除了用二元关系表示外,还可以直观的用图形表示.图形表示方法:对于数据集合D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点,简称为结点;对于关系R中的每一个二元组,用一条有向线段从前件结点指向后件结点,以表示数据元素之间的前后件关系.春夏秋冬女儿儿子父亲例:用图形表示数据结构B=(D,R),其中D={di|1≤i≤6}={d1,d2,d3,d4,d5,d6}R={(d1,d2),(d1,d3),(d3,d4),(d5,d4),(d5,d6)}这个数据结构的图形表示为:d1d2d3d5d4d6三.线性结构和非线性结构（概念）（P14）数据结构一般分为线性结构和非线性结构两大类.一个非空的线性结构满足如下条件:①有且仅有一个根结点;②每一个结点最多有一个前件,也最多有一个后件;③在一个线性结构中插入或删除一个结点后还是线性结构.如果一个数据结构不是线性结构,则称之为非线性结构.线性结构有:栈,队列,双向链表;非线性结构:树,二叉树.ACBABCABCD1.线性表的基本概念线性表定义:线性表是由n(n=0)个数据元素a1,a2,…an组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件.即线性表或是一个空表,或是可以表示为:(a1,a2,…,an)其中ai(i=1,2,…,n)是属于数据对象的元素,通常也称为线性表中的一个结点.非空线性表的基本特征:①有且只有一个根结点a1，它无前件；②有且只有一个终端结点an，它无后件；③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表的长度：线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。考点三、线性表及其顺序存储结构2.线性表的顺序存储结构（P16）具有两个基本特点：①线性表中所有元素所占的存储空间是连续的；②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件一定存储在后件元素的前面。线性表的随机存取地址的计算公式：ADR（ai）=ADR(a1)+(i-1)kk指每个元素所占的字节：：a1a2aian：：：：ADR(a1)占k个字节占k个字节占k个字节占k个字节：：：：：：：：ADR(a1)+kADR(a1)+(i-1)kADR(a1)+(n-1)k线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转3.线性表的插入运算一个长度为n的线性表，要在第i（1≤i≤n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始向后移动一个位置，直到第i个元素之间的n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1，变为n+1.其时间复杂度，在平均情况下，需要移动一半的元素，最坏情况下要移动所有元素。4731243536561829473124353656182947312435365618872912345678910123456789101234567891087线性表顺序存储结构的适用场合：对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单，对于元素需要变动的大线性表就不太合适了，因为插入和删除的效率比较低。4.线性表的删除运算要删除第i（1≤i≤n）个元素时，首先要从第i+1个元素开始，直到最后一个（即n个）元素之间的n-1个元素依次向前移动一个位置。删除结束后，线性表的长度就减少了1。变为n-1。删除操作的时间复杂度：在平均情况下，需要移动表中一半的元素，最坏情况下要移动表中的所有元素。考点四、栈和队列(重点)（P19）1、栈及其基本运算(1)栈的定义:栈是限定在一端进行插入和删除操作的线性表.它按照”后进先出”(或”先进后出”)的原则组织数据.(2)栈的顺序存储:在程序设计语言中一般是用一维数据S(1:m)作为栈的顺序存储空间,其中m为栈的最大容量.(3)栈的基本运算①入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置.当栈顶指针已经指向存储空间的最后一个位置时说明本栈空间已满,不可能再进行入栈操作.②退栈操作:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1.当栈顶指针为0时,说明栈空,不可能再进行退栈操作.③读栈顶元素:将栈顶元素赋给一个指定的变量,栈指针(top)不变.当栈顶指针为0时,说明栈空,读栈顶元素操作失败.ABCDEF10987654321topbottomABCD10987654321topbottom入栈退栈2、队列及其基本运算（P21）（1）队列的定义：队列是指允许在一端进行插入、而在另一端进行删除的线性表。它按照“先进先出”的原则组织数据。FEDCBA退队入队frontrear（2）循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。（3）循环队列的基本运算①入队运算：首先将队尾指针加1（real=real+1），并当real=m+1时，置real=1，然后将新元素插入到指针指向的位置。②退队运算：首先将排头指针加1（front=front+1），并当front=m+1时置front=1，然后将排头指针指向的元素赋给指定的变量。ABCDEF87654321realfront具有6个元素的循环队列加入X和Y后的循环队列realABCDEF87654321frontXYBCDEF87654321frontXYreal退出一个元素后的循环队列栈和队列都是顺序存储的。考点五、线性链表（P24）1、线性链表的基本概念：线性表的链式存储结构称为线性链表。线性链表的存储结构：线性链表的每个结点中数据域存放数据元素的值，指针域存放后件结点的存储地址。双向链表的存储结构：双向链表的存储结构比线性链表的存储结构多出一个指针域，它用来存放前件结点的存放地址。带链的栈，带链的队列HEADA0B…H0HEAD0……2、线性链表的基本运算（P27）：插入、删除、合并、分解、逆转、复制、排序、查找。①线性链表的插入：先从栈中为新元素分配一个新的结点q，并赋值。然后利用线性链表的查找算法找到待插入位置的前一个结点的指针p。先将q指向p的后件，然后将q挂在p结点的后面。xpxpqxpq②线性链表的删除：先找到待删除元素的前一个结点p，用另一个指针q暂时保存p的后续结点（即待删除结点），然后把q结点的后续链直接挂接在p的后面。最后归还q结点所分配的栈空间。xpqxpq3、循环链表（P30）：循环链表的几个特点：①在循环链表中增加一个表头结点，使得循环链表对空表和非空表的操作实现了统一。②循环链表中最后一个结点的指针域不是空，而是指向表头结点。③判断循环链表是否为空的办法不是看表头指针为空，而是看表头结点的后续结点是否还是表头结点。④在循环链表中，从任何一个结点出发都可以访问到表中其它所有的结点。xYHEADz…考点六、树与二叉树(重点)（P31）1、树的基本概念树是一种非线性结构，在树的这种数据结构中，所有数据元素之间的关系具有明显的层次特性。①父结点：在树结构中，每一个结点只有一个前件结点，称为父结