快速排序算法是基于分治策略的另一个排序算法。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数，记为x。
2．分区过程，将不小于x的数全放到它的右边，不大于x的数全放到它的左边。（这样key的位置左边的没有大于key的，右边的没有小于key的，只需对左右区间排序即可） 3．再对左右区间重复第二步，直到各区间只有一个数。
7、 设下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小。
16
普里姆（Prim）算法是一种构造性算法，用于构造最小生成树。过程如下： （1）初始化U={v}。v到其他顶点的所有边为候选边；
（2）重复以下步骤n-1次，使得其他n-1个顶点被加入到U中：
从候选边中挑选权值最小的边输出，设该边在V-U中的顶点是k，将k加入U中；
考察当前V-U中的所有顶点j，修改候选边：若(j，k)的权值小于原来和顶点k关联的候选边，则用(k，j)取代后者作为候选边。
17
克鲁斯卡尔（Kruskal）算法过程：
（1）置U的初值等于V（即包含有G中的全部顶点），TE的初值为空集（即图T中每一个顶点都构成一个连通分量）。
（2）将图G中的边按权值从小到大的顺序依次选取：
若选取的边未使生成树T形成回路，则加入TE； 否则舍弃，直到TE中包含(n-1)条边为止。
18
克鲁斯卡尔算法求解最小生成树的过程
8、假设哈希表长度m=13，采用除留余数法哈希函数建立如下关键字集合的哈希表(16，74，60，43，54，90，46，31，29，88，77)，共11个关键字。 解：n=11，m=13，设计除留余数法的哈希函数为： h(k)=k mod p
p应为小于等于m的素数，设p=13。
19
哈希冲突解决方法：开放定址法：冲突时找一个新的空闲的哈希地址。
（1）线性探查法
线性探查法的数学递推描述公式为： d0=h(k)
di=(di-1+1) mod m (1≤i≤m-1)
非同义词冲突：哈希函数值不相同的两个记录争夺同一个后继哈希地址 ? 堆积（或聚集）现象。
（2）平方探查法
平方探查法的数学描述公式为： d0=h(k)
2
di=(d0± i) mod m (1≤i≤m-1)
查找的位置依次为：d0、 d0 +1、 d0 -1 、 d0 +4、 d0 -4、?
平方探查法是一种较好的处理冲突的方法，可以避免出现堆积现象。它的缺点是不能探查到哈希表上的所有单元，但至少能探查到一半单元。 对于上题采用线性探查法解决冲突。
20
山西省2020年专升本选拔考试《数据结构》主观题常见题型及答案解析完整版
