问题 选择题

读2000年土地城市化质量的差异图表。完成下列各题。

小题1:根据图中信息,推断出关于四省市的结论正确的是

A.内蒙古的城市化进程最合理

B.上海的城市化质量最高

C.重庆的城市化速度最快

D.贵州的滞后城市化程度最高小题2:重庆城市用地人口密度大于上海,但城市用地经济密度却低于上海,与其相关的因素是

A.地形起伏较大,经济发展相对落后

B.第一产业发达

C.城市用地较为完整

D.城市化水平较高

答案

小题1:B 

小题2:A

题目分析:

小题1:内蒙古的城市用地人口密度,经济密度低,说明城市化水平低,不是最合理的,A错。上海城市用地经济密度最大,说明上海的城市化质量最高,B对。重庆的城市用地人口密度最大,说明人均占地少,城市用地经济密度低,城市化速度比上海慢,不是最快 ,C错。贵州的城市用地人口密度大于经济密度,说明虚假城市化程度最高,D错。

小题2:上海位于平原地区,重庆位于山地丘陵区,地形起伏较大,经济发展相对落后,受地形影响,城市用地经济密度小于上海,A对。城市化水平主要是看第二、三产业所占的比重,不是第一产业,B错。上海位于平原地区,城市用地较为完整 ,重庆是山城,城市结构是组团式,C错。上海的城市化水平较高重庆较低,D错。

填空题

阅读下列说明,回答问题1至问题3,将解答填入对应栏内。

[说明]

快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下:

(1)分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r],使得A[q]大于等于A[p..q-1]中的每个元素,小于A[q+1..r]中的每个元素。q的值在划分过程中计算。

(2)递归求解:通过递归的调用快速排序,对子数组A[p..q-1]和A[q+1..r]分别排序。

(3)合并:快速排序在原地排序,故不需要合并操作。

[问题1]

下面是快速排序的伪代码,请填补其中的空缺。

伪代码中的主要变量说明如下:

A:待排序数组;

p,r:数组元素下标,从p到r;

q:划分的位置;

x:枢轴元素;

i:整型变量,用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值:

j:循环控制变量,表示数组元素下标。

QUICKSORT(A,P,r)

if(p<r)

q=PARTITION(A,p,r);

QUICKSORT(A,p,q-1);

QUICKSORT(A,q+1,r);

PARTITION(A,p,r)

X=A[r];i=p-1;

for(j=p;j≤r-1;j++)

if(A[j]≤x)

i=i+1;

交换A[j]和A[j]

交换 (1) (2) //注:空(1)和空(2)答案可以互换,但两个空全部答对方可得分

return (3)

[问题2]

(1)假设要排序包含n个元素的数组,请给出在各种不同的划分情况下,快速排序的时间复杂度,用O记号。最佳情况为 (4) ,平均情况为 (5) ,最坏情况为 (6)

(2)假设要排序的n个元素都具有相同值时,快速排序的运行时间复杂度属于哪种情况 (7) 。(最佳、平均、最坏)

[问题3]

(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响,因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素,下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作,请填充其中的空缺处。其中,RANDOM(i,j)表示随机取i到j之间的一个数,包括i和j。

RANDOMIZED-PARTITION(A,p,r)

i=RANDOM(p,r);

交换 (8) (9) ;//注:空(8)和空(9)答案可以互换,但两个空全部答对方可得分

return PARTITION(A,p,r);

(2)随机化快速排序是否能够消除最坏情况的发生 (10) 。(是或否)

(1)处填()。

多项选择题