数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系

需要达到＜识记＞层次的基本概念和术语有：数据、数据元素、数据项、数据结构。

特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。

数据结构的两大类逻辑结构和四种常用的存储表示方法。

需要达到＜领会＞层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。

对于基本概念，仔细看书就能够理解，这里简单提一下：数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

如整数这个集合中，10这个数就可称是一个数据元素．又比如在一个数据库（关系式数据库）中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。

数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。

这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。

比如一个表（数据库），我们就称它为一个数据结构，它由很多记录（数据元素）组成，每个元素又包括很多字段（数据项）组成。

那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点（其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东）之间的关系来分析的，对于这个表中的任一个记录（结点），它只有一个直接前趋，只有一个直接后继（前趋后继就是前相邻后相邻的意思），整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。

而存储结构则是指用计算机语言如何表示结点之间的这种关系。

如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。

（注意，在本课程里，我们只在高级语言的层次上讨论存储结构。

）第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。

数据结构中的名词解释数据结构中的名词解释数据结构：数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。

在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。

结点：结点也叫数据元素，它是组成数据的基本单位。

逻辑结构：结点和结点之间的逻辑关系称为数据的逻辑结构。

存储结构：数据在计算机中的存储表示称为数据的存储结构。

数据处理：数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。

数据类型：数据类型是指程序设计语言中各变量可取的数据种类。

数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。

本章主要介绍了如下一些基本概念：线性表：一个线性表是n≥0个数据元素a0，a1，a2，…，an-1的有限序列。

线性表的顺序存储结构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。

