2018年武漢大學(xué)933計(jì)算機(jī)基礎(chǔ)

2018年招收攻讀碩士研究生

入學(xué)考試自主命題試題

考試科目及代碼：933計(jì)算機(jī)基礎(chǔ)(數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò))

適用專業(yè)：08用00計(jì)算機(jī)科學(xué)技術(shù)083900網(wǎng)絡(luò)空間安全

085211計(jì)算機(jī)技術(shù)

(所■答案都必須與在入耍欲上，寫(xiě)左鍬教欷上及草稿歆上無(wú)效，

考竟后徐耍履率敢皴袞①，

模擬卷一(藍(lán)3版)

填空題(20分，每題2分)

1.通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：、、和。

2.一個(gè)算法的時(shí)間復(fù)雜度為(n~3+n~210g2n)/n2,其數(shù)量級(jí)表示為。

3.設(shè)某順序循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾

指針R指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中最多存儲(chǔ)隊(duì)列元素。

4.設(shè)一棵三叉樹(shù)中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹(shù)中度數(shù)為

3的結(jié)點(diǎn)數(shù)有個(gè)。

5.設(shè)散列表的長(zhǎng)度為8,散列函數(shù)H(k)=k%7,用線性探測(cè)法解決沖突，則根據(jù)一組初始

關(guān)鍵字序列(8,15,16,22,30,32)構(gòu)造出的散列表的平均查找長(zhǎng)度是。

6.設(shè)有一組初始記錄關(guān)鍵字序列為(50,16,23,68,94,70,73),則將它們調(diào)整成初始

堆只需把16與相互交換即可。

7.IEEE802.3采用協(xié)議，IEEE802.il采用協(xié)議。

8.在采用TCP/IP協(xié)議通訊時(shí)，必須保證整個(gè)網(wǎng)段上主機(jī)的IP地址在或。

9.IPv6地址為個(gè)比特，其數(shù)據(jù)報(bào)基本首部為固定的字節(jié)。

10.表示主機(jī)比特全為“0”的IP地址，為：的地址，表示主機(jī)比特全為“1”的IP

地址，為：的地址。

判斷題（20分，每個(gè)2分）

No.12345678910

Answer

1.遞歸調(diào)用算法與相同功能的非遞歸算法相比，主要問(wèn)題在于重復(fù)計(jì)算太多，而且調(diào)用本

身需要分配額外的空間和傳遞數(shù)據(jù)和控制，所以時(shí)間與空間開(kāi)銷(xiāo)通常都比較大。（）

2.采用不同的遍歷方法，所得到的無(wú)向圖的生成樹(shù)總是相同的。（）

3.鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿的情況。（）

4.邊數(shù)很少的稀疏圖，適宜用鄰接矩陣表示。（）

5.直接選擇排序是一種穩(wěn)定的排序方法。（）

6.哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。（）

7.寬帶ISDN的核心技術(shù)是ATM技術(shù)。（）

8.在0SI模型中物理層實(shí)現(xiàn)了數(shù)據(jù)的無(wú)差錯(cuò)傳輸。（）

9.RIP協(xié)議采用的路徑算法是基于鏈路狀態(tài)協(xié)議的。（）

10.在命令狀態(tài)下鍵入“ping127.0.0.1”可以用來(lái)驗(yàn)證網(wǎng)卡是否正常。（）

三.選擇題（30分，每個(gè)3分）

No.12345678910

Answer

1.下列算法的時(shí)間復(fù)雜度為（）

voidfun（intn）｛

inti=0;

while(i*i*i<=n)

i++；

)

A.O(n)B,O(nlogn)C.而)D.0(4)

2.線性表(al,a2,…,an)以鏈接方式存儲(chǔ)時(shí)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜性為()

A.O(i)B.O(1)C.O(n)D.O(i-1)

3.下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）（）

A.深度優(yōu)先遍歷B.求兩個(gè)結(jié)點(diǎn)之間的路徑C.求最短路徑D.求關(guān)鍵路徑

4.一個(gè)棧的輸入序列為12345,則下列序列中不可能是棧的輸出序列的是（）。

A.23415B.54132C.23145D.15432

5.一棵二叉樹(shù)的前序遍歷序列為ABCDEFG,它的中序遍歷序列可能是（B）

A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG

6.為了使數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸延遲最小，首選的交換方式是（）。

A.電路交換

B.報(bào)文交換

C.分組交換

D.信元交換

7.在開(kāi)放系統(tǒng)互連環(huán)境中，兩個(gè)N層實(shí)體進(jìn)行通信，可能用到的服務(wù)是（）。

A.N-1層提供的服務(wù)

B.N層提供的服務(wù)

C.N+1層提供的服務(wù)

D.以上都不對(duì)

8.某部門(mén)申請(qǐng)到一個(gè)C類IP地址，若要分成8個(gè)子網(wǎng)，其掩碼應(yīng)為（）。

A.-55

B.

C.24

D.92

9.內(nèi)部網(wǎng)關(guān)協(xié)議包括（）o

A.OSPF和IGP

B.OSPF和EGP

C.RIP和BGP

D.OSPF和RIP

10.UDP數(shù)據(jù)報(bào)比IP數(shù)據(jù)報(bào)多提供了（）服務(wù)。

A.流量控制

B.擁塞控制

C.端口功能

D.路由轉(zhuǎn)發(fā)

四.簡(jiǎn)答題（60分）

1.一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。

求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

（遞歸解法。）

2.根據(jù)下圖回答下列問(wèn)題：

