下载文档原格式
数据结构各章概要数据结构是计算机科学中非常重要的一个学科，其主要研究各种数据的组织方式和操作方法。
善于运用合适的数据结构可以提高算法的效率，并优化程序的性能。
本文将对数据结构的各个章节进行概要介绍，帮助读者了解不同章节的主要内容和应用。
第一章：引论在引论章节，我们将引入数据结构的基本概念和术语，例如什么是数据、数据项、数据对象等等。
同时，还将介绍数据结构的分类和基本操作，如搜索、遍历、插入、删除和排序。
这些基础知识是后续章节的基础。
第二章：线性表线性表是数据结构中最简单、最基本的一种结构。
其特点是数据元素之间的前驱和后继关系非常明确。
线性表可以用数组和链表两种方式实现。
在本章节中，我们将分别介绍顺序表和链表的实现原理、插入、删除、合并以及应用场景。
第三章：栈和队列栈和队列是两种特殊的线性表结构，它们对数据的访问具有限制性。
栈具有“先进后出”的特点，而队列则具有“先进先出”的特点。
在本章节中，我们将介绍栈和队列的实现方式以及常见的应用场景，如递归、表达式求值、广度优先搜索等。
第四章：串串是由零个或多个字符组成的有限序列，其长度可以为零。
在本章节中，我们将介绍串的定义和操作，包括字符串的模式匹配、模式识别和编辑操作。
串的相关算法在文本处理、计算机网络等领域具有广泛的应用。
第五章：数组和广义表数组是一种在内存中以连续方式存储的数据结构，它具有高效的随机访问特性。
广义表是线性表的一种扩展，可以包含表结构、原子结构以及其他广义表。
本章节将介绍数组和广义表的定义、操作和应用。
第六章：树树是一种非线性的数据结构，具有分层次、递归和层次遍历等特点。
在本章节中，我们将介绍树的基本概念、二叉树、树的遍历算法、平衡树以及树的应用，如编译器中的语法树、文件系统的目录结构等。
第七章：图图是一种复杂的非线性数据结构，由顶点集合和边集合组成。
在本章节中，我们将介绍图的各种表示方式，图的遍历算法、最短路径算法以及常用的图算法，如最小生成树算法和拓扑排序。
《数据结构与算法》第二部分习题精选一、下面是有关二叉树的叙述，请判断正误（）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（）2.二叉树中每个结点的两棵子树的高度差等于1。
（）3.二叉树中每个结点的两棵子树是有序的。
（）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
（）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。
（）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。
（）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
（√）10. 具有12个结点的完全二叉树有5个度为2的结点。
二、填空1．由３个结点所构成的二叉树有种形态。
2. 一棵深度为6的满二叉树有个分支结点和个叶子。
3．一棵具有２５７个结点的完全二叉树，它的深度为。
4.设一棵完全二叉树有700个结点，则共有个叶子结点。
5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。
6.一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。
7. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。
因而二叉树的遍历次序有六种。
最常用的是三种：前序法（即按N L R次序），后序法（即按次序）和中序法（也称对称序法，即按L N R次序）。
这三种方法相互之间有关联。
若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。
8.中序遍历的递归算法平均空间复杂度为。
9.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是。
一、基础知识题6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。
【解答】设度为m的树中度为0,1,2,…,m的结点数分别为n0, n1, n2,…, nm，结点总数为n，分枝数为B，则下面二式成立n= n0+n1+n2+…+nm (1)n=B+1= n1+2n2 +…+mnm+1 (2)由(1)和(2)得叶子结点数n0=1+即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=86.2一棵完全二叉树上有1001个结点，求叶子结点的个数。
【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则n= n0+ n1+ n2n=2n0+n1-11002=2n0+n1由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。
本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，……。
虽然解法也对，但步骤多且复杂，极易出错。
6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。
【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。
6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。
【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。
若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。
6.5 某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。
第六章 树和二叉树一、选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D.-+A*BC/DE【北京航空航天大学 1999 一、3 （2分)】2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】A ．ab+cde/*B ．abcde/+*+C ．abcde/*++D 3. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D ．8【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（ ）【南京理工大学 1999 一、4 （1分）】①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A ．①②③B ．②③④C ．②④D ．①④6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ）A ．m-nB ．m-n-1C ．n+1D ．条件不足，无法确定 【南京理工大学2000一、17（1.5分）】7. 树是结点的有限集合，它（ (1）)根结点，记为T 。
其余结点分成为m （m>0）个(（2）)的集合T1，T2， …，Ｔm ，每个集合又都是树，此时结点T 称为Ti 的父结点，Ti 称为T的子结点（1≤i ≤m ）。
第6章树和二叉树一、选择题1.有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（ D ）A、向量B、树C、图D、二叉树2.树最适合用来表示（ B ）A、有序数据元素B、元素之间具有分支层次关系的数据C、无序数据元素D、元素之间无联系的数据3.树B 的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C ）A、1a(2b(3d,3e),2c)B、a(b(D,e),c)C、a(b(d,e),c)D、a(b,d(e),c)4.对二叉树的结点从1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ B ）次序的遍历实现二叉树的结点编号。
A、先序B、中序C、后序D、从根开始按层次遍历5.按照二叉树的定义，具有3 个结点的二叉树有（C ）种。
A、3B、4C、5D、66.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高度为（），其叶结点数为（）；树的最小高度为（），其叶结点数为（）；若采用链表存储结构，则有（）个空链域。
log+1 C、log2n D、nA、n/2B、⎣⎦n2E、n0+n1+n2F、n1+n2G、n2+1H、1I、n+1 J、n1K、n2L、n1+17.对一棵满二叉树，m 个树叶，n 个结点，深度为h，则（ D ）A、n=m+hB、h+m=2nC、m=h-1D、n=2h-18.设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（ A ），至多为（D ）。
A、2hB、2h-1C、2h-1D、2h-19.在一棵二叉树上第5 层的结点数最多为（B）（假设根结点的层数为1）A、8B、16C、15D、3210.深度为5 的二叉树至多有（ C ）个结点。
A、16B、32C、31D、1011.一棵有124 个叶结点的完全二叉树，最多有（B ）个结点A、247B、248C、249D、25012.含有129 个叶子结点的完全二叉树，最少有（ B ）个结点A、254B、255C、256D、25713.假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ D ）个。
第6章 树和二叉树（参考答案）6.1(1)根结点a6.2三个结点的树的形态： 三个结点的二叉树的形态：（1） （1） （2） （4） （5）6．3 设树的结点数是n ，则n=n0+n1+n2+……+nm+ (1)设树的分支数为B ，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m-1)nm+16.4(1) k i-1 (i 为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(4) (n-1)%k !=0; 其右兄弟的编号 n+16.5（1）顺序存储结构注：#为空结点6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)// bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度{ int bl,br; // 局部变量，分别表示二叉树左、右子树的高度if (bt==null) return(0);else { bl=height(bt->lchild);br=height(bt->rchild);return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） }}// 算法结束6.9void preorder(cbt[],int n,int i);// cbt是以完全二叉树形式存储的n个结点的二叉树，i是数// 组下标，初始调用时为1。
本算法以非递归形式前序遍历该二叉树{ int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0if (n<=0) { printf(“输入错误”);exit（0）；}while (i<=n ||top>0){ while(i<=n){visit(cbt[i]); // 访问根结点if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈i=2*i;// 先序访问左子树}if (top>0) i=s[top--]; // 退栈，先序访问右子树} // END OF while (i<=n ||top>0)}// 算法结束//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i);// bt是以完全二叉树形式存储的一维数组，n是数组元素个数。
习题六树和二叉树一、单项选择题1．以下说法错误的是 ( )A．树形结构的特点是一个结点可以有多个直接前趋B．线性结构中的一个结点至多只有一个直接后继C．树形结构可以表达(组织)更复杂的数据D．树(及一切树形结构)是一种"分支层次"结构E．任何只含一个结点的集合是一棵树2．下列说法中正确的是 ( )A．任何一棵二叉树中至少有一个结点的度为2B．任何一棵二叉树中每个结点的度都为2C．任何一棵二叉树中的度肯定等于2D．任何一棵二叉树中的度可以小于23．讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储C．将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义4．树最适合用来表示 ( )A．有序数据元素 B．无序数据元素C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。
与森林F 对应的二叉树根结点的右子树上的结点个数是（）。
A．M1 B．M1+M2 C．M3 D．M2+M37．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A． 250 B． 500 C．254 D．505 E．以上答案都不对8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )A．不确定 B．2n C．2n+1 D．2n-19．二叉树的第I层上最多含有结点数为（）A．2I B． 2I-1-1 C． 2I-1 D．2I -110．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+111. 利用二叉链表存储树，则根结点的右指针是（）。
A．指向最左孩子 B．指向最右孩子 C．空 D．非空12．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。
