19年408数据结构
第一题：
解析：
设程序执行了K次，则有x = K，n<=k^2,解得n=n^(1/2)
答案选B。
第二题：
解析：这道题直接当作一个结论来记，因为已经出现过很多次了：树的后根遍历和对应二叉树的中序遍历相同
这种题最适合用举例法了：
树： 对应的二叉树：
树的后根序列：E-B-C-A
对应二叉树的中序序列：E-B-C-A
答案选A。
第三题：
解析：
我们观察在构建哈夫曼树的过程中，符号始终是叶子节点，也就是说该哈夫曼树有n个叶子结点，同时，我们也能发现哈夫曼树中只有度为2和度为0的结点，这里可以用到一个二叉树的结论：在一棵二叉树中，度为2的结点比度为0的结点数（叶子结点）少一个。
度为1的结点数：n
度为2的结点数：n-1
总的结点数：n+n-1=115.
求出n=58
答案选C。
第四题：
解析：这种题的做法就是举例子，或者你要蒙的话就蒙个可能。
第一句：举例得证不相同
第二句：举例得证相同
第二句：举例得证不相同
答案选A。
第五题：
解析：我们说找最早开始时间就找它的头，找最晚开始时间就找它的尾。
关于这道题，首先要找到关键路径，关键路径就是找一条最长的路径。
找最早开始时间我们的策略就是从头到尾这个方向找到活动d开始的头2发生的时间，找最晚开始时间就是从尾到头这个方向找到尾4，然后减去活动d的权值就是最晚开始时间，
关键路径：很显然1-3-5-6 和 1-3-2-5-6都是关键路径，长度都是27.
活动d最早开始时间：活动d的起始结点是2，那我们找2的最早发生时间，从结点1出发，结点2要发生，就要让活动a和活动b先完成，活动a完成需要用3天，活动b完成需要8+4=12天，取最大值是12天，所以活动d的最早开始时间是12天。
活动d最晚开始时间：活动d这条边指向的是结点4，从6出发，往前推，结点4是结点6的前驱结点，因此最晚可以27-6=21天到达结点4,4的前驱结点是结点2，最晚可以21-7=14天的时候开始活动d，因此最晚开始时间是14天。
答案选C。
第六题：
解析：这道题考察出去重复点
第一步画图：以符号作为根结点，左右两个因数分别作为左子树和右子树。不难画出下面的图：
第二步将重复顶点去除：图中出现了两部分的x+y为了避免重复，需要重复利用‘/’号分别与+和x连线就表示（x+y）/ x,最终结果如下：5个顶点。
答案选A。
第七题：
解析：
第一句：数据的规模，如果待排序的数组很小，采用快速排序很方便，但是如果数组的大小是几千几百，肯定是采用基数排序更好一点。一对，
第二句：像快速排序这种经常进行查询比较的算法适合使用顺序存储，如果使用链式存储将会大大增加时间复杂度，二对，
第三句：对于两个权值相同的关键字k1和k2，使用不稳定的算法可能会改变k1，k2在数组中的相对位置，三对，
第四句：非常典型的一个问题：快速排序最坏时间复杂度。对于一个有序的序列，不适合使用快速排序。四也对。
答案选D。
第八题：
解析：
我们考虑一个算法的好坏时，需要考虑时间复杂度和空间复杂度，与空间复杂度相关的只有1和2.
答案选B。
第九题：
解析：注意题目使用的是线性探测法，因此要使用线性探测法的方式查找。
H(87) = 87%7 =3
H(40) = 40%7 =5
H(30) = 30%7 =2
H(6) = 6%7 =6
H(11) = 11%7 =4
H(22) = 22%7 =1
H(98) = 98%7 =0
H(20) = 20%7 =6
经过计算可以得知，这8个数存放在0-7这8个位置上。
如果H(key)=0,则需要一次访问0-8这九个位置，才能得知查找失败。
如果H(key)=1,则需要一次访问1-8这八个位置，才能得知查找失败。
如果H(key)=2,则需要一次访问2-8这七个位置，才能得知查找失败。
如果H(key)=3,则需要一次访问3-8这六个位置，才能得知查找失败。
如果H(key)=4,则需要一次访问4-8这五个位置，才能得知查找失败。
如果H(key)=5,则需要一次访问5-8这四个位置，才能得知查找失败。
如果H(key)=6,则需要一次访问6-8这三个位置，才能得知查找失败。
总共加起来：9+8+7+6+5+4+3=42
有8个关键字，平均查找失败的概率是42/8=6
答案选C。
第十题：
解析：
这种题简单，我们前面已经做过类似的，我们知道快速排序，每一轮排序都能确定一个关键字最终的位置，所以我们可以先把排好序的序列写出来先：2,5,12,16,28,32,60,72，然后一个一个选项进行比对，A选项28和72的位置是对的，B选项2和72的位置是对的，C选项2,16,28,32是对的，D选项，只有12的位置是对的，快速排序第二轮一定有两个元素的位置是确定的，所以D错
答案选D。
第十一题：
解析：
这里的k=12-1=11，当初始归并段的数量是122时，122-1对11取余正好是0，也就意味着可以构成严格k叉树，所以要补2个虚段。
答案选B。
原文地址：https://blog.csdn.net/weixin_62182040/article/details/142621265
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！