数据结构与算法

第一章数据结构与算法本章内容在笔试中会出现5-6个题目，是公共根底知识局部出题量比较多的一章，所占分值也比较大，约10分。1.1算法一、算法是指解题方案的准确而完整的描述。算法是对特定问题求解步骤的一种描述。二、算法的根本特征：可行性、确定性、有穷性、拥有足够的情报。三、算法的根本要素：〔1〕对数据对象的运算和操作；〔+，-，*，/等等〕。〔2〕算法的控制结构〔顺序结构、选择结构、循环结构〕。对数据对象的运算和操作指令系统：一个计算机系统能执行的所有指令的集合。根本运算包括：〔1〕算术运算：加、减、乘、除等。〔2〕逻辑运算：与、或、非等。〔3〕关系运算：大于，小于，等于，不等于等。〔4〕数据传输：主要包括赋值、输入、输出等操作。1.1算法四、算法设计的根本方法列举法、归纳法、递推、递归、减半递推技术、回溯法。五、算法复杂度：时间复杂度和空间复杂度〔1〕算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需根本运算的执行次数来度量。〔2〕算法空间复杂度是指执行这个算法所需要的内存空间。1.2数据结构1、数据结构是指相互有关联的数据元素的集合。2、数据结构研究的三个方面：〔1〕数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。〔2〕在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。〔3〕对各种数据结构进行的运算。数据的逻辑结构包含：1〕表示数据元素的信息；2〕表示各数据元素之间的前后件关系

。数据的存储结构有顺序、链接、索引等。1〕顺序存储。2〕链接存储。3〕索引存储。3、常见的数据结构常有以下四类根本结构：集合、线性结构、树形结构、图状结构。〔1〕集合特性：元素间为松散的关系。例如：〔2〕线性结构特性：元素间为严格的一对一关系。例如：成绩表中各元素。〔3〕树形结构特性：元素间为严格的一对多关系。例如：〔4〕图形结构特性：元素间为多对多关系。例如：4、数据结构分为：线性结构和非线性结构。〔1〕线性结构〔非空的数据结构〕条件：1〕有且只有一个根结点

