当前位置：首页 > news >正文

14年数据结构

news 来源：原创 2024/9/23 5:35:31

第一题

解析：

求时间复杂度就是看程序执行了多少次。

假设最外层执行了k次，我们看终止条件是k=n，则：

有 $2^{k}=n,k=\log 2 (n)$ ,

内层是一个j=1到j=n的循环，显然执行了n次。

总的时间复杂度是内层×外层= $\log 2(n)\times n=n\log 2(n)$

答案选C。

第二题

解析：

一步一步来分析栈内元素的变化：

输出a $\rightarrow$ /存入栈中 $\rightarrow$ b输出 $\rightarrow$ /输出 $\rightarrow$

此时栈：/

此时轮到+，+相对比/不够强，所以+不能直接进，需要先将/输出，然后+再进入。

此时栈：+

+存入栈中 $\rightarrow$

然后是‘(’，‘(’够强，直接进入。

(存入栈中 $\rightarrow$

此时栈：+ (

接着是c，c直接输出，然后是*,*够强直接存入栈中，d直接输出。

c输出 $\rightarrow$ *存入栈中 $\rightarrow$ d输出

此时栈：+ ( *

然后是-号，-号不够强，需要*先输出，-再进入。

*输出 $\rightarrow$ -存入栈中 $\rightarrow$

此时栈：+ ( -

然后是e，e直接输出，*够强存入栈中，f输出。

e输出 $\rightarrow$ *存入栈中 $\rightarrow$ f输出

此时栈：+ ( - *

然后是)，)有着和(配对的特点，需要将()一起输出出来。

( - * )输出 $\rightarrow$

此时栈：+

最后是/g，/够强直接存入栈中，g直接输出。

/存入栈 $\rightarrow$ g输出

此时栈：+ /

题目问扫描到f时，栈的情况，直接看f。

答案选B

第三题

解析：

end1指向A[0]，end2指向队尾元素的后一个位置，如果end2指向A[1]，那就说明表内还有一个元素，肯定不对。

首先，队列为空时，对头指针和队尾指针中间肯定没有位置，也就是说这两个指针都指向同一个位置，end1=end2，直接排除C和D

这种题，画个图就很好解决了：

数组的大小不难看出是M个，但是题目说队列最多能容纳M-1个元素，那就代表队列种最后一个元素的序号是M-2,end2指向最后一个元素的后一个位置，end2=M-1，如图可知，（end2+1）mod M=end1

第四题

解析：

直接写出图示二叉树的中序遍历序列：左根右

d e b x a c

很显然x的左右是ba很显然选D

第五题

解析：

对付这种题直接画一个特殊的树就好了：树转二叉树：兄弟变成右子树，孩子变成左子树。

叶子结点没有孩子，我们说树转二叉树的过程中，孩子会变成左子树，左孩子指针为空也就是没有左字数，也就代表该结点没有孩子，没有孩子的结点就是叶子结点。

答案选C

第六题

解析：

对于一个前缀编码有一个特点叫前缀不是前缀：对于一个前缀编码里面的任何一个元素都不是其它元素的前缀。

我们看D选项：

110是1110的前缀，D错

答案选D。

第七题：

解析：一个一个分析选项；拓扑序列是每次找入度为0的结点，并删除与之相连的线。

A：24显然不对，2的入度不是0，56显然不对，5的入度不是0 A错

B：和A一样的问题：24

C：和A一样的问题：56

答案选D

第八题：

解析：
存储效率和装填因子反应的是，顺序表中已经存储或者说装填的元素个数/总个数，和堆不堆积没关系。A和C错。

直接影响的应该是查找效率，在不堆积的情况下，查找效率高，通常能一次直接命中，如果发生了堆积，查找到当前位置发现不是该元素后，可能还要依次向后查找，以线性探测法为例。大大增大了查找长度。

答案选D

第九题

解析：

回顾一下B树的性质：

对于n阶B树的根节点，关键字的个数是[1,n-1]

对与n阶B树的非根结点，关键字的个数是【[n/2]向上取整-1，n-1】

回到这题：

题目要含关键字的结点个数最多，因为关键字的个数是有限的是15个，则要使每个结点的关键字最少。

我们可以算出，根节点最少是1个关键字，非根结点最少是4/2-1=1个关键字。

B树是一个完全二叉树。

因此直接画图：

正好是15个结点

选D。

第十题：

解析：

回顾一下希尔排序：设置一个间隔d，依次对i，i+d这两个元素进行排序。

也就是说经过一趟排序之后，间隔为d的两个元素，一定是有序的。

A.d=2,9-1是减序，1-13是升序，显然错。

B.d=3,B对

答案选B

第十一题：

解析：

快速排序每次都能确定一个元素的最终位置，且这个元素的左边都小于这个元素，这个元素的右边都大于这个元素。

经过两趟排序，至少能确定两个元素的最终位置。

我们直接写出排好序的最后的顺序是：2，3，4，5，6，7，9

A.23679的位置对了

B.29的位置对了

C.就一个9的位置是对的，我们说至少能确定两个元素的位置，C错

D.59的位置是对的。