数据结构期末PTA选择汇总
一、栈的应用
1、假设有5个整数以1、2、3、4、5的顺序被压入堆栈，且出栈顺序为3、5、4、2、1，那么为了获得这样的输出，堆栈大小至少为：4.
2、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是a、f、e、d、c、b
3、设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是3、2、1、5、4
4、令P代表入栈，O代表出栈。当利用堆栈求解后缀表达式1 2 3 + * 4 –时，堆栈操作序列是PPPOOPOOPPOOPO
5、表达式a*(b+c)-d的后缀表达式是a b c + * d -
6、从栈顶指针为ST的链栈中删除一个结点且用X保存被删结点的值，则执行X= ST->data; ST = ST->next;
7、若top为指向栈顶元素的指针，判定栈S（最多容纳m个元素）为空的条件是S->top == -1
8、利用大小为n的数组（下标从0到n-1）存储一个栈时，假定栈从数组另一头开始且top==n表示栈空，则向这个栈插入一个元素时，修改top指针应当执行top--
9、给定一个堆栈的入栈序列为{ 1, 2, ⋯, n }，出栈序列为{ p1, p2, ⋯, pn }。如果p2=n，则存在多少种不同的出栈序列？答案：n-1种
10、入栈出栈满足“先进先出”的原则
11、链式栈与顺序栈相比，一个比较明显的优点是通常不会出现栈满的情况
12、由两个栈共享一个向量空间的好处是节省存储空间，降低上溢发生的机率
13、栈的插入和删除操作在栈顶进行。
14、栈可用于递归调用。
15、若一个栈的入栈序列为1、2、3、…、N，其输出序列为p1、p2、p3、…、pN。若p1=N，则pi为n−i+1
二、二叉树的性质
1、一个二叉树第i层的最大节点数为,i>=1.
2、深度为k的二叉树有最大的节点总数,k>=1。
3、对于任何非空的二叉树T，若表示叶节点的个数、
表示度为2非叶结点个数，那么两者满足关系
。
4、具有n个节点的完全二叉树的深度k为。
三、树与二叉树
1、设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中的叶子结点数有8个。
2、一棵树有n1个孩子数为1的结点，n2个孩子数为2的结点，……，nm个孩子数为m的结点，则该树的叶结点数为：
3、“二叉树为空”意味着二叉树没有节点。
4、一棵二叉树的度可以小于2。
5、对一棵满二叉树，m个树叶，n个结点，深度为h，则.
6、一棵度为d的树，它的结点数为.
7、对一棵深度为h的二叉树，其结点的个数最多为。
8、树中的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左右之分，而二叉树的结点有左右之分；树和二叉树均为树形结构。
9、在有n个结点的二叉树的二叉链表表示中，空指针数。
10、树最适合于用来表示元素之间具有分支层次关系的数据。
11、如果一棵非空k（k≥2）叉树T中每个非叶子结点都有k个孩子，则称T为正则k叉树。若T的高度为h（单结点的树h=1），则T的结点数最多为：。
12、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是：82。
13、深度为h的满m叉树的第k层有个结点。
14、二叉树一定是有序数。
15、以二叉链表作为二叉树的存储结构，在具有 n 个结点的二叉链表中（n>0），空链域的个数为。
四、二叉树的遍历与求解
1、设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是n在m左方。
2、如果二叉树的前序遍历结果是12345，后序遍历结果是24531，那么该二叉树的中序遍历结果是21435.
3、设 T 是非空二叉树，若 T 的后序遍历和中序遍历序列相同，则 T 的形态是所有节点只有左孩子。
4、已知二叉树的前序遍历序列为 ABDCEFG，中序遍历序列为 DBCAFEG，则后序遍历序列为DCBFGEA。
5、某二叉树的前序和后序遍历序列正好相反，则该二叉树一定是高度等于其节点数。
6、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序不发生改变。
7、要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是只有右子树。
8、如果二叉树的后序遍历结果是FDEBGCA，中序遍历结果是FDBEACG，那么该二叉树的前序遍历结果是ABDFECG。
9、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为CBEFDA。
10、已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是cedba。
11、①只有一个结点的二叉树的度为0；②深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
12、按照二叉树的定义，具有3个结点的二叉树有5种。
13、按照二叉树的定义，具有3个结点的二叉树有为16.
五、二叉搜索树
1、将一系列数字顺序一个个插入一棵初始为空的AVL树中，第一次旋转是“右-左”双旋是3,1,4,6,5,2。
2、将 1, 2, 3, 6, 5, 4 顺序一个个插入一棵初始为空的AVL树，会经历一个“右-右”旋两个“右-左”旋。
3、在任意一棵非空平衡二叉树（AVL 树）T1 中，删除某结点 v 之后形成平衡二叉树 T2，再将 v 插入 T2 形成平衡二叉树 T3。若 v 是 T1 的叶结点，则 T1 与 T3 可能不相同。
4、给定平衡二叉树如下图所示，插入关键字 23 后，根中的关键字是：
25.
5、如果AVL树的深度为6（空树的深度定义为−1），则此树最少有33个结点。
6、 对二叉搜索树进行中序遍历可以得到从小到大的排序序列。
7、已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉搜索树后，最后两层上的结点总数为2.
8、若二叉搜索树是有N个结点的完全二叉树，所有结点的平均查找效率是O(logN)，最小值一定在叶结点上，中位值结点在根结点或根的左子树上。
9、将{ 32, 2, 15, 65, 28, 10 }依次插入初始为空的二叉搜索树。则该树的前序遍历结果是：32, 2, 15, 10, 28, 65。
10、下列二叉树中，可能成为折半查找判定树（不含外部结点）的是：
11、已知二叉排序树如下图所示，元素之间应满足的大小关系是：
x3<x5<x4 
12、AVL树是一种平衡的二叉搜索树，左、右子树高度差的绝对值不超过1。
13、满足平衡二叉树定义的是：
14、已知由（60,30,56,78,12,45）序列构成的二叉排序树，其等概率成功查找的平均查找长度为15/6.
15、在有N个结点且为完全二叉树的二叉搜索树中查找一个键值，其平均比较次数的数量级为：O(logN)。
16、在二叉搜索树中插入一个新结点，总是插入到最下层，作为新的叶子结点。
17、高度为8的平衡二叉树的结点数至少有54个。
18、由20，10，5，30，40，25，8输入序列所构造的二叉AVL平衡树，经历了4次旋转，依次是LL、RR、RL、LR旋转，最终得到的平衡树的根结点数的值20，其左子树的结点值为8，右子树的结点值为30。
19、、
在此平衡树中插入结点8后，会做RL旋转，旋转后根节点是5，其左节点是4，右节点是10。
六、图
1、具有5个顶点的有向完全图有20条弧。
2、若一个有向图用邻接矩阵表示，则第i个结点的入度就是：第i列的非零元素的个数。
3、有向图的邻接矩阵可以是对称的，也可以是不对称的。
4、设N个顶点E条边的图用邻接表存储，则求每个顶点入度的时间复杂度为：O(N+E)。
5、在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。
6、如果G是一个有28条边的非连通无向图，那么该图顶点个数最少为9.
7、下面给出的有向图中，各个顶点的入度和出度分别是：入度: 0, 2, 3, 1, 2; 出度: 3, 2, 1, 1, 1
8、
给定一个有向图的邻接表如下图，则该图有3 {{2}, {4}, {0, 1, 3, 5}}个强连通分量
9、
给定有向图的邻接矩阵如下：
顶点2（编号从0开始）的出度和入度分别是：0,2.
10、设无向图为 G=(V，E)，其中 V={v1,v2,v3,v4}，E={(v1,v2)，(v3,v4)，(v4,v1)，(v2,v3)，(v1,v3)}。则每个顶点的度依次为：3,2,3,2.
11、对于给定的有向图如下，其邻接矩阵为：
12、对于给定的有向图如下，其逆邻接表为：
13、以下哪个是给定无向带权图的邻接矩阵
14、图的遍历是从给定的源点出发每一个顶点仅被访问一次。
15、遍历的基本算法有两种：深度遍历和广度遍历。
16、图的深度遍历是一个递归过程。
17、已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为1,V2,V4,V5,V6,V3
18、给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：V1,V5,V4,V7,V6,V3,V2
19、在图中自c点开始进行广度优先遍历算法可能得到的结果为c,f,a,d,e,b
20、给定一有向图的邻接表如下。从顶点V1出发按广度优先搜索法进行遍历，则得到的一种顶点序列为：V1,V3,V2,V4,V5
21、已知一个图的邻接矩阵如下，则从顶点V1出发按广度优先搜索法进行遍历，可能得到的一种顶点序列为：V1,V2,V3,V5,V4,V6
22、对下图从顶点C出发进行广度优先搜索CBDAEHFG
23、已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是11.
24、对于无向图G=(V,E) ,当|V|>|E|+1 时，G一定不是连通的。
25、若无向图 G=(V,E) 的邻接多重表如下图所示，则 G 中顶点 b 与 d 的度分别是2,4
26、修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句移动到退出递归前（即执行输出语句后立即退出递归）。采用修改后的算法遍历有向无环图 ，若输出结果中包含 中的全部顶点，则输出的顶点序列是 的逆拓扑有序序列。
七、生成树、Prime、Kruskal
1、任何一个带权无向连通图的最小生成树——可能是不唯一的。
2、
给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：14
3、
给定有权无向图如下。关于其最小生成树，最小生成树不唯一，其总权重为23。
4、
给出如下图所示的具有 7 个结点的网 G，采用Prim算法，从4号结点开始，给出该网的最小生成树。树结点收集顺序是4563201.
5、
已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是：(b,f), (b,d), (a,e), (c,e), (b,e)
6、无向连通图的最小生成树有一个或多个。
7、若一个无向连通图没有权值相同的边，则该无向图的最小生成树唯一。
8、在求最小生成树时，Kruskal算法更适合于稀疏图。
9、
给定下图，其最小生成树的总权重是30.
10、适合构造一个稠密图G的最小生成树Prime算法。
11、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为O(n+e)。
12、
给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：23.
13、任何一个无向连通图的最小生成树有一颗或者是多颗。
14、在求最小生成树时，Prim算法更适合于稠密图。
15、用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是逆拓扑有序序列。
16、如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是连通图。
17、
给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：V1,V5,V4,V7,V6,V3,V2
18、
在图中自c点开始进行广度优先遍历算法可能得到的结果为：c,f,a,d,e,b。
19、
给定一有向图的邻接表如下。若从v1开始利用此邻接表做广度优先搜索得到的顶点序列为：{v1, v3, v2, v4, v5}，则该邻接表中顺序填空的结果应为：v3, v2, v4。
20、
给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：8.
21、用于求解最小生成树的是Prime算法。
22、克鲁斯卡尔（Kruskal）算法：
- 假设连通图G=(V,E)，其中V是顶点集，E是边集。初始时，最小生成树T=(V′,E′)，V′为图G中所有顶点的集合，E′为空集。
- 从E中选取权值最小的边，若将该边加入E′中不会形成回路，则将其加入E′；否则，舍弃该边。
- 重复上述步骤，直到E′中的边数为n−1或者所有边都已考察过为止，其中n是图G中顶点的个数。此时T=(V′,E′)就是图G的一棵最小生成树。
23、Prime算法 ：
- 从图中任意选择一个起始顶点v0，将其加入到最小生成树的顶点集合U中。
- 不断从与U中顶点相邻的边中选择权值最小的边，将该边及其对应的另一个顶点加入到U中，直到所有顶点都被加入到U中。
八、最短路和拓扑排序
1、在一个有权无向图中，如果顶点b到顶点a的最短路径长度是10，顶点c与顶点b之间存在一条长度为3的边。（c与a的最短路径长度不超过13；c与a的最短路径不小于7）
2、我们用一个有向图来表示航空公司所有航班的航线。最适合解决找给定两城市间最经济的飞行路线问题是Dijkstra算法。
3、数据结构中Dijkstra算法用来解决最短路径问题。
4、
使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：5,2,3,6,4.
5、最短路径的生成算法可用Dijkstra算法。
6、求图的最短路径可以用Dijkstra算法。
7、Dijkstra算法是按长度递增的顺序求出图中某顶点到其余顶点的最短路径的方法。
8、
使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：2,4,3,6,5,7
9、
试利用 Dijkstra 算法求下图中从顶点 A 到其他顶点的最短距离及对应的路径。ACFEDBG
10、数据结构中Dijkstra算法用来解决最短路径问题。
11、对含有n个顶点、e条边的带权图求最短路径的Dijkstra算法的时间复杂度为O(n^{2})。
12、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用深度优先遍历算法。
13、n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是O(n+e)。
14、在TopSort函数中，如果外循环还没结束，就已经找不到“未输出的入度为0的顶点”，则说明图中必定存在回路。
15、已知无向连通图 G 中各边的权值均为 1。一定能够求出图 G 中从某顶点到其余各顶点最短路径的是：图的广度优先搜索算法。
16、
使用 Dijkstra 算法求下图中从顶点 1 到其余各顶点的最短路径，将当前找到的从顶点 1 到顶点 2、3、4、5 的最短路径长度保存在数组 dist 中，求出第二条最短路径后，dist 中的内容更新为：21,3,14,6.
17、
对下图进行拓扑排序，可以得到不同的拓扑序列的个数是：3.
18、
下图为一个AOV网，其可能的拓扑有序序列为：ABCEDF
19、修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句移动到退出递归前（即执行输出语句后立即退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点，则输出的顶点序列是 G 的：逆拓扑有序序列。
20、
给定如下有向图，该图的拓扑有序序列的个数是：1.
21、求解最短路径的Floyd算法的时间复杂度为O(nnn)。
22、
若要求在找到从S到其他顶点最短路的同时，还给出不同的最短路的条数，我们可以将Dijkstra算法略作修改，增加一个count[]数组：count[V]记录S到顶点V的最短路径有多少条。则count[V]应该被初始化为：count[S]=1; 对于其他顶点V则令count[V]=0。
23、
算法：对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是：3,1,4,2,6,5.
