云南開(kāi)放大學(xué)數(shù)據(jù)結(jié)構(gòu)網(wǎng)上作業(yè)1-8

云南開(kāi)放大學(xué)數(shù)據(jù)結(jié)構(gòu)網(wǎng)上作業(yè)1一、單項(xiàng)選擇題(共17題,共68分)第1

題（4分）：（

）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A、數(shù)據(jù)元素

B．?dāng)?shù)據(jù)對(duì)象

C．?dāng)?shù)據(jù)結(jié)構(gòu)

D．?dāng)?shù)據(jù)項(xiàng)正確答案:

B第2

題（4分）：把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（

）。A．物理結(jié)構(gòu)

B．邏輯結(jié)構(gòu)

C．算法的具體實(shí)現(xiàn)

D．給相關(guān)變量分配存儲(chǔ)單元正確答案:

A第3

題（4分）：從n個(gè)數(shù)中選取最大元素（

）。A．基本操作是數(shù)據(jù)元素間的交換

B．算法的時(shí)間復(fù)雜度是O(n2)C．算法的時(shí)間復(fù)雜度是O(n)

D．需要進(jìn)行(n+1)次數(shù)據(jù)元素間的比較正確答案:

C第4

題（4分）：數(shù)據(jù)的（

）結(jié)構(gòu)與所使用的計(jì)算機(jī)無(wú)關(guān)。A．邏輯

B．物理

C．存儲(chǔ)

D．邏輯與存儲(chǔ)正確答案:

A第5

題（4分）：數(shù)據(jù)的物理結(jié)構(gòu)（

）。A．與數(shù)據(jù)的邏輯結(jié)構(gòu)無(wú)關(guān)

B．僅僅包括數(shù)據(jù)元素的表示C．只包括數(shù)據(jù)元素間關(guān)系的表示

D．包括數(shù)據(jù)元素的表示和關(guān)系的表示正確答案:

D第6

題（4分）：數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（

）結(jié)構(gòu)。A．物理

B．存儲(chǔ)

C．邏輯與物理

D．邏輯正確答案:

D第7

題（4分）：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（

）。A．只能有一個(gè)數(shù)據(jù)項(xiàng)組成

B．至少有二個(gè)數(shù)據(jù)項(xiàng)組成C．可以是一個(gè)數(shù)據(jù)項(xiàng)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成

D．至少有一個(gè)數(shù)據(jù)項(xiàng)為指針類型正確答案:

C第8

題（4分）：算法的時(shí)間復(fù)雜度與（

）有關(guān)。A．所使用的計(jì)算機(jī)

B．計(jì)算機(jī)的操作系統(tǒng)

C．算法本身

D．?dāng)?shù)據(jù)結(jié)構(gòu)正確答案:

C第9

題（4分）：同一種邏輯結(jié)構(gòu)（

）。A．只能有唯一的存儲(chǔ)結(jié)構(gòu)B．可以有不同的存儲(chǔ)結(jié)構(gòu)C．只能表示某一種數(shù)據(jù)元素之間的關(guān)系D．以上三種說(shuō)法均不正確正確答案:

B答案解析：暫無(wú)解析第10

題（4分）：線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（

）的關(guān)系。A．一對(duì)一

B．一對(duì)多C．多對(duì)多

D．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼正確答案:

A第11

題（4分）：樹(shù)形結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（

）的關(guān)系。BA．一對(duì)一

B．一對(duì)多C．多對(duì)多

D．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼正確答案:

B第12

題（4分）：圖形結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（

）的關(guān)系。A．一對(duì)一

B．一對(duì)多C．多對(duì)多

D．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼正確答案:

C第13

題（4分）：以下特征中，（

）不是算法的特性。A．有窮性

B．確定性

C．有效性

D．有0個(gè)或多個(gè)輸出正確答案:

D第14

題（4分）：某算法的時(shí)間復(fù)雜度為O（n）,表明該算法的（

）A.問(wèn)題規(guī)模為n

B.執(zhí)行時(shí)間等于nC.執(zhí)行的時(shí)間與n成正比

D.問(wèn)題規(guī)模與n成正比正確答案:

C第15

題（4分）：以下算法的時(shí)間復(fù)雜度為（

）。publicstaticvoidfun(intn){intj=0;for(i=1;i<=n;i++)j=j+i;}A.O(n)

B.O(n2)

C.O(nlog2n)

D.O(log2n)正確答案:

A第16

題（4分）：以下算法的時(shí)間復(fù)雜度為（

）。publicstaticvoidfun(intn){for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){System.out.print(j+”*”+i+”=”+i*j);}System.out.println();}}A.O(n)

B.O(n2)

C.O(nlog2n)

D.O(log2n)正確答案:

B第17

題（4分）：以下算法的時(shí)間復(fù)雜度為（

）。publicstaticvoidfun(intn){intj=0;for(i=1;i<=n;2*i){j=j+i;}System.out.println(j);}A.O(n)

B.O(n2)

C.O(nlog2n)

D.O(log2n)正確答案:

D二、判斷題(共8題,共32分)第18

題（4分）：在相同的規(guī)模n下,時(shí)間復(fù)雜度為O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度為O(2n)的算法。（

）正確答案:

√第19

題（4分）：所謂最壞的時(shí)間復(fù)雜度是指在最壞的情況下估算算法在執(zhí)行時(shí)間上的一個(gè)上界。（

）正確答案:

√第20

題（4分）：同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言越高級(jí)，執(zhí)行效率就越高。(

)正確答案:

×第21

題（4分）：同一種邏輯結(jié)構(gòu)可以用不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)（

）。正確答案:

√第22

題（4分）：一個(gè)算法可以無(wú)限制的執(zhí)行下去。（

）。正確答案:

×第23

題（4分）：程序就是算法。（

）。正確答案:

×第24

題（4分）：數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（

）正確答案:

×第25

題（4分）：數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)中世紀(jì)的存儲(chǔ)形式。（

）正確答案:

√

云南開(kāi)放大學(xué)數(shù)據(jù)結(jié)構(gòu)網(wǎng)上作業(yè)2一、單項(xiàng)選擇題(共22題,共64分)第1

題（3分）：線性表是有n個(gè)（

）的有限序列。A.數(shù)據(jù)表

B.字符

C.數(shù)據(jù)元素

D.數(shù)據(jù)項(xiàng)正確答案:

C第2

題（3分）：線性表是一個(gè)（

）。A.有限序列，可以為空

B.有限序列，不可以為空C.無(wú)限序列，可以為空

D.無(wú)限序列，不可以為空正確答案:

A第3

題（3分）：以下（

）是一個(gè)線性表。A.由n個(gè)實(shí)數(shù)組成的集合

