数据结构考研错题集_对于下图所示的无向图,若从顶点a开始进行先深搜索,可得到的顶点序列可能为

1、一颗完全二叉树上与1001个结点，其中叶子结点的个数是（）

解法一： 512<1001<1024 因此该完全二叉树有10层，第10层的叶子节点数=1001-511=490 第9层上非叶子节点数=490/2=245个，第9层总结点数=256， 因此第9层上叶子结点数=256-245=11个，该数总叶子结点个数为501个

解法二：完全二叉树的最后一个结点的编号一定是1001，则它的父结点的编号为1001/2=500，则叶子结点个数为1001-500=501.
总结一下：完全二叉树的最后一个结点的编号是n，则它的父结点的编号为[n/2]，则叶子结点个数为n-[n/2]。

2、一颗非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）
A、所有的结点均无左孩子
B、所有的结点均无右孩子
C、只有一个叶子结点
D、是任意一颗二叉树

答案：C

解法：先序遍历是“中左右”，后序遍历为“左右中” ，没有左子树时，就变成了“中右“和“”右中”，没有右子树时，就变成了"中左"和"左中"，所以没有左孩子或者没有右孩子都可以。

3、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）
A、非连通
B、连通
C、强连通
D、有向

答案：连通图

连通图：在无向图中，对于任意两个顶点都是连通的
连通分量：无向图中的极大连通子图
强连通图：在有向图中，对于每一对vi,vj都存在vi到vj和vj到vi的路径
强连通分量：有向图中的极大强连通子图

4、Prim算法适合构建稠密图的最小生成树，算法时间复杂度与网中的边数无关
Kurskal适合求稀疏网的最小生成树

5、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）

答案：(n+1)/2

解析：第一个数的比较次数为1，第二个数的比较次数为2。。。以此类推第N个数的比较次数为N，所以总的比较次数为1+2+…+N=N(N+1)/2,平均比较次数为(N+1)/2,也即平均查找长度。

6、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用（）查找法

答案：分块查找

解析：
分块查找是折半查找和顺序查找的一种改进方法，折半查找虽然具有很好的性能，但其前提条件时线性表顺序存储而且按照关键码排序，这一前提条件在结点树很大且表元素动态变化时是难以满足的。而顺序查找可以解决表元素动态变化的要求，但查找效率很低。如果既要保持对线性表的查找具有较快的速度，又要能够满足表元素动态变化的要求，则可采用分块查找的方法。
分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。
分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时，只需将该节点调整到所在的块即可。在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。
需要注意的是，当节点变化很频繁时，可能会导致块与块之间的节点数相差很大，没写快具有很多节点，而另一些块则可能只有很少节点，这将会导致查找效率的下降。

7、折半查找与二叉排序树的时间性能（）

答案：有时不相同

解析：
二叉排序树不一定是平衡树，它是只要求了左右子树与根结点存在大小关系，但是对左右子树之间没有层次差异的约束，因此通过二叉排序树进行查找不一定能够满足logn的，例如一棵只有多层左子树的而叉排序树。 只有是一棵平衡的二叉排序树时，其查找时间性能才和折半查找类似。

8、采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字（）

答案：不一定都是同义词

9、稳定的排序：直接插入排序、冒泡排序、归并排序、基数排序
不稳定的排序：希尔排序、快速排序、直接选择排序、堆排序

10、一棵有124个叶子结点的完全二叉树，最多有（）个结点

答案：248

解析：
首先明白完全二叉树度为1的结点数为0或1

n0=124, n0=n2+1 n2=123;
N=n0+n1+n2=247+n1=248

11、已知一棵完全二叉树的第6层有8个叶结点，则该完全二叉树的结点个数最多是（）

答案： 111

解析：
第6层有8个叶子结点，则，可能第7层没有结点，也有可能有结点，因此第7层有结点时，结点个数最多

12、线索二叉树是一种（）结构

答案：物理结构

解析：物理结构又称为存储结构，单纯说二叉树才是逻辑结构，每个结点的 线索，即前驱和后继是 通过指针去定义的，而 指针是c语言的一种功能，这就满足了定义中的 “使用计算机语言实现的逻辑结构”。

数据的逻辑结构
数据元素之间的逻辑关系，与数据的存储无关。
数据的存储结构
数据结构在计算机中的表示，是使用计算机语言实现的逻辑结构，它依赖于计算机语言。

13、n个结点的线索二叉树上含有的线索数为（）

答案：n+1

一个有n个节点的线索二叉树，每个节点都有指向左右孩子的两个指针域，则共有2n个指针域，而n个节点共有n-1条分支，所以共有2n-(n-1)个空指针域，即有n+1个线索

14、利用二叉链表存储森林时，根结点的右指针是（）

答案：不一定为空

二叉链表转为森林时，如果森林不止一棵树，则根结点的右指针会指向其他树的根结点

