下载文档原格式
数据结构（⼆⼗四）⼆叉树的链式存储结构（⼆叉链表） ⼀、⼆叉树每个结点最多有两个孩⼦，所以为它设计⼀个数据域和两个指针域，称这样的链表叫做⼆叉链表。
⼆、结点结构包括：lchild左孩⼦指针域、data数据域和rchild右孩⼦指针域。
三、⼆叉链表的C语⾔代码实现：#include "string.h"#include "stdio.h"#include "stdlib.h"#include "io.h"#include "math.h"#include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 100 /* 存储空间初始分配量 */typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 *//* ⽤于构造⼆叉树********************************** */int index=1;typedef char String[24]; /* 0号单元存放串的长度 */String str;Status StrAssign(String T,char *chars){int i;if(strlen(chars)>MAXSIZE)return ERROR;else{T[0]=strlen(chars);for(i=1;i<=T[0];i++)T[i]=*(chars+i-1);return OK;}}/* ************************************************ */typedef char TElemType;TElemType Nil=''; /* 字符型以空格符为空 */Status visit(TElemType e){printf("%c ",e);return OK;}typedef struct BiTNode /* 结点结构 */{TElemType data; /* 结点数据 */struct BiTNode *lchild,*rchild; /* 左右孩⼦指针 */}BiTNode,*BiTree;/* 构造空⼆叉树T */Status InitBiTree(BiTree *T){*T=NULL;return OK;}/* 初始条件: ⼆叉树T存在。
数据结构试卷（一）一、选择题(30分)1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。
(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。
(A) 2k-1(B) 2k(C) 2k-1(D) 2k-13．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。
(A) n(B) e(C) 2n(D) 2e4．在二叉排序树中插入一个结点的时间复杂度为（）。
(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。
(A) n(B) n-1(C) m(D) m-16．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。
(A) 3(B) 4(C) 5(D) 87．设用链表作为栈的存储结构则退栈操作（）。
(A) 必须判别栈是否为满(B) 必须判别栈是否为空(C) 判别栈元素的类型(D) 对栈不作任何判别8．下列四种排序中（）的空间复杂度最大。
(A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（）。
(A) N0=N1+1(B) N0=N l+N2(C) N0=N2+1(D) N0=2N1+l10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。
(A) log2n+1(B) log2n-1(C) log2n(D) log2(n+1)二、填空题(42分)1．1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。
二叉树的储存结构的实现及应用二叉树是一种常见的数据结构，它在计算机科学和算法设计中广泛应用。
二叉树的储存结构有多种实现方式，包括顺序储存结构和链式储存结构。
本文将从这两种储存结构的实现和应用角度进行详细介绍，以便读者更好地理解二叉树的储存结构及其在实际应用中的作用。
一、顺序储存结构的实现及应用顺序储存结构是将二叉树的节点按照从上到下、从左到右的顺序依次存储在一维数组中。
通常采用数组来实现顺序储存结构，数组的下标和节点的位置之间存在一定的对应关系，通过数学计算可以快速找到节点的父节点、左孩子和右孩子。
顺序储存结构的实现相对简单，利用数组的特性可以迅速随机访问节点，适用于完全二叉树。
1.1 实现过程在采用顺序储存结构的实现中，需要首先确定二叉树的深度，然后根据深度确定数组的长度。
通过数学计算可以得到节点间的位置关系，初始化数组并按照规定的顺序将二叉树节点逐一填入数组中。
在访问二叉树节点时，可以通过计算得到节点的父节点和子节点的位置，从而实现随机访问。
1.2 应用场景顺序储存结构适用于完全二叉树的储存和遍历，常见的应用场景包括二叉堆和哈夫曼树。
二叉堆是一种特殊的二叉树，顺序储存结构可以方便地实现它的插入、删除和调整操作，因此在堆排序、优先队列等算法中得到广泛应用。
哈夫曼树则是数据压缩领域的重要应用，通过顺序储存结构可以有效地构建和处理哈夫曼树，实现压缩编码和解码操作。
二、链式储存结构的实现及应用链式储存结构是通过指针将二叉树的节点连接起来，形成一个类似链表的结构。
每个节点包含数据域和指针域，指针域指向节点的左右孩子节点。
链式储存结构的实现相对灵活，适用于任意形态的二叉树，但需要额外的指针空间来存储节点的地址信息。
2.1 实现过程在链式储存结构的实现中，每个节点需要定义为一个包含数据域和指针域的结构体或类。
通过指针来连接各个节点，形成一个二叉树的结构。
在树的遍历和操作中，可以通过指针的操作来实现节点的访问和处理，具有较高的灵活性和可扩展性。
二叉树的顺序存储及基本操作二叉树的顺序存储是将树中的节点按照完全二叉树从上到下、从左到右的顺序依次存储到一个一维数组中，采用这种方式存储的二叉树也被称为完全二叉树。
一、在使用顺序存储方式时，可以使用以下公式来计算一个节点的左右子节点和父节点：
1. 左子节点：2i+1（i为父节点的在数组中的下标）
2. 右子节点：2i+2
3. 父节点：(i-1)/2（i为子节点在数组中的下标）
二、基本操作：
1. 创建二叉树：按照上述公式将节点存储到数组中。
2. 遍历二叉树：可采用递归或非递归方式，进行前序、中序、后序、层次遍历。
3. 插入节点：先将节点插入到数组末尾，然后通过比较节点和其父节点的大小，进行上浮操作直到满足二叉树的性质。
4. 删除节点：先将待删除节点和最后一个节点交换位置，然后通过比较交换后的节点和其父节点的大小，进行下沉操作直到满足二
叉树的性质。
5. 查找节点：根据节点值进行查找，可采用递归或非递归方式。
6. 修改节点：根据节点值进行查找，然后进行修改操作。
数据结构复习重点谁让我找到你们了.第一章1.数据是信息的载体,它能够被计算机识别、存储和加工处理。
2.数据元素是数据的基本单位。
有些情况下，数据元素也称为元素、结点、顶点、记录。
3.数据结构指的是数据之间的相互关系，即数据的组织形式。
一般包括三个方面的内容：①数据元素之间的逻辑关系，也称为数据的逻辑结构；②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构；③数据的运算，即对数据施加的操作。
4.数据类型是一个值的集合以及在这些值上定义的一组操作的总称。
按"值"是否可分解，可将数据类型划分为两类：①原子类型，其值不可分解；②结构类型，其值可分解为若干个成分。
5.抽象数据类型是指抽象数据的组织和与之相关的操作。
可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。
6.数据的逻辑结构简称为数据结构。
数据的逻辑结构可分为两大类：①线性结构(~的逻辑特征是若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继)；②非线性结构(~的逻辑特征是一个结点可能有多个直接前趋和直接后继)。
7.数据存储结构可用四种基本的存储方法表示：①顺序存储方法(该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储表示称为顺序存储结构)；②链接存储方法(该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。
由此得到的存储表示称为链式存储结构)；③索引存储方法(该方法通常是在存储结点信息的同时，还建立附加的索引表)；④散列存储方法(该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址)。
8.非形式地说，算法是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值为输出。
因此，一个算法是一系列将输入转换为输出的计算步骤。
9.求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢?选用的算法首先应该是"正确"的。
全国计算机等级考试四级复习纲要：树和二叉树(2)二叉树的顺序存储结构二叉树的顺序存储结构由一个一维数组构成，二叉树上的结点按某种次序分别存入该数组的各个单元。
显然，这里的关键在于结点的存储次序，这种次序应能反映结点之间的逻辑关系(父子关系)，否则二叉树的基本运算就难以实现。
由二叉树的性质5可知，若对任一完全二叉树上的所有结点按层编号，则结点编号之间的数值关系可以准确地反映结点之间的逻辑关系。
因此，对于任何完全二叉树来说，可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。
具体地说就是:将编号为i的结点存入一维数组的第i个单元。
在这一存储结构中，由于一结点的存储位置(即下标)也就是它的编号，故结点间的逻辑关系可通过它们下标间的数值关系确定。
(3)双亲表示法树上每个结点的孩子可以有任意多个，但双亲只有一个。
因此，通过指向双亲的指针而将树中所有结点组织在一起形成一种存储结构是十分简法的。
树的这种存储表示方法称为双亲表示法。
在双亲表示法下，每个存储结点由两个域组成:数据域———用于存储树上结点中的数据元素;“指针”域———用于指示本结点之双亲所在的存储结点。
值得注意的是，“指针”域的类型定义可以有两种选择。
第一种是将其定义为高级语言(如C语句)中的指针类型。
通过将存储结点中的指针域定义为高级语言中的指针类型，就得到各种链式存储结构，如单链表、二叉链表、孩子链表等等。
第二种选择是将“指针”域定义为整型、子界型等型。
严格地说，无论选择上述哪种定义，得到的都是链式存储结构，因为在这两种定义之下，各存储结点之间的联结是通过“指针”完成的，而且这些指针反映了结点之间的逻辑关系。
为了区别这两种链式结构，通常将指针域定义为高级语言中的指针类型的各种链式存储结构(如单链表、二叉链表等等)称为“动态链表”，相应的指针称为“动态指针”;将指针域定义为整型、子界型等类型的各种键式存储结构称为“静态链表”，相应的“指针”称为:“静态指针”。
数据结构基本概念练习题1、选择练习题1）执行下面程序段时，执行S语句的次数为-------for(int I=1;I<=n;I++)for(int j=1;j<=I;j++)S;(A) n^2 (B) n^2/2 (C) n(n+1) (D) n(n+1)/2答案：D2）算法是指令的有限序列，其中每一条指令表示一个或多个操作。
下列______不属于算法的五个特性之一。
(A) 有一或多个输出(B) 有零或多个输入(C) 有穷性(D) 通俗易懂性答案：D3）若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
(A) 顺序表(B) 双链表(C) 带头结点的双循环链表(D) 单循环链表答案：A4）下面的叙述正确的是（）(A) 线性表在链式存储时，查找第i个元素的时间同i的值成正比;(B) 线性表在链式存储时，查找第i个元素的时间同i的值无关;(C) 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比;(D) 以上说法都不对.答案：A5) 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。
(A) 单链表(B) 顺序表(C) 单向循环链表(D) 双链表答案：B6) 在双向链表指针p指向的结点前插入一个指针q指向的结点操作是( )。
(A) p->prior=q;q->next=p;p->prior->next=q;q->prior=q;(B) p->prior=q;p->prior->next=q;q->next=p;q->Prior=p->prior;(C) q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;(D) q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;答案：C7) 设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。
一、判断（每小题 1 分，共 10 分）1．数据的存储结构是数据的逻辑结构的存储映象，不仅要存储数据元素的值，还要存储元素之间的相互关系。
2．用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。
3．完全二叉树的叶子结点只能出现在最后一层上。
4．折半查找方法要求待查表必须是有序的顺序表。
5．在有向图 G 中， <V 2 ， V 1 > 和 <V 1 ， V 2 > 是两条不同的边。
6．图的最小生成树是唯一的。
7．从循环单链表的某一结点出发，只能找到它的后继结点，不能找到它的前趋结点。
8．在单链表中，头结点是必不可少的。
9．对快速排序来说，初始序列为正序和反序，都是最坏情况。
10．广义表是特殊的线性表。
二、选择（每题 1 分，共 15 分）1．设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S 。
若每个元素出栈后立即进入队列 Q ，且 7 个元素出队的顺序是 bdcfeag ，则栈 S 的容量至少是（）。
A．1 B．2 C．3 D．42．下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是( )。
3．已知广义表 A= （（ a,b ） ,(c,d) ） , 则 head(A) 等于 ( )。
A．(a,b) B．((a,b)) C．a,b D．a4．设字符串 s1='ABCDEFG',s2='PQRST', 则运算 s=strcat(strsub(s1,2, strlen(s2)),strsub (s1,strlen(s2),2)) 后结果为（）。
A．BCQR B．BCDEF C．BCDEFG D．BCDEFEF5．具有 8 个顶点的连通图的深度优先生成树，其边数为（）。
A．8 B．9 C．7 D．66．算法分析的两个主要方面是（）。
A．空间复杂性和时间复杂性 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性7．下列四种排序中（）的空间复杂度最大。
数据结构习题和答案习题课填空1、对于⼀棵⼆叉树，若⼀个结点的编号为i，则它的左孩⼦结点的编号为，双亲结点的编号为。
2、向⼀个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。
3、在⼀棵⼆叉树中，若双分⽀结点数为5个，单分⽀结点数为6个，则叶⼦结点数为个。
4、为了实现折半查找，线性表必须采⽤⽅法存储。
顺序5、⼀种抽象数据类型包括数据对象和。
6、在以L为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为__________和_______。
7、数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。
8、队列的插⼊操作在进⾏，删除操作在进⾏。
9、⼆叉搜索树的中序遍历得到的结点序列为____ ____。
10、在顺序表中插⼊或删除⼀个元素，需要平均移动元素，具体移动的元素个数与有关。
11、栈的特点是。
12、在单链表中，除了⾸元结点外，任⼀结点的存储位置由。
13、在⼀个具有n个顶点的⽆向图中，要连通所有顶点则⾄少需要条边。
14、深度为k（设根的层数为1）的完全⼆叉树⾄少有个结点，⾄多有个结点。
15、⼀棵深度为6的满⼆叉树有个分⽀结点和个叶⼦结点。
16、⼀个算法的效率可分为效率和效率。
17、队列的特点是。
18、⼀棵深度为5的满⼆叉树中的结点数为个。
19、在⼀个具有n个顶点的⽆向完全图中，包含有________条边，在⼀个具有n个顶点的有向完全图中，包含有________条边。
简答题1、已知⼀组元素为（38，26，62，94，35，50，28，55），画出按元素排列顺序输⼊⽣成的⼀棵⼆叉搜索树。
答:2、假设有⼆维数组A[0..5,0..7]，每个元素⽤相邻的6个字节存储，存储器按字节编址。
已知A的起始存储位置（基地址）为1000，计算：（1）末尾元素A57的第⼀个字节地址为；（2）若按列存储时，元素A47的第⼀个字节地址为。
(3) 数组A的体积（存储量）；(4) 若按⾏存储时，元素A14的第⼀个字节地址为。
数据结构综合题部分参考答案（仅供参考）一、填空1、一个算法的效率可分为_____时间_________效率和______空间________效率。
，2、栈的特点是_____先进后出______,队列的特点是_____先进先出________。
、3、在线性表的顺序存储结构中，若每个元素占L个存储单元，则第i个元素ai的存储位置为LOC(ai)=LOC(a1)+ ____（i-1）*L________。
4、已知一棵完全二叉树共139个结点，按照层次从左到右进行编号，根结点编号为1，则编号为60的左孩子编号为_____120_________右孩子编号为____121__________双亲编号为____30__________。
、、5、已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：__ s->next=p->next; p-next=s;___。
6、在各种查找方法中,平均查找长度与结点个数n无关的查法方法是______哈希表查找法________。
7、算法时间复杂度的分析通常有两种方法，即__事后统计_________和___事前估计________的方法，通常我们对算法求时间复杂度时，采用后一种方法。
8、已知元素序列E,F,G,H,I,J,K,L,M,N经过操作XXYXXYXYXYYXXYXYYYXY以后的出栈序列（注X表示入栈，Y表示出栈）_____ FHIJGLMKEN _________。
9、设数组A[1..10,1..8]的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素A[4,5]的存储地址为____2056_______；若以列序为主序顺序存储,则元素A[4,5]的存储地址为_2086______。
10、一个二叉树中叶子结点3个，度为1的结点4个，则该二叉树共有___9____个结点。
11、在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的__度_____,对于有向图来说等于该顶点的____出度_____。
二叉树结构的特点二叉树是一种常见的数据结构，它具有以下特点：1. 结构简单：二叉树是一种有序树结构，每个节点最多只有两个子节点，分别称为左子节点和右子节点。
这种结构的简洁性使得二叉树在实际应用中得到广泛使用。
2. 层次性：二叉树具有明显的层次性，即树的每一层都可以通过节点间的父子关系来确定。
根节点是第一层，根节点的子节点是第二层，以此类推。
3. 有序性：在二叉树中，每个节点的左子节点小于它，右子节点大于它。
这种有序性使得二叉树在查找和排序方面具有很高的效率。
4. 高度平衡：二叉树的高度平衡性是指树的左右子树的高度差不超过1。
高度平衡的二叉树可以保证查找、插入和删除操作的平均时间复杂度为O(log n)。
5. 递归性：二叉树的定义是递归的，即每个子树都是二叉树。
这种递归性质使得在二叉树上的操作可以通过递归算法来实现。
6. 存储结构灵活：二叉树的存储结构可以采用顺序存储和链式存储两种方式。
顺序存储是将二叉树的节点按照层次顺序存储在一维数组中，链式存储是通过每个节点的指针来连接各个节点。
在二叉树的基础上，还可以扩展出以下几种特殊的二叉树结构：1. 完全二叉树：完全二叉树是指除了最后一层外，其他层的节点个数都达到最大值，并且最后一层的节点依次从左到右排列。
完全二叉树的特点是高度平衡，可以用数组来存储。
2. 满二叉树：满二叉树是指每个节点都有两个子节点的二叉树，即除了叶子节点外，每个节点都有两个子节点。
满二叉树的特点是节点个数达到最大值，高度平衡。
3. 平衡二叉树：平衡二叉树是指任意节点的左右子树的高度差不超过1的二叉树。
平衡二叉树的特点是高度平衡，可以保证各种操作的时间复杂度较低。
4. 二叉搜索树：二叉搜索树是一种特殊的二叉树，它具有以下性质：对于树中的任意节点，其左子树中的节点值都小于它，右子树中的节点值都大于它。
二叉搜索树的特点是可以高效地进行查找、插入和删除操作。
5. 线索二叉树：线索二叉树是对二叉树的一种扩展，它的特点是在每个节点上增加了指向前驱节点和后继节点的指针。
第6章树6.1选择题1．一棵具有n个结点的完全二叉树的树高度（深度）是（）A）⎣log2n⎦+1 B）log2n +1 C）⎣ log2n ⎦D）log2n-12．有关二叉树下列说法正确的是（）A）二叉树的度为2 B）一棵二叉树的度可以小于2C）二叉树中至少有一个结点的度为2 D）二叉树中任何一个结点的度都为23．二叉树的第I层上最多含有结点数为（）A）2I B）2I-1-1 C）2I-1 D）2I-14．具有10个叶结点的二叉树中有（）个度为2的结点A）8 B）9 C）10 D）115．在下述结论中，正确的是（）①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A）①②③B）②③④C）②④D）①④6．由3 个结点可以构造出多少种不同的二叉树？（）A）2 B）3 C）4 D）57．引入二叉线索树的目的是（）A）加快查找结点的前驱或后继的速度B）为了能在二叉树中方便的进行插入与删除C）为了能方便的找到双亲D）使二叉树的遍历结果惟一8．有n个叶子的哈夫曼树的结点总数为（）A）不确定B）2n C）2n+1 D）2n-19．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A）所有的结点均无左孩子B）所有的结点均无右孩子C）只有一个叶子结点D）是任意一棵二叉树10．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A）250 B）500 C）505 D）以上答案都不对11．已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则它的先序遍历序列为（）A）ACBED B）DECAB C）DEABC D）CEDBA12．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A）9 B）11 C）15 D）不确定13．利用二叉链表存储树时，根结点的右指针是（）A）指向最左孩子B）指向最右孩子C）空D）非空14．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。
数据结构：一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
数据：数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。
数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据类型：是一个值的集合和定义在此集合上一组操作的总称。
包括原子类型：其值不可在分的数据类型结构类型：其值可以在分解为若干成分的数据类型抽象数据类型：ADT，指一个数学模型以及定义在该模型上的一组操作。
通常用数据对象、数据关系、基本操作集这样的三元组来表示。
有数据抽象和数据封装两个重要特性。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
包括（逻辑结构、存储结构和数据的运算）。
数据的逻辑结构：指数据元素之间的逻辑关系。
包括集合、线性结构、树形结构、图状结构或网状结构。
数据的存储结构：指数据结构在计算机中的表示，也成物理结构。
主要有顺序存储、连接存储、索引存储、散列存储。
数据的运算：施加在数据上的运算包括运算的定义和实现。
定义是针对逻辑结构，指出运算的功能。
实现是针对存储结构的，指出运算的具体操作步骤。
算法：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
有5个重要特性（有穷性、确定性、可行性、输入、输出）算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求。
时间复杂度：一般情况下，算法中基本操作的重复次数是问题规模n的某个函数f（n），算法的时间度量记作T（n）=O（f（n）），表示随着问题规模n的增大，算法执行时间增长率和f（n）的增长率相同，称为时间复杂度。
空间复杂度：S（n）定义为该算法所耗费的村粗空间，是问题规模n的函数。
第二章：线性表线性表：具有相同数据类型的n（n>=0）个数据元素的有限序列。
线性表的顺序存储又称顺序表；链式存储又称单链表。
静态链表：借助数组来描述线性表的链式存储结构，结点也有数据域和指针域。
判断题，在每小题前面打对号表示正确或打叉号表示错误1. 数据的逻辑结构与数据元素本身的内容和形式无关。
对2. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
对3. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历和按层遍历时具有相同的结果。
对4. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。
错5. 邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。
错6. 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。
对7. 向一棵B树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。
错8. 算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。
错9. 用字符数组存储长度为n的字符串，数组长度至少为n+1。
对10. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
对11. 邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。
错12. 对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。
对13. 在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。
错14. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。
对15. 线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
对16. 在线性链表中删除结点时，只需要将被删结点释放，不需要修改任何指针。
错17. 在用单链表表示的链式队列Q中，假定队头指针为Q->front，队尾指针为Q->rear，则链队为空的条件为Q->front==Q->rear。
错18. 一棵AVL树的所有叶结点不一定在同一层次上，同样，平衡的m路搜索树的叶结点也不一定在同一层次上。
对19. 一个广义表((a),((b),c),(d))的表尾是“((b),c),(d)”。
1
完全二叉树的顺序存储
#include<iostream.h>
#include<string.h>
class treenode { public:
char data; int left, right, parent;
treenode(){left=right=parent=-1;} };
int n; //全局变量
void creattree(char a[],treenode t[]) //建二叉树
{ for(int i=0;a[i]!='\0';i++)
{ t[i].data=a[i]; if(2*i+1<n) t[i].left=2*i+1; if(2*i+2<n) t[i].right=2*i+2; if(i!=0) t[i].parent=(i-1)/2; } } void searchchild(char x,treenode t[]) //寻找子节点 { for(int i=0;i<n;i++) if(t[i].data==x)
{ if(t[i].left==-1 && t[i].right==-1) //专对根节点的处理 cout<<x<<"无子节点"<<'\n'; else { if(t[i].left!=-1) cout<<x<<"的左子节点为:"<<t[t[i].left].data<<'\n'; f(t[i].right!=-1) cout<<x<<"的右子节点为:"<<t[t[i].right].data<<'\n'; if(t[i].left!=-1&&t[i].right==-1) cout<<x<<"无右子节点"<<endl; } break; } }
void searchparent(char x,treenode t[]) //寻找父节点 { for(int i=0;i<n;i++) if(t[i].data==x) { if(t[i].parent!=-1) cout<<x<<"的父节点为:"<<t[t[i].parent].data<<'\n'; else cout<<x<<"无父节点"<<'\n'; break; }
if(i>=n) cout<<"该树中无"<<x<<"此节点!"<<'\n'; } void searchbrother(char x,treenode t[]) //寻找兄弟节点 { for(int i=0;i<n;i++) if(t[i].data==x) { if(i==0) cout<<x<<"无兄弟"<<'\n'; //专对根节点的处理 else { if(i%2==0) cout<<x<<"的左兄弟为:"<<t[i-1].data<<'\n';
if(i%2!=0 && i+1<n)
cout<<x<<"的右兄弟为:"<<t[i+1].data<<'\n';
a[] left data right parent
0 1 A 2 -1
1 3 B 4 0
2 5 C 6 0
3 7 D -1 1
4 -1 E -1 1
5 -1 F -1 2
6 -1 G -1 2
7 -1 H -1 3
2
if(i%2==0 && i+1==n) //专对最后只有左节点的处理
cout<<x<<"无右兄弟"<<'\n'; } break; } }
void preorder(int r,treenode t[]) //前序遍历 { if(r<n) { cout<<t[r].data<<'\t'; preorder(2*r+1,t); preorder(2*r+2,t); } } void postorder(int r,treenode t[])//后序遍历 { if(r<n) { postorder(2*r+1,t); postorder(2*r+2,t); cout<<t[r].data<<'\t'; } } void main() { char a[20]; char x;
cout<<"请连续输入构成完全二叉树的各节点:"; cin>>a;
int size=strlen(a);n=size; //计算字符串的长度，赋值给全局变量n 。
treenode t[10]; //要输入的字符数需小于等于10 cout<<"请输入要查找的字符:"; cin>>x; creattree(a,t); int r=0; //从第一个节点开始遍历
cout<<'\n'<<"前序遍历结果为:"; preorder(r,t); cout<<'\n'; cout<<"中序遍历结果为:"; inorder(r,t); cout<<'\n'; cout<<"后序遍历结果为:"; postorder(r,t); cout<<'\n'; cout<<'\n'; searchchild(x,t); searchparent(x,t); searchbrother(x,t); }
结果如下：
void inorder(int r,treenode t[]) { if(r<n) { inorder(2*r+1,t); cout<<t[r].data<<'\t'; inorder(2*r+2,t); } } //中序遍历 请连续输入构成完全二叉树的各节点:ABCDEFGH 请输入要查找的字符:A
前序遍历结果为:A B D H E C F G 中序遍历结果为:H D B E A F C G 后序遍历结果为:H D E B F G C A
A 的左子节点为：
B A 的右子节点为：
C A 无父节点 A 无兄弟
请连续输入构成完全二叉树的各节点:ABCDEFGH 请输入要查找的字符:B
前序遍历结果为:A B D H E C F G 中序遍历结果为:H D B E A F C G 后序遍历结果为:H D E B F G C A
B 的左子节点为：D B 的右子兄弟为：E B 的父节点为：A B 的右兄弟为：C
A / \
B
C / \ / \
D
E
F
G / H
A / \
B C
/ \ / \ D E F G /
H。
