20年408数据结构

 第一题：

解析：这种题可以先画个草图分析一下，一下就看出来了。

这里的m(7,2)对应的是这图里的m(2,7),第一列存1个元素，第二列存2个元素，第三列存3个元素，第四列存4个元素，第五列存5个元素，第六列存6个元素，第7列到m(2,7)只存了2个元素，因此m(7,2)在数组中是第1+2+3+4+5+6+2 = 23个元素，又因为数组是从下标为0开始的，所以元素m(7,2)的下标是22。

答案选C。   

第二题：

解析：Push入栈，Pop出栈

a入栈-b入栈-b出栈-c入栈-c出栈-d入栈-e入栈-e出栈，出栈序列是b-c-e

答案选D。

第三题：

解析：本题考察二叉树的顺序存储：最坏情况下：高度为h且只有h个结点的单支树叶至少需要2^h-1个存储单元，所以：

答案选A。

第四题：

解析：

① 森林的先序遍历对应二叉树的先序遍历；② 森林的中序遍历对应二叉树的中序遍历。

知道二叉树的先序序列和中序序列可以确定这颗二叉树：

由此可见后序序列为：bfedca

答案选C。

第五题：

解析：

很显然选项B是错误的，1先输入的话，1应该是2的根结点。

答案选B。

第六题：

解析：

根据题干可知，修改后的深度优先搜索算法的实现方式为退出递归前输出当前结点。退出递归的条件是当前结点无法再深入，即出度为0。因此，修改后的深度优先搜索算法会次序输出图中出度为0的点。而拓扑排序是输出入度为0的点，因此上述算法输出的顶点序列为逆拓扑有序序列。

答案选B。

第七题：

解析：

克鲁斯卡尔算法也叫加边法，就是每次在剩下的边里面选一个最短的边填上去，且不形成环，最后连接所有顶点。

由此可见，依次添加的边是(b,f),(b,d),(a,e),(e,c),(e,b)

答案选A。

第八题：

解析：

由关键路径的概念可知，显然答案选B，A错。

增加一个关键活动的时间会延长关键路径，显然会延迟工程的工期。C错

缩短一个关键活动的时间会缩短这条关键路径的工期，但是如果本来存在多条关键路径，这条缩短之后就不是关键路径了，自然也不会影响共层的工期。D错

答案选B。

第九题：

解析：

在二叉排序树中，根的左子树小于根结点，根的右子树大于根结点，在大根堆中只是保证了根是最大的。显然第三句错误。

答案选C。

第十题：

解析：

显然对于除了叶子结点以外的非根节点，关键字至少为4/2向上取整-1=1个，最多为4-1=3个

（1，3），对于根结点来说关键字最少是1个，最多是4-1=3个，因此，同一个结点中插入的关键字数量达到4个就要从中间位置（[m/2])将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（[m/2]）的结点插入原结点的父结点。

答案选B。

第十一题：

解析：

直接拿1，2，3，4，5举例，使用直接插入排序总共只需要4次比较，而快速选择排序第一趟排序就要比较4次，第1句对，不管是直接插入排序还是选择排序他们都不需要辅助空间，都是直接原地进行比较，第2句错，对于1，2，3，4，5这样一个完全有序的序列，不管用哪一种排序算法都不需要进行移动，移动次数都是0，所以第3句错。

答案选A。