云南開放大學數(shù)據(jù)結構網上作業(yè)1-8

云南開放大學數(shù)據(jù)結構網上作業(yè)1一、單項選擇題(共17題,共68分)第1

題（4分）：（

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

B．數(shù)據(jù)對象

C．數(shù)據(jù)結構

D．數(shù)據(jù)項正確答案:

B第2

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

）。A．物理結構

B．邏輯結構

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

D．給相關變量分配存儲單元正確答案:

A第3

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

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

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

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

C第4

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

）結構與所使用的計算機無關。A．邏輯

B．物理

C．存儲

D．邏輯與存儲正確答案:

A第5

題（4分）：數(shù)據(jù)的物理結構（

）。A．與數(shù)據(jù)的邏輯結構無關

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

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

D第6

題（4分）：數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的（

）結構。A．物理

B．存儲

C．邏輯與物理

D．邏輯正確答案:

D第7

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

）。A．只能有一個數(shù)據(jù)項組成

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

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

C第8

題（4分）：算法的時間復雜度與（

）有關。A．所使用的計算機

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

C．算法本身

D．數(shù)據(jù)結構正確答案:

C第9

題（4分）：同一種邏輯結構（

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

B答案解析：暫無解析第10

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

）的關系。A．一對一

B．一對多C．多對多

D．每一個元素都有一個直接前驅和一個直接后繼正確答案:

A第11

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

）的關系。BA．一對一

B．一對多C．多對多

D．每一個元素都有一個直接前驅和一個直接后繼正確答案:

B第12

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

）的關系。A．一對一

B．一對多C．多對多

D．每一個元素都有一個直接前驅和一個直接后繼正確答案:

C第13

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

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

B．確定性

C．有效性

D．有0個或多個輸出正確答案:

D第14

題（4分）：某算法的時間復雜度為O（n）,表明該算法的（

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

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

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

C第15

題（4分）：以下算法的時間復雜度為（

）。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分）：以下算法的時間復雜度為（

）。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分）：以下算法的時間復雜度為（

）。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下,時間復雜度為O(n)的算法在時間上總是優(yōu)于復雜度為O(2n)的算法。（

）正確答案:

√第19

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

）正確答案:

√第20

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

)正確答案:

×第21

題（4分）：同一種邏輯結構可以用不同的存儲結構實現(xiàn)（

）。正確答案:

√第22

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

）。正確答案:

×第23

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

）。正確答案:

×第24

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

）正確答案:

×第25

題（4分）：數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機中世紀的存儲形式。（

）正確答案:

√

云南開放大學數(shù)據(jù)結構網上作業(yè)2一、單項選擇題(共22題,共64分)第1

題（3分）：線性表是有n個（

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

B.字符

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

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

C第2

題（3分）：線性表是一個（

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

B.有限序列，不可以為空C.無限序列，可以為空

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

A第3

題（3分）：以下（

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

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

D.

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

B第4

題（3分）：在線性表中，除了開始元素外，每個元素（

）。A.只有唯一的前驅元素

B.只有唯一的后即元素字符C.有多個前驅元素

D.有多個后繼元素正確答案:

A第5

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

)。A.存儲密度大

B.插入運算方便C.刪除運算方便

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

A第6

題（3分）：對于順序表，訪問編號為i的元素的時間復雜度為（

）。A.O(n)

B.O(1)

C.O(nlog2n)

D.O(log2n)正確答案:

B第7

題（3分）：對于順序表，在編號為i處插入一個新元素的間復雜度為（

）。A.O(n)

B.O(1)

C.O(nlog2n)

D.O(log2n)正確答案:

A第8

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

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

B．n

C．n-1

D．n/2正確答案:

B第9

題（3分）：帶頭結點的單向鏈表的頭指針為head，該鏈表為空的判定條件是（

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

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

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

C第10

題（3分）：鏈表所具備的特點是（

）。A．可以隨機訪問任一結點

B．占用連續(xù)的存儲空間C．可以通過下標對鏈表進行直接訪問D．插入刪除元素的操作不需要移動元素結點正確答案:

D第11

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

）。A．n/2

B．n

C．n-1

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

A第12

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

）。A．(n-1)/2

B．n

C．2n

