问答题X 纠错

一个线性表中的元素为正整数或负整数。设计算法将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少比较次数。

参考答案：

本题的基本思想是：先设置好上、下界和轴值，然后分别从线性表两端查找正数和负数，找到后进行交换，直到上下界相遇。算法如下：

进入题库练习
查答案就用赞题库小程序 还有拍照搜题 语音搜题 快来试试吧
无需下载 立即使用

你可能喜欢

问答题

写出快速排序的非递归调用算法。

参考答案：先调用划分函数Quickpass（划分函数同教材），以确定中间位置，然后再借助栈分别对中间元素的左、右两边的区域进行快速...
点击查看答案进入题库练习

问答题

对给定的序号j（1＜j＜n），要求在无序记录A[1]~A[n]中找到按关键码从小到大排在第j位上的记录，试利用快速排序的划分思想设计算法实现上述查找。

参考答案：

本算法不要求将整个记录进行排序，而只进行查找第j个记录。

 

点击查看答案进入题库练习

问答题

设待排序的记录序列用单链表作存储结构，试写出直接插入排序算法。

参考答案：本算法采用的存储结构是带头结点的单链表。首先找到元素的插入位置，然后把元素从链表中原位置删除，再插入到相应的位置处。具体...
点击查看答案进入题库练习

问答题

已知下列各种初始状态（长度为n）的元素，试问当利用直接插入排序进行排序时，至少需要进行多少次比较（要求排序后的记录由小到大顺序排列）？
⑴关键码从小到大有序（key1< key2< …< keyn）。
⑵关键码从大到小有序（key1> key2 >…> keyn）。
⑶奇数关键码顺序有序，偶数关键码顺序有序（key1< key3< …，key2key4…）。
⑷前半部分元素按关键码顺序有序，后半部分元素按关键码顺序有序，即：（key1< key2< …< keym，keym+1<
keym+2 <…）

参考答案：依题意，最好情况下的比较次数即为最少比较次数。⑴插入第i（2≤i≤n）个元素的比较次数为1，因此总的比较次数...
点击查看答案进入题库练习

问答题

判别下列序列是否为堆，如不是，按照堆排序思想把它调整为堆，用图表示建堆的过程。
⑴（1，5，7，25，21，8，8，42）
⑵（3，9，5，8，4，17，21，6）

参考答案：

序列⑴是堆，序列⑵不是堆，调整为堆（假设为大根堆）的过程如下图所示。

点击查看答案进入题库练习

问答题

对n=7，给出快速排序一个最好情况和最坏情况的初始排列的实例。

参考答案：最好情况：4，7，5，6，3，1，2
最坏情况：7，6，5，4，3，2，1
点击查看答案进入题库练习

问答题

已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，写出插入排序、起泡排序、快速排序、简单选择排序、堆排序以及二路归并排序每趟的结果。

参考答案：

用上述排序方法的每趟结果如下：

点击查看答案进入题库练习

判断题

设有键值序列（k1，k2，…，kn），当i>n/2时，任何一个子序列（ki，ki+1，…，kn）一定是堆。

参考答案：对
点击查看答案进入题库练习

判断题

堆排序所需的时间与待排序的记录个数无关。

参考答案：错
点击查看答案&解析进入题库练习

判断题

对n个记录的集合进行快速排序，所需要的附加空间是O（n）。

参考答案：错
点击查看答案进入题库练习
赞题库

赞题库-搜题找答案

（已有500万+用户使用）


  • 历年真题

  • 章节练习

  • 每日一练

  • 高频考题

  • 错题收藏

  • 在线模考

  • 提分密卷

  • 模拟试题

无需下载 立即使用
手机版 电脑版

版权所有©考试资料网(ppkao.com)All Rights Reserved