2021年重慶郵電大學考研專業(yè)課試題802數(shù)據(jù)結構A卷

重慶郵電大學2021年攻讀碩士學位研究生入學考試試題

機密啟用前

重慶郵電大學

2021年攻讀碩士學位研究生入學考試試題

科目名稱：數(shù)據(jù)結構（A）卷

科目代碼：802

考生注意事項

1、答題前，考生必須在答題紙指定位置上填寫考生姓名、報

考單位和考生編號。

2、所有答案必須寫在答題紙上，寫在其他地方無效。

3、填（書）寫必須使用黑色字跡鋼筆、圓珠筆或簽字筆。

4、考試結束，將答題紙和試題一并裝入試卷袋中交回。

5、本試題滿分150分，考試時間3小時。

注：所有答案必須寫在答題紙上，試卷上作答無效！第1頁/共9頁

重慶郵電大學2021年攻讀碩士學位研究生入學考試試題

一、選擇題（本大題共15小題，每小題2分，共30分）

1設N是描述問題規(guī)模的非負整數(shù)，下列程序段的時間復雜度是

（）。

staticintfun(intN){

if(N==1)return0;

return1+fun(N/2);

}

A．O(logN)B.O(N)C.(NlogN)D.O(N2)

2一些隨機產(chǎn)生的數(shù)采用線性鏈表存儲，在下面這些排序方法中，

（）的時間復雜度是最小的。

A．插入排序B.快速排序C.堆排序D.歸并排序

3一個棧的輸入序列為a，b，c，d，e，則下列序列中不可能是棧

的輸出序列的是（）。

A．bcdaeB．edacbC．bcadeD．a(chǎn)edcb

4實現(xiàn)一個隊列需要（）個棧。

A．1B.2C.3D.4

5下面（）是一顆滿二叉樹的結點個數(shù)。

A.8B.13C.14D.15

6若X是二叉中序線索樹中一個有左孩子的結點，且X不為根，

則X的前驅為（）。

A.X的雙親B.X的右子樹中最左的結

點

C.X的左子樹中最右的結點D.X的左子樹中最右的結

點

7下列序列中，哪一個是堆（）？

A.75,65,30,15,25,45,20,10

B.75,65,45,10,30,25,20,15

C.75,45,65,30,15,25,20,15

D.75,45,65,10,25,30,20,15

注：所有答案必須寫在答題紙上，試卷上作答無效！第2頁/共9頁

重慶郵電大學2021年攻讀碩士學位研究生入學考試試題

8一棵Huffman樹共有203個結點，對其Huffman編碼，共能得

到（）個不同的碼字。

A.100B.102C.200D.203

9下面說法錯誤的是（）。

A.一個有n個頂點和n條邊的無向圖一定是有環(huán)的。

B.建立十字鏈表的時間復雜度和建立鄰接表是相同的。

C.鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向

圖的存儲都適用。

D.在某些圖的應用問題中，如果需要找到表示同一條邊的兩個

結點，那么采用鄰接多重表比鄰接表作為儲存結構更為適

宜。

10圖的廣度優(yōu)先遍歷算法中使用隊列作為其輔助數(shù)據(jù)結構，那

么在算法執(zhí)行過程中每個頂點進隊次數(shù)最多為（）。

A.1B.2C.3D.4

11設一個有向圖G=(V,E)，其中

V={v1,v2,v3,v4,v5,v6}

E={<v1,v2>,<v2,v3>,<v3,v6>,<v4,v2>,<v4,v5>,<v5,v6>}

不屬于該圖的拓撲排序有序序列是（）。

A.v1v2v3v4v5v6B.v1v4v2v3v5v6

C.v4v5v1v2v3v6D.v4v1v2v3v5v6

12判斷一個有向圖是否存在回路，除可利用拓撲排序方法外，還

可以用（）。

A.求關鍵路徑的方法B.求最短路徑的方法

C.廣度優(yōu)先遍歷的方法D.深度優(yōu)先遍歷的方法

13設有一個二叉排序樹（二叉查找樹），其結點上存儲有數(shù)字1

到100?，F(xiàn)在需要查找數(shù)字55，下面（）序列不可能是查找過

程中訪問過的結點序列。

A.{10,75,64,43,60,57,55}B.{90,12,68,34,62,45,55}

C.{9,85,47,68,43,57,55}D.{79,14,72,56,16,53,55}

注：所有答案必須寫在答題紙上，試卷上作答無效！第3頁/共9頁

重慶郵電大學2021年攻讀碩士學位研究生入學考試試題

14在順序表{2、5、7、10、14、15、18、23、35、41、52}中，

用二分法查找關鍵碼12需做（）次關鍵碼比較。

A.2B.3C.5D.4

15一顆3階B-樹中有2047個關鍵字，包括葉結點層，該樹的最

大深度為（）。

A.11B.12C.13D.14

二、填空題（本大題共10小題，每小題3分，共30分）

16一顆深度為k的平衡二叉樹，其每個非終端結點的平衡因子均

為0，則該樹共有（）個結點。

17LetQdenoteaqueuecontainingsixteennumbersandSbeanempty

stack.Head(Q)returnstheelementattheheadofthequeue

QwithoutremovingitfromQ.SimilarlyTop(S)returnstheelementat

thetopofSwithoutremovingitfromS.Considerthealgorithmgiven

below.

Themaximumpossiblenumberofiterationsofthewhileloopinthe

algorithmis（）。

18對于模式串“aabaac”，給出其next數(shù)組：（）。

19現(xiàn)有按中序遍歷二叉樹的結果為abc，有（）種不同形態(tài)的

二叉樹可以得到這一遍歷結果。

