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

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

機(jī)密★啟用前

重慶郵電大學(xué)

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

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

科目代碼：802

考生注意事項(xiàng)

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

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

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

3、填（書）寫必須使用0.5mm黑色簽字筆。

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

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

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

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

一、選擇題（本大題共10小題，每小題2分，共20分）

1．對(duì)于雙向循環(huán)鏈表，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域next和prior，分別指向前驅(qū)和后

繼。在p指針?biāo)赶虻慕Y(jié)點(diǎn)之后插入s指針?biāo)附Y(jié)點(diǎn)的操作應(yīng)為（）。

A.p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

B.p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

C.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;

2．由abc,3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（）

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

3．設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1到8，j的值為

1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5，

8]的存儲(chǔ)首地址為()。

A.BA+141B.BA+180C.BA+222D.BA+225

4．一個(gè)棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是()。

A.231B.321

C.312D.123

5．下述編碼中哪一個(gè)不是前綴碼（）。

A.（00，01，10，11）B.（0，1，00，11）

C.（0，10，110，111）D.（1，01，000，001）

6．當(dāng)一棵有n個(gè)結(jié)點(diǎn)的二叉樹按層次從上到下，同層次從左到右將數(shù)據(jù)存放在

一維數(shù)組A[l..n]中時(shí)，數(shù)組中第i個(gè)結(jié)點(diǎn)的左孩子為（）。

A.A[2i](2i=<n)B.A[2i+1](2i+1=<n)C.A[i/2]D.無法確定

7．假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示,則刪除與某個(gè)頂點(diǎn)vi

相關(guān)的所有弧的時(shí)間復(fù)雜度是()。

A.O(n)B.O(e)C.O(n+e)D.O(n*e)

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

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

8．串的長(zhǎng)度是指（）。

A.串中所含不同字母的個(gè)數(shù)B．串中所含字符的個(gè)數(shù)

C.串中所含不同字符的個(gè)數(shù)D．串中所含非空格字符的個(gè)數(shù)

9．循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（）。

A.rear=rear+1B.rear=(rear+1)mod(m-1)

C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)

10．關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（）。

A.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B.從源點(diǎn)到匯點(diǎn)的最短路徑

C.最長(zhǎng)回路D.最短回路

二、填空題（本大題共15小題，每空2分，共40分）

1．中綴算式（3+4X）-2Y/3對(duì)應(yīng)的后綴算式為__________________。

2．在完全二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是______。

3．構(gòu)造n個(gè)結(jié)點(diǎn)的強(qiáng)連通圖，至少有______條弧。

4．設(shè)有一個(gè)空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為a，b，c，d，

e．經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_______，

而棧頂指針值是_______H。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)。

5．若串S1=‘ABCDEFG’,S2=‘9898’,S3=‘###’,S4=‘012345’,執(zhí)行

concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),lengt

h(S2)))，其結(jié)果為_______。

6．若一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法

建立的初始堆為_______。

7．在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時(shí)所需進(jìn)

行的關(guān)鍵字比較次數(shù)為_______。

8．有向圖的邊集為{<a,c>,<a,e>,<e,b>,<e,d>,<b,d>,<d,c),<c,f>}，該圖的一

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

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

個(gè)拓?fù)渑判驗(yàn)椋篲_________。

9．當(dāng)輸入序列局部有序或元素個(gè)數(shù)較小時(shí)，在快速排序、選擇排序、插入排序、

歸并排序、堆排序中，最佳的排序方法是__________。

10．假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間（參見右圖），其類型Queue2定義如

下：

typedefstruct{

DateTypedata[MaxSize]；

intfront[2],rear[2]；

}Queue2；

對(duì)于i=0或1，front[i]和rear[i]分別為第i個(gè)隊(duì)列的頭指針和尾指針。請(qǐng)對(duì)以下

算法填空，實(shí)現(xiàn)第i個(gè)隊(duì)列的入隊(duì)操作。

