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

1、下列程序段的時(shí)間復(fù)雜度是（  ）。

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

【考點(diǎn)】本題考查時(shí)間復(fù)雜度的運(yùn)算。

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

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

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

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

C.若in是ST的入棧序列，out是對(duì)應(yīng)in的出棧序列，則in與out一定不同。

D.若in是ST的入棧序列，out是對(duì)應(yīng)in的出棧序列，則in與out可能互為倒序。

【答案】D

【考點(diǎn)】本題考查棧的應(yīng)用。

【解析】本題的重點(diǎn)在于深刻理解棧的“后進(jìn)先出”的特性。當(dāng)已知棧的入棧序列時(shí)，可以得到有限個(gè)可能的出棧序列，因此A錯(cuò)誤。同理，當(dāng)已知棧的出棧序列時(shí)，可以得到有限個(gè)可能的入棧序列，因此B錯(cuò)誤。若元素每次入棧之后即實(shí)行出棧操作，則可以實(shí)現(xiàn)入棧和出棧序列相同，因此C選項(xiàng)錯(cuò)誤。若先將所有元素入棧，之后再將元素出棧，則可以實(shí)現(xiàn)入棧和出?；榈剐?，因此D正確。故本題選D。