1. 一个算法应该具有以下几个五个特征：（有穷性）（确定性）（输入）（输出）（可行性）
2. 算法的复杂度有（时间）和（空间）之分
3. 数据结构指的是数据之间的相互关系，，既数据的组织形式，一般包括三个方面的内容（逻辑结构）（存储结构）（数据的运算）
4. （数据元素）是数据的基本单位
5. （算法的复杂度）是算法效率的度量，是评价算法优势的重要依据
6. （结构）是元素之间的关系的集合
7. 通常来说，一个数据结构的DS 可以表示为一个（二元组）
8. 最常用的数据结构是（数组结构）和（记录结构）
9. 算法设计策略有（递归技术）（分治法）（模拟法）（贪心算法）（随机算法）（动态规划）（状态空间）（搜索法）
10. 现实世界中的事物及联系在数据世界中用（数据模型）描述
11. 数据元素之间的逻辑关系，也称（数据的逻辑结构）
12. 数据的逻辑结构可以形式的用一个二元组B=（K ，R ）来表示，其中K 是（结点的有穷集合）R 是*（K 上关系的有穷集合）
13. 一个数据元素可以有若干个（数据项）组成
14. （数据项）是具有独立含义的最小表示单位
15. （数据的运算）既对数据施加的操作
16. (数据的逻辑结构) 可以看做是从具体问题抽象出来的数学模型
17. 数据元素及其关系在计算机存储内的表示称为（数据的存取结构）
18. 数据的存储结构是逻辑结构用（计算机语言）的实现
19. 对机器语言而言，存储结构是具体的。一般只在（高级语言）层次上讨论存储结构
20. 所谓（抽象的操作），是只知道这些操作是“做什么”，而无需考虑：如何做；
21. 较早的软件开发用结构法程序设计方法。程序的定律是; 程序=（算法）+（数据结构）
22. 算法是一个独立的整体，数据结构也是一个独立的整体俩者分开设计以（算法）为主；’
23. 数据结构是介于（数学）（计算机硬件）（计算机软件）三者之间的一门核心课程
24. 数据的范畴包括（整数）（实数）（字符串）（图像）和（声音）
25. 下面程序的时间复杂度为）（0（sqrt （n ）））
Void prime(int n)
{ for(i=2;((n%i)!=)0&&(i
If(i>sqart(n))
Printf(“%d is a prime number”,n);
Else print(“%d is a prime number”,n); }
26. 下面程序的时间复杂度为（0（n ））
Float suml (int n)
{ p=1;suml=0;
For(i=1;i
{p=p*i;suml=suml+p; }}
27. 下面的时间复杂度为（0（n^2））
Float sum2(int n)
{ sum2=0;
For{i=1;i
} p=1;
For(j=1;j
Sum2=sum2+p; }}
1. 顺序存储的线性表，设其长度为n 。在任何位置上插入或删除操作的时间代价基本上都是等效的。则插入一个元素大约需要移动表中的（n(n+1)/2 ）个元素，删除一个元素时大约要移动表中的（ n(n-1)/2 ） 个元素。
2. 线性表的存储结构可以分为（线性存储结构）和（链式存储结构）。
3. 若要在一个不带表头结点的单链表的首结点*P结点之前插入一个*S结点时，可执行下列操作：
（1）s->next= p->next ;
(2) p->next=s;
(3)t=p->data;
(4)p->data= s->data ;
(5)s->data= t ;
4. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为（单链表）和（双链表）；而根据指针的联系方式，链表又可分为（非循环链表）和（循环链表）
5. 对于线性表的顺序存储，需要预先分配好存储空间。若分配太多容易造成存储空间的（浪费），若分配太少又容易在算法中造成（上溢），因而只适用于数据量变化不大的情况；对于线性表的链接存储，不需要（预先分配）存储空间，存储器中的整个（空间）都可供使用，分配和回收结点都非常方便，能有效的利用存储空间，在算法中不必考虑（上溢）的发生，因而适用于数据量变化较大的情况。
7. （双向）链表适合从指点结点开始，寻找直接前趋的运算。
8. 当一个线性表经常进行存取操作而很少进行插入和删除操作时，则采用（顺序）存储结构为宜，相反，当经常进行的是插入和删除操作时，则采用（链接）存储结构为宜。
9. 在单链表中设置头结点的作用是（使空表和非空表统一，算法处理一致）。
10. 顺序表中逻辑上相邻的元素物理位置（一定）紧邻，单链表中逻辑上相邻的元素物理位置（不一定）紧邻。
11. 如果线性表的存储空间变化较大，则适用（链）表。
12. 在链表中，每个结点中含8个字符，1个指针域。其中每个字符占1个字节，每个指针占4个字节。则该结点的存储密度是（2/3）。
13. 当向一个顺序表插入一个元素时，从插入位置开始向后的所有元素均（后移）一个位置，移动过程是从（后）向（前）依次移动没一个元素。
14. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需（前移）一个位置，移动过程是从（前）向（后）依次移动一个元素。
15在单链表中，若要在指针P 所指结点后插入指针S 所指结点，则需要执行下列两条语句（s->next=p->next）和（p->next=s）。
16. 在带有头结点的双链表1中，指针P 所指结点是第一个元素结点的条件是（p=L->next）。
17. 在线性表的单链存储中，若一个元素所在结点的地址为P ，则其后继结点的地址为（p->next），若假定P 为一个数组A 中的下标，则其后继结点的下标为（a 【p 】-next ）。
18. 在一个带头结点的单循环链表中，P 指向尾结点的直接前驱，则指向头结点的指针head 可用P 表示为head=（p->next->next）。
19. 既无前驱也没有后继的结点在所在线性表长度为（1），结点指针域的值为（空）。
20. 在单链表中，除了元结点外，任一结点的存储位置由（其直接前驱结点的链域的值）指示。
21. 静态链表是用（数组）描述的链表。
=
22、循环链表的特点是表中（最后 ）一个结点的指针域指向（ 头结点 ），整个链表形成一个环。
23、双向链表的结点中有（ 质 ）个指针域，其一指向（ 直接后继 ），另一指向（ 直接前驱 ）
24、设P 点为结点a 的指针，如果要删除a 的后一个结点，修改指针的语句为（ p->next=p->next->next ）
25、在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从（ 头结点 ）进行查找任何一个元素
26、链表的每个结点中只包含一个指针域，该链表称为（ 线性链表 ）或（ 单链表 ）
27、链式存储结构的特点是用一组（ 任意 ）的存储单元存储线性表的数据元素
28、在单链表中，若要在指针P 所指结点后插入指针s 所指结点，则需要执行下列两条语句，s->next=p->next，（ p->next=s ）
29、一个向量第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（ 108 ）
30、向顺序表中第i 个元素之前插入一个新元素时，首先从（ 位置i ）开始向后的所有元素均需（ 后移 ）一个位置，接着把新元素写入（位置i ）上，最后使线性表的长度（加1）。从顺序表中删除第i 个元素时，首先把第i 个元素赋给（工作单位），接着从（位置i+1）开始向后，所有元素均（前移），最后使线性表的长度（减1）
31、在一个长度为n 的顺序表中删除第i 个元素，要移动（n-i ）个元素，如果要在第i 个元素前插入一个元素，要后移（n+i-1）个元素
32、在双向循环链表中，在p 所指的结点之后插入s 指针所指的结点，其操作是
S->next=p->next;(p->next->prior )=s;s->prior=( p );p->next=s;
33. 对于一个长度为n 的顺序存储的线性表，在表头插入元素的时间复杂度为（O(n)），在表尾插入元素的时间复杂度为（ O(1) ）
34. 在双向循环表中，在p 所指的结点之后插入指针f 所指的结点，其操作为
F->next=p->next;( p->next->prior=f )( f->prior=p )。
35. 在顺序表中，插入或删除一个元素，需要平均移动（约表长的一半）个元素，具体移动的元素个数与（该元素在线性表中的位置）有关
36. 在线性表的顺序存储中，元素之间的逻辑关系是通过（物理存储位置）决定的，在线性表的链接存储中，元素之间的逻辑关系是通过（链域的指针）决定的
37. 对于一个具有n 个结点的单链表中，在已知的结点后插入一个新结点的时间复杂度为（O(1) ）在给定值为X 的结点后插入一个新结点的时间复杂度为（O （n ））
38. 在线性表中，若结构是一个非空集，则第一个结点称为（开始结点），且此结点（没有）前驱结点，其余各个结点有且仅有（一个前驱结点），最后一个结点称为（终端结点），它（没有）后继结点，其余各个结点有且仅有1个后继结点
39. 只要确定了存储线性表的起始位置，线性表中任何一个数据元素都可以（随机存取），这个特点也铸成了这种存储结构的弱点，在执行（插入）和（删除）操作时，需要移动大量元素
40. 从一个顺序存储的循环队列中删除一个元素时，应该（先移动队首指针，反取出元素）
41. 若L 是splist 类型的顺序表，则表中的第i 个数据元素是（Lelem[i-1]）
42. 已知一个顺序存储的线性表，设每个结点需占用m 个存储单元，若第一个结点的地址为d1，则第1个结点的地址为（dl+(I-1)*m）
第四份：CH03
1. 一个栈的输入序列号12345，则栈的输出序列是12345是（可能的）。
2. 队列的插入操作在（队尾）进行，删除操作在（对头）进行。
3. 栈又称为（后进先出）的表，队列称为（先进先出）的表。
4. 设长度为n 的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为（ O(n） ）和（ O (1) ）；若只设尾指针，则入队和出对操作的时间复杂度分别为（ O(1) ）和（ O(1) ）。
5. 向一个栈顶指针为HS 的链中插入一个S 所指结点时，则执行（ S->next=HS,HS=S; ）。
6. 设S （1：maxsize ）为一个顺序存储的栈，变量top 只是栈顶位置，栈为空的条件是（ top=0 ），栈为满的条件是（ top=maxsize ).
7. 向一个顺序栈插入一个元素时，受限使（ 栈顶指针 ）后移一个位置，然后把待插入元素（ 写入 ）到这个位置上。
8. 从一个栈删除元素时，需要前移一位（ 栈顶指针 ）。
9. 仅允许在表的同一端插入和删除运算的线性表被称为（ 栈 ) 。
10. 设sp （top
11. 在一个顺序栈中，若栈顶指针等于（ —1 ），则为空栈；若栈顶指针等于（ maxsize —1 ），则为栈满。
12. 在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为（ 0 ），当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为（ 空 ）。
13. 已知一个栈的输入序列为1,2,3，... ，n, 则其输出序列的第2个元素为n 的输出序列的种数是（ n—1 ）。
14. 在一个链式栈中，若栈顶指针等于NULL 则为（ 空栈 ），在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为（ 空 ）或该队列（ 只含有一个结点 ）。
15. 循环队列采用数组data （ front ）来存储元素的值，并用front 和rear 分别作为其头尾指针。为区分队列的满和空，约定队列中能够存放的元素个数最大为n —1, 也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下表是（ rear=rear+1 ）。入队时，可用语句（ mod n ）切除新元素在数组data 中的下标。
16. 向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给（ 新结点的指针域 ），然后把新结点的存储位置赋给（ 栈顶指针 ）。
17. 向一个循环队列中插入元素时，需要首先移动（ 队列指针 ），然后再向所指位置（ 写入 ）新插入的元素。
18. 对于一个栈，给出输入项A,B,C 。如果输入项顺序为A,B,C 所组成，则全部可能的输出项有（ 5 ）种，不可能的输出项为（ CAB ）。
19. 当用长度为n 的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为（ top==0 ）。
20. 向一个栈顶指针为top 的链式栈中插入一个新结点*p时，应执行（ P->link=top ）和（ top=p ）操作。
21. 链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的（ 最后一个结点 )。
22. 设输入元素的顺序为1,2,3,4,5，要在栈S 的输出端得到序列4.3.5.2.1，则进行的操作用栈的基本运算表示应为push(S,1)，push(S,2),push(S,3),push(S,4),pop（S ），( pop(s),push(s,5) ），pop(S)，pop （S ），pop(S)。
23. 在栈中存取数据遵从的原则是（ 后退先出 ）。
24、从一个栈顶指针为top 的非空链式栈中删除节点并不需要返回栈顶结点的值和回收结点时，应执行（ top=top→link ）操作。
25、假定front 和rear 分别为一个链式队列的对头和队尾指针，则链式队列中只有一个结点的条件为（front==rear&&front！=NULL）。
26、在一个循环队列中，队首指针指向队首元素的（前一个位置）；从循环队列中删除一个元素时，其操作是先取出队首元素，后（移动队首指针）；在具有n 个单元的循环队列中，队满时共有（n-1）个元素。
27、设有一个顺序栈S ，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2,s3,s6,s5,s1则顺序栈的容量至少应为（3）。
28、假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别只是循环队列中的队尾位置和队列中的所含元素的个数，则该循环的队列的对空条件为（length==0）。
29、中缀表达式3*（X+2）-5所对应的后缀表达式为（3*2+*5）。
30、后缀表达式45*32+-的值为（15）。
31、假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别只是循环队列中的队尾位置和队列中的所含元素的个数，则该循环的队列的对满条件为（length==Maxsize ）。
32、栈的存储结构有（顺序栈）和（链栈）。
33、栈的特点（后进先出），队列的特点是（先进先出），栈和队列的特点是（操作受限的线性表）。
34、设栈S 和队列Q 的初始状态为空，元素a.b.c.d.e.f 依次通过栈S ，一个元素出栈后即进入队列Q 。若这6个元素出队列的顺序是bdcfea. 则栈S 的容量至少应是（3）。
35、一个队伍的入队列是1234，则队列的输出顺序是（1、2、3、4）。
36、对于一个栈做进栈运算时，应先判断栈是否为（栈满），做出栈运算时，应先判断别栈是否（栈空），当栈中元素为m 时，做栈运算时发生上溢，则说明栈的可用最大容量为（m ）。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的（栈底）分别设在这片内存空间的两端，这样只有当（两栈和栈顶空间的某一个位置）时才发生上溢。
37、设有一个空栈，栈顶指针为1000H ，现有输入序列为12345，push ，push ，pop ，push ，pop ，push ，push 后，输出序列为（2，3），栈顶指针是（1003H ）。
38、设有一空栈，现有输入队列12345，经push ，push ，pop ，push ，pop ，push ，push ，后，输出队列是（2,3）。
39、用数组Q 表示一个环形队列，f 为当前对头元素的钱一位置，r 为队尾元素的位置。假定队列中元素个数总小于n ，求队列中元素个数公式是（（r-f+n）%n）。
40、用循环链表表示的队列长度为n ，若只设头指针，则出对和入对的时间复杂度分别是（0（1））和（0（n ））；若只设尾指针，则出队和入队的时间复杂度分别是（0（n ））和（0（1））。
41、向栈中压入元素的操作是（先移动栈顶指针，后存入元素）。
42、向栈进行出栈时的操作是（先取出元素，后移动栈顶指针）。
43、在一个循环队列中，队首指针指向对周元素的（前一个位置）。
44、从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出位置）。
45、假设Q[1,10]是一个循环队列，初始状态为front=rear=1，若做完debgh 入队和de 出队的操作后，rear=
（6），front=(3).
46、在具有n 个单元的循环队列中，队满时共有（n-1）个元素。
47、将f=1+1/2+1/3+.....+1/n转化成速递归函数，其递归出口是（f （1）=1）递归体是（f （n ）=f（n-1）+1/n）。
1、空串是 零个字符的串 ，其长度等于 零 。
2、空格串是 有一个或多个空格组成的串 ，其长度等于 串空格字符的个数 。
3、数组的长度是 数组的元素个数 。
4、空串与空格串的区别在于 空串的长度为零，而空格串的长度不为零 。
5、两个字符相等的充分必要条件是 长度相等 。
6、串的两种最基本的存储方式是 顺序存储方式和链接存储方式 。
7、两个串相等的充分必要条件是 两个串的长度相等且对应位置的字符相同 。
8、串中任意个连续相等的字符组成的子序列称为 子串 。
9、包含子串的串相应地称为 主串 。
10、当且仅当两个串的值相等，称两个串 相等 。
11、常对数组进行的操作是 查找和修改 。
12、二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是 200+（6x20+12）x1 。
13、有一个10阶对称矩阵A ，采用压缩存储方式（以行序列为主存储，且A[0][0]=1），则A[8][5]的地址是 42 。
14、串的逻辑结构和线性表极为相似，区别在于 串的数据对象约束 。
15、串的基本操作中，通常以 串的整体 为操作对象。
16、广义表（（a ），（（b ），c ），（（（d ））））的表头是 (a) ，表尾是 (((b)，c ），（（（d ）））) 。
17、广义表（（a ），（（b ），c ），（（（d ））））的长度是 3 ，深度是 4 。
18、子串的定操作通常称为串的 模式匹配 。
19、由零个或多个字符组成的有限序列，称为 串 。
20、通常称字符在序列中的序号为该字符在串中的 位置 。
21、两个字符串S1和S2的长度分别为m 和n ，求这两个字符串最大共同子串的时间复杂度为T （m ，n ），这最优的时间复杂度为 O(m*n) 。
22、广义表（a ，（a ，b ），d ，e ，（（i ，j ），k ））的长度是5 ，深度是 3 。
23、稀疏矩阵一般的压缩存储方式是 三元组和十字链表 。
24、二位数组A[10....20][5....10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是 1208 。
25、二维数组A[m][n]采用行序为主方式存储，每个元素占k 个存储单位，并且第一个元素的存储地址是LOC （A[0][0]），则A[i][j]的地址是 Loc(A[0][0])+(n*i+j)*k 。
26、写出模式串P=“abaabcac ”的next 函数值序列为01122312 。
27、数组A[-2....5,2....8,1.....8]以行序存储，设第一个元素的首地址是54，每个元素的长度为5，则元素A[0，6，5]的存储首址为 319 。
28、设n 行n 列的下三角矩阵A 已压缩到一维数组S[1....n*（n+1）/2]中，若按行序为主存储，则A[i][j]对应的S 中的存储位置是 i*(i+1)/2+j+1 。
29、数组A 中，每个元素A 的长度为3个字节，行下标i 从1到8，列下标j 从1到10，从首地址SA 开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为SA+222 。
30、其非零元素较零元素少，且分布没有一定规律的矩阵，称为SA+180 。
31、数组A 中，每个元素A 的长度为3个字节，行下标i 从1到8，列下标j 从1到10，从首地址SA 开始连续存放在存储器内，存放该数组至少需要的单元数是 稀疏矩阵 。
32、广义表的表尾总是一个 240 。
33、设按低下标优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占4个字节，a[3][1][2][5]的存储地址是 1784 。
34、假如值相同的元素或零元素在矩阵中的分布有一定规律，称为 特殊矩阵 。
35、为多个值相同的元素分配一个存储空间；对零元素不分配空间，称为 压缩存储 。
36、广义表的深度定义为 广义表中括弧的重数 ，是广义表的一种量度。
37、二维数组可有两种存储方式即 以行序为主序的存储方式和一列序为主序的存储方式 。
38、三元组顺序标又称有序的双下标法，它的特点是 非零元素在表中按行序有序存储 。
39、设广义表L=（（），（）），则Head （L ）是 Head(L)=0 ；Tail （L ）是 Tail(L)=(0) ；L 的长度是 2 ，深度是 2 。
1. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为2. 已知某二叉树的后序遍历为dabcc ，中序遍历为debac ，则它的前序遍历为
3. 如果t2是出有序树t 转换而来的二叉树，那么t 中的结点的前序就是＿t2＿＿＿结点中的前序。
4. 如果t2是由序树t 转换而来的二叉树，那么t 中的结点的后序就是＿
5. 某二叉树的前序遍历结点顺序为abdgcefg ，中序遍历结点顺序为dgbacchf ，则后序遍历的结点顺
序为＿gdbehfca ＿＿＿＿＿
6. 按照二叉树的定义，具有３个结点的二叉树有＿
7. 深度为５的二叉树至多以有＿＿31＿个结点
8. 树最适合用来表示元素之间具有＿的数据
9. 任何一颗二叉树的叶结点在＿前序，中序，后序＿＿＿遍历中的相对次序不发生改变
10. 在一非空二叉树的中，根结点的右边只有＿右子树＿＿＿上的所有结点
11. 实现任意二叉树的后序遍历的非递归算法而不适用栈结构，最佳的二叉树方法是采用＿三叉列表
的存储结构
12. 如果某二叉树的前序为ｓｔｕｗｖ，中序为uwtvs ，那么二叉树的后序为＿13. 具有五层结点的二叉树平衡树至少有＿＿个结点
14. 线索二叉树是一种
15. 设n\ m 为一棵二叉树上的两个结点，在中序遍历中，n 在m 的前面的条件是＿
16. 二叉树按照某种线索化后，任意结点均有指向其前驱和后继的线索，这种说法是＿错误的＿＿＿
二叉树的前序遍历中，任意一个结点均处于其子女结点的前面，这种说法是＿正确的＿
17. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法是＿错误的＿＿＿
18. 设F 是一个森林，B 是由F 转换得到的二叉树，F 中有n 个非终端结点，则B 中有指针域为空的
结点有＿n+1＿＿个
21. 对于二个具有a 个结点的二又树. 当它为一裸＿完成＿＿＿二叉树时具有最小高度，
即为＿【log2n 】+1＿＿. 当它为一裸单支树具有＿最大. ＿高度. 即为_＿n ＿＿
22. 在二叉搜素排序树上进行搜索查找时. 其时间复杂度为＿
其时间复杂度为＿o （log ＿n ）＿＿
23. 山带权为3, ，、6,2,5的5个叶子结点构成一裸哈夫爱树. 则带权路径长度为＿＿55＿
24. 在一裸二叉排序树上按＿中序＿＿遍历得到的结点序列是一个有序序列。
25 对于一裸具有n 个结点的二又树. 当进行链接存储时. 其二又链表中的指针城的
总数为＿2n ＿＿＿个. 其中（n-1）个用于链接孩子结点＿n+1＿＿个空闲着。
26. 在一操二叉树中. 度为0的结点个数为no. 度为2的结点个数为n2则
27在具有”个结点的二叉排序树上播人一个新结点时. 其时间复杂度大致＿＿＿＿为，n
个数据元众生成一裸二又排序树时，其时间复杂度大致为（O （log2n ）
28. 已知8个数据元素由( 35,75,40,15,20,55,95,65 )按照依次搔入结点的方法生成一裸二叉排序树后. 最后两层上的结点总数为 2_
29. 由a, b, c三个结点构成的二叉树. 共有_ 5 种不同结构。
30假定一裸三叉树的结点放为50, 则它的最小高度为 5
31，在一裸二叉树上的第5层的结点数最多为_ 16
32.由带权为，9、2. 5,7，的四个叶子结点构造一裸哈夫曼树. 该树的带权路径长度为 44
33假定在一操二又树中. 双分支结点数为15. 单分支结点致为30个. 则叶子结点数为 16
34. 在一裸度为3的树中. 度为3的结点数为2个，度为2的结点数为. 个。度为. 的结点数为2个. 则度为0的结点数为 6 个，
35.假定一裸树的广义表表示为A(B(E),C(F(H,I,J),G),D), (Il该树的深度为 4
36. 有12个结点的平衡二叉树的最大深度是 5
37. 设森林F 中有三裸树，第一、第二和第只裸树的结点个数分别为ml, m2, m3.则与森林F 对应的二又树根结点的右子树I. 的结点个致是_ m2+m3 。
38.若二又树采用的是二又链表存储结构. 要交换其所有分支结点左右子树的位置利用_中序 遍历方斌最合适。
39. 在计算递归曲数时，如不使用递归过程. 则一般悄况下必须借助于 栈 数据结构。
40树(及一切树形结构) 是一种“_ 分支层次 “结构，在树上根_结点没有育接晌驭，对树上任一结点x 来说.x 是它的任一子树的根结点惟一的_直接前驱 。
41.一裸树上的任何结点(不包括根本身) 称为根的_子孙 。若B 是A 的子孙. 则称A 是B 的 祖先
42.一般的. 二又树有 空 二又树、 只含根 的二叉树、只有 非空左子树 的二又树，只有 非空右子树 _的二叉树、同时有 非空左右子树 的二又树五种幕本形态:
43.二又树第i (i>=1）层上至多有 2t-1 个结点。
44.深度为k(k>=1)的二叉树至多有 2k-1 个结点.
45对任何二又树. 若度为2的结点数为n2:，则叶子数n0= n2+1
46满二叉树卜各层的结点数以达到了二叉树可以容纳的 最大值 。满二叉树也是_完全 二又树. 但反之不然。
47.具有n 个结点的完全二又树的深度为_（log2n ）+1 。
48. 如果将一裸有n 个结点的完全二X 树按层编号. 则对任一编号为i(1
(一) 若i=1则结点x 是_ 根 ;若i>1,则x 的双亲PARENT(X)的编号为
Floor （i/2）
(2)若2i>n.则结点x 无 左孩子 且无 右孩子 ;否则。x 的左孩子LC)iILD(X)的编号为 2i
(3)若2i+1>n。. 则结点x 无_ 右孩子 否则.x 的右孩子RCHILD(X)的编号为 2i+1
49. 二叉树通常有 顺序 存储结构和 链式 存储结构两类存储结构。
50. 每个二叉链表的访问只能从 根 结点的指针. 该指针几有标识二叉链表的作用。
51. 对二叉链表的访问只能从 根 指针开始. 若二叉树为空，
则 root =NULL,
1. 有向图G 用邻接矩阵A ｛1。。。。。n ，1。。。。。n ｝存储，其第一列的所有元素之和等于顶点1的（入度）。
2. 在一个有向图中，所有顶点入度之和等于所有顶点出度之和的（1）倍。
3. 对于含有N 个顶点E 条边的无向连通图，利用Kruskal 算法生成最小代价生成树的时间复杂度为（o
（elg0））。
4. 设G 为具有N 个顶点的无向连通图，则G 至少有（N-1）条边。
5. 一棵有N 个顶点的生成树有且仅有（N-1）条边。
6. 若连通网络上各边的权值均不相同，则该图的最小生成树有（1）棵。
7. 不存在拓扑序列的（有向图）是图中存在回路。
8. 已知一个图的邻接矩阵表示，删除所有从第一个节点出发的边的方法是（将矩阵第一行全部置为0）.
9. 对于一个图G ，若边集E （G ）为有向边的集合，则该图为（有向图）。
10. 对于一个图G ，若边集E （G ）为无向边的集合，则该图为（无向图）。
11. 在一个无向图中，若存在一条边,则称Vi 和Vj 为该边的两个端点，并称他们互为（邻接点）。
12. 对于有向图，顶点V 的度分为（入度和出度）。
13. 有向图顶点V 的度等于其（入度和出度）之和。
14. 入度是以该顶点为终点的入边（数目）。
15. 出度是以该顶点为起点的（出边）数目。
16. 具有N （N-1）/2条边的无向图成为（无向完全图）。
17. 具有N （N-1）/2条边的有向图成为（有向完全图）。
18. 边很少的图称为（稀疏图）。
19. 边很多的图称为（稠密图）。
20. 路径长度是指一条路径上经过的边的（数目）。
21. 若一条路径上所有顶点不重复出现，则称该路径为（向单路径）。
22. 若一条路径上的开始点和结束点为同一个顶点，则称该路径为（回路成环）。
23. 若图G 中任意两个顶点都连通，则称G 为（连接图）。
24. 无向图G 中极大连通子图称为G 的（连通分量）。
25. 在有向图G 中，若任意两个顶点Vi 和Vj 都连通，从VI 到Vj 和从Vj 到Vi 都存在路径，则称该图为
（强连通图）。
26. 有向图G 中极大强连通子图称为G 的（强连通分量）。
27. 在一个图中每条边可以表上具有某种含义的数值，该数值称为（权）。
28. 边上带权的图为（网）。
29. （邻接表）是图的一种连接存储结构。
30. 顶点表示活动，边表示活动之间的先后关系的有向图为顶点活动网称为（顶点表示活动的网）。
31. 图的遍历方式有（深度优先搜索）和（广度优先搜索）两种。
32. 从邻接矩阵A 可以看出，该图有（3）个顶点。如果是有向图，该图共有（4）条弧；如果是无向图，
则共有（2）条边。
33. 有向图中的结点前驱后继关系的特征是（一个结点可能有若干个前驱，也可能有若干个后继）。
34. Krushal 算法的时间复杂度为（o （Elge ）），他对（稀疏）图较为合适。
35. 如图所示，为由7个顶点组成的无向图。从顶点1出发，对他进行深度优先遍历得到的顶点序列是
（1534276），而进行广度优先遍历得到的顶点序列是（1354276）。
36、n 个顶点的连通图用邻接矩阵表示时，该矩阵至少有（n-1）范围非0元素。
37、在具有6个结点的无向简单图中，当边数最少为（5）条时，才能确保该图一定的连通图。
38、遍历图的过程中实质上是（对每个顶点查找其邻接点的过程）。Breadth-first search 遍历图的时间复杂度为（O(e)），depth-first search 遍历图的时间复杂度为（O(e)），两者不同之处在于（遍历图的顺序不同），反映在数据上的差别是（DFS 采用栈存储访问过的结点，BFS 采用队列存储访问过的结点）。
39、设有向图G 如图所示
V—>V3→V4
（1）写出所有的括扑序列：（1234，1324，2134）。
（2）添加（从结点3到结点2）的弧后，则仅可能有唯一的括扑序列。
40、Prim （普里姆）算法使用于求（边稠密）的网的最小生成树；Kruskal 算法适用于求（边稀疏）的网的最小生成树。
1. 一个算法应该具有以下几个五个特征：（有穷性）（确定性）（输入）（输出）（可行性）
2. 算法的复杂度有（时间）和（空间）之分
3. 数据结构指的是数据之间的相互关系，，既数据的组织形式，一般包括三个方面的内容（逻辑结构）（存储结构）（数据的运算）
4. （数据元素）是数据的基本单位
5. （算法的复杂度）是算法效率的度量，是评价算法优势的重要依据
6. （结构）是元素之间的关系的集合
7. 通常来说，一个数据结构的DS 可以表示为一个（二元组）
8. 最常用的数据结构是（数组结构）和（记录结构）
9. 算法设计策略有（递归技术）（分治法）（模拟法）（贪心算法）（随机算法）（动态规划）（状态空间）（搜索法）
10. 现实世界中的事物及联系在数据世界中用（数据模型）描述
11. 数据元素之间的逻辑关系，也称（数据的逻辑结构）
12. 数据的逻辑结构可以形式的用一个二元组B=（K ，R ）来表示，其中K 是（结点的有穷集合）R 是*（K 上关系的有穷集合）
13. 一个数据元素可以有若干个（数据项）组成
14. （数据项）是具有独立含义的最小表示单位
15. （数据的运算）既对数据施加的操作
16. (数据的逻辑结构) 可以看做是从具体问题抽象出来的数学模型
17. 数据元素及其关系在计算机存储内的表示称为（数据的存取结构）
18. 数据的存储结构是逻辑结构用（计算机语言）的实现
19. 对机器语言而言，存储结构是具体的。一般只在（高级语言）层次上讨论存储结构
20. 所谓（抽象的操作），是只知道这些操作是“做什么”，而无需考虑：如何做；
21. 较早的软件开发用结构法程序设计方法。程序的定律是; 程序=（算法）+（数据结构）
22. 算法是一个独立的整体，数据结构也是一个独立的整体俩者分开设计以（算法）为主；’
23. 数据结构是介于（数学）（计算机硬件）（计算机软件）三者之间的一门核心课程
24. 数据的范畴包括（整数）（实数）（字符串）（图像）和（声音）
25. 下面程序的时间复杂度为）（0（sqrt （n ）））
Void prime(int n)
{ for(i=2;((n%i)!=)0&&(i
If(i>sqart(n))
Printf(“%d is a prime number”,n);
Else print(“%d is a prime number”,n); }
26. 下面程序的时间复杂度为（0（n ））
Float suml (int n)
{ p=1;suml=0;
For(i=1;i
{p=p*i;suml=suml+p; }}
27. 下面的时间复杂度为（0（n^2））
Float sum2(int n)
{ sum2=0;
For{i=1;i
} p=1;
For(j=1;j
Sum2=sum2+p; }}
1. 顺序存储的线性表，设其长度为n 。在任何位置上插入或删除操作的时间代价基本上都是等效的。则插入一个元素大约需要移动表中的（n(n+1)/2 ）个元素，删除一个元素时大约要移动表中的（ n(n-1)/2 ） 个元素。
2. 线性表的存储结构可以分为（线性存储结构）和（链式存储结构）。
3. 若要在一个不带表头结点的单链表的首结点*P结点之前插入一个*S结点时，可执行下列操作：
（1）s->next= p->next ;
(2) p->next=s;
(3)t=p->data;
(4)p->data= s->data ;
(5)s->data= t ;
4. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为（单链表）和（双链表）；而根据指针的联系方式，链表又可分为（非循环链表）和（循环链表）
5. 对于线性表的顺序存储，需要预先分配好存储空间。若分配太多容易造成存储空间的（浪费），若分配太少又容易在算法中造成（上溢），因而只适用于数据量变化不大的情况；对于线性表的链接存储，不需要（预先分配）存储空间，存储器中的整个（空间）都可供使用，分配和回收结点都非常方便，能有效的利用存储空间，在算法中不必考虑（上溢）的发生，因而适用于数据量变化较大的情况。
7. （双向）链表适合从指点结点开始，寻找直接前趋的运算。
8. 当一个线性表经常进行存取操作而很少进行插入和删除操作时，则采用（顺序）存储结构为宜，相反，当经常进行的是插入和删除操作时，则采用（链接）存储结构为宜。
9. 在单链表中设置头结点的作用是（使空表和非空表统一，算法处理一致）。
10. 顺序表中逻辑上相邻的元素物理位置（一定）紧邻，单链表中逻辑上相邻的元素物理位置（不一定）紧邻。
11. 如果线性表的存储空间变化较大，则适用（链）表。
12. 在链表中，每个结点中含8个字符，1个指针域。其中每个字符占1个字节，每个指针占4个字节。则该结点的存储密度是（2/3）。
13. 当向一个顺序表插入一个元素时，从插入位置开始向后的所有元素均（后移）一个位置，移动过程是从（后）向（前）依次移动没一个元素。
14. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需（前移）一个位置，移动过程是从（前）向（后）依次移动一个元素。
15在单链表中，若要在指针P 所指结点后插入指针S 所指结点，则需要执行下列两条语句（s->next=p->next）和（p->next=s）。
16. 在带有头结点的双链表1中，指针P 所指结点是第一个元素结点的条件是（p=L->next）。
17. 在线性表的单链存储中，若一个元素所在结点的地址为P ，则其后继结点的地址为（p->next），若假定P 为一个数组A 中的下标，则其后继结点的下标为（a 【p 】-next ）。
18. 在一个带头结点的单循环链表中，P 指向尾结点的直接前驱，则指向头结点的指针head 可用P 表示为head=（p->next->next）。
19. 既无前驱也没有后继的结点在所在线性表长度为（1），结点指针域的值为（空）。
20. 在单链表中，除了元结点外，任一结点的存储位置由（其直接前驱结点的链域的值）指示。
21. 静态链表是用（数组）描述的链表。
=
22、循环链表的特点是表中（最后 ）一个结点的指针域指向（ 头结点 ），整个链表形成一个环。
23、双向链表的结点中有（ 质 ）个指针域，其一指向（ 直接后继 ），另一指向（ 直接前驱 ）
24、设P 点为结点a 的指针，如果要删除a 的后一个结点，修改指针的语句为（ p->next=p->next->next ）
25、在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从（ 头结点 ）进行查找任何一个元素
26、链表的每个结点中只包含一个指针域，该链表称为（ 线性链表 ）或（ 单链表 ）
27、链式存储结构的特点是用一组（ 任意 ）的存储单元存储线性表的数据元素
28、在单链表中，若要在指针P 所指结点后插入指针s 所指结点，则需要执行下列两条语句，s->next=p->next，（ p->next=s ）
29、一个向量第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（ 108 ）
30、向顺序表中第i 个元素之前插入一个新元素时，首先从（ 位置i ）开始向后的所有元素均需（ 后移 ）一个位置，接着把新元素写入（位置i ）上，最后使线性表的长度（加1）。从顺序表中删除第i 个元素时，首先把第i 个元素赋给（工作单位），接着从（位置i+1）开始向后，所有元素均（前移），最后使线性表的长度（减1）
31、在一个长度为n 的顺序表中删除第i 个元素，要移动（n-i ）个元素，如果要在第i 个元素前插入一个元素，要后移（n+i-1）个元素
32、在双向循环链表中，在p 所指的结点之后插入s 指针所指的结点，其操作是
S->next=p->next;(p->next->prior )=s;s->prior=( p );p->next=s;
33. 对于一个长度为n 的顺序存储的线性表，在表头插入元素的时间复杂度为（O(n)），在表尾插入元素的时间复杂度为（ O(1) ）
34. 在双向循环表中，在p 所指的结点之后插入指针f 所指的结点，其操作为
F->next=p->next;( p->next->prior=f )( f->prior=p )。
35. 在顺序表中，插入或删除一个元素，需要平均移动（约表长的一半）个元素，具体移动的元素个数与（该元素在线性表中的位置）有关
36. 在线性表的顺序存储中，元素之间的逻辑关系是通过（物理存储位置）决定的，在线性表的链接存储中，元素之间的逻辑关系是通过（链域的指针）决定的
37. 对于一个具有n 个结点的单链表中，在已知的结点后插入一个新结点的时间复杂度为（O(1) ）在给定值为X 的结点后插入一个新结点的时间复杂度为（O （n ））
38. 在线性表中，若结构是一个非空集，则第一个结点称为（开始结点），且此结点（没有）前驱结点，其余各个结点有且仅有（一个前驱结点），最后一个结点称为（终端结点），它（没有）后继结点，其余各个结点有且仅有1个后继结点
39. 只要确定了存储线性表的起始位置，线性表中任何一个数据元素都可以（随机存取），这个特点也铸成了这种存储结构的弱点，在执行（插入）和（删除）操作时，需要移动大量元素
40. 从一个顺序存储的循环队列中删除一个元素时，应该（先移动队首指针，反取出元素）
41. 若L 是splist 类型的顺序表，则表中的第i 个数据元素是（Lelem[i-1]）
42. 已知一个顺序存储的线性表，设每个结点需占用m 个存储单元，若第一个结点的地址为d1，则第1个结点的地址为（dl+(I-1)*m）
第四份：CH03
1. 一个栈的输入序列号12345，则栈的输出序列是12345是（可能的）。
2. 队列的插入操作在（队尾）进行，删除操作在（对头）进行。
3. 栈又称为（后进先出）的表，队列称为（先进先出）的表。
4. 设长度为n 的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为（ O(n） ）和（ O (1) ）；若只设尾指针，则入队和出对操作的时间复杂度分别为（ O(1) ）和（ O(1) ）。
5. 向一个栈顶指针为HS 的链中插入一个S 所指结点时，则执行（ S->next=HS,HS=S; ）。
6. 设S （1：maxsize ）为一个顺序存储的栈，变量top 只是栈顶位置，栈为空的条件是（ top=0 ），栈为满的条件是（ top=maxsize ).
7. 向一个顺序栈插入一个元素时，受限使（ 栈顶指针 ）后移一个位置，然后把待插入元素（ 写入 ）到这个位置上。
8. 从一个栈删除元素时，需要前移一位（ 栈顶指针 ）。
9. 仅允许在表的同一端插入和删除运算的线性表被称为（ 栈 ) 。
10. 设sp （top
11. 在一个顺序栈中，若栈顶指针等于（ —1 ），则为空栈；若栈顶指针等于（ maxsize —1 ），则为栈满。
12. 在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为（ 0 ），当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为（ 空 ）。
13. 已知一个栈的输入序列为1,2,3，... ，n, 则其输出序列的第2个元素为n 的输出序列的种数是（ n—1 ）。
14. 在一个链式栈中，若栈顶指针等于NULL 则为（ 空栈 ），在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列为（ 空 ）或该队列（ 只含有一个结点 ）。
15. 循环队列采用数组data （ front ）来存储元素的值，并用front 和rear 分别作为其头尾指针。为区分队列的满和空，约定队列中能够存放的元素个数最大为n —1, 也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下表是（ rear=rear+1 ）。入队时，可用语句（ mod n ）切除新元素在数组data 中的下标。
16. 向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给（ 新结点的指针域 ），然后把新结点的存储位置赋给（ 栈顶指针 ）。
17. 向一个循环队列中插入元素时，需要首先移动（ 队列指针 ），然后再向所指位置（ 写入 ）新插入的元素。
18. 对于一个栈，给出输入项A,B,C 。如果输入项顺序为A,B,C 所组成，则全部可能的输出项有（ 5 ）种，不可能的输出项为（ CAB ）。
19. 当用长度为n 的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为（ top==0 ）。
20. 向一个栈顶指针为top 的链式栈中插入一个新结点*p时，应执行（ P->link=top ）和（ top=p ）操作。
21. 链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的（ 最后一个结点 )。
22. 设输入元素的顺序为1,2,3,4,5，要在栈S 的输出端得到序列4.3.5.2.1，则进行的操作用栈的基本运算表示应为push(S,1)，push(S,2),push(S,3),push(S,4),pop（S ），( pop(s),push(s,5) ），pop(S)，pop （S ），pop(S)。
23. 在栈中存取数据遵从的原则是（ 后退先出 ）。
24、从一个栈顶指针为top 的非空链式栈中删除节点并不需要返回栈顶结点的值和回收结点时，应执行（ top=top→link ）操作。
25、假定front 和rear 分别为一个链式队列的对头和队尾指针，则链式队列中只有一个结点的条件为（front==rear&&front！=NULL）。
26、在一个循环队列中，队首指针指向队首元素的（前一个位置）；从循环队列中删除一个元素时，其操作是先取出队首元素，后（移动队首指针）；在具有n 个单元的循环队列中，队满时共有（n-1）个元素。
27、设有一个顺序栈S ，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2,s3,s6,s5,s1则顺序栈的容量至少应为（3）。
28、假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别只是循环队列中的队尾位置和队列中的所含元素的个数，则该循环的队列的对空条件为（length==0）。
29、中缀表达式3*（X+2）-5所对应的后缀表达式为（3*2+*5）。
30、后缀表达式45*32+-的值为（15）。
31、假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别只是循环队列中的队尾位置和队列中的所含元素的个数，则该循环的队列的对满条件为（length==Maxsize ）。
32、栈的存储结构有（顺序栈）和（链栈）。
33、栈的特点（后进先出），队列的特点是（先进先出），栈和队列的特点是（操作受限的线性表）。
34、设栈S 和队列Q 的初始状态为空，元素a.b.c.d.e.f 依次通过栈S ，一个元素出栈后即进入队列Q 。若这6个元素出队列的顺序是bdcfea. 则栈S 的容量至少应是（3）。
35、一个队伍的入队列是1234，则队列的输出顺序是（1、2、3、4）。
36、对于一个栈做进栈运算时，应先判断栈是否为（栈满），做出栈运算时，应先判断别栈是否（栈空），当栈中元素为m 时，做栈运算时发生上溢，则说明栈的可用最大容量为（m ）。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的（栈底）分别设在这片内存空间的两端，这样只有当（两栈和栈顶空间的某一个位置）时才发生上溢。
37、设有一个空栈，栈顶指针为1000H ，现有输入序列为12345，push ，push ，pop ，push ，pop ，push ，push 后，输出序列为（2，3），栈顶指针是（1003H ）。
38、设有一空栈，现有输入队列12345，经push ，push ，pop ，push ，pop ，push ，push ，后，输出队列是（2,3）。
39、用数组Q 表示一个环形队列，f 为当前对头元素的钱一位置，r 为队尾元素的位置。假定队列中元素个数总小于n ，求队列中元素个数公式是（（r-f+n）%n）。
40、用循环链表表示的队列长度为n ，若只设头指针，则出对和入对的时间复杂度分别是（0（1））和（0（n ））；若只设尾指针，则出队和入队的时间复杂度分别是（0（n ））和（0（1））。
41、向栈中压入元素的操作是（先移动栈顶指针，后存入元素）。
42、向栈进行出栈时的操作是（先取出元素，后移动栈顶指针）。
43、在一个循环队列中，队首指针指向对周元素的（前一个位置）。
44、从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出位置）。
45、假设Q[1,10]是一个循环队列，初始状态为front=rear=1，若做完debgh 入队和de 出队的操作后，rear=
（6），front=(3).
46、在具有n 个单元的循环队列中，队满时共有（n-1）个元素。
47、将f=1+1/2+1/3+.....+1/n转化成速递归函数，其递归出口是（f （1）=1）递归体是（f （n ）=f（n-1）+1/n）。
1、空串是 零个字符的串 ，其长度等于 零 。
2、空格串是 有一个或多个空格组成的串 ，其长度等于 串空格字符的个数 。
3、数组的长度是 数组的元素个数 。
4、空串与空格串的区别在于 空串的长度为零，而空格串的长度不为零 。
5、两个字符相等的充分必要条件是 长度相等 。
6、串的两种最基本的存储方式是 顺序存储方式和链接存储方式 。
7、两个串相等的充分必要条件是 两个串的长度相等且对应位置的字符相同 。
8、串中任意个连续相等的字符组成的子序列称为 子串 。
9、包含子串的串相应地称为 主串 。
10、当且仅当两个串的值相等，称两个串 相等 。
11、常对数组进行的操作是 查找和修改 。
12、二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是 200+（6x20+12）x1 。
13、有一个10阶对称矩阵A ，采用压缩存储方式（以行序列为主存储，且A[0][0]=1），则A[8][5]的地址是 42 。
14、串的逻辑结构和线性表极为相似，区别在于 串的数据对象约束 。
15、串的基本操作中，通常以 串的整体 为操作对象。
16、广义表（（a ），（（b ），c ），（（（d ））））的表头是 (a) ，表尾是 (((b)，c ），（（（d ）））) 。
17、广义表（（a ），（（b ），c ），（（（d ））））的长度是 3 ，深度是 4 。
18、子串的定操作通常称为串的 模式匹配 。
19、由零个或多个字符组成的有限序列，称为 串 。
20、通常称字符在序列中的序号为该字符在串中的 位置 。
21、两个字符串S1和S2的长度分别为m 和n ，求这两个字符串最大共同子串的时间复杂度为T （m ，n ），这最优的时间复杂度为 O(m*n) 。
22、广义表（a ，（a ，b ），d ，e ，（（i ，j ），k ））的长度是5 ，深度是 3 。
23、稀疏矩阵一般的压缩存储方式是 三元组和十字链表 。
24、二位数组A[10....20][5....10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是 1208 。
25、二维数组A[m][n]采用行序为主方式存储，每个元素占k 个存储单位，并且第一个元素的存储地址是LOC （A[0][0]），则A[i][j]的地址是 Loc(A[0][0])+(n*i+j)*k 。
26、写出模式串P=“abaabcac ”的next 函数值序列为01122312 。
27、数组A[-2....5,2....8,1.....8]以行序存储，设第一个元素的首地址是54，每个元素的长度为5，则元素A[0，6，5]的存储首址为 319 。
28、设n 行n 列的下三角矩阵A 已压缩到一维数组S[1....n*（n+1）/2]中，若按行序为主存储，则A[i][j]对应的S 中的存储位置是 i*(i+1)/2+j+1 。
29、数组A 中，每个元素A 的长度为3个字节，行下标i 从1到8，列下标j 从1到10，从首地址SA 开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为SA+222 。
30、其非零元素较零元素少，且分布没有一定规律的矩阵，称为SA+180 。
31、数组A 中，每个元素A 的长度为3个字节，行下标i 从1到8，列下标j 从1到10，从首地址SA 开始连续存放在存储器内，存放该数组至少需要的单元数是 稀疏矩阵 。
32、广义表的表尾总是一个 240 。
33、设按低下标优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占4个字节，a[3][1][2][5]的存储地址是 1784 。
34、假如值相同的元素或零元素在矩阵中的分布有一定规律，称为 特殊矩阵 。
35、为多个值相同的元素分配一个存储空间；对零元素不分配空间，称为 压缩存储 。
36、广义表的深度定义为 广义表中括弧的重数 ，是广义表的一种量度。
37、二维数组可有两种存储方式即 以行序为主序的存储方式和一列序为主序的存储方式 。
38、三元组顺序标又称有序的双下标法，它的特点是 非零元素在表中按行序有序存储 。
39、设广义表L=（（），（）），则Head （L ）是 Head(L)=0 ；Tail （L ）是 Tail(L)=(0) ；L 的长度是 2 ，深度是 2 。
1. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为2. 已知某二叉树的后序遍历为dabcc ，中序遍历为debac ，则它的前序遍历为
3. 如果t2是出有序树t 转换而来的二叉树，那么t 中的结点的前序就是＿t2＿＿＿结点中的前序。
4. 如果t2是由序树t 转换而来的二叉树，那么t 中的结点的后序就是＿
5. 某二叉树的前序遍历结点顺序为abdgcefg ，中序遍历结点顺序为dgbacchf ，则后序遍历的结点顺
序为＿gdbehfca ＿＿＿＿＿
6. 按照二叉树的定义，具有３个结点的二叉树有＿
7. 深度为５的二叉树至多以有＿＿31＿个结点
8. 树最适合用来表示元素之间具有＿的数据
9. 任何一颗二叉树的叶结点在＿前序，中序，后序＿＿＿遍历中的相对次序不发生改变
10. 在一非空二叉树的中，根结点的右边只有＿右子树＿＿＿上的所有结点
11. 实现任意二叉树的后序遍历的非递归算法而不适用栈结构，最佳的二叉树方法是采用＿三叉列表
的存储结构
12. 如果某二叉树的前序为ｓｔｕｗｖ，中序为uwtvs ，那么二叉树的后序为＿13. 具有五层结点的二叉树平衡树至少有＿＿个结点
14. 线索二叉树是一种
15. 设n\ m 为一棵二叉树上的两个结点，在中序遍历中，n 在m 的前面的条件是＿
16. 二叉树按照某种线索化后，任意结点均有指向其前驱和后继的线索，这种说法是＿错误的＿＿＿
二叉树的前序遍历中，任意一个结点均处于其子女结点的前面，这种说法是＿正确的＿
17. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法是＿错误的＿＿＿
18. 设F 是一个森林，B 是由F 转换得到的二叉树，F 中有n 个非终端结点，则B 中有指针域为空的
结点有＿n+1＿＿个
21. 对于二个具有a 个结点的二又树. 当它为一裸＿完成＿＿＿二叉树时具有最小高度，
即为＿【log2n 】+1＿＿. 当它为一裸单支树具有＿最大. ＿高度. 即为_＿n ＿＿
22. 在二叉搜素排序树上进行搜索查找时. 其时间复杂度为＿
其时间复杂度为＿o （log ＿n ）＿＿
23. 山带权为3, ，、6,2,5的5个叶子结点构成一裸哈夫爱树. 则带权路径长度为＿＿55＿
24. 在一裸二叉排序树上按＿中序＿＿遍历得到的结点序列是一个有序序列。
25 对于一裸具有n 个结点的二又树. 当进行链接存储时. 其二又链表中的指针城的
总数为＿2n ＿＿＿个. 其中（n-1）个用于链接孩子结点＿n+1＿＿个空闲着。
26. 在一操二叉树中. 度为0的结点个数为no. 度为2的结点个数为n2则
27在具有”个结点的二叉排序树上播人一个新结点时. 其时间复杂度大致＿＿＿＿为，n
个数据元众生成一裸二又排序树时，其时间复杂度大致为（O （log2n ）
28. 已知8个数据元素由( 35,75,40,15,20,55,95,65 )按照依次搔入结点的方法生成一裸二叉排序树后. 最后两层上的结点总数为 2_
29. 由a, b, c三个结点构成的二叉树. 共有_ 5 种不同结构。
30假定一裸三叉树的结点放为50, 则它的最小高度为 5
31，在一裸二叉树上的第5层的结点数最多为_ 16
32.由带权为，9、2. 5,7，的四个叶子结点构造一裸哈夫曼树. 该树的带权路径长度为 44
33假定在一操二又树中. 双分支结点数为15. 单分支结点致为30个. 则叶子结点数为 16
34. 在一裸度为3的树中. 度为3的结点数为2个，度为2的结点数为. 个。度为. 的结点数为2个. 则度为0的结点数为 6 个，
35.假定一裸树的广义表表示为A(B(E),C(F(H,I,J),G),D), (Il该树的深度为 4
36. 有12个结点的平衡二叉树的最大深度是 5
37. 设森林F 中有三裸树，第一、第二和第只裸树的结点个数分别为ml, m2, m3.则与森林F 对应的二又树根结点的右子树I. 的结点个致是_ m2+m3 。
38.若二又树采用的是二又链表存储结构. 要交换其所有分支结点左右子树的位置利用_中序 遍历方斌最合适。
39. 在计算递归曲数时，如不使用递归过程. 则一般悄况下必须借助于 栈 数据结构。
40树(及一切树形结构) 是一种“_ 分支层次 “结构，在树上根_结点没有育接晌驭，对树上任一结点x 来说.x 是它的任一子树的根结点惟一的_直接前驱 。
41.一裸树上的任何结点(不包括根本身) 称为根的_子孙 。若B 是A 的子孙. 则称A 是B 的 祖先
42.一般的. 二又树有 空 二又树、 只含根 的二叉树、只有 非空左子树 的二又树，只有 非空右子树 _的二叉树、同时有 非空左右子树 的二又树五种幕本形态:
43.二又树第i (i>=1）层上至多有 2t-1 个结点。
44.深度为k(k>=1)的二叉树至多有 2k-1 个结点.
45对任何二又树. 若度为2的结点数为n2:，则叶子数n0= n2+1
46满二叉树卜各层的结点数以达到了二叉树可以容纳的 最大值 。满二叉树也是_完全 二又树. 但反之不然。
47.具有n 个结点的完全二又树的深度为_（log2n ）+1 。
48. 如果将一裸有n 个结点的完全二X 树按层编号. 则对任一编号为i(1
(一) 若i=1则结点x 是_ 根 ;若i>1,则x 的双亲PARENT(X)的编号为
Floor （i/2）
(2)若2i>n.则结点x 无 左孩子 且无 右孩子 ;否则。x 的左孩子LC)iILD(X)的编号为 2i
(3)若2i+1>n。. 则结点x 无_ 右孩子 否则.x 的右孩子RCHILD(X)的编号为 2i+1
49. 二叉树通常有 顺序 存储结构和 链式 存储结构两类存储结构。
50. 每个二叉链表的访问只能从 根 结点的指针. 该指针几有标识二叉链表的作用。
51. 对二叉链表的访问只能从 根 指针开始. 若二叉树为空，
则 root =NULL,
1. 有向图G 用邻接矩阵A ｛1。。。。。n ，1。。。。。n ｝存储，其第一列的所有元素之和等于顶点1的（入度）。
2. 在一个有向图中，所有顶点入度之和等于所有顶点出度之和的（1）倍。
3. 对于含有N 个顶点E 条边的无向连通图，利用Kruskal 算法生成最小代价生成树的时间复杂度为（o
（elg0））。
4. 设G 为具有N 个顶点的无向连通图，则G 至少有（N-1）条边。
5. 一棵有N 个顶点的生成树有且仅有（N-1）条边。
6. 若连通网络上各边的权值均不相同，则该图的最小生成树有（1）棵。
7. 不存在拓扑序列的（有向图）是图中存在回路。
8. 已知一个图的邻接矩阵表示，删除所有从第一个节点出发的边的方法是（将矩阵第一行全部置为0）.
9. 对于一个图G ，若边集E （G ）为有向边的集合，则该图为（有向图）。
10. 对于一个图G ，若边集E （G ）为无向边的集合，则该图为（无向图）。
11. 在一个无向图中，若存在一条边,则称Vi 和Vj 为该边的两个端点，并称他们互为（邻接点）。
12. 对于有向图，顶点V 的度分为（入度和出度）。
13. 有向图顶点V 的度等于其（入度和出度）之和。
14. 入度是以该顶点为终点的入边（数目）。
15. 出度是以该顶点为起点的（出边）数目。
16. 具有N （N-1）/2条边的无向图成为（无向完全图）。
17. 具有N （N-1）/2条边的有向图成为（有向完全图）。
18. 边很少的图称为（稀疏图）。
19. 边很多的图称为（稠密图）。
20. 路径长度是指一条路径上经过的边的（数目）。
21. 若一条路径上所有顶点不重复出现，则称该路径为（向单路径）。
22. 若一条路径上的开始点和结束点为同一个顶点，则称该路径为（回路成环）。
23. 若图G 中任意两个顶点都连通，则称G 为（连接图）。
24. 无向图G 中极大连通子图称为G 的（连通分量）。
25. 在有向图G 中，若任意两个顶点Vi 和Vj 都连通，从VI 到Vj 和从Vj 到Vi 都存在路径，则称该图为
（强连通图）。
26. 有向图G 中极大强连通子图称为G 的（强连通分量）。
27. 在一个图中每条边可以表上具有某种含义的数值，该数值称为（权）。
28. 边上带权的图为（网）。
29. （邻接表）是图的一种连接存储结构。
30. 顶点表示活动，边表示活动之间的先后关系的有向图为顶点活动网称为（顶点表示活动的网）。
31. 图的遍历方式有（深度优先搜索）和（广度优先搜索）两种。
32. 从邻接矩阵A 可以看出，该图有（3）个顶点。如果是有向图，该图共有（4）条弧；如果是无向图，
则共有（2）条边。
33. 有向图中的结点前驱后继关系的特征是（一个结点可能有若干个前驱，也可能有若干个后继）。
34. Krushal 算法的时间复杂度为（o （Elge ）），他对（稀疏）图较为合适。
35. 如图所示，为由7个顶点组成的无向图。从顶点1出发，对他进行深度优先遍历得到的顶点序列是
（1534276），而进行广度优先遍历得到的顶点序列是（1354276）。
36、n 个顶点的连通图用邻接矩阵表示时，该矩阵至少有（n-1）范围非0元素。
37、在具有6个结点的无向简单图中，当边数最少为（5）条时，才能确保该图一定的连通图。
38、遍历图的过程中实质上是（对每个顶点查找其邻接点的过程）。Breadth-first search 遍历图的时间复杂度为（O(e)），depth-first search 遍历图的时间复杂度为（O(e)），两者不同之处在于（遍历图的顺序不同），反映在数据上的差别是（DFS 采用栈存储访问过的结点，BFS 采用队列存储访问过的结点）。
39、设有向图G 如图所示
V—>V3→V4
（1）写出所有的括扑序列：（1234，1324，2134）。
（2）添加（从结点3到结点2）的弧后，则仅可能有唯一的括扑序列。
40、Prim （普里姆）算法使用于求（边稠密）的网的最小生成树；Kruskal 算法适用于求（边稀疏）的网的最小生成树。