B.由100個(gè)字符組成的序列C.由所有整數(shù)組成的序列

D.

所有奇數(shù)組成的序列正確答案:

B第4

題（3分）：在線性表中，除了開(kāi)始元素外，每個(gè)元素（

）。A.只有唯一的前驅(qū)元素

B.只有唯一的后即元素字符C.有多個(gè)前驅(qū)元素

D.有多個(gè)后繼元素正確答案:

A第5

題（3分）：順序表的最大有優(yōu)點(diǎn)是(

)。A.存儲(chǔ)密度大

B.插入運(yùn)算方便C.刪除運(yùn)算方便

D.可以方便地用于各種邏輯的存儲(chǔ)表示正確答案:

A第6

題（3分）：對(duì)于順序表，訪問(wèn)編號(hào)為i的元素的時(shí)間復(fù)雜度為（

）。A.O(n)

B.O(1)

C.O(nlog2n)

D.O(log2n)正確答案:

B第7

題（3分）：對(duì)于順序表，在編號(hào)為i處插入一個(gè)新元素的間復(fù)雜度為（

）。A.O(n)

B.O(1)

C.O(nlog2n)

D.O(log2n)正確答案:

A第8

題（3分）：采用順序查找法對(duì)長(zhǎng)度為n的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行（

）次元素間的比較。A．n+2

B．n

C．n-1

D．n/2正確答案:

B第9

題（3分）：帶頭結(jié)點(diǎn)的單向鏈表的頭指針為head，該鏈表為空的判定條件是（

）的值為真。A．head==NULL

B．head.getNext()==headC．head.getNext()==NULL

D．head==head.getNext()正確答案:

C第10

題（3分）：鏈表所具備的特點(diǎn)是（

）。A．可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)

B．占用連續(xù)的存儲(chǔ)空間C．可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)D．插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)正確答案:

D第11

題（3分）：設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n，對(duì)于插入操作，設(shè)插入位置是等概率的，則插入一個(gè)元素平均移動(dòng)元素的次數(shù)為（

）。A．n/2

B．n

C．n-1

D．n-i+1正確答案:

A第12

題（3分）：設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n，對(duì)于刪除操作，設(shè)刪除位置是等概率的，則刪除一個(gè)元素平均移動(dòng)元素的次數(shù)為（

）。A．(n-1)/2

B．n

C．2n

D．n-i正確答案:

A第13

題（3分）：設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n，要?jiǎng)h除第i（0<=i<=n-1）個(gè)元素，按課本的算法，當(dāng)i=（

）時(shí)，移動(dòng)元素的次數(shù)為3。A．3

B．n/2

C．n-4

D．4正確答案:

C第14

題（3分）：設(shè)順序存儲(chǔ)的線性長(zhǎng)度為n，要在第i（0<=i<=n）個(gè)元素之前插入一個(gè)新元素，按課本的算法當(dāng)i=（

）時(shí)，移動(dòng)元素次數(shù)為2。A．n/2

B．n

C．1

D．n-2正確答案:

D答案解析：

在表長(zhǎng)為3的現(xiàn)象表上，在位序號(hào)為0位置插入的元素，需要向后移動(dòng)3元素開(kāi)辟空間供新元素存儲(chǔ)，移動(dòng)元素次數(shù)為3-0=32。歸納出在表長(zhǎng)為n的表上，在位序號(hào)為i的位置插入一個(gè)元素，需要移動(dòng)x=n-i個(gè)元素?，F(xiàn)在已知x=2,2=n-i,則i=n-2第15

題（3分）：設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i(0<=i<=n-1)個(gè)元素，按照課本算法，需移動(dòng)元素的個(gè)數(shù)為（

）。A．n-i+1

B．n-i

C．n-i-1

D．i正確答案:

C第16

題（3分）：下述各線性結(jié)構(gòu)中可以隨機(jī)訪問(wèn)的是（

）。A.單向鏈表

B.雙向鏈表

C.單向循環(huán)鏈表

D.順序表正確答案:

D第17

題（3分）：線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（

）。A．一定是不連續(xù)的

B．必須是連續(xù)的C．可以連續(xù)也可以不連續(xù)

D．部分地址必須是連續(xù)的正確答案:

C第18

題（3分）：在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn)，可用的語(yǔ)句是（

）。A．p=q.getNext();

B．p.setNext(q);C．p.setNext(q.getNext());

D．q.setNext(NULL);正確答案:

C第19

題（3分）：在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（

）。A．p.setNext(s);s.setNext(p.getNext());B．p,setNext(s.getNext());C．p=s.getNext();D．s.setNext(p.getNext());p.setNext(s);正確答案:

D第20

題（3分）：按照教材算法，在一個(gè)長(zhǎng)度為n的順序表中為了刪除第5個(gè)元素，從前到后依次移動(dòng)了15個(gè)元素。則原順序表的長(zhǎng)度為（

）。A.21

B.20

C.19

D.25正確答案:

A第21

題（2分）：針對(duì)線性表，在存儲(chǔ)后如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用（

）存儲(chǔ)方式最節(jié)省時(shí)間。A．單鏈表

B．雙鏈表

C．順序表

D．單循環(huán)鏈表正確答案:

C第22

題（2分）：假設(shè)在順序表中，每一個(gè)數(shù)據(jù)元素所占的存儲(chǔ)單元的數(shù)目為4，且第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為100，則第位序號(hào)為7的數(shù)據(jù)元素的存儲(chǔ)地址是：（

）。A．106

B．107

C．124

D．128正確答案:

D二、判斷題(共18題,共36分)第23

題（2分）：線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間。（

）正確答案:

√第24

題（2分）：正確答案:

√第25

題（2分）：線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間。（

）正確答案:

√第26

題（2分）：正確答案:

√第27

題（2分）：線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)。（

）正確答案:

√第28

題（2分）：正確答案:

√第29

題（2分）：線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)。（

）正確答案:

√第30

題（2分）：正確答案:

√第31

題（2分）：線性表的順序結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。（

）正確答案:

√第32

題（2分）：正確答案:

√第33

題（2分）：線性表的順序結(jié)構(gòu)中，數(shù)據(jù)元素是不能隨機(jī)訪問(wèn)的。（

）正確答案:

√第34

題（2分）：正確答案:

√第35

題（2分）：線性表的順序結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上也相鄰。（

）正確答案:

√第36

題（2分）：正確答案:

√第37

題（2分）：線性表的順序結(jié)構(gòu)中，進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高。（

）正確答案:

√第38

題（2分）：答案：錯(cuò)正確答案:

√第39

題（2分）：順序存儲(chǔ)方式只適合存儲(chǔ)線性結(jié)構(gòu)。（

