2014年408計算機學(xué)科專業(yè)基礎(chǔ)考研真題答案及解析

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

1、下列程序段的時間復(fù)雜度是（  ）。count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;

A、 O(log₂n)

B、 O(n)

C、 O(nlog₂n)

D、 O(n²)

2、假設(shè)棧初始為空，將中綴表達式a/b+(c*d-e*f)/g轉(zhuǎn)換為等價的后綴表達式的過程中，當掃描到f時，棧中的元素依次是（  ）。

A、 +(*-

B、 +(-*

C、 /+(*-*

D、 /+-*

3、循環(huán)隊列放在一維數(shù)組A[0…M-1]中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設(shè)隊列兩端均可進行入隊和出隊操作，隊列中最多能容納M-1個元素。初始時為空。下列判斷隊空和隊滿的條件中，正確的是（  ）。

A、 隊空：end1==end2；隊滿：end1==(end2+1)modM

B、 隊空：end1==end2；隊滿：end2==(end1+1)mod(M-1)

C、 隊空：end2==(end1+1)modM；隊滿：end1==(end2+1)modM

D、 隊空：end1==(end2+1)modM；隊滿：end2==(end1+1)mod(M-1)

4、若對如下的二叉樹進行中序線索化，則結(jié)點x的左、右線索指向的結(jié)點分別是（  ）。

A、 e、c

B、 e、a

C、 d、c

D、 b、a

5、將森林F轉(zhuǎn)換為對應(yīng)的二叉樹T，F(xiàn)中葉結(jié)點的個數(shù)等于（  ）。

A、 T中葉結(jié)點的個數(shù)

B、 T中度為1的結(jié)點個數(shù)

C、 T中左孩子指針為空的結(jié)點個數(shù)

D、 T中右孩子指針為空的結(jié)點個數(shù)

6、5個字符有如下4種編碼方案，不是前綴編碼的是（  ）。

A、 01，0000，0001，001，1

B、 011，000，001，010，1

C、 000，001，010，011，100

D、 0，100，110，1110，1100

7、對如下所示的有向圖進行拓撲排序，得到的拓撲序列可能是（  ）。

A、 3，1，2，4，5，6

B、 3，1，2，4，6，5

C、 3，1，4，2，5，6

D、 3，1，4，2，6，5

8、用哈希（散列）方法處理沖突（碰撞）時可能出現(xiàn)堆積（聚集）現(xiàn)象。下列選項中，會受堆積現(xiàn)象直接影響的是（  ）。

A、 存儲效率

B、 散列函數(shù)

C、 裝填(裝載)因子

D、 平均查找長度