(1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(shù)

(2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹(shù)

(3)根據(jù)普利姆(Prim)算法，

3.假設(shè)哈希表的地址范圍是0-8,哈希函數(shù)為：H(K)=(K+l)MOD9K為關(guān)鍵字，用線

性表探測(cè)再散列法處理沖突，輸入關(guān)鍵字序列｛13,32,17,31,30,36,63]

回答下列問(wèn)題：

(1)畫(huà)出構(gòu)造的哈希表。

(2)計(jì)算成功查找長(zhǎng)度以及失敗查找長(zhǎng)度。

4.在數(shù)據(jù)傳輸過(guò)程中，若接收方收到的二進(jìn)制比特序列為10110011010,接收雙方采用的

生成多項(xiàng)式為G(x)=x4+x3+l,則該二進(jìn)制比特序列在傳輸中是否出錯(cuò)？如果傳輸沒(méi)

有出現(xiàn)差錯(cuò)，發(fā)送數(shù)據(jù)的比特序列和CRC檢驗(yàn)碼的比特序列分別是什么？

5.(1)子網(wǎng)掩碼為代表什么意思？

(2)某網(wǎng)絡(luò)的現(xiàn)在掩碼為48,問(wèn)該網(wǎng)絡(luò)能夠連接多少個(gè)主機(jī)？

(3)某A類網(wǎng)絡(luò)和某B類網(wǎng)絡(luò)的子網(wǎng)號(hào)subnet-id分別為16個(gè)1和8個(gè)1,問(wèn)這兩個(gè)

網(wǎng)絡(luò)的子網(wǎng)掩碼有何不同？

(4)某A類網(wǎng)絡(luò)的子網(wǎng)掩碼為55,它是否是一個(gè)有效的子網(wǎng)掩碼？

五.算法設(shè)計(jì)（20分）

（請(qǐng)使用類C語(yǔ)言進(jìn)行編程，如果編碼困難可以寫(xiě)偽代碼，會(huì)適當(dāng)扣分）

試寫(xiě)出算法，求任意二叉樹(shù)中第一條最長(zhǎng)的路徑長(zhǎng)度（多條相等只輸出一條），并輸出此路

徑上各結(jié)點(diǎn)的值。

typedefstructBiTree{

intdata；

structBiTree*Rc；

structBiTree*Lc；

}*BiTree；

程過(guò)大學(xué)

2018年招收攻讀碩士研究生

入學(xué)考試自主命題試題

考試科目及代碼：933計(jì)算機(jī)基礎(chǔ)（數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)）

適用專業(yè)：08用00計(jì)算機(jī)科學(xué)技術(shù)0839技網(wǎng)絡(luò)空間安全

085211計(jì)算機(jī)技術(shù)

（所■答案都必須與在卷耍欲上，寫(xiě)左鍬耍欲上及草稿歆上無(wú)效,

考竟后曲蹶成答耍欷袞①，

模擬卷一（'J版）參考答案

填空題（20分，每題2分）

1.通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：I正確性I、I易讀性I、I強(qiáng)壯性胤高效樹(shù)。

2.一個(gè)算法的時(shí)間復(fù)雜度為（n~3+n~210g2n）/n2,其數(shù)量級(jí)表示為I。（n）|。

3.設(shè)某順序循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾

指針R指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中最多存儲(chǔ)叵］隊(duì)列元素。

4.設(shè)一棵三叉樹(shù)中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹(shù)中度數(shù)為

3的結(jié)點(diǎn)數(shù)有回個(gè)。

5.設(shè)散列表的長(zhǎng)度為8,散列函數(shù)Il（k）=k%7,用線性探測(cè)法解決沖突，則根據(jù)一組初始

關(guān)鍵字序列（8,15,16,22,30,32）構(gòu)造出的散列表的平均查找長(zhǎng)度是國(guó)。

6.設(shè)有一組初始記錄關(guān)鍵字序列為（50,16,23,68,94,70,73）,則將它們調(diào)整成初始

堆只需把16與網(wǎng)相互交換即可。

7.IEEE802.3采用〔CSMA/CD脅議,IEEE802.11采用|CSMA/CA|協(xié)議。

8.在采用TCP/IP協(xié)議通訊時(shí),必須保證整個(gè)網(wǎng)段上主機(jī)的1P地址在I同一網(wǎng)前TI或網(wǎng)

絡(luò)號(hào)相同。

9.IPv6地址為畫(huà)個(gè)比特，其數(shù)據(jù)報(bào)基本首部為固定的畫(huà)字節(jié)。

10.表示主機(jī)比特全為“0”的IP地址，為：國(guó)的地址,表示主機(jī)比特全為“1”的IP

地址，為：尸藕的地址。

判斷題（20分，每個(gè)2分）

No.12345678910

AnswerVXVXXVVXXJ

1.遞歸調(diào)用算法與相同功能的非遞歸算法相比，主要問(wèn)題在于重復(fù)計(jì)算太多，而且調(diào)用本

身需要分配額外的空間和傳遞數(shù)據(jù)和控制，所以時(shí)間與空間開(kāi)銷(xiāo)通常都比較大。（V）

2.采用不同的遍歷方法，所得到的無(wú)向圖的生成樹(shù)總是相同的。（X）

3.鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿的情況。（V）

4.邊數(shù)很少的稀疏圖，適宜用鄰接矩陣表示。（X）

5.直接選擇排序是一種穩(wěn)定的排序方法。（X）

6.哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。（V）

7.寬帶ISDN的核心技術(shù)是ATM技術(shù)。（V）

8.在OSI模型中物理層實(shí)現(xiàn)了數(shù)據(jù)的無(wú)差錯(cuò)傳輸。（X）

9.RIP協(xié)議采用的路徑算法是基于鏈路狀態(tài)協(xié)議的。（X）

10.在命令狀態(tài)下鍵入“ping127.0.0.1”可以用來(lái)驗(yàn)證網(wǎng)卡是否正常。（V）

