第四章习题（P111-113）
一、 复习题
1、试述数据和数据结构的概念及其区别。
数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。（P93）
2、列出算法的五个重要特征并对其进行说明。
算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须有确切的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。（P95）
3、算法的优劣用什么来衡量？试述如何设计出优秀的算法。
时间复杂度空间复杂度（P97-98）
4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？
线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。（P99-105）
5、简述树与二叉树的区别；简述树与图的区别。
树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。（P102-P104）
6、请举出遍历算法在实际中使用的例子。
第4章 树结构
1.选择题
（1）C （2）C （3）B （4）B （5）B （6）C （7）C （8）D （9）A （10）D
（11）D （12）B （13）B （14）D （15）B
2.判断题
（1）√（2）√ （3）Ⅹ （4）Ⅹ（5）√ （6）Ⅹ（7）√ （8）√（9）√（10）Ⅹ
（11）Ⅹ（12）Ⅹ（13）√（14）Ⅹ（15）Ⅹ（16）Ⅹ（17）√（18）Ⅹ（19）Ⅹ（20）√
3.简答题
（1）一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？
【解答】
①二叉树是有序树，度为2的树是无序树，二叉树的度不一定是2。
②二叉树是有序树，每个结点最多有两棵子树，树是无
序树，且每个结点可以有多棵子树。
（2）对于图4-37所示二叉树，试给出：
1）它的顺序存储结构示意图；
2）它的二叉链表存储结构示意图；
3）它的三叉链表存储结构示意图。
【解答】
1）顺序存储结构示意图：
2）二叉链表存储结构示意图： 3）三叉链表存储结构示意图：
（3）对于图4-38所示的树，试给出：
1）双亲数组表示法示意图；
2）孩子链表表示法示意图；
3）孩子兄弟链表表示法示意图。 A B C D E F ^ ^ ^ G ^ ^ H A
D B
G E
H C
F
(图 4-37)
A
B C ^
^ D ^
E ^ ^ F
^ G ^ ^ H ^ A ^ B C ^
^ D ^ E ^ ^ F
^ G ^ ^ H ^
I D
E
F G C
B A
N
M
K J
H
(图 4-38)
【解答】
1）双亲数组表示法示意图： 2）孩子链表表示法示意图：
3）孩子兄弟链表表示法示意图：
（4）画出图4-39所示的森林经转换后所对应的二叉树，并指出森林中满足什么条件的
结点在二叉树中是叶子。
【解答】
A B
^ N ^ ^ H ^ C ^
^ G F E D
I
^
^
J
^
K ^
^
M ^
I
第1章 概论 数据结构作业答案
1 一、填空题
01、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的(关系和运算)等的学科。
02、数据结构被形式地定义为(D,R)，其中D是(数据元素)的有限集合，R是D上的(关系)有限集合。
03、数据结构包括数据的(逻辑结构)、数据的(存储结构)和数据的(运算)这三个方面的内容。
04、数据结构按逻辑结构可分为两大类，它们分别是(线性结构)和(非线性结构)。
05、线性结构中元素之间存在(一对一)关系，树形结构中元素之间存在(一对多)关系，图形结构中元素之间存在(多对多)关系。
06、在线性结构中，第一个结点(没有)前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点(没有)后续结点，其余每个结点有且只有1个后续结点。
07、在树形结构中，树根结点没有(前驱)结点，其余每个结点有且只有(1)个前驱结点；叶子结点没有(后续)结点，其余每个结点的后续结点数可以(任意多个)。
08、在图形结构中，每个结点的前驱结点数和后续结点数可以(任意多个)。
09、数据的存储结构可用四种基本的存储方法表示，它们分别是(顺序)、(链式)、(索引)、(散列)。
10、对于给定的n个元素，可以构造出的逻辑结构有(集合)、(线性结构)、(树形结构)、(图状结构)四种。
11、数据的运算最常用的有5种，它们分别是(插入)、(删除)、(修改)、(查找)、(排序)。
12、一个算法的效率可分为(时间)效率和(空间)效率。
13、数据结构中评价算法的两个重要指标是算法的(时间复杂度)和(空间复杂度)。
14、一个数据结构在计算机中的(映射)称为存储结构。
15、算法的五个重要特性是(有穷性)、(确定性)、(可行性)、输入、输出。
16、已知如下程序段
for (i=n; i>=1; i--) //语句1
{ x++; //语句2
数据结构与算法
第一节数据结构及算法概述
一、数据结构
图、四类基本结构的示意图
【要点】
1 .数据元素是数据的基本单位。
2 .数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
3 .4类基本的规律结构:集合、线性结构、树形结构和网状结构。
4 .4种数据存储方式：挨次、链式、索引和散列。
【例题•单选题】(2022年义省信用社聘请考试真题)下列说法不正确的是
()O
A.数据元素是数据的基本单位 B.数据项是数据中不行分割的最小标志单
位
C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成
『正确答案』D
『答案解析』数据元素是数据的基本单位，在计算机程序中通常被作为一个整体进
行考虑和处理。一个数据元素可由若干个数据项组成。数据项是不行分割的、含有独立
意义的最小数据单位。因此D选项不正确。
二、算法 O——O——O——O——O
⑹树型结构 ⑹线性结构
(d)图形结构 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令
表示一个或多个操作。
算法的特性：有穷性、确定性、可行性、输入和输出。
【要点】
评价算法优劣标准：正确性、可读性、健壮性、高效率与低存储量需求。
其次节线性表
线性表是n (n≥0)个数据元素al, a2,…，an组成的有限序列,n=0时称为
空表。
非空的线性表，有以下特征：
L有且仅有一个开头结点al,没有直接前趋，有且仅有一个直接后继a2。
2 .有且仅有一个终结结点an,没有直接后继，有且仅有一个直接前趋a-。
3 .其余的内部结点ai (2WiWnT)都有且仅有一个直接前趋a-和一个直接
后继3i+ι o
线性表的链式存储包括单链表、循环链表和双链表。
【留意】
与单链表的插入和删除操作不同的是，在双链表中插入和删除须同时修改两个
方向上的指针。
第三节栈和队列
一、栈
栈是一种“特别的”线性表，这种线性表中的插入和删除运算限定在表的某一