）錯(cuò)正確答案:

√第40

題（2分）：答案：錯(cuò)正確答案:

√

云南開(kāi)放大學(xué)數(shù)據(jù)結(jié)構(gòu)網(wǎng)上作業(yè)3一、單項(xiàng)選擇題(共23題,共73分)第1

題（4分）：隊(duì)列的插入操作在（

）進(jìn)行。A．隊(duì)頭

B．隊(duì)尾

C．隊(duì)頭或隊(duì)尾

D．在任意指定位置正確答案:

B第2

題（4分）：隊(duì)列的刪除操作在（

）進(jìn)行。A．隊(duì)頭

B．隊(duì)尾

C．隊(duì)頭或隊(duì)尾

D．在任意指定位置正確答案:

A第3

題（4分）：棧的插入操作在（

）進(jìn)行。A．棧頂

B．棧底

C．棧頂或棧底

D．在任意指定位置正確答案:

A第4

題（4分）：棧的刪除操作在（

）進(jìn)行。A.棧頂

B.棧底

C.棧頂或棧底

D.在任意指定位置正確答案:

A第5

題（3分）：一個(gè)隊(duì)列的入隊(duì)序列是2，4，6，8，則隊(duì)列的輸出序列是（

）。A．8，6，4，2

B．2，4，6，8

C．4，2，8，6

D．6，4，2，8正確答案:

B第6

題（3分）：一個(gè)隊(duì)列的入隊(duì)序列是5，6，7，8，則隊(duì)列的輸出序列是（

）。A.5

6

7

8

B.8

7

6

5C.7

8

6

5

D.可能有多種情況正確答案:

A第7

題（3分）：一個(gè)棧的進(jìn)棧序列是1，2，3，4，則不可能的出棧序列是（

）（進(jìn)出棧操作可以交替進(jìn)行）。A．3，2，4，1

B．1，4，2，3C．4，3，2，1

D．3，2，1，4正確答案:

B第8

題（3分）：一個(gè)棧的進(jìn)棧序列是5，6，7，8，則棧的不可能的出棧序列是（

）（進(jìn)出棧操作可以交替進(jìn)行）A．5，8，6，7

B．7，6，8，5

C．7，6，5，8

D．8，7，6，5正確答案:

A第9

題（3分）：一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能輸出序列是（

）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A．dceab

B．edcba

C．decba

D．a(chǎn)bcde正確答案:

A第10

題（3分）：以下說(shuō)法不正確的是（

）。A．順序棧中，棧滿時(shí)再進(jìn)行進(jìn)棧操作稱為“上溢”B．順序棧中，?？諘r(shí)再作出棧棧操作稱為“下溢”C．順序隊(duì)列中，當(dāng)尾指針已經(jīng)超越隊(duì)列存儲(chǔ)空間的上界，則一定是隊(duì)列已滿D．順序隊(duì)列中，隊(duì)列的頭指針和尾指針均超越隊(duì)列存儲(chǔ)空間的上界，則隊(duì)列已空正確答案:

C第11

題（3分）：以下說(shuō)法不正確的是（

）。A．棧的特點(diǎn)是后進(jìn)先出B．隊(duì)列的特點(diǎn)是先進(jìn)先出C．棧的刪除操作在棧底進(jìn)行，插入操作在棧頂進(jìn)行D．隊(duì)列的插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)頭進(jìn)行答題歷史：C正確答案:

C第12

題（3分）：元素2，4，6，8按順序依次進(jìn)棧，則該棧的不可能輸出序列是（

）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A．8，6，4，2

B．2，4，6，8

C．4，2，8，6

D．8，6，2，4正確答案:

D第13

題（3分）：元素2，4，6按順序依次進(jìn)棧，則該棧的不可能的輸出序列是（

）。A.6

4

2

B.6

2

4

C.4

2

6

D.2

6

4正確答案:

B第14

題（3分）：棧和隊(duì)列的相同點(diǎn)是（

）。A．都是后進(jìn)先出B．都是后進(jìn)后出C．邏輯結(jié)構(gòu)與線性表不同D．邏輯結(jié)構(gòu)與線性表相同，都是操作規(guī)則受到限制的線性表正確答案:

D第15

題（3分）：從一個(gè)棧頂指針為top的鏈棧中插入一個(gè)由P指向的新結(jié)點(diǎn)時(shí)，則執(zhí)行的操作是（）。A．p.setNext(top);top=p;

B．top=p;p.setNext(top);C．top.setNext(p);p=top;

D．top.setNext(p);p=top;正確答案:

A第16

題（3分）：設(shè)top是一個(gè)鏈棧的棧頂指針，棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，則出棧操作為（

）。A．x=top.getData();top=top.getNext();

B．top=top.getNext();x=top.getData();C．x=top.getNext();top=top.getData();

D．top.setNext(top);x=top.getData();正確答案:

A第17

題（3分）：設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊(duì)列的頭指針和尾指針，要執(zhí)行出隊(duì)操作，用x保存出隊(duì)元素的值，p為指向結(jié)點(diǎn)類型的指針，可執(zhí)行如下操作：p=front.getNext();x=p.getData();然后執(zhí)行（

）。A．front=p.getNext();

B．front.setNext(p.getNext());C．front=p;

D．front.setNext(p);正確答案:

B第18

題（3分）：設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊(duì)列的頭指針和尾指針。設(shè)p指向要入隊(duì)的新結(jié)點(diǎn)(該結(jié)點(diǎn)已被賦值)，則入隊(duì)操作為（

）。A．rear.setNext(p);rear=p;

B．rear.setNext(p);p=rear;C．p=rear.getNext();rear=p;

D．rear=p;rear.setNext(p);正確答案:

A第19

題（3分）：在一個(gè)鏈隊(duì)列中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（

）。A．f．setNext(s);f=s;

B．r.setNext（s）;r=s;C．s．setNext(r);r=s;

D．s.setNext(f);f=s;正確答案:

B第20

題（3分）：在一個(gè)鏈隊(duì)列中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為（

）。A．r=f.getNext();

B．r=r.getNext();

C．f=r.getNext();

D．f=f.getNext();正確答案:

D第21

題（3分）：在一個(gè)循環(huán)隊(duì)列中，隊(duì)列的空間大小為length,設(shè)對(duì)頭指針為front,隊(duì)尾指針為rear,按照教材采用減少一個(gè)存儲(chǔ)元素的方法，以下那個(gè)能判斷隊(duì)列已滿。（

）A.(rear+1)%length==front;

B.rear==front;C.

rear%length==front;

D.(rear-1)%length==front;正確答案:

A第22

