二、填空题
1. 线性表是一种典型的___线性______结构。1．线性
2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移__n-i+1__个元素。2．n-i+1
3. 顺序表中逻辑上相邻的元素的物理位置__相邻______。3．相邻
4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需向__前___移一个位置，移动过程是从_前____向_后____依次移动每一个元素。4．前，前，后
5. 在线性表的顺序存储中，元素之间的逻辑关系是通过__物理存储位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过__链域的指针值_____决定的。5．物理存储位置，链域的指针值  
6. 在双向链表中，每个结点含有两个指针域，一个指向___前趋____结点，另一个指向____后继___结点。6．前趋，后继
7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用___顺序__存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用__链接___存储结构为宜。7．顺序，链接
8. 顺序表中逻辑上相邻的元素，物理位置__一定_____相邻，单链表中逻辑上相邻的元素，物理位置___不一定____相邻。8．一定，不一定
9. 线性表、栈和队列都是__线性_____结构，可以在线性表的___任何___位置插入和删除元素；对于栈只能在___栈顶____位置插入和删除元素；对于队列只能在___队尾____位置插入元素和在___队头____位置删除元素。9．线性，任何，栈顶，队尾，队头
10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为__单链表_______和__双链表_____；而根据指针的联接方式，链表又可分为__循环链表______和__非循环链表______。 10．单链表，双链表，非循环链表，循环链表  
11. 在单链表中设置头结点的作用是__使空表和非空表统一______。11．使空表和非空表统一；算法处理一致
12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为_o(1)_____，在给定值为x的结点后插入一个新结点的时间复杂度为__o(n)_____。12．O(1)，O(n)
13. 对于一个栈作进栈运算时，应先判别栈是否为__栈满_____，作退栈运算时，应先判别栈是否为_栈空______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大
容量为___m____。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的__栈底_____分别设在这片内存空间的两端，这样只有当__两个栈的栈顶在栈空间的某一位置相遇_____时才产生上溢。13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇
14. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是___2 3______。14．2、3
15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为____O(1)______。15．O(1)
二、判断题
1. 二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。    （　×　）1.×
2. 二叉树的前序遍历中，任意结点均处在其子女结点之前。            （　√　）2.√
3. 线索二叉树是一种逻辑结构。                                    （　×　）3.×
4. 哈夫曼树的总结点个数（多于1时）不能为偶数。                    （　√　）4.√
5. 由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。            （　×　）5.×
6. 树的后序遍历与其对应的二叉树的后序遍历序列相同。                （　√　）6.√
7. 根据任意一种遍历序列即可唯一确定对应的二叉树。                （　√　）7. ×
8. 满二叉树也是完全二叉树。                                        （ √　）8.√
9. 哈夫曼树一定是完全二叉树。                                    （　× ）9.×
10. 树的子树是无序的。                                            （　× ）10. √
三、填空题
1. 假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为__3___，树的深度为__4___，终端结点的个数为__6____，单分支结点的个数为____1__，双分支结点的个数为____1_先序中序后序遍历二叉树_，三分支结点的个数为____1___，C结点的双亲结点为___A____，其孩子结点为____F___和_____G__结点。1. 3，4，6，1，1，2，A，F，G
2. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有__n+1_____个。2. n+1
3. 对于一个有n个结点的二叉树，当它为一棵___完全_____二叉树时具有最小高度，即为___[log2n]+1____，当它为一棵单支树具有___最大___高度，即为___n____。3. 完全，，最大，n
4. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为__55_。4. 55
5. 在一棵二叉排序树上按___中序____遍历得到的结点序列是一个有序序列。5. 中序
6. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为___2n____个，其中___n-1____个用于链接孩子结点，__n+1_____个空闲着。6. 2n，n-1，n+1
7. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=__n2+1____。7. n2+1
8. 一棵深度为k的满二叉树的结点总数为__2^k  -1_____，一棵深度为k的完全二叉树的结点总数的最小值为__2^k-1___，最大值为__2^k  -1____。8. 2k-1，2k-1，2k-1
9. 由三个结点构成的二叉树，共有___5_种不同的形态。9. 5
10. 设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_
2^h  -1___。10. 2h-1+1
11. 一棵含有n个结点的k叉树，__单支数____形态达到最大深度，_完全二叉树___形态达到最小深度。11. 单支树，完全k叉树
12. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为____2i____，右孩子结点的编号为____2i+1____，双亲结点的编号为____i/2____。12. 2i，2i+1，i/2（或i/2）
13. 对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为______2n___个，其中_____n-1______个用于链接孩子结点，____n+1_________个空闲着。13. 2n，n-1，n+1
14. 哈夫曼树是指____带权路径长度最小__________________的二叉树。14. 带权路径长度最小
15. 空树是指___结点数为0______，最小的树是指___只有一个根节点的数_____。15. 结点数为0，只有一个根结点的树
16. 二叉树的链式存储结构有__二叉链表______和_三叉链表_______两种。16. 二叉链表，三叉链表
17. 三叉链表比二叉链表多一个指向____双亲结点____的指针域。17. 双亲结点
18. 线索是指___指向前驱和后继结点的指针___________________。18. 指向结点前驱和后继信息的指针
19. 线索链表中的rtag域值为__1___时，表示该结点无右孩子，此时__Rtag____域为指向该结点后继线索的指针。19. 1，RChild
20. 本节中我们学习的树的存储结构有____孩子表示法_________、_双亲表示法__________和__孩子兄弟表示法_________。20. 孩子表示法，双亲表示法，长子兄弟表示法
二、填空题
1. 在一个图中，所有顶点的度数之和等于所有边数的________倍。 1. 2
2. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。 2. n(n-1)/2，n(n-1)
3. 假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{<a,c>, <a,e>, <c,f>, <d,c>, <e,b>, <e,d>}，则出度为0的顶点个数为________，入度为1的顶点个数为________。3. 2，4
4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。4. n-1
5. 表示图的两种存储结构为__________和__________。5. 邻接矩阵，邻接表
6. 在一个连通图中存在着________个连通分量。6. 1
7. 图中的一条路径长度为k，该路径所含的顶点数为________。7. k+1
8. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________个连通分量。  8. 3
9. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为_____undefined_____。9. n，n
10. 对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为________和________。10. 2e，e
11. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有________和________结点。11. 出边，入边
12. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为________和________。 12. O（n），O（e/n）
13. 假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为________和________。13.O（n2），O（n+e）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。