22年408数据结构

 第一题：

解析：

观察一下这个程序：我们注意到最外层的循环是从i=1开始的，每次i=i*2，直到i<n为止，假设程序总共执行k次执行，则有2^(k+1)>=n。则k+1>=log(2)n这里是以2为底n的对数,

k>=log(2)n -1

我们再来看内层循环的特点：

i=1时        i=2时        i=4时        。。。        i=2^k

j=1            j=1           j=1            。。。        j=1

                 j=2           j=2            。。。        j=2

                                 j=3            。。。        j=3

                                 j=4            。。。        j=4

                                                  。。。       。。。

                                                  。。。        j=2^k   

我们来试着算一下内层循环一共执行了多少次：

 （这显然是一个等比数列，我们可以使用等比数列求和公式）

,把k的值log(2)n -1带入进去。

,结果是一个线性的表达式，选项B最接近。

答案选B。   

第二题：

解析：

A B明显错，我们做了这么多道推出栈顺序和入栈顺序的题了，看CD，如果入栈序列是abc

那么出栈序列也有可能是abc，只需要符号abc在入栈之后立刻出栈就好了，我们都知道栈有个特点是先进后出，输出的是栈顶元素，如果入栈序列是abc，依次将栈顶元素输出后的序列是cba。是逆序，显然D对

答案选D。

第三题：

解析：中序序列是左根右，题目要求p在q之前。

第一句：q是p的双亲，也就是说q是根结点，p是q的子结点，而且要求p在q之前，根据左根右可知，当p是q的左子树时满足条件。

第二句：q是p的右孩子，p是根结点，根据左根右，q一定在p的后面，满足条件。

第三句：根据左根右，左子树先被遍历，接着是根结点，然后才是q结点，因此在q前面的是根结点，不满足条件。

第四句：当p是q的左子树的右子树时满足条件。

答案选A。

第四题：

解析：

这就是一个简单的计算题，我们直接设这个三叉树的高度是h，题目要树的高度最少是多少，就是要让每一层的结点尽可能的最多，也就是满三叉树。那这样我们直接算高度为h的慢三叉树的结点个数是多少，(这显然是一个等比数列求和问题),直接把选项往里一带：

高度为8的满三叉树结点个数有：3280，

高度为7的满三叉树结点个数有：1093，

高度为6的满三叉树结点个数有：364，

高度为5的满三叉树结点个数有：121，

本题说该三叉树结点个数244，在121和364之间。

也就是说该三叉树是高度为6的非满三叉树。高度至少是6.

答案选C。

第五题：

解析：这种题就是举例子。

以1,2,3为例，画一个哈夫曼树：

对于一个定长编码，它的字符都是处于同一层才能使编码长度一致。

观察两幅图可知，两颗二叉树结点的个数显然不一致，A错。

两颗二叉树的高度显然是一致的,B错。

显然a和b是出于同一层的，C错。

对于一个定长编码，它的字符显然是处于同一层的，D对。

答案选D。

第六题：

解析：|V|指的是顶点数，|E|指的是边。

A显然不正确，当顶点数是100个，而边只有一个显然不是连通图。

B举例：

，边有6条，而顶点只有5个，而且不是连通图。

C我们说要想让一个图是连通的，边的数量至少是顶点的个数减一，而选项中边的个数甚至比顶点的个数还多一个，显然想要连通是错错有余的，C正确

D选项，边的个数至少要比顶点的个数少一个才能连通，而此时|E|<|V|-1,连最低的边的个数都达不到，D错误。

答案选C。

第七题：

解析：

答案选B。

第八题：

解析：

在5阶B树中，根结点的关键字个数最少是1个，最多是5-1=4个。

在除叶子结点以外的非根结点中，关键字个数最少是[5/2]向上取整-1=2个，最多是5-1=4个

在B树中，删除一个节点，如果关键字中的个数不符合B树的定义的话就需要调整，符合个数也可以调整，具体的调整方法，可以把该点的前驱，或者后继添补上这个空缺。

选项A：选择260的后继结点280来填补空缺，但是这样的话，右子树中的关键字个数只剩下了300，而我们说非叶子结点关键字个数最少是2个（注意下面一层是终端结点，不是叶子结点不要误会了。），我们就将300的后继结点350从根结点上移下来，与300，400，500一起合并成一个结点：

选项B：把260删除后，直接将100,110,280,300合并成了一个结点，且符合B树的定义。

选项C：

显然是对的。

选项D：90和110之间只有一个100，不符合最少2个关键字的设定，所以D错。

答案选B。

第九题：

解析：

1.装填因子越大，代表散列表中装填的个数越多，冲突的可能性越大，查找次数就会越大，所以第一句对，

2.散列函数以这两个为例：

显然对3取余比对7取余的更容易发生冲突，第二句也对。

3. 线性探测法很容易造成同义词，非同义词的聚集堆积现象，严重影响查找效率，就拿线性探测法和平方探测法来比较说，显然线性探测法的查找效率差，自然影响平均查找长度。

下表是不同方式处理冲突时的平均查找长度。

答案选D。

第十题：

解析：

将两个有序表合并成一个新的有序表：

答案选A。

第十一题：

解析：该题考察直接插入排序和快速排序的比较。

1.对于一个大部分有序的序列，不适合采用快速排序，这是一个老生常谈的问题了，所以第一句是对的。2.对于一个元素数量很少的序列，好像使用直接插入排序还是快速排序好像都挺快的，先放着，不过直接插入排序要更简单直接一点。3.直接插入排序是原地进行的，空间复杂度是O(1),快速排序空间复杂度最好log(2)n,最坏O(n),第三句正确，直接插入排序是稳定的。第四句对，科普一下：稳定的排序算法有：冒泡排序，归并排序，插入排序，基数排序，计数排序(未出现过)。

包括1和3的只有D。

答案选D。