第十章 分数排序定位法
一、分数排序定位法的由来及其定义
由于每个高考分数都对应着相对的排序位置，而相应的排序位置也大体对应着一定的高考分数，只不过不是一一对应的关系而是大体相对应的关系罢了。既然可以利用高考分数来填报高考志愿，那为什么不能利用排序位置的定位作用来填报高考志愿呢？来预测高校的投档(录取)分呢？回答当然是肯定的。这就是分数排序定位法的由来。
二、分数排序定位法的重要性
许多考生和家长的两眼往往只习惯盯在考试及高考的分数上，学校的录取分数线上，其实，这是一个很大的误区。这是因为：
4．从考生排序的位置，可分析被录取的可能性。由于多年的招生，每所院校的排序位置也是大体相对稳定的，当然不排除有波动。比如说北大、清华总是当之无愧的龙头老大，它们的录取分数线总是最高的，排序位置也总是最靠前的。这既可以从每所院校每年的招生录取分中可以看到。也可以从每所院校每年的招生排序位置中可以看到。因此，根据当年的招生情况结合历史的资料，就大体可以知道，你的排序位置是多少，被录取的可能性有多大。如2005年北大、清华在鄂计划招生理工类分别为49名、95名，那么从理论上来说，这144人都有可能被录取；可是从理论上来说，这144人中按现行的录取办法，有可能排序位置是第50名或其以后的若干名考生就可能会被淘汰出局，原因很简单，那就是前49名考生甚至更多的考生第一志愿全都填报了北大。当然在实际中第50名考生会被淘汰出局的可能性微乎其微，同样第144名考生被录取的可能性也不是100%。虽然对于所有院校均按招生计划与排序位置一一对应地实现招生几乎没有可能，但对于北大、清华这两所学校来说，是完全可以做到的，而且办法也比较简单，这是后话，下面再说。
5．考生的排序位置比其高考分数更重要的现实分析。那么到底排序在第144位及其稍后的考生有无必要第一志愿填报北大、清华呢？要回答这个问题就要知道首先应关注的是排序位置，不是高考分数因为排序在第144位及其以前的考生不论考分是多少，被录取的概率非常之大。因此可以说，此时的分数是次要的。排序144位对应的分数大约是647分(647分对应的排序是147位)。
第10章 排序
一、填空题
1. 大多数排序算法都有两个基本的操作： 和 。
2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 次。
3. 在插入和选择排序中，若初始数据基本正序，则应选用 排序算法；若初始数据基本反序，则应选用 排序算法。
4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 ；若初始记录基本无序，则最好选用 。
5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 。若对其进行快速排序，在最坏的情况下所需要的时间是 。
6. 对于n个记录的集合进行归并排序，所需要的平均时间是 ，所需要的附加空间是 。
7． 对于n个记录的表进行2路归并排序，整个归并排序需进行 趟（遍）。
8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是 ；初始步长为4的希尔（shell）排序一趟的结果是 ；归并排序一趟扫描的结果是 ；快速排序一趟扫描的结果是 ；堆排序初始建堆的结果是 。
9. 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表进行排序，则最省时间的是 算法，最费时间的是 算法。
10、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为 。
二、单项选择题
1、下列四个序列中，（ ）是堆。
1 9-12章 数据结构作业 答案
第九章 查找
选择题
1、 对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )
A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2
2. 下面关于二分查找的叙述正确的是 ( D )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序且表中数据必须是整型，实型或字符型
C. 表必须有序，而且只能从小到大排列
D. 表必须有序，且表只能以顺序方式存储
3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低
(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C)
（1） A．17 B. 13 C. 16 D. 任意
（2） A．0至17 B. 1至17 C. 0至16 D. 1至16
判断题
1．Hash表的平均查找长度与处理冲突的方法无关。 (错)
2. 若散列表的负载因子α<1，则可避免碰撞的产生。（错）
3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（错）
填空题
1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 4 .
第10章 内部排序
10.1以关键码序列
(503, 087, 512, 061, 908, 170, 897, 275, 653, 426)为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：
(1) 直接插入排序 (2) 希尔排序(d[1]=5, d[2]=3, d[3]=1)
(3) 快速排序(第一个记录为基准记录) (4) 堆排序
(5) 归并排序 (6) 基数排序
解答：
（1）直接插入排序：
第一趟：
087,503, 512, 061, 908, 170, 897, 275, 653, 426
第二趟：
087,503, 512, 061, 908, 170, 897, 275, 653, 426
第三趟：
061,087,503, 512, 908, 170, 897, 275, 653, 426
第四趟：
061,087,503, 512, 908, 170, 897, 275, 653, 426
第五趟：
061,087, 170, 503, 512, 908, 897, 275, 653, 426
第六趟：
061,087, 170, 275, 503, 512, 897, 908, 653, 426
第八趟：
061,087, 170, 275, 503, 512, 653, 897, 908, 426
第九趟：
061,087, 170, 275, 426, 503, 512, 653, 897, 908
（2）希尔排序
(d[1]=5, d[2]=3, d[3]=1)
第一趟：
170,087, 275, 061, 426, 503, 897, 512, 653, 908
第二趟：