三.選擇題（30分，每個(gè)3分）

No.12345678910

AnswerCCABBAACDC

1.下列算法的時(shí)間復(fù)雜度為（C）

voidfun（intn）｛

inti=0;

while（i*i*i<=n）

i++；

）

A.O（n）B.O（nlogn）C.0（西）D.0（4）

2.線性表（al,a2,…,an）以鏈接方式存儲(chǔ)時(shí)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜性為（C）

A.O（i）B.O（1）C.O（n）D.O（i-1）

3.下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）（A）

A.深度優(yōu)先遍歷B.求兩個(gè)結(jié)點(diǎn)之間的路徑C.求最短路徑D.求關(guān)鍵路徑

4.一個(gè)棧的輸入序列為12345,則下列序列中不可能是棧的輸出序列的是（B）。

A.23415B.54132C.23145D.15432

5.一棵二叉樹(shù)的前序遍歷序列為ABCDEFG,它的中序遍歷序列可能是（B）

A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEG

6.為了使數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸延遲最小，首選的交換方式是（A

A.電路交換

B.報(bào)文交換

C.分組交換

D.信元交換

【解析】電路交換需要在傳輸之前建立一個(gè)固定的連接，在連接未拆除之前，數(shù)據(jù)通信雙方

一直占用該連接，保證了數(shù)據(jù)傳輸?shù)目煽啃?，因此其傳輸?shù)难舆t最短。

7.在開(kāi)放系統(tǒng)互連環(huán)境中，兩個(gè)N層實(shí)體進(jìn)行通信，可能用到的服務(wù)是（A）。

A.N-1層提供的服務(wù)

B.N層提供的服務(wù)

C.N+1層提供的服務(wù)

D.以上都不對(duì)

【解析】在協(xié)議的控制下，兩個(gè)對(duì)等實(shí)體間的通信使得本層能夠向上一層提供服務(wù)，要實(shí)現(xiàn)

本層協(xié)議，還需要使用下面一層所提供的服務(wù)。

8.某部門(mén)申請(qǐng)到一個(gè)C類IP地址，若要分成8個(gè)子網(wǎng)，其掩碼應(yīng)為（C）.

A...55

B.

C.24

D.92

【解析】C類地址范圍：?54。C類地址第1字節(jié)、第2字節(jié)和第3

個(gè)字節(jié)為網(wǎng)絡(luò)地址，第4個(gè)字節(jié)為主機(jī)地址。為了劃分成8個(gè)子網(wǎng)，必須占用3位主機(jī)

地址，第4個(gè)字節(jié)對(duì)應(yīng)掩碼的二進(jìn)制應(yīng)為11100000。

所以子網(wǎng)掩碼應(yīng)為：24。

9.內(nèi)部網(wǎng)關(guān)協(xié)議包括（D）。

A.OSPF和IGP

B.OSPF和EGP

C.RIP和BGP

D.OSPF和R1P

【解析】要區(qū)分外部網(wǎng)關(guān)協(xié)議（EGP）和內(nèi)部網(wǎng)關(guān)協(xié)議（IGP）,OSPF、RIP屬于內(nèi)部網(wǎng)關(guān)協(xié)議，

BGP則屬于外部網(wǎng)關(guān)協(xié)議。

10.UDP數(shù)據(jù)報(bào)比IP數(shù)據(jù)報(bào)多提供了（C）服務(wù)。

A.流量控制

B.擁塞控制

C.端口功能

D.路由轉(zhuǎn)發(fā)

【解析】雖然UDP協(xié)議和IP協(xié)議都是數(shù)據(jù)報(bào)協(xié)議，但是它們之間還是存在差別。其中,

最大的差別是IP數(shù)據(jù)報(bào)只能找到目的主機(jī)而無(wú)法找到目的進(jìn)程，UDP提供端口功能以及

復(fù)用和分用功能，可以將數(shù)據(jù)報(bào)投遞給對(duì)應(yīng)的進(jìn)程。

四.簡(jiǎn)答題(60分)

1.一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。

求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

uoidforg(intn,inti)

(

count++；

elseif(n<i)

(

forg(n+1,i)；

forg(n+2,i)；

)

遞歸解法。).

2.根據(jù)下圖回答下列問(wèn)題：

(1)從頂點(diǎn)A出發(fā)，求它的深度優(yōu)先生成樹(shù)

(2)從頂點(diǎn)E出發(fā)，求它的廣度優(yōu)先生成樹(shù)

(3)根據(jù)普利姆(Prim)算法,

設(shè)該圖用鄰接表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，頂點(diǎn)的鄰接點(diǎn)按頂點(diǎn)編號(hào)升序排列

(l)ABGFDEC(2)EACFBDG

⑶

3.假設(shè)哈希表的地址范圍是0-8,哈希函數(shù)為：H(K)=(K+l)MOD9K為關(guān)鍵字，用線

性表探測(cè)再散列法處理沖突，輸入關(guān)鍵字序列｛13,32,17,31,30,36,63]

回答下列問(wèn)題：

(3)畫(huà)出構(gòu)造的哈希表。

(4)計(jì)算成功查找長(zhǎng)度以及失敗查找長(zhǎng)度。

地址012345678

關(guān)鍵字17366330133231

比較次1121113

失敗432154321

成功10/7

失敗25/9

4.在數(shù)據(jù)傳輸過(guò)程中，若接收方收到的二進(jìn)制比特序列為10110011010,接收雙方采用的

生成多項(xiàng)式為G(x)=x4+x3+l,則該二進(jìn)制比特序列在傳輸中是否出錯(cuò)？如果傳輸沒(méi)

有出現(xiàn)差錯(cuò)，發(fā)送數(shù)據(jù)的比特序列和CRC檢驗(yàn)碼的比特序列分別是什么？

