下载文档原格式
第 4 章广义线性表——多维数组和广义表2005-07-14第 4 章广义线性表——多维数组和广义表课后习题讲解1. 填空⑴数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。
【解答】存取，修改，顺序存储【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。
除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。
⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。
【解答】1140【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。
⑶设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。
【解答】d+41【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。
⑷稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。
【解答】三元组顺序表，十字链表⑸广义表((a), (((b),c)),(d))的长度是（），深度是（），表头是（），表尾是（）。
【解答】3，4，(a)，((((b),c)),(d))⑹已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。
【解答】Head(Head(Tail(LS)))2. 选择题⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。
数据结构之数组（Array）详解数组(Array)是由相同类型的元素(element)集合组成的固定长度(Size)的⼀种数据结构。
在内存中是连续存储的，因此可以通过索引(Index)计算出某个元素的地址。
下⾯介绍都是已java为⽰例。
对于没有详细了解过的相信有所收获。
基础知识声明type arrayName[] 或者 type[] arrayName。
如：int arrInt[] 或者int[] arrInt声明过程，只是告诉编译器: arrInt变量保存了⼀个int类型的数组。
这个过程并没有分配内存。
new分配内存分配内存需要通过new完成，同时指明类型和数组⼤⼩。
如：int[] arrInt = new int[4];数组中元素通过new分配后⾃动完成初始化，⼀般有⼏种：数字类型初始化为0(如：int/byte/short/long初始化为0，float/double初始化为0.0)，布尔型初始化为false(boolean 初始化为false),String或者其他对象类型初始化为null。
数组赋值也有两种int[] arrInt = {1,3,5,7};或int[] arrInt = new int[4];arrInt[0] = 1;arrInt[1] = 3;arrInt[2] = 5;arrInt[3] = 7;⽰意图如下：多维数组多维数组类似，即数组中的元素也是数组。
如int[][] arrInt = {{1,3,5},{2,4,6},{0,10,20}};⽰意图如下：数组特点1. 索引(即下标) ⼀般从0开始，如java, C/C++。
2. 长度固定，在申请时长度固定。
内存连续，在内存中则是申请⼀块连续的固定⼤⼩的空间。
3. 数组有⼀维数组和多维数组，数组元素可以是基本数据类型(Primitive)，也可以是对象引⽤(Reference)。
4. 随机访问，能够根据位置(下标)直接访问到元素。
一、课程简介算法与数据结构是计算机等相关专业的一门十分重要的专业基础课，在计算机学科中起到承前启后的作用。
它主要研究计算机加工对象的逻辑结构、在计算机中的表示形式以及实现各种基本操作的算法。
要求学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析技术，培养学生数据抽象的能力。
本课程主要是让我们掌握数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序等内容。
二、各章知识点概述第一章---绪论学习内容：数据结构相关的基本概念，包括数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构等；算法时间复杂度的分析。
重难点：数据结构相关的基本概念，数据结构所含两个层次的具体含义及其相互关系以及算法时间复杂度的分析方法（多重循序）。
第二章---线性表学习内容：第二章线性表主要内容是顺序表和链表的相关概念，顺序表和链表的查找、插入和删除等相关操作及其算法实现，链表的创建算法，并能够设计出线性表应用的常用算法，比如线性表的合并等；能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合，明确它们各自的优缺点。
重难点：理清顺序表和链表的特点，学会用C写相关操作的代码。
第三章---栈和队列学习内容：栈和队列的特点。
顺序栈和链栈的进栈和出栈算法，以及循环队列和链队列的进队和出队算法。
重难点：学会灵活运用栈和队列解决实际应用问题，用C及栈和队列的特点写相关操作的代码。
比如表达式求值算法，理解递归算法执行过程中栈的状态变化过程，以更好地使用递归算法等。
第四章---串、数组和广义表学习内容：串的存储方法，理解串的两种模式匹配算法—BF算法和KMP算法。
明确数组和广义表这两种数据结构的特点，数组地址计算方法，几种特殊矩阵的压缩存储方法。
广义表的定义、性质及GetHead和GetTail的操作。
重难点：KMP算法；数组存储时地址的计算方法等。
B(2.0) D(2.0) D(2.0) D(2.0) D(2.0) A(2.0) B(2.0) B(2.0) D(2.0) C(2.0) D(2.0) D(2.0)2-1广义表是一种（B）数据结构。
(2分)1.非递归的2.递归的3.树型4.图状作者: 严冰单位: 浙江大学城市学院2-2一个广义表为( a, (b, c), d, (), ((f, g), h) )，则该广义表的长度与深度分别为（D）。
(2分)1.4和62.6和33.3和54.5和3作者: 严冰单位: 浙江大学城市学院2-3稀疏矩阵的快速转置算法的时间复杂度是（D）。
(2分)1.三次方时间2.二次方时间3.对数时间4.线性时间作者: 严冰单位: 浙江大学城市学院2-4在定义稀疏矩阵的十字链接存储结构时，每个结点结构需包含（D）个域。
(2分)1. 42. 33. 64. 5作者: 严冰单位: 浙江大学城市学院2-5广义表与稀疏矩阵都是线性表的扩展，它们的共同点为（D）。
(2分)1.都可以用链接结构与顺序结构存储2.无共同点3.都是递归结构4.数据元素本身是一个数据结构作者: 严冰单位: 浙江大学城市学院2-6(neuDS_C++)以下叙述中正确的是(A )。
(2分)1.串是一种特殊的线性表2.串的长度必须大于零3.串中元素只能是字母4.空串就是空白串作者: 姚志军单位: 广东东软学院2-7(neuDS_C++)串是一种特殊的线性表，其特殊性体现在(B )。
(2分)1.可以顺序存储2.数据元素是一个字符3.可以链接存储4.数据元素可以是多个字符作者: 姚志军单位: 浙江大学2-8(neuDS_C++)设有两个串p和q，求q在p中首次出现的位置的运算称作( B)。
(2分)1.连接2.模式匹配3.求子串4.求串长作者: 姚志军单位: 广东东软学院2-9(neuDS_C++)设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x,y)返回x和y 串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是(D )。
第1 章绪论一、基础题1. A2. C3. C4. A5. C二、扩展题1.数据是计算机加工处理的对象；数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理；数据项是组成数据元素的、不可分割的最小单位。
2.数据结构是按某种逻辑关系组织起来的数据元素的集合，使用计算机语言描述并按一定的存储方式存储在计算机中，并在其上定义了一组运算。
3.集合结构、线性结构、树形结构和图形结构。
集合结构中，元素之间没有关系；线性结构中，元素之间存在一对一的关系；树形结构中，元素之间存在一对多的关系，其中最多只有一个元素没有前驱元素，这个元素就是根；图形结构中，元素之间存在多对多的关系。
4.顺序存储、链式存储、索引存储和散列存储。
5.一个算法是对特定问题的求解步骤的一种描述，是指令的有限序列。
其特征包括：➢输入：算法有零个或多个输入➢输出：算法至少产生一个输出➢确定性：算法的每一条指令都有确切的定义，没有二义性。
➢能行性/可行性：可以通过已经实现的基本运算执行有限次来实现➢有穷性：算法必须总能在执行有限步之后终止6.联系：程序是计算机指令的有序集合，是算法用某种程序设计语言的表述，是算法在计算机上的具体实现。
区别：在语言描述上不同，程序必须是用规定的程序设计语言来写，而算法的描述形式包括自然语言、伪代码、流程图和程序语言等；算法所描述的步骤一定是有限的，而程序可以无限地执行下去，比如一个死循环可以称为程序，但不能称为算法。
7.正确性：算法的执行结果应当满足功能需求，无语法错误，无逻辑错误简明性：思路清晰、层次分明、易读易懂，有利于调试维护健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果效率：有效使用存储空间和有高的时间效率最优性：解决同一个问题可能有多种算法，应进行比较，选择最佳算法可使用性：用户友好性8(1)执行次数为n-1（n>=2），n=1时执行1次；时间复杂度为O(n)。
(2）执行次数为⌈log3n⌉；时间复杂度为O(logn)(3) 执行次数为n2；时间复杂度为O(n2)(4）执行次数为⌊√n⌋ + 1；时间复杂度为O(√n)第2 章线性表1．A2．D3．B4．C5．B6．D7．D8．C9．A10．D1.编写程序实现对顺序表逆置。
数据结构知识整理（部分）第一章：绪论1．数据：数据是外部信息的载体，他能够被计算机识别、存储和加工处理，是计算机程序加工的原料；2．数据元素：数据元素是数据的基本单位，在计算机中通常被作为一个整体进行考虑和处理；3．一个数据元素可由若干个数据项组成。
数据项是不可分割的、含有独立意义的最小数据单位，数据项有时也称为字段或域；4．数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。
在任何问题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关系称为结构；5．4种基本数据结构：集合：只有“同属一个集合”的关系；线性结构：存在着一对一的关系；树形结构：存在着一对多的关系；图状结构：存在着多对多的关系；6．数据结构包括数据的逻辑结构和物理结构。
逻辑结构：从具体问题抽象出来的数学模型，与数据在计算机中的具体储存没有关系。
从逻辑上可以把数据结构分为线性结构和非线性结构，其中集合、树、图形结构属于非线性结构；7．数据的物理结构又叫存储结构，是数据在计算机中的表示和存储，包括数据元素的表示和存储以及数据元素之间关系的表示和存储，存储结构必须依赖于计算机。
数据元素之间的关系在计算机中的表示有两种:顺序映像和非顺序映像。
分别对应两和数据的存储结构：顺序存储结构和链式存储结构；顺序存储结构是指把逻辑上相邻的数据元素存储在物理位置相邻的存储单元中；链式存储结构不要求必须相邻。
链式存储结构中的数据元素叫做结点，在结点中附近设地址域来存储与该结点相邻的结点的地址来实现结点之间逻辑关系；8．在软件设计中，抽象数据类型通常包括定义、表示和实现三部分9．算法：是指在有限的时间范围之内为解决某一问题而采取的方法和步骤的准确完整的描述，他是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算；10算法的特征：有穷性，确定性，可行性，输入，输出；算法+数据结构=程序；11．评价一个算法的主要标准：正确性，可读性，健壮性，运行时间，占用空间；健壮性要求算法要全面细致的考虑所有可能出现的边界情况和异常情况；实际上，算法的时间效率和空间效率经常是一对矛盾，相互抵触，我们要根据实际问题进行处理，有时要牺牲空间换取时间，有时要牺牲时间换取空间。
第4章串、数组和广义表一、填空题1、零个或多个字符组成的有限序列称为串。
二、判断题1、稀疏矩阵压缩存储后，必会失去随机存取功能。
（√）2、数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。
（╳）3、若采用三元组存储稀疏矩阵，把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。
（╳）4、若一个广义表的表头为空表，则此广义表亦为空表。
（╳）5、所谓取广义表的表尾就是返回广义表中最后一个元素。
（╳）三、单项选择题1、串是一种特殊的线性表，其特殊性体现在（B）。
A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符若2、串下面关于串的的叙述中，（B）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储解释：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的串成为空格串，零个字符的串成为空串，其长度为零。
3、串“ababaaababaa”的next数组为（C）。
A．012345678999 B．012121111212 C．011234223456 D．01230123223454、串“ababaabab”的nextval为（A）。
A．010104101B．010102101 C．010100011 D．0101010115、串的长度是指（B）。
A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数解释：串中字符的数目称为串的长度。
6、假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（B）。
A．808 B．818 C．1010 D．1020解释：以行序为主，则LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。
第一章：绪论：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计;：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称;数据元素：表示一个事物的一组数据称作是一个数据元素,是数据的基本单位;数据项：是数据元素中有独立含义的、不可分割的最小标识单位;数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作;数据的逻辑结构指数据元素之间的逻辑关系,用一个数据元素的集合定义在此集合上的若干关系来表示,数据结构可以分为三种：线性结构、树结构和图;：数据元素及其关系在计算机中的存储表示称为数据的存储结构,也称为物理结构;数据的存储结构基本形式有两种：顺序存储结构和链式存储结构;：算法：一个算法是一个有穷规则的集合,其规则确定一个解决某一特定类型问题的操作序列;算法规则需满足以下五个特性：输入——算法有零个或多个输入数据;输出——算法有一个或多个输出数据,与输入数据有某种特定关系;有穷性——算法必须在执行又穷步之后结束;确定性——算法的每个步骤必须含义明确,无二义性;可行性——算法的每步操作必须是基本的,它们的原则上都能够精确地进行,用笔和纸做有穷次就可以完成;有穷性和可行性是算法最重要的两个特征;：算法与数据结构：算法建立数据结构之上,对数据结构的操作需用算法来描述;算法设计依赖数据的逻辑结构,算法实现依赖数据结构的存储结构;：算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求,这是算法设计的基本目标;健壮性：即使输入数据不合适,算法也能做出适当的处理,不会导致不可控结高时间效率：算法的执行时间越短,时间效率越高; 果;高空间效率：算法执行时占用的存储空间越少,空间效率越高;可读性：算法的可读性有利于人们对算法的理解;：度量算法的时间效率,时间复杂度,课本39页;：递归定义：即用一个概念本身直接或间接地定义它自己;递归定义有两个条件：至少有一条初始定义是非递归的,如1=1.由已知函数值逐步递推计算出未知函数值,如用n-1定义n;第二章：线性表线性表：线性表是由nn>=0个类型相同的数据元素a0,a1,a2,…an-1,组成的有限序列,记作：Linear List = a0,a1,a2,…an-1其中,元素ai可以是整数、浮点数、字符、也可以是对象;n是线性表的元素个数,成为线性表长度;若n=0,则LinearList为空表;若n>0,则a0没有前驱元素,an-1没有后继元素,ai0<i<n-1有且仅有一个直接前驱元素ai-1和一个直接后继元素ai+1;线性表的顺序存储是用一组连续的内存单元依次存放线性表的数据元素,元素在内存的物理存储次序与它们在线性表中的逻辑次序相同;线性表的数据元素数据同一种数据类型,设每个元素占用c字节,a0的存储地址为Loca0,则ai的存储地址Locai为：Locai = Loca0+ ic数组是顺序存储的随机存储结构,它占用一组连续的存储单元,通过下标识别元素,元素地址是下标的线性函数;：顺序表的插入和删除操作要移动数据元素;平均移动次数是属数据表长度的一半;课本第50页：线性表的链式存储是用若干地址分散的存储单元存储数据元素,逻辑上相邻的数据元素在物理位置上不一定相邻,必须采用附加信息表示数据元素之间的顺序关系;它有两个域组成：数据域和地址域;通常成为节点;课本第55页及56页单链表课本56页单链表的遍历：Node<E> p = head; whilep=null{ 访问p节点；p = ;}单链表的插入和删除操作非常简便,只要改变节点间的链接关系,不需移动数据元素;单链表的插入操作：1：空表插入/头插入2中间插入/尾插入ifhead == null Node<E> q = new Node<E>x;{ head = new Node<E>x; = ;}else{ = q;Node<E> q=new Node<E>x; 中间插入或尾插入都不会改变单表= head; 的头指针head;head = q;}单链表的删除操作：头删除：head = ;中间/尾删除：if=null{ =循环单链表：如果单链表最后一个节点的next链保存单链表的头指针head值,则该单链表成为环形结构,称为循环单链表;课本67若rear是单链表的尾指针,则执行=head;语句,使单链表成为一条循环单链表;当==head时,循环单链表为空;：双链表结构：双链表的每个结点有两个链域,分别指向它的前驱和后继结点,当==null时,双链表为空;设p指向双链表中非两端的某个结点,则成立下列关系：p=;双链表的插入和删除：1插入2删除q=new DLinkNodex；= ;=; =p; if=null{= q;=q; .prev = ;}循环双链表：当==head且==head时,循环双链表为空;第三章：栈和队列栈：栈是一种特殊的线性表,其中插入和删除操作只允许在线性表的一端进行;允许操作的一端称为栈顶,不允许操作的一端称为栈底;栈有顺序栈和链式栈;栈中插入元素的操作称为入栈,删除元素的操作称为出栈;没有元素的中称为空栈;栈的进出栈顺序：后进先出,先进后出;及75页的思考题;：队列：队列是一种特殊的线性表,其中插入和删除操作分别在线性表的两端进行;向队列中插入元素的过程称为入队,删除元素的过程称为出对,允许入队的一端称为队尾,允许出队的一端称为对头;没有元素的队列称为空队列;队列是先进先出;第四章：串：串是一种特殊的线性表,其特殊性在于线性表中的每个元素是一个字符;一个串记为：s=“s0s1s2…sn-1” 其中n>=0,s是串名,一对双引号括起来的字符序列s0s1s2…sn-1是串值,sii=0,1,2,…n-1为特定字符集合中的一个字符;一个串中包含的字符个数称为串的长度;长度为0的串称为空串,记作“”,而由一个或多个空格字符构成的字符串称为空格串;子串：由串s中任意连续字符组成的一个子序列sub称为s的子串,s称为sub 的主串;子串的序号是指该子串的第一个字符在主串中的序号;串比较：两个串可比较是否相等,也可比较大小;两个串子串相等的充要条件是两个串子串的长度相同,并且各对应位置上的字符也相同;两个串的大小由对应位置的第一个不同字符的大小决定,字符比较次序是从头开始依次向后;当两个串长度不等而对应位置的字符都相同时,较长的串定义为较“大”;第五章：数组和广义表：数组是一种数据结构,数据元素具有相同的数据类型;一维数组的逻辑结构是线性表,多维数组是线性表的扩展;：一维数组：一维数组采用顺序存储结构;一个一维数组占用一组连续的存储单元;设数组第一个元素a0的存储地址为Loca0,每个元素占用c字节,则数组其他元素ai的存储地址Locai为：Locai= Loca0+ic数组通过下标识别元素,元素地址是下标的线性函数;一个下标能够唯一确定一个元素,所划给的时间是O1;因此数组是随机存取结构,这是数组最大的优点;：多维数组的遍历：有两种次序：行主序和列主序;行主序：以行为主序,按行递增访问数组元素,访问完第i行的所有元素之后再访问第i+1行的元素,同一行上按列递增访问数组元素;a00,a01,…a0n-1, a10,a11,…a1n-1,…am-10,am-11,…,am-1n-12列主序：以列为主序,按列递增访问数组元素,访问完第j列的所有元素之后再访问第j+1列的元素,同一列上按列递增访问数组元素;多维数组的存储结构：多维数组也是由多个一维数组组合而成,组合方式有一下两种;静态多维数组的顺序存储结构：可按行主序和列主序进行顺序存储;按行主序存储时,元素aij的地址为：Locaij= Loca00+in+jc按列主序存储时,Locaij= Loca00+jm+ic动态多维数组的存储结构;二维数组元素地址就是两个下标的线性函数;无论采用哪种存储结构,多维数组都是基于一维数组的,因此也只能进行赋值、取值两种存取操作,不能进行插入,删除操作;第六章：树是数据元素结点之间具有层次关系的非线性结构;在树结构中,除根以外的结点只有一个直接前驱结点,可以有零至多个直接后继结点;根没有前驱结点;树是由nn>=0个结点组成的有限集合树中元素通常称为结点;N=0的树称为空树；n>0大的树T；有一个特殊的结点称为根结点,它只有后继结点,没有前驱结点;除根结点之外的其他结点分为mm>=0个互不相交的集合T0,T1,T3……..,Tm-1,其中每个集合Ti0<=i<m本身又是一棵树,称为根的子树;树是递归定义的;结点是树大的基本单位,若干个结点组成一棵子树,若干棵互不相交的子树组成一棵树;树的每个结点都是该树中某一棵子树的根;因此,树是由结点组成的、结点之间具有层次关系大的非线性结构;结点的前驱结点称为其父母结点,反之,结点大的后继结点称为其孩子结点;一棵树中,只有根结点没有父母结点,其他结点有且仅有一个父母结点;拥有同一个父母结点的多个结点之间称为兄弟结点;结点的祖先是指从根结点到其父母结点所经过大的所有结点;结点的后代是指该结点的所有孩子结点,以及孩子的孩子等;结点的度是结点所拥有子树的棵数;度为0的结点称为叶子结点,又叫终端结点；树中除叶子结点之外的其他结点称为分支结点,又叫非叶子结点或非终端结点;树的度是指树中各结点度的最大值;结点的层次属性反应结点处于树中的层次位置;约定根结点的层次为1,其他结点的层次是其父母结点的层次加1;显然,兄弟结点的层次相同;树的高度或深度是树中结点的最大层次树;设树中x结点是y结点的父母结点,有序对x,y称为连接这两个结点的分支,也称为边;设X0,X1,….,Xk-1是由树中结点组成的一个序列,且Xi,Xi+10<=i<k-1都是树中的边,则该序列称为从X0到Xk-1的一条路径;路径长度为路径上的边数;在树的定义中,结点的子树T0,T1…..,Tm-1之间没有次序,可以交换位置,称为无序树,简称树;如果结点的子树T0,T1……,Tm-1从左到右是有次序的,不能交换位置,则称该树为有序树;森林是mm>=0棵互不相干的树的集合;给森林加上一个根结点就变成一棵树,将树的根节点删除就变成森林;二叉树的性质1：若根结点的层次为1,则二叉树第i层最多有2 的i-1次方i>=1个结点;二叉树的性质2：在高度为k的二叉树中,最多有2的k次方减一个结点;二叉树的性质3：设一棵二叉树的叶子结点数为n0,2度结点数为n2,则n0=n2+1;一棵高度为k的满二叉树是具有2的k次方减一个结点的二叉树;满二叉树中每一层的结点数目都达到最大值;对满二叉树的结点进行连续编号,约定根节点的序号为0,从根节点开始,自上而下,每层自左至右编号;一棵具有n个结点高度为k的二叉树,如果他的每个节点都与高度为k的满二叉树中序号为0~n-1的结点一一对应,则这棵二叉树为为完全二叉树;满二叉树是完全二叉树,而完全二叉树不一定是满二叉树;完全二叉树的第1~k-1层是满二叉树第k层不满,并且该层所有结点必须集中在该层左边的若干位置上;二叉树的性质4：一棵具有n个结点的完全二叉树,其高度k=log2n的绝对值+1二叉树的性质5：一棵具有n个结点的完全二叉树,对序号为i的结点,有若i=0,则i为根节点,无父母结点；若i>0,则i的父母结点的序号为i-1/2;若2i+1<n,则i的左孩子结点序号为2i+1；否则i无左孩子;若2i+2<n,则i的右孩子结点的序号为2i+2,否则i无右孩子;二叉树的遍历二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点,并且每个结点仅被访问一次;二叉树的三种次序遍历1：先根次序；访问根节点,遍历左子树,遍历右子树;2：中根次序；遍历左子树,访问右子树,遍历右子树;3：后根次序；遍历左子树,遍历右子树,访问根节点;先根次序遍历时,最先访问根节点；后根次序遍历时,最后访问根节点；中根次序遍历时,左子树上的结点在根节点之前访问,右子树上的结点在根节点之后访问;二叉树的插入和删除操作P147二叉树的层次遍历P149习题P167 6—10,6—19第七章图是由定点集合及顶点间的关系集合组成的一种数据关边系;顶点之间的关系成为边;一个图G记为G=V,E,V是顶点A的有限集合,E是边的有限集合;即V={A|A属于某个数据元素集合}E={A,B|A,B属于V}或E={<A,B>|A,B属于V且PathA,B}其中PathA,B表示从顶点A到B的一条单向通路,即PathA,B是有方向的;无向图中的边事没有方向,每条边用两个顶点的无序对表示;有向图中的边是有方向,每条边用两个顶点的有序对表示;完全图指图的边数达到最大值;n个顶点的完全图记为Kn;无向完全图Kn的边数为nn-1/2,有向完全图Kn的边数为nn-1;子图：设图G==V,E,G’=V’,E’,若V’包含于V且E’包含于E,则称图G’是G的子图;若G’是G的真子图;连通图：在无向图G中,若从顶点VI到Vj有路径,则称Vi和Vj是联通的;若图G 中任意一对顶点Vi和VjVi不等于Vj都是联通的,则称G为连通图;非连通图的极大联通子图称为该图的联通分量;强连通图：在有向图中,若在每一对顶点Vi和VjVi不等于Vj之间都存在一条从Vi到Vj的路径,也存在一条从Vi到Vj的路径,也存在一条从Vi到Vj的路径,则称该图的强连通图;非强连通图的极大强连通子图称为该图的强连通图分量;图的遍历遍历图是指从图G中任意一个顶点V出发,沿着图中的边前行,到达并访问图中的所有顶点,且每个顶点仅被访问一次;遍历图要考虑一下三个问题：指定遍历的第一个访问顶点由于一个顶点可能与多个顶点相邻,因此要在多个邻接顶点之间约定一种访问次序;由于图中可能存在回路,在访问某个顶点之后,可能沿着某条路径又回到该顶点;深度优先搜索图的深度优先搜索策略是,访问某个顶点v,接着寻找v的另一个未被访问的邻接顶点w访问,如此反复执行,走过一条较长路径到达最远顶点；若顶点v没有未被访问的其他邻接顶点,则回到前一个被访问顶点,再寻找其他访问路径;图的深度优先搜索遍历算法P188联通的无回路的无向图,简称树;树中的悬挂点又成为树叶,其他顶点称为分支点;各连通分量均为树的图称为森林,树是森林;由于树中无回路,因此树中必定无自身环也无重边否则他有回路若去掉树中的任意一条边,则变成森林,成为非联通图；若给树加上一条边,形成图中的一条回路,则不是树;P191生成树和生成森林：一个连通无向图的生成树是该图的一个极小联通生成子图,它包含原图中所有顶点n个以及足以构成一棵树的n-1条边;一个非联通的无向图,其各连通图分量的生成图组成该图的生成森林;图的生成图或生成森林不是唯一的,从不同顶点开始、采用不同遍历可以得到不同的生成树或森林;在生成树中,任何树中,任何两个顶点之间只有唯一的一条路径;第八章折半查找算法描述P206,P207二叉排序树及其查找：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：每个结点都有一个作为查找依据的关键字,所有结点的关键字互不相同;若一个结点的左子树不空,则左子树上所有结点的关键字均小于这个节点的关键字；每个结点的左右子树也分别为二叉排序树;在一棵二叉排序树中,查找值为value的结点,算法描述如下：从根结点开始,设p指向根结点将value与p结点的关键字进行比较,若两者相等,则查找成功；若value值较小,则在p的左子树中继续查找；若value值较大,则在p的右子树中继续查找;重复执行上一步,直到查找成功或p为空,若p为空,则查找不成功;习题8-6第九章直接插入排序算法描述：p228冒泡排序算法的描述：p232快速排序算法描述p233直接选择排序算法描述p236直接选择排序算法实现如下：Public static void selectSortinttable{forint i=0;i<;i++{int min=I;forint j=i+1;j<;j++{iftablej<tableminmin=j;ifmin=i{int temp=tablei;tablei==tablemin;tablemin=temp;}}}}堆排序是完全二叉树的应用,是充分利用完全二叉树特性的一种选择排序;堆定义：设n个元素的数据序列{k0,k1,;;;;kn-1},当且仅当满足下列关系k1<=k2i+1且ki<=k2i+2 i=0,1,2,3,….,n/2-1或ki>==k2i+1且ki>=2i+2i=0,1,2,3,…..n/2-1时,序列{k0,k1…….kn-1}称为最小堆或最大堆;将最小大堆看成是一颗完全二叉树的层次遍历序列,则任意一个结点的关键字都小于等于大于等于它的孩子节点的关键字值,由此可知,根结点值最小大;根据二叉树的性质5,完全二叉树中的第i0<=i<n个结点,如果有孩子,则左孩子为第2i+1个结点,右孩子为第2i+2个结点;。
数据结构05数组与广义表数组与广义表可以看做是线性表地扩展,即数组与广义表地数据元素本身也是一种数据结构。
5.1 数组地基本概念5.2 数组地存储结构5.3 矩阵地压缩存储5.4 广义表地基本概念数组是由相同类型地一组数据元素组成地一个有限序列。
其数据元素通常也称为数组元素。
数组地每个数据元素都有一个序号,称为下标。
可以通过数组下标访问数据元素。
数据元素受n(n≥1)个线性关系地约束,每个数据元素在n个线性关系地序号 i1,i2,…,in称为该数据元素地下标,并称该数组为n维数组。
如下图是一个m行,n列地二维数组A矩阵任何一个元素都有两个下标,一个为行号,另一个为列号。
如aij表示第i行j列地数据元素。
数组也是一种线性数据结构,它可以看成是线性表地一种扩充。
一维数组可以看作是一个线性表,二维数组可以看作数据元素是一维数组（或线性表）地线性表,其一行或一列就是一个一维数组地数据元素。
如上例地二维数组既可表示成一个行向量地线性表: A1=(a11,a12,···,a1n)A2=(a21,a22, ···,a2n)A=(A1,A2, ···,Am) ············Am=(am1,am2, ···,amn)也可表示成一个列向量地线性表:B1=(a11,a21,···,am1)B2=(a12,a22, ···,am2)A=(B1,B2, ···,Bm) ············Bn=(a1n,a2n, ···,amn)数组地每个数据元素都与一组唯一地下标值对应。
第一章绪论一、选择题3。
在数据结构中，从逻辑上可以把数据结构分成（）(A)动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构5.算法分析的目的是（）。
（A) 找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性二、判断题1.数据的机内表示称为数据的存储结构。
（）2。
算法就是程序。
（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态.( ）三、填空题1.数据逻辑结构包括________、________、_________ 和_________四种类型，其中树形结构和图形结构合称为_____.2.在线性结构中，第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点，其余每个结点有且只有_______个后续结点。
3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点，其余每个结点的后续结点可以_________.4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。
5.线性结构中元素之间存在________关系，树形结构中元素之间存在______关系，图形结构中元素之间存在_______关系。
8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。
9。
设有一批数据元素，为了最快的存储某元素，数据结构宜用_________结构，为了方便插入一个元素,数据结构宜用____________结构。
四、算法分析题，求下列算法段的语句频度及时间复杂度for （i=1；i<=n;i++）for (j=1;j〈=i；j++)for （k=1;k<=j；k++)x=i+j—k；第二章线性表一、选择题1。
