2010公共基础知识-数据结构

计算机等级考试

公共基础知识

数计学院卫春芳1计算机二级考试公共基础知识大纲

数据结构与算法程序设计基础软件工程基础数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30％，是一个不小的比例。

2计算机二级考试公共基础知识试卷分析

章节考试时间数据结构与算法程序设计基础软件工程基础数据库设计基础2006年4月10分4分6分10分2006年9月10分2分8分10分2007年4月10分2分10分8分2007年9月12分4分8分6分2008年4月10分2分8分10分2008年9月10分2分8分10分2009年3月10分2分8分10分3算法⒈算法的基本概念

2.算法的基本特征

3.

算法的表示

4.算法的要素

5.算法的评价一、基本数据结构与算法数据结构⒈数据结构的概念⒉线性表⒊栈和队列⒋树与二叉树⒌查找技术⒍排序技术

对于等级考试，这个部分的考核重点主要在算法的基本概念和特征、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。4算法的定义对解题方案准确而完整的描述称为算法。算法是程序设计的核心⒈算法的基本概念

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。例：解方程：f(x)=0在区间[a,b]上有实根且f(a)与f(b)异号，求该方程在区间[a,b]上的实根。

有多种解法，常用的是用二分法求方程实根。5

2.

算法的基本特征一个算法应该具有以下五个重要的特征：有穷性确定性输入输出可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成算法的特征：有穷性、确定性、可行性、拥有足够的情报。6算法与计算机程序算法____是一组逻辑步骤程序——用计算机语言描述的算法3.算法的表示INPUTrS=3.14*r*rPTINTS开始输入RS=3.14*

R*R输出S结束问题：输入园的半径，计算园的面积

一个算法的表示需要使用一些语言形式。传统的算法-------图形法，如“流程图”和N-S图目前常用的方法-------使用伪码描述算法。7冒泡排序的方法：1.扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后；2.除最后一个元素，对剩余的元素重复上述过程，将次大的数排到表的倒数第二个位置；3.重复上述过程；对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。

算法举例：n个数排序84.算法的两个基本要素：基本运算和操作算术运算关系运算逻辑运算数据传输控制结构

顺序选择循环一是对数据对象的运算和操作；二是算法的控制结构。算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法

95.

算法评价评价一个算法优劣的主要标准是算法的执行效率和存储需求：时间复杂度：执行这个算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量空间复杂度：执行这个算法所需要的内存空间

算法在执行过程中临时占用的存储空间

时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。

一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分10一、算法对解题方案准确而完整的描述称为算法。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法的两个要素：一是对数据对象的运算和操作；二是算法的控制结构。算法的特征：

有穷性、确定性、可行性、输入、输出算法评价：

时间复杂度：执行这个算法所需要的计算工作量空间复杂度：执行这个算法所需要的内存空间11(1)算法一般都可以用哪几种控制结构组合而成____。

A.循环、分支、递归

B.顺序、循环、嵌套

C.循环、递归、选择

D.顺序、选择、循环(2)算法中，对需要执行的每一步操作，必须给出清楚、严格的规定，这属于算法的（07年4月）

A）正当性B）可行性C）确定性D）有穷性(3)在计算机中，算法是指______。

A.查询方法B.加工方法

C.解题方案的准确而完整的描述D.排序方法(4)下列叙述中正确的是（07年4月）A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关(D)(c)(c)(B)算法习题:12(5)算法的有穷性是指(08年4月)A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用(6)算法的时间复杂度是指______。A.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数(7)下列叙述中正确的是(06年9月)

A）一个算法的空间复杂度大，则其时间复杂度也必定大

B）一个算法的空间复杂度大，则其时间复杂度必定小

C）一个算法的时间复杂度大，则其空间复杂度必定小

D）上述三种说法都不对(A)(C)计算工作量(d)13

计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。二、数据结构程序=算法+数据结构数据结构是指相互有关联的数据元素的集合。

一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。14二.数据结构数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。

（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。151.逻辑结构

数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。例：1.一年四季的数据结构

B=(D,R)D={春，夏，秋，冬}R={(春，夏),(夏，秋),(秋，冬)}2.家庭成员的数据结构

B=(D,R)D={父亲，儿子，女儿}R={(父亲，儿子),(父亲，女儿)}春夏秋冬数据结构的图形表示父亲儿子女儿16常见的逻辑结构有：线性结构、树形结构和图形结构。线性结构树形结构图形结构①线性结构结构中的每个元素之间存在一个对一个的关系；②树形结构结构中的每个元素之间存在一个对多个的关系；③图形结构或网状结构结构中的每个元素之间存在多个对多个的关系。其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。17存储结构（物理结构）是指数据结构在计算机存储器中的具体实现。数据结构（包括数据及其数据之间的关系）在计算机存储器上的存储表示称为数据的物理结构或存储结构，由于存储表示的方法有多种，诸如顺序、链接、索引等，所以一种数据结构可以根据需要表示成一种或多种存储结构。

18

2.存储结构（物理结构）计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。如：一年四季

