一、單項選擇題（第1～40小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項最符合試題要求）

1、下列程序段的時間復雜度是（  ）。

int sum=0;

for(int i=1;i<n;i*=2)

for(int j=0;j<i;j++)

sum++;

A.O(logn)

B.O(n）

C.O(nlogn)

D.O(n2)

【答案】B

【考點】本題考查時間復雜度的運算。

【解析】分析循環(huán)體可知，循環(huán)內的執(zhí)行代碼為sum++;該代碼的執(zhí)行次數(shù)即為for循環(huán)執(zhí)行的次數(shù)。首先分析外層for循環(huán)，第一次執(zhí)行，i=1；第二次執(zhí)行，i=2；第三次執(zhí)行，i=4……設for循環(huán)執(zhí)行Tn1次，則i=2Tn1。將該結果帶入循環(huán)，2Tn1<n，Tn1<log2n。因此，Tn1=log2n-1。其次分析內層for循環(huán)，當i=1時，執(zhí)行2次；當i=2時，執(zhí)行2次；……；當i=2Tn1，循環(huán)執(zhí)行2Tn1次。設內層for循環(huán)執(zhí)行的次數(shù)為Tn2，則Tn2=20+21+22+……+2Tn1=2Tn1+1-1。Tn2=2log2n-1+1-1=2log2n-1=n-1。由此得出時間復雜度為O(n)。因此故本題選B。

 2、給定有限符號集S、in和out均為S中所有元素的任意排列，對于初始為空的棧ST，下列敘述中，正確的是（  ）。

A.若in是ST的入棧序列，則不能判斷out是否為其可能的出棧序列。

B.若out是ST的出棧序列，則不能判斷in是否為其可能的入棧序列。

C.若in是ST的入棧序列，out是對應in的出棧序列，則in與out一定不同。

D.若in是ST的入棧序列，out是對應in的出棧序列，則in與out可能互為倒序。

【答案】D

【考點】本題考查棧的應用。

【解析】本題的重點在于深刻理解棧的“后進先出”的特性。當已知棧的入棧序列時，可以得到有限個可能的出棧序列，因此A錯誤。同理，當已知棧的出棧序列時，可以得到有限個可能的入棧序列，因此B錯誤。若元素每次入棧之后即實行出棧操作，則可以實現(xiàn)入棧和出棧序列相同，因此C選項錯誤。若先將所有元素入棧，之后再將元素出棧，則可以實現(xiàn)入棧和出棧互為倒序，因此D正確。故本題選D。