D．n-i正確答案:

A第13

題（3分）：設順序存儲的線性表長度為n，要刪除第i（0<=i<=n-1）個元素，按課本的算法，當i=（

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

B．n/2

C．n-4

D．4正確答案:

C第14

題（3分）：設順序存儲的線性長度為n，要在第i（0<=i<=n）個元素之前插入一個新元素，按課本的算法當i=（

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

B．n

C．1

D．n-2正確答案:

D答案解析：

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

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

）。A．n-i+1

B．n-i

C．n-i-1

D．i正確答案:

C第16

題（3分）：下述各線性結構中可以隨機訪問的是（

）。A.單向鏈表

B.雙向鏈表

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

D.順序表正確答案:

D第17

題（3分）：線性表采用鏈式存儲時，其地址（

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

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

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

C第18

題（3分）：在一個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結點的直接后繼，現(xiàn)要刪除q所指結點，可用的語句是（

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

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

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

C第19

題（3分）：在一個單鏈表中p所指結點之后插入一個s所指的結點時，可執(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分）：按照教材算法，在一個長度為n的順序表中為了刪除第5個元素，從前到后依次移動了15個元素。則原順序表的長度為（

）。A.21

B.20

C.19

D.25正確答案:

A第21

題（2分）：針對線性表，在存儲后如果最常用的操作是取第i個結點及其前驅，則采用（

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

B．雙鏈表

C．順序表

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

C第22

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

）。A．106

B．107

C．124

D．128正確答案:

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

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

）正確答案:

√第24

題（2分）：正確答案:

√第25

題（2分）：線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間。（

）正確答案:

√第26

題（2分）：正確答案:

√第27

題（2分）：線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)。（

）正確答案:

√第28

題（2分）：正確答案:

√第29

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

）正確答案:

√第30

題（2分）：正確答案:

√第31

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

）正確答案:

√第32

題（2分）：正確答案:

√第33

題（2分）：線性表的順序結構中，數(shù)據(jù)元素是不能隨機訪問的。（

）正確答案:

√第34

題（2分）：正確答案:

√第35

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

）正確答案:

√第36

題（2分）：正確答案:

√第37

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

）正確答案:

√第38

題（2分）：答案：錯正確答案:

√第39

題（2分）：順序存儲方式只適合存儲線性結構。（

）錯正確答案:

√第40

題（2分）：答案：錯正確答案:

√

云南開放大學數(shù)據(jù)結構網上作業(yè)3一、單項選擇題(共23題,共73分)第1

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

）進行。A．隊頭

B．隊尾

C．隊頭或隊尾

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

B第2

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

）進行。A．隊頭

B．隊尾

C．隊頭或隊尾

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

A第3

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

）進行。A．棧頂

B．棧底

C．棧頂或棧底

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

A第4

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

）進行。A.棧頂

B.棧底

C.棧頂或棧底

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

A第5

題（3分）：一個隊列的入隊序列是2，4，6，8，則隊列的輸出序列是（

）。A．8，6，4，2

B．2，4，6，8

C．4，2，8，6

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

B第6

題（3分）：一個隊列的入隊序列是5，6，7，8，則隊列的輸出序列是（

）。A.5

6

7

8

B.8

7

6

5C.7

8

6

5

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

A第7

題（3分）：一個棧的進棧序列是1，2，3，4，則不可能的出棧序列是（

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

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

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

B第8

題（3分）：一個棧的進棧序列是5，6，7，8，則棧的不可能的出棧序列是（

）（進出棧操作可以交替進行）A．5，8，6，7

B．7，6，8，5

C．7，6，5，8

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

A第9

題（3分）：一個棧的進棧序列是a，b，c，d，e，則棧的不可能輸出序列是（

）（進棧出?？梢越惶孢M行）。A．dceab

B．edcba

C．decba

D．abcde正確答案:

A第10

題（3分）：以下說法不正確的是（

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

C第11

題（3分）：以下說法不正確的是（

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

C第12

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

）（進棧出?？梢越惶孢M行）。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按順序依次進棧，則該棧的不可能的輸出序列是（

）。A.6

4

2

B.6

2

4

C.4

2

6

D.2

6

4正確答案:

B第14