答：根據(jù)題意，生成多項(xiàng)式G(x)對(duì)應(yīng)的二進(jìn)制比特序列為11001。進(jìn)行如下的二進(jìn)制

模2除法，被除數(shù)為10110011010,除數(shù)為11001：

____________1101010

11001)10110011010

11001

11110

11001

11111

11001

11001

11001

0

所得余數(shù)為0,因此該二進(jìn)制比特序列在傳輸過(guò)程中沒(méi)有出現(xiàn)差錯(cuò)。發(fā)送數(shù)據(jù)的比特序列是

1011001,CRC

檢驗(yàn)碼的比特序列是1010。

5.(1)子網(wǎng)掩碼為代表什么意思？

(2)某網(wǎng)絡(luò)的現(xiàn)在掩碼為48,問(wèn)該網(wǎng)絡(luò)能夠連接多少個(gè)主機(jī)？

(3)某A類網(wǎng)絡(luò)和某B類網(wǎng)絡(luò)的子網(wǎng)號(hào)subnet-id分別為16個(gè)1和8個(gè)1,問(wèn)這兩個(gè)

網(wǎng)絡(luò)的子網(wǎng)掩碼有何不同？

(4)某A類網(wǎng)絡(luò)的子網(wǎng)掩碼為55,它是否是一個(gè)有效的子網(wǎng)掩碼？

答：(1)可代表C類地址對(duì)應(yīng)的子網(wǎng)掩碼默認(rèn)值：也可代表A類或B類

地址的掩碼，即主機(jī)號(hào)由最后8bit決定，而路由器尋找目的網(wǎng)絡(luò)的下一跳地址由前24bit決

定。

(2)248=(11111000)2，即IP地址中前29位代表網(wǎng)絡(luò)，后3位代表主機(jī)。所以共有主機(jī)

數(shù)為23=8,但由于主機(jī)號(hào)全0代表該網(wǎng)絡(luò)的網(wǎng)絡(luò)地址，主機(jī)號(hào)全1代表該網(wǎng)絡(luò)的廣播地

址，均不能分配給連網(wǎng)主機(jī)使用，所以網(wǎng)絡(luò)能夠連接的主機(jī)數(shù)為23—2=6臺(tái)。

(3)這兩個(gè)網(wǎng)絡(luò)的子網(wǎng)掩碼是一樣的，均為,但子網(wǎng)數(shù)不同，子網(wǎng)號(hào)為16bit

的A類網(wǎng)絡(luò)的子網(wǎng)數(shù)有2|6-2個(gè)，而子網(wǎng)號(hào)為8bit的B類網(wǎng)絡(luò)的子網(wǎng)數(shù)有28-2個(gè)。

(4)有效，因RFC文檔中沒(méi)有規(guī)定子網(wǎng)掩碼中的一串1必須是連續(xù)的，但不建議這樣使

用。

五.算法設(shè)計(jì)(20分)

(請(qǐng)使用類C語(yǔ)言進(jìn)行編程，如果編碼困難可以寫(xiě)偽代碼，會(huì)適當(dāng)扣分)

試寫(xiě)出算法，求任意二叉樹(shù)中第一條最長(zhǎng)的路徑長(zhǎng)度(多條相等只輸出一條)，并輸出此路

徑上各結(jié)點(diǎn)的值。

typedefstructBiTree{

intdata；

structBiTree*Rc；

structBiTree*Lc；

}*BiTree；

因?yàn)楹笮虮闅v棧中保留當(dāng)前結(jié)點(diǎn)的祖先的信息，用一變量保存棧的最高棧頂指針，每當(dāng)退棧

時(shí)，棧頂指針高于保存最高棧頂指針的值時(shí)，則將該棧倒入輔助棧中，輔助棧始終保存最長(zhǎng)

路徑長(zhǎng)度上的結(jié)點(diǎn)，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。

voidLongestPath(BiTreebt)//求二叉樹(shù)中的第一條最長(zhǎng)路徑長(zhǎng)度

{BiTreep=bt,IM,s[]；〃l,s是棧，元素是二叉樹(shù)結(jié)點(diǎn)指針，1中保留當(dāng)前最長(zhǎng)路徑中的結(jié)

點(diǎn)

inti>top=0,tag[],longest=0;

while(p||top>0)

{while(p){s[++top]=p；tag[top]=0;p=p->Lc;}//沿左分枝向下

if(tag[top]==l)〃當(dāng)前結(jié)點(diǎn)的右分枝已遍歷

{if(!s[top]->Lc&&!s[top]->Rc)〃只有到葉子結(jié)點(diǎn)時(shí)，才查看路徑長(zhǎng)度

if(top>longest){for(i=1;i<=top;i++)l[i]=s[i];longest=top;top—;}

〃保留當(dāng)前最長(zhǎng)路徑到1棧，記住最高棧頂指針，退棧

}

elseif(top>0){tag[top]=l;p=s[top].Rc;}〃沿右子分枝向下

}//while(p!=null||top>0)

}〃結(jié)束LongestPath

2018年招收攻讀碩士研究生

入學(xué)考試自主命題試題

考試科目及代碼：933計(jì)算機(jī)基礎(chǔ)（數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)）

適用專業(yè)：081200計(jì)算機(jī)科學(xué)技術(shù)083900網(wǎng)絡(luò)空間安全

085211計(jì)算機(jī)技術(shù)

（所■答案都必須與在答電欲上，寫(xiě)左鍬教欷上及草稿歆上無(wú)效，

考竟后徐蹶履率夏皴拿命，

模擬卷二（僦版）

填空題（20分，每題2分）

