本文提供2022年408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)考研真題答案及解析，以下為具體內(nèi)容

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）

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可能互為倒序。

3、若結(jié)點(diǎn)p與q在二叉樹T的中序遍歷序列中相鄰，且p在q之前，則下列p與q的關(guān)系中，不可能的是（ ）。I.q是p的雙親II.q是p的右孩子III.q是p的右兄弟IV.q是p的雙親的雙親

A、 僅I

B、 僅III

C、 僅II、III

D、 僅II、IV

4、若三叉樹T中有244個(gè)結(jié)點(diǎn)（葉結(jié)點(diǎn)的高度為1），則T的高度至少是（ ）。

A、 8

B、 7

C、 6

D、 5

5、對(duì)任意給定的含n（n>2）個(gè)字符的有限集S，用二叉樹表示S的哈夫曼編碼集和定長(zhǎng)編碼集，分別得到二叉樹T1和T2。下列敘述中，正確的是（ ）。

A、 T1與T2的結(jié)點(diǎn)數(shù)相同

B、 T1的高度大于T2的高度

C、 出現(xiàn)頻次不同的字符在T1中處于不同的層

D、 出現(xiàn)頻次不同的字符在T2中處于相同的層

6、對(duì)于無向圖G=（V，E），下列選項(xiàng)中，正確的是（ ）。

A、 當(dāng)|V|>|E|時(shí)，G一定是連通的

B、 當(dāng)|V|<|E|時(shí)，G一定是連通的

C、 當(dāng)|V|=|E|-1時(shí)，G一定是不連通的

D、 當(dāng)|V|>|E|+1時(shí)，G一定是不連通的

7、下圖是一個(gè)有10個(gè)活動(dòng)的AOE網(wǎng)，時(shí)間余量最大的活動(dòng)是（ ）。

A、 c

B、 g

C、 h

D、 j

8、在下圖所示的5階B樹T中，刪除關(guān)鍵字260之后需要進(jìn)行必要的調(diào)整，得到新的B樹T1。下列選項(xiàng)中，不可能是T1根結(jié)點(diǎn)中關(guān)鍵字序列的是（ ）。

A、 60，90，280

B、 60，90，350

C、 60，85，110，350

D、 60，90，110，350