題（3分）：若一個(gè)棧用數(shù)組data[n]存儲(chǔ),空棧初始棧頂指針top為n-1,則如元素x進(jìn)棧的正確操作是：（

）A.top++;data[top]=x;

B.data[top]=x;top++;C.top–;data[top]=x;

D.data[top]=x;top–;正確答案:

D第23

題（3分）：為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題，通常設(shè)計(jì)打印機(jī)數(shù)據(jù)緩沖區(qū)，主機(jī)將輸出的數(shù)據(jù)依次寫(xiě)入緩沖區(qū)，而打印機(jī)依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是：（

）。A.棧

B.隊(duì)列

C.樹(shù)

D.圖正確答案:

B二、判斷題(共9題,共27分)第24

題（3分）：棧和隊(duì)列都是一種特殊的線性表。（

）對(duì)正確答案:

√第25

題（3分）：?？梢杂庙樞蚪Y(jié)構(gòu)實(shí)現(xiàn)，也可以使用鏈表結(jié)構(gòu)實(shí)現(xiàn)。（

）對(duì)正確答案:

√第26

題（3分）：隊(duì)列可以使用順序結(jié)構(gòu)實(shí)現(xiàn)，也可以使用鏈表結(jié)構(gòu)實(shí)現(xiàn)。（

）正確答案:

√第27

題（3分）：編輯軟件的撤銷編輯內(nèi)容操作可以通過(guò)棧結(jié)構(gòu)來(lái)實(shí)現(xiàn)。（

）正確答案:

√第28

題（3分）：瀏覽器記錄用戶的訪問(wèn)地址以實(shí)現(xiàn)“回撤”操作，可以通過(guò)隊(duì)列結(jié)構(gòu)來(lái)實(shí)現(xiàn)。（

）正確答案:

×第29

題（3分）：不考慮優(yōu)先級(jí)的前提下，打印機(jī)任務(wù)可以采用棧結(jié)構(gòu)實(shí)現(xiàn)。（

）正確答案:

×第30

題（3分）：遞歸的實(shí)現(xiàn)過(guò)程，可以使用棧實(shí)現(xiàn)。（

）正確答案:

√第31

題（3分）：方法調(diào)用的實(shí)現(xiàn)過(guò)程，通常采用棧實(shí)現(xiàn)。（

）正確答案:

√第32

題（3分）：操作系統(tǒng)進(jìn)程管理設(shè)計(jì)中，不考慮優(yōu)先級(jí)的條件下，可以采用隊(duì)列結(jié)構(gòu)設(shè)計(jì)。（

）正確答案:

√

云南開(kāi)放大學(xué)數(shù)據(jù)結(jié)構(gòu)網(wǎng)上作業(yè)4一、單項(xiàng)選擇題(共29題,共86分)第1

題（3分）：串方法concat(str)的功能是進(jìn)行串（

）。A．比較

B．復(fù)制

C．賦值

D．連接正確答案:

D第2

題（3分）：串函數(shù)s=“Hello”;s.indexOf(“e”,0)的值為（

）。A．1

B．0

C．“He”

D．“e”正確答案:

A第3

題（3分）：空串的長(zhǎng)度為（

）。A．0

B．1

C．2

D．3正確答案:

A第4

題（3分）：以下陳述中正確的是（

）。A．串是一種特殊的線性表

B．串的長(zhǎng)度必須大于零C．串中元素只能是字母

D．空串就是空白串正確答案:

A第5

題（3分）：設(shè)有兩個(gè)串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱為（

）。A．求子串

B．連接

C．匹配

D．求串長(zhǎng)正確答案:

C第6

題（3分）：串是（

）。A．不少于一個(gè)字母的序列

B．任意個(gè)字母的序列C．不少于一個(gè)字符的序列

D．有限個(gè)字符的序列正確答案:

D第7

題（3分）：串的長(zhǎng)度是指（

）。A．串中所含不同字母的個(gè)數(shù)

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

D．串中所含非空格字符的個(gè)數(shù)正確答案:

B第8

題（3分）：若串S=“English”，其子串的個(gè)數(shù)是（

）。A．9

B．16

C．36

D．29正確答案:

D第9

題（3分）：下面關(guān)于串的敘述中，不正確的是（

）。A．串是字符的有限序列

B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運(yùn)算

D．串即可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)正確答案:

B第10

題（3分）：串與普通的線性表相比較，它的特殊性體現(xiàn)在（

）。A．順序的存儲(chǔ)結(jié)構(gòu)

B．鏈接的存儲(chǔ)結(jié)構(gòu)C．?dāng)?shù)據(jù)元素是一個(gè)字符

D．?dāng)?shù)據(jù)元素可以任意正確答案:

C第11

題（3分）：空串與空格串（

）。A．相同

B．不相同

C．可能相同

D．無(wú)法確定正確答案:

B第12

題（3分）：兩個(gè)字符串相等的條件是（

）。A．兩串的長(zhǎng)度相等B．兩串包含的字符相同C．兩串的長(zhǎng)度相等，并且兩串包含的字符相同D．兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同正確答案:

D第13

題（3分）：在實(shí)際應(yīng)用中，要輸入多個(gè)字符串，且長(zhǎng)度無(wú)法預(yù)定。則應(yīng)該采用（

）存儲(chǔ)比較合適。A．鏈?zhǔn)?/p>

B．順序

C．堆結(jié)構(gòu)

D．無(wú)法確定正確答案:

A第14

題（3分）：對(duì)特殊矩陣進(jìn)行壓縮的目的是(

)。A．表達(dá)式變得簡(jiǎn)單

B．對(duì)矩陣元素存取方便C．去掉矩陣中多于元素

D．減少不必要的存儲(chǔ)空間正確答案:

D第15

題（3分）：對(duì)于n階對(duì)稱矩陣，如果以行或者列存放到內(nèi)存中，則需要(

)個(gè)存儲(chǔ)單元進(jìn)行保存。A．n*(n+1)/2

B．n*n/2

C.n*(n-1)/2

D.n*n正確答案:

A第16

題（3分）：對(duì)于n階對(duì)稱矩陣A(矩陣A的第一個(gè)元素為A[0][0])，利用數(shù)組S存儲(chǔ)（數(shù)組S的下標(biāo)從0開(kāi)始），以行優(yōu)先順序存儲(chǔ)則A[5][3]元素，在S數(shù)組中的下標(biāo)是：(

)A.S[18]

B.S[13]

C.S[16]

D.S[15]正確答案:

A第17