1.廣義表（a,（a,b）,d,e,（（i,j）,k））的長(zhǎng)度是,深度是。

2.循環(huán)隊(duì)列用數(shù)組A［0..mT］存放其元素值，已知其頭尾指針?lè)謩e是front和rear,則當(dāng)

前隊(duì)列的元素個(gè)數(shù)是。

3.對(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ù)雜度為。

4.已知數(shù)組AE0..9.0..9］的每個(gè)元素占5個(gè)存儲(chǔ)單元，將其按行優(yōu)先次序存儲(chǔ)在起始地

址為1000的連續(xù)的內(nèi)存單元中，則元素A［6,8］的地址為。

5.高度為K的完全二叉樹(shù)至少有個(gè)葉子結(jié)點(diǎn)。

6.如果含n個(gè)頂點(diǎn)的圖形形成一個(gè)環(huán)，則它有棵生成樹(shù)。

7.IP使用D類地址支持多播，其地址范圍是。

8.目前常用的四種信道復(fù)用方式是：、時(shí)分復(fù)用、和波分復(fù)用。

9.在路由表中，對(duì)第一條路由最主要的是和。

10.一個(gè)TCP報(bào)文段分為首部和—兩部分，TCP首部的最小長(zhǎng)度是字節(jié)。

判斷題（20分，每個(gè)2分）

No.12345678910

Answer

1.數(shù)組是同類型值的集合。（）

2.取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān).（）

3.若輸入序列為1,2,3,4,5,6,則通過(guò)一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1.（）

4.一個(gè)廣義表可以為其它廣義表所共享。（）

5.最小生成樹(shù)的KRUSKAL算法是一種貪心法（GREEDY）。（）

6.當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動(dòng)后，必將產(chǎn)生不同的關(guān)鍵路徑。（）

7.TCP適用于組播和廣播通信方式，而UDP只適用于單播。（）

8.OSI參考模型中的數(shù)據(jù)鏈路層的主要功能是負(fù)責(zé)分組流控制、差錯(cuò)控制等。（）

9.應(yīng)用層的網(wǎng)絡(luò)應(yīng)用程序分為直接網(wǎng)絡(luò)應(yīng)用和間接網(wǎng)絡(luò)應(yīng)用兩類。（）

10.RIP是一種距離矢量路由選擇算法，現(xiàn)在仍然廣泛使用，適合于大型網(wǎng)絡(luò)。（）

三.選擇題（30分，每個(gè)3分）

No.12345678910

Answer

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

x=2;

while（x<n/2）

x=2*x+l;

A.O（log2n）B.O（n）C.O（nlog2n）D.O（n2）

2.以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)

A.樹(shù)B.字符串C.隊(duì)D.棧

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

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

4.設(shè)哈希表長(zhǎng)為14,哈希函數(shù)是H（key）=key%ll,表中已有數(shù)據(jù)的關(guān)鍵字為15,38,61,84

共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的

位置是（）

A.8B.3C.5D.9

5.用直接插入排序方法對(duì)下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是

（）。

A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80

C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,40

6.在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（）。

A.G中有弧<Vi,Vj>B.G中有一條從Vi到Vj的路徑

C.G中沒(méi)有弧<Vi,Vj>D.G中有一條從Vj到Vi的路徑

7.以下沒(méi)有采用存儲(chǔ)轉(zhuǎn)發(fā)技術(shù)的交換方式是（）。

A.電路交換

B.報(bào)文交換

C.分組交換

D.信元交換

8.在以太網(wǎng)中，當(dāng)一臺(tái)主機(jī)發(fā)送數(shù)據(jù)時(shí)，總線上所有計(jì)算機(jī)都能檢測(cè)到這個(gè)數(shù)據(jù)信號(hào)，只

有數(shù)據(jù)幀中的目的地址與某主機(jī)的地址一致時(shí)，該主機(jī)才接收這個(gè)數(shù)據(jù)幀。這里所提到的

地址是()。

A.MAC地址

B.IP地址

C.端口

D.地理位置

9.局域網(wǎng)的協(xié)議結(jié)構(gòu)一般不包括(

A.網(wǎng)絡(luò)層

B.數(shù)據(jù)鏈路層

C.物理層

D.媒體訪問(wèn)控制層

10.考慮在一條1000米長(zhǎng)的電纜(無(wú)中繼器)上建立一個(gè)1Gb/s速率的CSMA/CD網(wǎng)

絡(luò)，假定信號(hào)在電纜中的速度為2*108米/秒。最小幀長(zhǎng)是()。

A.1220字節(jié)

B.1230字節(jié)

C.1280字節(jié)

D.1250字節(jié)

四.簡(jiǎn)答題(60分)

1.某算法的計(jì)算時(shí)間為：T(n)=4T(n/2)+O(n),其中T(l)=0(1),求其時(shí)間復(fù)雜

度，寫(xiě)出具體過(guò)程。

2.采用哈希函數(shù)H(k)=3*kmod13并用線性探測(cè)開(kāi)放地址法處理沖突，在數(shù)列地址空間

[0..12]中對(duì)關(guān)鍵字序列22,41,53,46,30,13,1,67,5k

(1)構(gòu)造哈希表(畫(huà)示意圖)；

(2)裝填因子；

(3)成功的平均查找長(zhǎng)度。

(4)不成功的平均查找長(zhǎng)度。

3.已知待排序的序列為（503,87,512,61,908,170,897,275,653,462）,試完成

下列各題。（12分）

（1）根據(jù)以上序列建立一個(gè)堆（畫(huà)出第一步和最后堆的結(jié)果圖），希望先輸出最小值。

（2）輸出最小值后，如何得到次小值。（并畫(huà)出相應(yīng)結(jié)果圖）

4.欲構(gòu)建一個(gè)數(shù)據(jù)傳輸率為1Gb/s的千兆以太網(wǎng)，假設(shè)電纜長(zhǎng)度為1km,其中無(wú)中繼器,

信號(hào)在電纜中的傳播速度為2*108m/s?則幀的最小長(zhǎng)度是多少？

5.一個(gè)自治系統(tǒng)有5個(gè)局域網(wǎng)，如下圖所示，LAN2至LAN5上的主機(jī)數(shù)分別為：91、

150、3和15,該自治系統(tǒng)分配到的IP地址塊為30.138.118/23,試給出每一個(gè)局域網(wǎng)的

地址塊（包括前綴）。

LAN2,91臺(tái)主機(jī)LAN3,150臺(tái)主機(jī)LAN4,3臺(tái)主機(jī)

LAN5,15臺(tái)主機(jī)

LANI

五.算法設(shè)計(jì)（20分）

（請(qǐng)使用類C語(yǔ)言進(jìn)行編程，如果編碼困難可以寫(xiě)偽代碼，會(huì)適當(dāng)扣分）

設(shè)計(jì)非遞歸算法求樹(shù)的深度。（20分）

typedefstructBiTree（

intdata；

structBiTree*rchild；

structBiTree*lchild；

}*BiTree；