；2〕每一个结点最多有一个前件，也最多有一个后件。常见的线性结构有线性表、栈、队列和线性链表等。〔2〕非线性结构：不满足线性结构条件的数据结构。常见的非线性结构有树、二叉树和图等。1.3线性表1、线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。线性表是由n(n≥0)个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。线性表中数据元素的个数称为线性表的长度。线性表可以为空表。*：线性表是一种存储结构，它的存储方式：顺序和链式。2、线性表的顺序存储结构具有两个根本特点〔1〕线性表中所有元素所占的存储空间是连续的；〔2〕线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。*：由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面，可以通过计算机直接确定第i个结点的存储地址。3、顺序表的插入、删除运算〔1〕顺序表的插入运算：顺性表的插入运算时需要移动元素，在等概率情况下，平均需要移动n/2个元素。〔2〕顺序表的删除运算：进行顺性表的删除运算时也需要移动元素，在等概率情况下，平均需要移动〔n-1〕/2个元素。插入、删除运算不方便。1.4栈和队列1、栈及其根本运算栈是限定在一端进行插入与删除运算的线性表。在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈是按照“先进后出〞或“后进先出〞的原那么组织数据的。栈具有记忆作用。栈的根本运算：1〕插入元素称为入栈运算；2〕删除元素称为退栈运算；3〕读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。2、队列及其根本运算队列是指允许在一端〔队尾〕进入插入，而在另一端〔队头〕进行删除的线性表。尾指针〔Rear〕指向队尾元素，头指针〔front〕指向排头元素的前一个位置〔队头〕。队列是“先进先出〞或“后进后出〞的线性表。队列运算包括：1〕入队运算：从队尾插入一个元素；2〕退队运算：从队头删除一个元素。3、循环队列及其运算：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。S=0表示队列空；S=1且front=rear表示队列满。4、队列中的元素的个数=rear-front。1.5线性链表结点：数据结构中每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。线性表的链式存储结构称为线性链表，是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的。链式存储：要求每个结点由两局部组成，一局部用于存放数据元素值，称为数据域；第二局部用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点。1.5线性链表线性链表：线性表的链式存储结构。线性链表的表示方式：单指针和双指针。线性链表中，head称为头指针，head=null〔或0〕称为空表，如果有两个指针，有左右之分，左指针〔Llink〕指向前件结点，右指针(Rlink〕指向后件结点。线性链表的运算：查找、插入、删除。1.6树与二叉树1、树的根本概念树是一种简单的非线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。在树结构中，每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。结点A的度：结点B的度：结点M的度：树中的叶子：结点A的孩子：结点B的孩子：结点I的双亲：结点L的双亲：树的度：结点A的层次：结点M的层次：树的深度：B，C，DE，F3414K，L，F，G，M，I，JDEABCDEFGHIJKLM3202、二叉树的重要特性性质1:在二叉树的第i层上至多有2i-1个结点(i≥1)性质2：深度为k的二叉树上至多含2k-1个结点〔k≥1〕性质3：对任何一棵二叉树，假设他含有n0个叶子结点、n2个度为2的结点，那么必存在关系式：n0=n2+1两种特殊形式的二叉树〔1〕满二叉树：指的是深度为k且含有2k-1个结点的二叉树。特点：每一层上的结点数都是最大结点数。深度为k的满二叉树有2k-1个结点。〔2〕完全二叉树：除最后一层外，每一层上的结点数均到达最大值，在最后一层只能缺少右边的假设干结点。1231145891213671014151231145891267101234567123456性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，那么对任一结点i(1≤I≤n)，有：(1)如果i=1，那么结点i是二叉树的根，无双亲；如果i>1，那么其双亲是i/2(2)如果2i>n，那么结点i无左孩子；如果2i≤n，那么其左孩子是2i(3)如果2i+1>n，那么结点i无右孩子；如果2i+1≤n，那么其右孩子是2i+1性质4：1、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为〔〕个。2、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，那么叶子结点数为〔〕个。3、在一棵二叉树上第5层的结点数最多为：解析：画出任意一棵满足要求的树，数一下叶子个数。6个。由性质3得n0=n2+1，那么叶子结点为16个。由性质1得：164、深度为k〔设根的层数为1〕的完全二叉树至少有〔〕个结点，至多有〔〕个结点，k和结点数n之间的关系为〔〕。5、一棵有124个叶结点的完全二叉树，最多有〔〕个结点。2k-12k-1k=1+[log2n]分析：由性质3得知：n0=n2+1;所以n2=n0-1=123,因为是完全二叉树,度为1的结点要有也只能为一个;所以结点数为：n=n0+n1+n2=123+124+1=2481．假设一棵二叉树具有10个度为2的结点，5个度为1的结点，那么度为0的结点个数是〔〕A．9B．11C．15D．不确定2．具有10个叶结点的二叉树中有〔〕个度为2的结点A．8B．9C．10D．ll3．一棵完全二叉树上有1001个结点，其中叶子结点的个数是〔〕A．250B．500C．254D．505E．以上答案都不对4.有关二叉树以下说法正确的选项是〔〕A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2BBEB5．二叉树的第I层上最多含有结点数为〔〕A．2IB．2I-1-1C．2I-1D．2I-16．对于有n个结点的二叉树,其高度为〔〕A．nlog2nB．log2nC．|log2n|+1D．不确定7.一棵树高为K的完全二叉树至少有〔〕个结点A．2k-1B.2k-1-1C.2k-1D.2kCDC1．二叉树由_(1)__，__(2)_，_(3)__三个根本单元组成。5．深度为H的完全二叉树至少有_(1)__个结点；至多有_(2)__个结点；6．一棵有n个结点的满二叉树有__(1)_个度为1的结点、有__(2)_个分支〔非终端〕结点和__(3)_个叶子，该满二叉树的深度为_(4)__。根结点左子树右子树2H-12H-10(n-1)/2(n+1)/2[Log2n]+17．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。8．设只含根结点的二叉树的高度为0，那么高度为k的二叉树的最大结点数为______,最小结点数为______。9．二叉树有50个叶子结点，那么该二叉树的总结点数至少是______。10．一个有2001个结点的完全二叉树的高度为______。n2K+1-1K+199116、判断正误：完全二叉树的某结点假设无左孩子，那么它必是叶结点。7、具有n个结点的满二叉树，其叶结点的个数为〔〕。正确，根据完全二叉树的定义，假设某一结点没有左孩子，必定没有右孩子，因此是叶结点。(n+1)/2由性质3：n0=n2+1;由满二叉树知，只有度为0和度为2的结点，所以n=n0+n2,即n=n0+n0-1,所以推出n0=(n+1)23、二叉树的存储结构一般二叉树通常采用链式存储结构，对于满二叉树与完全二叉树来说，可以按层序进行顺序存储。

4、二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树常用的遍历可以分为以下三种：〔1〕前序遍历〔DLR〕：假设二叉树为空，那么结束返回。否那么：首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。〔2〕中序遍历〔LDR〕；〔3〕后序遍历〔LRD〕；〔2〕中序遍历〔LDR〕：假设二叉树为空，那么结束返回。否那么：首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

〔3〕后序遍历〔LRD〕：假设二叉树为空，那么结束返回。否那么：首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。遍历例题1CDEHFGBA中序序列为：ABCEFGHD后序序列为：ABFHGEDC先序序列为：CBADEGFH2先序遍历：中序遍历：后序遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef考试例题3FEGCABD中序遍历的结果为：ACBDFEG如果考试的题目是给定一棵树，写出相应的中序遍历序历，最简单的方法是投影得出的序历。1.7查找技术查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。查找结果：〔查找成功：找到；查找不成功：没找到。〕平均查找长度：查找过程中关键字和给定值比较的平均次数。查找方法：1、顺序查找根本思想：从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否那么就是表中没有要找的元素，查找不成功。在平均情况下，顺序查找法最坏情况下需要比较n次。顺序查找一个具有n个元素的线性表，其平均复杂度为O〔n〕。以下两种情况下只能采用顺序查找：1〕如果线性表是无序表〔即表中的元素是无序的〕，那么不管是顺序存储结构还是链式存储结构，都只能用顺序查找。2〕即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。2、二分法查找前提：必须在具有顺序存储结构的有序表中进行。查找过程：1〕假设中间项〔中间项mid=(n-1)/2，mid的值四舍五入取整〕的值等于x，那么说明已查到；2〕假设x小于中间项的值，那么在线性表的前半局部查找；3〕假设x大于中间项的值，那么在线性表的后半局部查找。二分法查找的特点：对于有n个元素的线性表：特点：比顺序查找方法效率高。最坏的情况下，需要比较log2n次。顺序查找需要比较n次。*：二分法查找只适用于顺序存储的线性表，且表中元素必须按关键字有序〔升序〕排列。在长度为n的有序线性表中进行二分法查找，其时间复杂度为O〔log2n〕。1.8排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列，即是将无序的记录序列调整为有序记录序列的一种操作。1、交换类排序法〔方法：冒泡排序，快速排序〕。2、插入类排序法〔方法：简单插入排序，希尔排序〕。3、选择类排序法〔方法：简单项选择择排序，堆排序〕。本章习题1一.选择题

1.算法的时间复杂度是指(

)

A.

执行算法程序所需要的时间

B.

算法程序的长度

C.

算法执行过程中所需要的根本运算次数

D.

算法程序中的指令条数

2.算法的空间复杂度是指(

)

A.

算法程序的长度

B.

算法程序中的指令条数

C.

算法程序所占的存储空间

D.

算法执行过程中所需要的存储空间CD本章习题23.以下表达中正确的选项是(

)

A.

线性表是线性结构

B.

栈与队列是非线性结构

C.

线性链表是非线性结构

D.

二叉树是线性结构

4.数据的存储结构是指(

)

A.

数据所占的存储空间量

B.

数据的逻辑结构在计算机中的表示

C.

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

D.

存储在外存中的数据AB本章习题35.以下关于队列的表达中正确的选项是(

)

A.

在队列中只能插入数据

B.