计算机等级考试 java 二级重点内容 原创

设栈的存储空间为S(1:50),初始状态为top=51.经过一系列正常的入栈和退栈操作之后，top=20,则栈中的元素为31.

解析：top=0表示栈空,top=50表示栈满。入栈操作首先将top加1，然后将新元素插入到top指针指向的位置；退栈操作首先将top指针指向的元素赋给一个指定的变量，然后将top减1.栈顶指针top动态反映了栈中元素的变化情况。栈中的元素个数为50-20+1=31.所以答案是31.

循环队列中，font=出队，rear是入队，所以一般剩余的元素个数为m-font+rear(只出现在font=rear=m)

循环队列中初始值font=rear=50，经过一系列入队和退队操作后，font=rear=25，则该循环队列中元素个数为0或者50个。

循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。如果循环队列的初始状态是空的。即rear= front =m，队列元素个数为rear=front。

在带链队列中，经过正常操作后，如果front=rear，则队列中的元素个数为0或1.

在带链中，经过正常操作之后，如果top=bottom，则栈中元素个数为0或1.

栈·······初始状态top为0，经过一系列的入栈和退栈之后， top=30，栈中元素为30.

栈的顺序存储空间为s(1:m)，初始状态为top=0，栈中元素个数为top。

栈存储空间是1：50，初始状态top=0，经过入栈退栈后，top=51，栈中元素个数不可能。

算法 要考虑 时间复杂度 和空间复杂度；时间复杂度是指算法所需要的计算工作量，空间复杂度是指执行这个算法所需要的内存空间。

算法的时间复杂度与运行算法时特定的输入法有关。

算法的时间复杂度与问题规模无关 ❌

对于各种特定的输入，算法的时间复杂度是固定不变的 ❌

算法是指阶梯方案的准确而完整的描述，有如下特征：可行性、确定性、有穷性（算法的有穷性是指算法必须在有限的时间内做完，即算法必须能在执行有限个步骤之后终止）。

平均情况与最坏情况下的时间复杂度相同的是在顺序存储的线性表中寻找最大（或小）项**（n-1）**。

在最坏情况下， 冒泡排序 的比较次数为n(n-1)/2

顺序表 的长度为n,最坏情况下比较次数等于n(n-1)/2的是 快速排序

顺序查找的比较次数为n,有序表的插入比较次数也为n。

查找算法中，在最坏的情况下，比较次数最少的是有序表的 二分查找 。

最坏情况下事件复杂度最高的是 希尔排序 （n1.5）,堆排序（log2n）最小，有序链表查找（n），循环链表中寻找 最大项 （n-1）。