精华内容
下载资源
问答
  • 数据结构期末复习

    万次阅读 多人点赞 2017-12-18 10:14:04
    这句话是不对的,因为数据的逻辑结构是指数据元素之间的关系,而不是数据内部的各数据项之间的关系。 2、数据的(逻辑结构)包括集合、线性结构、树形结构和图形结构四种基本类型。 3、数据结构是一门研究非数值...

    1、数据的逻辑结构是指数据的各数据项之间的逻辑关系
    这句话是不对的,因为数据的逻辑结构是指数据元素之间的关系,而不是数据内部的各数据项之间的关系。
    2、数据的(逻辑结构)包括集合、线性结构、树形结构和图形结构四种基本类型。
    3、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的关系和运算等的学科。
    4、数据在计算机内存中的表示是指(数据的存储结构)。
    5、下列函数中,哪个函数具有最慢的增长速度(A)
    A.Nlog(N^2) B.N(logN)^2 C.N^1.5 D.N^2logN
    6、计算机算法指的是()
    A、排序方法
    B、计算方法
    C、解决问题的有限运算序列
    D、调度方法
    C
    7、(neuDS)线性表的顺序存储结构是一种( A)
    A、随机存取的存储结构
    B、顺序存取的存储结构
    C、索引存取的存储结构
    D、散列存取的存储结构
    ​8、带表头附加结点的双向循环链表为空的判断条件是头指针L满足条件()
    A、L= =NULL
    B、L->right= =NULL
    C、L->left = =NULL
    D、L->right= =L
    D
    9、存在一棵总共有2016个结点的二叉树,其中有16个结点只有一个孩子。
    不对。应该是32个。
    10、如果一棵非空k(k≥2)叉树T中每个非叶子结点都有k个孩子,则称T为正则k叉树。若T的高度为h(单结点的树h=1),则T的结点数最多为(k^h-1)/(k-1),则T的结点数最少为K(h-1)+1;
    11、有一个四叉树,度2的结点数为2,度3的结点数为3,度4的结点数为4。问该树的叶结点个数是多少()
    A、21
    B、10
    C、12
    D、20
    答案:A
    因为任一棵树中,结点总数=总分支数目+1,所以:
    n+2+3+4=2*2+3*3+4*4+n*0+1
    解得:n=21;
    12、若森林F有15条边、25个结点,则F包含树的个数是10
    树的个数=森林的结点数-边数。
    13、将森林转换为对应的二叉树,若在二叉树中结点u是结点v的父结点的父结点,则在原来的森林中,u和v可能具有的关系是__
    Ⅰ.父子关系 Ⅱ.兄弟关系 Ⅲ.u的父结点与v的父结点是兄弟关系

    A.只有Ⅱ
    B.Ⅰ和Ⅱ
    C.Ⅰ和Ⅲ
    D.Ⅰ、Ⅱ、Ⅲ
    B
    14、已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则该完全二叉树的结点个数最多是 111 个;
    第六层有8个叶节点意味着其他的24个结点都是存在子结点的。
    15、对N(≥2)个权值均不相同的字符构造哈夫曼树,则树中任一非叶结点的权值一定不小于下一层任一结点的权值。
    16、(neuDS)在哈夫曼树中,任何一个结点它的度都是( )
    A、1或2
    B、0或2
    C、0或1
    D、0或1或2
    B
    17、不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑”溢出”情况。 这句话是对的。
    18、无向完全图:边数最大的无向简单图,满足e=n*(n-1)/2;有向完全图:弧数最大的有向简单图,满足e=n*(n-1);
    19、回路:第一个顶点(始点)和最后一个顶点(终点)相同的路径称为回路(环)。
    简单路径:如果一条路径上的顶点除了起点和终点可以相同外,其它顶点均不相同,则称此路径为一条简单路径;起点和终点相同的简单路径称为回路(或环)。
    简单回路:图的顶点序列中,除了第一个顶点和最后一个顶点相同外,其余顶点不重复出现的回路叫简单回路。或者说,若通路或回路不重复地包含相同的边,则它是简单的。
    20、树是含边数最小的连通图(n-1);图中若边小于n-1则必不连通;若图连通则至少含n-1条边;若图中多于n-1条边则必然含有回路;含n-1条边的连通图必然是树。对非连通图,由各个连通分量的生成树组成的集合称为非连通图的生成森林。
    21、下面关于图的存储的叙述中,正确的是__
    A.用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
    B.用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关
    C.用邻接表法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
    D.用邻接表法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关
    ​​[解析] 邻接矩阵的空间复杂度为O(n2),与边的个数无关。邻接表的空间复杂度为O(n+e),与图中的结点个数和边的个数都有关。
    22、在一个有向图中,所有顶点的入度与出度之和等于所有边之和的2倍。
    23、在任一有向图中,所有顶点的入度之和等于所有顶点的出度之和。
    24、无向连通图所有顶点的度之和为偶数
    25、如果无向图G必须进行两次广度优先搜索才能访问其所有顶点,则G一定有2个连通分量
    26、若无向图G=(V,E)中含8个顶点,为保证图G在任何情况下都是连通的,则需要的边数最少是__

    A.7
    B.21
    C.22
    D.28
    [解析] 本题考查图的基本概念。
    要保证无向图G在任何情况下都是连通的,即任意变动图G中的边,G始终保持连通。首先需要图G的任意7个结点构成完全连通子图G1,需n(n-1)/2=7×(7-1)/2=21条边,然后再添加一条边将第8个结点与G1连接起来,共需22条边。
    本题非常容易错误地选择选项A,主要原因是对“保证图G在任何情况下都是连通的”的理解,分析选项A,在图G中,具有8个顶点7条边并不能保证其一定是连通图,即有n-1条边的图不一定是连通图。
    分析选项D,图G有8个顶点28条边,那么图G一定是无向完全图,无向完全图能保证其在任何情况下都是连通的,但是这不符合题目中所需边数最少的要求。
    27、图的广度优先遍历类似于二叉树的:D
    A、先序遍历
    B、中序遍历
    C、后序遍历
    D、层次遍历
    28、图的深度优先遍历类似于二叉树的:先序遍历
    29、已知一个长度为16的顺序表L,其元素按关键字有序排列。若采用二分查找法查找一个L中不存在的元素,则关键字的比较次数最多是 5次;
    log2n+1;
    30、下列叙述正确的是()。
    A、在任意一棵非空二叉搜索树,删除某结点后又将其插入,则所得二叉搜索树与删除前原二叉搜索树相同。
    B、二叉树中除叶结点外, 任一结点X,其左子树根结点的值小于该结点(X)的值;其右子树根结点的值≥该结点(X)的值,则此二叉树一定是二叉搜索树。
    C、虽然给出关键字序列的顺序不一样,但依次生成的二叉搜索树却是一样的。
    D、在二叉搜索树中插入一个新结点,总是插入到最下层,作为新的叶子结点。
    D

    31、有12个结点的平衡二叉树的最大深度是 (41) 。
    A.4
    B.5
    C.6
    D.3
    B
    假设Nh表示深度为h的平衡二叉树中含有的最少的结点数目。那么,N0=0,N1=1,N2=2,并且Nh=Nh-1+Nh-2+1。根据平衡二叉树平衡二叉树的这一性质,N5=12。所以选择B。
    32、平衡二叉树的旋转
    参考:http://blog.csdn.net/vesper305/article/details/13614403
    参考:http://blog.csdn.net/winder9898/article/details/51098211

    33、对包含N个元素的散列表进行查找,平均查找长度为:
    A、O(1);
    B、O(logn);
    C、O(n);
    D、不确定
    D;
    34、填装因子:散列表中的元素个数与散列表大小的比值。
    35、给定散列表大小为11,散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的4个元素。问:此时该散列表的平均不成功查找次数是多少?
    A、1
    B、4/11
    C、21/11
    D、不确定
    编号1-11,假设是冲突的是1,他就会占满1,2 ,3 ,4四个格子。当查找到第一个空位置的时候查找失败,则查找1的时候5次,2的时候4次,3的时候3次,4的时候两次,后面的都是1次,所以是5+4+3+2+7=21.
    36、对给定序列{ 110,119,7,911,114,120,122 }采用次位优先(LSD)的基数排序,则两趟收集后的结果为:
    A、7, 110, 119, 114, 911, 120, 122
    B、7, 110, 119, 114, 911, 122, 120
    C、7, 110, 911, 114, 119, 120, 122
    D、110, 120, 911, 122, 114, 7, 119
    C第二趟收集的时候7的十位数字就是0了,不要想当然的看成7,再遇到类似情况的时候一定要注意。
    37、:顶点的度之和 = 边数的二倍 ,而边数是小于等于N*(N-1)/2;
    38、下列二叉树中,可能成为折半查找判定树(不含外部结点)的是: (4分)

    这里写图片描述

    展开全文
  • 数据结构

    热门讨论 2016-09-11 20:33:20
    数据结构的必要性: 计算机解决一个具体问题时,大致需要经过下列几个...所设计的而运算对象一般是简单的额整型、逻辑型数据,因此程序设计者的主要精力集中于程序设计技巧上,而不是数据的存储和组织上。然而,计算

    数据结构的必要性:

    计算机解决一个具体问题时,大致需要经过下列几个步骤:首先要从具体问题中国抽象出一个适当的数学模型,然后设计一个解此数学模型的算法。最后编出程序、进行测试、调整直至得到最终解答。当人们用计算机处理数值计算问题时,所用的数学模型是用数学方程描述。所设计的而运算对象一般是简单的额整型、逻辑型数据,因此程序设计者的主要精力集中于程序设计技巧上,而不是数据的存储和组织上。然而,计算机应用的更多领域是“非数值型计算问题”,他们的数学模型无法yoga数学方程描述,而是用数据结构描述,解决此类问题的关键是设计出何时的数据结构,描述非数值型问题的数学模型是用线性表、树、图等结构来描述的。

    了解数据结构首先我们需要了解他的一些基本概念:

    数据:计算机存储和处理的对象,例如一个字,一张表,一张图片,一段声音等都属于数据。

    数据元素:计算机处理的基本单位,在程序中作为一个整体而加以考虑和处理。他又由数据项组成,所以我觉得数据元素可以看成数据库中的某张表中的某条记录。数据项就是这张表中的某字段或域。

    数据结构的基本了解:

    数据结构是计算机组织数据和存储数据的方式。更进一步地说,数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和他们在计算机内的存储方式,以及定义在该组数据上的一组操作。合理的数据结构可降低程序设计的复杂性,提高程序执行的效率。从宏观来看,数据结构分类如下:


    研究对象:

    1.数据的逻辑结构

    反映数据元素之间的逻辑关系的数据结构,其中逻辑关系是指数据元素支架的关系,与他们在计算机中的存储位置无关。

    下图可以清晰地看出由集合到线性到树再到图的演变:

    (1)集合结构

    集合结构:集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系。各个数据元素是“平等”的,它们的共同属性是“同属于一个集合”。数据结构中的集合关系就类似于数学中的集合

    • 如果将紧密相关的数据组合到一个集合中,则能够更有效地处理这些紧密相关的数据。代替编写不同的代码来处理每一单独的对象,您可以使用相同的调用代码来处理一个集合的所有元素。

    (2)线性结构

    线性结构:线性结构中的数据元素之间是一对一的关系。包括一维数组、队列和栈。

    • 线性结构中的数据元素之间是一种线性关系,数据元素一个接一个地排列。如排除的队列、表格中一行行的记录等。
    • 队列:先进先出。例如排队买饭。
    • 栈:后进先出。例如放盘子与拿盘子。

    (3)树形结构

    树形结构:树形结构中的数据元素之间存在一种一对多的层次关系。

    • 树形结构是一层次的嵌套结构。一个树形结构的外层和内层有相似的结构,所以,这种结构多可以递归的表示。

    (4)图形结构

    图形结构:图形结构中的数据元素是多对多的关系。

    • 图形结构的数据元素之间存在着多对多的关系,也称网状结构。
    • 从上面的例子也可以看出,逻辑结构是针对具体问题的,是为了解决某个问题, 在对问题理解的基础上,选择一个合适的数据结构表示数据元素之间的逻辑关系。

    2.数据的物理结构

    指数据的逻辑结构在计算机存储空间的存放形式。

    顺序存储方式:存储结点都放在连续的存储区中。利用结点在存储器中相对位置表示数据元素之间的逻辑关系。

    链式存储方式:每个存储结点除含数据元素外,还包含指针,用指针来表示数据元素之间的逻辑关系。

    拓展:

    关系的机内表示:一种逻辑结构可以采用一种或几种存储方式来表达数据源之间的额逻辑关系,相应的存储结构称为给定逻辑结构的存储实现或存储映像。

    如何描述存储结构?

    机器级(讨论存储结构在计算机存储器里的表示形式,直接以内存地址来描述存储结构)。语言级(用程序设计语言中的类型说明、变量等手段描述)。语言级存储描述经编译器转换成机器级,因此可看成是机内表示。

    3.数据结构的运算

    指在某种逻辑结构上个施加的操作,即对逻辑结构的加工。在每个逻辑结构上,都定义了一组基本运算,这些运算包括:建立、查找、读取、插入和删除等


    有了之前的介绍,最后讲到了查找和排序。

    查找:

    静态查找表:是以具有相同特性的数据元素集合为逻辑结构运算;动态查找表是以集合为逻辑结构运算。

    查找在不同存储结构下的实现:

    顺序表:从表最后一个数据元素位置开始,从后往前依次将各个位置上的数据元素的键值与给定值比较。

    有序表:二分查找:mid=(low+high)/2

    索引顺序表:

    未完,待续。。。


    展开全文
  • 数据结构PTA选择判断填空(1)

    千次阅读 2019-10-27 17:03:30
    数据的逻辑结构是指数据的各数据项之间的逻辑关系。 错误,逻辑结构是数据元素之间的关系而不是数据元素的内容(数据项)关系 作业2 算法复杂度分析 2-2 下列代码 if ( A > B ) { for ( i=0; i<N*N/100; i++ ...

    作业1 数据结构基本概念与顺序表基本操作
    1-2
    数据的逻辑结构是指数据的各数据项之间的逻辑关系。

    错误
    逻辑结构是数据元素之间的关系而不是数据元素的内容(数据项)关系

    作业2 算法复杂度分析
    2-2
    下列代码

    if ( A > B ) {
        for ( i=0; i<N*N/100; i++ )
            for ( j=N*N; j>i; j-- )
                A += B;
    }
    else {
        for ( i=0; i<N*2; i++ )
            for ( j=N*3; j>i; j-- )
                A += B;
    }
    

    的时间复杂度是O(N的四次方)

    else里面是N乘不是方(我吐了)

    作业5-链表
    2-10
    将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为( )。
    O(m)

    作业10-数组与广义表及树的概念

    2-2
    设有数组A[i,j],数组的每个元素长度为3字节,i的值为1 到8 ,j的值为1 到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为()。

    A. BA+141
    B. BA+180
    C. BA+222
    D. BA+225
    答案:B
    以列为主,每列存放八个元素,
    Loc(aij) = BA + [(8-1)8 + 5-1]3 = BA + 180。
    2-4
    若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1…(n(n+1))/2]中,则在B中确定aij(i<j)的位置k的关系为()。
    A. i
    (i-1)/2+j
    B. j
    (j-1)/2+i
    C. i*(i+1)/2+j
    D. j*(j+1)/2+i
    答案:B
    i<j算的是上三角的元素对应的下三角元素。
    i>j就选A了。

    作业11 树和二叉树的定义与基本操作

    2-8
    如果一棵非空k(k≥2)叉树T中每个非叶子结点都有k个孩子,则称T为正则k叉树。若T的高度为h(单结点的树h=1),则T的结点数最多为:
    (K^H -1)/ (K-1)
    就是K叉树节点数公式
    同时,二叉树第i层最多**2^(i-1)**个节点。

    展开全文
  • 数据结构描述的关系并不是真正的逻辑关系,因为数据元素之间在数据内容上没有具体逻辑可言,数据结构描述的是——特定业务场景下对应的数据元素集合内数据元素如何存取。数据结构由工业界诞生,具体的数据结构由具体...

    数据结构描述的关系并不是真正的逻辑关系,因为数据元素之间在数据内容上没有具体逻辑可言,数据结构描述的是——特定业务场景下对应的数据元素集合内数据元素如何存取。数据结构由工业界诞生,具体的数据结构由具体的业务场景决定,人们从商业应用中某一类/某个数据对象的数据表现出来的存取方式来定义数据结构。

    根据数据元素之间关系的不同特性,通常有下列四种基本机构:1:集合,结构中的元素除了同属一个数据对象外没有其他关系。2:线性结构(线性表),结构中的元素同属一个数据对象,一个对一个首尾相连,有唯一的“第一个”数据元素和“最后一个”数据元素,相邻元素存在顺序不可打乱的关系。3:树形结构(二叉树),结构中的元素同属一个数据对象,结构中的元素存在一个对多个的关系,如数据库索引。4:图状结构/网状结构,结构中的元素同属一个数据对象,结构中的元素存在多个对多个的关系。

     

    数据结构的形式定义为:数据结构是一个二元组

    Data_Structure=(D,S);

    D是数据元素的有限集,S是数据元素间关系的有限集

    数据类型和数据结构的概念密切相关,数据类型是一个值的集合和定义在这个值集上的一组操作的总称(包含了“集合”这种数据结构和一组操作)。

    数据类型的三元组表示形式为:

    (D,S,P)

    D是数据元素的有限集,S是数据元素间关系的有限集,P是对数据元素的操作集。

     

    数据结构在计算机中的表示/映像称为数据元素的物理结构,又称存储结构,包括数据元素的表示和存在关系的表示。

    数据的存在关系结构和物理结构是密切相关的,任何一个算法的设计取决于存在关系结构,算法的实现依赖于采取的存储结构。

    数据元素之间的存在关系在计算机中有两种不同的表示方法:顺序映像和非顺序映像,并由此得到两种不同的存储结构:顺序存储结构和链式存储结构。(四种数据结构(存在关系)可以用两种物理结构的任意一种来表示)

    顺序映像的特点是:借助元素在存储器中的相对位置来表示数据元素之间的存在关系。比如用两个字长的位串来表示一个实数,则可以用地址相邻的四个字长的位串表示一个复数。

    非顺序映像的特点是:借助指示存储元素地址的指针来表示数据元素之间的存在关系。见下图(b)

                                                                             线性表/线性结构

    线性结构(线性表),结构中的元素同属一个数据对象,一个对一个首尾相连,有唯一的“第一个”数据元素和“最后一个”数据元素,相邻元素存在顺序不可打乱的关系。第一个数据元素的地址常称为起始位置或基地址。含有大量记录(含有多个数据项的数据元素)的线性表又称为文件。

    顺序存储结构和链式存储结构表示线性表/线性结构优缺点对比:

    顺序存储结构

    插入或删除元素成本大:顺序存储结构中,在某个位置上插入或删除一个数据元素时,时间主要消耗在移动元素上,移动元素的个数取决于插入或删除元素的位置。

    可随机存(set赋值)取(get读值):顺序存储结构中,每个元素的存储位置和物理结构表示的线性表的起始位置相差一个和数据元素在线性表中位置成正比的常数,只要确定了起始位置便可存取任一元素。【随机存取指的是按下标存取,若是根据元素内容查找,跟链式结构一样需要遍历没有优点】

    存储空间紧密相连,空间利用率大。

    (高级程序语言中常常用数组来描述顺序存储结构。)

    链式存储结构

    用一组任意的存储单元存储线性表的数据元素,因此为了表示每个数据元素和其直接后继元素的逻辑关系,元素a的存储映像除了保存元素的数据信息外还需存储一个指示其直接后继元素位置的信息,元素的这个存储映像也称为结点,包括数据域和指针域。

    C语言中的指针和java中的对象引用是一个意思。

    每个结点中只包含一个指针域,这样的链式存储结构也叫线性链表或单链表。最后一个元素没有后继元素,因此线性链表的最后一个结点的指针为null。

    整个单链表的存取(set、get)必须从头指针开始进行

    整个链表的插入或删除仅需要修改最多两个指针不需要移动元素。

     

    任何一种数据结构:起始位置是系统确定的,插入的数据一定可以是有序的,虽然set没有实现。

    关于双向链表和循环链表:

    循环链表即收尾相连的链表,最后一个元素的指针部分指出第一个元素的存储位置。

    双向链表则是指元素的指针部分有两块,一块指向前趋元素,一块指向后继元素。双向链表也可以是循环的(肯定是可以的,工业界各种结构可见,而数据结构课程是对工业界数据结构的总结)。

     

     

                                                                                         

     

                                                                                         线性表/线性结构之数组

    数组是受限的线性结构

    数组一旦被定义其维数和维界不再改变,因此除了结构的初始化和销毁外,数组只有存取元素和修改元素值的操作,不能插入和删除。因此,采用顺序存储结构表示数组是自然的事了(也可以用链式结构)。在java语言中数组类型数据的确是不可变长的,但用数组实现的arrayLis和Vector均可以在指定位置删除和插入元素,本质是建立一个新的数组然后进行复制。

                                                                                        线性表/线性结构之栈和队列

    栈和队列也是受限的线性表结构,栈和队列一样可以用链式结构和顺序结构来表示。顺序栈(顺序存储结构的栈)设立一个top指针来指示栈顶元素,出栈时top指针减1,入栈则加1.

    队列和栈类似,指示需要在队头和队尾设立两个指针。

     

                                                                                          树和二叉树

    树是n个节点的有限集,任何非空树中有且仅有一个根节点。n>1时,其他节点可分为若干个互不相交的有限集,每个集合本身是一个树,称为根的子树。

    树的节点包含一个数据元素和若干指向其子树的分支,节点拥有的子树的数量称为子树的度。度为0的节点称为叶子或终端节点。节点A的子树的根节点B称为节点A的孩子,反过来节点A是节点B的双亲。同一双亲的孩子称为兄弟。

    树中节点的最大层次为数的深度(第一层为根节点,最后一层为叶子)。

    如果将树种各子树看成是有序的则为有序树,否则为无序树,有序树中左边第一个子树为第一个孩子,右边第一个子树为最后一个孩子。任意一个节点至多只有两个分支并且子树有左右之分的树称为二叉树(二叉树中不存在度大于2的节点),(任何二叉树都是有序树)

    一个深度为k且有(2的k次方)-1个节点的二叉树为满二叉树。

    将一个满二叉树编号,从上至下,从左到右。如果一个普通二叉树上的节点跟满二叉树上对应位置的节点的编号一样,则该二叉树为完全二叉树。

    二叉树的存储结构:

    顺序存储结构只适用于完全二叉树(非完全二叉树的空节点随机分布且编号不确定)

    链式存储结构:由二叉树的定义知一个结点至少包括数据,左右指针,有时还包括指向双亲的指针,根据这两种结构得到二叉树的物理存储结构为二叉链表和三叉链表。二叉链表查找某节点只能从根节点出发。

    二叉树的遍历和线索二叉树:

    在实际应用中对二叉树遍历是少不了的操作,为了方便对二叉树进行遍历,必须在第一次复杂的遍历的动态过程中对二叉树进行线索化(第一次遍历按照树上所有根节点统一被遍历的先后顺序分为先序遍历,中序遍历和后序遍历),将线性遍历链路上的每个节点可找到其前趋和后继元素,以便以后实现简单的线性遍历。这个过程叫二叉树的线索化,线索化后的二叉树叫线索二叉树。当然线索二叉树上有左右子树的节点是没有后继/前趋元素的,线索二叉树在遍历到这类节点的时候按照先序/中序/后序原则找到其后继元素继续进行遍历。

    二叉树和二叉排序树的区别:二叉树是只区分左右子树的有序树,而二叉排序树则分清了左右子树的值和节点的值相比较的大小。

     

                                                                                         查找

    查找和存取的取的区别?

    根据相对于起始元素的相对位置进行的搜寻叫取,根据内容(关键字)进行的搜寻叫查找。顺序存储结构的存取可以根据相对于起始元素的相对位置算出目标元素的地址进行直接存取,链式存储结构的存取只能从特殊位置出发一个一个找(单链表只能从头,双向链表只能头/尾,双向循环链表可以任何一个元素,线索二叉树如果用二叉链表只能从根节点,三叉链表是根节点或最后一个遍历的节点)。java语言没有提供对非顺序存储结构的集合中单个元素的存取(只能add添加一个元素和遍历取得所有元素)。

    实际应用中有一种大量使用的集合性质的集合元素间没有存在关系(除了同属一个数据对象),完全松散的数据结构——"查找表"。

    对查找表常进行的操作有:1,查询某数据元素是否在查找表中2,检索某数据元素的各种属性3,在查找表中插入元素4,在查找表中删除元素。只对查找表进行前两种操作时称该查找表为静态查找表,对查找表的操作包括插入和删除元素时称该查找表为动态查找表。

    关键字(key):关键字是数据元素(或记录)中某个数据项的值,它可以标识一个数据元素或记录,若关键字可以唯一得标识一个记录则该关键字为主关键字,否则为次关键字。关键字的概念不仅用于集合,在四种逻辑结构中也用于线性结构(如线性表)和树形结构。关键字只是数据的一部分,仅仅和数据有关系,和数据元素的位置没有任何关系。给出关键字找到对应数据只能通过让所有数据元素的关键字和给定的关键字依次比较来查找,查找的快慢取决于比较的次数。。。

    查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或记录的过程即查找。

     

    静态查找表查找方法一般有顺序表查找(实现顺序查找意味着必须将查找表进行线性化遍历,用线性结构实现或以二叉链表或三叉链表来实现再进行线索化,然后实现顺序查找,但这样更麻烦。说白了顺序表查找就是一个一个找。)和有序表的折半查找。折半查找只适用于顺序存储结构(存储位置需要折半),并且元素也是按大小顺序排列的才行。静态查找表中查找效率几乎最高构建成本又不高的结构是次优二叉查找树。次优二叉查找树和后面所说的二叉排序树唯一的区别是静态的,不能删除或添加元素,根据固定的元素一次性生成。并且次优二叉查找树取的根节点不是按数据大小的中间值取的,而是取最接近给定值的元素为根节点。 

    从静态查找表的查找方法可以看出最适合实现查找的物理存储结构是树结构,根据范围边界来排查查找无疑提高了查找效率。还有一种更高效率的查找方式是哈希表(但哈希表的构建成本应该高,索引都不用哈希表去实现可想而知。。。) 

      

    二叉排序树:(也叫二叉查找树)

    对于任何一个结点,左子树的值均小于根节点的值,右子树的值均大于根节点的值。并且二叉排序树是动态生成的,一个元素一个元素查找并添加且不添加重复元素。

    二叉排序树的查找:(二分查找法)

    先比较根节点的值,再依次从左子树/右子树进行查找。(即二分查找法)

    二叉排序树的插入或删除:

    插入:当树中不存在关键字等于给定值的节点时再进行插入。

    删除P节点时:用P节点的左子树替代P,并将P节点的右子树变成P节点左子树的最右节点的右子树。

     

    平衡二叉树:(在二叉排序树(二叉查找树)的基础上,为提高查找效率进行平衡处理的二叉查找树(二叉排序树))

    效率较低的二叉查找树和平衡处理后查找效率提高的二叉查找树对比:

    任何一个节点的左子树与右子树的深度差的绝对值小于等于1.平衡二叉树不一定是二叉排序树,讨论是否是平衡二叉树仅关注深度。

    B-树和B+树:(是平衡树,因为记录全在同一层次的叶子节点上,可以推出任一节点的左右子树深度一样。其实B就是balance平衡的意思)

    B-树几乎和二叉排序树一模一样,仅仅是分叉多了而已。查找过程也一模一样。

    B+树是B-树的变形,差异仅在于:1.每个节点上的关键字和其子树数量相等(结点中的关键字是子树中的最大/最小关键字。)(B-树中关键字为子树个数-1)。2.叶子节点包含全部关键字的信息并依关键字大小从小到大顺序链接(比B-树多了一种查找方式)

    红黑树:同B-树B+树一样,也是基于平衡二叉树演化而来的。https://zhuanlan.zhihu.com/p/31805309

    1.根节点和叶子节点(nil节点/空节点)为黑色。

    2.不能有两个连续的红色节点。

    3.任一节点到其所有叶子节点包含的黑色节点数目相同。

    插入:

    首先插入的节点肯定是红色的(为了保证任一节点到其所有叶子节点包含的黑色节点数目相同肯定不能直接插入黑色节点)。

    当插入节点的父节点是红色,由于红色节点不能相连,就需要做调整了。调整有两种方式,调整颜色,或左右旋转(说的是两个节点同时进行逆时针旋转互换父子关系,并把多出来的叶子节点插在少了叶子节点的位置)。

    树的查找时间复杂度一般为logn:

     

     

                                                                                        哈希表

    在线性表和树中,记录在结构中的相对位置是随机的,和记录的关键字之间不存在确定的关系,因此在结构中查找记录时需进行一系列和关键字的比较,查找的效率取决于查找过程中所进行的比较次数。理想的情况是希望不进行任何比较,一次得到所查记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系,是每个关键字和结构中一个唯一的存储位置相对应。我们称这个对应关系f为哈希函数,哈希函数是关键字集合到地址集合的映像。按这个思想建立的表为哈希表。

    哈希表只能表明查找方式,不能说明底层物理存储结构是以什么实现的。

    由此可知:hashset和treeset的本质区别是查找数据元素时的效率:前者直接根据哈希code定位到数据元素的地址,后者是根据节点关键字确定范围排除查找关键字。

                      插入数据方面的区别似乎没有:因为hashset也需要遍历集合来保证其中没有相同的hashcode。treeset暂不详,只知道排序二叉树树和hashset的插入是一样的,只是遍历的不是hashcode而是关键字而已。

     

     

     

     

     

     

     

                                                                                     算法

    算法是对特定问题的求解步骤的描述,是指令的有限序列。由控制结构(顺序,分支,循环)和原子操作构成。通常以原操作重复执行的次数为算法的时间度量。比如:

    {++x;s=0}

    算法复杂度为O(1)

    for(i=0;i<n;i++){++x;s+=x;}

    算法复杂度为O(n)

    排序类算法关键:区分出嵌套循环,独立循环和交叉循环(这一步映像做不到,算法基础再好都扯淡)。交叉循环的自增通常放在交叉结果后。

    冒泡排序:不断比较取最大/小的值,便能把最大/小的值排到末尾。

    构造哈希函数:对于关键字中的任何一个关键字,经哈希函数映像到地址集合中任何一个地址的概率是相等的,则成此类哈希函数是均匀的哈希函数。也就是让关键字经过哈希函数得到一个“随机的地址”,以便使一组关键字的哈希地址均匀分布在整个地址区间中,从而减少冲突。

    1.直接定址法:一次线性关系

    2.随机数法:用一个随机函数,取关键字的随机函数值为地址。

    哈希冲突处理方法:

    1:开放定址法:

    2:再哈希法:产生哈希冲突时计算另一个哈希函数地址,直到冲突不再发生。

    3:链地址法:

    4:公共溢出区:建立一个公共溢出区,将产生冲突的哈希地址填入溢出表。

    算法的复杂度:

     

                                                                                            内部排序

    按排序工作量的分:1.简单排序方法O(n²),   2.先进排序方法O(nlogn)   3.基数排序时间复杂度为O(d▪n)

     

    求二叉排序树的最长路径:

     

    展开全文
  • 学会分析研究计算机加工处理的对象的特征,以便为应用涉及的对象选择适当的逻辑结构,存储结构以及相应的算法,并初步掌握算法的时间分析以及空间分析技术 数据结构:是相互之间存在一种或多种特定关系的数据元素的...
  • 数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( ) 【上海海运学院 1998 一、1(1分)】 三、填空 1.数据的物理结构包括(数据元素) 的表示和(数据元素间的关系) 的表示。【燕山...
  • 可方便地用于各种逻辑结构的存储表示 C. 存储密度大 D. 删除运算方便 2. 下面关于线性表的叙述中,错误的是哪一个 【 】 A. 线性表采用顺序存储,必须占用一片连续的存储单元。 B. 线性表采用顺序存储,便于进行...
  • 拓扑排序算法 2数据结构逻辑上可以分为 3下述编码中不是前缀码 4下列陈述正确的是 对于哈希函数 H key =key%17,被称为同义词的关键字 5若查找每个元素的概率相等则在长度为 n 的顺序表上查找任一元素查找成功的...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    <br>实验二 单链表结构及计算 实验目的: 通过实验掌握下列知识: 1、熟悉线性表基本运算在两种存储结构(顺序结构和链式结构)上实现; 2、继续熟悉VC编程、编译和调试环境; 内容及步骤:...
  • 数据驱动测试框架

    千次阅读 2018-04-02 19:42:19
    如果测试过程中会遇到下列问题:测试需要针对许多具有类似结构的数据来执行实际的测试逻辑是一样的,发生改变的仅仅是数据数据可以被一组不同的人修改 这种类型的测试通常有很好的处理方法,即所谓的“数据驱动测试...
  • 在以下的存储形式中,不是树的存储形式的是() A.双亲表示法 B.孩子链表表示法 C.孩子兄弟表示法 D.顺序存储表示法 D 常用孩子兄弟表示法转化为二叉树进行储存。 在一个无向图,所有顶点的度数之和等于图的...
  • 字符型数据的输入与输出;逻辑运算中的"非(!)"、"与(&&)"、"或(||)";switch语句; 2. 不能很熟练打出代码需要多练。 3. 这节课所学的知识都不是很复杂 4. 学习到了各种不同程序所输出的不同结果,...
  • k和k+2之间发生的是什么数据相关 I. 先写后读相关 II.写-写相关 III. 先读后写相关 A.只有I B.只有I、II C.只有I、III D.以上都不对 2.开发并行的途径有( D ),资源重复和资源共享。 A、多计算机系统 B、多道分...
  • 下列不是数据流计算特点的是( . A.设置状态 B.没有指令计数器 ) C.没有变量的概念 D.操作结果不产生副作用 8.在尾数下溢处理方法中,平均误差最大的是( A.舍入法 B.截断法 C.恒置“1”法 ) D.ROM 查表法 9.字串位并...
  • 在以下的存储形式中,不是树的存储形式的是() A.双亲表示法 B.孩子链表表示法 C.孩子兄弟表示法 D.顺序存储表示法 D 常用孩子兄弟表示法转化为二叉树进行储存。 在一个无向图,所有顶点的度数之和等于图的...
  • Wishbone 开放总线连接器允许在FPGA 上实现的逻辑模块可以透明的连接到各 种处理器上。引入了以FPGA 为目标的虚拟仪器,当其与LiveDesign-enabled 硬 件平台NanoBoard 结合时,用户可以快速、交互地实现和调试基于...
  • 数据的逻辑结构在计算机中的表示 C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据 (33) 设有下列二叉树:图见书P46 对此二叉树中序遍历的结果为(B) A. ABCDEF B. DBEAFC C. ABDECF D. DEBFCA (34) 在面向...
  • ”&”、”|”为位操作符,而对应的逻辑操作符为:”&&”、”||”;不等号可以使用”~=”、”!=”、””中的任何一个。 关于如何将一个源字符流数据按照数学规则计算出结果的算法编译原理已有成熟的理论介绍,通常是...
  • 数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素:一是数据元素的集合,通常记为D;二是D上的关系,它反映了数据元素之间...
  • 【基础】Oracle基础1

    2018-01-16 15:34:00
    1.下列不属于Oracle得逻辑结构的是(D) A.区 B.段 C. 表空间 D. 数据文件 解析:Oracle中逻辑结构包括表空间、段、区和块。其中,数据库由表空间构成,而表空间又是由段构成,而段又是由区构成,而区又是由...
  •  --- 创建 备份数据的 device USE master EXEC sp_addumpdevice 'disk', 'testBack', 'c:\mssql7backup\MyNwind_1.dat'  --- 开始 备份 BACKUP DATABASE pubs TO testBack  4、说明:创建新表 create table ...
  • (2) 数据的逻辑结构在计算机存储空间中的存放形式称为数据的______。 答:模式#逻辑模式#概念模式 (3) 若按功能划分,软件测试的方法通常分为白盒测试方法和______测试方法。 答:黑盒 (4) 如果一个工人可管理多个...
  • 下列不属于ORACLE的逻辑结构的是C 区 段 数据文件 表空间 ? 2. 下面哪个用户不是ORACLE缺省安装后就存在的用户(A) A . SYSDBA B. SYSTEM C. SCOTT D. SYS ? 3? 下面哪个操作会导致用户连接到ORACLE数据库但不能创建...
  • 任选项不是入口条件,但每完成一项都会加分,对于完成了必选项同学,尽可能地多完成一些任选项,以期获得更高答辩成绩。 如果所有项(包括必选和任选)都完成,那么功能分就是满分。 如果设计思路、界面...
  • 下列属于面向对象开发方法的是(A B C D)。 A) Booch B) UML C) Coad D) OMT 6. 软件危机的主要表现是(B D)。 A) 软件成本太高 B) 软件产品的质量低劣 C) 软件开发人员明显不足 D) 软件生产率低下 7...
  • 下列选项中,不是一个算法的基本特征的是( )。A.完整性B.可行性C.有穷性D.拥有足够的情报2.数据结构中,与所使用的计算机无关的是数据的( )。A.存储结构B.物理结构c.逻辑结构D.物理和存储结构3...
  • 1. 下列不属于ORACLE的逻辑结构的是(C)区段数据文件表空间2. 下面哪个用户不是ORACLE缺省安装后就存在的用户(A)A . SYSDBAB. SYSTEMC. SCOTTD. SYS3 下面哪个操作会导致用户连接到ORACLE数据库,但不能创建表(A)...
  • 笔记

    2019-11-19 20:26:23
    下列选项中,不是大数据发展趋势的是?大数据未来可能会被淘汰 在Spark的软件栈中,用于图计算的是GraphX 使用有监督学习的问题可以被分为两类:回归问题和分类问题 HBase是在Hadoop之上构建的开源分布式结构化...
  • 1. 下列不属于ORACLE的逻辑结构的是(C) 区 段 数据文件 表空间 2. 下面哪个用户不是ORACLE缺省安装后就存在的用户(A) A . SYSDBA B. SYSTEM C. SCOTT D. SYS 3 下面哪个操作会导致用户连接到...
  • Oracle笔试题

    万次阅读 2016-02-02 13:21:06
    1、下列不属于ORACLE的逻辑结构的是() A、区 B、段 C、数据文件 D、表空间 答案:C 2、下面哪个用户不是ORACLE缺省安装后就存在的用户( ) A、SYSDBA B、SYSTEM C、SCOTT D、SYS 答案:A 3、下面哪个操作会导致...

空空如也

空空如也

1 2 3 4
收藏数 67
精华内容 26
关键字:

下列不是数据的逻辑结构的是