网站建设所需技术,做网站的公司深圳,标志设计作业,做国外有那些网站比较好的第一题#xff1a; 解析#xff1a; 第一点#xff0c;我们要知道顺序存储的特点#xff1a;优点就是随用随取#xff0c;就是你想要查询第几个元素可以直接查询出来#xff0c;时间复杂度就是O(1)#xff0c;缺点就是不适合删除和插入#xff0c;因为每次删除和插入一… 第一题 解析 第一点我们要知道顺序存储的特点优点就是随用随取就是你想要查询第几个元素可以直接查询出来时间复杂度就是O(1)缺点就是不适合删除和插入因为每次删除和插入一个元素之后都可能需要调整剩下的元素因此时间复杂度不确定[最好情况下是O(1)最坏情况下是O(n)平均时间复杂度是O(n)]。由此可知在顺序表中查询也就是获取第i个元素的平均时间复杂度是O(1)。选项D对且直接排除B,C最后在来看一看A选项在顺序表中查找一个指定值的元素可能需要遍历整个数组因此时间复杂度是O(n)。选项A错。 答案选D。 第二题 解析注意题目说的是一个双向链表该题考察的是双向链表的插入这种题就是要画图。 在执行题目给的语句之后结点pp指针所指向的结点简称结点p后面的同理的next指针指向结点s结点s的next指针指向结点q。因为是双向链表还缺一个结点s到结点p的指针结点q到结点s的指针。因为链表有一个特点就是未知的结点我们要用已知的指针表示出来不能直接使用就比如这个结点q在执行语句中并没有出现q指针因此结点q就是未知的先看一下结点q怎么给它表示出来s-nextq下图就是执行完语句之后的样子。 1.此时还缺一条结点s指向结点p的指针观察图结点s是已知的怎么找到结点p因为此时只有图中的三根指针想找到结点p只能s-next-prevp, 结点s到结点p的指针s-prevp,而ps-next-prev合并一下s-prevs-next-prev。 2.因为此时结点q的前指针prev还指向的p我们应该把这个指针调整成指向s。 因此结点q到结点s的指针q-prevs,而s-nextq,合并一下也就是s-next-prevs。 这题不难就是要注意是双向链表以及要细心留意一下有哪些指针和怎么用已有的指针来表示出各种结点。这是结点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 第四次折半3837 1 37注意第38元素左边37个元素右边37个元素因此下次折半的个数是37138 第五次折半199 1 9注意第10元素左边9个元素右边9个元素因此下次折半的个数是9110 第六次折半10 第七次折半52 1 2注意第3元素左边2个元素右边2个元素因此下次折半的个数是213 第八次折半31 1 1注意第2元素左边1个元素右边1个元素因此下次折半的个数是112 第九次折半2 第十次折半1 最多十次 答案选B。 第九题 解析 第一步计算散列函数将关键字填上去 最后是这个样子 第二步计算查找失败的平均查找长度做这个题需要我们非常的细心。首先我们要清楚逻辑删除的概念当我们删除掉散列表中的一个数之后这个位置并不是为空了里面的值会变为-1为什么会这样的呢因为假设如果表中还存在一个关键字0 我们算出来和25的位置是冲突的经过线性探测再散列法之后串到了0的位置如果我们使用线性查找到4这个位置的值时发现为空的话就不会继续查找了就会漏点这个0因为0原本也是在4这个位置的所以这里的位置不是空而是-1我们在查找H4时查到里面的关键字是-1说明还没有完事接着向后查找到0这个位置发现是空的这时候才算是查找失败因此查找H4时是要查找两次的这个要注意。 查找失败的平均查找长度:是从这个点开始到下一个空节点的长度÷所有结点的个数之和。 这题要注意的就是查找H4失败的次数是2次。 答案选C。 第十题 解析 这个题太简单了我们正常的话都会记住稳定的算法冒泡排序归并排序直接插入基数排序计数排序排除掉这些就是不稳定的算法直接排除A,B,D 答案选C。 第十一题 解析考察快速排序的演变过程。 每一次排序之后都会确定枢轴元素在序列中最终的位置且它的左边都是小于这个枢轴元素的右边都是大于这个枢轴元素的。显然这个枢轴元素就是81. 答案选D。
