数据：是对客观事物的符号表示。数据元素：是数据的基本单位，也称节点（node）或记录（record）。数据对象：是性质相同的数据元素的集合，是数据的一个子集。。数据项：有独立含
义的数据最小单位，也称域(field)数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素间关系的基本特性，有四种基本数据结构集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。线性结构：结构中的数据元素之间存在一个对一个的关系。树形结构：结构中的数据元素之间存在一个对多个的关系。图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。逻辑结构：抽象反映数据元素之间的逻辑关系。（算法设计）（算法实现）物理结构（存储结构）：数据结构在计算机中的表示。存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。算法：对特定问题求解步骤的一种描述。算法的五个重要特性：有穷性，确定性，可行性，输入和输出。算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。。衡量算法效率的方法：事后统计法和事前分析估算法T (n) = O(f(n))，称T (n) 算法执行时间的增长率和为算法的(渐近)时f(n) 的增长率相同，则可记作：间复杂度算法运行时间的衡量准则：以基本操作在算法中重复执行的次数。删除栈顶元素的操作。栈：限定仅在表尾进行插入或删除操作线性表。入栈：插入元素的操作；出栈：队列：只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾，删除的一端叫队头。串：由零个或多个字符组成的有限序列；空串：零个字符的
串；长度：串中字符的数目；；串中任意个连续的字符组成的子
序列；位置：字符在序列中的序号；空串：零个字符的串；子串：
相等：串的值相等；空格串：由一个或多个空格组成的串，空格
串的长度为串中空格字符的个数。LOC(i ,j)=LOC(0,0)+(b存储位
置：*i+j)L2结点:: 结点拥有的子树；包含一个数据元素及若干指
向其子树的分支；结点的度树的度: 度大于零的结点度为零的结
点；分支结点:树中所有结点的度的最大值；叶子结点:
树的深度：树中叶子结点所在的最大层次森林：m棵互不相交的
树的集合。二叉树的性质：i-1 个结点。层上至多有2(i≥1)
性质1：在二叉树的第i
k性质2：深度为k 的二叉树上至多含2-1 个结点。（k≥1）n 个叶子结点、n对任何一棵二叉树，若它含有个度为 2 的结点，
性质3: 2 0
n则必存在关系式：= n+1。20性质4: 具有n log +1。n 个
结点的完全二叉树的深度为2k且含有满二叉树：指的是深度为个
结点的二叉树。-1k2n 1 n 的结点一一对应。至完全二叉树：
树中所含的个结点和满二叉树中编号为路径长度：路径上分支的
数目。树的路径长度：树根到每个结点的路径长度之和。WPL(T) =wl树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：kk长度最小的二叉树，称为最优树二叉树或赫夫曼树。带权路径关键路径：路径长度最长的路径。．
顶点：数据元素vi称为顶点边、弧：P (vi,vj)表示顶点vi和顶点
vj之间的直接连线，在无向图中称为边，在有向图中称为弧。任
意两个顶点构成的偶对(vi,vj)∈E是无序的，该连线称为边。是
有序的，该连线称为弧。弧头、弧尾：带箭头的一端称为弧头，不带箭头的一端称为弧尾。顶点的度(TD)=出度(OD)+入度(ID)
图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等
算法的基础。通常有两条遍历图的路径：深度优先搜索和广度优
先搜索。排序的分类：按待排序记录所在位置内部排序：待排序
记录存放在内存外部排序：排序过程中需对外存进行访问的排序
按排序依据原则插入排序：直接插入排序、折半插入排序、希尔
排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、
堆排序归并排序：2-路归并排序基数排序一、名词总结：ADT：抽象数据型是一个数学模型和在该模型上定义的
操作的集合线性表：线性表是由n(n≥0)个相同类
型的元素组成的有序集合。栈：线性表的一种特殊形式，是一种限定性数据结构，也就是在对线性表的操作加以限制后，形成的一种新的数据结构。是限定只在表尾进行插入和删除操作的线性表。栈又称为后进先出的线性表。队列：将线性表的插入和删除操作分别限制在表的两端进行，和栈相反，队列是一种先进先出的线性表。串：线性表的一种特殊形式，表中每个元素的类型为字符型，是一个有限的字符序列。广义表：由零个原子，或若干个原
子或若干个广义表组成的有穷序列。也是这株树的根。x这个结点，(Tree)是一株树{x}组成的集x一个结点、1树：
2、假设x是一个结点，T1，T2，,，Tk是k 株互不相交的树，我们可以构造一株新树：令x为根，并有k条边由x指向树T1，T2，,，Tk。这些边也叫做分支，T1，T2，,，Tk称作根x的树之子树。二叉树：有限个结点的集合，这个集合或者是空集，或者是由一个根结点和两株互不相交的二叉树组成，其中一株叫根的做左子树，另一棵叫做根的右子树。满二叉树：深度为k且有2k －1个结点的二叉树称为满二叉树。完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每个结点都与深度为k 的满二叉树中编号从 1 至n 的结点一一对应，称之为完全二叉树。线索二叉树：若结点p 有左孩子，则p->lchild指向其左孩子结点，否则令其指向其（中序）前驱。若结点p有右孩子，则
p->rchild指向其右孩子结点，否则令其指向其（中序）后继。堆：如果一棵完全二叉树的任意一个非终端结点的元素都不小于其左儿子结点和右儿子
结点（如果有的话）的元素，则称此完全二叉树为最大堆。同样，如果一棵完全二叉树的任意一个非
终端结点的元素都不大于其左儿子结点和右儿子
结点（如果有的话）的元素，则称此完全二叉树为最小堆。选择树：一棵选择树是一棵二叉树，其中每一个结点都代表该结点两个儿子中的较小者。这样，树的根结点就表示树中最小元素的结点。二叉排序树：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：1、若它的左子树非空，则左
子树上的所有结点的值均小于它的根结点的值。2、若它的右子树非空，则右子树上的所有结点的值均大于或等于它的根结点的值。3、它的左右子树分
别为二叉排序树。图：一个图G=（V，E）是一个由非空的有限集V和一个边集E所组成的。若E
中的每条边都是顶点的有序对（v , w），就说该图
是有向图（directed graph，digraph）。若E中的
每条边是两个不同顶点无序对，就说该图是无向图，其边仍表示成（v, w）。开放树：连通而无环路的无向图称作开放树。最小生成树：设G=( V, E )是一
个连通图，E中每一条边(u, v)的权为C(u, v)，中
所有结点的一株开V是连接(spanning tree)的一
株生成树G也叫做边长。图
放树。将生成树中所有边长之总和称为生成树的价(cost)。使这个价最小的生成的最小生成树。G树
称为图无向图双连通分量：设是中各边所连接的点集（1≤i≤k）, 每个图Ei Vi
Gi = ( Vi , E i) G的一个双连通分量。叫做双连通图：若对V中每个不同的三元组；在和之间都存在wvv,w,a一条不包含的路，就说G是双连通的a 强连通性：设G =（V, E）是一个有向图，称顶点∈V是等价的，要么v = v ,wwvwwv也有一条有向路。到有一条有向路；要么从顶点，并且从顶点到拓扑排序：给定一个无环路有向图G=(V,E) , 各结点的编号为=(1,2, ,,n)。vi ij 的前导，则有重新进行编号，使得若是要求对每一个结点ij]Label[。即拓扑分类是将无环路有向图排成一个线性序列，使当从] 表示一个数据元素。AVL树：AVL树或者是一颗空二叉树，或者具有如下性质的二叉查找树：其左子树和右子树都是高度平衡的二叉树，且左子树和右子树高度之差的绝对值不超过1。B-树：B-树是一种非二叉的查找树除了要满足查找树的特性，还要满足以下结树：B- m 阶的构特性：一棵m之间。和或者其儿子数在一个节点的树), 2 ）树的根或者是一片叶子（1(m/2m之间。）除根外，所有的非叶子结点的孩子数在和（2）所有的叶子结点都在相 同的深度。3（树的一种变形，二者区别在于：B-树：B+个关键码；k个子结点的结点必然有k、有1． 2、非叶子结点仅具有索引作用，与记录有关的信 息均放在叶结点中。地址散列法：被查找元素的存储地址= Hash ( )。KeyA表示的二元树称为堆（堆分类：把具有如下性质的数组Heap）: ≤(1) A[2*i].key ; 若2*i≤n，则A[i].key 若2*i+1 (2) ≤小顶堆n，则A[i].key≤A[2*i+1].key; A表示的二元树称为堆（Heap）: 把具有如下性质的数组(1) 若2*i≤n， 则≥A[2*i].key ; A[i].key 若2*i+1≤n，则A[i].key≥A[2*i+1].key; (2) 大顶堆词典排序：设集合中的元素为整数元组，关系为的线性序，对两个元SS≤ ( s1,s2,,,sp )( t1,t2,,,tq )存和素,,tq )j1≤j≤ ( s1,s2,,,sp ) ≤( t1,t2,在当存在一个整数，，max[p,q]，使得sj≤tj，且所有1≤i＜j，si＝ti；或者p≤q，并且si＝ti，1≤i≤p≤称为词典序。，则关系归并方法：首先将文件中的数据输入到内存，采用内部分类方法进行分类（归并段），然后将有序段写回外存；对多归并段进行多遍归并，最后形成一个有序序列。索引：指的是记录的关键字值与记录驻留在外存的地址组成数对的集合。每个数对称为一个索引项。二、重要算法总结第二章：1、模式匹配法（KMP算法）2、串的Substr算法第三章：1、二叉树的先、中、后序遍历（递归算法） 2、二叉树的中序非递归遍历（辅助栈、非辅助栈） 3、二叉树交换左右子树； 4、二叉树求深度、结点赋层号、哈夫曼树的构造5． 第四章：1、DFS、BFS 2、最小生成树 3、强连通性 4、拓扑排序 5、Dijkstra算法单源最短路径第五章：1、二叉排序树2、AVL树3、地址散列法第六章：简单排序算法及快排1．数据结构是一门研究什么内容的学科？数据结构是一门研究在非数值计算的程序设 计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。2．数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 四种表示方法（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。（3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的 地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。3．数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据 类型的主要好处是什么？数据类型是程序设计语 言中的一个概念，它是一个值的集合和操作的集合。如C语言中的整型、实型、字符型等。整型值的范围（对具体机器都应有整数范围），其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型（ADT）”指一个数学模型及定义在该模型上的一 组操作。“抽象”的意义在于数据类型的数学抽象 特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类 型。使用抽象数据类型定义的软件模块含定义、表 示和实现三部分，封装在一起，对用户透明（提供接口），而不必了解实现细节。抽象数据类型的出 现使程序设计不再是“艺术”，而是向“科学”迈 进了一步。4．对于一个数据结构，一般包括哪三个方面：逻辑结构、存储结构、操作（运算）。5．根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？集合、线性结构、树形结构、图形或网状结构。6．线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有n个线性表同 时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。7．线 性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。 线性表的链式存储结构是否一定都能够克服上述 三个弱点，试讨论之。链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储受可用内存空间的限制。8的缺点。．栈是只准在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（）表。9．队列是允许在一端插入而LIFO在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（）表。．什么是循环队列？用常规意义下顺序存储结10FIFO构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存11．若元素的进栈序列为：储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。A、B、C、A、E、D和D、B、A、C、E？为什么？、BC、D、E，运用栈操作，能否得到出栈序列能得到D。其理由为：若出栈序列以开头，、C、EDAC、、E、，不能得到出栈序列D、B、AB出栈序列、A、B 和C之前的入栈元素是说明在D，三个元素中C是栈顶元素，B 和A不可能早于C出栈，故不12、出栈序列。．串？串是零个至多个字符组成的有限序列。从数据结构CAB、、、E可能得到D 角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。．描述以下概念的区别：空13ASCII码值是格串与空串。空格是一个字符，其32。空格串是由空格组成的串，其长度等于空格的14．数组A[1..8，-2..6，0..6]以行为主序存个数。空串是不含任何字符的串，即空串的长度是零。4，试求元素A[4,2,3]的存储首地址。78，每个元素的长度为储，设第一个元素的首地址是958 三维为：主组数以行为地存序储，其址公式元素LOC(ALOC(ALOC(ALOC(Aijkijkijkijk)=LOC(A)=LOC(A)=LOC( A)=LOC(Ac1c2c3c1c2c3c1c2c3c1c2c3)+[(i)+[(i)+[(i)+[(i----cccc 1111)V)V)V)V2222VVVV3333+(j+(j+(j+(j----cccc2222)V)V)V)V 3333+(k+(k+(k+(k----cccc3333)]*L+1)]*L+1)]*L+1)]*L+1 其中ci,di是各维的下界和上界，Vi=di-ci+1是各维元素个数，L是一个元素所占A[i,j]的长度均为32个二进位,行下标从的存储单元数。．数组15A中，每个元素-1到9，列下标从（1）存放该数组所需111到，从首地址S开始连续存放主存储器中，主存储器字长为位。求：164列所有元素至少需多少单元？（2）数组按行存放时，元素（多少单元？3A[7,4]）存放数组第的起始地址是多少？A[4,7]）数组按列存放时，元素4（答：每个元素个二32的起始地址是多少？ 进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。（1）242 （2）22 （3）s+142 ）4s+182 （16. 从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。17线性表属．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。在非空线性表中，只有一个“第一个”于约束最强的线性结构，元素，也只有一个“最后一个”元素；每个元素有唯一后继。树是一种层次结除最后一个元素外，除第一个元素外，每个元素有唯一前驱；，从这个意义上构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲）说存在一（双亲）对多（子女）的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕 变为线性结构。如度为1的树，以及广义表中的元素都是原子时。另外，广义也符合线性表，表从元素之间的关系可看成前驱和后继，但这时元素有原子，也有子表，即元素并不0或为2，则二叉树的枝数为2(n0-1)，其中18．一棵二叉树中的结点的度或为属于同一数据对象。证明：2的结点数及总的结点数分别为设二叉树度为和n，0和n0，n0是度为0的结点的个数。n2 (1) 再设二叉树的分支数为B, n=n0+n2 则除根结点外，每个结点都有一个分支所指，则,2的结点有两个分支，因此（,(2) 2n=B+1,,）式可度为零的结点是叶子，没有分支，而度为写为 n=2*n2+1 (3) 由（1）（3）、得n2=n0-1,,,,,,代入（1），并由（1）和（2）得B=2*(n0-1)。n个顶点的连通无向图，那么19．（G1最少1）G1最多有多少条边？证毕。．如果G1是一个具有（nG2有多少条边？个顶点的强连通有向图，那么G2最多有多少条边？2）．如果G2是一个具有最少有多少条边？（3）．如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少有多少条边？答：（1）G1最多n(n-1)/2条边，最少n-1条边(2) G2最多n(n-1)条边，最少n条边(3) G3最多n(n-1)条边，最少n-1条边(注：弱连通有向图指把有向图看作无向图时，仍 是连通的) 20．nn n个顶点的有向连通图最少有多少条边？n-1，个顶点的无向连通图最少有多少条边？21．内部排序（名词解释）假设含n个记录的序列为{ R1, R2, ,{ K1, ，Rn }，其相应的关键字序列为K2, ,，Kn }，这些关键字相互之 间可以进行比较，即在它们之间存在着这样一个关系Ks1≤Ks2≤，{ Rs1, Rs2, nKsn，按此固有关系将个记录序列重新排列为,，Rsn }。若整个排序过程都在内存中≤完成，则称此类排序问题 为内部排序。22．在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例直 接插入排序二路插入排序OO（n2）O（n2）O（1）稳定折半插入排序O（n2）O（n2）O（1）稳定O表插入排序（O（n）稳定n2）O（n2OO（n2））O（1）稳定起泡排序））（n2O（n2直接选择排序O））（n2O（1稳定（n2）O（n2）O（1）不稳定2,2'）（On1.3,1 希尔排序3,2,2',1(d=2,d=1) 快速排序O （nlog2n）O（不稳定1On1.3O（）（）n2）O（log2n）不稳定2,2',1 O（nlog2n）O（nlog2n）堆排序O（nlog2n）O（nlog2n）O （1）不稳定2,1,1'(极大堆) 2-路归并排序O（n）稳定基数排序O ( d*(rd+n) ) O ( d*(rd+n) ) O (rd ) 稳定23．文件文件是由大量性质相同的记录组成的集合，按记录类型不同可分为操作系统文件和数据库文件。24．文件存储结构的基本形式有哪些？一个文件采用何种存储结构应考虑哪些因素？文件的基本组织方式有 顺序组织、索引文件的存储结构可以采用将基本组织结合的方法，组织、散列组织和链组织。常用的结构有顺序结构、． 索引结构、散列结构。（1）顺序结构，相应文件为顺序文件，其 记录按存入文件的先后次序顺序若逻辑上相邻的两个记录在存 储位置上相邻，则为连续文件；若存放。顺序文件本质上就是顺序表。则称为串联文件。顺序文件只能顺序存取，要更新某个记录，记录之间以指针相链接，必须复制整个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。）带索引的结构，2（索引表中的索引项包括数据表中数据的关键字相应文件为索引文件。索引文件包括索引表和数据表，和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能隋机存取。（3）散列结构，也称计算寻址结构，相应文件称存取速度快，不需索引，节省存储为散列文件，其记录是根据关键字值经散列函数计算确定其地址，其它文件均由以上文件派生而得。文件采用何种存储结构应不能顺序存取，只能随机存取。空间。综合考虑各种因素，如：存储介质类型、记录的类型、大小和关键字的数目以及对文件作何种操作。25．索引文件在主文件外，再建立索引表指示关键字及其物理记录的地址间一一对应关系。这索引表依关键字有序。主文件若按关键字有序称种由索引表和主文件一起构成的文件称为索引文件。为索引顺序文件，否则称为索引非顺序文件（通常简称索引文件）。索引顺序文件因主文件有序，一VSAM而采用静态索引结构，ISAM。VSAM占用空间较少。般用稀疏索引，常用索引顺序文件有和ISAM树的动态索引结构。索引文件既能顺序存取，也能随机存取。26采用．索 引顺序文件在索引文B+件中，若（数据区）主文件中关键字有序，则文件称为索引顺序文件。． 数据：是对客观事物的符号表示。 数据元素：是数据的基本单位，也称节点（node）或记录（record）。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。 数据项：有独立含义的数据最小单位，也称域(field)。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 根据数据元素间关系的基本特性，有四种基本数据结构集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 线性结构：结构中的数据元素之间存在一个对一个的关系。 树形结构：结构中的数据元素之间存在一个对多个的关系。 图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。 逻辑结构：抽象反映数据元素之间的逻辑关系。（算法设计）物理结构（存储结构）：数据结构在计算机中的表示。（算法实现） 存储结构分为： 顺序存储结构：借助元素在存储器中的相对位置来表 示数据元素间的逻辑关系。 链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。 算法：对特定问题求解步骤的一种描述。 算法的五个重要特性：有穷性，确定性，可行性，输入和输出。 算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。 衡量算法效率的方法：事后统计法和事前分析估算法。 算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n))，称T (n) 为算法的(渐近)时间复杂度算法运行时间的衡量准则：以基本操作在算法中重复执行的次数。 栈：限定仅在表尾进行插入或删除操作线性表。入栈：插入元素的操作；出栈：删除栈顶元素的操作。 队列：只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾，删除的一端叫队头。串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目； 空串：零个字符的串；子串：；串中任意个连续的字符组成的子序列；位置：字符在序列中的序号； 相等：串的值相等；空格串：由一个或多个空格组成的串， 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 数据结构概念名词解 释大全 数据：是对客观事物的符号表示。 数据元素：是数据的基本单位，也称节点（node）或记录（record）。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。 数据项：有独立含义的数据最小单位，也称域(field)。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 根据数据元素间关系的基本特性，有四种基本数据结构 集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 线性结构：结构中的数据元素之间存在一个对一个的关系。 树形结构：结构中的数据元素之间存在一个对多个的关系。 图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。 逻辑结构：抽象反映数据元素之间的逻辑关系。（算法设计） 物理结构（存储结构）：数据结构在计算机中的表示。（算法实现） 存储结构分为： 顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。 链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。 算法：对特定问题求解步骤的一种描述。 算法的五个重要特性：有穷性，确定性，可行性，输入和输出。 算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。 衡量算法效率的方法：事后统计法和事前分析估算法。 算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n))，称T (n) 为算法的(渐近)时间复杂度 算法运行时间的衡量准则：以基本操作在算法中重复执行的次数。 栈：限定仅在表尾进行插入或删除操作线性表。入栈：插入元素的操作；出栈：删除栈顶元素的操作。 队列：只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾，删除的一端叫队头。串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目； 空串：零个字符的串；子串：；串中任意个连续的字符组成的子序列；位置：字符在序列中的序号； 相等：串的值相等；空格串：由一个或多个空格组成的串，空格串的长度为串中空格字符的个数。 存储位置：LOC(i ,j)=LOC(0,0)+(b2*i+j)L 结点:包含一个数据元素及若干指向其子树的分支；结点的度: 结点拥有的子树； 树的度:树中所有结点的度的最大值；叶子结点: 度为零的结点；分支结点: 度大于零的结点 树的深度：树中叶子结点所在的最大层次森林：m棵互不相交的树的集合。 二叉树的性质： 性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i≥1) 性质 2：深度为 k 的二叉树上至多含 2k-1 个结点。（k≥1） 性质 3: 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。 性质 4: 具有 n 个结点的完全二叉树的深度为? log2n? +1。 满二叉树：指的是深度为k且含有2k-1个结点的二叉树。 完全二叉树：树中所含的n 个结点和满二叉树中编号为1 至n 的结点一一对应。 Data Structure 2015 hash table散列表：存放记录的数组 topological sort拓扑排序：将一个DAG中所有顶点在不违反前置依赖条件规定的基础上排成线性序列的过程称为拓扑排序（44） worst case 最差情况：从一个n元一维数组中找出一个给定的K，如果数组的最后一个元素是K，运行时间会相当长，因为要检查所有n 个元素，这是算法的最差情况（15） FIFO先进先出：队列元素只能从队尾插入，从队首删除（20）（P82）2014 growth rate增长率：算法的增长率是指当输入的值增长时，算法代价的增长速率（14） priority queue 优先队列：一些按照重要性或优先级来组织的对象成为优先队列（26） external sorting外排序：考虑到有一组记录因数量太大而无法存放到主存中的问题，由于记录必须驻留在外存中，因此这些排序方法称为外排序（32） connected component连通分量：无向图的最大连通子图称为连通分量（40） 2013 stack栈：是限定仅在一端进行插入或删除操作的线性表（19） priority queue 优先队列：一些按照重要性或优先级来组织的对象成为优先队列（26） BFS广度优先搜索：在进一步深入访问其他顶点之前，检查起点的所有相邻顶点（42） collision (in hashing)冲突：对于一个散列函数h和两个关键码值k1和k2，如果h(k1) =β= h(k2) ，其中β是表中的一个槽，那么就说k1和k2对于β在散列函数h下有冲（35） Chapter 1 Data Structures and Algorithms type类型：是指一组值的集合 data type数据类型：一个类型和定义在这个类型上的一组操作abstract data type (ADT) 抽象数据类型：指数据结构作为一个软件构件的实现 data structure数据结构：是ADT的实现 problem问题：一个需要完成的任务，即对应一组输入，就有一组相应的输出 function函数：是输入和输出之间的一种映射关系 algorithm算法：是指解决问题的一种方法或者一个过程algorithm算法是解决问题的步骤，它必须把每一次输入转化为正确的输出；一个算法应该由一系列具体步骤组成，下一步应执行的步骤必须明确；一个算法必须由有限步组成；算法必须可以终止。computer program计算机程序：被认为是使用某种程序设计语言对一个算法的具体实现 1.数据结构：数据结构是所有数据元素以及数据元素之间的关系，可以看作是相互之间存 在着某种特定关系的数据元素的集合。 2.逻辑结构:逻辑结构是从逻辑关系上描述数据的，与存储结构无关，是独立于计算机的， 可以看作是从具体问题抽象出来的数学模型。 a.集合：指数据元素之间除了同属于一个集合的关系外，别无其他关系。 b.线性结构：指该结构中的节点之间存在着一一对应的关系。 c.树形结构：指该结构中的节点之间存在一对多的关系。 d.图形结构：指该结构中的节点存在多对多的关系。 3.存储结构：存储结构是逻辑结构用计算机语言表示或在计算机中的实现，也就是逻辑结 构在计算机中的存储。 a.顺序存储结构：该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元 里，节点之间的逻辑关系由存储单元的邻接关系来体现。 b.链式存储结构：节点间的逻辑关系是由附加的指针字段表示的。 c.索引存储结构：该结构通常是在存储节点信息的同时，还建立附加的索引表。 d.哈希表：根据节点的关键字通过哈希函数直接计算出一个值，并将这个值作为该 节点的存储地址。 4．算法：在具体存储结构中实现某个抽象的运算。 5．时间复杂度：执行算法所需要的计算工作量。 6．空间复杂度：执行算法所需要的内存空间。 7．线性表：具有相同特性的数据元素的一个有限序列。 8．线性表的顺序存储结构：把线性表中的所有元素按照逻辑顺序依次存储到从计算机存储器指定位置开始的一连续的存储空间中。 9．线性表的链式存储结构：每个存储节点不仅包含有元素本身的信息，而且包含元素之间逻辑关系的信息。 10．有序表：指其中所有元素以递增或递减方式有序排列的线性表。 11．栈：栈是一种只能在一端进行插入或删除操作的线性表。（采用顺序存储结构的栈称为顺序栈；采用链式存储结构的栈称为链式栈） 12．队列：队列是一种仅表的一端进行插入，而在表的另一点进行删除的线性表。（把存储队列元素的表从逻辑上看成一个环，环形队列） 13．串：由零个或多个字符组成的有限序列。 14．串的模式匹配：在主串中找到一个与子串相等的子串。 15．递归：在定义一个过程或函数时出现调用本过程或本函数的成分称为递归。 16．数组：数组是具有相同类型的数据元素的有限序列。 17．广义表：一个广义表是n(n>=0)个元素的一个序列。 18．树：树是由n(n>=0)个节点组成的有限集合。 a．表示方法：树形表示法；文氏图表示法；凹入表示法；括号表示法。 b.存储方法：双亲存储结构；孩子链存储结构；孩子兄弟链存储结构。 19．二叉树：它是有限的节点集合。 20．平衡二叉树：若一颗二叉树中每个节点的左右子树的高度至多相差1，称为平衡二叉树。21．哈夫曼树：在n个带权叶子节点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树。 22．图：由顶点和边构成。 存储方法：邻接矩阵存储法（特点：1>图的邻接矩阵表示唯一； 2>适用于存储边的数目较多的稠密图，存储空间为O（n2）; 计算机网络名词解释文件管理序列号：[K8UY-K9IO69-O6M243-OL889-F88688] 备考川大NET名词解释 1、计算机网络是利用通信设备和线路将地理位置不同的、功能独立的多个计算机系统互连起来，以功能完善的网总软件实现网络中资源共享和信息传递的系统。 2、联机系统是由一台中央计算机连接大量的地理位置分散的终端而构成的计算机系统。 3、PDN是公用数据网。网中传输的是数字化的数据，属于通信子网的一种。 4、OSI是开放系统互连参考模型。为ISO（国际标准化组织）制订的七层网络模型。 5、PSE是分组交换设备。作为网络的中间节点，它具有存储转发分组的功能。 6、PAD是分组装配/拆卸设备。在发送方将大的报文拆成若干分组，在接受方将属于同一报文的分组再重新组成报文的设备。 7、FEP是前端处理机。设置在中心计算机与通信线路之间，专门负责通信控制。 8、IMP是接口信息处理机，是网络中间节点的统称。 二、 1、数据通信：是一种通过计算机或其他数据装置与通信线路，完成数据编码信号的传输、转接、存储和处理的通信技术。 2、数据传输率：每秒能传输的二进制信息位数，单位为B/S。 3、信道容量：是信息传输数据能力的极限，是信息的最大数据传输速率。 4、自同步法：是指接收方能从数据信号波形中提取同步信号的方法。 5、PCM：称脉码调制，是将模拟数据换成数字信号编码的最常用方法。 6、FDM：又称时分多路复用技术，是在信道带宽超过原始信号所需带宽情况下，将物理停产的总带宽分成若干个与传输单个信号带宽相同的子停产，每个子信息 传输一路信号。 7、同步传输：是以一批字符为传输单位，仅在开始和结尾加同步标志，字符间和比特间均要求同步。 8、差错控制：是指在数据通信过程中能发现或纠正差错，把差错限制在尽可能小的允许范围内的技术和方法。 9、FEC：又叫向前纠错，是一种差错控制方法，接收端不但能发现错误，而且能确定二进制码元发生错误的位置，从而加以纠正。 10、信号：是数据的电子或电磁编码。 11、MODEM：又称调制解调器。其作用是完成数字数据和模拟信号之间的转换，使传输模拟信号的媒体能传输数字数据。发送端MODEM将数字数据调制转换为模拟信号，接收端MODEM再把模拟信号解调还原为原来的数字数据。 12、信号传输速率：也称码元率、调制速率或波特率，表示单位时间内通过信道传输的码元个数，单位记做BAND。 13、基带传输：是在线路中直接传送数字信号的电脉冲，是一种最简单的传输方式，适用于近距离通信的局域网。 14、串行通信：数据是逐位地在一条通信线上传输的，较之并行通信速度慢，传输距离远。 15、信宿：通信过程中接收和处理信息的设备或计算机。 16、信源：通信过程中产生和发送信息的设备或计算机。 17、全双工：允许数据同时在两个方向上传输，要有两条数据通道，发送端和接收端都要有独立的接收和发送能力。 18、冲击噪声：呈突发状，常由外界因素引起；其噪声幅度可能相当大，无法靠提高信噪比来避免，是传输中的主要差错。 第一章名词解释 这是书本上的课后习题上的： 1-26 试解释以下名词：协议栈、实体、对等层、协议数据单元、服务访问点、客户、 服务器、客户-服务器方式。 答：实体(entity) 表示任何可发送或接收信息的硬件或软件进程。 协议是控制两个对等实体进行通信的规则的集合。 客户(client)和服务器(server)都是指通信中所涉及的两个应用进程。客户是 服务的请求方，服务器是服务的提供方。 客户服务器方式所描述的是进程之间服务和被服务的关系。 协议栈:指计算机网络体系结构采用分层模型后,每层的主要功能由对等层协议 的运行来实现,因而每层可用一些主要协议来表征,几个层次画在一起很像一个栈的结构 对等层:在网络体系结构中,通信双方实现同样功能的层. 协议数据单元:对等层实体进行信息交换的数据单位. 服务访问点:在同一系统中相邻两层的实体进行交互（即交换信息）的地方.服务访问点SAP是一个抽象的概念,它实体上就是一个逻辑接口. 2-04 试解释以下名词：数据，信号，模拟数据，模拟信号，基带信号，带通信号，数 字数据，数字信号，码元，单工通信，半双工通信，全双工通信，串行传输，并行传输。 答：数据：是运送信息的实体。 信号：则是数据的电气的或电磁的表现。 模拟数据：运送信息的模拟信号。 模拟信号：连续变化的信号。 数字信号：取值为有限的几个离散值的信号。 数字数据：取值为不连续数值的数据。 码元(code)：在使用时间域（或简称为时域）的波形表示数字信号时，代表不同离散数值的基本波形。 单工通信：即只有一个方向的通信而没有反方向的交互。 半双工通信：即通信和双方都可以发送信息，但不能双方同时发送（当然也不能同时接收）。这种通信方式是一方发送另一方接收，过一段时间再反过来。 全双工通信：即通信的双方可以同时发送和接收信息。 基带信号（即基本频带信号）——来自信源的信号。像计算机输出的代表各种文字或图像文件的数据信号都属于基带信号。 带通信号——把基带信号经过载波调制后，把信号的频率范围搬移到较高的频段以便在信道中传输（即仅在一段频率范围内能够通过信道）。 数据 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据项 是数据结构中讨论的最小单位，是数据记录中最基本的、不可分的数据单位。 数据元素 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象 是性质相同的数据元素的集合，是数据的一个子集。 数据处理 是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。 数据结构 是指互相之间存在一种或多种特定关系的数据元素的集合。（包括逻辑结构、存储结构和数据运算） I.逻辑结构：线性结构、非线性结构。 II.物理结构：又称为存储结构，是数据的逻辑结构在计算机中的表示（映像），包括顺序存储方法、链式存储方法、索引存储方法、散列存储方法。 数据类型 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型 是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。 算法 解决一个问题的方法和步骤。算法的特性：有穷性、确定性、输入、输出、可行性。算法设计的目的：正确性、可读性、健壮性、高效率与低存储量需求。 时间复杂度 T(n)＝ O(F(n))，它表示随问题规模Ｎ增大，算法执行时间增长率与F(n)的增长率相同．F(n)算法的时间复杂性。原地工作 算法执行时，若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 线性表 具有相同特性数据元素的一个有限序列。是N(N>=0)个同质元素的有限序列，除首尾元素外，每个元素有唯一的前驱和唯一的后继。 顺序表 把线性表中的所有元素按照其逻辑顺序，依次存储到指定的存储位置开始的一块连续的存储空间中。 单链表 每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接后继结点的地址（指针），称为指针域，元素的存储空间可以连续，也可以是不连续的。而数据元素之间的逻辑关系由指针域来确定。 双向链表 线性表采用链式存储时，每个结点除一个数据域外，包含两个指针域，一个指向该结点的直接后继，一个指向该结点的直接前驱，这种方式构成的链表，即为双向链表。 单循环链表 是单链表的另一种形式，它是一个首尾相接的链表，表中最后一个结点的指针域由NULL改为指向头结点或线性表的第一个结点，整个链表形成了一个环． 栈 一种只能在一端进行插入或删除操作的线性表。 队列 是一种受限线性表，其限制为允许在表的一端进行插入，而在表的另一端进行删除。（进行插入的一端称为队尾，进行删除的一端称为队头），先进先出的特点（FIFO） 循环队列 地理信息系统名词解释大全 地理信息系统Geographic Information System GIS作为信息技术的一种，是在计算机硬、软件的支持下，以地理空间数据库（Geospatial Database）为基础，以具有空间内涵的地理数据为处理对象，运用系统工程和信息科学的理论，采集、存储、显示、处理、分析、输出地理信息的计算机系统，为规划、管理和决策提供信息来源和技术支持。简单地说，GIS就是研究如何利用计算机技术来管理和应用地球表面的空间信息，它是由计算机硬件、软件、地理数据和人员组成的有机体，采用地理模型分析方法，适时提供多种空间的和动态的地理信息，为地理研究和地理决策服务的计算机技术系统。地理信息系统属于空间型信息系统。 地理信息是指表征地理圈或地理环境固有要素或物质的数量、质量、分布特征、联系和规律等的数字、文字、图像和图形等的总称；它属于空间信息，具有空间定位特征、多维结构特征和动态变化特征。 地理信息科学与地理信息系统相比，它更加侧重于将地理信息视作为一门科学，而不仅仅是一个技术实现，主要研究在应用计算机技术对地理信息进行处理、存储、提取以及管理和分析过程中提出的一系列基本问题。地理信息科学在对于地理信息技术研究的同时，还指出了支撑地理信息技术发展的基础理论研究的重要性。 地理数据是以地球表面空间位置为参照，描述自然、社会和人文景观的数据，主要包括数字、文字、图形、图像和表格等。 地理信息流即地理信息从现实世界到概念世界，再到数字世界（GIS），最后到应用领域。 数据是通过数字化或记录下来可以被鉴别的符号，是客观对象的表示，是信息的表达，只有当数据对实体行为产生影响时才成为信息。 信息系统是具有数据采集、管理、分析和表达数据能力的系统，它能够为单一的或有组织的决策过程提供有用的信息。包括计算机硬件、软件、数据和用户四大要素。 四叉树数据结构是将空间区域按照四个象限进行递归分割（2n×2n，且n ≥1），直到子象限的数值单调为止。凡数值（特征码或类型值）呈单调的单元，不论单元大小，均作为最后的存储单元。这样，对同一种空间要素，其区域网格的大小，随该要素分布特征而不同。 不规则三角网模型简称TIN，它根据区域有限个点集将区域划分为相连的三角面网络，区域中任意点落在三角面的顶点、边上或三角形内。如果点不在顶点上，该点的高程值通常通过线性插值的方法得到（在边上用边的两个顶点的高程，在三角形内则用三个顶点的高程）。 拓扑关系拓扑关系是指网结构元素结点、弧段、面域之间的空间关系，主要表现为拓扑邻接、拓扑关联、拓扑包含。根据拓扑关系，不需要利用坐标或距离，可以确定一种地理实体相对于另一种地理实体的位置关系，拓扑数据也有利于空间要素的查询。 拓扑结构为在点、线和多边形之间建立关联，以及彻底解决邻域和岛状信息处理问题而必须建立的数据结构。这种结构应包括以下内容：唯一标识，多边形标识，外包多边形指针，邻接多边形指针，边界链接，范围（最大和最小x、y坐标值）。 游程编码是逐行将相邻同值的网格合并，并记录合并后网格的值及合并网 《数据结构》第二次单元测试 姓名学号. 分数. 一、单项选择题（每小题2分，共26分） 1. 数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时， 物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C. 链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 J ( )。插入和删除元素 D.没 B. 头、尾 D.头、尾指栈 C. 线性表 k层的结点数最多为B.2K+1 C.2K-1 二、填空题（每空2分，共32分） 1. 一维数组的逻辑结构是__线性____，存储结构是____顺序存储____；对于二维或多维数组，分为____顺序____和_____链式______两种不同的存储方式。 2.栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除操作，进行操作的这一端称为栈顶，与其对应的另一端称为栈底。 3. 在树型结构中，树根结点没有_____后继_____结点，其余每个结点的有且只有___1__个前趋驱结点；叶子结点没有_____子____结点；其余每个结点的后续结点可以____有多个结点______。 4. 线性结构中元素之间存在___一对一____关系；树型结构中元素之间存在__一对多_______关系。 5. 一棵深度为k的满二叉树的结点总数为__ (2^h)-1 ___，一棵深度为k的完全二叉树的结点总数的最小值为__(2^h)-1__，最大值为__(2^h)-1_。 6. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEFG，则该二叉树的 前序遍历序列为_ABDECFG___。 三、判断题（每题1分，共8分） 1. 数组可看作基本线性表的一种推广， 因此与线性表一样，可以对它进行插入、删 除等操作。（） 2. 对于不同的特殊矩阵应该采用不同的存 储方式。（） 3. 采用压缩存储之后，下三角矩阵的存 储空间可以节约一半。（） 4. 在一般情况下，采用压缩存储之后， 对称矩阵是所有特殊矩阵中存储空间节约 最多的。（） 5. 距阵中的数据元素可以是不同的数 据类型。（） 6. 矩阵中的行列数往往是不相等的。 （） 7．线性表的顺序存储结构比链式存 储结构更好。（） 页脚内容3 本章主要介绍了如下一些基本概念： ?数据结构：数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 ?数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。 ?结点：结点也叫数据元素，它是组成数据的基本单位。 ?逻辑结构：结点和结点之间的逻辑关系称为数据的逻辑结构。 ?存储结构：数据在计算机中的存储表示称为数据的存储结构。 ?数据处理：数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。 ?数据类型：数据类型是指程序设计语言中各变量可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。 本章主要介绍了如下一些基本概念： 线性表：一个线性表是n≥0个数据元素a0，a1，a2，…，an-1的有限序列。 线性表的顺序存储结构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。 线性表的链式存储结构：线性表的链式存储结构就是用一组任意的存储单元——结点（可以是不连续的）存储线性表的数据元素。表中每一个数据元素，都由存放数据元素值的数据域和存放直接前驱或直接后继结点的地址（指针）的指针域组成。 循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结 循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结点。 双向链表：双向链表中，在每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点。 除上述基本概念以外，学生还应该了解：线性表的基本操作（初始化、插入、删除、存取、复制、合并）、顺序存储结构的表示、线性表的链式存储结构的表示、一元多项式Pn(x)，掌握顺序存储结构（初始化、插入操作、删除操作）、单链表（单链表的初始化、单链表的插入、单链表的删除）。 本章主要介绍了如下一些基本概念： 栈：是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。因此，栈也被称为“后进先出”的线性表。 栈的顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的各个数据元素，称为栈的顺序存储结构。 双向栈：使两个栈共享一维数组stack[MAXNUM]，利用栈的“栈底位置不变，栈顶位置动态变化”的特性，将两个栈底分别设为-1和MAXNUM，而它们的栈顶都往中间方向延伸的栈称为双向栈。 数据结构习题 一、名词解释 1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、 算法、时间复杂度、空间复杂度。 2. 线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头 指针、头结点、首元结点（第1个元素结点）。 3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。 4. 树、叶子结点、结点的度、树的度、树的高（深）度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL哈夫曼编码。 5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、 （最小）生成树、邻接矩阵、邻接表、DFS BFSO 6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。 7. 排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2 路归并。 一、填空题 1. 数据结构是研究数据的 _逻辑结构_和—物理结构_ ,并在这种结构上定义相关的运算，设计实 现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为—时间复杂度和空间复杂度—。 2. 数据的基本单位是数据元素，数据的最小单位是数据项。 3. 算法是对特定问题求解—步骤___的一种描述，是指令的有限序列。 4. 一个算法的时间复杂度为（3n3+2n — 7）,其数量级表示为_0 （ n3） __。 5. 一个算法具有5个特性：_确定性、—可行性_、_有穷性_、输入和输出。 6. 算法性能的分析和度量，可以从算法的时间复杂度一和—空间复杂度—来评价算法的优劣。 7. 数据的逻辑结构包括集合结构、_线性结构 _、—树形结构_和_图型结构—四种类型。 8. 数据结构在计算机中的表示称为数据的物理结构，它可以采用 _顺序存储_ 或_链式存储_ 两种存储方法。 9. 线性表有两种存储结构，分别为_顺序存储 _ 和___________ 链式存储_。 10. 链式存储的特点是利用指针—来表示数据元素之间的逻辑关系。 11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用链式存储—存储结构。 12. 线性表中的数据元素之间具有 _一对一_的线性关系，除第一个和最后一个元素外，其他数据元素有且只有 一个_直接后继和直接前趋。 13. 在一个单链表中 P所指结点之后插入一个S所指结点时，应执行 s->next=_ p->next ___________ 和 p->next=_ S ________ 的操作。 数据是描述客观事物的符号,是能够被计算机输入,识别,处理的各种符号,是计算机化的信息。 2.数据项 数据不可分割的最小单位,一个元素由若干个数据项构成。 3.数据元素 它是组成数据的基本单位,是数据集合中的个体,在计算机程序中,通常作为一个整体进行考虑和处理。 4.数据对象 是性质相同的数据元素的集合,是数据的一个子集。 5.数据处理 是指对数据进行查找,插入,删除,合并,排序,统计以及简单计算等的操作过程。 6.数据结构 是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示(即数据的逻辑结构和物理结构),并对这种结构定义相适应的运算,设计出相应的算法,且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 7.数据类型 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 8.抽象数据类型 是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。 ９.算法 解决一个问题的方法和步骤。 10.时间复杂度 T(N)＝O(F(N)),它表示随问题规模Ｎ增大,算法执行时间增长率与F(N)的增长率相同,F(N)算法的时间复杂性。 11.原地工作 算法执行时,若额外空间相对于输入数据量来说是常数,则称此算法为原地工作。 12.线性表 一种数据结构,是N(N>=0)个同质元素的有限序列,除首尾元素外,每个元素有唯一的前驱和唯一的后继。 13.队列 是一种受限线性表,是先进先出的线性表 14.循环队列 在队列的顺序存储结构中,把存储空间的首尾逻辑上相连,构成一个环,使得存储空间上只要有空余的地址,就可以继续进行入队列操作,极大利用了物理空间。用头部和尾部两个指示器表示队列头和队列尾,插入在尾部进行,删除在头部进行。 15.单链表 每一个数据元素,都需用两部分来存储：一部分用于存放数据元素值,称为数据域；另一部分用于存放直接后继结点的地址(指针),称为指针域,元素的存储空间可以连续,也可以是不连续的。而数据元素之间的逻辑关系由指针域来确定。 16.双向链表 线性表采用链式存储时,每个结点除一个数据域外,包含两个指针域,一个指向该结点的直接后继,一个指向该结点的直接前驱,这种方式构成的链表,即为双向链表。 17.希尔排序 是插入排序的一种,又叫缩小增量排序,先按增量进行分组,组内插入排序,然后每次缩短增量,再进行分组和组内插入排序, 直到增量为1时,进行最后一次排序止。 18.完全图 任何一个有N个结点的无向图,若其边数为N(N-1)/2,则这个无向图就是完全图 数据结构：一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 数据：数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据类型：是一个值的集合和定义在此集合上一组操作的总称。包括 原子类型：其值不可在分的数据类型 结构类型：其值可以在分解为若干成分的数据类型 抽象数据类型：ADT，指一个数学模型以及定义在该模型上的一组操作。通常用数据对象、数据关系、基本操作集这样的三元组来表示。有数据抽象和数据封装两个重要特性。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。包括（逻辑结构、存储结构和数据的运算）。 数据的逻辑结构：指数据元素之间的逻辑关系。包括集合、线性结构、树形结构、图状结构或网状结构。 数据的存储结构：指数据结构在计算机中的表示，也成物理结构。主要有顺序存储、连接存储、索引存储、散列存储。 数据的运算：施加在数据上的运算包括运算的定义和实现。定义是针对逻辑结构，指出运算的功能。实现是针对存储结构的，指出运算的具体操作步骤。 算法：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。有5个重要特性（有穷性、确定性、可行性、输入、输出） 算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求。 时间复杂度：一般情况下，算法中基本操作的重复次数是问题规模n的某个函数f（n），算法的时间度量记作T（n）=O（f（n）），表示随着问题规模n的增大，算法执行时间增长率和f（n）的增长率相同，称为时间复杂度。 空间复杂度：S（n）定义为该算法所耗费的村粗空间，是问题规模n的函数。 第二章：线性表 线性表：具有相同数据类型的n（n>=0）个数据元素的有限序列。 线性表的顺序存储又称顺序表；链式存储又称单链表。 静态链表：借助数组来描述线性表的链式存储结构，结点也有数据域和指针域。但指针是结点的相对地址（数组下标）。需要预先分配连续的内存空间。 栈：限定在表尾进行插入或删除操作的线性表。操作端称为栈顶，后进先出 队列：一种先进先出的线性表，只允许在表的一段插入元素，另一端删除元素，在队列中允许插入的一端为队尾，允许删除的一端为队头。 串：由零个或者多个字符组成的有限序列。串中任意个连续的字符组成的子序列称为该串的子串。字符在序列中的序号为该字符的位置。 树的结点包括一个数据元素以及若干指向其子树的分支。结点拥有的子树称为结点的度。度为0的结点称为叶子或终端结点。树的度是树内个结点的度的最大值。结点的子树的根称为该结点的孩子，相应的该节点为孩子的双亲。同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点的所经分支上的所有结点。反之，以某结点为根的子树中任一结点都称为该结点的子孙。 结点的层次：从树根开始定义，根结点为第1层，它的子结点为第2层，以此类推。 树的高度或深度：树中结点的最大层数。 有序树和无序树：树中结点的子树从左到右是有次序的，不能交换，叫做有序树。反之为无序树。 1、数据 数据就是描述客观事物得符号,就是能够被计算机输入，识别，处理得各种符号，就是计算机化得信息。 2、数据项 数据不可分割得最小单位，一个元素由若干个数据项构成. 3、数据元素 它就是组成数据得基本单位,就是数据集合中得个体，在计算机程序中，通常作为一个整体进行考虑与处理。 4、数据对象 就是性质相同得数据元素得集合，就是数据得一个子集。 ５、数据处理 就是指对数据进行查找,插入，删除，合并，排序，统计以及简单计算等得操作过程。 ６、数据结构 就是研究数据元素之间抽象化得相互关系与这种关系在计算机中得存储表示（即数据得逻辑结构与物理结构），并对这种结构定义相适应得运算,设计出相应得算法,且确保经过这些运算后所得到得新结构仍然就是原来得结构类型。 7、数据类型 数据类型就是一个值得集合与定义在这个值集上得一组操作得总称。 8、抽象数据类型 就是指一个数学模型以及定义在该模型上得一组操作。抽象数据类型得定义取决于它得一组逻辑特性，而与其在计算机内部如何表示与实现无关. ９、算法 解决一个问题得方法与步骤. 1０、时间复杂度 T（N）=O(F（N）），它表示随问题规模Ｎ增大,算法执行时间增长率与Ｆ(N)得增长率相同，F(N）算法得时间复杂性。 11、原地工作 算法执行时，若额外空间相对于输入数据量来说就是常数，则称此算法为原地工作. １2、线性表 一种数据结构,就是N(N>=0)个同质元素得有限序列，除首尾元素外，每个元素有唯一得前驱与唯一得后继. 13、队列 就是一种受限线性表,就是先进先出得线性表 14、循环队列 在队列得顺序存储结构中，把存储空间得首尾逻辑上相连，构成一个环，使得存储空间上只要有空余得地址，就可以继续进行入队列操作，极大利用了物理空间.用头部与尾部两个指示器表示队列头与队列尾，插入在尾部进行，删除在头部进行。 15、单链表 每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接后继结点得地址（指针)，称为指针域，元素得存储空间可以连续，也可以就是不连续得。而数据元素之间得逻辑关系由指针 数据库： 数据库是“按照数据结构来组织、存储和管理数据的仓库”。是一个长期存储在计算机内的、有组织的、可共享的、统一管理的大量数据的集合。 简介： 定义 数据库是存放数据的仓库。它的存储空间很大，可以存放百万条、千万条、上亿条数据。但是数据库并不是随意地将数据进行存放，是有一定的规则的，否则查询的效率会很低。当今世界是一个充满着数据的互联网世界，充斥着大量的数据。即这个互联网世界就是数据世界。数据的来源有很多，比如出行记录、消费记录、浏览的网页、发送的消息等等。除了文本类型的数据，图像、音乐、声音都是数据。 数据库是一个按数据结构来存储和管理数据的计算机软件系统。数据库的概念实际包括两层意思： （1）数据库是一个实体，它是能够合理保管数据的“仓库”，用户在该“仓库”中存放要管理的事务数据，“数据”和“库”两个概念结合成为数据库。 （2）数据库是数据管理的新方法和技术，它能更合适的组织数据、更方便的维护数据、更严密的控制数据和更有效的利用数据。 发展现状 在数据库的发展历史上，数据库先后经历了层次数据库、网状数据库和关系数据库等各个阶段的发展，数据库技术在各个方面的快速 的发展。特别是关系型数据库已经成为目前数据库产品中最重要的一员，80年代以来，几乎所有的数据库厂商新出的数据库产品都支持关系型数据库，即使一些非关系数据库产品也几乎都有支持关系数据库的接口。这主要是传统的关系型数据库可以比较好的解决管理和存储关系型数据的问题。随着云计算的发展和大数据时代的到来，关系型数据库越来越无法满足需要，这主要是由于越来越多的半关系型和非关系型数据需要用数据库进行存储管理，以此同时，分布式技术等新技术的出现也对数据库的技术提出了新的要求，于是越来越多的非关系型数据库就开始出现，这类数据库与传统的关系型数据库在设计和数据结构有了很大的不同，它们更强调数据库数据的高并发读写和存储大数据，这类数据库一般被称为NoSQL（Not only SQL）数据库。而传统的关系型数据库在一些传统领域依然保持了强大的生命力。数据结构概念名词解释大全
数据结构复习要点(整理版).docx
数据结构复习提纲(整理)
数据结构概念名词解释大全复习课程
数据结构名词解释整理
数据结构名词解释整理
计算机网络名词解释
计算机网络名词解释、简答题目汇总
数据结构名词解释
地理信息系统名词解释大全(整理版本)
《数据结构》考试及答案
数据结构中的名词解释
数据结构复习题及答案
数据结构名词解释
数据结构名词解释(个人备考时结合群里那个文档和王道书自己摘录的-仅供参考)
数据结构名词解释
数据库名词解释
相关主题
文本预览