家庭成员计算机存储空间怎样存放？

存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：顺序存储结构链式存储结构索引存储结构19数据处理检索插入删除更新排序

数据处理（数据的运算）是指对数据集合中各个元素以各种方式进行运算，包括：插入、删除、查找、更改、排序等，还包括对数据元素进行分析。数据的逻辑结构表示数据元素之间的关系，有一对一、一对多、多对多的关系；数据的存储结构有顺序、链接、索引等。20数据结构是研究数据和数据之间关系的一门学科，研究以下三方面内容：

数据的逻辑结构数据的存储结构数据的运算21常见的数据结构

1.线性表

2.栈和队列

3.树22１．线性表（LinearList）线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。简单的线性表春夏秋冬复杂的线性表记录102011001

张三男…

记录202011003李四女…记录3记录423线性表的顺序存储结构线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。顺序表的运算：插入、删除。24线性表的顺序存储结构

顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，顺序存储结构只存储结点的值，不存储结点间的关系，结点间的关系由存储单元的邻接关系来体现。…a1a2…ai…an…存储地址200020042000+4*(i-1)2000+4*(n-1)……占4个字节Loa（ai）=Loa（a1）+L*（i-1）第i个数的地址第一个数的地址L为该类型数所占的字节25顺序表的插入运算顺序表的删除运算顺序表的插入和删除运算在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。线性表的顺序存储结构称为顺序表。26线性表的存储结构线性表的存储结构有两种：

顺序存储结构

链式存储结构注意：数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。一个逻辑数据结构可以有多种存储结构，且不同的存储结构影响数据处理的效率。27线性表的链式存储结构线性表的链式存储结构称为线性链表。链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：数据域指针域28应用举例——线性链表的存储结构设线性表为（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的物理状态1a12a23a34a45a567线性表的顺序存储结构注意:123此类编号不代表所在的地址单元的地址编码29线性链表数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构。线性链表，HEAD称为头指针，HEAD=NULL（或0）称为空表，如果是两指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。30单链表的插入运算单链表的删除运算线性链表的插入和删除运算采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。312.栈和队列栈和队列都是特殊的线性表。

栈（Stack）及其基本运算

队列（Queue）及其基本运算

循环队列及其基本运算32栈（Stack）是一种特殊的线性表。其特点是插入和删除运算都只能在线性表的一端进行。栈是按照“先进后出”或“后进先出”的原则组织数据的线性表。用top表示栈顶位置，用bottom表示栈底。栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。顺序栈的进栈和出栈运算在顺序栈中插入和删除运算不需要移动表中其他数据元素。33队列（Queue）是一种特殊的线性表。队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。

Rear指针指向队尾，front指针指向队头。队列是按照“先进先出”或“后进后出”的原则组织数据的线性表。队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。顺序队列的运算

34栈有三种操作：入栈＼出栈＼读栈顶元素队列有三种操作：入队＼出队＼读队首元素例：有入栈元素序列：ABCD，求可能的出栈序列．如是队列又是什么情况呢？35循环队列把队列的存储空间在逻辑上看作一个环，当R指向存储空间的末端后，就把它重新置于始端。循环队列的运算队列中进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。

习题：数据结构分为逻辑结构和存储结构，循环队列属于【】结构。（2005年9月）答案：存储结构。36常见数据结构的逻辑结构线性表

线性结构栈

是特殊的线性表

队列

也是一种操作受限的特殊的线性表树（树型结构）是一种重要的非线形数据结构37线性结构与非线性结构线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。a1a2a5a3a4HEAD319510线性链表的逻辑状态

A∧G∧∧

E∧∧

F∧

B∧

C∧

Dt38数据存储结构方面的考题

1：数据的存储结构是指

（2005年4月）

A)存储在外存中的数据

B)数据所占的存储空间量

C)数据在计算机中的顺序存储方式

D)数据的逻辑结构在计算机中的表示2：下列叙述中正确的是（2009年3月）

A）栈是“先进先出”的线性表

B）队列是“先进后出”的线性表

C）循环队列是非线性结构

D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构3.数据结构分为线性结构和非线性结构，带链的队列属于[]。答案：D。答案：D。答案：线性结构。394。下列叙述中正确的是（）。（2008年9月）

A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

C）顺序存储结构能存储有序表，链式存储结构不能存储有序表

D）链式存储结构比顺序存储结构节省存储空间答案：A。5。下列关于栈的叙述正确的是（2008年4月）

A）栈按“先进先出”组织数据B)栈按“先进后出”组织数据

C）只能在栈底插入数据D）不能删除数据

答案：B。6。假设用一个长度为50的数组（数组元索的下标从0到49）作为栈的存储空间，栈底指针bottom指间栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有【】个元素。（2009年3月）

答案：19。40树型结构是一种重要的非线性结构。

树的概念

二叉树的概念

二叉树的存储

二叉树的遍历3.树与二叉树41树的概念

树的定义：n个结点的有限集。（n>=0）树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点

根：onlyone