題（3分）：對(duì)于n階對(duì)稱矩陣A(矩陣A的第一個(gè)元素為A[0][0])，利用數(shù)組S存儲(chǔ)（數(shù)組S的下標(biāo)從0開(kāi)始），以行優(yōu)先順序存儲(chǔ)則A[4][6]元素在S數(shù)組中的下標(biāo)是：(

)A.S[25]

B.S[16]

C.S[21]

D.S[15]正確答案:

A第18

題（3分）：設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹鞔鎯?chǔ)到一維數(shù)組b中（數(shù)組下標(biāo)從0開(kāi)始），則矩陣中元素A[8][5]在一維數(shù)組b中的下標(biāo)是（

）。A．b[33]

B．b[32]

C．b[85]

D．b[41]正確答案:

D第19

題（3分）：設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中。（矩陣A的第一個(gè)元素為A[0][0]，數(shù)組b的下標(biāo)從0開(kāi)始），則矩陣元素A[5][3]對(duì)應(yīng)一維數(shù)組b的數(shù)組元素是（

）。A．b[18]

B．b[8]

C．b[13]

D．b[10]正確答案:

A第20

題（3分）：設(shè)有一個(gè)12階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中（矩陣A的第一個(gè)元素為A[0][0]，數(shù)組b的下標(biāo)從0開(kāi)始），則矩陣A中第4行的元素在數(shù)組b中的下標(biāo)i一定有（

）。A．7≤i≤10

B．11≤i≤15

C．9≤i≤14

D．6≤i≤9正確答案:

D第21

題（3分）：設(shè)有一個(gè)15階的對(duì)稱矩陣a，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從0開(kāi)始），則矩陣中元素a[7][6]在一維數(shù)組B中的下標(biāo)是（

）。A．42

B．13

C．27

D．34正確答案:

D第22

題（3分）：設(shè)有一個(gè)15階的對(duì)稱矩陣a，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中。（矩陣A的第一個(gè)元素為a0,0，數(shù)組b的下標(biāo)從0開(kāi)始），則數(shù)組元素b[13]對(duì)應(yīng)A的矩陣元素是（

）。A．a(chǎn)[4][3]

B．a(chǎn)[6][4]

C．a(chǎn)[7][2]

D．a(chǎn)[6][8]正確答案:

A第23

題（3分）：設(shè)有一個(gè)20階的對(duì)稱矩陣a，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從0開(kāi)始），則矩陣中元素a[9][2]在一維數(shù)組B中的下標(biāo)是（

）。A．41

B．32

C．18

D．47正確答案:

D第24

題（3分）：設(shè)有一個(gè)10階的對(duì)角矩陣，其半帶寬為2，則需要使用（

）個(gè)存儲(chǔ)空間存儲(chǔ)該矩陣元素。A．44

B．45

C．34

D．35正確答案:

A第25

題（3分）：在Java語(yǔ)言中，利用數(shù)組a存放字符串“Hello”，以下語(yǔ)句中正確的是（

）。A．char

a[10]=“Hello”;B．char

a[10];

a=“Hello”;C．char

a[10]=‘Hello’;D．char

a[]={‘H’,’e’,’l’,’l’,’o’};正確答案:

D第26

題（3分）：稀疏矩陣的三元組存儲(chǔ)方法（

）。A．實(shí)現(xiàn)矩陣的轉(zhuǎn)置操作,只需將每個(gè)三元組行和列的下標(biāo)交換即可B．矩陣的非零元素個(gè)數(shù)和位置在操作中變化不大時(shí)較有效C．是一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D．比十字鏈表更高效正確答案:

B第27

題（3分）：采用十字鏈表表示一個(gè)稀疏矩陣,每一個(gè)非零元素一般用一個(gè)含有（

）域的結(jié)點(diǎn)表示。A．5

B．4

C．3

D.2正確答案:

A第28

題（3分）：在稀疏矩陣壓縮后，必然會(huì)失去（

）功能。A．順序存儲(chǔ)

B．隨機(jī)存儲(chǔ)

C．輸入輸出

D.以上都不對(duì)正確答案:

B第29

題（2分）：以下(

)是稀疏矩陣的一種存儲(chǔ)方法。A．十字鏈表

B．循環(huán)鏈表

C．?dāng)?shù)組

D.棧正確答案:

A二、判斷題(共7題,共14分)第30

題（2分）：空串是任何串的子串。（

）正確答案:

√第31

題（2分）：任何串都是其自身的子串。（

）正確答案:

√第32

題（2分）：空白串與空串是一樣的。（

）正確答案:

×第33

題（2分）：若兩個(gè)串有相同的字符集，則說(shuō)明兩個(gè)串相等。（

）正確答案:

×第34

題（2分）：串中任意多個(gè)連續(xù)的字符組成的子序列稱為該串的子串。（

）正確答案:

√第35

題（2分）：特殊矩陣壓縮是為了去掉矩陣中多于元素。（

）正確答案:

×第36

題（2分）：特殊矩陣壓縮是減少不必要的存儲(chǔ)空間。（

）正確答案:

√

云南開(kāi)放大學(xué)數(shù)據(jù)結(jié)構(gòu)網(wǎng)上作業(yè)5一、單項(xiàng)選擇題(共35題,共100分)第1

題（3分）：樹(shù)最適合用來(lái)表示（

）。A．有序數(shù)據(jù)元素

B.無(wú)序數(shù)據(jù)元素C.數(shù)據(jù)元素之間存在層次關(guān)系的數(shù)據(jù)

D.元素之間無(wú)聯(lián)系正確答案:

C第2

題（3分）：對(duì)于一顆有n個(gè)節(jié)點(diǎn)的樹(shù)，其中所有度之和等于：（

）。A．n

B．n-1

C．n-2

D．n+1正確答案:

B第3

題（3分）：對(duì)于一顆有n個(gè)節(jié)點(diǎn)、度為4的樹(shù)來(lái)說(shuō)，（

）。A．樹(shù)的高度最多為n-3

B．樹(shù)的高度最多為n-4C．第i層上最多有4(i-1)個(gè)節(jié)點(diǎn)

D．至少在某一層上正好有4個(gè)節(jié)點(diǎn)正確答案:

A第4

題（3分）：對(duì)于一顆高度為h、度為4的樹(shù)來(lái)說(shuō)，（

）。A．至少有h+3個(gè)節(jié)點(diǎn)

B．至多有4h-1個(gè)節(jié)點(diǎn)C．至多有4h個(gè)節(jié)點(diǎn)

D．至少有h+4個(gè)節(jié)點(diǎn)正確答案:

A第5

題（3分）：對(duì)于一顆有50個(gè)節(jié)點(diǎn)的，度為3的樹(shù)來(lái)說(shuō)，其最小高度為（

）。A．3

B．4

C．5

D．6正確答案:

C第6

