杭州紫金港培训学校(紫金港专升本)杭州紫金港培训学校(紫金港专升本)
同等学力申硕控制科学与工程学科综合考前辅导计算机软件技术第 26 节 / 共 32 节约 40 分钟报名学员看全文

软件(三):树与二叉树、图、检索与排序

对应计算机软件技术「二、数据结构」后三条:树与二叉树的性质、遍历和哈夫曼树,图的概念、存储结构与遍历,顺序查找、二分查找和散列查找,常用排序方法的过程、复杂度与稳定性。

本节考点:树与二叉树图及其存储结构检索排序

本节导读

这一节对应「二、数据结构」的后三条:「树与二叉树的概念及其应用」「图的概念及其存储结构」「检索与排序」。树和图是非线性结构:树是一对多,图是多对多。检索(查找)和排序是对各种结构最常做的两种运算。

学完要做到:会用二叉树的性质计算结点数,会由两种遍历序列还原二叉树,会构造哈夫曼树;会算邻接矩阵、邻接表的规模,会写深度优先和广度优先遍历序列;会做二分查找和线性探测散列;说清常用排序的过程、复杂度和稳定性。

树与二叉树

树是 nnn 个结点的有限集,有唯一的根,其余结点分成互不相交的子树。结点的子树个数叫度,度为 0 的结点叫叶子。

二叉树每个结点最多两棵子树,且分左右。主要性质:

  • 第 iii 层最多 2i−12^{i-1}2i−1 个结点;深度为 kkk 的二叉树最多 2k−12^{k}-12k−1 个结点。
  • 叶子数 n0n_{0}n0​ 与度为 2 的结点数 n2n_{2}n2​ 满足 n0=n2+1n_{0}=n_{2}+1n0​=n2​+1。
  • nnn 个结点的完全二叉树深度为 ⌊log⁡2n⌋+1\lfloor\log_{2}n\rfloor+1⌊log2​n⌋+1;按层编号后,编号大于 ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋ 的结点都是叶子。

遍历:先序(根、左、右),中序(左、根、右),后序(左、右、根),层次遍历按层从左到右。由先序和中序(或后序和中序)可以唯一确定一棵二叉树:先序的第一个是根,在中序里把它左右分开。

应用:哈夫曼树(带权路径长度 WPL 最小的二叉树)——每次选两个权最小的结点合并,用于哈夫曼编码;二叉排序树——左子树都比根小、右子树都比根大,中序遍历得到有序序列。

图的概念及其存储结构

图由顶点集和边集组成,分有向图和无向图。无向图所有顶点的度之和等于边数的 2 倍;nnn 个顶点的无向完全图有 n(n−1)/2n(n-1)/2n(n−1)/2 条边。

存储结构做法规模
邻接矩阵n×nn\times nn×n 矩阵,有边处为 1(或权值)n2n^{2}n2 个元素,适合稠密图
邻接表每个顶点一个链表,挂上它的邻接点无向图 2e2e2e 个边结点,有向图 eee 个,适合稀疏图

遍历:深度优先(DFS)从某顶点出发,沿一个未访问的邻点一直走下去,走不通再回退,类似树的先序;广度优先(BFS)先访问所有邻点,再一层层向外,借助队列。图的典型应用还有最小生成树(普里姆、克鲁斯卡尔算法)、最短路径(迪杰斯特拉算法)和拓扑排序。

检索

  • 顺序查找:逐个比较,等概率下查找成功的平均查找长度为 (n+1)/2(n+1)/2(n+1)/2,对表没有要求。
  • 二分查找:要求顺序存储且有序。取中间位置 mid=⌊(low+high)/2⌋mid=\lfloor(low+high)/2\rfloormid=⌊(low+high)/2⌋ 比较,相等则成功,小了在左半找(high=mid−1high=mid-1high=mid−1),大了在右半找(low=mid+1low=mid+1low=mid+1);最多比较 ⌊log⁡2n⌋+1\lfloor\log_{2}n\rfloor+1⌊log2​n⌋+1 次。
  • 二叉排序树查找:从根开始,比根小走左子树,比根大走右子树。
  • 散列查找:用散列函数(如除留余数法 H(key)=key mod pH(key)=key\bmod pH(key)=keymodp)直接算地址;不同关键字算出同一地址叫冲突,常用开放定址法(线性探测:依次试 H+1H+1H+1、H+2H+2H+2、…)或链地址法处理。

本节后面还有约 1496 字:报名学员看全文

每门课前 10 节免费看全文;从第 11 节起,完整教程要报名后由顾问在后台为你的账号开通才能看。

题库账号可以直接登录,但第 11 节起的完整教程要报名后由后台开通才能看。

学完练一练

按本节考点从本课的课后练习里抽题(每次 10 道以内),做完看解析、错题自动进错题本。第 11 节起的课后练习报名学员才能练。

本节内容由 AI 辅助编写,配图由 AI 生成,仅供备考参考;考试要求以《全国各类成人高等学校招生考试大纲(2024 年版)》及浙江省教育考试院当年公布为准。

我要提问免费报名咨询