題（3分）：棧和隊列的相同點是（

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

D第15

題（3分）：從一個棧頂指針為top的鏈棧中插入一個由P指向的新結點時，則執(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分）：設top是一個鏈棧的棧頂指針，棧中每個結點由一個數(shù)據(jù)域data和指針域next組成，設用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ù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用x保存出隊元素的值，p為指向結點類型的指針，可執(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ù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針。設p指向要入隊的新結點(該結點已被賦值)，則入隊操作為（

）。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分）：在一個鏈隊列中，假設f和r分別為隊頭和隊尾指針，則插入s所指結點的操作為（

）。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分）：在一個鏈隊列中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點的操作為（

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

B．r=r.getNext();

C．f=r.getNext();

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

D第21

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

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

B.rear==front;C.

rear%length==front;

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

A第22

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

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

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

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

D第23

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

）。A.棧

B.隊列

C.樹

D.圖正確答案:

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

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

）對正確答案:

√第25

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

）對正確答案:

√第26

題（3分）：隊列可以使用順序結構實現(xiàn)，也可以使用鏈表結構實現(xiàn)。（

）正確答案:

√第27

題（3分）：編輯軟件的撤銷編輯內容操作可以通過棧結構來實現(xiàn)。（

）正確答案:

√第28

題（3分）：瀏覽器記錄用戶的訪問地址以實現(xiàn)“回撤”操作，可以通過隊列結構來實現(xiàn)。（

）正確答案:

×第29

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

）正確答案:

×第30

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

）正確答案:

√第31

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

）正確答案:

√第32

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

）正確答案:

√

云南開放大學數(shù)據(jù)結構網上作業(yè)4一、單項選擇題(共29題,共86分)第1

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

）。A．比較

B．復制

C．賦值

D．連接正確答案:

D第2

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

）。A．1

B．0

C．“He”

D．“e”正確答案:

A第3

題（3分）：空串的長度為（

）。A．0

B．1

C．2

D．3正確答案:

A第4

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

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

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

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

A第5

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

）。A．求子串

B．連接

C．匹配

D．求串長正確答案:

C第6

題（3分）：串是（

）。A．不少于一個字母的序列

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

D．有限個字符的序列正確答案:

D第7

題（3分）：串的長度是指（

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

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

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

B第8

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

）。A．9

B．16

C．36

D．29正確答案:

D第9

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

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

B．空串是由空格構成的串C．模式匹配是串的一種重要運算

D．串即可以采用順序存儲，也可以采用鏈式存儲正確答案:

B第10

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

）。A．順序的存儲結構

B．鏈接的存儲結構C．數(shù)據(jù)元素是一個字符

D．數(shù)據(jù)元素可以任意正確答案:

C第11

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

）。A．相同

B．不相同

C．可能相同

D．無法確定正確答案:

B第12

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

）。A．兩串的長度相等B．兩串包含的字符相同C．兩串的長度相等，并且兩串包含的字符相同D．兩串的長度相等，并且對應位置上的字符相同正確答案:

D第13

題（3分）：在實際應用中，要輸入多個字符串，且長度無法預定。則應該采用（

）存儲比較合適。A．鏈式

B．順序

C．堆結構

D．無法確定正確答案:

A第14

題（3分）：對特殊矩陣進行壓縮的目的是(

)。A．表達式變得簡單

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

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

D第15

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

)個存儲單元進行保存。A．n*(n+1)/2

B．n*n/2

C.n*(n-1)/2

D.n*n正確答案:

A第16

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

)A.S[18]

B.S[13]

C.S[16]

D.S[15]正確答案:

A第17

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

)A.S[25]

B.S[16]

C.S[21]

D.S[15]正確答案:

A第18

題（3分）：設有一個10階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數(shù)組b中（數(shù)組下標從0開始），則矩陣中元素A[8][5]在一維數(shù)組b中的下標是（

）。A．b[33]

B．b[32]

C．b[85]

D．b[41]正確答案:

D第19

題（3分）：設有一個10階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣A的第一個元素為A[0][0]，數(shù)組b的下標從0開始），則矩陣元素A[5][3]對應一維數(shù)組b的數(shù)組元素是（

）。A．b[18]

B．b[8]

C．b[13]