題（3分）：對(duì)于一顆度為4的樹(shù)來(lái)說(shuō)，若有20個(gè)度為4的節(jié)點(diǎn)，10個(gè)度為3的節(jié)點(diǎn)，1個(gè)度為2的節(jié)點(diǎn)，10個(gè)度為1的節(jié)點(diǎn)，則樹(shù)有多少個(gè)葉子節(jié)點(diǎn)：（

）。A．41

B．82

C．115

D．122正確答案:

B第7

題（3分）：二叉樹(shù)與度為2的樹(shù)的相同之處包括：（

）。A．每個(gè)節(jié)點(diǎn)都有一個(gè)或兩個(gè)孩子B．至少有一個(gè)根節(jié)點(diǎn)C．至少有一個(gè)度為2的節(jié)點(diǎn)D.每個(gè)節(jié)點(diǎn)至多只有一個(gè)雙親節(jié)點(diǎn)正確答案:

D第8

題（3分）：假設(shè)一顆二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)為50，則它的最小高度為：（

）。A．4

B．5

C．6

D．7正確答案:

C第9

題（3分）：高度為h的二叉樹(shù)最大節(jié)點(diǎn)個(gè)數(shù)為：（

）。A．2h

B．2h-1

C．2h-1

D．2h-1-1正確答案:

C第10

題（3分）：具有10個(gè)葉子節(jié)點(diǎn)的二叉樹(shù)有（

）個(gè)度為2的節(jié)點(diǎn)。A．8

B．9

C．10

D．11正確答案:

B第11

題（3分）：一個(gè)具有1025個(gè)節(jié)點(diǎn)的二叉樹(shù)的高度為（

）。A．11

B．10

C．11~1025

D．12~1024正確答案:

C第12

題（3分）：一顆完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)為100，則第60個(gè)節(jié)點(diǎn)的度為（

）。A．0

B．1

C．2

D．不確定正確答案:

A第13

題（3分）：一顆滿二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)為n，其中有m個(gè)葉子節(jié)點(diǎn)，高度為h，則（

）。A．n=h+m

B．h+m=2n

C．m=h-1

D．n=2h-1正確答案:

D第14

題（3分）：根據(jù)使用頻率為5的字符設(shè)計(jì)的哈夫曼編碼，不能的是（

）。A．111，110，10，01，00

B．000，001，010，011，1C．100，11，10，1，0

D．001，000，01，11，10正確答案:

C第15

題（3分）：若二叉樹(shù)的中序遍歷結(jié)果是abcdef，且c為根節(jié)點(diǎn)，則（

）。A．節(jié)點(diǎn)C有兩顆子樹(shù)

B．二叉樹(shù)有兩個(gè)度為0的節(jié)點(diǎn)C．二叉樹(shù)的高為5

D．以上都不對(duì)正確答案:

A第16

題（3分）：任何一顆二叉樹(shù)，采用自上而下,自左至右的方法遍歷,如果節(jié)點(diǎn)a有左孩子b,右孩子c，則在節(jié)點(diǎn)的先序遍歷、中序遍歷、后續(xù)遍歷中，（

）。A．節(jié)點(diǎn)b一定在節(jié)點(diǎn)a的前面

B．節(jié)點(diǎn)a一定在節(jié)點(diǎn)c的前面C．節(jié)點(diǎn)b一定在節(jié)點(diǎn)c的前面

D．節(jié)點(diǎn)a一定在節(jié)點(diǎn)b的前面正確答案:

C第17

題（3分）：若唯一確定一顆二叉樹(shù)，只需知道二叉樹(shù)的（

）。A．先序序列

B．中序序列

C．中序和后序序列

D．先序和后序序列正確答案:

C第18

題（3分）：若唯一確定一顆二叉樹(shù)，只須知道二叉樹(shù)的（

）。A．先序序列和后序序列

B．先序序列和層次序列C．層次序列和后序序列

D．層次序列和中序序列正確答案:

D第19

題（3分）：一顆二叉樹(shù)的中序序列為ABDCEFG,后序序列為BDCAFGE,則其左子樹(shù)中的節(jié)點(diǎn)個(gè)數(shù)為（

）。A．3

B．2

C.4

D.5正確答案:

C第20

題（3分）：若一顆二叉樹(shù)的中序序列為BDAECF,先序序列為ABDCEF,則該樹(shù)的后序序列為（

）。A．DBEFCA

B．DEBFCA

C.DFEBCA

D．DBFECA正確答案:

A第21

題（3分）：若一顆二叉樹(shù)的先序序列為EFHIGJK,中序序列為HFIEJKG,,則該樹(shù)根節(jié)點(diǎn)的右孩子節(jié)點(diǎn)為（

）。A．E

B．F

C.G

D．H正確答案:

C第22

題（3分）：若一顆二叉樹(shù)的后序序列為DABEC,中序序列為DEBAC，則該樹(shù)的先序序列為（

）。A．ACBED

B．DECAB

C.DEABC

D．CEDBA正確答案:

D第23

題（3分）：對(duì)二叉排序樹(shù)進(jìn)行（

）遍歷，遍歷所得到的序列是有序序列。A．按層次

B．前序

C．中序

D．后序正確答案:

C第24

題（3分）：深度為5的完全二叉樹(shù)第5層上有4個(gè)結(jié)點(diǎn)，該樹(shù)一共有（

）個(gè)結(jié)點(diǎn)。A．28

B．30

C．31

D．19正確答案:

D第25

題（3分）：深度為5的完全二叉樹(shù)共有20個(gè)結(jié)點(diǎn)，則第5層上有（

）個(gè)結(jié)點(diǎn)(根所在結(jié)點(diǎn)為第一層)。A．3

B．8

C．5

D．6正確答案:

C第26

題（3分）：一棵哈夫曼樹(shù)共有n個(gè)非葉結(jié)點(diǎn)，則該樹(shù)一共有（

）個(gè)結(jié)點(diǎn)。A.2*n-1

B.2*n+1

C.2*n

D.2*(n-1)正確答案:

B第27

題（3分）：一棵哈夫曼樹(shù)共有n個(gè)非葉結(jié)點(diǎn)，則該樹(shù)有（

）個(gè)葉結(jié)點(diǎn)。A．n

B．n+1

C．n-1

D．2n正確答案:

B第28

題（3分）：一棵哈夫曼樹(shù)共有n個(gè)葉結(jié)點(diǎn)，則該樹(shù)有（

）個(gè)非葉結(jié)點(diǎn)。A．n-1

B．n

C．n+1

D．2n正確答案:

A第29

題（3分）：一棵哈夫曼樹(shù)有n個(gè)葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)），該樹(shù)總共有（