15、若森林F有15条边，25个结点，则F包含树的个数是（）

答案：10

一棵树有n条边则必有n-1个结点

16、若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是（）

答案：中序遍历

具体可以写一个二叉树，将他转化为树，会发现对树的后根遍历与对二叉树的中序遍历结果一样

17、一个有28条边的非连通无向图至少有（）个顶点

答案：9个

可以想象一个完全图＋一个独立的点
n个顶点 最多拥有 n(n-1)/2条边，所以8个顶点最多有28条边，要想28条边而且保持非连通，至少要9个节点，第九个节点是孤立的，不与任何节点连通。

18、对于一个有n个顶点的图：若是连通无向图，其边的个数至少为()；若是强连通有向图，其边的个数至少为（）

答案：n-1, n

无向图：其构成树的情形就是边最少的情况 n-1
有向图：环的结构

19、无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G有（）个顶点

答案：16

无向图所有顶点度数之和=边数*2=46
设度为2的顶点数为x
则 54+34+x*2=46 得x=7
所以定点数为16

20、若具有n个顶点的图是一个环,则它有（）棵生成树

答案：n

生成树：极小连通子图
n个顶点构成的环有n条边，随便去掉一条都是一个生成树

21、设哈夫曼编码的长度不超过4，若已对两个字符编码为1和01，则还最多可对（）个字符编码

答案：4

在哈夫曼编码中，一个编码不能是任何其他编码的前缀。3位编码可能是001，对应的4位编码只能是0000和0001。3位编码也可能是000，对应的4位编码只能是0010和0011.若全采用4位编码，则可以为0000,0001,0010和0011.

1）DFS、采用邻接矩阵表示
空间复杂度：

由于DFS需要一个递归工作栈，最差的情况是如图所示。当从第一个节点开始遍历时，先访问它，修改它的访问标记。然后找到它的第一个邻居（把它的邻居称为a），访问a，修改a的访问标记。

从a找到a的邻居（称为b），访问b，修改b的访问标记 ，…，依次递归，每个节点都需要进入函数调用栈，最深的函数栈层数为n，故其空间复杂度为O(n-1)~O(n)。

时间复杂度：

时间复杂度为非两个部分：a：访问每个节点花费的时间 b：在每个节点找邻居花费的时间。

a：n个节点需要O(n)；

b：由于是邻接矩阵，对于节点i，需要扫描第i行的每一个元素，需要O(n)；

总的复杂度O(n^2)。

2）DFS、采用邻接表表示
空间复杂度：

同邻接矩阵的分析

时间复杂度：

时间复杂度分为两个部分：a：访问每个节点花费的时间 b：在每个节点找邻居花费的时间。

a：n个节点需要O(n)；

b：采用邻接表，总共的找邻居时间复杂度就是遍历边表的时间复杂度。对于有向图：O(e)，对于无向图O(2e)~O(e)（取最高阶）;

总的复杂度O(n+e)。

1）BFS、采用邻接矩阵表示
空间复杂度：

无论是邻接表还是邻接矩阵，BFS算法需要借助一个辅助队列，在最坏的情况下（如下图从中心节点出发），n个顶点需全入队一次，空间复杂度O(n)；

时间复杂度：

时间复杂度为非两个部分：a：访问每个节点花费的时间 b：在每个节点找邻居花费的时间。

a：n个节点需要O(n)；

b：由于是邻接矩阵，对于节点i，需要扫描第i行的每一个元素，需要O(n)；

总的复杂度O(n^2)。

2）BFS、采用邻接表表示
空间复杂度：

同上

时间复杂度：

时间复杂度分为两个部分：a：访问每个节点花费的时间 b：在每个节点找邻居花费的时间。

a：n个节点需要O(n)；

b：采用邻接表，总共的找邻居时间复杂度就是遍历边表的时间复杂度。对于有向图：O(e)，对于无向图O(2e)~O(e)（取最高阶）;

总的复杂度O(n+e)。

深度优先生成树


红色部分即是生成树，即遍历一次走过的顶点的路径

广度优先生成树


22、判断有向图中是否存在回路，除可以利用拓扑排序外，还可以利用（）

答案：深度优先遍历算法

23、最短路径一定是简单路径
Dijkstra算法适合求解有回路的带权图的最短路径，也可以求任意两个顶点的最短路径，不适合求带负权值的最短路径问题

24、关于判断一个有向图是否有环

①深度优先搜索：根据深度优先搜索，我们这里默认按行进行遍历，对于第一行，起始节点就是第一行对应到那个元素0，遍历到第二个元素时发现不为0，则节点0可以到达节点1；接着以节点1作为中转点，遍历节点1对应的那一行，也就是矩阵中的第二行，发现节点1可以到达节点2；同理，继续遍历节点2所在的行，发现节点2可以到达节点0，而节点0正是起始节点，也就是发现了有向图中存在着环路。

