15年408-数据结构

第一题

解析：

栈第一次应该存main的信息。

然后进入到main里面，要输出S(1)，将S(1)存入栈内，

进入到S(1)中，1>0,所以还要调用S(0)

S(0)进入栈中，此时栈内从下至上依次是main(),S(1),S(0)

答案选A

第二题：

解析：

先序序列个数为0时，二叉树个数是1：

先序序列个数为1时，二叉树个数是1：

先序序列个数为2时，二叉树个数是2：

先序序列个数为3时，二叉树个数是5：

先序序列个数为4时，二叉树个数是5+2+2+5=14：

第三题：

解析：

A：A错

B：B错

C：C错

答案选D

第四题：

解析：

该题给的是一棵平衡二叉树，平衡二叉树的定义是：根节点的左右两个子树的高度之差不大于1，当插入一个元素之后，可能会使平衡二叉树失衡，这时候需要判断失衡的类型，有RR，RL，LL，LR四种类型，为了使二叉树重新保存平衡，在经过左旋，右旋等操作后，插入的叶子结点可能到了根节点的位置。例如：

，C错，

题目说对其进行中序遍历之后能得到一个降序序列，中序遍历是左根右，也就是说该二叉树最大的结点一定是位于最左边的叶子结点，该结点没有左子树，D对

当二叉树的结点个数是2个时，根节点的度是1，A错。

第五题：

解析：

直接画图，就能看出答案了，答案是5个，选D

第六题：

解析：

卡鲁斯卡尔算法（选边）：选权值最小的边：权值为5

第一次选：（v1,v4）

第二次选：权值为8的点，(v1,v3),(v3,v4),(v2,v3)

普利姆算法（选点）：第一次选：v1,v4这两个点。

第二次的选择：选择与v1，v4这两个点相连的点，并且这条边权值要最小，由观察可得，权值最小的是8；也就是(v1,v3)和(v3,v4)这两条边。

（v2，v3）不是普利姆算法第二次选择的边，答案选（v2，v3）

第七题:

解析：

使用折半查找二叉树可以很直观的看待这个问题：

A：180出现在了200的右子树中，显然错误。

第八题：

解析：

abaaba

abaabc

第六个字符出现匹配失败，i=j=5，说明字符串下标是从0开始的。

因为是最后一个字符c和a匹配失败的，前面都能匹配的上，也就是说前面都是确定的字符，只有最后一个字符是匹配不上的，是未知的，ab是确认的，且模式串开头也是ab，因此下一轮匹配我们直接可以从ab开始后比较第三个元素，此时j在T[2],i在S[5],这个用文字不太好描述，王道课直接用这个题讲的课，可以看一下王道的KMP课。

答案选C

第九题：

解析：

A.直接插入排序：每次将待排序的记录中一个元素，按其关键字的大小插入到前面已经排好序的序列中，直到所有记录插入完毕。以1，2，3，4，5为例，进行升序排序，

因为本来就是有序的，所以不需要将元素进行任何交换。

而如果元素的序列是5，4，3，2，1，进行升序排序时，则每插入一个元素都要与前面的元素进行交换位置。显然A错

B：起泡排序也叫冒泡排序，是将一个序列，从左到右或者从右到左，两两进行比较，如果是逆序，则交换位置，直到序列比较完成。

还是以1，2，3，4，5为例，不需要移动元素，而5，4，3，2，1需要移动元素。B错

C：基数排序：是按照个位，十位，百位，依次排的，和次序无关。C对

D：快速排序很经典的问题，时间复杂度最差的情况是有序序列：

时间复杂度最好的情况是：

显然有序的时候不用交换次序，无序的时候要进行多次比较，然后需要交换元素次序。

第十题：

解析：

先将这个小根堆构建出来：

删除8后，将最后一个元素12放上去根的位置，接着下火海。

小根堆是根比左右两个子树要小，所以先从左右两个子树当中找出最小的一个，15和10进行比较，得出10比较小，然后10在和12比较一次，得出10最小，10和12交换位置。

接着要保证，12小于左右两个子树，因此12要和16进行一次比较，12比16小，不用交换位置，得到新的小根堆，题目完成。

一共要进行3次比较。

第十一题：

解析：

组内就两个元素在比较，使用直接插入排序就好了，不用那么复杂，答案选A。

原文地址：https://blog.csdn.net/weixin_62182040/article/details/142455962

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！