一、 单选题（每小题1分，共10分）1、下列函数中，渐近紧致界为的是（ C ）。A； B； C； D 。2、下列函数中，渐近非紧上界为的是（ D ）。A； B； C； D 。3、以下描述中，不正确的有（ A ）。A在渐进复杂性概念下，等式在时成立；B在渐进复杂性概念下，有成立； C在渐进复杂性概念下，与无法渐近比较； D对于任意函数， (为空集)。4、在快速排序中，以下描述不正确的是（ D ）。A在快速排序，最好时间复杂性和平均时间复杂性均为；B若精心挑选一个划分元，每次经过Partition算法后，分成两个子问题，从而使得 其 最坏时间复杂性为； C若随机挑选一个划分元，每次经过RandomizedPartition算法后，分成两个期望均长的子问题，从而使得其期望时间复杂性为； D不管是精心挑选还是随机挑选划分元，快速排序的最坏时间复杂性均为。 6、Dijkstra算法是解单源最短路径问题的一个贪心算法，工作过程与Prim算法是一样的，不同点在于它比较的是路径的长度而
