单项选择(2017年春程序员软考)

采用【 】算法对序列{18,12,10,11,23,2,7}进行一趟递增排序后,其元素的排列变为{12,10,11,18,2,7,23}。

A、选择排序

B、快速排序

C、归并排序

D、冒泡排序

答案解析

D一趟选择排序会选出序列中的最小元素(或最大元素),并通过最多 1 次交换将其换至序列最前端(或最末端)。对于序列{18,12,10,11,23,2,7},如果是选出最小元素并将其换至最前端,则得到的序列为{2,12,10,11,23,18,7}:若是选出最大元素并将其换至最末端,则得到的序列为{18,12,10.11,7,2,23}。快速排序是通过划分将小于枢轴元素者和不大于枢轴元素者以枢轴元素为界划分开,若以第一个元素作为枢轴,对{1...

查看完整答案

讨论

表达式可采用后缀形式表示。例如,“a+b”的后缀式为“ab+”。那么,表达式“a*(b-c)+d”的后缀表示为【 】

设某无向图的顶点个数为n,则该图最多有______条边;若将该图用邻接矩阵存储,则矩阵的行数和列数分别为______。

搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询串的长度不超过255 字节。假设目前有一千万个查询记录(重复度比较高,其实互异的查询串不超过三百万个;显然,一个查询串的重复度越高,说明查询它的用户越多,也就是越热门)。现要统计最热门的 10 个查询串,且要求使用的内存不能超过 1GB。以下各方法中,可行且效率最高的方法是【 】。

对于一般的树结构,可以采用孩子-兄弟表示法,即每个结点设置两个指针域,一个指针(左指针)指示当前结点的第一个孩子结点,另一个指针(右指针)指示当前结点的下一个兄弟结点。某树的孩子-兄弟表示如下图所示。以下关于结点 D 与 E 的关系的叙述中,正确的是【 】。

若要求对大小为n的数组进行排序的时间复杂度为 O(nlog2n),且是稳定的(即如果待排序的序列中两个数据元素具有相同的值,在排序前后它们的相对位置不变),则可选择的排序方法是【 】

设元素a、b、c、d依次进入一个初始为空的栈,则不可能通过合法的栈操作序列得到【 】。

若某线性表长度为n且采用顺序存储方式,则运算速度最快的操作是【 】。

线性表采用单循环链表存储的主要特点是【 】

在单 CPU 计算机系统中,完成相同功能的递归程序比非递归程序【 】

对于n个元素的关键码序列{k1,k2,…,kn},当且仅当满足下列关系时称其为堆。或以下关键码序列中,【 】不是堆。

对n个记录进行非递减排序,在第一趟排序之后,一定能把关键码序列中的最大或最小元素放在其最终排序位置上的排序算法是【 】。

序列【 】可能是第一趟冒泡排序后的结果。

在待排序的一组关键码序列k1,k2,…,kn中,若ki和kj相同,且在排序前ki领先于kj,那么排序后,如果ki和kj的相对次序保持不变,ki仍领先于kj,则称此类排序为稳定的。若在排序后的序列中有可能出现kj领先于ki的情形,则称此类排序为不稳定的。【 】是稳定的排序方法。

队列采用如下图所示的循环单链表表示,左图表示队列为空,右图为e1、e2、e3依次入队列后的状态,其中,rear指针指向队尾元素所在结点,size为队列长度。以下叙述中,正确的是【 】。

对二叉树中的结点如下编号:树根结点编号为1,根的左孩子结点编号为2、右孩子结点编号为3,以此类推,对于编号为i的结点,其左孩子编号为2i、右孩子编号为2i+1。例如,下图所示二又树中有6个结点,结点a、b、c、d、e、f的编号分别为1、2、3、5、7、11。那么,当结点数为n(n>0)的【 】时,其最后一个结点编号为2n-1。

某二又树的先序遍历序列为 ABCDFGE,中序遍历序列为 BAFDGCE。以下关于该二又树的叙述中,正确的是【 】。

对n个记录进行非递减排序,在第一趟排序之后,一定能把关键码序列中的最大或最小元素放在其最终排序位置上的排序算法是【 】。

线性表采用单链表存储时的特点是【 】。

完全二叉树的特点是叶子结点分布在最后两层,且除最后一层之外,其他层的结点数都达到最大值,那么25个结点的完全二叉树的高度(即层数)为【 】。

在数据结构中,【 】是与存储结构无关的术语。