② 拓扑排序：当某顶点不为任何边的头时才能加入序列,存在环时环中的顶点一直是某条边的头
不能加入拓扑序列。也就是说,还存在无法找到下一个可以加入拓扑序列的顶点，则说明此图存在回路。

③关键路径：能否判断一个图有环,则存在一些争议。关键路径本身虽然不允许有环,但求家关键路径的算法本身无法判断是否有环,判断是否有环是求关键路径拓扑排序。

25、若一个有向图的顶点不能排在一个拓扑序列中，则可判定该有向图（）

答案：含有顶点数目大于1的强连通分量

分析：强连通图顶点数为1时，可以排在一个拓扑序列中，含有顶点数目大于1的强连通图必有环

强连通图一定有环，但有环未必是强连通图

26、若一个有向图具有有序的拓扑排序序列，则它的邻接矩阵必定为（）

答案：三角矩阵

分析：此处的三角矩阵指的是线代中的上（下）三角矩阵，且主对角线元素为0，则必为有序的拓扑排序序列，
若把此处的有序去掉，则为一般矩阵

27、在图G的最小生成树G1中，某条边的权值可能会超过为选边的权值
有向无环图的拓扑序列唯一，无法唯一确定图

28、所有权值最小的边一定会出现在所有的最小生成树中（x） 分析：当权值最小的边有多条，且构成环，则不会出现在最小生成树中

29、最小生成树的代价唯一（√）

30、普利姆算法与边无关，适合于稠密图
克鲁斯卡尔算法适合于稀疏图

31、树或森林与二叉树之间存在一一对应的关系。任何一棵树或一个森林可唯一地对应到一棵二叉树；反之，任何一棵二叉树也能唯一地对应到一个森林或一棵树。

32、先根次序遍历森林等同于按先根遍历对应得二叉树,后根次序遍历森林等同与按中根遍历对应得二叉树

33、解决散列法中出现冲突问题常采用的方法是____。

答案：题目中说的是解决冲突的方法：有以下三种：
1：开放地址法（线性探测、二次探测、伪随机探测）
2：链地址法
3：多重散列法

34、折半查找过程所对应的判定树是一棵 平衡二叉树

35、采用开放地址法解决冲突的散列查找中，发生聚集的原因主要是解决冲突的方法选择不当

36、一个好的哈希函数其转换地址应尽可能均匀，而且函数运算应尽可能简单

37、当循环列表非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算，这种情况称为上溢

38、评价基于比较的排序算法的时间性能，主要标准是关键码的比较次数和记录的移动次数

39、线索二叉树中某结点R没有左孩子的充要条件R.ltag=1

解析：R.lchild为空则没有左孩子，但是没有左孩子R.lchild却不一定为空，因为它可以指向R的前驱结点。

40、链表的每个结点中都恰好包含一个指针（）。

答案：错误，有可能是双向链表

41、对二维或多维数组，分按行序为主序、列序为主序两种不同的存储方式

42、当循环队列为空时，不能进行出队运算，这种情况称为 下溢 不能入队，称为上溢

43、构造哈希表包括选择哈希函数和确定解决冲突方法
44、折半查找时要求线性表中必须采用顺序存储结构，而且表中元素按关键字有序排列。

45、设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省时间

答案：双向循环链表
解析：双向循环链表可以从头直接到尾

46、数据对象是指 相互之间存在一种或多种特定关系的数据元素的集合

47、以下哪个数据结构不是多型数据类型（）
答案：字符串
解析：多型数据是数据元素的类型不确定，字符串的每个元素始终都是字符，而不会是别的类型。

48、算法的计算量的大小称为计算的 复杂性

49、同一个算法，实现语言的级别越高，执行效率越低

50、算法的健壮性：当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果

51、在汉诺塔递归中，假设碟子的个数为n，则时间复杂度为 2^n

52、哈夫曼树、平衡二叉树都是数据的存储结构

53、数据的物理结构包括数据元素的表示和数据元素间关系的表示

54、二叉树的顺序存储结构比链式存储更浪费时间
55、静态链表中指针表示的是 下一元素在数组中的位置
56、某线性表用带头结点的循环单链表存储，头指针为head，当head->next->next->next=head成立时，线性表长度可能是 0或2

57、顺序存储结构是通过结点物理上相邻表示元素之间的逻辑关系，链式存储结构是通过指针表示元素之间的关系

58、循环单链表的最大优点是从任一结点出发都可访问到链表中每一个元素

59、带头结点的双向循环链表L为空表的条件是 L->next=L->prior=L
60、在双向循环链表中，在p所指的结点之后插入指针f所指的结点，其操作是f->next=p->next,p->next->piror=f;

61、用链接方式存储的队列，在进行插入运算时（）
答案：头、尾指针可能都要修改
队列如果是不带头结点的队列，则插入时，头尾指针都要修改

62、在二叉排序树中插入一个结点的时间复杂度为（）
答案：O（n）