2018年招收攻讀碩士研究生

入學(xué)考試自主命題試題

考試科目及代碼：933計(jì)算機(jī)基礎(chǔ)（數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)）

適用專業(yè)：081200計(jì)算機(jī)科學(xué)技術(shù)083900網(wǎng)絡(luò)空間安全

085211計(jì)算機(jī)技術(shù)

（所■答案都必須與在答電欲上，寫(xiě)左鍬教欷上及草稿歆上無(wú)效，

考竟后徐蹶履率夏皴拿命，

模擬卷二（箴版）參考答案

填空題（20分，每題2分）

1.廣義表（a,（a,b）,d,e,（（i,j）,k））的長(zhǎng)度是耳，深度是,

2.循環(huán)隊(duì)列用數(shù)組A［Om-1］存放其元素值，已知其頭尾指針?lè)謩e是front和rear,則當(dāng)

前隊(duì)列的元素個(gè)數(shù)是（rear-front+m）%川。。

3.對(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ù)雜度為國(guó)。

4.已知數(shù)組A［0..9,0..9］的每個(gè)元素占5個(gè)存儲(chǔ)單元，將其按行優(yōu)先次序存儲(chǔ)在起始地

址為1000的連續(xù)的內(nèi)存單元中，則元素A［6,8］的地址為回。

5.高度為K的完全二叉樹(shù)至少有四個(gè)葉子結(jié)點(diǎn)。

6.如果含n個(gè)頂點(diǎn)的圖形形成一個(gè)環(huán)，則它有臼棵生成樹(shù)。

7.IP使用D類地址支持多播，其地址范圍是1224.0.0.0~239.255.255.255

8.目前常用的四種信道復(fù)用方式是：|頻分復(fù)用|、時(shí)分復(fù)用、|碼分復(fù)用|和波分復(fù)

用。

9.在路由表中，對(duì)第一條路由最主要的是|目的網(wǎng)絡(luò)地址|和|下一跳地址|。

10.一個(gè)TCP報(bào)文段分為首部和陋兩部分，TCP首部的最小長(zhǎng)度是網(wǎng)字節(jié)。

判斷題（20分，每個(gè)2分）

No.12345678910

AnswerXXqqXXXqX

1.數(shù)組是同類型值的集合。（x）

2.取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān).（X）

3.若輸入序列為1,2,3,4,5,6,則通過(guò)一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1.

（4）

4.一個(gè)廣義表可以為其它廣義表所共享。（4）

5.最小生成樹(shù)的KRUSKAL算法是一種貪心法（GREEDY）。（4）

6.當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動(dòng)后，必將產(chǎn)生不同的關(guān)鍵路徑。

（X）

7.TCP適用于組播和廣播通信方式，而UDP只適用于單播。（x）

8.0SI參考模型中的數(shù)據(jù)鏈路層的主要功能是負(fù)責(zé)分組流控制、差錯(cuò)控制等。

（x）

9.應(yīng)用層的網(wǎng)絡(luò)應(yīng)用程序分為直接網(wǎng)絡(luò)應(yīng)用和間接網(wǎng)絡(luò)應(yīng)用兩類。（4）

10.RIP是一種距離矢量路由選擇算法，現(xiàn)在仍然廣泛使用，適合于大型網(wǎng)絡(luò)。

（x）

三.選擇題（30分，每個(gè)3分）

No.12345678910

AnswerAADDCDAAAD

1.設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是（A）。

x=2;

while(x<n/2)

x=2*x+l;

A.O(log2n)B.O(n)

C.O（nlog2n）D.O（n2）

2.以下數(shù)據(jù)結(jié)構(gòu)中，（A）是非線性數(shù)據(jù)結(jié)構(gòu)

A.樹(shù)B.字符串C.隊(duì)D.棧

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

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

4.設(shè)哈希表長(zhǎng)為14,哈希函數(shù)是H（key尸key%11,表中己有數(shù)據(jù)的關(guān)鍵字為15,38,61,84

共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的

位置是（D）

A.8B.3C.5D.9

5.用直接插入排序方法對(duì)下面四個(gè)序列進(jìn)行排序（由小到大），元素比較次數(shù)最少的是

（C）。

A.94,32,40,90,80,46,21,69B.32,40,21,46,69,94,90,80

C.21,32,46,40,80,69,90,94D.90,69,80,46,21,32,94,40

6.在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前,則下列情形不可能出現(xiàn)的是（D）。

A.G中有弧<Vi,Vj>B.G中有一條從Vi到Vj的路徑