intEnQueue(Queue2*Q,inti,DateTypex)

{//若第i個(gè)隊(duì)列不滿，則元素x入隊(duì)列，并返回1；否則返回0

if(i<0||i>1)return0；

if(Q－>rear[i]==Q－>front[__________])return0；

Q－>data[__________]=x；

Q－>rear[i]=[__________];

return1；

}

11．高度為8的平衡二叉樹的結(jié)點(diǎn)數(shù)至少有__________個(gè)。

12.文件由______組成；記錄由______組成。

13．對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)

間復(fù)雜度為________,在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為

________。

14.在n個(gè)記錄的有序順序表中進(jìn)行折半查找，最大比較次數(shù)是__________。

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

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

15.求從某源點(diǎn)到其余各頂點(diǎn)的Dijkstra算法在圖的頂點(diǎn)數(shù)為10，用鄰接矩陣表

示圖時(shí)計(jì)算時(shí)間約為10ms，則在圖的頂點(diǎn)數(shù)為40，計(jì)算時(shí)間約為______ms。

三、問答題（本大題共6小題，每小題10分，共60分）

1．一個(gè)線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表

為HT[0..12]，散列函數(shù)為H（key）=key%13并用線性探查法解決沖突，請(qǐng)畫

出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度。

2．已知二叉樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，閱讀下面算法。

typedefstructnode{

DateTypedata；

Structnode*next；

}ListNode；

typedefListNode*LinkList；

LinkListLeafhead=NULL；

VoidInorder(BinTreeT)

{

LinkLists；

If(T){

Inorder(T－>lchild)；

If((!T－>lchild)&&(!T－>rchild))

{

s=(ListNode*)malloc(sizeof(ListNode))；

s－>data=T－>data；

s－>next=Leafhead；

Leafhead=s；

}

Inorder(T－>rchild);

}

}

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

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

對(duì)于如下所示的二叉樹

（1）畫出執(zhí)行上述算法后所建立的結(jié)構(gòu)

（2）說明該算法的功能

3.假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出

棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，

否則稱為非法序列。

（1）下面所示的序列中哪些是合法的？

A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO

（2）通過對(duì)（1）的分析，寫出一個(gè)算法，判定所給的操作序列是否合法。（假

定被判定的操作序列已存入一維數(shù)組charA[]中,若操作序列合法，返回true，

否則返回false）。

4.已知一個(gè)連通圖如下圖所示，試給出圖的鄰

接矩陣和鄰接表存儲(chǔ)示意圖，若從頂點(diǎn)v1出發(fā)

對(duì)該圖進(jìn)行遍歷，分別給出一個(gè)按深度優(yōu)先遍歷

和廣度優(yōu)先遍歷的頂點(diǎn)序列.

(1)圖的鄰接矩陣

(2)鄰接表存儲(chǔ)示意圖

(3)從v1開始的深度優(yōu)先遍歷的頂點(diǎn)序列

(4)分析在深度遍歷過程中，分別使用鄰接矩陣和鄰接表存儲(chǔ)的算法復(fù)雜度

(5)討論在圖遍歷問題中，這兩種存儲(chǔ)方式的優(yōu)劣

5．一棵二叉樹的先序序列為ABCDGEF，中序序列為CBDGAFE。

(1)請(qǐng)畫出該二叉樹

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

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

(2)將二叉樹轉(zhuǎn)換為相應(yīng)的森林

6.請(qǐng)閱讀下列算法，回答問題

sort（r,n）

{

for(i=2;i<=n;i++)

{x=r(i);r(0)=x;j=i-1;

while(x<r(j))

{

r(j+1)=r(j);

j=j-1;

}

r(j+1)=x;

}

}

（1）這是什么類型的排序算法，該排序算法穩(wěn)定嗎？

（2）設(shè)置r(0)的作用是什么？

（3）若將while語句中判斷條件改為x<=r(j),該算法將會(huì)有什么變化？

（4）若將while