数据结构基础知识整理
数据结构基础知识整理
*名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。
*2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可
以由若干个数据项组成，数据项是具有独立含义的最小标识单位。
*3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的
逻辑结构、数据的存储结构和数据的运算三个方面的内容。
*4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数
据的存储无关，是独立于计算机的。
*5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结
构用计算机语言的实现，是依赖于计算机语言的。
*6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端
结点，并且其余每个结点只有一个直接前趋和一个直接后继。
*7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。
*8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或
多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。
*9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。
*10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。
*11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而
实现是要在存储结构上进行。
*12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关
系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。
*13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻
物理位置上来反映结点间逻辑关系。
*14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结
点的直接后继结点。头指针是它的充分必要的信息。单链表是一种单向的结构。
*15、双链表：每个结点中增加了一个prior，用来指向该点的直接前趋结点。它是一种
双向、对称的结构。
*16、循环链表：是一种首尾相接的链表。单循环链表形成一个next链环，而双循环链
表形成next链环和prior链环。
*17、存储密度：是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。顺
序表的存储密度为1，而链表的存储密度小于1。
*18、栈：只允许在一端进行插入、删除运算的线性表，称为“栈”（stack）。
*19、LIFO表：即后进先出表，修改操作按后进先出的原则进行。譬如栈就是一种LIFO 表。
*20、顺序栈：采用顺序存储结构的栈，称为顺序栈。
*21、链栈：采用链式存储结构的栈，称为链栈。
*22、队列：只允许在一端进行插入、另一端进行删除运算的线性表，称为“队列”（queue）。*23、FIFO表：即先进先出表。譬如队列就是一种FIFO表。
*24、顺序队列：采用顺序存储结构的队列，称为顺序队列。
*25、循环队列：为克服顺序队列中假上溢现象，将向量空间想象为一个首尾相接的圆环，
这种向量称为循环向量，存储在其中的队列称为循环队列。
*26、链队列：采用链式存储结构的队列，称为链队列。
*27、字符串：由零个或多个字符组成的有限序列，一般高为S=“a1，a2，…an”。
*28、空白串：由一个或多个空格组成的串称为空白串。
*29、空串：长度为零的串称为空串，它不包括任何字符。
*30、顺序串：串的顺序存储结构简称的为顺序串。
*31、链式串：串的链式存储结构简称为链式串。
*32、模式匹配：子串的定位运算又称为串的模式匹配。
*33、对称矩阵：元素满足aij=aji（0≤i,j≤n）的矩阵。
*34、三角矩阵：主对角线以上或以下的元素（不包括对角线）均为常数的矩阵。
*35、带状矩阵：所有非零元素均集中在以主对角线为中心的带状区域的矩阵。
*36、稀疏矩阵：非零元素远远少于矩阵元素的矩阵。
*37、广义表：有n个元素a1,a2…an组成的有限序列，其中n可以是原子或一个广义表。
*38、三元组表：若线性表顺序存储的每一个结点均是三元组，那么该线性表的存储结构
称为三元组表。
*39、行表：记录稀疏矩阵中每行非零元素在三元组表中的起始位置的表称为行表。
*40、内部排序：假设给定含有n个记录（R1,R2……,Rn）的文件，其相应的关键字为（K1，K2，……,Kn）,则排序是确定一个排列（P(1),P(2),……P(n)），使得（Kp(1))≤Kp(2)≤……≤Kp(n)），从而得到有序文件（R
*p(1),R p(2),……,R p(n)）。整个排序过程都在内存中进行的排序即为内部排序。
*41、稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字
在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然保持不变，则这处排序方法是稳定的。
*42、就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O(1),则称为就地排序。
*43、堆：n个关键字序列K1，K2，……,Kn，称为堆，当且仅当序列满足如下性质：Ki ≤K2i，且Ki≤K2i＋1或Ki≥K2i，且Ki≥K2i＋1。
*44、查找：即给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。
*45、动态查找表：若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表。
*46、静态查找表：若在查找的同时不对表做修改操作（如插入和删除），则相应的表称之为静态查找表。
*47、内查找：若整个查找过程都在内存中进行，则称之为内查找。
*48、外查找：若查找过程中需要访问外存，则称之为内查找。
*49、平均查找长度：ASL＝∑pici，其中n是结点的个数；pi是查找第i个结点的概率；ci是找到第i个结点所需要进行的比较次数。
*50、散列函数：在关键字和表地址之间建立的对应关系h称为散列函数。
*51、冲突：两个不同的关键字，其散列函数值相同，因而被映射到同一个表位置上的现
象称为冲突。
*52、同义词：发生冲突的两个关键字称为该散列函数的同义词。
*53、装填因子：设m和n分别表示表长和表中填入的结点数，则将ɑ=n/m定义为散列表的装填因子。
*二、填空
*1、数据的存储结构可用四种基本的存储方法表示，它们分别是顺序存储方法、链接、
索引、散列。2、数据的运算最常用的有五种，检索、插入、删除、更新、排序。
*3、一个算法的效率可分为时间和空间效率。4、数据结构按逻辑结构可分为线性结构
和非线性结构。线性结构反映结点间的逻辑关系是一对一的，非线性是多对多的。
*5、顺序表相对于链表的优点有节省存储和随机存储。6、链表相对于顺序表的优点有插入和删除操作方便。
*7、按顺序存储方法存储的线性表称为顺序表，按链式存储方法存储的线性表称为链表。
8、线性表中结点的集合是有限的，结点间的关系是一对一的。
*9、在n个结点的顺序表中插入(删除)一个结点需平均移动n/2（(n-1)/2）个结点，具体的移动次数取决于表长n和插入（删除）位置i。
*10、在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。
*11、在民个结点的单链表中要删除已知结点*p，需找到它的直接前趋结点的地址，其
时间复杂度为O(n)。
*12、在双链有中要删除已知结点*p，其时间复杂度为O(1)。
*13、在单链表中要在已知结点*p之前插入一新结点，仍需找到*p的直接前趋结点的地址，其时间复杂度为O(n)；而在双链表中，完成同样操作其时间复杂庶O(1)。
*14、在循环链表中，可根据在一结点的地址遍历整个链表，而单链表中需知道头指针才
能遍历链表。15、在栈中存取数据遵从后进先出的原则，队列中则是先进先出。
*16、栈结构中，允许插入、删除的一端称为栈顶，另一瑞称为栈底；在队列中，允许插
入的称为队尾，允许删除的一端称为队首。
*17、在有n个元素的栈中，进栈和退栈操作的复杂度为O(1)和O(1)。
*18、设长度为n的链队列用单循环链表示，若只设头指针，则入队和出队操作的时间复
杂度分别为O(n)和O(1)；若只设尾指针，则O(1)和O(1)。
*19、通常在程序中使用串可分为串变量和串常量；而串按存储方式又可分为顺序串和链
式串。20、链式存储与顺序存储的相互串匹配算法的效率相同。
*21、成功匹配的起始位置称为有效位移，所有匹配不成功称为无效位移；NaivestrMatch返回的是第1个有效位移。
*22、串的朴素匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)m,n为主串长，m为子串长。
*23、对于数组An×m，其元素aij按行优先与列优先存储的地址之差为(i-1)(n-1)-(j-1)(m-1).(两次存储的LOC(a11)相同.)
*24、特殊矩阵是指非零或零元素分布有一定规律的矩阵。25、多维数组的存储方式有
顺序和链式。26、递归表是指允许递归的广义表，纯表是指与树对应的广义表。
*27、任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可是广义表而表
尾必定是广义表。
*28、表的长度是指广义表元素的个数，表的深度是指广义表展开后扩号的层数。29、树中结点的最大层次称为树的深度（高度）。
*30、若有一棵二叉排序树，则按照中序遍历顺序将产生一个有序序列。31、由一棵二叉树的前序序列和中序可惟一确定这棵二叉树。
*32、将一棵树转换成一棵二叉树后，二叉树的根结点没有右子树。33、图有邻接矩阵、邻接表等存储结构，遍历图有深度优先（DFT）和广度优先（BFT）等方法。
*34、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。35、如果n个顶点的图是一个环，则它有n个生成树。
*36、n个顶点e条边的图用邻接矩阵（邻接表）存储，则空间复杂度为O(n2)（O(n+e)）。
37、稀疏（稠密）图G，采用邻接表（邻接矩阵）存储较省空间。
*38、图的逆邻接表存储结构只适用于有向图。39、已知一个图的邻接矩阵表示，删除
所有从第i个顶点出发的边的方法是将邻接矩阵的第i行全置0、
*40、n个顶点e条边的图用邻接矩阵（邻接表）存储，深度优先遍历的时间复杂度为O(n2)（O(n+e)）。（广度优先时间复杂度同上。）
*41、图的BFS生成树的树高比DFS生成树的树高小或相等。
*42、用Prim（Kruskal）算法求具有n个顶点e条边的图的最小生成树的时间复杂度为
O(n2)（O(elog2e)）。
*43、稀疏（稠密）图G的最小生成树，最好用Kruskal（Prim）算法求解。
*44、用迪杰斯特拉（Dijkstra）算法求n个顶点e条边的图中的某一顶点到其余各顶点
间最短路径的时间复杂度为O(n2)。
*45、用Dijkstra算法求某一顶点到其余各顶点间最短路径是按路径长度递增的次序来
得到最短路径的。
*46、拓扑排序算法是通过重复选择具有0个前趋顶点的过程来完成的。47、拓扑排序输出的顶点数小于有向的顶点数，刚该图一定存在环。
*48、对n个顶点e条边的图进行拓扑排序，算法的时间复杂度为O(n+e)。
*49、在插入和选择排序中，若初始数据基本正序，则选用插入；若初始反序，则选用选
择。
*50、在堆排序和快速排序中，初始记录接近正序或反序，则用堆，初始无序则用快速。
*51、在堆、快速和归并排序中，只考虑存储空间，先选堆，其次快速，最后并归；只从
排序结果的稳定性考虑，则先并归；只从平均情况下最快考虑，先选快速；只从最坏考虑并
要节省内在，则先堆。
*52、大多数排序算法都有两个基本操作：比较两上关键字的大小和改变指向记录的指针
或移动记录本身。
*53、散列法存储的基本思想是由关键字的值决定数据的存储地址。54、散列表的查找
效率主要取决于散列表造表是时选取的散列函数和处理的方法。
*55、当所有结点的权值都相等时，用这些结点构造的二叉树的特点是只有右子树。56、m阶B-树每一个结点的子树都小于或等于m.
*57、m阶B-树具有k个子树的非叶子结点含有k－1个关键字。58、m阶B-树的任何一个结点的左右子树的高度都相等。
*59、中序遍历二叉树排序树的结点就可以得到排好序的结点序列。60、对两棵具有相
同关键字集合而形状不同的二叉排序树，中序遍历它们得到的序列的顺序是一样的。
*61、B－和B＋树都旨在建立起文件中全部记录的索引，以便随访问。在B－树中记录地址存于它的关键码所在的结点中；在B＋树中记录地址存于叶结点中各关键码之下。
*62、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。
*63、对于长度为n的线性表，若进行顺序查找，则时间复杂度为O(n)；若采用折半查找，则O(log2n)；若用分块查找则O(sprt(n))。
*64、在散列存储中，装填因子ɑ的值越大，则存取元素时发生冲突的可能性越大。反之
则越小。
*65、假设在有序线生表a[20]上进行二分查找，则比较一次查找的结点数为1；比较两次查找成功的结点数为2；比较四次查找成功的结点数为8；平均查找长度为 3.7.
*66、在文件中，能唯一标识记录的数据项，称为主关键字，否则称为次关键字。67、文件有四种基本的组织方式：顺序、索引、散列和链组织。
*68、文件有四种常用的组织：顺序、索引、散列和多关键字文件。69、评价一个文件组织的效率从两方面考察：执行文件所花费的时间和文件组织所需的存储空间。
*70、衡量文件操作质量的重要标志是检索功能的多少和速度的快慢。71、索引文件由索引表和主文件组成。在存储器上分两个区：索引区和数据区。
*72、在索引非顺序文件中采用动态索引时，为减少访问外存的次数，应尽量缩减索引表
的深度。
*73、在索引文件中，评价外存索引表的查找性能，主要看访问外存的次数，即索引表的
深度。
*74、常用的索引顺序文件有ISAM（索引顺序存取法）和VSAM（虚拟存储存取方法）。
*75、ISAM是一种专为磁盘存取文件设计的文件组织方式，采用静态索引结构。由多级
主索引、柱面索引、磁道索引和主文件组成。
*76、VSAM是一种索引顺序文件的组织方式，采用B+树作为动态索引结构。由索引集、
顺序集和数据集组成。
*77、多重表文件是将索引方法和链接方法结合的一种组织方式。
*78、在双链表中，存储一个结点有三个域，一个数据域；另两个是指针域，分别指向该
结点的直接后继和直接前趋。
*79、对于一棵满二叉树，若有m个叶子，则结点数为2m-1；若满二叉树的结点数为n，则其高度为log2(n+1).
*80、森林的后序遍历序列正是相应二叉树的中序遍历序列，森林的先序遍历序列正是相
应二叉树的先序遍历序列。
*81、在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结
点编号。设根结点编号为1。若编号为i的结点，有左孩子，那么其右孩子的编号为2i＋1；若编号为i的结点，有父结点，那么其父结点编号为「i/2」.
*82、采用折半查找法进行查找的数据文件应为有序表和顺序存储结构。83、线性表按存储方式的不同，可分为顺序表、链表和散列表三种。
*84、在有n个结点的二叉链表中，空指针域有n+1个，利用这些空指针域，存放指向结
点在中序次序下的前趋或后继的指针，这种附加的指针称为线索。
*85、由一棵二叉树的前序序列和中序序列可确定一棵二叉树。
*86、在含胡n个结点的二叉排序树上查找某结点时，其平均查找长度ASL的范围估计是从log2n至（n+1）/2.
*87、顺序表的存储密度为1，而链表的存储密度小于 1.
*88、在上三角矩阵中，它的下三角（不包括对角线）中的元素均为常数C。上三角矩阵中的重复元素C可共享一个存储空间，其余的元素正好有n(n+1)/2个。
*89、对于一棵有n个结点的4度树，每个结点中有4个指针，指向子结点，则树中指向子
结点的指针有n-1个，空指针有3n+1个。
*三、简答题
*1、简述线性结构与非线性结构的不同点。
*答：线性结构的逻辑特征是除开始结点和终端结点外，其余每个结点只有一个直接前趋
和一个直接后继，即结点间存在一对一的关系；
*而非线性结构的逻辑特征是一个结点可以有多个直接前趋和直接后继，即结点间存在多对多的关系。
*2、简述数据的存储四种常用存储方法
*答：顺序存储方法：把逻辑上相邻的结点存储在物理位置相邻的存储单元里，这样结点
间的逻辑关系由存储单元的邻接关系来体现。
*链接存储方法：除存储结点外，还要由附加的指针字段来表示结点间的逻辑关系。
*索引存储方法：在存储结点的同时，还建立附加的索引表。
*散列存储方法：根据结点的关键字直接计算出该结点的存储地址。
*3、简述稠密索引与稀疏索引的不同点答：稠密索引：每个结点在索引表中都有一个索
引项。
*稀疏索引：一组结点在索引表中只对应一个索引项。
*4、简述算法复杂度（效率分析）的评价方法。
*答：算法复杂度可分为时间复杂度和空间复杂度。时间复杂度是该算法所破费的时间，
可用该算法中所有语句的频度之和来计算。
*由于评价一个算法的时间性能时，主要标准是算法时间复杂度的数量级，即算的渐近时间复杂度，它一般是算法中频度最大的语句的频度的数量级。
*空间复杂度是该算法所耗费的存储空间，也是总是规模n的函数，同样用渐近空间复杂
度作为空间复杂度。
*5、简述线性表的存储结构及各自的长处。
*答：线性表的两种存储结构：顺序存储结构—顺序表、链式存储结构—链表。
*顺序表用结点物理位置的相邻性来反映结点间的逻辑关系，其优点是：节省存储，随机
存取，当表长变化较小，主要操作是进行查找，宜采用顺序表。
*链表用附加的指针来反映结点间经，当表长变化较大，主要操作是进行插入和删除，宜
采用链表。
*6、简述头指针、头结点的作用。
*答：头指针指向链表的“第一个结点”（头结点，或无头结点时的开始结点）。头结点不是线性表中的结点，是在链表中虚设的一个结点。
*设置头结点有两个好处：无需对链表中第一个位置上的操作进行特殊处理，对空表和非空表的处理可以统一起来。
*7、为什么在单循环链表中设置尾指针比设置头指针更好？
*答：由于对表的操作常常在表的两端进行，所以对单循环链表，当知道尾指针rear后，其另一端的头指针是rear→next→next(表中带头结点)。这将给操作带来很多方便。
*8、线性表、栈、队列有异同？
*答：栈和队列是受限的线性表，对插入、删除运算加以限制。
*栈是只允许在一端进行插入、删除运算，因而是后进先出表；
*而队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表。
*9、在顺序栈中简述进栈、退栈操作的过程。
*答：顺序栈的进栈、通栈操作均在栈顶进行，栈顶指针指向栈顶元素处。进栈时，栈顶
指针先加1，再送值到栈顶指针指向处。退栈时，先从栈顶指针指向处取值，栈顶指针再减
1.
*10、在队列中简述入队、出队操作的过程（用“少和一个元素空间”的方法）。
*答：在循环队列中，设队头指针指向队头元素，队尾指针指向队尾元素后的一个空闲元
素。
*在队列不满时，可执行入队操作，此时先送值到队尾指针指向的空闲元素，队尾指针再
加1（要取模）。
*在队列不空时，可执行出队操作，此时先从队头指针指向处取值，队头指针再加1（要取模）。
*11、在什么情况下，才能使用栈、队列等数据结构？
*答：栈结构主要应用在三方面：①算术表达式的求值②子程序的调用与返回③递归函数
的求值。
*队列结构主要应用在需要“排除”的事件中，例如OS中的作业调度等。
*12、试举例说明链式串在哪些操作上比顺序串有更高的效率。
*答：链式存储在串的插入和删除操作上效率较高，因为它只需做查找工作，而不需移动
后面的元素。
*13、在执行某种排序算法的过程中，出现了排序码朝着最终排序序列相反的方向移动，
从而认为该排序算法是稳定的，这种说法对吗？为什么？
*答：这种说法不对。因为排序的不稳定性是指排序前两个排序码相同的元素的相对次序
经过排序后发生了变化，而题中未涉及到幸免于难
*的相对次序（特别是相同排序码的元素）的改变，只有移动方向，所以这种说法不对。
*14、选择排序算法是否稳定？为什么？
*答：选择排序不稳定。由于选择排序的原则是从剩余的记录中找最小（或最大）都并与
第i个记录交换，一旦交换到某个位置以后再也不动了，
*这种算法就不能保证具有相同排序码的记录原来所具有的相对次序，即原来排在前面的
经过后有可能排在某一个具有相同码的记录的后面。
*例如排序码43，89，21，43，28，15，经过5遍排序后次序为15，21，28，43，43，89.排序前每一个位置上的排序码43现在位于第5个位置上。
*15、在快速排序算法中，能否用队列代替栈来保存子文件首、尾记录的地址（下标）？
*答：保存子文件首、尾记录的地址（下标），其目的是为了处理某个子文件时，能知道
其首、尾记录的地址（下标），
*这才能地该子文件进行快速排序（排序过程又可能出现新的子文件），但与处理子文件
的先后没有什么关系，仅仅起存储作用，因此，用队列也可起到栈的作用，故可取而代之。
*16、设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素，在快速
排序、堆排序、归并排序、基数排序和Shell排序中采用哪种方法最好？为什么？
*答：以上几种算法中，快速排序、归并排序、基数排序和Shell排序都是在排序结束后
才能确定数据元素的全部顺序，
*而无法知道排序过程中部分元素的有序性。堆排序则每次输出一个最大（或最小）的元
素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大的（或最小）。
*根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的。
*17、将十进制的关键字用二进制表示，对基数排序所需的计算时间和附设空间分别有何
影响？各是多少？
*答：因为基数排序所需的计算时间不仅与文件的大小n有关，还与关键字的位数、关键
字基数有关。
*设关键字的基数为r(十进制基数为10，二进制基数为2)，为建立r个空队列所需的时间
为O(r)。
*把n个记录分放到各个人列中并重新收集起来所需的时间为O(n)，因此一遍排序所需的
时间复杂度为O(n+r)。
*若每个关键字有d位，则总共要d遍排序，所以基数排序的时间复杂度为O(d(n+r))。由于关键字的位数d直接与基数r以及最大关键字的值有关，因此不同的r和关键字将需要不
同的时间。
*18、有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问什么排序方法时间复杂性最佳？为什么？
*答：采用基数排序方法时间复杂性最佳。因为这里英文单词的长度相等，且英文单词是
由26个字母组成，满足进行基数排序的条件，
*另外，依题意，m< *19、试述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求，并求其等 概率时查找成功的平均查找长度。 *答：顺序查找法：表中元素可以任意存放。查找成功的平均查找长度为（n+1）/2. *折半查找：表中元素必须以关键字的值递增或递减地存放且只能以顺序表存放。查找成功的平均查找长度为㏒2（n+1）-1。 *分块查找：表中每块内的元素可以任意存放，但块与块之间必须按关键字的大小递增或 递减在存放， *即前一块仙所有元素的关键字不能大（或小）于后一块内任意一个元素的关键字。若用 顺序查找确定所在块，平均查找长度为1/2(n/s+s)+1；若用折半查找确定所在块，平均 查找长度为㏒2（n/s+1）+s/2. *20、假定散列函数可映射的地址空间的长度为1000，如果散列函数只是简单地抽取关 键字中间的3位作为散列函数的映射地址，会出现什么问题？ *答：由于这种简单的抽取方法，使得关键字两端的数字在产生散列函数值时不起作用， 只简单地依赖于中间的个别数字，这就增加了产生冲突的可能性，而这正是散列查找方法所 不希望的。 *21、假定有n个关键字，它们具有相同的散列函数值，用线性探测方法把这n个关键字存入到散列地址中间要做多少次探测？ *答：由于线性探测的查找次数主要取决于装填因子ɑ，即与散列地址地占用情况有关。 假定初始时散列地址为空， *则在此情况下连续装入n个具有相同的散列函数值的关键字所需的总探测次数为1＋2＋……＋n=n(n+1)/2。 *22、已知一个含有100个记录的表，关键字为中国姓氏的拼音。请给出此表的一个散列 表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过 3. *答：散列查找的主要取决于处理冲突的方法，而且直接与散列表的装填因子ɑ有关。ɑ越 小，表中的记录数越小或表越长， *发生冲突的可能性就越小，查找效率也越高；反之，ɑ越大，表中的记录密度越高，发 生冲突的可能性就越大，查找时间也越长。 *若采用二次探测再散列，这样在等概率情况下查找成功的平均查找长度为Sn≈-1/ɑ㏑(1-ɑ)，根据题目要求有-1/ɑ㏑(1-ɑ)<3，即-㏑(1-ɑ)<3ɑ， *可求得ɑ＝0.8.因为ɑ＝0.8，表中含有100个记录，由此可推得散列表长为100/0.8 ＝125.根据关键字的特性和表的长度选取合适的散列函数，例如随机数法。 *通常当关键字长度不等时采用此法构造散列函数较恰当。 *23、DB中研究的文件与OS中研究的文件有什么区别？ *答:OS中研究的文件是一维的无结构连续字符序列（即“流式文件”）。DB中研究的文件是带有结构的记录集合，每个记录可由若干个数据项构成（即“记录式文件”）。 *24、文件结构就包括哪三个方面的内容？ *答：逻辑结构、存储结构及在文件上的各种操作三方面。文件的操作是定义在逻辑结构 上的，但操作的具体实现要在存储结构上进行。 *25、文件上的检索操作有哪四类询问方式？并做简单的解释答：文件上的检索操作， 按检索条件的不同可分为四种询问：简单询问、范围、函数、布尔询问。 *26、顺序文件有哪些查找方法？答：磁带上的文件都是顺序文件，只能采用“顺序查 找法”。 *磁盘上的顺序文件，有多种查找方法，譬如顺序查找法、分块查找法、二分查找法、插 值查找法、跳步查找法等。 *27、试述索引非顺序文件的结构。 *答：索引非顺序文件中，主文件中记录未按主键值排序，必须为每个记录建立一个索引 项（即建立“稠密索引”）。 *索引非顺序文件在存储器上分为两个区：索引区和数据区，前者存放索引表（按主键值 排序），后者存放主文件。 *28、试述散列文件的基本结构。 *答：散列文件由“基桶”和“溢出桶”两部分组成。每个基桶放m个记录，溢出的记录 放到溢出桶中。 *溢出桶和基桶大小相同，相互之间用指针相链接。同一散列地址的溢出桶和基桶，最好 在同一柱面，以提高查询速度。 *29、试述多重表文件的基本结构。 *答：多重表文件是将索引方法和链接方法相结合的一种组织方式。在索引表中，对每个 需要查询的次键值建立一个索引，包括三项：次键值、主文件中该次键值记录的链表的头指针、链长。在主文件中将具有同一次键值的记录链成一个链表。 *30、试述倒排文件的结构。并指出倒排表中列出亡灵的物理地址与列出记录的主键值这 两种方式的差异。 *答：倒排文件由倒排表和主文件一起构成。倒排表即索引表，若列出记录的地址，则其 优点是存取速度快，但主文件中记录被“拴”住了，维护复杂。若列出记录的主键值，则倒 排表与主文件具有相对独立性，但存取速度要慢些。 *31、试述索引顺序文件中，ISAM文件与VSAM文件的区别。 *答：ISAM文件：索引顺序存取方式，静态索引结构，多级索引机制，文件结构由四部 分组成（多级主索引、柱面索引、磁道索引、主文件），应周期性整理ISAM文件。 *VSAM文件：虚拟存储存取方式，动态索引结构，B++树机制，文件结构由三部分组成（索引集、顺序集、数据集），永远不必对文件进行再组织。 * 数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 数据结构基础知识整理 *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可 以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的 逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数 据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结 构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端 结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或 多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而 实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关 系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻 物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结 /** *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结点的直接后继结点。头指针是它的充分必要的信息。单链表是一种单向的结构。 *15、双链表：每个结点中增加了一个prior，用来指向该点的直接前趋结点。它是一种双向、对称的结构。 *16、循环链表：是一种首尾相接的链表。单循环链表形成一个next链环，而双循环链表形成next链环和prior链环。 *17、存储密度：是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。顺序表的存储密度为1，而链表的存储密度小于1。 *18、栈：只允许在一端进行插入、删除运算的线性表，称为“栈”（stack）。 *19、LIFO表：即后进先出表，修改操作按后进先出的原则进行。譬如栈就是一种LIFO 表。 *20、顺序栈：采用顺序存储结构的栈，称为顺序栈。 *21、链栈：采用链式存储结构的栈，称为链栈。 *22、队列：只允许在一端进行插入、另一端进行删除运算的线性表，称为“队列”（queue）。*23、FIFO表：即先进先出表。譬如队列就是一种FIFO表。 *24、顺序队列：采用顺序存储结构的队列，称为顺序队列。 *25、循环队列：为克服顺序队列中假上溢现象，将向量空间想象为一个首尾相接的圆环， 数据结构基本知识 数据（Data） 数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。随着计算机应用领域的扩大，数据的范畴包括： 整数、实数、字符串、图像和声音等。 数据元素（Data Element） 数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。 一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。 数据项是具有独立含义的最小标识单位。 数据结构（Data Structure） 数据结构指的是数据之间的相互关系，即数据的组织形式。 1．数据结构一般包括以下三方面内容： ①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）； 数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 ②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）； 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。 ③数据的运算，即对数据施加的操作。 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的 检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。 为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。 【例1．1】学生成绩表，见下表。 注意：在表中指出数据元素、数据项、开始结点和终端结点等概念 （1）逻辑结构 表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。 表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"马二"所在结点的直接前趋结点和直接后继结点分别是"丁一"和"张三"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。 小学语文各年级知识结构图 一年级 一、拼音 1.声母 2.韵母 （1）。单韵母 （2）复韵母 （3）前鼻音韵母 （4）后鼻音韵母 （5）特殊韵母 3.整体认读音节 4.大小字母 5声调 二、字 1.笔顺 2.识字 a。形近字 b.会意字 c．形声字 d．多音字 e．多义字 3.生字组词 1.反义词 2.量词 3.叠词（AABB式） 三、句 1．看拼音写句子 2.关联词 ……因为……所以…..、……一边……一边……3造句 …….像……、……..从……、……来……. 3.疑问句 四段 1.认识自然段. 2.在自然段前面加序号 五、口语交际 1看图 2.按顺序说 a.从上到下 b.从左到右 c.从中间到两边 d.从景到人 六积累 2.对子 3.儿童诗歌 4.谚语 二年级一字 1.识字 a。形近字 b.会意字 c．形声字 d．多音字 e．多义字 2.熟练识字方法 3.生字组词 二词 1.写 a看拼音写词语 b多音字组词 2词语搭配 3积累词语 a.四字词语 b.成语 三句 .- 1认识句子 a比喻句 b拟人句 c.反问句 3.写句子 a.运用标点符号写句子（逗号、句号、问号、感叹号。） b.联系上下文写句子 四段 1.背诵片段 2.理解段落内容 五口语交际 1制定计划 2.听别人讲 3.学会转述 六习作 1.培养写作兴趣 2.学写 把看到的，听到的，想到的记录下来 3.拓展 学写日记 七积累 1.儿歌 2.谚语 3.古典诗词 4.名言警句 三年级 一、字 1.学写钢笔字 a.练字必须有正确的姿势 b.练字必须有正确的执笔和运笔方法 c. 注意钢笔字的笔法 2.识字 a．形近字 b．多音字 3.生字组词 二词 1写 a看拼音写词语 b生字组词 c多音字组词 d近义词反义词 2.积累词语 a.成语 b.ABB式词语 初中语文知识结构图 初中语文知识结构图 3、汉字1、字音 2、字形 4、含义 5、色彩 9、词语6、近义词辨析 7、熟语 8、关联词语 12、标点符号10、点号 11、误用辨析 27、基础知识15、修辞13、常见修辞格 14、辞格辨 16、词类 20、语法17、短语 47 18、复句 初19、辨析修改病句 中21、作家作品语24、文学文化常识22、名篇名句文23、文化常识 26、语言表达——25、简明、连贯、得体28、常见实词 45、知识体系31、文章内容的归纳，中心的概括29、常见虚词 34、古代诗文阅读32、实词、虚词30、一词多义 33、文章内容的理解（翻译、断句） 35、文体知识 36、依据作品内容进行的合理推断 37、作文作品语言、表达技巧和形象的鉴赏 38、文学作品思想内容、作者态度的评价 44、现代文阅读39、重要句子的理解和解释 40、重点词语的理解 41、文中信息的分析和筛选 42、内容的归纳，中心的概括 43、结构的分析，思路的把握 46、中考复习 初中数学知识结构图 1、有理数（正数与负数） 2、数轴 6、有理数的概念3、相反数 4、绝对值 5、有理数从大到小的比较 7、有理数的加法、加法运算律 17、有理数8、有理数的减法 9、有理数的加减混合运算 10、有理数的乘法、乘法运算律 16、有理数的运算11、有理数的除法、倒数 12、有理数的乘方 13、有理数的混合运算 21、代数式 14、科学记数法、近似 数与有效数字 22、列代数式15、用计算器进行简单的数的运算 23、代数式的值18、单项式 27、整式的加减20、整式的概念19、多项式 24、合并同类项 25、去括号与添括号 26、整式的加减法 28、等式及其基本性质 29、方程和方程的解、解方程 198 32、一元一次方程30、一元一次方程及其解法 初31、一元一次方程的应用33、代入（消元）法 中35、二元一次方程组的解法34、加减（消元）法 数193 36、相关概念及性质 学数39、二元一次方程组37、三元一次方程组及其解法举例与38、一元方程组的应用40、一元一次不等式及其解法 代45、一元一次不等式43、一元一次不等式41、不等式的解集 数和一元一次不等式组44、一元一次不等式组42、不等式和它的基本性质 46、同底数幂的乘法、单项式的乘法 47、幂的乘方、积的乘方 51、整式的乘法48、单项式与多项式相乘 49、多项式的乘法 56、整式的乘除50、平方差与完全平方公式 52、多项式除以单项式 55、整式的除法53、单项式除以单项式 54、同底数幂的除法 57、提取公因式法 61、方法58、运用公式法 63、因式分解59、分组分解法 62、意义60、其他分解法66、含字母系数的一元 65、分式的乘除法——64、分式的乘除运算一次方 数据结构考研真题及知识点解析 考察目标 1. 理解数据结构的基本概念、基本原理和基本方法。 2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3. 能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C、C++或Java语言设计与实现算法的能力。 第2章线性表 一、考研知识点 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储 2.链式存储 3.线性表的应用 二、考研真题 （一）选择题 近两年第2章没有考选择题，因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，而且可以和第3章、第9章和第10章的内容结合来出题。 1．（11年）设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。 x=2; while(x 1钢结构施工图的基本知识 1.1钢结构施工详图 1.1.1.设计图和施工详图的区别 1.1.3.施工详图编制内容 (1)图纸目录 (2)钢结构设计总说明。 应根据设计图总说明编制，内容一般应有设计依据、设计荷载、工程概况和对材料、焊接、焊接质量等级、高强度螺栓摩擦面抗滑移系数、 预拉力、构件加工、预装、除锈与涂装等施工要求及注意事项等。(3)布置图。 主要供现场安装用。依据钢结构设计图，以同一类构件系统（如屋盖、刚架、吊车梁、平台等）为绘制对象，绘制本系统构件的屏幕布置 和剖面布置，并对所有的构件编号；布置图尺寸应标明各构件的定位尺 寸、轴线关系、标高以及构件表、设计说明等。 (4)构件详图。 按设计图及布置图中的构件编制，主要供构件加工厂加工并组装构件用，也是构件出厂运输的构件单元图，绘制时应按主要表示面绘制每 一个构件的图形零配件及组装关系，并对每一构件中的零件编号，编制 各构件的材料表和本图构件的加工说明等。绘制桁架式构件时，应放大 样确定构件端部尺寸和节点板尺寸。 (5)安装节点图。 详图中一般不再绘制节点详图，仅当构件详图无法清楚表示构件相互连接处的构造关系时，可绘制相关的节点图。 1.1.4.施工详图绘制的基本规定 (1)线型分类表 (2)尺寸线的标注 详图的尺寸由尺寸线、尺寸界线、尺寸起止点组成；尺寸单位除标高以m为单位外，其余尺寸均以mm为单位，且尺寸标注时不再书写单 位。一个构件的尺寸线一般为三道，由内向外依次为：加工尺寸线、装 配尺寸线、安装尺寸线。当构件图形相同，仅零件布置或构件长度不同 时，可以一个构件图形及多道尺寸线表示A、B、C！……等多个构件， 但最多不超过5个。 1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树 问题背景： 假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/ 2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢 分析问题（建立模型）： 可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。即无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。 图G5无向连通图的生成树为(a)、(b)和(c)图所示： G5 G5的三棵生成树： 可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。 最小生成树的定义： 如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。 最小生成树的性质： 假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u, v）是个一条具有最小权值(代价)的边，其中， 则必存在一棵包含边（u,v）的最小生成树。 解决方案： 两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。他们都利用了最小生成树的性质 1.普里姆（Prim）算法：有线到点，适合边稠密。时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。设置两个新的集合U和T，其中 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基 本单位，在计算机程序常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数据 项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入 5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 数据结构与方法 1、算法的基本特征：可行性、确定性、有穷性、拥有足够的情报 2、算法的基本运算和操作：算术运算、逻辑运算、关系运算、数据传输 3、算法的基本控制结构：顺序结构、选择结构、循环（重复）结构 4、算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法 5、算法的复杂度主要包括：时间复杂度、空间复杂度 6、算法的时间复杂度：指执行算法所需要的计算工作量 7、算法的空间复杂度：指执行这个算法所需要的内存空间 8、数据结构主要研究：数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算 9、数据结构研究的目的：提高数据处理的效率 10、数据处理的效率：数据处理的速度、减少处理过程中占用计算机的存储空间 11、数据处理：指对数据集合中的各元素以各种方式进行运算 12、数据元素：指在数据处理中，每一个需要处理的对象都可以抽象成数据元素 13、数据结构：指反映数据元素之间关系的数据元素集合的表示 14、数据的逻辑结构：指反映数据元素之间逻辑关系的数据结构，两要素：数据元素的集合、数据元素在集合上的关系 15、数据的存储结构：指数据的逻辑结构在计算机存储空间的存放形式，常用的存储结构有：顺序、链接、索引等 16、数据结构的图形表示中每个元素加上方框成为结点 17、数据结构一般分为：线性结构、非线性结构 18、线性结构满足：有且仅有一个根结点、每个结点最多有一个前件和后件、在一个线性结构中插入和删除任何一个结点后还是线性结构 19、线性表定义：线性表是由n个数据元素a1、a2、a3、a4……an组成的一个有限序列，表中每一个数据元素，除了第一个外，有且仅有一个前件，除了最后一个外，有且仅有一个后件 20、非线性表的特征：有且只有一个根节点a1，它无前件、有且只有一个终结点an，它无后件、除了第一个和最后一个外，其他所有结点只有一个前件和一个后件 21、线性表的长度：线性表中的结点的个数n成为线性表的长度，当n=0时，成为空表 22、线性表的顺序存储的特点：所有元素所占的存储空间是连续的、各数据元素在存储空间中是按逻辑顺序一次存放的 23、线性表的随机存取地址计算公式：ADD(ai)=ADD(a1)+(i-1)*k 24、线性表的主要操作：插入、删除、查找、排序、分解、合并、复制、逆转 25、栈的定义：栈是限定在一端进行插入和删除的线性表，它按照“先进后出，后进先出”的原则组织数据 26、栈的顺序存储：在程序设计语言中，一般一维数组S（1：m）作为栈的顺序存储空间，其中m为栈的最大容量 27、栈的基本运算：入栈、退栈、读栈顶元素 28、入栈运算：首先将栈顶指针（top）加1，然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，称为“上溢”错误 29、退栈运算：首先将栈顶元素赋给一个指定的变量，然后将栈顶指针（top）减1。当栈顶指针为0时，说明栈空，成为“下溢”错误 30、队列的定义：队列是指允许在一端进行插入，而在另一端进行删除的线性表，它按照“先进先出”的原则组织数据 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 数据结构试卷（一） 一、单选题（每题 2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)， A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联 系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素 放A[1]中，现进行二分查找，则查找A［3］的比较序列的下 标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致 为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储 时，若选用H（K）=K %9作为散列函数，则散列地址为1的元 素有（）个， A．1 B．2 C．3 D．4 在启动WindowsXP时按F8键选择带命令行的安全模式，使用net命令可以对用户身份进行操作。具体步骤如下：使用命令“net user abcd/add”添加一名为abcd的用户，使用命“net localgroup administrators abcd/add”将用户abcd提升为管理员，重新启动电脑，用abcd身份登录，最后对遗忘密码的用户进行密码修改即可。 数据结构里'malloc'什么意思 2008-3-8 20:31 提问者：LoulouBlue|浏览次数：1216次 我用VC6.0编译时出错:'malloc' : undeclared identifier 还有exit为什么也是未定义呢? 2008-3-9 08:38 最佳答案 malloc 是动态分配存储空间的，须在 malloc是向系统请求分配内存空间 sizeof（LNode）是要分配内存空间的大小 （LinkList*）表示请求的内存是用来装LinkList这种类型的指针数据的 数据结构中status 是什么意思？ 2011-9-25 20:13 提问者：whataword|悬赏分：5|浏览次数：342次 2011-9-25 20:57 最佳答案 状态函数，以Status开头的函数返回值对应课本上给出的（实际开发中是自己定义的）值，ERROR,OVERFLOAT,TRUE,FALSE... DataType是什么意思 DataType顾名思义就是数据类型 数据结构用的不算是C语言而是类C 那么要使用C语言正确编译的话我们就需要把这些映射成C语言的相应类型 这里DataType就映射成int整形/批：/这个书上P22说可以是任何相应的数据类型int.char 代码为typedef DataType int; 就是把DataType和int等价 在后面的 DataType a; 也就是相当于int a; 结构体定义typedef struct 用法详解和用法小结 typedef是类型定义的意思。typedef struct 是为了使用这个结构体方便。 具体区别在于: 若struct node {}这样来定义结构体的话。在申请node 的变量时，需要这样写，struct node n; 若用typedef，可以这样写，typedef struct node{}NODE; 。在申请变量时就可以这样写，NODE n; 区别就在于使用时，是否可以省去struct这个关键字。 第三篇：struct和typedef struct 分三块来讲述： 1 首先： 在C中定义一个结构体类型要用typedef: typedef struct Student 第1章绪论 内容提要： ◆数据结构研究的内容。 针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。 数据结构涵盖的内容： ◆基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。 数据——所有能被计算机识别、存储和处理的符号的集合。 数据元素——是数据的基本单位，具有完整确定的实际意义。 数据对象——具有相同性质的数据元素的集合，是数据的一个子集。 数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为： Data_Structure=（D, R） 数据类型——是一个值的集合和定义在该值上的一组操作的总称。 抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作， 它由基本的数据类型构成。 ◆算法的定义及五个特征。 算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 算法的基本特性：输入、输出、有穷性、确定性、可行性 ◆算法设计要求。 ①正确性、②可读性、③健壮性、④效率与低存储量需求 ◆算法分析。 时间复杂度、空间复杂度、稳定性 学习重点： ◆数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。 ◆用计算语句频度来估算算法的时间复杂度。 第二章线性表 内容提要： ◆线性表的逻辑结构定义，对线性表定义的操作。 线性表的定义：用数据元素的有限序列表示 ◆线性表的存储结构：顺序存储结构和链式存储结构。 顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。 链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。通过指针来实现！ ◆线性表的操作在两种存储结构中的实现。 数据结构的基本运算：修改、插入、删除、查找、排序 1)修改——通过数组的下标便可访问某个特定元素并修改之。 核心语句:V[i]=x; 顺序表修改操作的时间效率是O(1) 2) 插入——在线性表的第i个位置前插入一个元素 实现步骤： ①将第n至第i 位的元素向后移动一个位置； ②将要插入的元素写到第i个位置； ③表长加1。 注意：事先应判断: 插入位置i 是否合法?表是否已满? 应当符合条件：1≤i≤n+1 或i=[1, n+1] 核心语句： for (j=n; j>=i; j--) a[j+1]=a[ j ]; a[ i ]=x; n++; 插入时的平均移动次数为：n(n+1)/2÷（n+1）＝n/2≈O(n) 3) 删除——删除线性表的第i个位置上的元素 实现步骤： ①将第i+1 至第n 位的元素向前移动一个位置； ②表长减1。 注意：事先需要判断，删除位置i 是否合法? 应当符合条件：1≤i≤n 或i=[1, n] 核心语句： for ( j=i+1; j<=n; j++ ) a[j-1]=a[j]; n--; 建筑结构施工图识图入门总结，很详细 知识，力求达到以下四个方面能力： 1、理解建筑施工图的成图原理和制图标准； 2、看懂房屋的组成和各部分的材料、做法，能够看懂一般建筑工程的主要施工图纸； 3、能够根据施工图纸进行建筑面积和一般工程量的计算以及常用构件数量的统计； 4、能够发现图纸中较明显的错误、遗漏和图样之间相互矛盾的地方。 第一节建筑工程施工图的组成 各专业施工图的内容 1、总图：建筑场地范围内建筑物的位置、形状和尺寸，道路、绿化及各种室外管线的布置等。 2、建筑专业图：建筑平面图、立面图、剖面图、各种详图及门窗表、材料做法表。 3、结构专业图：基础图、各层顶板的平面、剖面、各种构件详图，构件数量表及设计说明。 4、设备专业图：包括给水、排水、采暖、通风各系统的平面图、轴测图和各种详图。 5、电气专业图：包括照明、动力和弱电的系统图、平面图及详图等。 第二节建筑工程图的成图原理 一、投影的概念 用一组假想的投射线把物体的形状投到一个平面上，就可以得到一个图形，称为投影法。 二、投影的种类 1、中心投影：投影线由一点放射出来投射到物体上，这种作图方法称为中心投影法。 2、平行投影：投影线呈相互平行状投射到物体上，称平行投影。 （1）正投影：使投影线垂直于投影面时，并且使物体的一个面也垂直于投影线。 （2）斜投影：当投影线倾斜于投影面时，所作出的投影。 三、物体的三面正投影图 1、三面正投影体系的形成 （1）将物体放在三个相互垂直的投影面间； （2）用三组垂直于投影面的投影线作投影； （3）在三个投影面上得到三个正投影图。 2、三面正投影体系的展开 （1）正立投影面不动； （2）水平投影面向下转动90°； （3）侧立投影面向右后方转动90°。 3、三面投影图的特性 （1）不全面性 每个投影图只能反映物体两个方向的尺寸；立面图反映长度和高度；平面图反映长度和宽度；侧面图反映高度和宽度。 精心整理1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树 1.1问题背景： 假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个 1.2 个顶 图 G5 G5的三棵生成树： 可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。 1.3最小生成树的定义： 如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。 最小生成树的性质： 假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中， 则必存在一棵包含边（u,v）的最小生成树。 1.4解决方案： 两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。他们都利用了最小生成树的性质 1.普里姆（Prim）算法：有线到点，适合边稠密。时间复杂度O(N^2) 假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。设置两个新的集合U和T，其中 集合U（顶点集）用于存放G的最小生成树中的顶点， 集合T（边集合）存放G的最小生成树中的边。 T，U的初始状态：令集合U的初值为U＝{u1}（假设构造最小生成树时，从顶点u1出发），集合T的初值为T＝{}。 Prim算法的思想是：从所有u∈U，v∈V－U的边中，选取具有最小权值的边（u，v）∈E，将顶点v加入集合U中，将边（u，v）加入集合T中，如此不断重复，直到U ＝V时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。 Prim算法可用下述过程描述，其中用wuv表示顶点u与顶点v边上的权值。 （1 （2 (u， T＝T U＝U （3 按照 typedefstructArcNode { intadjvex;//adjex域存储该边依附的在U中的顶点数据结构与算法基础知识总结
(完整版)非常实用的数据结构知识点总结
数据结构基础知识整理
数据结构基础知识大全
数据结构基本知识.
小学语文各年级学习知识结构图
初中语文知识结构图
数据结构考研知识点总结
钢结构施工图的基本知识
考研数据结构图的必背算法及知识点
大数据结构与算法设计知识点
数据结构与算法知识点必备
数据结构基础知识
广州大学插本数据结构试题
数据结构基础知识
数据结构知识点全面总结—精华版
建筑结构施工图识图入门总结,很详细
考研数据结构图的必背算法及知识点