数据结构与算法-等级考试试题(程序员软考 2016年春冒泡排序)

单项选择（2016年春程序员软考）

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

A、冒泡排序

B、快速排序

C、直接插入排序

D、归并排序

答案解析

A

【解析】

冒泡排序在一趟排序过程中将最大元素(或最小元素)交换至最终排序位置。快速排序是经过划分后将枢轴元素放在最终排序位置。直接插入排序是在有序序列中插入一个元素保持序列的有序性并使得有序序列不断加长，每次插入的元素不能保证是最大元素(或最小元素)。归并排序是将有序序列进行合并，第一趟归并是将长度为1的序列合并为长度为2的序列，在m>2的情况下，不能保证第一趟就将最大元素(或最小元素)放在最终位置。

讨论

数据结构与算法

设有二叉排序树如下图所示，根据关键码序列【】可构造出该二叉排序树。

某图G的邻接矩阵如下所示。以下关于该图的叙述中，错误的是【】

对于关键码序列(54，34，5，14，50，36，47，83)，用链地址法(或拉链法)解决冲突构造散列表(即将冲突的元素存储在同一个单链表中，单链表的头指针存入散列地址对应的单元)，设散列函数为H(Key)= Key MOD7(MOD表示整除取余运算)，则构造散列冲突次数最多的哈希单元的地址是【】。

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

对二叉树中的结点如下编号：树根结点编号为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。

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

设有初始为空的栈S，对于入栈序列a、b、c、d，经由一个合法的进栈和出栈操作序列后(每个元素进栈、出栈各1次)，以c作为第一个出栈的元素时，不能得到的序列为【】。

对于长度为n的线性表(即n个元素构成的序列)，若采用顺序存储结构(数组存储)，则在等概率下，删除一个元素平均需要移动的元素数为【】。

递归函数执行时，其调用和返回控制是利用【】来进行的。

与算术表达式3-(2+7)/4对应的二又树为【】。

冒泡排序

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

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

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

已知字符串s='(X+Y)*Z'，其中，单引号不是字符串的内容，经过以下运算后，t3的值是【】。t1= SubString(s,3,1)t2=Concat('XY', t1)t3=Replace(s,SubString(s,1,5),t2)注: SubString(s,k,n)表示从串s的第k个字符开始取出长度为n的子串， Concat(s,t)表示将串t连接在s之后， Replace(s,t,r)表示用r替换串s中的子串t。

设有关键码序列(10，40，30，20)，根据该序列构建的二叉排序树是【】。

根据枢轴元素(或基准元素)划分序列而进行排序的是【】。

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

设数组A[1..m,1..n]的每个元素占用1个存储单元，对于数组元素A[i,j](1≤证≤m，1≤j≤n)，在按行存储方式下，其相对于数组空间首地址的偏移量为【】

设数组A[1..m,1..n]的每个元素占用1个存储单元，对于数组元素A[i,j](1≤证≤m，1≤j≤n)，在按列存储方式下，其相对于数组空间首地址的偏移量为【】。

以下关于字符串的叙述中，正确的是【】

内部排序

如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序序列，用【】方法最快

若有n个元素已构成一个小根堆，那么如果增加一个元素Kn+1，请用文字简要说明如何在log2n的时间内将其重新调整为一个堆。

如果待排序序列中两个数据元素具有相同的值，在排序前后它们的位置发生颠倒，则称该排序算法是不稳定的，【】就是不稳定的排序算法。

若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，应该选【】。

堆排序是不是一种稳定的排序方法？为什么？

若需在O(log2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是【】。

对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为__________。

下列排序算法中，哪些时间复杂度不会超过nlogn【】。

初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为【】。

回答问题并写出推导过程：对50个整数进行快速排序需进行关键字间比较次数可能达到的最大值和最小值各为多少？