D．b[10]正確答案:

A第20

題（3分）：設有一個12階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中（矩陣A的第一個元素為A[0][0]，數(shù)組b的下標從0開始），則矩陣A中第4行的元素在數(shù)組b中的下標i一定有（

）。A．7≤i≤10

B．11≤i≤15

C．9≤i≤14

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

D第21

題（3分）：設有一個15階的對稱矩陣a，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從0開始），則矩陣中元素a[7][6]在一維數(shù)組B中的下標是（

）。A．42

B．13

C．27

D．34正確答案:

D第22

題（3分）：設有一個15階的對稱矩陣a，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣A的第一個元素為a0,0，數(shù)組b的下標從0開始），則數(shù)組元素b[13]對應A的矩陣元素是（

）。A．a[4][3]

B．a[6][4]

C．a[7][2]

D．a[6][8]正確答案:

A第23

題（3分）：設有一個20階的對稱矩陣a，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從0開始），則矩陣中元素a[9][2]在一維數(shù)組B中的下標是（

）。A．41

B．32

C．18

D．47正確答案:

D第24

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

）個存儲空間存儲該矩陣元素。A．44

B．45

C．34

D．35正確答案:

A第25

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

）。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分）：稀疏矩陣的三元組存儲方法（

）。A．實現(xiàn)矩陣的轉置操作,只需將每個三元組行和列的下標交換即可B．矩陣的非零元素個數(shù)和位置在操作中變化不大時較有效C．是一種鏈式存儲結構D．比十字鏈表更高效正確答案:

B第27

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

）域的結點表示。A．5

B．4

C．3

D.2正確答案:

A第28

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

）功能。A．順序存儲

B．隨機存儲

C．輸入輸出

D.以上都不對正確答案:

B第29

