1. 用某种排序方法对线性表（25, 84，21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下：
15, 20, 21, 25，27, 35, 47, 68, 84， 问采用的是什么排序方法？
答：用的是快速排序方法。注意每一趟要振荡完全部元素才算一个中间结果。
2. 对于整数序列100，99，98，…3，2，1，如果将它完全倒过来，分别用冒泡排序和快速排序法，它们的比较次数和交换次数各是多少？
答：冒泡排序的比较和交换次数将最大，都是1+2+…+n-1=n(n-1)/2＝50×99=4545次。
快速排序则看按什么数据来分子表。
如果按100来分，则很惨，也会是n(n-1)/2！
若按中间数据50或51来分表，则：
第1轮能确定1个元素，即在1个子表中比较和交换了n－1个元素；n－（21-1）
第2轮能再确定2个元素，即在2个子表中比较和交换了n－3个元素；n－（22-1）
第3轮能再确定4个元素，即在4个子表中比较和交换了n－7个元素；n－（23-1）
第4轮能再确定8个元素，即在8个子表中比较和交换了n－15个元素；n－（24-1）
第6轮能再确定32个元素，即在32个子表中比较和交换了n－65个元素；n－（26-1）
第7轮则能全部确定，（因为27=128）， 在100个子表中比较和交换了n－（100－1）个元素；
比较和交换总次数为：7n－(21－1＋22－1＋23－1……＋26－1＋100－1) ＝7n+7－(1＋2＋4＋……64+100)=7n－(8+16+32+164)=700-220=480次。
若从中间选择初始元素，则asl=（n+1）log2n－(21＋22＋23+……2m)= nlog2n+log2n－(21＋22＋23+……n)≈o（nlog2n）
3. 以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？
直接插入排序 ② 希尔排序 ③冒泡排序 ④快速排序。
直接选择排序 ⑥ 堆排序 ⑦ 归并排序 ⑧ 基数排序 （8分）
解：先回答第2问皆易于在链表上实现。
1 直接插入排序的中间过程如下希尔排序的中间过程如下：
3 冒泡排序的中间过程如下快速排序的中间过程如下：
5 直接选择排序的中间过程如下堆排序（大根堆）的中间过程如下：
7 归并排序排序的中间过程如下。
8 基数排序的中间过程如下：
4. 序列的“中值记录”指的是：如果将此序列排序后，它是第[n/2]个记录。试写一个求中值记录的算法。
typedef struct
mid=0;
min_dif=abs(b[0].gt-b[0].lt);
for(i=0;i if(abs(b[i].gt-b[i].lt) return mid;
//get_mid
作业7答案
1.下面是两个程序流程图，试分别用n s图和pad表示之，并计算它们的mccabe复杂性度量。它们的mccabe复杂性度量都为3.2.从下列关于模块化程序设计的叙述中选出5条正确的叙述。程序设计比较方便，但比较难以维护。便于由多个人分工编制大型程序。软件的功能便于扩充。程序易于理解，也便于排错。在主...
1 7 1 7作业答案
第七节无穷小的比较。一 填空题。1.当时，是的低阶无穷小 是的等价 或同阶 无穷小 是的低阶无穷小 是的同阶无穷小 是的等价 或同阶 无穷小 是的高阶无穷小。提示 2.已知时，与为等价无穷小，则常数。提示 二 计算题。1 解 2.解 3.解 4.解。第八节函数的连续性与间断点。一 填空题。1.设在处...
作业7 群落 答案
班级姓名。一 选择题 共10题，每空1分 1 浅海中牡蛎与鱼类 节肢动物 棘皮动物等生物生活在一起。这些生物构成了 a a 群落b 种群c 生态系统d 生态因子。2 大多数生物群落在空间上有垂直分层现象，称为群落的垂直结构。引起森林群落中植物和动物垂直分层现象的主要因素分别是d a.温度 食物 b....