C.G中沒(méi)有弧<Vi,Vj>D.G中有一條從Vj到Vi的路徑

7.以下沒(méi)有采用存儲(chǔ)轉(zhuǎn)發(fā)技術(shù)的交換方式是（A）。

A.電路交換

B.報(bào)文交換

C.分組交換

D.信元交換

【解析】“電路交換”又稱為“線路交換”，是一種面向連接的服務(wù)。電路交換沒(méi)有采用存儲(chǔ)轉(zhuǎn)

發(fā)機(jī)制，而報(bào)文交換和分組交換則采用了存儲(chǔ)轉(zhuǎn)發(fā)機(jī)制。

8.在以太網(wǎng)中，當(dāng)一臺(tái)主機(jī)發(fā)送數(shù)據(jù)時(shí)，總線上所有計(jì)算機(jī)都能檢測(cè)到這個(gè)數(shù)據(jù)信號(hào)，只

有數(shù)據(jù)幀中的目的地址與某主機(jī)的地址一致時(shí)，該主機(jī)才接收這個(gè)數(shù)據(jù)幀。這里所提到的

地址是（A）。

A.MAC地址

B.IP地址

C.端口

D.地理位置

【解析】數(shù)據(jù)幀中的源地址和目的地址指的是MAC地址。

9.局域網(wǎng)的協(xié)議結(jié)構(gòu)一般不包括（A）。

A.網(wǎng)絡(luò)層

B.數(shù)據(jù)鏈路層

C.物理層

D.媒體訪問(wèn)控制層

【解析】局域網(wǎng)中的所有主機(jī)都處于同一個(gè)網(wǎng)段中，不需要路由器或更上層設(shè)備將數(shù)據(jù)轉(zhuǎn)發(fā)

到不同網(wǎng)段，在局域網(wǎng)中只需要物理地址就可以實(shí)現(xiàn)主機(jī)間的通信，物理地址屬于數(shù)據(jù)鏈路

層的地址，因此局域網(wǎng)僅涉及數(shù)據(jù)鏈路層和物理層，不會(huì)包括網(wǎng)絡(luò)層及其上層。

10.考慮在一條1000米長(zhǎng)的電纜（無(wú)中繼器）上建立一個(gè)1Gb/s速率的CSMA/CD網(wǎng)

絡(luò)，假定信號(hào)在電纜中的速度為2*108米/秒。最小幀長(zhǎng)是（D）。

A.1220字節(jié)

B.1230字節(jié)

C.1280字節(jié)

D.1250字節(jié)

【解析】本題考查最小幀長(zhǎng)的計(jì)算，信道中的往返傳播延時(shí)=2*1000/（2*108）=10ps

=10-5so在1Gb/s即109b/s的速率下，所以最小幀長(zhǎng)=數(shù)據(jù)發(fā)送速率*往返傳播延

時(shí)=109*10—5=10000b=1250字節(jié)。

四.簡(jiǎn)答題(60分)

1.某算法的計(jì)算時(shí)間為：T(n)=4T(n/2)+O(n),其中T(l)=0(1),求其時(shí)間復(fù)雜

度，寫(xiě)出具體過(guò)程。

答：

假設(shè)有遞推關(guān)系式T(")=aT(m)+f(")，其中"為問(wèn)題規(guī)模，.為遞推的子問(wèn)題數(shù)量，￡為每個(gè)子問(wèn)題的規(guī)模(假設(shè)

每個(gè)子問(wèn)題的效?；疽粯?，/5)為遞推以外進(jìn)行的計(jì)算工作。

ail,A1為常數(shù)，*n)為函數(shù)，T(n)為非負(fù)整數(shù)。則有以下結(jié)果：

(D若/■(")=0(/08“-'),￡>0,那么7'(“)=6(/°8?")

⑵若/(”)=e"咱"),T(”)=e("啕alogn)

(3)若f(")=Q(”iog"+e),f>0,且對(duì)于某個(gè)常數(shù)c<1和所有充分大的"有a/(m)V<7(”),那么

T(n)=O(f(n)).

設(shè)T(n)=4T(n/2)+n,

則a=4,b=2,f(n)=n,代入得T(n)=O(n2)。

2.采用哈希函數(shù)H(k)=3*kmod13并用線性探測(cè)開(kāi)放地址法處理沖突，在數(shù)列地址空間

[0..12]中對(duì)關(guān)鍵字序列22,41,53,46,30,13,1,67,51.

(1)構(gòu)造哈希表(畫(huà)示意圖)；

(2)裝填因子；

(3)成功的平均查找長(zhǎng)度。

(4)不成功的平均查找長(zhǎng)度。

答：

(1)

散列地址0123456789101112

關(guān)鍵字13225314167465130

比較次數(shù)111212111

(2)裝填因子=9/13=0.7(3)ASLs*=ll/9(4)ASLx=29/13

3.已知待排序的序列為(503,87,512,61,908,170,897,275,653,462),試完成

下列各題。(12分)

(3)根據(jù)以上序列建立一個(gè)堆(畫(huà)出第一步和最后堆的結(jié)果圖)，希望先輸出最小值。

(4)輸出最小值后，如何得到次小值。(并畫(huà)出相應(yīng)結(jié)果圖)

答：

回畫(huà)畫(huà)畫(huà)回回

(2)求次小值

908

4.欲構(gòu)建一個(gè)數(shù)據(jù)傳輸率為1Gb/s的千兆以太網(wǎng)，假設(shè)電纜長(zhǎng)度為1km,其中無(wú)中繼器，

信號(hào)在電纜中的傳播速度為2*108m/s。則幀的最小長(zhǎng)度是多少？

答：已知電纜的長(zhǎng)度為1km,信號(hào)在電纜中的傳播速度為2*108m/s,則信號(hào)的單向傳播

時(shí)延為1/200000s,

往返時(shí)延=2*1/200000=1/100000s,即為該網(wǎng)絡(luò)的爭(zhēng)用期。為了按照CSMA/CD的方

式，最小幀的發(fā)送時(shí)間不能小于1/100000s,否則會(huì)被當(dāng)成無(wú)效幀。以1Gb/s

的數(shù)據(jù)傳輸速率發(fā)送數(shù)據(jù)，1/100000s內(nèi)可發(fā)送的比特?cái)?shù)為109*1/100000=10kb。因