題（2分）：以下(

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

B．循環(huán)鏈表

C．數(shù)組

D.棧正確答案:

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

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

）正確答案:

√第31

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

）正確答案:

√第32

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

）正確答案:

×第33

題（2分）：若兩個串有相同的字符集，則說明兩個串相等。（

）正確答案:

×第34

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

）正確答案:

√第35

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

）正確答案:

×第36

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

）正確答案:

√

云南開放大學數(shù)據(jù)結構網上作業(yè)5一、單項選擇題(共35題,共100分)第1

題（3分）：樹最適合用來表示（

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

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

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

C第2

題（3分）：對于一顆有n個節(jié)點的樹，其中所有度之和等于：（

）。A．n

B．n-1

C．n-2

D．n+1正確答案:

B第3

題（3分）：對于一顆有n個節(jié)點、度為4的樹來說，（

）。A．樹的高度最多為n-3

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

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

A第4

題（3分）：對于一顆高度為h、度為4的樹來說，（

）。A．至少有h+3個節(jié)點

B．至多有4h-1個節(jié)點C．至多有4h個節(jié)點

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

A第5

題（3分）：對于一顆有50個節(jié)點的，度為3的樹來說，其最小高度為（

）。A．3

B．4

C．5

D．6正確答案:

C第6

題（3分）：對于一顆度為4的樹來說，若有20個度為4的節(jié)點，10個度為3的節(jié)點，1個度為2的節(jié)點，10個度為1的節(jié)點，則樹有多少個葉子節(jié)點：（

）。A．41

B．82

C．115

D．122正確答案:

B第7

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

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

D第8

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

）。A．4

B．5

C．6

D．7正確答案:

C第9

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

）。A．2h

B．2h-1

C．2h-1

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

C第10

題（3分）：具有10個葉子節(jié)點的二叉樹有（

）個度為2的節(jié)點。A．8

B．9

C．10

D．11正確答案:

B第11

題（3分）：一個具有1025個節(jié)點的二叉樹的高度為（

）。A．11

B．10

C．11~1025

D．12~1024正確答案:

C第12

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

）。A．0

B．1

C．2

D．不確定正確答案:

A第13

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

）。A．n=h+m

B．h+m=2n

C．m=h-1

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

D第14

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

）。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分）：若二叉樹的中序遍歷結果是abcdef，且c為根節(jié)點，則（

）。A．節(jié)點C有兩顆子樹

B．二叉樹有兩個度為0的節(jié)點C．二叉樹的高為5

D．以上都不對正確答案:

A第16

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

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

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

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

C第17

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

）。A．先序序列

B．中序序列

C．中序和后序序列

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

C第18

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

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

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

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

D第19

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

）。A．3

B．2

C.4

D.5正確答案:

C第20

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

）。A．DBEFCA

B．DEBFCA

C.DFEBCA

D．DBFECA正確答案:

A第21

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

）。A．E

B．F

C.G

D．H正確答案:

C第22

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

）。A．ACBED

B．DECAB

C.DEABC

D．CEDBA正確答案:

D第23

題（3分）：對二叉排序樹進行（

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

B．前序

C．中序

D．后序正確答案:

C第24

題（3分）：深度為5的完全二叉樹第5層上有4個結點，該樹一共有（

）個結點。A．28

B．30

C．31

D．19正確答案:

D第25

題（3分）：深度為5的完全二叉樹共有20個結點，則第5層上有（

）個結點(根所在結點為第一層)。A．3

B．8

C．5

D．6正確答案:

C第26

題（3分）：一棵哈夫曼樹共有n個非葉結點，則該樹一共有（

）個結點。A.2*n-1

B.2*n+1

C.2*n

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

B第27

題（3分）：一棵哈夫曼樹共有n個非葉結點，則該樹有（

）個葉結點。A．n

B．n+1

C．n-1

D．2n正確答案:

B第28

題（3分）：一棵哈夫曼樹共有n個葉結點，則該樹有（

）個非葉結點。A．n-1

B．n

C．n+1

D．2n正確答案:

A第29

題（3分）：一棵哈夫曼樹有n個葉子結點（終端結點），該樹總共有（

）個結點。A．2n-2

B．2n-1

C．2n

D．2n+2正確答案:

B第30

題（3分）：設有13個權值的結點，用它們組成一棵哈夫曼樹，則該樹有（

）個結點。A．13

B．12

C．26

D．25正確答案:

D第31

題（2分）：一棵哈夫曼樹總共有23個結點，該樹共有（

）個葉結點（終端結點）。A．10

B．13

C．11

D．12正確答案:

D第32

題（2分）：一棵完全二叉樹共有30個結點，則該樹的高度是（

）。A．6

B．4

C．3

D．5正確答案:

D第33

題（2分）：一棵完全二叉樹的高度是5，最后一層上有6個結點，該樹共有（

）個結點。A．30

B．20

C．21

D．23正確答案:

C第34

題（2分）：一棵有n個結點采用鏈式存儲的二叉樹，則該樹共有（

）個指針域為空。A．2n

B．2n+1

C．2n+2

D．n+1正確答案:

D第35

題（2分）：在一棵二叉樹中，若根的編號從0開始,若編號為i的結點存在右孩子，則右孩子的順序編號為（

）。A．2i

B．2i-1

C．2i+2

D．2i+1正確答案:

C

云南開放大學數(shù)據(jù)結構網上作業(yè)6一、單項選擇題(共23題,共100分)第1

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

）倍。A.1/2

B.1

C.2

D.4正確答案:

C答案解析：無向圖中，一條邊計入兩個頂點的度數(shù)。第2

題（5分）：有n個頂點的無向圖，最多有（

）條邊。A.n

B.n(n-1)

C.n（n-1）/2

D.2n正確答案:

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

題（5分）：在一個具有n個頂點的無向圖中，要連通全部頂點至少需要（

）條邊。A.n

B.n+1

C.

n-1

D.n/2正確答案:

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

題（5分）：在無向圖中，定義頂點i到頂點j的路徑，是從頂點i到頂點j的一個（

）。A.頂點序列

B.頂點個數(shù)

C.權值之和

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

A答案解析：路徑是由頂點序列構成的。第5

題（5分）：在n個頂點的連通圖中，任意一條簡單的路徑，其長度不可能超過（

）。A.1

B.n/2

C.n-1

D.n正確答案:

C答案解析：若路徑長度超過n-1,則其中必存在重復的頂點。第6

題（5分）：以說法錯誤的是（

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

A答案解析：一個有向圖可以有很多頂點沒有邊。第7

題（5分）：對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣大小是（

）。A.n

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

C.n-1

D.n*n正確答案:

D答案解析：含有n個頂點的圖采用鄰接矩陣存儲，矩陣大小為n*n。第8

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

）。A.n

B.2e

C.e

D.n+e正確答案:

B答案解析：

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

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

）。A.n

B.2e

C.e

D.n+e正確答案:

C答案解析：

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

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

）。A.完全圖

B.連通圖

C.有回路

D.一棵樹正確答案:

B答案解析：

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

題（4分）：一個無向連通圖的生出樹是含有該連通圖的全部頂點的（

）。A.極小連通子圖

B.極小連通圖

C.極大連通子圖

D.極大子圖正確答案:

A答案解析：生成樹是含有全部頂點的極小連通子圖。第12

題（4分）：最小生成樹是指（

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

A第13

題（4分）：求最短路徑的Dijkstra算法的時間復雜度為（

）。A.O(n)

B.O(n+e)

C.O(n2)

D.

O(ne)正確答案:

C第14

題（4分）：求最短路徑的Floyd算法的時間復雜度為（

）。A.O(n)

B.O(n+e)

C.O(n2)

D.

O(n3)正確答案:

D第15

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

）。A.

sB.s-1C.

s+1D.n正確答案:

A第16

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

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

B第17

題（4分）：具有6個頂點的無向圖至少應有（）條邊才能確保是一個連通圖。A.5B.6C.7D.8正確答案:

A第18

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

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

C第19

題（4分）：任何一個無向連通圖的最小生成樹（

）。A.至少有一棵

B.只有一棵

C.一定有多棵

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

A第20

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

）。A．2m

B．m

C．2m+1

D．m/2正確答案:

A答案解析：一條邊連接兩個頂點，可以記為兩個頂點的度。第21

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

）。A．4

B．8

C．12

D．9正確答案:

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

題（4分）：以下說法不正確的是（

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

D第23

題（4分）：以下說法正確的是（

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

D

云南開放大學數(shù)據(jù)結構網上作業(yè)7一、單項選擇題(共25題,共100分)第1

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

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

A第2

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

）不需要進行關鍵字的比較。A．快速排序

B．歸并排序

C．基數(shù)排序

D．堆排序正確答案:

C第3

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

）。A．快速排序

B．希爾排序

C．基數(shù)排序

D．堆排序正確答案:

C第4

題（4分）：將1000個英文單詞進行排序，采用（

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

B．直接插入排序

C．堆排序

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

D第5

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

）。A．在外存上進行的排序方法B．不需要使用內存的排序方法C．數(shù)據(jù)很大，需要人工干預的排序方法D.排序前后數(shù)據(jù)在外存，排序時數(shù)據(jù)調入內存的排序方法正確答案:

D第6

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

）。A.直接插入排序

B．簡單選擇排序

C．快速排序

D．歸并排序正確答案:

A第7

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

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

D第8

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

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

B．堆排序

C．二路歸并排序

D．冒泡排序正確答案:

B第9

題（4分）：在下列排序算法中，哪一種算法的時間復雜度與初始排序序列無關（

）。A．直接插入排序

B．冒泡排序

C．快速排序

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

D第10

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

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

B.冒泡排序

C.插入排序

D.堆排序正確答案:

C第11

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

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

B．希爾排序

C．快速排序

D．歸并排序正確答案:

D第12

題（4分）：一組記錄的關鍵字為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為支點得到的一次劃分結果為（

）。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分）：在對一組關鍵字序列{70，55，100，15，33，65，50，40，95}，進行直接插入排序時，把65插入，需要比較(

)次。A.2

B.4

C.6

D.8正確答案:

A第14

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

)。A.

希爾排序

B.

直接選擇排序

C.

冒泡排序

D.

快速排序正確答案:

B第15

題（4分）：當待排序序列基本有序時，以下排序方法中，(

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

直接選擇排序

B.

快速排序

C.冒泡排序

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

B第16

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

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

B.原序列是降序排列C.對序列只進行了2趟冒泡

D.對序列只進行了3趟冒泡正確答案:

D第17

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

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

B．j-1

C．n-j

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

C第18

題（4分）：對n個元素進行冒泡排序若某趟冒泡中只進行了（

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