线性表的链式存储结构：线性表的链式存储结构就是用一组任意的存储单元——结点（可以是不连续的`）存储线性表的数据元素。

表中每一个数据元素，都由存放数据元素值的数据域和存放直接前驱或直接后继结点的地址（指针）的指针域组成。

循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结点。

数据结构基础知识整理*名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。

*2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。

一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。

*3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。

*4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

*5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。

是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。

*6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且其余每个结点只有一个直接前趋和一个直接后继。

*7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。

*8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。

*9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。

*10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。

而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。

*11、数据的运算：指对数据施加的操作。

数据的运算是定义在数据的逻辑结构上的，而实现是要在存储结构上进行。

*12、线性表：由n(n≥0)个结点组成的有限序列。

其逻辑特征反映了结点间一对一的关系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。

*13、顺序表：顺序存储的线性表，它是一种随机存取结构。

第一章概论1.数据：信息的载体,能被计算机识别、存储和加工处理;2.数据元素：数据的基本单位,可由若干个数据项组成,数据项是具有独立含义的最小标识单位;3.数据结构：数据之间的相互关系,即数据的组织形式;它包括：1数据的逻辑结构,从逻辑关系上描述数据,与数据存储无关,独立于计算机；2数据的存储结构,是逻辑结构用计算机语言的实现,依赖于计算机语言;3数据的运算,定义在逻辑结构上,每种逻辑结构都有一个运算集合;常用的运算：检索/插入/删除/更新/排序;4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型;数据的存储结构是逻辑结构用计算机语言的实现;5.数据类型：一个值的集合及在值上定义的一组操作的总称;分为：原子类型和结构类型;6.抽象数据类型：抽象数据的组织和与之相关的操作;优点：将数据和操作封装在一起实现了信息隐藏;7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象类的实例解决问题;8.数据的逻辑结构,简称为数据结构,有：1线性结构,若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继;2非线性结构,一个结点可能有多个直接前趋和后继;9.数据的存储结构有：1顺序存储,把逻辑相邻的结点存储在物理上相邻的存储单元内;2链接存储,结点间的逻辑关系由附加指针字段表示;3索引存储,存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引;4散列存储,按结点的关键字直接计算出存储地址;10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间辅助存储空间；易于理解、编码、调试;11.算法的时间复杂度Tn：是该算法的时间耗费,是求解问题规模n的函数;记为On;时间复杂度按数量级递增排列依次为：常数阶O1、对数阶Olog2n、线性阶On、线性对数阶Onlog2n、平方阶On^2、立方阶On^3、……k次方阶On^k、指数阶O2^n;13.算法的空间复杂度Sn：是该算法的空间耗费,是求解问题规模n的函数;12.算法衡量：是用时间复杂度和空间复杂度来衡量的,它们合称算法的复杂度;13. 算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关;第二章线性表1.线性表：是由nn≥0个数据元素组成的有限序列;3.顺序表：把线性表的结点按逻辑次序存放在一组地址连续的存储单元里;4.顺序表结点的存储地址计算公式：Locai=Loca1+i-1C；1≤i≤n5.顺序表上的基本运算public interface List {链表：只有一个链域的链表称单链表;在结点中存储结点值和结点的后继结点的地址,data next data是数据域,next是指针域;1建立单链表;时间复杂度为On;加头结点的优点：1链表第一个位置的操作无需特殊处理；2将空表和非空表的处理统一; 2查找运算;时间复杂度为On;public class SLNode implements Node {private Object element;private SLNode next;public SLNodeObject ele, SLNode next{= ele;= next;}public SLNode getNext{return next;}public void setNextSLNode next{= next;}public Object getData {return element;}public void setDataObject obj {element = obj;}}public class ListSLinked implements List {private SLNode head; etData==ereturn p;else p = ;return null;}etData;.getNext;size--;return obj;}etNext;size--;return true;}return false;}环链表：是一种首尾相连的链表;特点是无需增加存储量,仅对表的链接方式修改使表的处理灵活方便;8.空循环链表仅由一个自成循环的头结点表示;9.很多时候表的操作是在表的首尾位置上进行,此时头指针表示的单循环链表就显的不够方便,改用尾指针rear来表示单循环链表;用头指针表示的单循环链表查找开始结点的时间是O1,查找尾结点的时间是On；用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O1;10.在结点中增加一个指针域,prior|data|next;形成的链表中有两条不同方向的链称为双链表;public class DLNode implements Node {private Object element;private DLNode pre;private DLNode next;public DLNodeObject ele, DLNode pre, DLNode next{= ele;= pre;= next;}public DLNode getNext{return next;}public void setNextDLNode next{= next;}public DLNode getPre{return pre;}public void setPreDLNode pre{= pre;}public Object getData {return element;}public void setDataObject obj {element = obj;}}public class LinkedListDLNode implements LinkedList {private int size; etPrenode;node;size++;return node;}etNextnode;node;size++;return node;}etNext;.setPre;size--;return obj;}序表和链表的比较1基于空间的考虑：顺序表的存储空间是静态分配的,链表的存储空间是动态分配的;顺序表的存储密度比链表大;因此,在线性表长度变化不大,易于事先确定时,宜采用顺序表作为存储结构;2基于时间的考虑：顺序表是随机存取结构,若线性表的操作主要是查找,很少有插入、删除操作时,宜用顺序表结构;对频繁进行插入、删除操作的线性表宜采用链表;若操作主要发生在表的首尾时采用尾指针表示的单循环链表;12.存储密度=结点数据本身所占的存储量/整个结点结构所占的存储总量存储密度：顺序表=1,链表<1;第三章栈和队列1.栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表LIFO表;插入、删除端称为栈顶,另一端称栈底;表中无元素称空栈;2.栈的基本运算有：1initstacks,构造一个空栈；2stackemptys,判栈空；3stackfulls,判栈满；4pushs,x,进栈；5pops,退栈；6stacktops,取栈顶元素;3.顺序栈：栈的顺序存储结构称顺序栈;4.当栈满时,做进栈运算必定产生空间溢出,称“上溢”;当栈空时,做退栈运算必定产生空间溢出,称“下溢”;上溢是一种错误应设法避免,下溢常用作程序控制转移的条件;5.在顺序栈上的基本运算：public interface Stack {栈：栈的链式存储结构称链栈;栈顶指针是链表的头指针;7.链栈上的基本运算：public class StackSLinked implements Stack {private SLNode top; 列是一种运算受限的线性表,允许删除的一端称队首,允许插入的一端称队尾;队列又称为先进先出线性表,FIFO表;9.队列的基本运算：1initqueueq,置空队；2queueemptyq,判队空；3queuefullq,判队满；4enqueueq,x,入队；5dequeueq,出队；6queuefrontq,返回队头元素;10.顺序队列：队列的顺序存储结构称顺序队列;设置front和rear指针表示队头和队尾元素在向量空间的位置;11.顺序队列中存在“假上溢”现象,由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用,队尾指针超过向量空间的上界而不能入队;12.为克服“假上溢”现象,将向量空间想象为首尾相连的循环向量,存储在其中的队列称循环队列;i=i+1%queuesize13.循环队列的边界条件处理：由于无法用front==rear来判断队列的“空”和“满”;解决的方法有：1另设一个布尔变量以区别队列的空和满；2少用一个元素,在入队前测试rear在循环意义下加1是否等于front；3使用一个记数器记录元素总数;14.循环队列的基本运算：public interface Queue {队列：队列的链式存储结构称链队列,链队列由一个头指针和一个尾指针唯一确定;16.链队列的基本运算：public class QueueSLinked implements Queue {private SLNode front;private SLNode rear;private int size;public QueueSLinked {front = new SLNode;rear = front;size = 0;}etData;}}第四章串1.串：是由零个或多个字符组成的有限序列；包含字符的个数称串的长度；2.空串：长度为零的串称空串；空白串：由一个或多个空格组成的串称空白串；子串：串中任意个连续字符组成的子序列称该串的子串；主串：包含子串的串称主串；子串的首字符在主串中首次出现的位置定义为子串在主串中的位置；3.空串是任意串的子串；任意串是自身的子串；串常量在程序中只能引用但不能改变其值；串变量取值可以改变；4.串的基本运算1intstrlenchars;求串长;2charstrcpycharto,charfrom;串复制;3charstrcatcharto,charfrom;串联接;4intstrcmpchars1,chars2;串比较;5charstrchrchars,charc;字符定位;5.串的存储结构：1串的顺序存储：串的顺序存储结构称顺序串;按存储分配不同分为：1静态存储分配的顺序串：直接用定长的字符数组定义,以“\0”表示串值终结;definemaxstrsize256typedefcharseqstringmaxstrsize;seqstrings;不设终结符,用串长表示;Typedefstruct{Charchmaxstrsize;Intlength;}seqstring;以上方式的缺点是：串值空间大小是静态的,难以适应插入、链接等操作;2动态存储分配的顺序串：简单定义：typedefcharstring;复杂定义：typedefstruct{charch;intlength;}hstring;2串的链式存储：串的链式存储结构称链串;链串由头指针唯一确定;类型定义：typedefstructnode{chardata;structnodenext;}linkstrnode;typedeflinkstrnodelinkstring;linkstrings;将结点数据域存放的字符个数定义为结点的大小;结点大小不为1的链串类型定义：definenodesize80typedefstructnode{chardatanodesize;structnodenext;}linkstrnode;6.串运算的实现1顺序串上的子串定位运算;1子串定位运算又称串的模式匹配或串匹配;主串称目标串；子串称模式串; 2朴素的串匹配算法;时间复杂度为On^2;比较的字符总次数为n-m+1m; Intnaivestrmatchseqstringt,seqstringp{inti,j,k;intm=;intn=;fori=0;i<=n-m;i++{j=0;k=i;whilej<m&&k==j{j++;k++;}ifj==mreturni;}return–1;}2链串上的子串定位运算;时间复杂度为On^2;比较的字符总次数为n-m+1m;LinkstrnodelilnkstrmatchlinkstringT,linkstringP {linkstrnodeshift,t,p;shift=T;t=shift;p=P;whilet&&p{ift->data==p->data{t=t->next;p=p->next;}else{shift=shift->next;t=shift;p=P;}}ifp==NULLreturnshift;elsereturnNULL;}第五章多维数组和广义表1.多维数组：一般用顺序存储的方式表示数组;2.常用方式有：1行优先顺序,将数组元素按行向量排列；2列优先顺序,将数组元素按列向量排列;3.计算地址的函数：LOCAij=LOCAc1c2+i-c1d2-c2+1+j-c2d4.矩阵的压缩存储：为多个非零元素分配一个存储空间；对零元素不分配存储空间;1对称矩阵：在一个n阶的方阵A中,元素满足Aij=Aji0<=i,j<=n-1;称为对称矩阵;元素的总数为：nn+1/2;设：I=i或j中大的一个数；J=i或j中小的一个数；则：k=II+1/2+J;地址计算：LOCAij=LOCsak=LOCsa0+kd=LOCsa0+II+1/2+Jd2三角矩阵：以主对角线划分,三角矩阵有上三角和下三角；上三角的主对角线下元素均为常数c；下三角的主对角线上元素均为常数c;元素总数为：nn+1/2+1;以行优先顺序存放的Aij与SAk的关系：上三角阵：k=i2n-i+1/2+j-i;下三角阵：k=ii+1/2+j;3对角矩阵：所有的非零元素集中在以主对角线为中心的带状区域,相邻两侧元素均为零;|i-j|>k-1/2以行优先顺序存放的Aij与SAk的关系：k=2i+j;5.稀疏矩阵：当矩阵A中有非零元素S个,且S远小于元素总数时,称为稀疏矩阵;对其压缩的方法有顺序存储和链式存储;1三元组表：将表示稀疏矩阵的非零元素的三元组行号、列号、值按行或列优先的顺序排列得到的一个结点均是三元组的线性表,将该表的线性存储结构称为三元组表;其类型定义：definemaxsize10000typedefintdatatype;typedefstruct{inti,j;datatypev;}trituplenode;typedefstruct{trituplenodedatamaxsize;intm,n,t;}tritupletable;2带行表的三元组表：在按行优先存储的三元组表中加入一个行表记录每行的非零元素在三元组表中的起始位置;类型定义：definemaxrow100typedefstruct{tritulpenodedatamaxsize;introwtabmaxrow;intm,n,t;}rtritulpetable;6.广义表：是线性表的推广,广义表是n个元素的有限序列,元素可以是原子或一个广义表,记为LS;7.若元素是广义表称它为LS的子表;若广义表非空,则第一个元素称表头,其余元素称表尾;8.表的深度是指表展开后所含括号的层数;9.把与树对应的广义表称为纯表,它限制了表中成分的共享和递归；10.允许结点共享的表称为再入表；11.允许递归的表称为递归表；12.相互关系：线性表∈纯表∈再入表∈递归表；13.广义表的特殊运算：1取表头headLS；2取表尾tailLS;第六章树1.树：是n个结点的有限集T,T为空时称空树,否则满足：1有且仅有一个特定的称为根的结点；2其余结点可分为m个互不相交的子集,每个子集本身是一棵树,并称为根的子树;2.树的表示方法：1树形表示法；2嵌套集合表示法；3凹入表表示法；4广义表表示法；3.一个结点拥有的子树数称为该结点的度；一棵树的度是指树中结点最大的度数;4.度为零的结点称叶子或终端结点；度不为零的结点称分支结点或非终端结点5.根结点称开始结点,根结点外的分支结点称内部结点；6.树中某结点的子树根称该结点的孩子；该结点称为孩子的双亲；7.树中存在一个结点序列K1,K2,…Kn,使Ki为Ki+1的双亲,则称该结点序列为K1到Kn的路径或道路；8.树中结点K到Ks间存在一条路径,则称K是Ks的祖先,Ks是K的子孙；9.结点的层数从根算起,若根的层数为1,则其余结点层数是其双亲结点层数加1；双亲在同一层的结点互为堂兄弟；树中结点最大层数称为树的高度或深度；10.树中每个结点的各个子树从左到右有次序的称有序树,否则称无序树；11.森林是m棵互不相交的树的集合;12.二叉树：是n个结点的有限集,它或为空集,或由一个根结点及两棵互不相交的、分别称为该根的左子树和右子树的二叉树组成;13.二叉树不是树的特殊情况,这是两种不同的数据结构；它与无序树和度为2的有序树不同;14.二叉树的性质：1二叉树第i层上的结点数最多为2^i-1；2深度为k的二叉树至多有2^k-1个结点；3在任意二叉树中,叶子数为n0,度为2的结点数为n2,则n0=n2+1；15.满二叉树是一棵深度为k的且有2^k-1个结点的二叉树；16.完全二叉树是至多在最下两层上结点的度数可以小于2,并且最下层的结点集中在该层最左的位置的二叉树；17.具有N个结点的完全二叉树的深度为log2N取整加1；18.二叉树的存储结构1顺序存储结构：把一棵有n个结点的完全二叉树,从树根起自上而下、从左到右对所有结点编号,然后依次存储在一个向量b0~n中,b1~n存放结点,b0存放结点总数;各个结点编号间的关系：1i=1是根结点；i>1则双亲结点是i/2取整；2左孩子是2i,右孩子是2i+1；要小于n3i>n/2取整的结点是叶子；4奇数没有右兄弟,左兄弟是i-1；5偶数没有左兄弟,右兄弟是i+1；2链式存储结构结点的结构为：lchild|data|rchild；相应的类型说明：typedefchardata;typedefstructnode{datatypedata;structnodelchild,rchild;}bintnode;typedefbintnodebintree;19.在二叉树中所有类型为bintnode的结点和一个指向开始结点的bintree类型的头指针构成二叉树的链式存储结构称二叉链表;20.二叉链表由根指针唯一确定;在n个结点的二叉链表中有2n个指针域,其中n+1个为空;21.二叉树的遍历方式有：前序遍历、中序遍历、后序遍历;时间复杂度为On;22.线索二叉树：利用二叉链表中的n+1个空指针域存放指向某种遍历次序下的前趋和后继结点的指针,这种指针称线索;加线索的二叉链表称线索链表;相应二叉树称线索二叉树;23.线索链表结点结构：lchild|ltag|data|rtag|rchild；ltag=0,lchild是指向左孩子的指针；ltag=1,lchild是指向前趋的线索；rtag=0,rchild是指向右孩子的指针；rtag=1,rchild是指向后继的线索；24.查找p在指定次序下的前趋和后继结点;算法的时间复杂度为Oh;线索对查找前序前趋和后序后继帮助不大;25.遍历线索二叉树;时间复杂度为On;26.树、森林与二叉树的转换1树、森林与二叉树的转换1树与二叉树的转换：1}所有兄弟间连线；2}保留与长子的连线,去除其它连线;该二叉树的根结点的右子树必为空;2森林与二叉树的转换：1}将所有树转换成二叉树；2}将所有树根连线;2二叉树与树、森林的转换;是以上的逆过程;27.树的存储结构1双亲链表表示法：为每个结点设置一个parent指针,就可唯一表示任何一棵树;Data|parent2孩子链表表示法：为每个结点设置一个firstchild指针,指向孩子链表头指针,链表中存放孩子结点序号;Data|firstchild;3双亲孩子链表表示法：将以上方法结合;Data|parent|firstchild4孩子兄弟链表表示法：附加两个指向左孩子和右兄弟的指针;Leftmostchild|data|rightsibling28.树和森林的遍历：前序遍历一棵树等价于前序遍历对应二叉树；后序遍历等价于中序遍历对应二叉树;29.最优二叉树哈夫曼树：树的路径长度是从树根到每一结点的路径长度之和;将树中的结点赋予实数称为结点的权;30.结点的带权路径是该结点的路径长度与权的乘积;树的带权路径长度又称树的代价,是所有叶子的带权路径长度之和;31.带权路径长度最小的二叉树称最优二叉树哈夫曼树;32.具有2n-1个结点其中有n个叶子,并且没有度为1的分支结点的树称为严格二叉树;33.哈夫曼编码34.对字符集编码时,要求字符集中任一字符的编码都不是其它字符的编码前缀,这种编码称前缀码;35.字符出现频度与码长乘积之和称文件总长；字符出现概率与码长乘积之和称平均码长；36.使文件总长或平均码长最小的前缀码称最优前缀码37.利用哈夫曼树求最优前缀码,左为0,右为1;编码平均码长最小；没有叶子是其它叶子的祖先,不可能出现重复前缀;第七章图1.图：图G是由顶点集V和边集E组成,顶点集是有穷非空集,边集是有穷集；中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；G中每条边都没有方向的称无向图;3.顶点n与边数e的关系：无向图的边数e介于0~nn-1/2之间,有nn-1/2条边的称无向完全图；有向图的边数e介于0~nn-1之间,有nn-1条边的称有向完全图；4.无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和;所有图均满足：所有顶点的度数和的一半为边数;5.图GV,E,如V’是V的子集,E’是E的子集,且E’中关联的顶点均在V’中,则G’V’,E’是G的子图;6.在有向图中,从顶点出发都有路径到达其它顶点的图称有根图；7.在无向图中,任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；8.在有向图中,任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；9.将图中每条边赋上权,则称带权图为网络;10.图的存储结构：1邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵;n个顶点就是n阶方阵;无向图是对称矩阵；有向图行是出度,列是入度;2邻接表表示法：对图中所有顶点,把与该顶点相邻接的顶点组成一个单链表,称为邻接表,adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点,vertex|firstedge,并顺序存储在一个向量中；vertex保存顶点信息,firstedge保存邻接表头指针;11.邻接矩阵表示法与邻接表表示法的比较：1邻接矩阵是唯一的,邻接表不唯一；2存储稀疏图用邻接表,存储稠密图用邻接矩阵；3求无向图顶点的度都容易,求有向图顶点的度邻接矩阵较方便；4判断是否是图中的边,邻接矩阵容易,邻接表最坏时间为On；5求边数e,邻接矩阵耗时为On^2,与e无关,邻接表的耗时为Oe+n；12.图的遍历：1图的深度优先遍历：类似与树的前序遍历;按访问顶点次序得到的序列称DFS序列;对邻接表表示的图深度遍历称DFS,时间复杂度为On+e;对邻接矩阵表示的图深度遍历称DFSM,时间复杂度为On^2;2图的广度优先遍历：类似与树的层次遍历;按访问顶点次序得到的序列称BFS序列;对邻接表表示的图广度遍历称BFS,时间复杂度为On+e;对邻接矩阵表示的图广度遍历称BFSM,时间复杂度为On^2;13.将没有回路的连通图定义为树称自由树;14.生成树：连通图G的一个子图若是一棵包含G中所有顶点的树,该子图称生成树;有DFS生成树和BFS生成树,BFS生成树的高度最小;非连通图生成的是森林;15.最小生成树：将权最小的生成树称最小生成树;是无向图的算法1普里姆算法：1确定顶点S、初始化候选边集T0~n-2；formvex|tovex|lenght2选权值最小的Ti与第1条记录交换；3从T1中将tovex取出替换以下记录的fromvex计算权；若权小则替换,否则不变；4选权值最小的Ti与第2条记录交换；5从T2中将tovex取出替换以下记录的fromvex计算权；若权小则替换,否则不变；6重复n-1次;初始化时间是On,选轻边的循环执行n-1-k次,调整轻边的循环执行n-2-k；算法的时间复杂度为On^2,适合于稠密图;2克鲁斯卡尔算法：1初始化确定顶点集和空边集；对原边集按权值递增顺序排序；2取第1条边,判断边的2个顶点是不同的树,加入空边集,否则删除；3重复e次;对边的排序时间是Oelog2e；初始化时间为On；执行时间是Olog2e；算法的时间复杂度为Oelog2e,适合于稀疏图;16.路径的开始顶点称源点,路径的最后一个顶点称终点；17.单源最短路径问题：已知有向带权图,求从某个源点出发到其余各个顶点的最短路径；18.单目标最短路径问题：将图中每条边反向,转换为单源最短路径问题；19.单顶点对间最短路径问题：以分别对不同顶点转换为单源最短路径问题；20.所有顶点对间最短路径问题：分别对图中不同顶点对转换为单源最短路径问题；21.迪杰斯特拉算法：1初始化顶点集Si,路径权集Di,前趋集Pi；2设置Ss为真,Ds为0；3选取Di最小的顶点加入顶点集；4计算非顶点集中顶点的路径权集；5重复3n-1次;算法的时间复杂度为On^2;22.拓扑排序：对一个有向无环图进行拓扑排序,是将图中所有顶点排成一个线性序列,满足弧尾在弧头之前;这样的线性序列称拓扑序列;1无前趋的顶点优先：总是选择入度为0的结点输出并删除该顶点的所有边;设置各个顶点入度时间是On+e,设置栈或队列的时间是On,算法时间复杂度为On+e;2无后继的顶点优先：总是选择出度为0的结点输出并删除该顶点的所有边;设置各个顶点出度时间是On+e,设置栈或队列的时间是On,算法时间复杂度为On+e;求得的是逆拓扑序列;第八章排序1.文件：由一组记录组成,记录有若干数据项组成,唯一标识记录的数据项称关键字；2.排序是将文件按关键字的递增减顺序排列；3.排序文件中有相同的关键字时,若排序后相对次序保持不变的称稳定排序,否则称不稳定排序；4.在排序过程中,文件放在内存中处理不涉及数据的内、外存交换的称内排序,反之称外排序；5.排序算法的基本操作：1比较关键字的大小；2改变指向记录的指针或移动记录本身;6.评价排序方法的标准：1执行时间；2所需辅助空间,辅助空间为O1称就地排序；另要注意算法的复杂程度;7.若关键字类型没有比较运算符,可事先定义宏或函数表示比较运算;8.插入排序1直接插入排序算法中引入监视哨R0的作用是：1保存Ri的副本；2简化边界条件,防止循环下标越界;关键字比较次数最大为n+2n-1/2；记录移动次数最大为n+4n-1/2；算法的最好时间是On；最坏时间是On^2；平均时间是On^2；是一种就地的稳定的排序；2希尔排序实现过程：是将直接插入排序的间隔变为d;d的取值要注意：1最后一次必为1；2避免d 值互为倍数；关键字比较次数最大为n^；记录移动次数最大为^；算法的平均时间是On^；是一种就地的不稳定的排序；9.交换排序1冒泡排序实现过程：从下到上相邻两个比较,按小在上原则扫描一次,确定最小值,重复n-1次;关键字比较次数最小为n-1、最大为nn-1/2；记录移动次数最小为0,最大为3nn-1/2；算法的最好时间是On；最坏时间是On^2；平均时间是On^2；是一种就地的稳定的排序；2快速排序实现过程：将第一个值作为基准,设置i,j指针交替从两头与基准比较,有交换后,交换j,i;i=j时确定基准,并以其为界限将序列分为两段;重复以上步骤;关键字比较次数最好为nlog2n+nC1、最坏为nn-1/2；算法的最好时间是Onlog2n；最坏时间是On^2；平均时间是Onlog2n；辅助空间为Olog2n；是一种不稳定排序；10.选择排序1直接选择排序实现过程：选择序列中最小的插入第一位,在剩余的序列中重复上一步,共重复n-1次;关键字比较次数为nn-1/2；记录移动次数最小为0,最大为3n-1；算法的最好时间是On^2；最坏时间是On^2；平均时间是On^2；是一种就地的不稳定的排序；2堆排序。

数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 0第2章线性表 (4)第3章栈和队列 (12)第4章串、数组和广义表 (25)第5章树和二叉树 (32)第6章图 (41)第7章查找 (53)第8章排序 (64)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

数据结构（C语言版）（第2版）课后习题答案李冬梅目录第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。

每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。

《数据结构》学习指导说明：本指导以《数据结构》(C语言版)(严蔚敏等编著,清华大学出版社1997年出版，国家级优秀教材特等奖)和《数据结构题集》(严蔚敏等编著,清华大学出版社1999年出版)为教学主要参考书。

一、绪论1、学习目的：明确数据结构课程在本专业知识结构中的地位，作用。

课程的特点，教学的要求，方法。

明确数据结构所研究的问题以及有关基本概念。

初步掌握抽象数据类型的表示与实现，初步明确算法分析的作用与分析的重点，初步掌握算法分析的方法。

2、学习重点：数据的逻辑结构、存储结构及其算法，数据结构的有关概念，抽象数据类型及其表示与实现，算法，算法设计的要求，算法的时间复杂度和算法的空间复杂度。

3、学习难点：数据结构的有关概念，抽象数据类型的表示与实现；算法的时间复杂度分析。

4、课程内容与基本要求(一) 数据结构的引入(1) 三个世界：现实世界，信息世界，机器世界。

数据结构要解决的就是实现从现实世界到信息世界，再由信息世界到机器世界的转换，从而实现用计算机来解决问题的目的。

(2) 非数值问题(结合三个世界讲)：控制，管理，数据处理(3) 数值问题：数值计算(4)数据结构：从学科角度讲，数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及他们之间的关系和操作等等的学科。

(二) 课程的地位，性质，作用。

(1) 地位: 计算机专业的核心课程之一。

(2) 性质: 算法理论基础和软件设计的技术基础课。

(3) 作用: 程序设计的基础，编译程序，操作系统，数据库系统及软件系统和应用程序的基础(三) 数据结构的产生和发展(四) 课程的特点，学习的要求教材：《数据结构》(C语言版)严蔚敏等编著北京清华大学出版社1997年参考书：《数据结构》许卓群等编著北京高等教育出版社1987年数据结构实用教程》（C/C++描述）徐孝凯北京清华大学出版社1999年《数据结构题集》严蔚敏等编著北京清华大学出版社1999年《数据结构导学》苏光奎等编著北京清华大学出版社20XX年《数据结构》(C语言篇)－习题与解析李春葆编著北京清华大学出版社20XX年《数据结构》实验指导书唐开山自编讲义20XX年(五) 基本概念和术语数据数据元素数据对象(4)数据结构:按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它存储到计算机的存储器中，并在这些数据上定义了一个运算的集合，叫做一个数据结构。

第一章概述一、概念：1．学科：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等。

2．概念：由某一数据对象及该对象中所有数据成员之间的关系组成。

具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存储结构和对数据所施加的运算。

3．这三个方面的关系为：1)数据的逻辑结构独立于计算机，是数据本身所固有的。

2)存储结构也称为物理结构，是逻辑结构在计算机存储器中的映像，必须依赖于计算机。

3)运算是指所施加的一组操作总称。

运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。

4．数据（data）:信息的载体，指能够输入到计算机中，并被计算机识别和处理的符号的集合。

例如：数字、字母、汉字、图形、图像、声音都称为数据。

5．数据元素（data element）：数据元素是组成数据的基本单位。

数据元素是一个数据整体中相对独立的单位。

但它还可以分割成若干个具有不同1属性的项（字段），故不是组成数据的最小单位。

6．逻辑结构：从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。

7．物理结构：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。

8．逻辑结构与存储结构二者关系：物理结构是逻辑结构的存储映象。

任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。

9．从逻辑结构划分数据结构：线性结构和非线性结构（树、图）10．线性结构：1)元素之间为一对一的线性关系2)第一个元素无直接前驱3)最后一个元素无直接后继11．非线性结构231) 元素之间为一对多或多对多的非线性关系2) 每个元素有多个直接前驱或多个直接后继12．顺序存储：数据元素存储方法：所有元素存放在一片连续的存贮单元中。

数据元素之间关系表示：逻辑上有相邻关系的元素存放到计算机内存仍然相邻，即存储位置体现了数据元素之间的关系。

全国计算机等级考试二级教程一一公共基础知识考试大纲♦基本要求1.掌握算法的基本概念。

2,掌握基本数据结构及其操作。

3,掌握基本排序和查找算法。

4,掌握逐步求精的结构化程序设计方法。

5,掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。

6,掌握数据库的基本知识，了解关系数据库的设计。

♦考试内容一、基本数据结构与算法1,算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。

2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。

3,线性表的定义；线性表的顺序存储结构及其插入与删除运算。

4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。

5,线性单链表、双向链表与循环链表的结构及其基本运算。

6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。

7,顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。

二、程序设计基础1.程序设计方法与风格。

2,结构化程序设计。

3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。

三、软件工程基础1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。

2,结构化分析方法，数据流图，数据字典，软件需求规格说明书。

3,结构化设计方法，总体设计与详细设计。

4,软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。

5 .程序的调试，静态调试与动态调试。

四、数据库设计基础1,数据库的基本概念：数据库，数据库管理系统，数据库系统。

6 .数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。

7 .关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。

8 .数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。

*考试方式公共基础知识有10道选择题和5道填空题共三十分第一章数据结构与算法1.1算法1、算法是指解题方案的准确而完整的描述。

数据：是对客观事物的符号表示。

数据元素：是数据的基本单位，也称节点（node）或记录（record）。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

数据项：有独立含义的数据最小单位，也称域(field)。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

根据数据元素间关系的基本特性，有四种基本数据结构集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。

线性结构：结构中的数据元素之间存在一个对一个的关系。

树形结构：结构中的数据元素之间存在一个对多个的关系。

图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。

逻辑结构：抽象反映数据元素之间的逻辑关系。

（算法设计）物理结构（存储结构）：数据结构在计算机中的表示。

（算法实现）存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。

链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。

算法：对特定问题求解步骤的一种描述。

算法的五个重要特性：有穷性，确定性，可行性，输入和输出。

算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。

衡量算法效率的方法：事后统计法和事前分析估算法。

算法执行时间的增长率和f(n) 的增长率相同，则可记作：T (n) = O(f(n))，称T (n) 为算法的(渐近)时间复杂度算法运行时间的衡量准则：以基本操作在算法中重复执行的次数。

栈：限定仅在表尾进行插入或删除操作线性表。

入栈：插入元素的操作；出栈：删除栈顶元素的操作。

队列：只能在队首进行删除、队尾进行插入的线性表。

允许插入的一端叫队尾，删除的一端叫队头。

串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目；空串：零个字符的串；子串：；串中任意个连续的字符组成的子序列；位置：字符在序列中的序号；相等：串的值相等；空格串：由一个或多个空格组成的串，空格串的长度为串中空格字符的个数。

1. 《数据结构》课程学习什么内容？数据结构是指数据以及相互之间的关系。

记为：数据结构= { D, R }。

其中，D是某一数据对象，是数据元素的有限集合；R是该对象中所有数据元素之间的关系的有限集合。

有关数据结构的讨论一般涉及以下三方面的内容：①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；③施加于该数据结构上的操作。

2. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？集合、线性结构、树形结构、图形或网状结构。

3. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？（1）顺序存储方式。

数据元素顺序存放，每个存储结点只含一个元素。

存储位置反映数据元素间的逻辑关系。

存储密度大，但有些操作（如插入、删除）效率较差。

（2）链式存储方式。

每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。

指针反映数据元素间的逻辑关系。

这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。

（3）索引存储方式。

除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。

（4）散列存储方式。

通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。

其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。

4. 数据类型和抽象数据类型是如何定义的。

二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。

如C语言中的整型、实型、字符型等。

整型值的范围（对具体机器都应有整数范围），其操作有加、减、乘、除、求余等。

数据结构（ C语言版）（第 2版）课后习题答案李冬梅2015.3目录第 1 章绪论 (1)第 2 章线性表 (5)第 3 章栈和队列 (13)第 4 章串、数组和广义表 (26)第 5 章树和二叉树 (33)第 6 章图 (43)第 7 章查找 (54)第 8 章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0 ，± 1，± 2，, } ，字母字符数据对象是集合C={‘A’，‘B’， , ，‘Z’，‘ a’，‘ b’， , ，‘z ’} ，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学 1999 一、3（1分）】A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学 1999 一、4】A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构。

精品文档考试教学资料施工组织设计方案数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (42)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

数据结构与算法1. 数据结构数据结构是带结构的数据元素的集合。

（结构是指数据元素之间的关系）数据结构包含：逻辑结构：数据之间的逻辑关系物理结构（存储结构）：数据元素及其关系在计算机内部的表示数据的运算和实现2. 逻辑结构线性结构：有且只有一个开始和一个终端结点，并且所有结点最多只有一个直接前驱和一个直接后继。

非线性结构：一个结点可能有多个直接前驱和直接后继；具体有集合结构，树形结构，图状结构。

3. 存储结构顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。

优点：随机存取；缺点：只能使用相邻的一整块存储单元，可能产生较多外部水片。

链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。

优点：不会产生碎片现象，能充分利用所有存储单元；缺点：每个元素因指针而占用额外的存储空间，只能实现顺序存储。

索引存储结构：在存储元素信息的同时，还建立附加的索引表。

优点：检索速度快；缺点：索引表占用额外的存储空间，增加和删除数据会修改索引表，耗时较多。

散列存储结构：根据元素的关键字直接计算出该元素的存储地址。

优点：检索、增加、删除结点操作很快；缺点：可能出现冲突，解决冲突会增加时间和空间开销。

4. 数据类型数据类型是一组性质相同的值的集合，以及定义于这个集合上的一组操作的总称。

在C语言中，声明了某个数据类型的变量，意味着规定了该变量的存储空间大小，以及能够执行的运算。

5. 抽象数据类型（A bstract D ata T ype, ADT）三要素<D, S, P>数据对象数据对象的关系集数据对象的操作集6. 算法算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。

此外算法具有如下5个重要特性：有穷性：一个算法必须总在执行有穷不之后结束，且每一步都可在有穷时间内完成；确定性：算法中每条指令必须有确切的含义，对于相同的输入只得得到相同的输出；可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现；输入输出7. 算法效率的度量时间复杂度时间复杂度是指算法中基本运算的执行次数的数量级。