此，幀的最小長(zhǎng)度為10kb。

5.一個(gè)自治系統(tǒng)有5個(gè)局域網(wǎng)，如下圖所示，LAN2至LAN5上的主機(jī)數(shù)分別為：91、

150、3和15,該自治系統(tǒng)分配到的IP地址塊為30.138.118/23,試給出每一個(gè)局域網(wǎng)的

地址塊(包括前綴)。

LAN2,91臺(tái)主機(jī)LAN3,150臺(tái)主機(jī)LAN4,3臺(tái)主機(jī)

LANI

答：分配網(wǎng)絡(luò)前綴應(yīng)先分配地址數(shù)較多的前綴。已知該自治系統(tǒng)分配到的IP地址塊為

30.138.118/23o

LAN3：主機(jī)數(shù)150,由于(27—2)<150+1<(28—2),所以主機(jī)號(hào)為8bit,網(wǎng)絡(luò)前綴為24bit。

取第24位為

0,分配地址塊/24,

LAN2：主機(jī)數(shù)91,由于(26—2)<91+1<(27—2),所以主機(jī)號(hào)為7bit,網(wǎng)絡(luò)前綴為25bit。

取第24,25位

10,分配地址塊/25?

LAN5：主機(jī)數(shù)為15,由于(24—2)VI5+l<(25—2),所以主機(jī)號(hào)為5bit,網(wǎng)絡(luò)前綴27bit?

取第24,25,

26,27位為1110,分配的地址塊為92/27?

LAN1：共有3個(gè)路由器，再加上一個(gè)網(wǎng)關(guān)地址，至少需要4個(gè)IP地址。由于(22—

2)<3+1<(23-2),所以主機(jī)號(hào)為3bit,網(wǎng)絡(luò)前綴29bit。取第24,25,26,27,28,29

位為111101,分配的地址塊為32/29?

LAN4：主機(jī)數(shù)為3,由于Q2—2)V3+1V(23—2),所以主機(jī)號(hào)為3bit,網(wǎng)絡(luò)前綴29bit。

取第24,25,26,27,28,29位為111110,分配的地址塊為40/29o

五.算法設(shè)計(jì)(20分)

(請(qǐng)使用類C語(yǔ)言進(jìn)行編程，如果編碼困難可以寫(xiě)偽代碼，會(huì)適當(dāng)扣分)

設(shè)計(jì)非遞歸算法求樹(shù)的深度。(20分)

typedefstructBiTree{

intdata；

structBiTree*rchild；

structBiTree*lchild；

}*BiTree；

[題目分析]由孩子兄弟鏈表表示的樹(shù)，求高度的遞歸模型是：若樹(shù)為空，高度為零；若第一

子女為空，高度為1和兄弟子樹(shù)的高度的大者；否則，高度為第一子女樹(shù)高度加1和兄弟子

樹(shù)高度的大者。其非遞歸算法使用隊(duì)列，逐層遍歷樹(shù)，取得樹(shù)的高度。

intheight(CSTreet)〃非遞歸遍歷求以孩子兄弟鏈表表示的樹(shù)的深度

{if(t==null)return(O);else{intfront=1,rear=1;//front,rear是隊(duì)頭隊(duì)尾

元素的指針

intlast=l,h=O;//last指向樹(shù)中同層結(jié)點(diǎn)中最后一個(gè)結(jié)點(diǎn)，h是樹(shù)的高度

Q[rear]=t;//Q是以樹(shù)中結(jié)點(diǎn)為元素的隊(duì)列

while(front<=last)

{t=Q[front++l;〃隊(duì)頭出列while(t!=null)

〃層次遍歷

{if(t->firstchild)Q[++rear]=t->firstchild;〃第一子女入隊(duì)t=t->nextsibling;〃同

層兄弟指針后移

)

if(front>last)//本層結(jié)束，深度加1(初始深度為0)

{h++;last=rear;}//last再移到指向當(dāng)前層最右一個(gè)結(jié)點(diǎn)

}//while(front<=last)

}//else

}//Height

2018年招收攻讀碩士研究生

入學(xué)考試自主命題試題

考試科目及代碼：933計(jì)算機(jī)基礎(chǔ)（數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)）

適用專業(yè)：08用00計(jì)算機(jī)科學(xué)技術(shù)083900網(wǎng)絡(luò)空間安全

085211計(jì)算機(jī)技術(shù)

（所■答案都必須與在入耍欲上，寫(xiě)成鍬耍欷上及草稿歆上無(wú)效，

考竟后徐耍成率敢皴袞?，

模擬卷三（僦版）

填空題（20分，每題2分）

1.隊(duì)列的插入操作是在隊(duì)列的進(jìn)行，刪除操作是在隊(duì)列的進(jìn)行。

2.廣義表A=（a,（a,b）,（（a,b）,c））,則它的深度為,它的長(zhǎng)度為.

3.二叉樹(shù)是指度為2的樹(shù)。一棵結(jié)點(diǎn)數(shù)為N的二叉樹(shù)，其所有結(jié)點(diǎn)的度的總和

是o

4.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用排序：