计算机考研:数据结构常用算法精析(6)

计算机考研:数据结构常用算法精析(6)


    数据结构是计算机考研408计算机学科专业基础综合的重要组成部分,考生需要认真复习,尤其是对于数据结构中一些常用…

计算机考研:数据结构常用算法精析(6)

  

  数据结构是计算机考研408计算机学科专业基础综合的重要组成部分,考生需要认真复习,尤其是对于数据结构中一些常用的算法问题,考生一定要弄懂弄会,理解的去掌握。小编下面一一为大家分析一下,帮助考生更好地去掌握。

  第六章

  结点的出度(OD):结点拥有的非空子树数目。

  结点的入度(ID):指向结点的分支(或有向弧、指针)的数目。

  树的度(TD):树中结点出度的最大值。

  结点的度:该结点的出度

  例如 在下述结论中,正确的是( D )【南京理工大学 1999 一、4 (1分)】

  ①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

  A.①②③ B.②③④ C.②④ D.①④

  有关二叉树下列说法正确的是( B )【南京理工大学 2000 一、11 (1.5分)】

  A.二叉树的度为2 B.一棵二叉树的度可以小于2

  C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2

  有序树和无序树:若树中任一结点的各子树从左到右有序,则该树为有序树(强调子树的次序),否则为无序树。(只强调各子树之间相对有序,而并不像二叉树那样,当只有一个子树是要么是左子树要么是右子树。而在有序树中,只有一个子树的有序树就不唯一了。)

  例题:在下列情况中,可称为二叉树的是( B )

  A.每个结点至多有两棵子树的树 B. 哈夫曼树 C.每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E.以上答案都不对

  C错在有序树不一定是二叉树,有序只是子树的相对保持有序,并没有严格定义具体那颗子树就是第几颗子树。

  森林(或树林):m(m≥0) 棵互不相交的有序树的有序集合。

  深度=h(h≥1)的K(K>1)叉树至多有( -1)/(K-1)个结点。

  包含n(n≥0)个结点的K(K>1)叉树的最小深度为:

  证:设有n个结点的K叉树的深度为h,若该树h-1层都是满的,即每层有最大结点数 -1(1≤i≤h-1),且其余结点都落在第h层,则该树的深度达最小,如图6.11所示:

计算机考研:数据结构常用算法精析(6)

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部