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

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

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

您可能感兴趣的试卷

你可能感兴趣的试题

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

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

点击查看完整答案

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

参考答案：

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