文档内容
《信息技术》三色速记手册
第七章 程序设计基础知识
【考点一】算法描述
算法描述（Algorithm Description）是指对设计出的算法，用一种方式进行详细的描述，
以便与人交流。算法可采用多种描述语言来描述，一般用自然语言、伪代码、流程图描述。
各种描述语言在对问题的描述能力方面存在一定的差异，但描述的结果必须满足算法的五个
特征。
（一）自然语言
自然语言是人们日常所用的语言，如汉语、英语、德语等。
例如：描述讲橙汁和可乐互换杯子。
第一步：橙汁倒入空杯；
第二步：可乐倒入刚空出的杯子；
第三步：橙汁倒入刚刚可乐空出的杯子。
自然语言的缺点：
用自然语言描述算法符合人们的表达习惯，容易理解，但用自然语言描述算法有以下缺点：
（1）自然语言描述算法较长、较繁琐；
（2）自然语言具有歧义性，容易导致算法的不确定性；
（3）当算法中有循环和分支较多等复杂的问题时，难以表达清晰、准确；
（4）自然语言描述算法不能被计算机识别和执行。
（二）伪代码
伪代码是介于自然语言和计算机程序语言之间的一种算法描述，通常是自然语言和类编程
语言组成的混合结构。
例如，工作日上班的算法用伪代码描述如下：
IF 九点以前 THEN
do 私人事务；
ELSE 9点到18点 THEN
工作；
ELSE
下班；
END IF
伪代码比自然语言更精确，描述算法结构清晰、代码简单、可读性好，从而易懂、修改容
易。使用伪代码的目的是为了使被描述的算法可以容易转换成计算机程序，同时还可以避开
不同程序语言的语法差别，如Pascal语言使用“:=”作为赋值，使用“=”作为比较；又如
C/C++的赋值使用“=”，而判断相等的比较则是用“==”。
伪代码缺点是不直观、错误不容易排查。
（三）流程图
以特定的图形符号加上说明，表示算法的图，称为流程图或框图。流程图是算法的一种图
形化表示方法，由如下表所示的图框和流程线组成。其中图框表示各种操作的类型，图框中
的文字和符号表示操作的内容，流程线表示操作的先后次序。
流程图的基本要素
48《信息技术》三色速记手册
流程图的优点是：形象、直观，各种操作一目了然，不会产生“歧义性”，容易理解。算法
出错时容易发现，并可以直接转化为程序。
流程图的缺点是：所占篇幅较大，由于允许使用流程线，过于灵活，不受约束，使用者可使
流程任意转向，从而造成程序阅读和修改上的困难，不利于结构化程序的设计。
【考点二】线性表
（一）顺序存储结构
1.基本概念
线性表的顺序存储结构具有以下两个基本特点：
（1）线性表中所有元素所占的存储空间是连续的。
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
线性表中的第一个数据元素的存储地址（指第一个字节的地址，即首地址）为ADR（a1），
每一个数据元素占k个字节，则线性表的第i个元素在计算机存储空间中存储地址为ADR
（ai）=ADR（a1）+（i-1）k。
2.顺序表的运算
（二）链式存储结构
1.基本概念
每一个结点包含两个域，存储数据元素信息的被称为数据域，存储直接后继位置的域称为
指针域。指针域中存储的信息称做指针或链。n个结点连接成一个链表，即为线性表的链式
49《信息技术》三色速记手册
存储结构。又由于此链表的每个结点只包含一个指针域，故又称为线性链表或单链表。
2.线性表的单链表存储
在链表中，节点的存储空间可以不连续，逻辑关系上相邻的节点物理位置上不一定相邻，节
点之间的逻辑关系由指针域来确定。每个节点只有一个指针域的链表称为单链表，如下图
所示。
通常，单链表中每个节点的指针域用于存放后继节点的存储地址，最后一个节点无后继节点，
指针域为空，用Null或^表示。
假设p是指向线性表第i个元素的指针，则该节点a1的数据域用p→data来表示，节点a1
的指针域可以用p→next来表示。
（1）获取单链表元素。
读取单链表第i个数据，基本思路如下:
①声明一个节点p指向链表第一个节点，初始化j从1开始；
②当j=0）个结点的有限集合，n=0时，称为空树，树是属于逻辑结构而任意非空树
应满足：
1）有且仅有一个特定的称为根的结点
2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集合，其中每一个集合本身又是
一棵树，称为根结点的子树
结论：n个结点的树中只有n-1条边
50《信息技术》三色速记手册
树的基本概念
1.祖先结点和子孙结点：如k是子孙结点，ABE是k的祖先结点
2.双亲结点和孩子结点：如k是E的孩子结点，E是k的双亲结点
3.兄弟结点：有共同的双亲结点称为兄弟结点，如K和L是兄弟结点
4.度：树中一个结点的子结点的个数称为该结点的度，如B结点的度为2
5.树的度：树中最大度数称为树的度，如上图树的度为3
6.分支结点：度大于0的结点称为分支结点（有孩子结点），如ABCDE
7.叶子结点：度为0的结点称为叶子结点（没有孩子结点），如FGHIJKL
注意：有的教材称第一层为第0层，需要注意一下，这里第一层定义为第一层
8、结点的层次：如A结点在第一层，B结点在第二层，E结点在第三层，K结点在第四层
9、结点的高度：从叶子结点开始自低向上逐层累加的，如B结点的高度为3
10、结点的深度：从根结点开始自顶向下逐层累加的（和结点的高度刚好相反），如B结点
的深度是2
树的高度（深度）是树中结点的最大层数
11、有序树：如把B和D的位置调换后，上图的树就变为另一棵树了，那么上图的树就是有
序树
12、无序树：如把B和D的位置调换后，上图的树还是同一棵树，那么上图的树就是无序树
13、路径：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的（路径
一定是自上而下的）
14、路径长度：路径上所经历边的个数，如A到E这条路径有两条边，所以路径长度为2
15、森林：m（m>=0）棵互不相交的树的集合，树和森林之间是可以相互转换的，如把上图
根结点A去掉，就变成由三棵树组成的森林，下图加上一个根结点A就变成一棵树
51《信息技术》三色速记手册
解释性质1：所有的叶子结点的度为0，所以不考虑叶子结点，只考虑分支结点。E的度为2
（分别是K、L），B的度为2（E、F），C的度为1（G），D的度为3（H、I、J），A的度为3
（B、C、D），这时会发现有一个结点没包含进来，就是根结点A，所以要加1。这就是这条
结论的由来
解释性质2：假设每个结点都有最大的度m。第一层只能有一个结点，第二层的最多结点数
为m，第三层为m*m，以此类推，第i层最多结点数为m^（i-1）
解释性质3：就是把结论2中的所有结点加起来，就可以得到这条结论了（使用学过的等比
数列求和公式推导）
错位相减法
Sn=a1+a2 +a3 +…+an
Snq= a1q+a2q+…+a（n-1）q+anq= a2 +a3 +…+an+anq
以上两式相减得（1-q）Sn=a1-anq
52《信息技术》三色速记手册
二叉树的定义
二叉树（Binary Tree）是结点的有限集合，它或者为空，或者由一个根结点及两棵互不相
交的左、右子树构成，而其左、右子树又都是二叉树。
注意：二叉树必须严格区分左右子树。即使只有一棵子树，也要说明它是左子树还是右子树。
交换一棵二叉树的左右子树后得到的是另一棵二叉树。
二叉树的基本形态
结点总数为3 的所有二叉树的不同形状
满二叉树
一棵高度为k并具有2k－1个结点的二叉树称为满二叉树。
一棵二叉树中任意一层的结点个数都达到了最大值
完全二叉树
在满二叉树的最底层自右至左依次（注意：不能跳过任何一个结点）去掉若干个结点得到的
二叉树也被称之为完全二叉树。满二叉树一定是完全二叉树，但完全二叉树不一定是满二
叉树。
完全二叉树的特点是：
（1）所有的叶结点都出现在最低的两层上。
（2）对任一结点，如果其右子树的高度为k，则其左子树的高度为k或k＋1。
53《信息技术》三色速记手册
二叉树的性质1
一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。
1层：结点个数 21-1=1个
2层：结点个数 22-1=2 个
3层：结点个数 23-1=4 个
二叉树的性质2
54
