23年408数据结构

 第一题：

解析：

第一点，我们要知道顺序存储的特点：优点就是随用随取，就是你想要查询第几个元素可以直接查询出来，时间复杂度就是O(1)，缺点就是不适合删除和插入，因为每次删除和插入一个元素之后都可能需要调整剩下的元素，因此时间复杂度不确定[最好情况下是O(1)，最坏情况下是O(n)，平均时间复杂度是O(n)]。由此可知，在顺序表中，查询（也就是获取）第i个元素的平均时间复杂度是O(1)。选项D对，且直接排除B,C，最后在来看一看A选项：在顺序表中查找一个指定值的元素，可能需要遍历整个数组，因此时间复杂度是O(n)。选项A错。

答案选D。   

第二题：

解析：注意题目说的是一个双向链表，该题考察的是双向链表的插入，这种题就是要画图。

在执行题目给的语句之后，结点p（p指针所指向的结点简称结点p，后面的同理）的next指针指向结点s，结点s的next指针指向结点q。因为是双向链表，还缺一个结点s到结点p的指针，结点q到结点s的指针。因为链表有一个特点就是未知的结点我们要用已知的指针表示出来不能直接使用，就比如这个结点q，在执行语句中并没有出现q指针，因此结点q就是未知的，先看一下结点q怎么给它表示出来：s->next=q，下图就是执行完语句之后的样子。

1.此时还缺一条结点s指向结点p的指针，观察图：结点s是已知的，怎么找到结点p？因为此时只有图中的三根指针，想找到结点p只能s->next->prev=p,

结点s到结点p的指针：s->prev=p,而p=s->next->prev，合并一下：s->prev=s->next->prev。

2.因为此时结点q的前指针prev还指向的p，我们应该把这个指针调整成指向s。

因此结点q到结点s的指针：q->prev=s,而s->next=q,合并一下也就是s->next->prev=s。
这题不难，就是要注意是双向链表，以及要细心留意一下有哪些指针和怎么用已有的指针来表示出各种结点。这是结点s插入完成的样子，可以对比着看一下。

答案选C

第三题：

解析：这个题的话你要知道三元组表是什么，三元组表储存了矩阵中关键字所在的行，列已经具体的值。三元组表储存稀疏矩阵时是不储存0的，只储存非零常数。因此你并不需要保存M中包含非零元素的行列数，因为只储存非零常数，而行和列同样能看到，数一下就行了，我们只还需要知道M的行数和列数就能将稀疏矩阵M还原出来了，就给非零常数填上去，其他位置添0就完了。

答案选A。

第四题：

解析：考察加权平均长度的计算方法：加权平均长度=带权路径长度/所有结点频次之和

第一步：构造哈夫曼树：

第二步：计算哈夫曼树带权平均长度：就是在带权路径长度的基础上再除一个所有频次之和。

答案选B。

第五题：

解析：这种题就你看这个结点的序列顺序，然后依次把字母添上去就行，最后是这个样子：

，然后根据这个图把前序序列写出来就行。

答案选A。

第六题：

解析：这个考察单源最短路径算法，我们说单源最短路径就是求一个点到另一个点的最短路径。而单源最短路径包括BFS算法和迪杰斯特拉算法，这两个算法都没有出现在题目当中，再来看看1,2。1,2是用来构造最小生成树的，边都变少了，显然不能求某点到其余顶点的最短路径，下面来看看3，广度优先搜索算法是从点一层一层往外拓展然后进行搜索的，越往外的顶点距离该点的距离越远，所以3是对的。

答案选C。

第七题：

解析：这题很奇怪，把终端结点当成了叶子结点。

1：插入操作可能增加树的高度：考察B树的插入。1对。

2：若被删结点是叶结点，显然会导致叶结点的变化:若被删结点不是叶结点，则要先将被删结点和它的前驱或后继交换，最终转换为删除叶结点，还是会导致叶结点的变化，Ⅱ正确。

3：如果在非叶结点中查找到了给定关:键字，则不用向下继续查找，Ⅲ错误。

4：插入关键字的初始位置是最底层叶结点，但可能因结点分裂而被转移到父结点中，IV错误。

答案选B。

第八题：

解析：

第一次折半：300

第二次折半：150

第三次折半：75

第四次折半：38（37 1 37注意第38元素左边37个元素，右边37个元素，因此下次折半的个数是37+1=38）

第五次折半：19（9 1 9注意第10元素左边9个元素，右边9个元素，因此下次折半的个数是9+1=10）

第六次折半：10

第七次折半：5（2 1 2注意第3元素左边2个元素，右边2个元素，因此下次折半的个数是2+1=3）

第八次折半：3（1 1 1注意第2元素左边1个元素，右边1个元素，因此下次折半的个数是1+1=2）

第九次折半：2

第十次折半：1

最多十次

答案选B。

第九题：

解析：

第一步：计算散列函数，将关键字填上去：

最后是这个样子：

第二步：计算查找失败的平均查找长度，做这个题需要我们非常的细心。首先，我们要清楚逻辑删除的概念：当我们删除掉散列表中的一个数之后，这个位置并不是为空了，里面的值会变为-1，为什么会这样的呢，因为假设如果表中还存在一个关键字0，

，我们算出来和25的位置是冲突的，经过线性探测再散列法之后串到了0的位置，如果我们使用线性查找到4这个位置的值时，发现为空的话，就不会继续查找了，就会漏点这个0，因为0原本也是在4这个位置的，所以这里的位置不是空，而是-1，我们在查找H=4时，查到里面的关键字是-1，说明还没有完事，接着向后查找到0这个位置，发现是空的，这时候才算是查找失败，因此查找H=4时，是要查找两次的，这个要注意。

查找失败的平均查找长度:是从这个点开始到下一个空节点的长度÷所有结点的个数之和。

这题要注意的就是查找H=4，失败的次数是2次。

答案选C。

第十题：

解析：

这个题太简单了，我们正常的话都会记住稳定的算法：冒泡排序，归并排序，直接插入，基数排序，计数排序，排除掉这些就是不稳定的算法，直接排除A,B,D

答案选C。

第十一题：

解析：考察快速排序的演变过程。

每一次排序之后，都会确定枢轴元素在序列中最终的位置，且它的左边都是小于这个枢轴元素的，右边都是大于这个枢轴元素的。显然这个枢轴元素就是81.

答案选D。