若n=0，则称为空树；否则，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归的。ABDFECGHIJKM42树型结构的常用术语ABDFECGHIJKM

结点的度一个结点的子树的个数；Q：结点A、G的度数？

树的度树中所有结点度的最大值；Q：右图中树的度？

终端结点度为0的结点；

Q：图中叶子结点有几个？7

非终端结点

度不为0的结点；

Q：图中非终端结点有几个？5孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先43树型结构的常用术语ABDFECGHIJKM

结点的层次树中根结点的层次为1，根结点子树的根为第2层，以此类推；

Q：图中结点F的层次？

树的深度

树中所有结点层次的最大值；

Q：图中树的深度？

有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。①②③④44树的基本术语在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。ABCDFEHG45二叉树的基本性质：（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；（2）深度为m的二叉树最多有2m-1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分；（5）具有n个结点的完全二叉树的深度为[log2n]+1；461213891011456123满二叉树完全二叉树84567123满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点，深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点714151213891011456123非完全二叉树47（5）具有n个结点的完全二叉树的深度为[log2n]+1121314158910114567123深度为4的满二叉树深度为4的完全二叉树84567123深度为３的完全二叉树具有４～７深度为４的完全二叉树具有８～１５深度为５的完全二叉树具有１６～３１log2(8+1)=ln9/In2=4log2(15+1)=In16/In2=4481：在深度为7的满二叉树中,叶子结点的个数为（2006年4月）

A)32

B)31

C)64

D)632：在深度为7的满二叉树中，度为2的结点个数为【】

。(07年4月）3：一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（07年9月）

A）219B）221C）229D）2314：某二叉树中度为2的结点有18个，则该二叉树中有【】个叶子结点。（2005年4月）5：一棵二叉树第六层（根结点为第一层）的结点数最多为【】个。（2005年9月）

树型结构方面的考题

1答案：C。3答案：A。5答案：32。2答案：63。4答案：19。49二叉树的存储在计算机中，二叉树通常采用链式存储结构。LlinkinfoRlink二叉树的存储结点的结构ABDCFGE

A∧G∧∧

E∧∧

F∧

B∧

C∧

Dt50二叉树的遍历（1）前序遍历（DLR）首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LDR）首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。ABCDFEHG遍历指不重复地访问二叉树中的所有结点。二叉树的遍历的次序与树型结构上的大多数运算有联系。51二叉树的遍历ABCDFEHG先序遍历的结果：

ABECFGHD中序遍历的结果：

EBAFHGCD后序遍历的结果：

E

BHGFDCA52先序序列：ABDGCEFH 中序序列：DGBAECHF 后序序列：GDBEHFCAABCFHDEG下图所示的二叉树经过三种遍历得到的顺序分别为？练习：根据先序遍历序列，建立二叉树531:对下列二叉树（06年9月）

进行中序遍历的结果是______。

A）ACBDFEG

B）ACBDFGE

C）ABDCGEF

D）FCADBEG树型结构方面的考题

22:对如下二叉树（2006年4月）D进行后序遍历的结果为A)ABCDEF

B)DBEAFCC)ABDECF

D)DEBFCAAD54⒌查找技术顺序查找：（1）线性表为无序表；（2）表采用链式存储结构。从线性表的第一个元素开始，依次将线性表中的元素与关键字进行比较，若相等，则查找成功；

二分查找：首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为0。适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次。55折半查找算法举例对给定数列（有序）{3，5，11，17，21，23，28，30，32，50}，按折半查找算法，查找关键字值为30的数据元素。

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

第1次：{3，5，11，17，21，23，28，30，32，50}

K=30mid1=（1+10）/2=5

k>a(mid1)=a(5)=21

第2次：{23，28，30，32，50}mid2=（6+10）/2=8K=a(mid2)=a(8)=30lowhighmidlowhighmid56练习

假设待查有序（升序）顺序表中数据元素的关键字序列为（8,18,27,42,47,50,56,68,95,120），用折半查找方法查找关键字值为27的数据元素.对于长度为n的有序线性表，最坏情况只需比较log2n次。

57⒍排序技术

排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。排序方法中其排序对象一般是顺序存储的线性表。根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法：交换类排序法：（1）冒泡排序法；（2）快速排序法。插入类排序法：（1）简单插入排序法；（2）希尔排序法。选择类排序法：（1）简单选择排序法；（2）堆排序法。58冒泡排序冒泡排序的方法：扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大(或最小)的元素排到表的最后(或最前)

；除最后(或最前)一个元素，对剩余的元素重复上述过程，将次大(或次小)的数排到表的倒数(或正数)第二个位置；重复上述过程；对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。59冒泡排序的方法设待排数据元素的关键字为(26,18,32,54,47,9,15)，第一趟冒泡排序后的序列状态如图所示：

2618325447915182632544791518263254479151826325447915182632475491518263247954151826324791554

最大数60初始第一趟第二趟第三趟第四趟第五趟序列排序后排序后排序后排序后排序后 26 18 1818 189 18 26 2626 915 32 32 329 15 18 54