）個(gè)結(jié)點(diǎn)。A．2n-2

B．2n-1

C．2n

D．2n+2正確答案:

B第30

題（3分）：設(shè)有13個(gè)權(quán)值的結(jié)點(diǎn)，用它們組成一棵哈夫曼樹(shù)，則該樹(shù)有（

）個(gè)結(jié)點(diǎn)。A．13

B．12

C．26

D．25正確答案:

D第31

題（2分）：一棵哈夫曼樹(shù)總共有23個(gè)結(jié)點(diǎn)，該樹(shù)共有（

）個(gè)葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）。A．10

B．13

C．11

D．12正確答案:

D第32

題（2分）：一棵完全二叉樹(shù)共有30個(gè)結(jié)點(diǎn)，則該樹(shù)的高度是（

）。A．6

B．4

C．3

D．5正確答案:

D第33

題（2分）：一棵完全二叉樹(shù)的高度是5，最后一層上有6個(gè)結(jié)點(diǎn)，該樹(shù)共有（

）個(gè)結(jié)點(diǎn)。A．30

B．20

C．21

D．23正確答案:

C第34

題（2分）：一棵有n個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)，則該樹(shù)共有（

）個(gè)指針域?yàn)榭铡．2n

B．2n+1

C．2n+2

D．n+1正確答案:

D第35

題（2分）：在一棵二叉樹(shù)中，若根的編號(hào)從0開(kāi)始,若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（

）。A．2i

B．2i-1

C．2i+2

D．2i+1正確答案:

C

云南開(kāi)放大學(xué)數(shù)據(jù)結(jié)構(gòu)網(wǎng)上作業(yè)6一、單項(xiàng)選擇題(共23題,共100分)第1

題（5分）：在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度之和等于邊數(shù)的（

）倍。A.1/2

B.1

C.2

D.4正確答案:

C答案解析：無(wú)向圖中，一條邊計(jì)入兩個(gè)頂點(diǎn)的度數(shù)。第2

題（5分）：有n個(gè)頂點(diǎn)的無(wú)向圖，最多有（

）條邊。A.n

B.n(n-1)

C.n（n-1）/2

D.2n正確答案:

C答案解析：完全無(wú)向圖的邊數(shù)最多。有n個(gè)頂點(diǎn)的完全無(wú)向圖有n（n-1）/2條邊。第3

題（5分）：在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要（

）條邊。A.n

B.n+1

C.

n-1

D.n/2正確答案:

C答案解析：成為樹(shù)圖是邊最少。第4

題（5分）：在無(wú)向圖中，定義頂點(diǎn)i到頂點(diǎn)j的路徑，是從頂點(diǎn)i到頂點(diǎn)j的一個(gè)（

）。A.頂點(diǎn)序列

B.頂點(diǎn)個(gè)數(shù)

C.權(quán)值之和

D.邊的條數(shù)正確答案:

A答案解析：路徑是由頂點(diǎn)序列構(gòu)成的。第5

題（5分）：在n個(gè)頂點(diǎn)的連通圖中，任意一條簡(jiǎn)單的路徑，其長(zhǎng)度不可能超過(guò)（

）。A.1

B.n/2

C.n-1

D.n正確答案:

C答案解析：若路徑長(zhǎng)度超過(guò)n-1,則其中必存在重復(fù)的頂點(diǎn)。第6

題（5分）：以說(shuō)法錯(cuò)誤的是（

）。A.圖和樹(shù)的區(qū)別在于圖的邊數(shù)大于等于頂點(diǎn)數(shù)B.無(wú)向圖的連通分量是指無(wú)向圖中極大連通子圖C.一個(gè)強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量D.一個(gè)圖中所有頂點(diǎn)的度之和等于邊數(shù)的兩倍正確答案:

A答案解析：一個(gè)有向圖可以有很多頂點(diǎn)沒(méi)有邊。第7

題（5分）：對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣大小是（

）。A.n

B.(n-1)*(n-1)

C.n-1

D.n*n正確答案:

D答案解析：含有n個(gè)頂點(diǎn)的圖采用鄰接矩陣存儲(chǔ)，矩陣大小為n*n。第8

題（5分）：對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無(wú)向圖存儲(chǔ)在鄰接矩陣中，則非零元素的個(gè)數(shù)是（

）。A.n

B.2e

C.e

D.n+e正確答案:

B答案解析：

無(wú)向圖的鄰接矩陣中，每個(gè)非零元素記2次，即非零元素個(gè)數(shù)為2e。第9

題（4分）：對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的有向圖存儲(chǔ)在鄰接矩陣中，則非零元素的個(gè)數(shù)是（

）。A.n

B.2e

C.e

D.n+e正確答案:

C答案解析：

有向圖的鄰接矩陣中，每個(gè)非零元素記1次，即非零元素個(gè)數(shù)為e。第10

題（4分）：如果從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先遍歷即可訪問(wèn)所有的頂點(diǎn)。則該圖一定是一個(gè)（

）。A.完全圖

B.連通圖

C.有回路

D.一棵樹(shù)正確答案:

B答案解析：

只有連通圖才能一次深度優(yōu)先遍歷即可訪問(wèn)所有頂點(diǎn)。第11

題（4分）：一個(gè)無(wú)向連通圖的生出樹(shù)是含有該連通圖的全部頂點(diǎn)的（

）。A.極小連通子圖

B.極小連通圖

C.極大連通子圖

D.極大子圖正確答案:

A答案解析：生成樹(shù)是含有全部頂點(diǎn)的極小連通子圖。第12

題（4分）：最小生成樹(shù)是指（

）。A.由連通圖所得到的邊數(shù)最少的生成樹(shù)B.由連通圖所得到的頂點(diǎn)數(shù)相對(duì)較少的生成樹(shù)C.由連通圖所有生成樹(shù)中權(quán)值之和為最小的生成樹(shù)D.連通圖的極小連通子圖正確答案:

A第13

題（4分）：求最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為（

）。A.O(n)

B.O(n+e)

C.O(n2)

D.

O(ne)正確答案:

C第14

題（4分）：求最短路徑的Floyd算法的時(shí)間復(fù)雜度為（

）。A.O(n)

B.O(n+e)

C.O(n2)

D.

O(n3)正確答案:

D第15

題（4分）：在一個(gè)有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為s，則所有頂點(diǎn)的入度之和為（

）。A.

sB.s-1C.

s+1D.n正確答案:

A第16

題（4分）：一個(gè)有向圖有n個(gè)頂點(diǎn)，則每個(gè)頂點(diǎn)的度可能的最大值是（

）。A.n-1B.2(n-1)C.nD.2n正確答案:

B第17