20設一棵二叉樹有20個葉子結點，則在該樹中有2個孩子的結

點個數(shù)為（）。

注：所有答案必須寫在答題紙上，試卷上作答無效！第4頁/共9頁

重慶郵電大學2021年攻讀碩士學位研究生入學考試試題

21設G是一個非連通無向圖，有10條邊，則該圖的頂點數(shù)至少

有（）個。

22順序查找3個元素的順序表，若查找第1、第2和第3個元素

的查找概率分布是1/2、1/3和1/6，則查找任一元素的平均查找

長度為（）。

23散列函數(shù)有一個共同的性質，即函數(shù)值應當以（）取其值

域的每個值。（請在最大概率、最小概率、平均概率、同等概率這

些術語中選擇正確的進行填空）

24假設某算法在輸入規(guī)模為n時的計算時間為T(n)=n2。在某臺

計算機上實現(xiàn)并完成該算法的時間為t秒。現(xiàn)有另一臺計算機，

其運行速度為第一臺計算機的64倍，那么在這臺計算機上用同

一算法在t秒內能解輸入規(guī)模（）的問題。

25表達式a×b－c－d$e$f－g－h(huán)×i中，運算符的優(yōu)先級由高到

低依次為－，×，$，均右結合，則相應的后綴式是（）。

三、綜合應用題（本大題共7小題，共60分）

26（10分）假設稱正讀和反讀都相同的字符序列為“回文”，例

如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。下面

代碼判別讀入的一個以‘@’為結束符的字符序列是否是“回文”。請

給出缺失的5行代碼。

StatusSymmetryString(char*p)

{

Queueq;

if(!InitQueue(q))return0;

Stacks;

InitStack(s);

ElemTypee1,e2;

while(（1）){

Push(s,*p);

EnQueue(q,*p);

（2）

}

while(!StackEmpty(s)){

（3）

（4）

注：所有答案必須寫在答題紙上，試卷上作答無效！第5頁/共9頁

重慶郵電大學2021年攻讀碩士學位研究生入學考試試題

if(（5）)returnFALSE;

}

returnOK;

}

27（5分）閱讀下面代碼：

intcount=0;

intN=a.length;

sort(a);

for(inti=0;i<N;i++){

for(intj=i+1;j<N;j++){

if(BinarySearch(a,a[i]+a[j]))count++;

}

}

假設當N=3500，上述代碼運行1秒。那么，當N=35000時，

該代碼的運行時間最接近下面那個時間？請給出簡單的分析過

程。

A.10secondsB.20secondsC.1minuteD.2minutes

E.1hourF.2hours

28（8分）將關鍵字序列{23，14，9，6，30，12，18}散列存儲到

散列表中，散列表的存儲空間是一個下標從0開始的一維數(shù)組，

散列函數(shù)為H(Key)=KeyMOD7，處理沖突采用線性探測法，要

求裝填（載）因子為0.7。

請畫出所構造的散列表。

29（12分）已知一棵二叉樹的先序序列：ABDGJEHCFIKL，中序

序列：DJGBEHACKILF。

（1）畫出此二叉樹的形態(tài)。

（2）畫出此二叉樹的后序線索樹。

（3）采用孩子兄弟表示法來存儲該二叉樹，請畫出此二叉樹的

存儲結構。

（4）畫出與此二叉樹對應的森林。

30（8分）考慮下列36個字符（symbol）的序列:FCFCECAC

注：所有答案必須寫在答題紙上，試卷上作答無效！第6頁/共9頁

重慶郵電大學2021年攻讀碩士學位研究生入學考試試題

BDEDFEABFBAFFCDCBEDFFFCCDEEF

下面表30-1給出了為上述字符序列編碼的四種變長編碼方式，即

CODE1、CODE2、CODE3、CODE4；表30-2給出了編碼特點，

即A、B、C、D，請給出這4種編碼方式所具有的編碼特點。（填

寫該編碼方式具有的編碼特點編號即可，不用給出具體分析過程）

表30-1：表30-2：

symbolfrequencyCODE1CODE2CODE3CODE4A.前綴編碼

A30110111110100B.Huffman編

B40100101111101碼(能夠由

C800000001Huffman算法

D5110101110110生成)

E600110010111

C.最優(yōu)前綴編

F1010110100

碼

D.上述都不滿

CODE1：_____CODE2：_____CODE3：_____CODE足4：_____

31（7分）圖G的鄰接矩陣如右邊所示：

（1）求從頂點1出發(fā)的廣度優(yōu)先搜索序列；

（2）根據(jù)prim算法，求圖G從頂點1出發(fā)

的最小生成樹，要求表示出其每一步

生成過程。

32（10分）表32-1中，第0行是待排序序列的原始輸入(122

1630281016*20618);其他各行是5種排序算法得

到的某個中間步驟的內容。表32-2列出了6種排序算法。請按行

序直接給出每行對應排序算法的編號。每個編號只使用一次。

表32-排序算法序列

1第：0行原始輸入1221630281016*206

18

算法2121630281016*206

1：18

算法621012283016*2016

2：18

注：所有答案必須寫在答題紙上，試卷上作答無效！第7頁/共9頁

重慶郵電大學2021年攻讀碩士學位研究生入學考試試題

算法2121630102816*206

3：18

算法102166181216*2030

4：28

算法21216281016*20618

5：30

表32-2：

排序算法排序算法名稱排序算法排序算法名稱

編號編號

A希爾排序(增量D二路歸并排序

為5，2，1)

B快速排序E直接插入排序

C直接選擇排序F冒泡排序

四、算法分析與設計題(本大題共2小題,每小題15分,共30分)

33如果一個序列是一個先單調遞增后單調遞減的序列，那