數(shù)據(jù)結(jié)構(gòu)習題集原題序1

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)習題集原題序1其次章線性表

第1章緒論

一、選擇題7．從規(guī)律上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。

A．動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B．順序結(jié)構(gòu)、鏈式結(jié)構(gòu)

C．線性結(jié)構(gòu)、非線性結(jié)構(gòu)D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

8．以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（）。

A．循環(huán)隊列B.鏈表C.哈希表D.棧9．以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（）？

A．廣義表B.二叉樹C.稀疏矩陣D.串

10．以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（）A．棧B.哈希表C.線索樹D.雙向鏈表11．在下面的程序段中，對x的賦值語句的頻度為（）

FORi:=1TOnDO

FORj:=1TOnDO

x:=x+1;

A．O(2n)B．O(n)C．O(n2)D．O(log2n)

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

A．棧B.隊列C.完全二叉樹D.堆16．連續(xù)存儲設(shè)計時，存儲單元的地址（）。

A．一定連續(xù)B．一定不連續(xù)C．不一定連續(xù)D．部分連續(xù)，部分不連續(xù)17．以下屬于規(guī)律結(jié)構(gòu)的是（）。

A．順序表B.哈希表C.有序表D.單鏈表

二、判斷題

1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。()

2.記錄是數(shù)據(jù)處理的最小單位。()

3.數(shù)據(jù)的規(guī)律結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的規(guī)律關(guān)系；()

4．算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。()

5．頑強的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()

7．程序一定是算法。()

8．數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。()

10.在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。()

11.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()

-1-

其次章線性表

13.數(shù)據(jù)的規(guī)律結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系,它依靠于計算機的存儲結(jié)構(gòu).()三、填空

1．數(shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示。2.對于給定的n個元素,可以構(gòu)造出的規(guī)律結(jié)構(gòu)有（1），（2），（3），__（4）_四種。

3．數(shù)據(jù)的規(guī)律結(jié)構(gòu)是指。

4．一個數(shù)據(jù)結(jié)構(gòu)在計算機中稱為存儲結(jié)構(gòu)。6．數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是7.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_（1）_和_（2）_，以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應的_（3）_，設(shè)計出相應的（4）_。8．一個算法具有5個特性:（1）、（2）、（3），有零個或多個輸入、有一個或多個輸出。

15.下面程序段的時間繁雜度為________。(n>1)sum=1；

for(i=0;sum0）。

A．表元素B．字符C．數(shù)據(jù)元素D．數(shù)據(jù)項E．信息項4．若某線性表最常用的操作是存取任一指定序號的元素和在最終進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。

A．順序表B．雙鏈表C．帶頭結(jié)點的雙循環(huán)鏈表D．單循環(huán)鏈表5．某線性表中最常用的操作是在最終一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。

A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表

7．若某表最常用的操作是在最終一個結(jié)點之后插入一個結(jié)點或刪除最終一個結(jié)點。則采用（）存儲方式最節(jié)省運算時間。

A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．帶頭結(jié)點的雙循環(huán)鏈表8.靜態(tài)鏈表中指針表示的是（）.

A．內(nèi)存地址B．數(shù)組下標C．下一元素地址D．左、右孩子地址9.鏈表不具有的特點是（）

A．插入、刪除不需要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正比

12.(1)靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關(guān)。

(2)靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。(3)靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。

以上錯誤的是（）A．（1），（2）B．（1）C．（1），（2）,(3)D.（2）13.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間繁雜度為（）(1Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；

-3-

其次章線性表

B.p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C.q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

24．在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是：（）。

A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;

C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;

25．對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是（）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL

二、判斷

1.鏈表中的頭結(jié)點僅起到標識的作用。()3．線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。()4．順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。()

5.對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。()

6．順序存儲方式只能用于存儲線性結(jié)構(gòu)。()

9.線性表的特點是每個元素都有一個前驅(qū)和一個后繼。()

10.取線性表的第i個元素的時間同i的大小有關(guān).()

11.循環(huán)鏈表不是線性表.()12.線性表只能用順序存儲結(jié)構(gòu)實現(xiàn)。()13.線性表就是順序存儲的表。()14．為了很便利的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。()

15.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()

三、填空

1．當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用_______存儲結(jié)構(gòu)。2．線性表L=（a1,a2,?,an）用數(shù)組表示，假定刪除表中任一元素的概率一致，則刪除一個元素平均需要移動元素的個數(shù)是________。3．設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點,若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行以下語句:_______；______;4．在一個長度為n的順序表中第i個元素（1next;h->next=NULL;while((1)________)

{q=p;p=p->next;q->next=h->next;h->next=(2)________;}}

31.下面是用c語言編寫的對不帶頭結(jié)點的單鏈表進行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當?shù)恼Z句