《公共基础课件.ppt》由会员分享，可在线阅读，更多相关《公共基础课件.ppt（241页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、公共基础课件公共基础课件考试方式1、公共基础的考试方式为笔试，与C语言（VisualBASIC、Visual FoxPro、Java、Access、Visual C+）的笔试部分合为一张试卷。公共基础部分占全卷的30分。2、公共基础知识有10道选择题和5道填空题。（15*2）基本要求1.掌握算法的基本概念。2.掌握基本数据结构及其操作。3.掌握基本查找和排序算法。4.掌握逐步求精的结构化程序设计方法。5.掌握软件工程的基本概念。6.掌握数据库的基本知识，了解关系数据库的设计。学习方法基本概念要理解理解的基础上适当记忆一些概念多做练习，从练习中总结与所学的知识结合起来，以增加对知识的理解能力考试
2、内容：第一章1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。考试内容：第二章1.程序设计方法与风格。2.结构化程序设计。3.面向对象的程序设计方法，对象，方法，
3、属性及继承与多态性。考试内容：第三章1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。3.结构化设计方法，总体设计与详细设计。4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5.程序的调试，静态调试与动态调试。考试内容：第四章1.数据库的基本概念：数据库，数据库管理系统，数据库系统。2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4.数据库设计方法和步骤：需求分析、概念设计、逻辑设
4、计和物理设计的相关策略。第一章 数据结构与算法1.1算法1.1.1 1.1.1 算法的基本概念算法的基本概念算法算法：是指解题方案的准确而完整的描述。（是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。）算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，取能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。算法的基本要素：算法的基本要素：一是对数据对象的运算
5、和操作；二是算法的控制结构。（1）算法中对数据的运算和操作计算机指令系统：一个计算机系统能执行的所有指令的集合。基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。（2）算法的控制结构：一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。描述算法的工具通常有传统流程图、有传统流程图、NSNS结构化流程图、结构化流程图、算法描述语言算法描述语言等。一个算法一般都可以用顺序、选择、循环顺序、选择、循环三种基本控制结构组合而成。算法设计基本方法算法设计基本方法v（1）列举法：根据提出的问题，列举所有可能的情况，并用问题中给定的
6、条件检验哪些是需要的，哪 些是不需要的。v（2）归纳法：通过列举少量的特殊情况，经过分析，最后找出一般的关系。v（3）递推：是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。算法设计基本方法（续）算法设计基本方法（续）v（4）递归：将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决到最后那些最简单的总是后，再沿着原来分解的逆过程逐步进行综合，v（5）减半递推技术：所谓“减半”，是指将问题材的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。v（6）回溯法：通过对问题的分析，找出一个解决总是的线索，然后沿着这个线索，然后沿着这个线索逐步试探，对于每一步的
7、试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。1.1.2算法的复杂度算法的复杂度算法复杂度：算法时间复杂和算法空间复杂度算法时间复杂和算法空间复杂度。1.算法的时间复杂度算法时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量=f(n)(1)平均性态：是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。算法的平均性态定义：(2)最坏情况复杂性：是指在规模为n时，算法所执行的基本运算的最大次数。O(1)常量级 O(n)线性级 O(n2)平方级时间复杂度举
8、例1 X=X+1 S=0此算法的基本操作是赋值语句。执行两条语此算法的基本操作是赋值语句。执行两条语句各一次，共句各一次，共2次次,与规模无关。时间复杂度与规模无关。时间复杂度为为(1)，即常量阶。，即常量阶。执行次数：执行次数：2时间复杂度：时间复杂度：O(1)时间复杂度举例2 For i=1 to n x=x+1 s=s+xNext i 执行次数为：执行次数为：2n其时间复杂度为：其时间复杂度为：O(n)即时间复杂度为线性阶。即时间复杂度为线性阶。时间复杂度举例3For i=1 to n For j=1 to n x=x+1 s=s+x next jNext i 基本语句基本语句执行次数执
9、行次数2n2其时间复杂度为：其时间复杂度为：O(n2)即时间复杂度为平方阶。即时间复杂度为平方阶。2.算法空间复杂度算法空间复杂度是指执行这个算法所需要的内存空间。算法空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。算法的空间复杂度和时间复杂度没有直接的联系。例题讲解 算法的时间复杂度是指A)执行算法程序所需要的时间 B)算法程序的长度C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数算法的基本特征是可行性、确定性、【1】和拥有足够的情报。算法的空间复杂度是指 A)算法程序
10、的长度 B)算法程序中的指令条数 C)算法程序所占的存储空间 D)执行过程中所需要的存储空间在计算机中，算法是指 A)加工方法B)解题方案的准确而完整的描述 C)排序方法D)查询方法1.2数据结构的基本概念 数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。讨论以上问题的主要目的是为了提高数据的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。算法分析的目的是 A)找出数据结
11、构的合理B)找出算法中输入和输出之间的关系 C)分析算法的易懂性和可靠性 D)分析算法的效率以求改进算法的工作量大小和实现算法所需的存储单元多少分别称为算法的【1】。1.2.1什么是数据结构数据结构数据结构是指反映数据元素之间关系的数据元素的集合的表示。1、数据的逻辑结构数据结构包含：v（1 1）表示数据元素的信息；）表示数据元素的信息；v（2 2）表示各数据元素之间的）表示各数据元素之间的前后件前后件关系。关系。逻辑结构是指反映数据元素之间逻辑关系的数据结构。2、数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。数据元素在计算机存储空间中的位
12、置关系可能与数据元素的逻辑结构不同。数据的存储结构有顺序、链接、索引等。1.2.2数据结构的图形表示例如：一年四季的数据结构可以用图形来表示。春夏秋冬用图形表示数据结构B=（D，R），其中 D=di|1=in时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度 在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为
13、n-i+1。pi 是在第i 个元素之前插入一个元素的概率，故 Eis(n)=pi(n-i+1)不失一般性，假设在表中任何位置(1in+1)上插入结点的机会是均等的，则 p1=p2=p3=p（n+1）=1/(n+1)因此，在等概率插入的情况下，Eis(n)=(n-i+1)/(n+1)线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。删除运算是
14、指将表的第i(1in)结点删去,使得长度为n的线性表变成n-1的线性表。(a0,a1,ai-1,ai,an-1)a0a1ai-1aiai+1an-1删除lastmaxsize删除前删除前a0a1ai-1ai+2an-1lastmaxsize删除后删除后ai+11.3.4 顺序表的删除运算算法思想：删除第i个元素时，需要将n至i+1个（共n-I）个元素向前移动一个位置。步骤：v 1 1、检查删除要求的有关参数的合理性、检查删除要求的有关参数的合理性v 2 2、把原来的第、把原来的第I+1I+1个数据元素至第个数据元素至第n n个（共个（共n-In-I）个元个元素依次向前移动一个位置素依次向前移动
15、一个位置v 3 3、修正线性表的数据元素个数。、修正线性表的数据元素个数。删除算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i 决定。若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若i=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故 Ede(n)=pi(n-i)式中，pi表示删除表中第i个结点的概率。在等概率的假设下，p1=p
16、2=p3=pn=1/n在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。平均时间复杂度也是O(n)。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。算法复杂性分析算法复杂性分析1、插入、插入 n/2 T(n)=O(n)2、删除、删除 (n-1)/2 T(n)=O(n)顺序表的基础要点1 1、线性表是具有、线性表是具有n n个数据元素的有限序列。个数据元素的有限序列。2 2、线性表的顺序存储结构具有三个弱点：、线性表的顺序存储结构具有三个弱点：v在插入和
17、删除时，需移动大量元素v由于难以估计，必须预先分配较大的空间v表的容量难以扩充(如何解决？）3 3、顺序存储结构通过元素的相对存储地址来表示元素之、顺序存储结构通过元素的相对存储地址来表示元素之间的关系间的关系4 4、线性表顺序存储的优点是可随机存取元素。、线性表顺序存储的优点是可随机存取元素。顺序表的基础要点（续）5 5、顺序表中逻辑上相邻的元素的物理位置必定紧邻。、顺序表中逻辑上相邻的元素的物理位置必定紧邻。6 6、顺序表是一种随机存取的存储结构。、顺序表是一种随机存取的存储结构。7 7、在顺序表中插入或删除一个元素时，需要平均移动表、在顺序表中插入或删除一个元素时，需要平均移动表的一半元
18、素，具有移动的元素个数与该元素的位置有关。的一半元素，具有移动的元素个数与该元素的位置有关。8 8、在长度为、在长度为n n的顺序表中插入一个元素的时间复杂度为的顺序表中插入一个元素的时间复杂度为O(n)O(n)，删除一个元素的时间复杂度为，删除一个元素的时间复杂度为O(n)O(n)。1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。A线性结构 B非线性结构A 顺序存储 B 链式存储 线性表栈队树形结构图形结构数据结构的三个方面(亦称物理结构亦称物理结构)栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的表尾端进行。如下所示：进行插
19、入和删除的表尾端是浮动端，通常被称为栈顶，an 为栈顶元素，并用一个“栈顶指针”指示；而表头端是固定端，通常被称为栈底，a1 为栈底元素，。我们经常将栈用下图的形式描述：a1,a2,a3,.,an 插入和删除端插入和删除端结论：结论：后进先出后进先出（Last In First Out），简称为），简称为LIFO线性线性表。表。举例举例1：家里吃饭的碗，通常在洗干净后一个一个地：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。走最上面的那只碗，而最后拿出最下面的
20、那只碗。举例举例2：在建筑工地上，使用的砖块从底往上一层一层：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。地码放，在使用时，将从最上面一层一层地拿取。栈的基本运算：v（1 1）插入元素称为入栈运算；）插入元素称为入栈运算；v（2 2）删除元素称为退栈运算；）删除元素称为退栈运算；v（3 3）读栈顶元素是将栈顶元素赋给一个指定的变量，）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化此时指针无变化 栈顶指针和栈中元素之间的关系栈顶指针和栈中元素之间的关系basetopbase A A B C D Etopbase=top 空栈top 指向栈顶元素的
21、下一个位置当base=时，表明栈结构不存在。base topbase A B Ctop 1.4.2 队列及其基本运算队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an，也就是说队
22、列的修改是依先进先出的原则进行的。下图是队列的示意图：a1a2an 插入端和删除端都是浮动的。通常我们将插入端称为队尾，用一个“队尾指针”指示；而删除端被称为队头，用一个“队头指针”指示。结论：先进先出（First In First Out），简称为FIFO线性表。出队入队v队列的顺序存储结构队列的顺序存储结构实现：用一维数组实现sqMfront=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初
23、值front=rear=-1空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront存在问题存在问题v设数组维数为设数组维数为M M，则：则：v当当front=-1,rear=M-1front=-1,rear=M-1时，再有元素入队发生溢出时，再有元素入队发生溢出真溢出真溢出v当当frontfront-1,rear=M-1-1,rear=M-1时，再有元素入队发生溢出时，再有元素入队发生溢出假溢出假溢出解决方案解决方案v队首固定，每次出队剩余元素向下移动
24、队首固定，每次出队剩余元素向下移动浪费时间浪费时间v循环队列循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;0M-11frontrear.实现：利用“模”运算入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队空判定条件012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear解决方案：1.另外设一个标
25、志以区别队空、队满队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满1.5.1 线性链表的基本概念线性表顺序存储结构的特点：是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。线性表顺序存储结构暴露的问题v在做插入
26、或删除元素的操作时，会产生大量的数据元素移在做插入或删除元素的操作时，会产生大量的数据元素移动；动；v对于长度变化较大的线性表，要一次性地分配足够的存储对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；空间，但这些空间常常又得不到充分的利用；v线性表的容量难以扩充。线性表的容量难以扩充。1.5 线性链表线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示数据元素间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位
27、置的信息。这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：datalink指针域，用来存放结点指针域，用来存放结点的直接后继的地址的直接后继的地址数据域，用来数据域，用来存放结点的值存放结点的值 线性表的链式存储结构例如：线性表（a,b,c,d)数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的
28、逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构，也可用于表示非线性结构。术语v表示每个数据元素的两部分信息组合在一起被称为结表示每个数据元素的两部分信息组合在一起被称为结点；点；v其中表示数据元素内容的部分被称为数据域（其中表示数据元素内容的部分被称为数据域（datadata）；）；v表示直接后继元素存储地址的部分被称为指针或指针表示直接后继元素存储地址的部分被称为指针或指针域（域（nextnext）。）。headd cba单联表结构示意图单联表结构示意图datalink其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，
29、所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（）符号表示。110 hat 200130 cat 135135 eat 170160 mat NULL165 bat 130170 fat 110200 jat 205205 lat 160165head头指针数据域 指针域例如：线性表例如：线性表（bat,cat,eat,fat,hat,jat,lat,mat）单链表只注重结点单链表只注重结点的逻辑顺序，不关心每的逻辑顺序，不关心每个结点的实际存储位置，个结点的实际存储位置，因此用箭头来表示链域因此用箭头来表示链域中的指针。中的指针。bat cat eat mat head链式
30、存储结构的特点v（1 1）线性表中的数据元素在存储单元中的存放顺序与逻）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；辑顺序不一定一致；v（2 2）在对线性表操作时，只能通过头指针进入链表，并）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。等，具有这种特点的存取方式被称为顺序存取方式。1.5.2 线性链表的基本运算1、在线性链表中查找指定元素在对
31、线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，要线性链表中指定值的前一个结点。v单链表的基本运算单链表的基本运算查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULLWhile循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n算法评价pabxs插入：在线性表两个数据元素a和b间插入x，已知p指向as-link=p-link;p-link=s;v算法评价算法评价pabc删除：删除链表中b结点，已知p指向a结点p-link=p-link-linkv算法评价算法评价循环链表循环链表(circular linked
32、list)(circular linked list)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同v单链表单链表p p或或p-link=NULLp-link=NULLv循环链表循环链表p p或或p-link=Hp-link=Hhh空表 双向链表（双向链表（double linked listdouble linked list）单链表具有单向性的缺点单链表具有单向性的缺点L空双向循环链表：非空双向循环链表：LABp-prior-next=p=p-next-proir;若是栈中元素的数目变化
33、范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图所示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。栈的链式存储 top队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一确定。添加头节点。和顺序队列类似，我们也是将这两个指针封装在一
34、起frontrear队列的链式存储例题讲解链表不具有的特点是A)不必事先估计存储空间 B)可随机访问任一元素C)插入删除不需要移动元素 D)所需空间与线性表长度成正比数据结构分为逻辑结构与存储结构，线性链表属于 【1】。数据结构中，与所使用的计算机无关的是数据的 A)存储结构B)物理结构 C)逻辑结构D)物理和存储结构 数据的逻辑结构有线性结构和【1】两大类。数据处理的最小单位是 A)数据 B)数据元素 C)数据项D)数据结构数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及 A)数据的存储结构B)计算方法C)数据映象D)逻辑存储线性表的顺序存储结构和线性表的
35、链式存储结构分别是 A)顺序存取的存储结构、顺序存取的存储结构 B)随机存取的存储结构、顺序存取的存储结构 C)随机存取的存储结构、随机存取的存储结构 D)任意存取的存储结构、任意存取的存储结构 顺序存储方法是把逻辑上相邻的结点存储在物理位置【2】的存储单元中。根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成 A)动态结构和静态结构 B)紧凑结构和非紧凑结构 C)线性结构和非线性结构 D)内部结构和外部结构 数据结构包括数据的逻辑结构、数据的【2】以及对数据的操作运算。数据的基本单位是【5】。下列叙述中，错误的是 A)数据的存储结构与数据处理的效率密切相关 B)数据的存储结
36、构与数据处理的效率无关 C)数据的存储结构在计算机中所占的空间不一定是连续的 D)一种数据的逻辑结构可以有多种存储结构数据的存储结构是指A A）数据所占的存储空间数据所占的存储空间B B）数据的逻辑结构在计算机中的表示）数据的逻辑结构在计算机中的表示C C）数据在计算机中的顺序存储方式）数据在计算机中的顺序存储方式D D）存储在外存中的数据存储在外存中的数据 下列叙述中，错误的是 A)数据的存储结构与数据处理的效率密切相关 B)数据的存储结构与数据处理的效率无关 C)数据的存储结构在计算机中所占的空间不一定是连续的 D)一种数据的逻辑结构可以有多种存储结构线性表若采用链式存储结构时，要求内存中
37、可用存储单元的地址 A)必须是连续的 B)部分地址必须是连续的 C)一定是不连续的 D)连续不连续都可以栈和队列的共同特点是 A)都是先进先出 B)都是先进后出 C)只允许在端点处插入和删除元素 D)没有共同点如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是 A)e3,e1,e4,e2 B)e2,e4,e3,e1 C)e3,e4,e1,e2D)任意顺序一些重要的程序语言(如C语言和Pascal语言)允许过程的递归调用。而实现递归调用中的存储分配通常用 A)栈B)堆 C)数组 D)链表当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为【2】。栈底至栈
38、顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是 A)ABCED B)DCBEA C)DBCEA D)CDABE 栈通常采用的两种存储结构是 A)顺序存储结构和链表存储结构B)散列方式和索引方式 C)链表存储结构和数组 D)线性存储结构和非线性存储结构栈和队列通常采用的存储结构是【1】。下列数据结构中，按先进后出原则组织数据的是 A)线性链表 B)栈 C)循环链表 D)顺序表由两个栈共享一个存储空间的好处是 A)减少存取时间，降低下溢发生的机率 B)节省存储空间，降低上溢发生的机率 C)减少存取时间，降低上溢发生的机率 D)节省存储空间，降低下溢发生的机率
39、下列关于栈的叙述中正确的是）在栈中只能插入数据 B）在栈中只能删除数据C）栈是先进先出的线性表 D）栈是后进先出的线性表下列关于队列的叙述中正确的是）在队列中只能插入数据 B）在队列中只能删除数据C）队列是先进先出的线性表 D）队列是后进先出的线性表1.6树与二叉树 树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为
40、树的深度。树是一种常用的非线性结构。我们可以这样定义：树是n（n0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。(C)是有13个结点的树，其中A是根，其余结点分成3个子集：T T1 1、T T2 2、T T3 3。都是根A的子树，且本身也是一棵树。例如：T T1 1 其根为B，两棵子树为 T T11 11 =F T T1212 =E,K,L，T T1212 又是一棵子树，树根为F，K 和 L是E的两个互不相交的子集。结点：数据元素的内容及其
41、指向其子树根的分支统称为结点。结点的度（Degree):结点的分支数，即结点拥有的子树数。终端结点（叶子leaf）:度为0的结点。非终端结点:度不为0的结点。结点的层次:树中根结点的层次为1，根结点子树的根为第2 层，以此类推。树的度:树中所有结点度的最大值。树的深度:树中所有结点层次的最大值。有序树、无序树:如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。术语术语1.6.2二叉数及其基本性质1.定义定义：定义：二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。二叉树也可以用递归的形式定义。即：二叉树是n（n
42、0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。G HD E FB CA 二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的二叉树的5 5种形态：种形态：(a)(b)(c)(d)(e)(a)空树空树 (b)只有根结点的二叉树只有根结点的二叉树 (c)右子树为空的二叉右子树为空的二叉树树 (d)左子树为空的二叉树左子树为空的二叉树 (e)左、右子树均非空的二叉树左、右子树均非空的二叉树二叉树具有下
43、列5个重要的性质。【性质1】在二叉树的第i层上最多有2i-1个结点（i1）。二叉树的第1层只有一个根结点，所以，i=1时，2i-1=21-1=20=1成立。假设对所有的j，1ji成立，即第j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。二叉树的性质二叉树的性质【性质2】深度为K的二叉树最多有2K-1个结点(K1）。由性质1可以得出，1至K层各层最多的结点个数分别为：20,21,22,23,.,2K-1。这是一个以2为比值的等
44、比数列，前n项之和的计算公式为：其中 a1为第一项，an为第k项，q为比值。可以得到，该数列前K项之和为：【性质3】对于任意一棵二叉树BT，如果度为0的结点（叶子）个数为n0，度为2的结点个数为n2，则n0=n2+1。证明：1.假设度为1的结点个数为n1，结点总数为n。因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：n=n0+n1+n2 （1）2.设B为二叉树中的分支数从入支的角度看，即前驱结点的角度看，二叉树中，除根结点之外，其余每个结点都有一个且只有一个前驱结点，即有一个从上向下的分支指向(即占有一个分支)，所以，总的结点个数n与分支数B之间的关系为：n=B+1。（2）从出支的
45、角度看，即后继结点的角度看，因为在二叉树中，度为0的结点没有后继结点，即不占分支，度为1的结点有一个后继结点，产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。（3）将此式代入上式，得：n=n1+2n2+1 （4）用（1）式减去（4）式，并经过调整后得到：n0=n2+1。满二叉树：如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。8 9 10 11 12 13 14 154 5 6 72 31完全二叉树：完全二叉树：有一棵深度为有一棵深度为h h，具有，具有n n个结点的二叉树，若个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，
46、将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为分别与满二叉树中编号为1n1n的结点位置一一对应，则称的结点位置一一对应，则称这棵二叉树为这棵二叉树为完全二叉树完全二叉树。8 9 10 11 12 4 5 6 72 31 7 8 94 5 6 2 31 4 5 62 31一棵满二叉树一定是一棵完全二叉树，而一棵完全二叉树不一定是满二叉树。完全二叉树的特点：（1）叶子结点只可能在层次最大的两层上出现（2）对任意结点，若其右分支下的子孙的最大层次是l，则其左分支下的子孙的最大
47、层次必是l 或l+1【性质4】具有n个结点的完全二叉树的深度为 log2n+1。其中，log2n 的结果是不大于log2n的最大整数。证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：2K-1-1n2K-1将不等式两端加1得到：2K-1n2K将不等式中的三项同取以2为底的对数，并经过化简后得到：K-1log2n 1其双亲结点的编号为 i/2。（2）如果2in，则结点i没有左孩子（结点i为叶子结点）；否则其左孩子结点的编号为2i。（3）如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。2i+2 2i 2i+1 2i+2 2i+3 i+1 2i 2i+1i i
48、 i+1二叉树的基本性质：（1）在二叉树的第k层上，最多有2k-1(k1)个结点；（2）深度为m的二叉树最多有2 m-1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分；（5）具有n个结点的完全二叉树的深度为log2n+1；满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。（6）设完全二叉树共有n个结点。如果从根结点开始，按
49、层序（每一层从左到右）用自然数1，2，.n给结点进行编号（k=1,2.n），有以下结论：v 若若k=1k=1，则该结点为根结点，它没有父结点；若则该结点为根结点，它没有父结点；若k1k1，则该结，则该结点的父结点编号为点的父结点编号为INT(k/2)INT(k/2)；v 若若2kn2kn，则编号为，则编号为k k的结点的左子结点编号为的结点的左子结点编号为2k2k；否则该结；否则该结点无左子结点（也无右子结点）；点无左子结点（也无右子结点）；v 若若2k+1n2k+1n，则编号为，则编号为k k的结点的右子结点编号为的结点的右子结点编号为2k+12k+1；否则；否则该结点无右子结点。该结点无右
50、子结点。1.6.3 二叉树的存储结构二叉树通常使用链式存储结构。链式存储结构 常见的二叉树结点结构如下所示：常见的二叉树结点结构如下所示：G HD E FB CA G H D E F B CABT这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。1.6.4二叉的遍历二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更