題（4分）：具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有（）條邊才能確保是一個(gè)連通圖。A.5B.6C.7D.8正確答案:

A第18

題（4分）：一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有（）條邊。A.nB.n(n-1)C.

n(n-1)/2D.2n正確答案:

C第19

題（4分）：任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（

）。A.至少有一棵

B.只有一棵

C.一定有多棵

D.可能不存在正確答案:

A第20

題（4分）：已知一個(gè)圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（

）。A．2m

B．m

C．2m+1

D．m/2正確答案:

A答案解析：一條邊連接兩個(gè)頂點(diǎn)，可以記為兩個(gè)頂點(diǎn)的度。第21

題（4分）：已知一個(gè)圖的所有頂點(diǎn)的度數(shù)之和為m，則m一定不可能是（

）。A．4

B．8

C．12

D．9正確答案:

D答案解析：在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度之和等于邊數(shù)的2倍。因此，度之和肯定是偶數(shù)。第22

題（4分）：以下說(shuō)法不正確的是（

）。A．連通圖G一定存在生成樹(shù)B．連通圖G的生成樹(shù)中一定包含G的所有頂點(diǎn)C．連通圖G的生成樹(shù)中不一定包含G的所有邊D．連通圖G的生成樹(shù)可以是不連通的正確答案:

D第23

題（4分）：以下說(shuō)法正確的是（

）。A．連通圖G的生成樹(shù)中可以包含回路B．連通圖G的生成樹(shù)可以是不連通的C．連通圖G的生成樹(shù)一定是唯一的D．連通圖G的生成樹(shù)一定是連通而不包含回路的正確答案:

D

云南開(kāi)放大學(xué)數(shù)據(jù)結(jié)構(gòu)網(wǎng)上作業(yè)7一、單項(xiàng)選擇題(共25題,共100分)第1

題（4分）：穩(wěn)定的排序算法指（

）。A．經(jīng)過(guò)排序后，能使關(guān)鍵字相同的元素保持原順序中的相對(duì)位置不變B．經(jīng)過(guò)排序后，能使關(guān)鍵字相同的元素保持原順序中的絕對(duì)位置不變C．排序算法的性能與被排序元素的個(gè)數(shù)關(guān)系不大D．排序算法的性能與被排序元素的個(gè)數(shù)關(guān)系密切正確答案:

A第2

題（4分）：以下排序方法中，（

）不需要進(jìn)行關(guān)鍵字的比較。A．快速排序

B．歸并排序

C．基數(shù)排序

D．堆排序正確答案:

C第3

題（4分）：以下排序方法中，穩(wěn)定的排序方式是（

）。A．快速排序

B．希爾排序

C．基數(shù)排序

D．堆排序正確答案:

C第4

題（4分）：將1000個(gè)英文單詞進(jìn)行排序，采用（

）方法最好。A．快速排序

B．直接插入排序

C．堆排序

D．基數(shù)排序正確答案:

D第5

題（4分）：外排序是指（

）。A．在外存上進(jìn)行的排序方法B．不需要使用內(nèi)存的排序方法C．?dāng)?shù)據(jù)很大，需要人工干預(yù)的排序方法D.排序前后數(shù)據(jù)在外存，排序時(shí)數(shù)據(jù)調(diào)入內(nèi)存的排序方法正確答案:

D第6

題（4分）：在待排序的元素序列基本有序的前提下，效率最高的排序方法是（

）。A.直接插入排序

B．簡(jiǎn)單選擇排序

C．快速排序

D．歸并排序正確答案:

A第7

題（4分）：內(nèi)部排序算法的穩(wěn)定性是指(

)。A．該排序算法不允許有相同的關(guān)鍵字記錄B．該排序算法允許有相同的關(guān)鍵字記錄C．平均時(shí)間為0（nlogn）的排序方法D．以上都不對(duì)正確答案:

D第8

題（4分）：下面給出的四種排序算法中，(

)是不穩(wěn)定的排序。A．插入排序

B．堆排序

C．二路歸并排序

D．冒泡排序正確答案:

B第9

題（4分）：在下列排序算法中，哪一種算法的時(shí)間復(fù)雜度與初始排序序列無(wú)關(guān)（

）。A．直接插入排序

B．冒泡排序

C．快速排序

D．直接選擇排序正確答案:

D第10

題（4分）：關(guān)鍵字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中(

)的兩趟排序后的結(jié)果。A．選擇排序

B.冒泡排序

C.插入排序

D.堆排序正確答案:

C第11

題（4分）：下列排序方法中，(

)所需的輔助空間最大。A．選擇排序

B．希爾排序

C．快速排序

D．歸并排序正確答案:

D第12

題（4分）：一組記錄的關(guān)鍵字為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為支點(diǎn)得到的一次劃分結(jié)果為（

）。A．(38,40,46,56,79,84)

B．(40,38,46,79,56,84)C．(40,38,46,56,79,84)

D．(40,38,46,84,56,79)正確答案:

C第13

題（4分）：在對(duì)一組關(guān)鍵字序列{70，55，100，15，33，65，50，40，95}，進(jìn)行直接插入排序時(shí)，把65插入，需要比較(

)次。A.2

B.4

C.6

D.8正確答案:

A第14

題（4分）：從待排序的序列中選出關(guān)鍵字值最大的記錄放到有序序列中，該排序方法稱為(

)。A.

希爾排序

B.

直接選擇排序

C.

冒泡排序

D.

快速排序正確答案:

B第15

題（4分）：當(dāng)待排序序列基本有序時(shí)，以下排序方法中，(

)最不利于其優(yōu)勢(shì)的發(fā)揮。A.

直接選擇排序

B.

快速排序

C.冒泡排序

D.直接插入排序正確答案:

B第16

題（4分）：對(duì)n個(gè)元素進(jìn)行冒泡排序，要求按升序排列，程序中設(shè)定某一趟冒泡沒(méi)有出現(xiàn)元素交換，就結(jié)束排序過(guò)程。對(duì)某n個(gè)元素的排序共進(jìn)行了3n-6次元素間的比較就完成了排序，則（

）。A.原序列是升序排列

B.原序列是降序排列C.對(duì)序列只進(jìn)行了2趟冒泡

D.對(duì)序列只進(jìn)行了3趟冒泡正確答案:

D第17

題（4分）：對(duì)n個(gè)元素進(jìn)行冒泡排序，通常要進(jìn)行n-1趟冒泡，在第j趟冒泡中共要進(jìn)行（

）次元素間的比較。A．j

B．j-1

C．n-j

D．n-j-1正確答案:

C第18

題（4分）：對(duì)n個(gè)元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了（

）次元素間的交換，則表明