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

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

機(jī)密啟用前

重慶郵電大學(xué)

2021年攻讀碩士學(xué)位研究生入學(xué)考試試題

科目名稱：數(shù)據(jù)結(jié)構(gòu)（A）卷

科目代碼：802

考生注意事項(xiàng)

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

考單位和考生編號(hào)。

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

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

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

5、本試題滿分150分，考試時(shí)間3小時(shí)。

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

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

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

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

（）。

staticintfun(intN){

if(N==1)return0;

return1+fun(N/2);

}

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

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

（）的時(shí)間復(fù)雜度是最小的。

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

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

的輸出序列的是（）。

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

4實(shí)現(xiàn)一個(gè)隊(duì)列需要（）個(gè)棧。

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

5下面（）是一顆滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)。

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

6若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，

則X的前驅(qū)為（）。

A.X的雙親B.X的右子樹中最左的結(jié)

點(diǎn)

C.X的左子樹中最右的結(jié)點(diǎn)D.X的左子樹中最右的結(jié)

點(diǎn)

7下列序列中，哪一個(gè)是堆（）？

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

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

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

8一棵Huffman樹共有203個(gè)結(jié)點(diǎn)，對(duì)其Huffman編碼，共能得

到（）個(gè)不同的碼字。

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

9下面說(shuō)法錯(cuò)誤的是（）。

A.一個(gè)有n個(gè)頂點(diǎn)和n條邊的無(wú)向圖一定是有環(huán)的。

B.建立十字鏈表的時(shí)間復(fù)雜度和建立鄰接表是相同的。

C.鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無(wú)向

圖的存儲(chǔ)都適用。

D.在某些圖的應(yīng)用問(wèn)題中，如果需要找到表示同一條邊的兩個(gè)

結(jié)點(diǎn)，那么采用鄰接多重表比鄰接表作為儲(chǔ)存結(jié)構(gòu)更為適

宜。

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

么在算法執(zhí)行過(guò)程中每個(gè)頂點(diǎn)進(jìn)隊(duì)次數(shù)最多為（）。

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

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

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

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

不屬于該圖的拓?fù)渑判蛴行蛐蛄惺牵ǎ?/p>

A.v1v2v3v4v5v6B.v1v4v2v3v5v6

C.v4v5v1v2v3v6D.v4v1v2v3v5v6

12判斷一個(gè)有向圖是否存在回路，除可利用拓?fù)渑判蚍椒ㄍ?，還

可以用（）。

A.求關(guān)鍵路徑的方法B.求最短路徑的方法

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

13設(shè)有一個(gè)二叉排序樹（二叉查找樹），其結(jié)點(diǎn)上存儲(chǔ)有數(shù)字1

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

程中訪問(wèn)過(guò)的結(jié)點(diǎn)序列。

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}

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

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

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

用二分法查找關(guān)鍵碼12需做（）次關(guān)鍵碼比較。

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

15一顆3階B-樹中有2047個(gè)關(guān)鍵字，包括葉結(jié)點(diǎn)層，該樹的最

大深度為（）。

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

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

16一顆深度為k的平衡二叉樹，其每個(gè)非終端結(jié)點(diǎn)的平衡因子均

為0，則該樹共有（）個(gè)結(jié)點(diǎn)。

17LetQdenoteaqueuecontainingsixteennumbersandSbeanempty

stack.Head(Q)returnstheelementattheheadofthequeue

QwithoutremovingitfromQ.SimilarlyTop(S)returnstheelementat

thetopofSwithoutremovingitfromS.Considerthealgorithmgiven

below.

Themaximumpossiblenumberofiterationsofthewhileloopinthe

algorithmis（）。

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

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

二叉樹可以得到這一遍歷結(jié)果。

20設(shè)一棵二叉樹有20個(gè)葉子結(jié)點(diǎn)，則在該樹中有2個(gè)孩子的結(jié)

點(diǎn)個(gè)數(shù)為（）。

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

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

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

有（）個(gè)。

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

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

長(zhǎng)度為（）。

23散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以（）取其值

域的每個(gè)值。（請(qǐng)?jiān)谧畲蟾怕?、最小概率、平均概率、同等概率這

些術(shù)語(yǔ)中選擇正確的進(jìn)行填空）

24假設(shè)某算法在輸入規(guī)模為n時(shí)的計(jì)算時(shí)間為T(n)=n2。在某臺(tái)

計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t秒?，F(xiàn)有另一臺(tái)計(jì)算機(jī)，

其運(yùn)行速度為第一臺(tái)計(jì)算機(jī)的64倍，那么在這臺(tái)計(jì)算機(jī)上用同

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

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

低依次為－，×，$，均右結(jié)合，則相應(yīng)的后綴式是（）。

三、綜合應(yīng)用題（本大題共7小題，共60分）

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

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

代碼判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是“回文”。請(qǐng)

給出缺失的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）

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

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

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++;

}

}

假設(shè)當(dāng)N=3500，上述代碼運(yùn)行1秒。那么，當(dāng)N=35000時(shí)，

該代碼的運(yùn)行時(shí)間最接近下面那個(gè)時(shí)間？請(qǐng)給出簡(jiǎn)單的分析過(guò)

程。

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

E.1hourF.2hours

28（8分）將關(guān)鍵字序列{23，14，9，6，30，12，18}散列存儲(chǔ)到

散列表中，散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開始的一維數(shù)組，

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

求裝填（載）因子為0.7。

請(qǐng)畫出所構(gòu)造的散列表。

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

序列：DJGBEHACKILF。

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

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

（3）采用孩子兄弟表示法來(lái)存儲(chǔ)該二叉樹，請(qǐng)畫出此二叉樹的

存儲(chǔ)結(jié)構(gòu)。

（4）畫出與此二叉樹對(duì)應(yīng)的森林。

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

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

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

BDEDFEABFBAFFCDCBEDFFFCCDEEF

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

CODE1、CODE2、CODE3、CODE4；表30-2給出了編碼特點(diǎn)，

即A、B、C、D，請(qǐng)給出這4種編碼方式所具有的編碼特點(diǎn)。（填

寫該編碼方式具有的編碼特點(diǎn)編號(hào)即可，不用給出具體分析過(guò)程）

表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）求從頂點(diǎn)1出發(fā)的廣度優(yōu)先搜索序列；

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

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

生成過(guò)程。

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

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

到的某個(gè)中間步驟的內(nèi)容。表32-2列出了6種排序算法。請(qǐng)按行

序直接給出每行對(duì)應(yīng)排序算法的編號(hào)。每個(gè)編號(hào)只使用一次。

表32-排序算法序列

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

18

算法2121630281016*206

1：18

算法621012283016*2016

2：18

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

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

算法2121630102816*206

3：18

算法102166181216*2030

4：28

算法21216281016*20618

5：30

表32-2：

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

編號(hào)編號(hào)

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

為5，2，1)

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

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

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

33如果一個(gè)序列是一個(gè)先單調(diào)遞增后單調(diào)遞減的序列，那