搜题请搜索小程序“爱下问搜题”
问题 选择题

A new bridge         over the river now ,You can see many railway workers and engineers working every day．

A．is built

B．is being built

C．has been built

D．should be built

答案

答案：B

题目分析：句意：在河上正在建一座新桥,你可以看到很多铁路工作人员和工程师在工作.主语是动作的承受者,有now用现在进行时,结合句意，故选B

填空题

阅读下列说明，回答问题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) 。(是或否)

（6）处填（）。
查看答案
单项选择题

电气设备最高允许表面温度（）℃引燃温度组别T13有过负荷的设备。

A.110

B.120

C.145

D.160
查看答案